一种基于多播分发树的无线传感器网络代码分发协议*

任万春， 马廷淮， 刘 琦

(南京信息工程大学 计算机与软件学院，江苏 南京 210044)

0 引 言

无线传感器网络(WSNs)在实地部署之后,随着用户需求的变化和技术的进步,不可避免地需要修改传感器节点的软件功能或者修复节点软件中存在的问题。传感器节点可能部署在环境非常恶劣的人类不可抵达区域(如火山、深海)，人工回收传感器节点也有可能破坏监测过程(如鸟类生活习性监测)，因此，人工烧录节点的方式不能满足实际应用的需要。使用代码分发协议通过无线方式进行代码更新是上述问题的有效解决途径[1]。代码分发协议已经成为现阶段无线传感器网络研究的热点问题。

Deluge协议[2]是TinyOS系统的标准代码分发协议，采用ADV-REQ-DATA三次握手机制和NACK(negatrue acknowledge)机制来保证可靠性。该协议提出了分页机制，使得网络能够使用流水线进行空间多路分发，大大提高了分发速度。

Typhoon协议[3]使用Snoop机制进行数据侦听，在进行快速重传的同时，降低了数据碰撞概率，使用信道转换技术解决了隐蔽站问题，提高了空间多路传输的效率。

ECD协议[4]提出了一种基于链路质量的发送节点选择算法，该算法选择链路质量最优的节点作为发送节点，提高了发送节点选择的精确度。此外,该协议能够动态地对数据包大小进行配置，极大提高了代码分发的效率。

SYNAPASE++协议[5]使用无比率喷泉码对数据包进行错误恢复，通过降低数据包重传次数提高代码分发效率,同时采用了基于NACK的ARQ错误恢复机制进一步提高了代码分发效率。

综上所述，传统的代码分发协议基于传染病[6]机制通过广播方式进行数据传输，网络中所有节点都要参与代码分发并接收到完整的新代码文件。在实际应用中，不同传感器节点的硬件结构可能不同，不同传感器节点也可能需要负责不同的感知或通信任务，这样就造成不同传感器节点执行的代码镜像文件的差异，对不同类型的节点需要分发不同的代码镜像文件。使用传染病算法对特定目标节点进行代码分发有以下不足：1)冗余代码镜像的传输浪费大量的网络资源；2)所有节点参与代码分发，对网络监测应用造成影响。

因此，本文提出了一种基于多播分发树的代码分发(multicast dissemination tree-based code dissemination，MTCD)协议。MTCD协议通过建立分发树将代码文件发送到网络中指定的目标节点上，使得在面向特定目标节点进行代码分发时，降低参与代码分发节点的数目，避免冗余代码数据的传输。

1 MTCD协议的模型

1.1 MTCD协议的原理

MTCD协议能够将代码镜像文件分发到网络中指定的目标节点中，其核心在于建立以基站节点为树根节点的多播分发树。如图1所示，MTCD协议通过广播发送代码版本消息，使网络中所有节点建立到基站节点的路由路径，形成以基站节点为根节点的多播分发树。指定目标节点向其上游节点发送代码请求消息，代码请求消息通过分发树多跳传输到基站节点。基站节点在接收到目标节点的代码数据请求后，沿着代码请求的路径将代码数据发送到目标节点。

图1 MTCD协议的代码分发过程

1.2 代码版本广播

用户将编译好的代码镜像文件通过串口发送到基站节点，当基站节点接收到完整的代码镜像文件后，开始广播发送代码版本消息，代码版本消息描述了代码镜像的摘要信息，其中标识号(UID)是每个代码文件的唯一标识；类型号(Type)用来区分传感器网络中不同类型的传感器节点；版本号码(CodeVersion)代表代码镜像文件的版本号码；代码大小(CodeSize)和页数(PageNum)用来描述代码文件的大小和代码文件包含的页数；TTL用来描述代码版本消息的生存周期；序列号(SequenceNum)用来区分不同广播周期发送的代码版本消息。MTCD协议使用泛洪方式发送代码版本消息，在泛洪的过程中，网络中的每个节点都选择一个邻居节点作为其父节点，这样就建立了以基站节点为根节点的分发树。

1.3 代码数据请求

由于代码文件占用存储空间很大(10～50 kB)，远远超过节点的内存容量，因此，代码镜像文件被划分为固定大小的页，页被划分为固定大小的数据包，如图2所示。每页的数据量占用内存较小，能够满足节点的内存容量要求，基站节点到目标节点的数据传输以页为单位进行。目标节点通过发送代码请求消息来请求页面数据，代码请求消息沿着分发树进行页面数据请求，基站节点作为分发树的根节点逐页发送数据。代码请求消息中包含节点自身ID、目标节点ID、请求页号、请求数据包号。目标节点只有在完整接收到一个页的数据后，才进行下一个页的请求。

图2 代码镜像文件划分

1.4 代码数据发送

节点接收到下游节点发送的代码请求消息后，向其父节点进行代码数据请求。代码请求从目标节点经过中间节点转发到基站节点，基站节点接收到代码请求消息后，将代码数据封装在代码数据消息中发送。代码数据消息包括下游请求节点ID、目标节点ID和代码数据。代码数据沿着分发树从基站节点先发送到离基站较近的中间节点，然后通过多跳传输到目标节点。

2 多播分发树的建立与维护

MTCD协议的核心在于通过基站节点到目标节点之间的路由路径来进行代码数据的分发。路由路径的建立基于网络中节点的邻居节点表和请求节点表。邻居节点表用来记录邻居节点的状态信息，每条记录包含邻居节点ID、邻居节点到基站的跳数、邻居节点到本节点的链路质量、以及邻居节点是否为本节点的父节点。请求节点表用来记录向本节点请求数据的下游节点的信息，每条记录包括其请求节点ID、代码文件标识号(UID)、请求页的号码、请求数据包的号码和目标节点ID。

2.1 普通节点的算法流程

MTCD协议通过代码版本消息建立和维护分发树。基站节点周期性地广播发送代码版本消息，节点通过代码版本消息对其邻居节点表进行更新，这样,如果新的节点加入到网络或者节点失效，依然能够建立新的分发树进行数据分发。当网络中的节点接收到代码版本消息时，可以通过代码版本消息中的TTL来计算邻居节点到基站节点的跳数；链路质量可以使用无线信号的接收信号强度指示(RSSI)或者链路质量指示(LQI)来表示。节点选择邻居节点中到基站距离(跳数)最小并且链路质量最优的节点为父节点。

如图3所示，节点在接收到代码版本消息后，对节点的邻居节点表进行更新，同时更新其父节点。网络中的所有节点在起初都是普通节点，普通节点在接收到代码版本消息后，如果代码版本消息中的Type号与自身的相同，并且代码版本消息中的代码版本号也要比自身的新，那么,此节点成为目标节点。代码版本消息中的序列号(SequenceNum)越大，说明是越新的代码版本消息。如果接收到的是新的代码版本消息,则节点重新将此代码版本消息广播发送。当节点接收到代码请求消息后，对其自身的请求节点表进行更新。如果节点已经有请求页的数据，那么,节点直接将请求页的数据发送给下游的请求节点；如果节点正在向父节点请求这个页的数据，那么,等接收完请求页的数据后进行转发；否则，节点将代码请求消息转发给其父节点。当普通节点接收到代码数据消息时，通过查询自身的请求节点表，将代码数据转发给下游的请求节点。

图3 普通节点流程图

2.2 目标节点的算法流程

如图4所示，当目标节点接收到代码数据消息时，如果代码数据消息的目标节点不是本节点，那么节点根据其请求节点表将收到的代码数据消息转发给请求节点。如果代码数据消息的目标节点是本节点，则将代码数据存储入外存中；如果已接收到完整的代码页数据，则发送代码请求消息进行下一个页的传输。当目标节点接收到完整的代码镜像后，目标节点停止周期性发送代码请求消息，节点从目标节点变化为普通节点。

图4 目标节点流程图

请求节点表的每条记录都有一个有效时间，如果记录在有效时间内未进行更新，那么就将此条记录从请求节点表删除。每个目标节点都会周期性地发送代码请求消息对路径上节点的请求节点表进行更新。当目标节点接收到完整镜像时，停止发送代码请求消息。其上游节点的请求节点表中的记录在超过有效时间后被删除。

3 MTCD协议的可靠性机制

由于代码镜像文件的特殊性，代码分发协议必须保证目标节点接收到100%可靠地代码镜像文件。保证传输可靠性的机制主要有两种，纠错编码机制和重传机制。纠错编码机制在每个数据包附加大量的冗余数据来进行数据恢复，额外消耗能量较多。传感器网络多采用重传机制，即使用数据包重传来保证可靠性，分为NACK(negative acknow-ledge)机制与ACK(acknowledge)机制。

ACK机制由发送节点负责丢包监测，即接收节点每接收到数据包，就发送ACK包给发送节点进行确认，发送节点在接收到ACK包后确认数据包成功发送，否则，需要重传此数据包。传统的分发协议多采用NACK机制，即接收节点进行丢包监测，接收节点周期性地根据数据接收状态来发送重传请求消息进行数据请求。传统的分发协议由于使用传染病算法，数据发送采用的是广播方式。如果使用ACK机制，由于广播域内的节点都会发送ACK包进行数据确认，会造成网络拥塞。

MTCD协议代码数据的发送是基于单播，避免了ACK机制可能引起的网络拥塞问题。如果使用NACK机制，由于NACK机制必须由接收节点周期性地发送重传请求消息进行数据发送，相比ACK机制，其数据重传速度较慢，在重传请求消息的发送周期上浪费大量时间。因此，MTCD协议使用ACK机制进行数据重传来保证协议的可靠性。

4 实验结果与分析

本文使用TinyOS系统的专用仿真平台TOSSIM[7]进行仿真实验，并与Deluge协议进行对比。实验的网络拓扑使用栅格(grid)结构，节点传输半径为5 m，节点间的间距为3 m，实验用代码文件大小为33 kB。如图5所示为一个5 grid×5 grid网络拓扑，基站节点位于网络左上角,为测试目标节点位置对MTCD协议的影响，使用MTCD-T代表目标节点为离基站距离固定为2跳的黑色节点；MTCD-R代表目标节点为网络右下角的2个灰色节点。通过改变每条边上节点的个数，来测试网络3×3～10×10不同节点规模下的性能。文献[8]给出了传感器每项操作耗费能量的经验模型，通过统计各项操作次数结合经验模型计算其各项操作的耗费能量。

图5 5 grid×5grid网络拓扑

图6是协议在不同节点规模下的分发时间对比。分发时间是与目标节点到基站节点的距离相关的，距离越大，需要耗费在路由转发上的时间就越多。MTCD-R随着节点规模变大，分发时间渐渐超过Deluge协议，这是由于随着路由路径变长，路由路径失效的概率增大，每次路由路径失效，都需花费大量时间进行路由重建。

图6 分发时间对比

图7是协议在不同节点规模下的空闲侦听耗费能量对比。空闲侦听耗费能量与网络中参与分发的节点数目以及分发耗费时间相关。Deluge协议是面向全网节点分发的，因此,网络中所有节点总空闲侦听时间很大。随着节点规模的扩大，MTCD-R路由路径上节点数目变多，分发时间耗费能量逐渐增多；MTCD-T由于参与分发节点数目很少，分发耗费时间最低，因此,空闲侦听能耗是最小的。

图7 空闲侦听耗费能量

图8是协议在不同节点规模下的数据消息耗费能量对比，数据消息指用来发送代码数据的消息。数据消息耗费能量与数据消息的传输次数相关。Deluge协议将代码数据发送到网络中所有节点，MTCD协议只需要将代码数据沿分发树的路径进行转发。因此,MTCD协议的数据消息能耗随分发树的路径长度增大而增大，数据消息传输低于Deluge。

图8 数据消息耗费能量

图9是协议在不同节点规模下的控制消息耗费能量对比，控制消息不进行代码数据的传输，而是协议用来进行网络信息交换，包括代码版本消息、代码请求消息以及ACK消息。MTCD协议的性能稍优于Deluge协议，MTCD-R的控制消息开销与MTCD-T相差不大。这是由于MTCD协议的代码版本消息周期性使用泛洪方式进行广播发送，造成了大量的控制消息传输开销。

图9 控制消息耗费能量

5 结 论

本文提出了一种MTCD协议,与传统的基于传染病算法的代码分发协议Deluge相比，MTCD协议通过建立代码分发目标节点与基站节点之间的路由路径，减少了网络中参与代码分发节点的个数，并保证了协议的可靠性。TOSSIM仿真实验结果表明：在对指定目标节点进行分发时，MTCD协议的能量消耗远远低于Deluge协议。

参考文献:

[1] 况晓辉,许 飞,刘 丽.无线传感器网络远程代码更新技术研究进展[J].计算机科学,2013,40(6):255-261.

[2] Hui J,Culler D.The dynamic behavior of a data dissemination protocol for network programming at scale[C]∥Proc ACM SenSys'04.Baltimore,MD,USA:ACM,2004:81-94.

[3] Liang M,Musaloiu-E M,Terzis A.Typhoon:A reliable data dissemination protocol for wireless Sensor Networks [C] ∥EWSN 2008,Bologna,Italy:Springer,2008:268-285.

[4] Dong Wei,Liu Yunhao,Wang Chao,et al.Link quality aware code dissemination in wireless sensor networks[C]∥The 19th IEEE International Conference on Network Protocols,Vancouver,BC:IEEE,2011:89-98.

[5] Rossi M,Bui N,Zanca G,et al.SYNAPSE++:Code dissemination in wireless sensor networks using fountain codes [J].IEEE Transactions on Mobile Computing,2010,9(12):1749-1765.

[6] Akdere M,Bilgin C,Gerdaneri O,et al.A comparison of epidemic algorithms in wireless sensor networks [J].Computer Communications.2006,29:2450-2457.

[7] Levis P,Lee N,Welsh M,et al.TOSSIM:Accurate and scalable simulation of entire TinyOS Applications[C]∥Proc ACM SenSys’03,Los Angeles,CA,USA:ACM 2003:126-137.

[8] Mainwaring A,Culler D,Polastre J,et al.Wireless sensor networks for habitat monitoring∥Proc the 1st ACM International Workshop on Wireless Sensor Networks and Applications,Atlanta,GA,USA:ACM,2002:88-97.