基于网络编码的WSNs数据收集方法

汪淑丽

(吉林大学公共计算机教学与研究中心，吉林长春130012)

0 引言

无线传感器网络(WSNs)中的节点不仅能量有限，而且缓存较小，因此，一个节点只能存储一小部分从周围收集到的信息，为了完成数据的收集、存储和复制，大量的节点必须协同工作。现有的部分方式是服务器端首先给Sink节点发送查询消息，然后Sink节点把查询消息广播给所有传感器节点。最后所有的传感器节点响应此次查询，把监测数据通过路由发送给服务器端。但是，这种查询方式存在着较多的弊端:1)延时比较大;2)如果服务器端需要原始数据，这样导致就不能进行数据融合，进一步导致主干路由的负担临时变得非常大，容易发生通信中断的情况;3)在转发存储过程中，存在着大量的数据拷贝，浪费了存储空间，也消耗了节点的能量。文献［1］指出由于无线传播的广播特性，网络编码非常适合应用于WSNs。如WSNs中，节点以自组织方式增加或移除部分节点会导致网络拓扑结构的变化，预测数据分组的丢失和节点以及链路的故障将变得困难，而网络编码却能够使目的节点有效地利用编码数据流恢复原始信息，甚至可以恢复一些网络中因干扰、拥塞或移动而丢失的数据分组。

在数据采集方面，文献［2］提出了部分网络编码(PNC)作为连续数据采集的一般工具。PNC推广了现有的网络编码，能够对传感器节点连续接收到的数据进行有效的存储替换，但没有给出完整数据收集算法。文献［3］提出了一种数据聚合算法，每个单独的节点只保存一个数据包，当监听到邻居节点的数据包时，就在有限域上乘一个随机系数并和自身数据相加。这样，单个普通传感器节点可能不能解码数据，但是对信宿节点来说，就能以很高的概率通过查询仅仅n个节点而重建n个数据包，使得传感器网络数据聚合的效率得到极大的提高。

在提高鲁棒性方面，文献［4］提出了一种结合分布式源编码私网络编码的优化算法，目的是用来提高传感器网络的容错性和可靠性，同时对分布式源编码的压缩效率和网络鲁棒性进行了折衷考虑。文献［5］提出了一种通过在IP和MAC层之间植入一个网络编码层，将编码层集成到现有协议栈中，针对实际使用环境，提出了一种自适应纠错机制，使编码的纠错能力与分组的丢失率相匹配，减少数据重传次数。文献［6］给出了连续的数据收集算法，但是，其要求在数据源节点周围拥有较多专门用于存储转发的中继节点，并不符合WSNs的特征。

本文参考上述文献，提出了一种改进的适应于WSNs特性的部分网络编码的数据收集算法，该算法着重于网络数据的收集、数据的编码和解码，实验结果表明其有不错的效果。

1 网络编码的基本概念

1.1 网络编码原理

目前，传统路由器的存储转发模式根本不可能达到香农最大流最小割定理规定的上界。这是因为现有通信网络中使用的路由机制认为网络中传输的信息是不能叠加的，只能进行存储和转发［7］。然而 Ahlswede R等人［8］提出的网络编码技术彻底推翻了这一结论，Ahlswede R指出:如果允许网络节点对传输的信息按照合适的方式进行编码处理，而非有限域存储和转发，则给予该方式的网络多播总能够实现理论上的最大传输容量。网络节点对传输信息进行操作和处理的过程，就称为网络编码。

Ahlswede R等人以著名的“蝴蝶网络”模型为例，详细阐述了网络编码的基本原理。如图1所示的网络中，设各链路容量为1，S是信源节点，Y和Z是信宿节点，其余为中间节点。S有2个包 b1和 b2均要发送给 t1和 t2。在图1(a)所示的传统模式中，中间节点只能对接收到的数据包赋值和转发，即3到4的链路每次只能传输b1或者b2，该链路必须使用2次才能达到目的，平均速率为1.5个包/s。而在图1(b)中采用了网络编码，节点3对数据包进行了异或处理，这样一次传输就可以将b1⊕b2传送到节点4，因为t1和t2已经接收到b1和b2，所以，再次进行异或操作便可以得到b1和b2，该模式下的所能达到的平均速率为2个包/s。由此可见，基于网络编码的多播实现了理论上的最大传输容量。

图1 蝴蝶网络Fig 1 Butterfly networks

1.2 网络编码的核心思想

网络编码的核心思想为［7］:具备编码条件的网络节点对接收到的信息进行一定方式的处理(编码)，然后传输给下一级的网络节点，收到消息的下一级节点如果具备编码条件，又对其接收的信息按照同样的方式进行处理和传输，如此反复，直到所有经过处理后的信息都汇聚到信宿节点为止。最后，在信宿节点通过逆过程的操作(译码)，即可译出信源发送的原始信息。

2 基于网络编码的数据收集方法描述

WSNs有其自身的资源缺陷，而在能量方面尤其明显。参考已有的文献可知，节点间的数据通信是耗能最大的环节，故网络中的数据收集采用网络编码，以降低网络中的数据流量，提高网络的整体性能是可行的。

2.1 网络的基本结构描述

本文采用基于簇的网络结构，结构中有3种不同类型的节点，分别为簇成员节点、簇头节点和Sink节点，这3种类型的节点在缓存空间大小、携带能量多少和处理器的运算处理能力方面均存在一定的不同。其中，Sink节点拥有大的缓存空间、多的能量和强的运算处理能力，簇头节点在这三方面的硬件条件次之，而簇成员节点在这三方面的硬件条件最差。这样的网络结构能够有效地克服网络中所有节点具有相同但是小的缓存空间而引起的性能下降，保证簇头节点对来自其簇成员节点的数据进行缓存和编码，Sink节点对整个网络的数据进行存储和解码操作。网络结构图如图2所示。

图2 网络结构图Fig 2 Diagram of network structure

2.2 基于部分网络编码的举例说明

在传统的网络编码中，可能存在延时、节点解码准确性不高和删除过时数据存在缺陷的情况，这里考虑的情况是如何以最小的代价删除过时的数据信息，部分网络编码将能够比较有效地解决这个问题，为了更好地说明该问题，参考文献［2］，举例说明部分网络编码在数据删除过时数据信息的优点。

设有6个传感器节点，传感器节点分别标记为s0，s1，s2，s3，s4，s5，每个节点的缓存空间大小为 2，每个缓存空间中原始数据的最大数量值为4，且这6个传感器节点存储的数据分别为

当产生新的数据c4时，c0变为过时数据，节点s0和s4分别丢弃过时数据，同时添加新的数据c4，则节点s0和s4缓存中的数据更新为

该举例说明部分网络编码具有无需解码的情况下，就可以移除过时的数据的特性。不过，值得注意的是:部分网络编码的译码能力取决于组合数据的势集(定义为其所包含的原始数据块的个数)，在统一的势集分布情况下，译码性能最理想。然而，从传感器的角度考虑，由于缓存空间有限，同时，传感器节点也无法知道其他节点所存储的数据。基于上述情况的考虑，由于本文所构造的网络构造为基于簇的结构，簇头节点和Sink节点的缓存大和处理能力较强的特性，使得这两种类型的节点能够有效地获取相对全局的信息。

2.3 网络编码过程

数据的收集基于簇结构，簇成员节点和簇头节点的通信距离均为一跳，这样会降低因为通信而导致的能量消耗，而簇头节点与簇头节点的通信距离可以不受限制，这样簇头节点之间形成了数据收集和传输的主干路由。簇成员节点采集其监测区域的数据，簇头节点根据其实际缓存的大小，对数据进行缓存和更新，同时把缓存数据发送给簇头节点，簇头节点对接收到的数据采用随机编码，利用主干路由把数据发送到Sink节点，Sink节点在得到一定程度编码数据的基础上，解码得到各个簇的编码数据，进而得到整个网络的数据。

3 模拟实验结果与分析

均匀部署200个节点到100 m×100 m的区域，经过成簇算法形成8～10个簇，成为簇头节点的通信区域认为可以覆盖整个部署区域。在此要说明的是，网络中所需要汇报的数据只有一种类型的数据，而不考虑汇报多种类型的数据。

本文采用文献［9］提出的能量模型，通信模型采用多路径效应模型，即完成一次发送、接收通信的总能量消耗为E(l，d)=l(2Eelec+ εmpd4)，通信能量参数设为:Eelec=50 nJ/bit，εmp=0.0013 pJ/bit/m4，d=20 m。

不同的网络编码方案将影响整个网络的鲁棒性，也对节点的丢包率产生影响，本文主要考虑能量开销和数据准确率这2个性能评价参数。

图3是整个网络的能量消耗图，从图中可以看出:采用网络编码时，全网的能量消耗明显低于非网络编码的数据。

图3 网络的能耗Fig 3 Energy consumption of network

图4是采用网络编码时的数据恢复准确率，从图中可以看出:虽然数据恢复的准确率有所反复，但是，基本保持在较高的准确率，在参考能量消耗的基础上，这个性能是比较理想的。

图4 网络的丢包Fig 4 Packet loss of network

4 结论

网络编码是一个学科交叉的产物，经过多年的研究，网络编码正给网络带来革命性的变化，但在多源网络编码、非线性编码、网络编码的具体实现、降低网络编码的复杂性，以及网络编码在安全方面的研究仍然方兴未艾，将成为网络编码下一步的研究方向和热点。本文主要讨论了部分网络编码用于WSNs的监测数据收集的算法，在基本保证数据精确度的前提下，能有效降低网络内的能量消耗。

［1］张书奎，樊建席，崔志明.无线传感器网络中可靠的数据协作传输机制［J］.通信学报，2010(11):30-40.

［2］Wang Dan，Zhang Qian，Liu Jiangchuan.Partial network coding:Theory and application for continuous sensor data collection［C］∥Proceedings of 14th IEEE International Workshop on Quality of Service，2006:93-101.

［3］Dimakis A G，Probhakaran V，Ramchandran K.Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes［C］∥ Proceedings of 4th International Symposium on Information Processing in Sensor Networks，2005:111-117.

［4］Zhang Xin，Wicker S B.Robustness vs efficiency in sensor networks［C］∥Proceedings of 4th International Symposium on Information Processing in Sensor Networks，2005:225-230.

［5］唐文胜，王 威，罗 娟.WSNs中一种基于网络编码的可靠传输算法［J］.湖南师范大学学报:自然科学版，2008(1):59-64.

［6］王俊义.编码分组网络的效用最大化及网络编码在应用方面的研究［D］.北京:北京邮电大学，2008.

［7］陶少国，黄佳庆，杨宗凯.网络编码研究综述［J］.小型微型计算机系统，2008(4):583-592.

［8］Ahlswede R，Cai Ning，Li Shuoyen R.Network information flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204-1216.

［9］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-sepcific protocol archietecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications ＆Mobile Computing，2002，1(4):660-670.