一种结合网络编码的分发协议在无线传感器网络中的应用研究

黄名钿，黎 英，高 伟，张金飞

（昆明理工大学 信息工程与自动化学院，云南 昆明 650500）

0 引言

无线传感器网络（WSN）一般由大量部署在信号监测区的集传感、计算和无线通信功能于一身的微型传感器节点组成，这些节点通过无线通信的方式形成一个多跳的自组织网络。无线传感器网络中，将节点相关参数更新的过程称为小数据分发[1]。不同于传感数据，配置参数对一个网络的重要性不言而喻，如果不能保证网络中所有节点的配置参数一致的话，很可能导致整个网络瘫痪。对部署在无人看管区域的无线传感器网络而言，如何高效和可靠地实现对传感器网络中的应用程序进行参数配置是一个具有很强应用需求的问题。一种最简单的想法是将所有部署好的节点收集回来重新进行参数或程序的修改，但这种方式需要耗费大量的人力和时间，在实际应用中可操作性不强，因此研究能够远程将所需要配置的参数可靠地分发到传感器节点的方法具有非常重要的意义。

小数据分发因其所发送的数据量小（通常可能就几十个字节），而且数据格式往往相差很大，灵活性强，可靠性要求高，因而在实际传感器网络的操作中会使用单独的小数据分发协议来解决这类需求。针对无线传感器网络小数据分发，国内外学者提出了许多协议。

Drip[2]协议把每个数据项都当做分发的单独实体并为每个数据项建立一个独立的Trickle定时器，提供了很好的粒子性控制，控制何时以及如何快速地把数据项分发出去。对于每个数据项的每一个新的版本都单独生成一个概要元组进行通知。Drip协议中的传输代价是和其数据项成线性相关的。即当有N个数据项时，需要有N个相应的概要元组数据包进行通知。

DIP[3]协议采取将所有数据项借助哈希树的数据结构压缩到一个概要数据包中，这样只需比较根节点数据就可以判断是否有数据项需要更新。采用这种方案，可在O（1）时间内作出是否有新的数据项需要更新的判断。然而，由于这种机制将所有的通知都压缩到一个数据包中，无法给出具体哪个数据包需要更新，并且涉及到复杂的算法，需要耗费更多的内存。

DHV[4]协议提出了仅仅检测版本号上的差异，以达到传输尽可能少的数据的目的。

BDP[7]协议采用了布隆过滤这一数据结构作为压缩存储数据项元数据信息的工具，能快速识别出具有相同键值的数据项间的版本差异，并且在保证全网范围内数据项的一致性上具有非常高的可靠性。然而由于布隆过滤天生的缺点可能导致出现假阳性判定错误概率，BDP的设计没有考虑无线传感器网络的特点，其长度远远大于无线传感器网络中消息的大小，此外BDP协议应用不当可能引起死锁。

DIP和DHV将所有数据项当做一个群体进行分发，而Drip则是把每个数据项当做单一项进行分发，灵活性强，很适合参数重配置这样的应用场合[5-6]。使用了DIP和DHV协议的网络中的所有节点在分发消息之前必须统一固定的数据集，在数据量小时容易造成高延时。尽管DIP和DHV在大规模数据项更新方面优势明显，但是在小数据项更新方面性能不如Drip，并且 DIP、DHV和 BDP都使用了复杂的算法，计算复杂度使得这些协议需要消耗传感器节点更多的内存。

网络编码[8]（NC）是编码技术中的一种，于2000年提出，是一种通过将接收到的数据包进行编码使得在增加传输信息量的同时减少网络中数据包的技术。它推翻了网络中独立比特不能再被压缩的经典结论，理论上能使源与组播成员间达到最大流最小割的组播速率，在解决网络拥塞，提高传输可靠性方面效果显著。

针对像配置参数这样的小数据分发，因其数据量小、数据量数目有限、数据格式差异大、要求高可靠性的特点和传感器节点本身资源有限的实际情况，并不适合使用采用复杂算法的小数据分发协议。因此我们结合Drip协议和网络编码技术的优点，采取一种以空间换时间的思路，在Drip协议的基础上使用网络编码，对其进行改进，提出一种改进的基于网络编码的无线传感器网络小数据分发协议，用以改善小数据分发在延迟和可靠性方面的性能[12]。以下为方便阐述，简称该改进协议为NCDP 。

1 网络编码分发方式分析

Drip使用了线性扫描来辅助发现具有不同版本号的数据项。仅当某个节点发现邻居节点上有旧的数据项时，才由前者对后者上的旧数据项进行更新，从而避免了重复传输。然而为了保证全网范围内数据项版本的一致性，对于每一数据项，每个节点都必须周期性地向周围邻居广播相关的版本信息。一旦节点发现周围存在不同版本的数据，就需要发送更多的消息与邻居协同，从而识别出哪个节点上的数据具有更新的版本号。在数据项数量较多时，如果处理不当，上述过程将造成大量的通信开销，既浪费了节点上宝贵的能量，也占用了有限的带宽资源。因此，如何保持该协议性能的前提下，同时降低协议开销，是本课题的一项挑战。接下来，将通过对网络编码模式进行分析，证明网络编码这一技术的可行性。

1.1 网络拓扑结构

假定节点的广播半径为 R，D为相邻两节点之间的距离[9],[13]。当D>R时，源节点发出的数据包将不会到达目标节点；当 D≤R<2D时，源节点发出的数据包将逐跳传输到各个节点，整个网络形成一个多跳的结构；当3D>R≧2D时，源节点发送一次数据包，1跳范围内和 2跳范围内的节点都会收到此数据包，第1跳中的节点在转发此数据包时2跳中的节点将收到大量重复数据包，这将严重降低网络的性能。同理，当R≧3D时，网络将产生更多的重复数据包，如此类推。本课题讨论的无线传感器网络如图1所示。

图1 网络拓扑结构Fig.1 Network topology

1.2 网络编码分发方式的增益分析

为方便起见，这里只讨论一跳范围内的数据分发[10]。假设一个源节点S向两个普通节点R1和R2分发N个数据项，源节点S到R1和R2的丢包率分别为 P1和 P2，且 P1

方式A（非网络编码分发方式）：当一个节点在当前时隙丢失一个数据包并且先前时隙从未完整接收到该数据包时，立即发送一个 NAK消息给源节点，源节点根据丢包再进行重传恢复。

方式B（网络编码方式）：该方式与方式A相似，如果普通节点不能正确接收到数据包将会立即发送NAK消息给源节点。不同之处在于源节点需要等到所有数据包都发送出去之后才开始进行重传恢复。同时，源节点维护有一张表，表中包含R1和R2相应丢的数据包的Id，如图2所示。重传过程中，先将两者都缺失的数据包进行异或操作然后分发出去，R1和R2接收到编码包之后根据先前已接收到的数据包进行恢复。特别的是，对于两者同时缺失的数据包在重传的时候不再进行异或操作。对于图2的例子，源节点在重传阶段发送的编码包为a1a3⊕，a4a5⊕，a6，a8。R1通过a3⊕（a1a3⊕）恢复丢失的数据包a1，R2通过a1⊕（a1a3⊕）恢复丢失的数据包 a3。由于 R1和R2同时丢失 a6，因此不对a6进行异或编码。最后，由于只有R1丢失a8，所以也不用进行异或编码。

图2 网络编码方式Fig.2 Network Coding

根据以上假设，分发N个数据项，接收节点只有两个的情况下，方式A所需发送的信息量为：

方式B需要发送的信息量为：

当接收节点数量为M时，

使用网络编码的分发方式相比非网络编码方式，同样情况下分发更少的数据，更有效率，可靠性和实时性更好。

2 NCDP的实现

2.1 NCDP思想

NCDP使用了Trickle算法用来控制消息分发的速率，并随机发送编码包和原始数据包。因为不利用拓扑信息来决定哪些消息需要编码，因此可以减少路由控制方面的资源开销，降低延迟，使用网络编码提高了可靠性。相对于其它使用了复杂编码操作的分发协议，考虑到异或操作往往作为一种硬件功能集成在CPU中这一现成优势，于是NCDP将用简单的异或操作用于编解码[9,15]。

2.2 NCDP设计

NCDP是在已有分发协议Drip的基础上增加网络编码的功能，对Drip协议中原有的相关数据帧和数据发送与接收的功能进行重新设计。

（1）相关数据帧定义

数据帧格式定义如图3所示：

图3 数据帧定义Fig.3 Data frame definition

分发消息帧格式定义如图4所示：

图4 分发消息帧定义Fig.4 Dissemination message frame definition

其中，Idi和 Idj分别为编码包所包含的源数据项Id，Data为想要分发的原始数据项，NoteId为节点Id。

NCDP协议数据帧格式由包含编码包信息的头部和包含被编码的消息主体Data组成。由于解码过程需要知道编码包由哪些原始数据包组成，因此编码包头部包含了若干个原始数据包的编号，代表该编码包由几个原始数据包编码而成，每个编号占据一个字节大小，如果数据项超过256个，可以相应地对编号占据的字节数进行扩展。当数据包需要发送时，节点会将数据包帧添加到分发消息帧中，并在分发消息帧中添加上本节点的 NoteId。当数据帧中Idj为0，代表这是一个原始数据，如图5所示。

图5 原始数据Fig.5 Raw data

（2）接收与发送功能设计

NCDP数据接收与分发过程流程图如图6所示。

当接收到消息时，如果该消息包为原始数据包，那么就将消息存入原始数据存储区，并和已接收到的编码包轮流进行解码操作，尝试解码出其它原始数据。如果解码成功则将解码出来的原始数据先存储进原始数据区，然后删除和其成功进行解码操作的编码包，重复此过程直到无法再解码出新的原始数据。

当接收到的消息是编码包时，先利用已接收到的原始数据对其进行解码，如果解码出另一个原始数据则存储解码出来的原始数据并将该编码包删除。如果该编码包无法解码出原始数据，则将其先存储到编码包区，等待下一次解码。

如果当原始数据区的数据对应的Trickle定时器触发时将该数据与其它已接收到的原始数据进行随机编码然后发送该编码包给其它邻居节点。当节点接收到的数据为原始数据并且该数据已存储在原始数据区时，说明有其它节点正在发送该原始数据给邻居节点，没必要再发送给对方，因此将该原始数据对应的Trickle定时器定时间隔翻倍，避免重复发送冗余信息，减轻网络拥塞。

图6 NCDP数据接收与分发过程流程图Fig.6 Process flow chart of data receiving and distribution of NCDP

（3）随机编码算法

为了降低延迟，NCDP使用随机编码算法对数据包进行随机编码，而不是等待所有原始数据都分发出去之后才进行重传恢复。随机编码流程如图 7所示。其中rand_num为生成的16位随机数，COMB为随机编码概率，MAX_STORE为原始数据存储区最大存储量。next_content表示当前原始数据存储区存放的数据项数量，初始值为 0，每添加一个原始数据项自加1。

图7 随机编码算法流程图Fig.7 Flow chart of random coding algorithm

随机编码步骤如下：

步骤 1.判断是否是原始数据，是的话进入步骤2，不是的话进入步骤7；

步骤 2.判断是否小于编码率，是的话进行步骤3，不是的话进入步骤6；

步骤 3.判断两个编码对象是不是同一个原始数据项，不是的话进入步骤6，是的话进入步骤6；

步骤 4.判断是否有其它原始数据可以与自身进行编码，是的话进入步骤5，不是的话进入步骤6；

步骤5.异或编码并进入步骤6；

步骤6.发送并进入步骤7；

步骤7.结束。

3 仿真实验

接下来我们将通过一系列实验来评估NCDP的各项性能。本论文使用的仿真工具是 TOSSIM，TOSSIM 是 TinyOS自带的仿真器，专门用来仿真TinyOS的应用，可以支持大规模的网络仿真，而且其仿真代码和实际的传感器节点运行的代码一样，具有高可信度。TinyOS则是一款专门为无线传感器网络而开发的开源嵌入式操作系统，广泛应用于物联网领域。

3.1 评估指标

实验过程中随机产生节点的网络拓扑，节点间两两连接，为确保仿真的可信度，每个节点都加载了噪声道模型，每个实验仿真10次，并选取数据的均值作为实验结果。我们使用以下指标来评估NCDP的性能。

效率：通过网络总的消息分发量来衡量效率。

可靠性：通过已接收到所有数据的节点百分比来评估可靠性。

分发速度：通过所有节点接收到所有消息的延迟时间来评估分发速度。

3.2 性能评估

第一组实验，通过对比 NCDP、Drip、DIP和DHV在不同节点数量下分发20个数据项时，网络中总的消息发送量来评估其分发效率。根据Roofnet[8]项目，一般真实环境中一对收发节点有50%的丢包率，因此为提高可信度设置网络的丢包率为50%，实验结果如图8所示。

由图8可以看出，我们可以发现在不同节点数量的网络中NCDP发送量总要比Drip和DHV低，但比DIP高。虽然DIP分发速度更快，但是因为涉及复杂的哈希树使得DIP相比NCDP更消耗内存。

图8 分发效率评估Fig.8 Dissemination efficiency assessment

图9 分发延迟评估Fig.9 Dissemination delay assessment

第二组实验，对比NCDP、Drip、DIP和DHV的分发延迟，如图9所示。图9展示了随机布置100个节点，分发20个数据项，节点完成率所对应的时间。由图9可以看出，Drip、DIP和DHV刚开始时丢包率比较严重，因为分发起始阶段只有少数的节点传输数据，许多数据包丢失了。相比之下，得益于网络编码，NCDP在起始阶段，即使只有少数的节点在传输消息，数据仍然传播到网络中的绝大部分。由图9我们还可以看出最后一两个节点往往导致整个网络大范围延迟，NCDP的网络延迟比Drip、DIP和DHV更低。这是因为当一些节点没能收到最后的消息时，使用了Drip、DIP和DHV的节点只能等待其它节点给它发送消息，这样造成极大的延迟。相比之下，使用了NCDP的节点能通过解码已接收到的编码包来提高接收到最后一个数据项的可能性，降低延迟。由图 8和图 9，我们可以得出这样一个结论：NCDP总体比Drip、DIP和DHV更快分发、更可靠和更有效率。

3.3 缓存占用分析

第三组实验，我们将评估在分发过程中 NCDP每个节点所占用的缓存大小，如图10所示[15]。通过在网络中随机布置100个节点，发送100个数据项。图 10的 X轴表示节点所占用的最大缓存大小，Y轴表示落在相应缓存大小的节点数量。由图10可以看出大部分节点只使用了不超过 36个字节大小的缓存，最大的缓存大小为84个字节。图10中的折线图显示网络中 80%的节点使用了最大为 36个字节大小的缓存。

第四组实验，我们评估分发数据量对内存占用的影响，如图 11所示。实验中，我们通过分发 10到100个数据项，每组实验按10个数据项递增，随机布置100个节点到网络中。由图11可以看出尽管最大的内存占用随着分发数据项数量增多而激增，但是缓冲区的均值却比较平稳。甚至如果我们增加网络的分发数据量时，实际缓存的开销并不像编码包数量那么多，因为编码包一旦解码成功就被删除了，不会一直占用着空间。

图10 缓存占用评估Fig.10 Cache occupancy assessment

3.4 编码率与抑制率分析

由于NCDP使用了Trickle算法和网络编码，因此如何设置编码率和抑制率使得NCDP能发挥出最大的性能，将是接下来两组实验中所要研究的。

第四组实验，我们在一个随机布置有100个节点的网络中分发10个数据项，NCDP在不同编码率下所需分发的消息数和网络的分发用时，如图12和图13所示。由图12和图13可观察出，将编码率设置为30%-60%比较合适。

第五组实验，我们在一个随机布置有100个节点的网络中分发10个数据项，NCDP在不同抑制率下所需分发的消息数和网络的分发用时，如图14和图15所示。由图14和图15可以看出将抑制率设置为50%比较合适。

图11 最大缓存与均值缓存Fig.11 Maximum caching and mean caching

图12 编码率与分发效率Fig.12 Coding rate and dissemination efficiency

4 结论

图13 编码率与分发延迟Fig.13 Coding rate and distribution delay

图14 抑制率与分发效率Fig.14 Inhibition rate and dissemination efficiency

图15 抑制率与分发延迟Fig.15 Inhibition rate and dissemination delay

本文给出了针对现有小数据分发协议在无线传感器网络参数重配置场合下的不足之处，以空间换时间的思路，通过对Drip协议使用网络编码技术并对其中收发数据功能进行改进，提出 NCDP。尽管NCDP需要额外的空间用于存储消息包的版本号和额外的缓存用来存储编码包。不过这些开销可以通过指定最大编码数和最大缓存空间来控制。通过多次仿真实验研究结果表明，NCDP相比Drip和DHV，在同样情况下只需发送更少的消息。尽管在同样情况下NCDP发送的消息包多于DIP，但是相比DIP它可靠性更好。总的来说，NCDP相比 Drip、DIP和 DHV在小数据分发实时性和可靠性总体性能方面有一定提高。

[1] 潘浩, 董齐芬, 张贵军, 等. 无线传感器网络操作系统TinyOS[M]. 北京: 清华大学出版社, 2011.4.PAN H, DONG Q F, ZHANG G J et al. Wireless Sensor Network Operating System[M]. Beijing: Tsinghua university press, 2011.4

[2] Tolle G, Culler D. Design of an application cooperative management system for wireless sensor network[C]. Istanbul,Turkey: Sencond European Workshop on Wireless Sensor Networks (EWSN), 2005, 121-132.

[3] Lin K., Levis P. Data discovery and dissemination with dip[C]. Washington DC, USA: Proceedings of the 7th International Conference on Information Processing in Sensor,2008, 433-444.

[4] Dang T., Bulusu N., Feng W. C., et al. DHV: A Code Consistency Maintenance Protocol for Multi-hop Wireless Sensor Networks[C]. Cork, Ireland: Wireless Sensor Networks, 6th European Conference, 2009, 327-342.

[5] 闫彩芹, 方群. 基于能量敏感的无线传感器网络信任度计算模型[J]. 软件, 2012, 33(4): 84-88.YAN C Q, FAN Q. A Model of Reliability Calculation of Wireless Sensor Network Based on Energy[J] Sensitivity.Software, 2012, 33(4): 84-88.

[6] 周唯, 刘冬, 刘会师. 基于无线传感器网络拓扑的研究与设计[J]. 软件, 2013, 34(12): 22-25.ZHOU W, LIU D, LIU H S. Research and Design of Wireless Sensor Network Topology[J]. Software, 2013, 34(12): 22-25.

[7] Chen Tao, Guo Deke. A Bloom filters based dissemination protocol in wireless sensor networks[J]. Ad Hoc Network,2013, 11: 1359-1371.

[8] Ahlswede R., Cai N., Li S. Y., et al. Network information flow[C]. Inf. Theory IEEE Trans, 2000, 46(4): 1204-1216.

[9] 郑军、张宝贤 编著. 无线传感器网络技术[M]. 北京: 机械工业出版社, 2012.ZHENG J, ZHANG B X. Wireless Sensor Network Technology[M]. Beijing: Mechanical industry press, 2012.

[10] Wang Xiumin, Wang Jianping, Xu Yinlong. Data Dissemination in Wireless Sensor Networks with Network Coding[J].EURASIP Journal on Wireless Communications and Networking, 2010, 2010: 14-30.

[11] Nildo dos Santos Ribeiro Júnior. CodeDrip: Improving data dissemination for wireless sensor networks with network coding[J]. Ad Hoc Network. 2017, 54: 42-52.

[12] Doddavenkatappa M., Chan M. C., Leong B. Splash: fast data dissemination with constructive interference in wireless sensor networks[C], Lombard: The 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), 2013, 269-282.

[13] Gao Y., Bu J., Dong W., et al. Exploiting concurrency for efficient dissemination in wireless sensor networks[C], New York:IEEE Transactions on Parallel and Distributed Systems,2013, 24(4): 691-700.

[14] 赵欣荣, 肖迎元, 王晓晔, 等. 无线传感器网络多路径聚集的改进[J]. 软件, 2014, 35(7): 7-12.ZHAO X R, XIAO Y Y, WANG X Y. Improvement of Multi-path Aggregation of Wireless Sensor Networks[J].Software, 2014, 35(7): 7-12.

[15] 吕占伟, 陶峥. 重传下的无线传感器网络的生命周期分析[J]. 软件, 2015, 36(1): 116-121.LU Z W, TAO Z. Life Cycle Analysis of Wireless Sensor Networks under Retransmission[J]. Software, 2015, 36(1):116-121.