无线传感网中基于能量均衡的机会路由算法

王 雷，王 珺，朱志伟，吴 涵

(1.南京邮电大学 宽带无线通信与传感网技术教育部重点实验室,江苏 南京 210003;2.南京邮电大学 江苏省无线通信重点实验室,江苏 南京 210003)

无线传感网中基于能量均衡的机会路由算法

王 雷1,2，王 珺1,2，朱志伟1,2，吴 涵1,2

(1.南京邮电大学 宽带无线通信与传感网技术教育部重点实验室,江苏 南京 210003;2.南京邮电大学 江苏省无线通信重点实验室,江苏 南京 210003)

机会路由实现了数据在有损无线链路中的高吞吐量传输。现有的机会路由协议—MORE，虽然是第一个将网络编码应用到机会路由中的，但是在选择候选转发节点集时，仅考虑节点间的链路质量，使得部分节点因为能量耗尽而过早死亡，影响了无线传感网的整体性。针对这一突出问题，提出了一种改进的基于MORE协议的机会路由算法，以均衡节点的能量消耗。根据机会路由的传输机制，综合考虑节点的期望传输次数(ETX)和剩余能量(RE)，提出了一种新的路由测度期望生存时间(ELT)和基于它的候选转发节点集的选择策略。最后，基于NS2仿真平台进行仿真分析。仿真结果表明：在考虑节点剩余能量的基础上，改进MORE协议既保证了数据传输的可靠性，同时均衡了节点的能量消耗，提高了节点生存时间，延长了网络的生命周期。

机会路由；期望传输次数；剩余能量；期望生存时间

0 引 言

作为21世纪最有影响力的技术之一，无线传感器网络(WSNs)[1]正在深刻改变着人类的生活。而路由协议作为无线传感器网络技术发展的关键因素之一，一直是近年来的研究热点。

用于无线网络的传统路由协议，在实际的数据传输开始之前，会预先选择一个或多个理想的、确定的路径作为最佳路径路由。这种策略的最大缺点是，它只是简单应用了最初设想用于有线网络路由的解决方案和规则。事实上，传统的无线路由协议不能很好地适应无线环境的变化。因此，传统无线路由协议将引起链路层的过度重传，网络资源的重传，甚至可能导致系统的崩溃。此外，无线媒介被认为是这些协议的限制，因为它的动态变化、拥挤等，是很难控制的。但是，在机会路由[2]中，共享无线介质被认为是机会而不是限制。

机会路由背后的关键思想是，利用无线媒介广播特性克服无线传输不可靠的缺点。也就是说，不同于在每一次的传输过程中，预先选择中继节点，机会路由是广播数据分组，以便它的邻居节点能够侦听到该数据包，而后这些邻居节点成为它的候选中继节点集。之后，实际的数据包转发节点将从这些成功接收到数据包的候选节点集中选择。但是，在选择候选节点集时，路由度量考虑不充分。

针对这一问题，在机会路由选取候选转发节点上进行改进，定义新的路由度量，综合考虑链路质量和节点剩余能量，提出一种改进的基于MORE协议的能量均衡的机会路由算法，并对此方案进行仿真验证。

1 相关工作

在麻省理工学院(MIT)的Biswas等[2]提出机会路由的概念之后，研究者们进行了深入研究。Eric Rozner等[3]提出的SOAR协议，采用自适应转发路径以避免重传，并通过基于优先级的定时器，局部损失恢复方案与自适应速率控制，获得了较好的性能。文献[4]提出的多速率地理选择路由(MGOR)，是以地理位置为基础，并结合无线网络中多速率传输的特点提出的机会路由。该协议引入OEOT路由度量，通过该路由度量达到传输速率和候选转发节点集的平均优化的目的。而面对机会路由相关的开销问题，许多研究人员利用网络编码来解决该问题。S.Chachulski等[5]抓住这一特点，将随机线性网络编码引入到机会路由中，提出了MAC层独立的机会路由(MORE)协议，以非常低的成本显著降低了节点间的协作开销，改进了机会路由的性能。但是在该协议下，只能被动利用各节点网络编码机会。针对这一问题，文献[6]提出了编码感知机会路由协议(CAOR)。CAOR将局部流间网络编码策略和机会路由相结合，创造出更多的编码机会，从而提高了多流情况下无线网络的吞吐量。文献[7]提出的CoAOR协议，主要是为了解决CAOR中转发节点需要其两跳邻居节点状态信息这一突出问题。但是，在低功耗多跳无线网络中，即无线传感器网络中，能量消耗是一个极为重要的因素。因此，最近的一些机会路由协议将能量消耗这个参数考虑进去。

在节能路由的研究中，Mao等[8]提出了能量有效机会路由协议(EEOR)。在该协议中，候选转发节点的选择及其优先级都是以最小能量消耗为度量。此外，EEOR认为可以通过调节传输功率，使得发送者逐渐增加它的发射功率达到最大阈值，从而增加候选转发节点的数目。文献[9]提出的MDOR路由算法，利用动态能量计算的方式，优化网络的端到端传输时延以及网络的生存时间。Zorzi等[10]设计的地理路由协议(GeRaF)，运用基于竞争的路由机制，允许节点自主休眠与苏醒，从而提高了网络整体的生存时间。文献[11]提出的CL-EE算法，是结合物理层和介质介入控制层感知的机会路由协议。该协议利用跨层之间的信息交换，以较小的能量消耗获得了较高的端到端吞吐量。文献[12]提出的基于拓扑和链路质量感知的地理机会路由协议(TLG-OR)，将地理位置、链路质量以及节点的剩余能量考虑进来。在候选节点集的选择上，以地理位置为主要参考因素，选择具有最少转发时延的节点作为最佳转发节点。文献[13]提出了具有异步睡眠的机会路由协议(ORAS)，在保证发送者有潜在的转发节点并能高效接收数据包的同时，降低能耗。文献[14]提出了一种适用于WSN的基于协同的机会路由协议，提出新的路由度量，转发能效，以能量有效的方式提高了数据的转发速率，但是也增加了信令开销。

2 基于MORE的改进算法

2.1 无线传感网节点能耗模型

文献[15]中提出了first-order能耗模型，该模型的结构如图1所示。

图1 first-order能耗模型

根据该能量消耗模型，传输k位数据包的发送能耗etx(d,k)与接收能耗erx(k)如下：

etx(d,k)=(eelec+eamp*d2)*k

(1)

erx(k)=eelec*k

(2)

其中，无线收发器的运行开销为eelec=50nJ/b；传输开销eamp=100 pJ/(b*m2)。

Douglas等[16]提出了期望传输次数(ETX)路由度量。ETX值是一个预测值，用来衡量数据包在一对节点间传输数据直到成功时，可能需要的次数，自然包括重传次数。但是对于一个完整的路由，不好直接预测ETX值，所以通过将各链路ETX值相加的形式，得到一条路由的ETX值。

ETX的计算，由两个因素构成，分别为前向转发成功率df与反向ACK确认成功率dr。那么，一次传输的期望概率，即成功接收与确认，为df*dr。因为每一次传输数据包的尝试，可以被认为是伯努利实验，所以期望传输次数为：

(3)

通过对链路探测包的计算，可以得到转发率df和dr。根据设定的发送周期τ，每个节点会发送固定大小的探测包。如果所有节点都在同一时间发送探测包，可能会导致同步效应，所以每个节点探测包采用0.1τ的抖动发送。另外，因为探测包的发送是以广播的形式，而且在802.11b的机制下，不存在确认和重传机制。所以，每个节点只要记录在过去的时间内接收到的探测包的数据，就能够计算转发率，见式(4)。

(4)

其中，count(t-w,t)为在过去的ω时间内实际接收到的探测包个数；ω/T为在ω时间内应该收到的探测包数量。

通过探测包，可以计算出节点间链路质量，得到ETX值，这样也能够得出节点成功接收一个数据包时期望的能量消耗：

Erx=ETXi*erx(k)

(5)

其中，ETXi为节点i与其前一跳的ETX值。

同理，节点i成功发送一个数据包的预期能量消耗为：

Etx=ETXj*etx(d,k)

(6)

其中，ETXj为节点i与其下一条的ETX值。

那么节点i成功接收并发送一个数据包的预期能量消耗为：

EECi=Erx+Etx

(7)

2.2 ELT路由测度

ETX值代表节点间的链路质量，数值越小，意味着数据在节点间重传的可能性越小，节点间的预期能量消耗也越小(根据式(7))。但是，如果单纯的以ETX作为路由度量，链路质量较好的节点将持续不断地作为转发节点，那么这些节点将因为能量耗尽而过早死亡。为了保证网络的整体性，避免部分节点的过早死亡而退出网络，期望既保证数据传输的可靠性，又能够考虑节点的剩余能量(Eres)，防止某些节点能量过早耗尽。因此，综合了ETX和节点的剩余能量，提出了期望生存时间(ExpectedLifeTime,ELT)作为路由度量，计算公式为：

(8)

由式(8)知，ETX值越小且Eres越大，节点期望生存时间越长，那么选择该节点转发数据包的概率越大。

2.3 候选转发节点集的选取

和传统路由协议相比，机会路由最主要的工作在于候选转发节点集的选择。对于候选转发节点集，当中的节点个数越多，可以认为数据转发的成功率越高。可是这也带来了另一方面的问题，节点过多，它们的协作开销将非常困难。MORE协议是根据各个节点到目的节点的ETX来选择候选转发节点集。在该协议中，将节点的剩余能量考虑其中，并且假设候选转发节点集的集合大小为6，其候选转发节点集选择确定的具体算法如图2所示。

图2 确定候选转发节点集的流程算法

2.4 改进MORE协议的性能分析

对改进MORE协议，定性分析其三大优点：

(1)较高的可靠性。

经典MORE协议以节点间的链路质量作为路由测度，并采用网络编码的方法，在进行转发前，将数据包随机混合，保证了较高的数据传输成功率。改进MORE协议，以经典MORE协议为基础，继承了其高可靠性的特点。另外，以ELT作为路由度量，考虑了节点剩余能量，保证了网络的整体性，同时提高了数据传输的可靠性。

(2)均衡能耗，延长网络生存时间。

所提出的ELT路由测度，综合考虑了节点间的链路质量和节点的剩余能量，在保证数据传输质量的同时，也保证了网络的整体性。以图3为例，假设一个数据包的能耗E为1，ETX值和剩余能量如图所示。经典MORE协议，将选择节点B作为下一跳，那将导致节点B因能量耗尽而死亡。而根据式(8)计算得ELTA≈3.57，ELTB≈1.67，改进MORE协议将选择节点A进行转发。所以，以ELT为路由测度，考虑节点的剩余能量，减少剩余能量较少节点的数据转发次数，以防止其因能量耗尽而过早死亡，均衡节点间传输数据的能量消耗，延长网络的生存时间。

图3 下一跳路由选择示意图

(3)提高网络吞吐量。

经典MORE协议，以节点间的链路质量作为路由测度，在选择转发节点时，将一直选择链路质量较好的节点转发数据包，导致这些节点因为能量耗尽而过早死亡，影响了网络整体性以及吞吐量。改进MORE协议，以链路质量和节点的剩余能量作为路由测度，均衡了节点能量消耗，延长了链路质量较好的节点的生存时间，保证了网络的整体性，也提高了在整个网络生存周期中的网络吞吐量。

3 仿真结果分析

采用NS2(NetworkSimulatorVerson2)软件完成仿真实验，将改进的MORE协议与经典MORE协议进行比较。具体的仿真参数为：网络拓扑大小为500m*500m；节点数目为50个，初始能量为10J；节点传输距离为100m；网络编码数据包大小为1 400B。

3.1 评价指标

在路由度量的设计上，综合了链路质量和节点剩余能量。为了进行有效的对比，设计了以下指标：

(1)节点剩余能量方差：每经过一段时间，统计各节点的剩余能量，并计算所有节点剩余能量的平均值，计算所有节点与该平均值之差的平方和。

(2)网络节点存活数：每经过一段时间，统计网络中节点剩余能量还能支撑节点工作的节点个数。

(3)网络吞吐量：在MORE协议中，传输吞吐量定义为数据块的大小(一个数据块所包含的个数)除以数据块的传输时间(即从源节点开始发送当前数据块到源节点收到来自目的节点的ACK确认信息为止)。从这里可以看出，传输吞吐量是由每秒发送多少个数据包为单位的，即Packets/s。设传输吞吐量为100 Packets/s，换算成常用单位bps，换算关系式如式(9)所示：

100 Packets/s=100*1 400*8/1 024= 1 093.75kbps

(9)

3.2 实验结果

3.2.1 节点剩余能量方差

由图4可以看出，0～20 s内，改进MORE协议和经典MORE协议的节点剩余能量方差相差无几,但在20 s之后，节点的剩余能量方差出现了分歧。由于经典MORE协议不考虑节点的能量消耗，优先选择链路质量较好的节点进行转发，导致部分节点的能耗较大，所有节点的剩余能量方差较大。而改进MORE协议，在路由度量上，考虑节点的剩余能量，在选择候选节点时，分散了节点的能量消耗，从而均衡了网络的能量消耗。

图4 节点剩余能量方差

3.2.2 网络节点存活数

图5给出了经典MORE协议和改进MORE协议关于网络节点存活数的对比情况。在0～20 s内，两种协议的网络节点死亡数目都为0。之后，经典MORE协议下的节点开始因为能量耗尽而不断死亡；改进MORE协议下节点也出现死亡，但相比较而言，出现的时间晚一些。在30～100 s之间，经典MORE协议下节点的存活数目都小于改进MORE协议下的。特别是在100 s时，经典MORE协议下的节点已经全部死亡；而改进MORE协议下还有少量节点存活，还能完成少部分的数据传输工作。综上所述，改进MORE协议能够延长网络生命周期。

图5 网络节点存活数

3.2.3 网络吞吐量

由图6可以看出，在30 s之前，两种协议的吞吐量大致相当。而在30 s，根据图5，经典MORE协议下部分节点已经因为能量耗尽而死亡，所以吞吐量有所降低。而改进MORE协议考虑了节点的剩余能量，在选择转发节点时，会舍弃部分能量较低的节点作为转发节点，使得整个网络中节点的能量消耗较为平均，节点不会出现像经典MORE协议中，节点间链路质量较好，却过早因能量耗尽而退出网络的情况。但是即便如此，毕竟节点的能量有限，还是会有节点因能量耗尽而退出网络，那么网络的整体性能也势必会降低。

图6 吞吐量

4 结束语

经典MORE协议，率先将网络编码引入到机会路由中，进一步提高了网络吞吐量，但是在选择候选转发节点时，仅考虑节点间的链路质量，使得部分节点因为能量耗尽而过早地退出网络。针对这一突出问题，提出了以ELT为路由度量选择候选转发节点集的标准，并设计了基于新路由度量的候选节点选择策略，提出了改进MORE协议。通过分析以及仿真结果表明，改进MORE协议在选择候选转发节点时，同等条件下，会舍弃能量较低的节点，均衡能量消耗，保证节点的存活率，提高网络的完整性，延长网络的生存周期。在今后的研究中，将针对数据传输时延进行优化，提高数据传输的效率。

[1] 崔 莉,鞠海玲,苗 勇,等.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1):163-174.

[2] Biswas S,Morris R.Opportunistic routing in multihop wireless networks[J].ACM SIGCOMM Computer Communication Review,2004,34(1):69-74.

[3] Rozner E,Seshadri J,Mehta Y,et al.SOAR:simple opportunistic adaptive routing protocol for wireless mesh networks[J].IEEE Transactions on Mobile Computing,2009,8(12):1622-1635.

[4] Zeng K,Lou W,Zhai H.Capacity of opportunistic routing in multi-rate and multi-hop wireless networks[J].IEEE Transactions on Wireless Communications,2008,7(12):5118-5128.

[5] Chachulski S,Jennings M,Katti S,et al.Trading structure for randomness in wireless opportunistic routing[C]//Proceedings of the ACM SIGCOMM 2007.New York:ACM Press,2007:169-180.

[6] Yan Y,Zhang B,Mouftah H T,et al.Practical coding-aware mechanism for opportunistic routing in wireless mesh networks[C]//IEEE international conference on communications.[s.l.]:IEEE,2008:2871-2876.

[7] Hu Q,Zheng J.CoAOR:an efficient network coding aware opportunistic routing mechanism for wireless mesh networks[C]//IEEE GLOBECOM workshops.[s.l.]:IEEE,2013:4578-4583.

[8] Mao Xufei,Xu Xiaohua,Tang Shaojie,et al.Energy-efficient opportunistic routing in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(11):1934-1942．

[9] Sharma M,Singh Y.Middle position dynamic energy opportunistic routing for wireless sensor networks[C]//International conference on advances in computing,communications and informatics.[s.l.]:IEEE,2015.

[10] Zorzi M,Rao R R.Geographic random forwarding (GeRaF) for ad hoc and sensor networks:energy and latency performance[J].IEEE Transactions on Mobile Computing,2003,2(4):349-365.

[11] Jing Z,Chen D,Nguyen H V,et al.Cross-layer aided energy-efficient opportunistic routing in ad hoc networks[J].IEEE Transactions on Communications,2014,62(2):522-535.

[12] Zhao Z,Rosario D,Braun T,et al.Topology and link quality-aware geographical opportunistic routing in wireless ad-hoc networks[C]//International wireless communications and mobile computing conference.[s.l.]:[s.n.],2013:1522-1527.

[13] Liu S,Sha M,Huang L.ORAS:opportunistic routing with asynchronous sleep in wireless sensor networks[C]//2010 2nd international conference on future computer and communication.Hefei,China:ACM,2012:234-248.

[14] 胡海峰,杨 震.无线传感器网络中基于协同的机会路由[J].通信学报,2009,30(8):116-123.

[15] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless sensor networks[C]//Proceedings of the 33rd IEEE Hawaii international conference on system sciences.Maui:IEEE Computer Society,2000:233-243.

[16] Couto D S J D,Aguayo D,Bicket J,et al.A high-throughput path metric for multi-hop wireless routing[J].Wireless Networks,2003,11(4):419-434.

Opportunistic Routing Algorithm Based on Energy Balance in Wireless Sensor Network

WANG Lei1,2，WANG Jun1,2，ZHU Zhi-wei1,2，WU Han1,2

(1.Key Lab of Broadband Wireless Communication and Sensor Network Technology of Ministry of Education,NJUPT,Nanjing 210003,China;2.Jiangsu Key Lab of Wireless Communication of NJUPT,Nanjing 210003,China)

Opportunistic routing achieves high throughput in the face of lossy wireless links.The current opportunistic routing protocol,MORE,is the first opportunistic routing work to adopt network coding,but in the selection of candidate forward node set,it only considers the quality of the link between nodes,which leads to premature dead for some nodes because of energy depletion,affecting the integrity of wireless sensor networks.Aiming at this outstanding issue,an improved routing protocol based on MORE is proposed,which balances energy consumption of wireless sensor nodes.According to transmission mechanism of opportunistic routing,considering the expected transmission count (ETX) and residual energy (RE),a new routing metric expected life time (ELT) and a selection strategy of candidate forward node set based on it is proposed.Finally,simulations are performed by NS2.The results show that in the basis of taking the residual energy into account,the improved MORE protocol not only ensures the reliability of data transmission,but also balances the energy consumption of nodes,improving survival of nodes and prolonging the network life cycle.

opportunistic routing;expected transmission count;residual energy;expected lifetime

2016-06-17

2016-09-21

时间：2017-03-07

国家自然科学基金资助项目(61401234)；江苏高校优势学科工程资助项目；江苏省政府留学奖学金

王 雷(1990-)，男，硕士研究生，研究方向为基于网络编码的数据收集技术；王 珺，博士，副教授，研究方向为下一代通信网络技术。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0922.080.html

TP301.6

A

1673-629X(2017)04-0034-05

10.3969/j.issn.1673-629X.2017.04.008