无线传感网使用网络编码的新型数据传输方法

杨 波，徐建波

湖南科技大学 计算机科学与工程学院，湖南 湘潭 411201

无线传感网使用网络编码的新型数据传输方法

杨 波，徐建波

湖南科技大学 计算机科学与工程学院，湖南 湘潭 411201

1 概述

无线传感器网络是一种以数据为中心的网络，许多应用需要很高的数据传输可靠性，要求数据从源节点可靠地传输到目的节点。

传统提高数据传输可靠性的方法通过增加数据冗余传输实现，主要有重传和多路径两种方式[1-2]。重传中，为了保证数据可靠传输，每跳信息传输都需要确认机制，以保转发成功；多路径方法事先根据所需的信息传输可靠性计算出路径数，将信息沿着多条路径传输，该方法不需要确认消息，但需要维护多条路径，控制复杂。增加数据冗余传输的思想以消耗传感器节点大量额外能量为代价，而且控制信息量大。由于传感器节点能量非常有限，大量的冗余数据传输很容易使节点能量消耗殆尽，缩短网络寿命。

2000年，Ahlswede等人[3]提出网络编码理论，其初衷是为了提升组播传输的网络吞吐量。伴随着研究不断深入，网络编码其他方面的优点也体现了出来[4-5]，如均衡网络负载、节省网络带宽、减少网络能耗等。在提高无线传感器网络数据传输可靠性方面，文献[6]提出了一种基于网络编码的无线传感网多路径传输方法；文献[7]借助网络编码为传感器网络提出了一个数据收集协议SenseCode；文献[8]在无线网络中将基于簇的协作通信与网络编码结合起来研究；文献[9]提出了一种无线传感器网络基于网络编码的机会路由机制。这些方法都采用类似的随机线性编码策略，需携带编码向量传输，附带信息量大；而且许多策略都需要构建固定传输路径，网络各节点能量消耗不够均衡。

本文首先设计了一个新的编码矩阵构造方法，它能提高解码效率且不用传输编码向量；随后提出了一种新的数据包转发策略，通过“区域推进”机制，实现数据的可靠传输与各节点的均衡能耗，并极大地减少不必要的冗余传输。新的数据传输策略简单易行，可提高数据传输可靠性，提升网络整体性能。

2 实用网络编码思想

实用的基于网络编码的数据传输方法的基本思想是，源节点将要传输的多份数据编码成许多彼此无关的数据，目的端只要接受到一部分编码数据就能恢复出原始数据。具体的过程如下。

源节点S具有k份数据，记为 x1，x2，…，xk，需要发送给目的节点D。发送前，源节点S随机产生n个(n＞k)k维（每个向量含有k个分量）向量，记为v1，v2，…，vn，即

各向量称作编码向量。

将这n个向量与k份数据进行式（3）的编码运算，得到n份编码数据，记为 y1，y2，…，yn，即

这些编码向量组成的矩阵称为编码矩阵。

源节点S将每个编码后的数据 yj(j=1，2，…，n)与其对应的编码向量打包，得到n个编码数据包，记为 pj(j=1，2，…，n)，将这n个编码数据包发往目的节点D。目的节点收到足够的编码包后，当有k个编码向量线性无关时，就能解码出原始数据x1，x2，…，xk，如式（4）所示。

需要说明的是，为便于计算机存储和计算，编码、解码运算均是指有限域GF(2q)中运算。

3 新的编码矩阵构造方法

现有方法中，编码矩阵都是通过在有限域中随机生成各编码向量得到，这不利于解码甚至造成解码失败；而且需要携带各编码向量传输，以便目的节点获得解码向量。传感器节点能量有限，应尽量节能，减少额外信息传输，延长网络寿命。

虽然有文献指出增大有限域、或者让中间节点对接受到的数据包再次编码以增加编码向量之间线性无关的机会，但都无法使解码得到最终保证。而且，有限域越大，传输编码向量的负担也越大。

下面提出一种新的编码矩阵构造方法，它能保证任意的k个编码向量线性无关，且不用携带编码系数传输，目的节点只要收到任意k个编码包即可推导出k个编码向量并成功解码。

3.1 构造编码矩阵

定理1构造如下的矩阵M，其中k＜n，ai≠aj(i≠j)，ai≠0 (i=1，2，…，n)，则M中的任意k个列向量线性无关。

证明 如下所示构建范德蒙行列式A，矩阵B是A对应的矩阵：

由范德蒙行列式的性质，当ai(i=1，2，…，n)互不相等时，行列式A≠0，因此，矩阵B的秩R(B)=n，所以矩阵B 的n个列向量线性无关。

从矩阵M中任意取k个列向量，由于每个列向量有k个分量，则这k个列向量可构成一个行列式，记为C，设行列式C对应的矩阵记为D。由矩阵M可知，行列式C仍是一个范德蒙行列式，所以C≠0，因此行列式C对应的矩阵D的秩R(D)=k，即满秩，因此D中的k个列向量线性无关。证毕。

3.2 编码实现与解码

使用新的编码矩阵对原始数据编码过程如式（5）所示。其中，D=(d1d2…dk)，表示由k份原始数据d1，d2，…，dk组成的数据行向量。编码矩阵M的每个列向量即为编码向量，编码向量的第二个分量即ai称为编码向量标识，只需携带编码向量标识传输即可。

每当sink收到一个编码包，就可获得该包的编码数据yi和对应的编码向量标识ai，从而可导出该编码包的编码向量，即

当sink收到源节点S的任意k个编码包后，即可推导出对应的k个编码向量和编码数据。由定理1可知，这任意k个编码向量是线性无关的。因此，收到任意k个编码包即可成功解码。

4 新型数据传输策略

现有基于网络编码的数据传输方法中，数据传输需要构建固定传输路径，构建和维护多条路径控制复杂。数据包只能沿着固定的路径传输到sink节点，当一路径上的某个节点失效会造成数据链路的中断，不能保证每跳转发成功。

下面提出一种新的数据转发策略，不用构建固定传输路径，使用区域推进机制，把数据可靠地向sink推进，能保证每跳可靠转发和节点间均衡能耗。

4.1 区域推进机制

该策略中，数据传输不使用传统的图1所示的固定路径模式，而是使用图2的模式，本文称之为区域推进。

图1 固定路径

图2 区域推进

区域推进的基本思想是，在远区（如区域A）使用一种简单的策略自动选择最佳代表节点将数据“推向”近区（如区域B）。

区域推进充分利用无线通信的广播优势，受到广播信息的节点都具有转发信息的可能性，动态地自动选取某些最佳节点转发数据，将数据向前推进；而固定路径只有特定的节点才会转发数据。区域推进不用建立固定的传输路径；与分簇相比，不用周期性地选择簇头，不用构建和维护簇，也不用只由簇头将数据传送给下一个簇头。

4.2 策略实现

使用如图3的网络模型，网络以sink为中心被划分成许多圆环，每个圆环的宽度为r/4，r为传感器节点的最大辐射半径。每个圆环内的节点都有一个相同的圆环ID号，不同圆环内的节点的圆环ID号不同，圆环ID号从里向外依次为1，2，…，n。圆环ID号代表节点到sink的跳数，也代表节点到sink的距离。这样，每个圆环就代表了一个区域，数据沿着圆环由外往里向sink推进。

图3 网络模型示意

数据传输之前，源节点S需要对每个编码数据打包，数据包由包头和包体组成。包体即为一个编码数据；包头有三部分：编码向量标识、源节点S的ID号和当前节点圆环ID号。数据包传输过程中，当前节点圆环ID号会逐步被修改。

当某个节点收到（receive）一个数据包后，若该节点的圆环ID号小于收到包的包头中的圆环ID号，则接受（accept）该包，否则丢弃（discard）该包。为便于讨论，下面使用示意图进行说明，该讨论具有一般性。

如图4所示，假设在某时刻，节点1为转发节点，则称区域C为转发节点的后向区域，区域D为转发节点的所在区域，区域E、F为转发节点的前向区域。本文中，节点转发数据包的辐射半径设为r/2。因此，当节点1转发数据包时，只有区域E、F中的节点才会接受包，区域C、D中的节点不接受包。

图4 数据转发

当节点a接受一个包 pj时，便计算出其对该包的转发概率 pa(pj)和转发等待时间ta(pj)。pa(pj)计算方法如式（7）所示：

其中，ERes(a)表示节点a的当前剩余能量，EIni(Const)为统一设定的初始能量参考值，是个常量，各节点中该值都相同。

由于区域的宽度为r/4，数据包的转发半径为r/2，因此，节点1转发数据包时会跨越覆盖其前向(0，r/4)区域E，但只部分覆盖(r/4，2r/4)区域F。所以，若F中有节点接收到转发包，则应从F中选取转发节点，否则从E中选取下一轮转发节点，目的是让每次转发都将数据推进的更远。据此设计ta(pj)如式（8）所示：

其中，T为一个事先约定时间系数。于是，所有F中的接受节点的转发等待时间均小于T，而E中的所有接受节点的转发等待时间都大于T但小于2T。下面讨论如何自动确定下一次的转发节点。

某个接受节点在其转发等待时间内，若没有侦听到“抑制”信号，则表示还没有节点转发该包，该节点a就获得该包的转发权。获得转发权的节点立即发送一个该包的“抑制”信号，抑制信号发射半径为r，用于抑制所有其他接受节点再次转发该包。所以，ta(pj)最小的节点就被自动选取为最佳转发节点。

如图5，节点1广播后，节点2、3、4都将收到，由于数据包发射半径为r/2，所以两个接受节点如2、3之间的距离可能会大于r/2，但一定不超过r。因此，选取抑制信号发射半径为r，这样，所有其他接受节点都将收到抑制信号，从而放弃转发。

图5 抑制信号

选取出的转发节点广播抑制信号后，立即将包头的当前节点圆环ID号更新为自身的圆环ID号，并进行下一步的数据推进。

另一方面，某个接受节点在其转发等待时间内，若侦听到了“抑制”信号，则表明已有节点转发该包，因此收到抑制信号的节点将该包丢弃不再转发。

本文网络模型中，数据包的转发半径为r/2，抑制信号发射半径为r，这样，数据包在往sink方向的“推进”过程中，每次推进一定会选出一个最佳转发节点，保证了向前推进的可靠性。使用抑制信号机制，所有其他接受节点不再重复转发，避免了不必要的冗余传输，节约节点能量，也降低了冲突和干扰。

从上述转发节点的产生过程可以看出，在所有接受节点，当前剩余能量最多的节点转发概率越大，转发等待时间越短，从而越容易获得转发权，这样每次获得的转发节点都是最优的。数据包以这种方式传输，不仅保证了每跳传输的可靠性，而且实现了各节点间能耗的均衡，避免了某些节点由于能耗过快而过早死亡。

5 性能分析

无线传感器网络现有基于网络编码的数据传输方法需要携带编码向量传输，需要构建固定的多条路径，这些固定路径上的节点能量消耗快，没有实现网络的均衡能耗。本文新策略具有如下优点：不用构造和维护固定路径，路由简便且有效；不用携带编码系数，节约传输系数的能量消耗；使用“区域推进”机制转发数据包，保证了每跳可靠传输；充分利用无线通信广播特性，实现节点间能耗的均衡使用；sink只要收到任意k个编码包就可以成功解码出原始k份数据。

表1对基于网络编码的多路径传输（记为NCM）和本文新方法（记为NCDT）进行了对比分析，其中的sink解码成功率是指sink收到k个编码包的解码成功率。

仿真关键参数设置如下，网络大小为200 m×200 m，传感器节点个数为400，各节点在网络中随机均匀分布，能量不可补充，sink位于网络中心位置，传感器节点的最大辐射半径r设为20 m，以下结果为重复运行100次仿真的平均性能。

表1 NCM和NCDT性能对比

（1）为比较数据传输的可靠性，定义冗余系数为发送的编码包数量与实际应发送的原始数据数量的比率。如某源点S有5份原始数据需要传输给sink节点，当冗余系数取2时，则S对源数据编码后往外发送编码包个数为5×2=10。图6比较了NCDT和NCM在不同冗余系数下的传输成功率，可以看到，在较小冗余系数时NCDT优势较大。这是由于当传输的编码包较少时，新策略能保证sink收到任意k个编码包即成功解码。

图6 数据传输可靠性分析

（2）网络的生存周期可以用存活节点的数量间接反映出来。图7是网络中存活节点百分比随网络运行时间的变化，可以看出，NCM节点存活数量下降较快，因为NCM使用多条固定路径且携带编码向量传输会造成路径上节点的能量快速消耗，网络没有实现均衡能耗。

图7 网络节点的生命周期

6 结束语

本文设计了一种新的编码矩阵生成方法，提出了一种新的基于网络编码的可靠数据传输策略。该策略不用传输编码系数，充分利用了无线通信广播特性，使用“区域推进”机制实现数据的可靠传输。sink节点根据收到的编码包可推导出编码系数，且只要收到任意k个编码包就可解码出k个原始数据，而以前的方法很难做到这一点。与传统的冗余传输、基于网络编码的多路径数据传输等思想相比，新的数据传输策略控制简单，能提高数据传输可靠性，并实现节点之间能量的均衡利用。

[1]Deb B，Bhatnagar S，Nath B.ReInForm：reliable information forwarding using multiple paths in sensor networks[C]// Proc of the 28th Annual IEEE Conf on Local Computer Networks.Los Alamitos：IEEE Computer Society，2003：406-415.

[2]Popa L，Raiciu C，Stoica I，et al.Reducing congestion effects in wireless networks by multipath routing[C]//Proc of the ICNP.Santa Barbara：IEEE Press，2006：96-105.

[3]Ahlswede R，Cai N，Li S Y R，et al.Network information flow[J].IEEE Transactions on Information Theory，2000，46 （4）：1204-1216.

[4]Noguchi T，Matsuda T，Yamamoto M.Performance evaluation of new multicast architecture with network coding[J]. IEICE Trans on Comm，2003.

[5]康巧燕，孟相如，王建峰.网络编码对组播通信的性能改善[J].计算机工程与应用，2007，43（3）：150-152.

[6]李珊珊，廖湘科，朱培栋，等.基于网络编码的无线传感网多路径传输方法[J].软件学报，2008，19(10）：2638-2647.

[7]Lorenzo K，Emre A，Katerina A，et al.SenseCode：network coding forreliable sensornetworks[R].Lausanne，Switzerland：EPFL，2009.

[8]Haas Z J，Chen T C.Cluster-based cooperative communication with network coding in wirelessnetworks[C]//IEEE MILCOM.[S.l.]：IEEE Press，2010：596-603.

[9]Rout R R，Ghosh S K，Chakrabarti S.A network coding based probabilistic routing scheme for wireless sensor networks[C]//Wireless Communication and SensorNetworks （WCSN）.Allahabad：[s.n.]，2010：1-6.

YANG Bo,XU Jianbo

School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China

Recent researches show network coding can improve data transmission reliability in wireless sensor networks,existing network coding-based data transmission strategies select encoding vectors randomly and use fixed paths to transmit packets, which causes performance deficiencies.This paper designs a new scheme for constructing encoding matrix,and proposes a novel reliable data transmission method.Any k encoding vectors of the new encoding matrix are linearly independent and encoding vectors are not need to be transmitted to sink.Data forwarding uses“region pushing”mechanism,which automatically selects the best forwarding nodes to“push”packets from one area to another area closer to sink.Analysis and simulation results illustrate that the new proposed method can improve data transmission reliability and reduce network energy consumption.

wireless sensor network;network coding;data transmission;encoding matrix;reliability

网络编码能提高无线传感器网络数据传输可靠性，针对现有基于网络编码的数据传输策略随机选取编码向量和使用固定路径所带来的缺陷，设计了一个新的编码矩阵构造方法，并提出了一种新型的基于网络编码的可靠数据传输方法。该编码方案能保证任意k个编码向量线性无关，且不用传输编码向量。数据转发使用“区域推进”机制，自动选取最佳转发节点，将数据包可靠地向sink“推进”，并实现了最少冗余传输和网络均衡能耗。分析与仿真表明，新的数据传输策略能消除现有方法的缺陷，提高数据传输可靠性，降低能耗。

无线传感器网络；网络编码；数据传输；编码矩阵；可靠性

A

TP393

10.3778/j.issn.1002-8331.1108-0371

YANG Bo,XU Jianbo.Novel data transmission method in wireless sensor network using network coding.Computer Engineering and Applications,2013,49（5）：99-102.

湖南省教育厅科学研究重点项目（No.09A027）；湖南省自然科学基金项目（No.09JJ9006）；湖南科技大学研究生创新基金（No.S100117）。

杨波（1986—），男，硕士研究生，主要研究领域为无线传感器网络；徐建波（1963—），男，博士，教授。E-mail：bozyyang@126.com

2011-08-25

2011-10-08

1002-8331（2013）05-0099-04

CNKI出版日期：2011-12-09 http://www.cnki.net/kcms/detail/11.2127.TP.20111209.1000.015.html