徐 骥,朱艺华,田贤忠,池凯凯

(浙江工业大学计算机科学与技术学院,浙江杭州 310023)



无线传感器网络中利用随机网络编码的低能耗可靠机会

徐 骥,朱艺华,田贤忠,池凯凯

(浙江工业大学计算机科学与技术学院,浙江杭州 310023)

无线传感器网络中节点大多采用电池供电，让节点以低能耗将采集的数据传递到信宿，对无线传感器网络有效运行极为重要.该文提出了能量有效的可靠机会路由EROR(Energy-efficient Reliable Opportunistic Routing)，它利用结合节点剩余能量和链路上收发双方的总能耗的转发代价，选择转发节点集合(简称“转发集”)、主转发节点和协助转发节点，让节点调节发射功率并利用随机线性编码把数据包分片编码发送到转发集，进而以多跳方式把数据可靠低能耗地传递到信宿.仿真结果表明：在网络生存时间和能耗方面，EROR比已有路由策略CodePower更优.

无线传感器网络;机会路由;节能;功率控制;网络编码

1 引言

传统的路由协议需要节点在发送数据之前建立一条或多条端到端的数据传输路径，以将数据逐跳发送到目的节点.为了提高可靠性，路径上节点通常采用重传和确认机制传递数据.在通信链路质量比较差的情况下，节点需要重传多次才能将数据包发送给下一跳节点.频繁的重传会导致节点过多消耗能量.而且，节点重传需要竞争信道，从而导致带宽利用率不高[1,2].

无线信道的广播特性可以在某一程度上克服上述不足.当一个节点发送数据包时，其邻居节点可以监听到该数据包.机会路由[3]利用了无线信道的这一广播特性，它需要在正确接收数据包的节点中选择到目地节点的一个节点来转发数据包，从而提高转发数据包的可靠性以提高吞吐率.如图1，设源节点S到目地节点D存在一条路径S→1→2→3→4→D，其中，S到节点1，2，3的数据包传输成功率分别为0.9，0.7，0.5，且节点2和3到D的数据包传输成功率分别为0.6和0.85.按照传统路由，节点S将数据包发送到节点1，且在节点1未能成功收到数据包的条件下，需要重传.由于无线链路的广播特性，在节点S向节点1发送数据包时，节点2和3分别以0.7和0.5的概率监听数据包.也就是说，在节点1收到数据包的同时，节点2和(或)节点3可能均收到该数据包.传统路由忽视了这一现象，只是简单地逐跳转发：把数据包从节点1转发到节点2，再转发到节点3，最终到达目的节点D.但机会路由并非这样做，而是直接让节点3把数据包发送给其下游节点甚至于目的节点D.由这个例子可见，机会路由可以减小数据包的传递次数.

在无线传感器网络中，节点通常由能量有限的电池供电，因此，机会路由需要考虑节点的能耗.若节点选择较大的发生功率，那么数据包能够被更远更多的节点监听到，但会增加网络的能耗开销；若减少发送的功率，链路质量越差，数据包可能要经过更多节点转发才能到达Sink，可靠性降低.因此在无线传感器网络中，我们需要设计一个能量高效的可靠机会路由，此乃本文的研究动机.本文的贡献如下：

(1)给出了结合节点剩余能量和收发双方能耗的数据包转发代价计算公式，设计了能够让节点在数据传输过程中动态地选择转发节点集合(下称“转发集”)、发送功率和转发代价的算法.

(2)提出了基于编码的低能耗机会路由策略EROR(Energy-efficient Reliable Opportunistic Routing).EROR利用随机线性编码，让节点将编码包发送到下游节点，以提高传输可靠性.在数据转发过程中，EROR可以让节点根据转发代价在转发集中动态选择一个主转发节点，使数据传递到Sink节点.此外，EROR允许主转发节点选取若干协助转发节点，并且每个协助转发节点可以根据其所在转发集的代价、链路质量和缓存的编码包个数来确定自己需要发送的最大编码包个数，以降低和平衡各转发节点的消耗，从而延长网络的生存时间.

2 相关工作

目前，已经有一些机会路由在选择转发节点时考虑了能耗问题，但这些研究还存在不足.在文献[4]中作者提出的EEOR每个节点可在调发送能量和不可调发送能量模型下计算路由代价和选择最优转发节点集合，从而使得数据通过这些节点转发到Sink时总能耗最小.EEOR中节点根据优先级转发数据，若高优先级的转发了数据，那么低优先级的节点需要丢弃监听到的数据包，造成节点能量的浪费.AsOR[5]设计了分段路由的方法，通过选择最优的段内节点个数使得平均能耗最小化，但AsOR是从全局角度优化能耗，是集中式的路由算.一些研究将网络编码用于路由，如基于网络编码的无重传路由[6]和编码增益感知的路由[7].MORE[8]将机会路由和流内随机线性编码相结合，解决了节点转发调度困难的问题.CodeOR[9]用滑动窗口提高MORE数据传输的效率，但CodeOR没有考虑能耗.CodePower[10]通过分布式算法选择了最优的发送功率和对应的最优转发节点，将结合流内随机线性编码的机会路由用于无线传感器网络，但CodePower不能保证数据可靠传递，节点只转发确定数量的编码包，不能保证数据可靠传递.本文提出的EROR通过选择主转发节点和协助转发节点来解决了上述能量浪费和可靠性问题.文献[11]提出基于部分网络编码的机会路由.文献[12]提出分布式联合候选节点选择和速率分配的多流机会路由算法.文献[13]结合端到端的可靠性与能耗，针对自组织网络，提出两个路由策略：RMECR(Reliable Minimum Energy Cost Routing)和RMER(Reliable Minimum Energy Routing).前者的链路权重考虑了链路两端节点的收发能耗和剩余能量，后者的链路权重仅考虑链路两端节点的收发能耗；两者均利用Dijkstra算法找到能耗最小的路径.文献[13]的作者指出：上述两种路由需要网络中每个节点知道整个网络的拓扑结构，可以采用诸如洪泛(flooding)等方法获得网络拓扑结构信息；两者在采用Dijkstra方法求最小能耗时，均需要采用集中计算.事实上，文献[13]提出的RMECR和RMER路由均不适用无线传感器网络，其理由如下所述:(1)当代无线传感器网络大多基于IEEE 802.15.4标准，节点的处理能力、无线电覆盖范围、可以通信的数据包长度、内存空间等均为捉襟见肘.IEEE 802.15.4标准针对低数据率、低功耗的无线个域网络，其物理层可以携带的来自数据链路层数据帧的最大长度只有127字节[14].目前，CrossBow公司生产的TelosB传感器节点，其射频收发器兼容IEEE 802.15.4标准，通信距离仅为数十米，而且只有10kB内存；(2)在低功耗的无线传感器网络中，节点之间的链路时断时续，这会导致采用集中方式计算出来的最优路径在传递数据包时可能因某个链路中断而失效，而且存在最优路径未使用就失效的可能，这是因为最优路径在计算出来之后，计算路径的节点需要发送数据包通知各相关节点，而且包含该通知的数据包在发送过程中可能丢失.本文提出的EROR路由方案，可以克服上述缺陷.本文的EROR的主要异同之处在于：EROR采用分布式算法，节点在选路时只需获取邻居的状态信息，无须知道整个网络的拓扑结构，也不需要计算从信源到信宿的路径.而且，EROR适用于资源极度受限的、链路时断时续的、基于IEEE 802.15.4标准的无线传感器网络.

3 基于编码的低能耗可靠机会路由

3.1 EROR的转发策略

与MORE[8]类似，本文提出的EROR协议利用流内随机线性网络编码来传递数据，关键在于：利用转发代价确定转发节点集合(简称“转发集”).我们将在下一节给出转发代价的定义.

转发集Fs中的节点，每侦听到一个来自节点s的编码包，就检查收到的编码包与缓存的编码包是否线性无关.若是，则放入缓存，否则，弃之.当一个节点缓存的编码包的个数达到m时，该节点就向节点s回复一个ACK，使节点s停止生成和发送编码包.

我们称转发集中第一个收足m个编码包的节点为“主转发节点”.设节点u是Fs的主转发节点.由于节点u的m个编码包系数形成一个满秩矩阵，它可以通过解码得到节点s发送的原始数据.此时，Fs中其余节点收到的编码包个数不足m，虽然这些节点不能通过解码获得原始数据，但其收到的编码包或许对下游节点的解码有用.因此，下述方案可以在Fs中筛选一些节点(称为“协助转发节点”)让其转发所收到的编码包给下游节点.

(1)若f∈Fu，则f侦听Fs中的节点广播的编码包；

(3)若f∉Fu∪Fs，则不侦听也不转发数据.

主转发节点u和协助转发节点将各自缓存的编码包进行随机编码不断产生新的编码包，再把编码包广播给Fu内的下游节点，直到收到Fu内主转发节点的ACK为止.在图2中，v是Fu的主转发节点.节点v采用广播的形式发送ACK，使得Fs中节点收到确认后就停止发送编码包.

上述过程逐步推进，直到Sink收到m个线性无关的编码包，进而解出源数据.之后，Sink发送ACK给其上游转发节点，使其停止发送编码包.

3.2 EROR的数据转发代价

由上节可知，EROR协议是根据转发代价选择转发节点的.因此，在设计转发代价时，需要考虑以下因素：

(1)转发代价应能够根据节点的能量状态和链路质量状态来影响数据的转发路径.

(2)由于节点的发射功率影响着节点的邻居集合，高发射功率使节点的邻居多，但耗能大，因此，转发代价需要反映节点的发射功率.

(3)为了使网络有更长的工作时间，转发代价应该分担给剩余能量小的节点更小的数据转发任务.

(1)

我们取

(2)

接下来，我们确定式(2)右边两个代价的表达式.本文采用文献[13]的能耗模型.用A表示节点计算和处理调制数据的平均功率，用B表示接收方接收数据的平均功率.于是，在功率ε下发送l比特数据消耗的能量Etx(l,ε)和接收l比特数据消耗的能量Erx(l)可以表示为[13]：

(3)

(4)

其中0<β<1是放大器的效率，R是物理层的速率(单位：bps).

我们考虑瑞利衰落无线信道，节点u以功率ε发送信号给节点v的误码概率为[13]

(5)

(6)

式中，g1是与传输和接收天线有关的常数，εN是噪声和干扰的功率，η为路径衰减指数，du,v为节点u和v之间的距离.因而，

(7)

(8)

其中，REu和REv分别为节点u和v的剩余能量.

表1 集合F的主转发节点及对应概率

(9)

上式中，右边分式是在集合F中至少有一个节点接收到节点u所广播的数据包这一条件下，节点fi成为主转发节点的概率.

3.3 确定转发集、发射功率和转发代价的算法及其复杂度

3.4 转发数据量的确定

考虑到协助转发节点需要协助主转发节点发送编码包给下游转发集，为了节省能量，我们需要限制协助转发节点发送的编码包的最大个数.假设节点f为主转发节点u的一个协助转发节点.我们引入符号

(10)

(11)

其中Γf是节点f缓存的编码包的个数.每个协助转发节点一旦发送的数据包个数达到Af或者收到确认包时，就停止发送.

3.5 主转发节点的选择

转发集合中的节点在侦听数据时，可能在同一时刻有多个节点缓存的编码包个数同达到m.这时，如果这些节点同时发送确认包，可能会导致确认包的碰撞，也可能产生多个主转发节点.为了避免这种情况发生，在节点f收齐m个编码包时，我们让节点延缓Tf符号周期(Symbol Period)发送确认包，而且，在延缓的Tf符号周期内，若该节点监听到其它节点已经发送了确认包，则它取消发送确认包(即放弃成为主转发节点).考虑到IEEE 802.15.4标准要求发送确认包的延迟时间在[12,32]这个区间内，我们定义：

(12)

4 仿真分析

由于节点可以调整发射功率，因此若节点增大发送功率，那么可能有更多节点能够收到数据包，这样节点的邻居会随功率增大而增多.在仿真中，我们使用与文献[13]类似的方法确定式(6)中的g1/εN：我们取g1/εN的值满足节点u以最大功率发送长度为800比特的数据包给相距50米远的节点v收到的概率为0.5.利用文献[13]的方法，可得：g1/εN=2058314.我们参考Telos节点的参数[16]：接收功率为38mW，发送功率为35mW，节点活跃时总功率为41mW.因此，我们取式(4)中B=38mW，发送功率E中最大值为35mW，式(3)中A=5mW.其它仿真参数如表2所示.我们采用C++程序设计语言设计仿真程序.

表2 其它仿真参数

考虑到RMECR和RMER[13]不适合于无线传感器网络(见第2节)，而CodePower与EROR均属于机会路由，采用类似的机制，我们对EROR和CodePower的性能进行对比.由于EROR保证每跳可靠传输，源节点发送的数据包都到达sink节点，因此，以下仅对两者的网络生存时间和能耗进行对比.网络生存时间定义为从发送第一个数据包开始到出现第一个剩余能量为0的节点为止这段时间，并且采用源节点发送数据包个数进行度量.平均能耗定义为网络生存时间内平均每个到达Sink的数据包消耗的能量.仿真区域大小为1000×1000m2，Sink节点位于区域左下角，在区域中随机产生节点.Sink的代价为0，其余节点初始代价取为无穷大.我们假设Sink节点能耗不受限制并且有足够的计算能力，因而忽略Sink的接收能耗.图3和图4是不同网络规模下1000次仿真运行的平均结果.由图3可见：本文提出的EROR的生存时间大于CodePower.这是因为EROR在选择转发节点时，考虑了节点的剩余能量.剩余能量少的节点代价比较大，EROR避免将这些节点作为转发节点，而是选择其它能量比较充足的节点转发数据包.然而，CodePower在计算代价时未能考虑节点的剩余能量，导致能耗不均.从图3(a)可以看出：两者的生存时间都随着网络规模的增大呈先增大后减小的趋势.这是因为网络中节点密度增大，每个节点的邻居节点个数随着增加，使得一个节点有更多机会从邻居中选择代价更小的节点作为转发节点，从而使得生存时间增大.但当节点个数进一步增大时，主转发节点的转发集也随着增大，即参与转发数据包的节点个数增大，相互转发的数据包增多，从而引起生存时间减小.从图3(b)可以看出，网络生存时间都随分片增多而减小，这是因为分片数越多，节点转发的数据包个数就越多，耗能越大.

由图4可见：EROR的平均能耗低于CodePower，且两者的能耗均随着节点数和分片数的增大而增大.但随着节点数的增大，EROR的能耗比CodePower增大缓慢(见图4(a)).这是因为EROR的主转发节点使得编码包逐跳可靠传输，而且，它通过选择适当的协助转发节点来协同主转发节点转发部分编码包.然而，CodePower采用端到端确认以保证可靠传输.因此，随着网络规模的扩大，CodePower的数据包可能因中途夭折而重传，这时夭折的数据包可能走过了很多跳，从而导致平均能耗的上升.从图4(b)可以看出，平均能耗都随分片增多而增加，这与直观是吻合的.

5 总结

本文提出了一种基于随机线性编码并且发送功率可调的低能耗机会路由EROR.这种路由策略利用随机线性网络编码，并利用结合节点剩余能量和链路上收发双方总能耗的转发代价，选择主转发节点、协助转发节点和转发集，使数据可靠地从信源传递到信宿，降低和均衡了节点的能耗，在保证可靠性的同时，延长了网络生存时间.

[1]Poonguzharselvi B,Vetriselvi V.Survey on routing algorithms in opportunistic networks[A].Proceedings of the 2013 International Conference on Computer Communication and Informatics(ICCCI)[C].Coimbatore:IEEE,2013.1-5.

[2]Zhang Z,Krishnan R.An overview of opportunistic routing in mobile ad hoc networks[A].Proceedings of the 2013-2013 IEEE Military Communications Conference[C].San Diego:IEEE,2013.119-124.

[3]Biswas S,Morris R.ExOR:opportunistic multi-hop routing for wireless networks[J].ACM SIGCOMM Computer Communication Review,2005,35(4):133-144.

[4]Mao Xufei,Tang Shaojie,Xu Xiahua,Li Xiangyang,Ma Huadong.Energy-efficient opportunistic routing in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(11):1934-1942.

[5]Wei Chen,Zhi Chen,Fan Pingyi,et al.AsOR:an energy efficient multi-hop opportunistic routing protocol for wireless sensor networks over Rayleigh fading channels[J].IEEE Transactions on Wireless Communications,2009,8(5):2452-2463.

[6]卢文伟，朱艺华，陈贵海.无线传感器网络中基于线性网络编码的节能路由算法[J].电子学报，2010,38(10):2309-2314.

Lu Wenwei,Zhu Yihua,Chen Guihai.Energy-efficient routing algorithms based on linear network coding in wireless sensor networks[J].Acta Electronica Sinaca,2010,38(10):2309-2314.(in Chinese)

[7]田贤忠，朱艺华，缪得志.无线网络编码增益感知的低时延路由协议[J].电子学报，2013，41(4):652-658.

Tian Xianzhong,Zhu Yihua,Miao Dezhi.Wireless network coding gain aware routing protocol with low delay[J].Acta Electronica Sinaca,2013,41(4):652-658.(in Chinese)

[8]Chachulski S,Jennings M,Katti S,et al.Trading structure for randomness in wireless opportunistic routing[J].ACM SIGCOMM Computer Communication Review,2007,37(4):169-180.

[9]Lin Y,Li B,Liang B.CodOR:opportunistic routing in wireless mesh networks with segmented network coding[A].Proceedings of the 2008 IEEE International Conference on Network Protocols(ICNP 2008)[C].Orlando:IEEE,2008.13-22.

[10]Tong J,Qian D,Du Z,et al.Energy-efficient coded routing with selective transmission power for wireless sensor networks[A].Proceedings of the 2010 IEEE 72nd Vehicular Technology Conference Fall(VTC 2010-Fall)[C].Ottawa:IEEE,2010.1-5.

[11]王晓东，霍广城，孙海燕，孟祥旭，孙言强.移动自组网中基于部分网络编码的机会主义路由[J].电子学报，2010,38(8):1736-1740.

Wang Xiaodong,Huo Guangcheng,Sun Haiyan,Meng Xiangxu,Sun Yangqiang.An opportunistic routing for MANET based on partial network coding[J].Acta Electronica Sinaca,2010,38(8):1736-1740.(in Chinese)

[12]何施茗，张大方，谢鲲，张继，乔宏.多并发流无线网状网中的机会路由算法[J].电子学报，2014,42(5):1004-1008.

He Shiming,Zhang Dafang,Xie Kun,Zhang Ji,Qiao Hong.Opportunistic routing for multi-flow in wireless mesh networks[J].Acta Electronica Sinaca,2014,42(5):1004-1008.(in Chinese)

[13]Vazifehdan J,Prasad R V,Niemegeers I.Energy-efficient reliable routing considering residual energy in wireless ad hoc networks[J].IEEE Transactions on Mobile Computing,2013,13(2):434-447.

[14]IEEE Computer Society.IEEE 802.15.4 Standard for Wireless Medium Access Control(MAC)and Physical Layer(PHY)Specifications for Low-Rate Wireless Personal Area Networks(WPANs)[S].2011.

[15]Ho T,M′edard M,Koetter R,Karger D,Effros M,Shi J,Leong B.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[16]Polastre J,Szewczyk R,Culler D.Telos:enabling ultra-low power wireless research[A].Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks[C].IEEE,2005.364-369.

徐 骥 男，1990年生于浙江绍兴.硕士研究生,研究方向为无线传感器网络.

朱艺华(通信作者) 男，1961年生于浙江玉环，博士，教授，研究方向为无线网络、物联网、网络编码等.

E-mailyhzhu@zjut.edu.cn

Energy-Efficient Reliable Opportunistic Routing Applying Random Network Coding for Wireless Sensor Network

XU Ji,ZHU Yi-hua,TIAN Xian-zhong,CHI Kai-kai

(SchoolofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou，Zhejiang310023,China)

The nodes in Wireless Sensor Networks(WSNs)are usually powered by battery.It is extremely important to let the nodes deliver data to the destination in an energy-efficient manner such that the WSNs have longer runtime.In this paper,the Energy-efficient Reliable Opportunistic Routing(EROR)is presented.The EROR uses the forwarding cost,which takes into account node’s residual energy and the total energy consumption expended by the nodes over a wireless link;chooses the forwarding set consisting of forwarding nodes(FNs),the main FN,and the assistant FNs;and allows a node to change its transmission power to transmit the encoded packets,which are generated by randomly linear network coding,to the forwarding set such that the data are delivered to the destination in a multi-hop,reliable,and energy-efficient way.Simulation results indicate that the EROR outperforms the existing CodePower routing in terms of network lifetime and energy consumption.

wireless sensor network;opportunistic routing;energy conservation;transmit power control;network coding

2015-02-08;

2015-04-08；责任编辑：诸叶梅

国家自然科学基金重点项目(No.61432015);国家自然科学基金(No.61472367，No.61379124)

TP393

A

0372-2112 (2016)08-1799-07

��学报URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.08.004