谭 劲，张曼曼，禇 娜

(中国计量学院，杭州310018)

无线传感网络再编程(Reprogramming)通常由两部分组成:传感节点上已装入更新代码的安装机制和分布更新软件到传感节点的传播机制。安装机制负责将到达的软件代码重启动，这涉及到重写闪存和微控制器复位等技术问题，属于操作系统与硬件结构研究的范畴;传播机制负责及时、安全、可靠地更新代码传播到网络中的各个节点，属网络协议研究的范畴。目前安装机制方面的技术相对成熟，第二代传感节点已经具备再编程的能力(远程节点程序更新)，新的第三代节点还支持硬件重配置(Reconfiguration)［1］，因而传感网络再编程传播协议成为当前研究的重点［2－5］。这些研究将整个软件影像分成许多段或包，然后采用泛洪方式将段或包分发到网络中的不同节点，其研究重点集中在用较低的资源消耗和较少的端到端延迟可靠地将更新的软件影像分发到网络中的每个节点。为了支持流水线操作以便加速多跳网络中的再编程效率，引入了管道(Pipelining)的概念［3］;通过 ADV(广告)－REQ(请求)－DATA(数据)三次握手协商传输，避免了代码冗余传输而提高了再编程的可靠性［4－5］;层次结构Sprinkler［2］由于采取层次结构减少了控制包的数量，从而加快了代码分发的速度。

然而，已有的传感网络再编程协议大多假定网络中所有节点的功能是相同的(Homogeneous)，运行同一版本的应用程序，因而将同一软件影像分发到整个网络，没有考虑再编程节点的范围选择问题［6］。在实际中，许多传感网络往往分成了许多组，不同的节点或组完成不同的任务，为了增强网络的可靠性和延长整个网络的生命周期，传感节点感知的对象、通信能力、CPU处理能力等都是异类的(Heterogeneous)［7－8］。因此，一个传感网络中可能有多个不同功能的应用程序，这就需要传输协议动态地选择一定范围的节点进行再编程某种类型应用程序的所有节点。

本文提出了一种新的具有范围选择的再编程协议，该协议变传统的ADV－REQ－DATA三次握手协议为路由形成、代码传送、请求丢失包三个阶段协议，有效地降低了参与代码转发的中间节点数;中间节点通过获取一跳范围内希望接收更新代码数据的节点序列，采取单播或组播方式有针对性传送更新代码，而不是泛洪式的广播，减少了REQ确认信息包，并能统计出参与代码更新的同类节点数和代码转发的异类中间节点数。性能分析与模拟实验表明:该协议在平均延时、能量消耗等方面优于传统的Aqueduct。

1 相关工作

范围选择允许管理员或网络动态选择指定的节点集进行再编程，这不仅减少了参与再编程的节点数，还能降低整个网络能量消耗，但目前具有范围选择的研究相对较少，已有的研究主要分为静态网络［9－13］和移动网络［14－16］两部分。在静态网络方面，文献［9－10］是较早进行这方面的初步研究。Aqueduct［9］是一种异质网络代码分发协议，网络中的节点分为转发节点(不需进行代码更新，只起连接传输路径的作用)和成员节点(需要进行代码更新)两类，减少了参与代码更新的节点数，成员节点缓存所有代码，转发节点缓存部分经过转发的代码;Aqueduct与我们提出的协议网络环境相似，但它是在传统的ADV－REQ－DATA三次握手协议的基础上增加了范围选择功能，是一种数据包级的范围选择协议。TinyCubus［10］为异质网络提出了一种跨层的框架，由数据管理框架、跨层框架和配置引擎三部分组成;前两部分支持异质传感网络中数据获取，配置引擎采用一种灵活的描述语言并使用规则进行范围选择，如“通过检测振动的节点再编程检测温度的节点”，但该方案不能保证到达所有目标节点并进行再编程［6］。Melete［11］通过将节点分组(如监视一个房间温度的所有节点)构造一个“转发区域”来控制再编程节点的范围，并假设连接节点的网关存储所有应用程序代码;然而，如果节点的物理位置不在一个组内，再编程的范围将增长到整个网络［12］。Starburst SSD［12］引入了 Hub 节点(类似于文献［11］中的网关)，根据网络拓扑结构和动态性，一个节点子集动态地选择连接到不同的Hub;并在数据包中加入字段来限制再编程范围，例如，字段表达式＜VariabledId，Operator，Operand1，Operand2 ＞ 中 的VariabledId是发布变量，Operator是比较操作符，后面两个参数为操作数，如再编程“感知温度超过70℃的节点”;由于更新代码分成了许多包，节点接收每个包都要进行运算来检测自己是否接收该数据，会消耗节点的能量;此外，这种依靠规则来选择范围有可能带来更新代码不兼容问题，也就是说不同硬件或操作系统平台的节点可能都满足指定的规则而更新为相同的软件。文献［13］提出了一种基于模块化的再编程方案，将软件代码分为全局模块(运行于所有节点)与局部模块(运行部分节点)，再编程任务分为插入(Insert)、更新(Update)、删除(Delete)三种操作;更新/删除通过比较节点已装入的模块来确定节点的范围，而插入新模块通过在Sink节点中加入元数据(MetaData)来限制插入节点的范围，但该方案对节点的软件设计与存储器分配机制提出了新要求。

ReMo［14］较早地进行了无线移动传感网络环境下的再编程研究，其思路是在节点移动过程中，根据节点密度而动态地调整Advertisement的广播速率，选择链接优良的节点进行代码交换，减少参与代码传播的节点数从而节省能量;但探测节点周围其它节点密度需要耗费比较多的能量，并且不一定准确，该研究不具备节点范围选择。Pasztor等人提出野生动物监测传感网络具有范围选择的再编程研究［15－16］，该方案基于野生动物(如大象)群体的个体交互，利用它们的存在和关系(社会行为)进行具有节点范围选择的代码更新;但该方案需要一种新的网络拓扑结构，Sink或节点一方是可移动的，或者它们都是可移动的，这涉及到移动路线、方式、速率等问题。

2 系统模型

为了描述方便，本研究的系统模型如下:

(1)整个网络有一个Sink(基站)，M个节点随机分布在一个二维区域A;其中M个节点分为T类，每类节点有 Nii∈(1，T)，M=N1+…+Ni+…+NT;每个节点拥有唯一的ID(Sink的ID为0)，且都能通过同类或非同类节点将自己感知的数据通过单跳或多跳的方式传送到Sink，如图1所示，图中有正方形、圆形、菱形三类节点，对菱形节点进行代码更新;

(2)再编程是网络管理员对部署好的传感网络发起的强制性操作，Sink知道每类节点的个数Ni，i∈(1，T);

(3)同类节点运行相同版本的应用程序Vi，i∈(1，T);

(4)更新的代码分为在Sink端分为P1P2…PC段，每段 Pk，k∈(1，C)的长度为 L(最后一段 PC可以小于L);

(5)每个节点配备足够的NAND闪存，接收到的每一个代码段Pk按顺序存放于NAND闪存中;节点执行重启动后，新的应用程序从NAND闪存转入内存中;

(6)和其它研究相同，节点是静止的，且无线通信为双向的;由于再编程过程相对于传感网络工作过程来说是很短暂的，假定这期间节点不会故障且没有新的节点加入;

(7)没有类似于文献［11－12］中的Hub节点，不需要节点的任何位置信息。

图1 再编程网络结构(对菱形节点进行代码更新)

3 协议描述

本文提出的协议分为3部分:

①路由形成 在代码传送前，先形成到所有选择节点的路由，排除不参与代码更新的节点，类似与传感网络数据收集中的AODV、DSR［17］等路由发现阶段，但这些协议是End-to-End，而再编程是Oneto-Many协议;

②代码传送 形成路由后，代码传送变成了一条范围内的单播或组播，而不是传统协议中的广播;

③请求丢失包 参与代码更新的节点请求丢失的数据包(单播方式)。

3．1 节点类型

传感网络再编程是对已经部属好并且可能运行一段时间后的节点进行代码更新，在我们的协议中，使用了3种类型节点:同类边界节点、同类中间节点、异类中间节点。每个节点收到消息(见§3．2协议消息)时，能确定自己属于哪类节点。

同类边界节点:指网络中那些自己感知数据，不转发其它同类节点感知数据，又需要进行代码更新的节点，如图1中的i，r，t等节点;同类边界节点只接收消息和相关数据，不再进行转发消息和数据。与之对应的异类边界节点(a，l，o)在确定自己是异类后(不同Vi)，不接收相关数据，也不转发消息。同类边界节点可能变成异类中间节点，如图1中的y，v在对圆形节点更新代码时就变成异类中间节点。

同类中间节点:指那些自己感知数据且转发其它节点感知数据的同类节点(相同Vi)，这类节点接收更新代码后，自己变成源节点，并向周围节点转发，如图 1 中的 b，d，f，m 等节点。

异类中间节点:指那些自己感知数据且转发其它节点感知数据的异类节点(不同Vi)，这类节点只起中间桥接作用转发数据，不保存数据，如图1中的e，g，j，p 等节点。

3．2 协议消息

本协议中使用了6种消息，消息格式见图2。

Rcreation:形成路由，消息中的“同类数据源节点ID”与“异类中间转发节点ID”只有一个是有效的，最开始由Sink发出(“同类数据源节点ID”为0)，“最大跳数Max”为Sink接收感知数据时获得到最远节点的距离;中间节点(同类和异类)收到Rcreation后(可能有多个)，选择 Hop最小的Rcreation(如果Hop相同，选择先到的)，将Max减1后保存该消息，形成该消息备份，并做如下处理:(1)同类中间节点将原“同类数据源节点ID”改为自己的ID，“异类中间转发节点ID”置为空，并将跳数(Hop)置为0，继续广播新的Rcreation;(2)异类中间节点将原“同类数据源节点ID”置为空，“异类中间转发节点ID”改为自己的ID，并将跳数(Hop)加1，继续广播新的Rcreation;如果再收到Rcreation消息，比较消息中的“更新软件版本Vi”，相同版本不作处理。

Rresponse:路由响应，最开始由同类边界节点发出Rresponse，说明该节点参与再编程，如图1中的 k，x，r，t，q，y 等;“发出节 ID”为边界节点自身ID，“同类节点计数HemoCount”设置为1。在一个时间段内，同类边界节点可能收到多个Rcreation消息，选择Hop最小的Rcreation(如果Hop相同，选择先到的)保存，Rcreation消息中的“同类数据源节点ID”或“异类中间转发节点ID”作为Rresponse消息中的“数据源节点ID”，单播给数据源节点。如图1中的节点y，会收到来自节点 g(Hop=2)和节点f(Hop=0)的两条Rcreation，就选择f作为数据源节点;而对于节点 i，节点w，d发出的Rcreation消息Hop都为0，就按时间先后顺序了。

对于中间节点(同类或异类)，将收到的多个Rresponse中的“同类节点计数HomoCount”或“异类节点计数HeteroCount”进行累加，并在存储器中形成“接收节点ID序列”(序列的长度等于收到的Rresponse消息数)用于后续代码传送。表1列出了中间节点 s，p，n，m，j，f，b 形成的 Rresponse 中相关字段的值。

表1 中间节点 s、p、n、m、j、f、b 形成的 Rresponse 消息

中间节点如果在规定的时间内(见§3．3协议算法)接收不到Rresponse，就不参与代码转发了，如图1中的节点v，h节点，但同类中间节点v要参与代码接收。

Dadv与Dsend:数据广告与数据发送，形成路由后，最开始由Sink发出，中间节点收到Dadv后，将在路由形成时生成的“接收节点ID序列”复制到Dadv“接收节点ID序列”字段中，采取单播或组播(而不是广播)的方式传送代码数据。

Drequest与Dresend:由同类边界或中间节点发出Drequest，同类中间或Sink节点发出Dresend。接收数据时，如果由于某种原因(校验位出错)需要重传输某个数据包，就由请求节点向该节点生成的Rresponse消息中“数据源节点”单播发出Drequest(“目标节点序列”字段为请求节点的ID);如果该数据源节点(同类)有请求的代码包Pk，就在单跳范围内将Pk单播Dresend给请求节点;否则就在Drequest消息的“目标节点序列”中添加该节点ID，并向它的数据源节点转发Drequest;经历几跳后，如果某个数据源节点有代码包Pk，就向请求节点单播发送Dresend(该消息中的“目标节点序列”为逆向的Drequest消息中“目标节点序列”)。

3．3 协议算法

本协议的基本思想就是先形成完整的代码传送路由，排除参与代码转发的异类中间节点、同类中间节点，变传统再编程的广播为单播或组播，从而节省整个网络的能量消耗和提高再编程的效率，作为再编程的总指挥Sink节点，在形成路由时，还获得了“同类节点计数 HomoCount”、“异类节点计数 HeteroCount”等信息。

协议的关键是路由形成时间段的确定，由于Sink知道最远边界节点到Sink的距离H(跳数)，并将此值作为开始的 Rcreation消息重“最大跳数Max”字段的初值，Rcreation每经过一个中间节点，其Max减1;假定在1跳范围传输Rcreation消息的时间为τ，则形成路由总的时间(Sink发出Rcreation消息后，收到Rresponse消息的时间间隔)的最大值为2·H·τ。总段数C与某段代码段Pk保证节点乱序接收到某代码段后能写入NAND闪存中的正确位置，接收完C段代码后确定接收完成;如果节点有丢失或出错的数据包，通过周期性地广播Drequest获取。图3为同类中间节点si算法的主要部分流程图，协议的主要操作过程如下:

(1)Sink将更新的代码分为P1P2…PC段，获得本次传输的代码段最大值C。

(2)Sink确定填写“更新软件版本Vi”、“最大跳数Max”等值后，发出形成路由Rcreation消息。

(3)中间节点收到Rcreation，通过比较Vi就知道自己属于同类中间节点或是异类中间节点，并按中间节点类型处理并转发(广播)Rcreation消息(见§3．2 协议消息)。

(4)同类边界节点收到Rcreation消息，向上一级节点单播Rresponse消息。

(5)中间节点收到Rresponse，形成向上级(同类源节点或异类中间节点)路由和向下级(接收代码)节点 ID序列等信息，并向上一级节点单播Rresponse消息(见 §3．2 协议消息)。在 2·Max·τ时间范围内(注意Max在不同级的中间节点值是不同的)没有收到Rresponse消息的节点就不再参与代码转发了。

(6)Sink收到Rresponse消息(大于等于1条)后，具有范围选择的代码传送路由形成完毕，通过累加，获取了全网参与代码更新的“同类节点计数HomoCount”和“异类节点计数HeteroCount”信息。

(7)Sink循环发送(单播或组播)Dadv与Dsend，异类中间节点只转发Dadv与Dsend，同类中间节点接收并转发Dadv与Dsend(也有只接收不转发的同类中间节点，如图1中的v节点)。

(8)同类中间节点或同类边界节点可以通过发出Drequest请求丢失的代码包。

(9)接收完C段代码后，节点执行重起动运行新的代码。

图3 中间节点算法流程图

4 性能分析

4．1 减少REQ消息数与代码传输总时间

本协议先在2·H·τ时间内形成路由和接收代码节点序列，排除不参与更新代码转发的中间同类和异类节点，中间节点在一跳范围内采取单播或组播的方式传送更新代码给接收代码节点序列，减少了大量REQ确认信息包。在传统的ADV－REQDATA三次握手该协议中，对每一个数据包，数据源节点(Sink或中间节点)先发出ADV消息后，需要等待一个时间片δ接收需要DATA节点发出的REQ消息后，才发送DATA，但众多的REQ会带来类似于确认爆炸(ACK Implosion)问题［18］。而我们提出的协议在形成路由时发送一次(Rresponse，相当于REQ)，由于Dadv消息中带有接收代码节点序列，收到Dadv的节点知道应该接收后续的Dsend，数据源节点不需要等待REQ消息，用TotalRt、TotalTt和TotalRo、TotalTo分别表示传统协议和我们提出协议总的REQ数、传送完代码总的时间，则(λ为在一跳范围内传送代码段Pk的时间):

由于Pk远大于 Rcreation和 Rresponse，δ为等待多个REQ的时间，因而λ远大于τ，δ大于τ。因此，我们的方案优于传统的三次握手该协议;代码段C越大，我们的方案越优。

4．2 平均延时与能量消耗

我们提出协议为三阶段协议ThreeStages，其网络模型与Aqueduct相似，网络中没有Hub、网关等专用节点，全是可再编程的不同类型节点。因此，我们比较ThreeStages与Aqueduct的性能。在不同代码大小传输下，我们在OMNet++4．0网络仿真环境下比较两种协议的性能。我们假定传感节点随机分布在7×7的网格内，节点总数为49，再编程范围为菱形节点，总数为20个，圆形节点为29个，如图4所示。模拟参数见表2，模拟结果见图5、图6。

图4 模拟实验节点分布图(菱形为再编程节点)

表2 模拟参数

图5 不同更新代码大小下的平均延时

从图5中可以看出，在传输完不同大小代码影像(30 k～80 k)的平均延时方面，ThreeStages明显优于Aqueduct，原因是ThreeStages是先形成路由，再传送代码;而Aqueduct是在ADV－REQ－DATA的基础上增加了转发功能，也就是说中间节点在转发每一个代码数据段Pi时，都需要等待一个时间片δ;而ThreeStages只在路由形成阶段需要等待，延时的主要部分是Pi的传输时间。

图6 不同更新代码大小下的消息总数

我们没有直接测试每个节点的能量消耗，而是统计出所有节点转发的消息数。因为发送/接收消息远比计算指令更耗费能量。在图6中，由于ThreeStages在路由形成的2·H·τ时间内，采用泛洪的广播方式转发了比较多的消息;而在代码传送阶段采取组播或单播的形式传送，有效地减少了中间节点数，从而减少了消息数。例如，在代码传送阶段，Sink只需要单播给左上角的菱形节点，紧靠该节点的两个圆形节点不参与代码转发了。但是，在重传输率比较大时(50%)，由于ThreeStages没有采取异类中间节点缓存，消息数增加明显，这是该协议需要改进的地方。

5 结论

已有的传感网络再编程协议大多假定网络中所有节点，运行同一版本的应用程序，没有节点范围选择，基于泛洪的代码传送方式尽管能在很短的时间内将更新代码传遍整个网络，但也带来了很多不必要的消息开销。本文提出了一种新的具有范围选择的再编程协议，该协议变传统的ADV－REQ－DATA三次握手该协议为路由形成、代码传送、请求丢失包三个阶段协议，有效地降低了参与代码转发的中间节点数，提高了代码传送的有效性。接下来准备将缓存相关理论引入代码传送中，研究有效的缓存策略算法，进一步完善本协议。

［1］ Kateeb A E．Hardware Reconfiguration Capability for Third-Generation Sensor Nodes［J］．Computer，2009，42(5):95－97．

［2］ Vinayak N，Anish A，Prasun S，et al．Sprinkler:A Reliable and Energy Efficient Data Dissemination Service for Extreme Scale Wireless Networks of Embedded Devices［J］．IEEE Transactions on Mobile Computing，2007，6(7):1－13．

［3］ Krasniewski M D，Panta R K，Bagchi S，et al．Energy-Efficient On-Demand Reprogramming of Large-Scale Sensor Networks［J］．ACM Transactions on Sensor Networks，2008，4(1):Article 2．

［4］ Kulkarni S，Wang L．Energy-Efficient Multihop Reprogramming for Sensor Networks［J］．ACM Transactions on Sensor Networks，2009，5(2):16．

［5］ 谭劲，康顺利，金宁．一种基于OLSR的传感网络再编程可靠与能量有效传输协议［J］．传感技术学报，2010，23(8):1146－1152．

［6］ Wang Q，Zhu Y Y，Cheng L．Reprogramming Wireless Sensor Networks:Challenges and Approaches［J］．IEEE Networks，2006，20(3):48－55．

［7］ Shilpa M，Jyoteesh M．Energy Efficient Control Strategies in Heterogeneous Wireless Sensor Networks:A Survey［J］．International Journal of Computer Applications，2011，14(6):31－37．

［8］ 潘巨龙，李善平，吴震东，等．一种基于无线传感器网络安全的社区卫生保健监护系统设计［J］．传感技术学报，2009，22(6):838－843．

［9］ Phillips L A．Aqueduct:Robust and Efficient Code Propagation in Heterogeneous Wireless Sensor Networks［D］．Master’s thesis，University of Colorado，2005．

［10］ Pedro J M，Daniel M，Andreas L，et al．TinyCubus:An Adaptive Cross-Layer Framework for Sensor Networks［J］．Information Technology，2005，47(2):87－97．

［11］ Yu Y，Rittle L J．Supporting Concurrent Applications in Wireless Sensor Networks［C］//Proc．of the 4th International Conference on Embedded Networked Sensor Systems，Boulder，Colorado，USA，November 2006．

［12］ Tahir A，Qasim M，Philip L．Starburst SSD:An Efficient Protocol for Selective Dissemination［C］//Proc．of the IEEE International Conference on Communications，Dresden，Germany，June 2009．

［13］ Lee S H，Choi L，Nah Y．Policy-Based Reprogramming for Wireless Sensor Networks［C］//Proc．ofthe13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops，Carmona，Sevilla，Spain，May 2010．

［14］ De P，Liu Y，Das S K．ReMo:An Energy Efficient Reprogramming Protocol for Mobile Sensor Networks［C］//Proc．of Sixth Annual IEEE International Conference on Pervasive Computing and Communications，Hong Kong，March 2008．

［15］ Pasztor B，Mottola L，Mascolo C，et al．Selective Code Dissemination in Mobile Wireless Sensor Networks［C］//Proc．of the ACM/IFIP/USENIX Middleware Conference Companion， Leuven，Belgium，December 2008．

［16］ Pasztor B，Mottola L，Mascolo C，et al．Selective Reprogramming of Mobile Sensor Networks through Social Community Detection［C］//Proc．of the European Conference on Wireless Sensor Networks，Coimbra，Portugal，February 2010．

［17］ Jeya Kumar M K，Rajesh R S．A Survey of MANET Routing Protocols in Mobility Models［J］．InternationalJournalofSoft Computing，2009，4(3):136－141．

［18］ Yamamoto K，Sawa Y，Yamamoto M，et al．Performance Evaluation of ACK-Based and NAK-Based Flow Control Schemes for Reliable Multicast［C］//Proc．of IEEE TENCON 2000，Kuala Lumpur，Malaysia，September 2000．