能量均衡的AD Hoc网络路由协议研究

刘 宏，夏未君，王其涛

(江西理工大学 电气工程与自动化学院，江西 赣州 341000)



能量均衡的AD Hoc网络路由协议研究

刘 宏，夏未君，王其涛

(江西理工大学 电气工程与自动化学院，江西 赣州 341000)

传统的ADHoc路由协议由于节点的能量不均衡，导致网络耗能较大，减少了网络生命周期；-从能量均衡角度提出了一种能量优化的AdHoc网络路由协议(EOARP协议)，通过引入公共经济学中洛伦茨指数法来衡量网络的能耗均衡，结合节点通信繁忙程度、节点剩余能量等因素建立代价函数PEQ，选择剩余能量相对较高，通信繁忙程度较轻的路由链路，从而达到均衡网络的目的；仿真结果表明，EOARP协议在数据传输性能、能量均衡、以及网络节点剩余能量等方面指标均有较大改善，有效地延长了网络生命周期。

无线传感器网络；路由协议；能量均衡；能量优化

0 引言

AD Hoc网络[1]是由移动终端所组成的具有自主性、临时性、无基础设施要求、多跳临时性自治网络系统，现已得到广泛应用。由于AD Hoc网络的资源有限、拓扑结构动态、无全局标识、带宽低等特性，会导致出现以下两个问题[2]：

1)在理想的网络中，每个节点的能量消耗应该是比较均等的，不会出现某个节点由于能量耗尽而过早的退出网络，这样就使得整个网络的存活时间最长。然而在实际AD Hoc网络中，一些处在网络中心的节点由于频繁的参与路由的建立、转发而导使这些节点的能量消耗过大，导致路由链接断裂，降低网络生命周期；

2)当网络中的业务量比较大时，许多的链路可能会共用一个或几个节点作为路径的中间转发节点，尤其是处在网络中心位置的一些节点，因而导致网络的流量传输不均衡，部分中心节点负载过重，就会发生数据拥塞。降低了网络性能。

近年来，关于AD Hoc网络协议[3]节能和延长网络生命周期的研究已成为人们的研究热点。并且提出了多种节能传输方案：文献[4]中提出的基于跳数的无线传感器网络路由算法，这个算法的优点是设计思路简单有效，可靠性、负载均衡、网络的生命周期都得到了提高，但是随着发包频率的增加，算法优势不在，保障机制不明显；文献[5]提出的LEACH协议，提出了数据聚合的层次路由协议，协议通过周期性的选择簇头来平衡网络各节点的能量。该协议的优点是选择簇头不固定，从而使网络节约了能量，增加了生存时间。但是该协议需要节点具有较大功率，导致移动性变差，而且对大规模网络不适合；文献[6]提出了WSN动态重传算法，减少了重传的次数，降低了网络能耗，但是可靠性没有得到足够的保证；文献[7]提出了基于能量角度联合自适应路由修复算法，通过计算剩余能量的大小，选择最佳的路由。其优点是延长了网络节点的生存时间。缺点是协议不稳定，因为很容易受到外界因素的干扰；文献[8]提出的TEEN协议，与LEACH采用相同的聚簇方式。其优点是使数据传输量减少，而且其层次型簇头结构对节点功率没有要求。但是因为存在门限设置，使某些数据上报受阻。

基于此，本文能平衡网络各节点能量角度出发，提出了基于能量优化的路由协议(Energy Optimization Ad Hoc Routing Protocol，EOARP)，该协议综合考虑网络各节点的通信繁忙程度，并引入公共经济学中洛伦茨指数法[9](Approach of Lorenz)来衡量网络的能耗均衡，由此建立代价函数PEQ，根据代价函数选择剩余能量相对高，通信繁忙程度相对轻的路由链路，从而达到均衡网络的目的。

1 能量均衡代价函数建立

EOARP路由协议不是单纯以最短路径为路由，而是从均衡网络各节点能量方面着手，选择剩余能量相对高，通信繁忙程度相对轻的路由链路，均衡网络能量。从而最大限度地延长网络的生命。

1.1 节点通信繁忙程度

节点通信繁忙程度是衡量路由协议质量的重要指标，节点越繁忙，该节点就越耗能，且不能及时接收数据，影响通信质量，故必须综合分配各节点的通信。设节点i的通信繁忙程度[10]为Ri，如式(1)所示：

(1)

其中，Qlen表示当前转发缓存队列长度，Qmax表示节点转发缓存队列的最大长度，Nlink表示节点当前的连接数，Nneighbor表示节点当前的邻居节点个数。和是系数，满足a1+a2=1。Ri越大，说明节点i通信越繁忙。

1.2 能量均衡路由

节点耗能管理是各路由协议均要重点考虑问题，本协议从维护各节点能耗的均衡方向入手，引入公共经济学中洛伦茨指数法来衡量网络的能耗均衡。

根据美国著名统计学家M.O.洛伦茨提出的洛伦茨曲线，按照节点现有贮能从低到高排序得出了网络内节点数累计百分比和节点剩余贮能累计百分比的洛伦茨曲线，并在此曲线的基础上得出了度量节点剩余贮能分配不公平程度测定的基尼系数[11](Gini Coefficient)。如图1所示。

图1 网络内节点数累计百分比(%)

基尼系数为洛伦茨曲线与45度对角线围成的面积和45度对角线以下的三角形面积之比。其取值范围为[0，1]，当各节点剩余贮能完全相等时基尼系数就为0；当仅有一个节点剩余贮能为初始贮能E0，而其余节点剩余贮能均为0，则基尼系数就为1，达到了能量分配最不公平状况。

基尼系数可由式(2)计算得出：

(2)

(3)

进一步定义节点i的贮能剩余率[12]ηi如式(4)所示：

(4)

式中，Ei为节点i的剩余贮能，E0为其初始贮能。

在进行路由选择时，将结合网络基尼系数及节点剩余贮能进行比较，选择剩余贮能最多的路由链路，实现能量均衡的目的。

1.3 路由代价函数

由上所述可得到基于能量有效的路由代价函数，当网络基尼系数在0.5以内，说明在当前的网络内，各节点剩余贮能比较平均。而且基尼系数越小，各节点剩余贮能越平均，当基尼系数为0时，表明网络各节点剩余贮能都一样，且在路由选择时更偏重选择节点通信繁忙程度较轻的链路；而当网络基尼系数大于0.5，说明当前网络内各节点剩余贮能相差校大，基尼系数越大，各节点剩余贮能就相差越大，此时，路由选择则以偏重选择链路剩余贮能较的链路。综合考虑网络内各节点繁忙程度以及能量均衡机制，定义代价函数PEQ如式(5)所示：

(5)

由此可定义网络最佳路由选择函数，如式(6)所示

PathSelect[source,dest]=min[PEQ(K)]k∈[1，M]

(6)

式中，M表示本协议所形成的多条备选路径。

2 能量有效的路由的建立

当源节点S需要与目标节点D通信时，由于其路由表中没有相关路由条目信息，于是源节点就按如下步骤发起路由发现过程：

1)源节点S创建一个RREQ消息，消息中包括源地址、目标地址、目标节点序列号等，并将此RREQ向周围邻居节点广播；

2)邻居节点N收到一个RREQ消息后，首先对此消息进行判断，如果是首次收到该RREQ且本节点不是目标节点时，则根据自身链路通信状态及能量状态由式(5)计算此链路的累计链路代价值，然后再转发该RREQ消息到它的邻居节点。如果节点不是首次收到该RREQ，前面已收到相同广播标识的RREQ时，则节点丢弃该消息；

3)当RREQ消息转发到目的节点D后，沿途经过的节点都建立起到源节点的反向路由，让RREQ消息在网络内转发已经产生RREP消息返回源节点；

4)源节点S收到RREP消息后，由式(6)计算出最佳路由链路，其余则作为备份链路保留下来。

3 路由维护

网络运行中，各节点通过周期性地向周围邻居节点发送TTL[13]为1的“Hello”消息，以确定该节点到达邻居节点的可达性，如果检测到节点检测到它的上游节点或下游节点链路断开，则该节点将通知源节点重新根据前面式(6)，从多条备选路由中选择一条链路代价最小的链路代替断开链路。

4 性能分析与仿真

本文使用NS-2(版本2.34)[14]进行仿真，将EOARP路由协议与E-AODV(An Energy-efficient AODV)[15]协议、I-LEACH(Improved LEACH )[16]进行比较，分别在数据传输性能、能量均衡、以及网络节点剩余能量[17]等方面指标进行比较。

4.1 仿真参数设置

假定网络传感器节点随机分布在正方形区域范围，且在此区域内各节点随机分布，实验主要参数设置如表1所示。

4.2 仿真结果

1)数据传输性能比较：

路由协议数据传输性能，可从数据包投递率和路由开销两方面进行仿真，仿真EOARP、E-AODV、I-LEACH3种路由协议的数据包投递率，如图2所示。仿真结果表明，EOARP、E-AODV、I-LEACH这3种协议均保持着较高的投递率，随着时间的延长，数据包投递率相应增加，E-AODV协议和EOARP协议均保持了较高的数据包投递率，且EOARP协议最高。

表1 仿真参数

图2 数据包投递率比较

仿真EOARP、E-AODV、I-LEACH三种路由协议的路由开销，如图3所示，仿真I-LEACH协议在路由开销最小，E-AODV协议最大，而EOARP协议由于路由代价函数占用了一定的资源，导致路由开销稍微变大相比I-LEACH协议稍弱。

图3 路由开销比较

2)能耗均衡比较：

仿真EOARP、E-AODV、I-LEACH三种协议下节点平均消耗的能量比较网络能量消耗的均衡性。结果如图4所示。从图中可以看出：E-AODV和I-LEACH协议能耗因为也采用了能量优化算法，波动不是很大，但是能耗维持在0.5 J左右。而EOARP协议网络的能耗一直比较的平稳，保持在0.4 J左右，表明EOARP协议网络耗能比较均衡。

图4 能耗均衡比较

3)节点剩余能量比较：

在EOARP、E-AODV、I-LEACH三种协议下，仿真网络节点的平均剩余能量随网络运行时间的变化情况，结果如图5所示。由图中可看出：在0～50 s范围内E-AODV、I-LEACH、EOARP三种协议节点耗能均不大，50～150 s范围时E-AODV、I-LEACH协议节点耗能明显提高，耗能达60%以上，而EOARP协议节点耗能为50%左右。至250 s时，EOARP协议节点耗能才达到80%左右，而E-AODV、I-LEACH协议节点耗能已达90%以上。在整个网络运行时间，EOARP协议均比E-AODV、I-LEACH协议的节点剩余能量剩余能量要多。

图5 节点剩余能量比较

5 结论

从能量均衡角度出了提出了EOARP路由协议，该协议通过引入公共经济学中洛伦茨指数法来衡量网络的能耗均衡，建立代价函数PEQ，根据代价函数选择剩余能量相对高，通信繁忙程度相对轻的路由链路，从而达到均衡网络的目的，提高了网络的能量利用率，节约能源。仿真结果表明：文中提出的EOARP路由协议在数据传输性能、能量均衡、节点剩余能量等方面指标方面均比E-AODV协议、I-LEACH协议有较大的改善。

[1] 赵志峰,郑少仁. Ad hoc网络体系结构研究[J]. 电信科学,2001,12(1)：14-17.

[2] 麻晋文. 移动Ad hoc网络中AODV路由协议的研究[D].兰州：兰州大学,2014.

[3] Ad M, Perkins C E, Das S R. Ad hoc On-Demand Distance Vector (AODV) Routing[J]. Rfc, 2000, 6(7)：90.

[4] 任丰原，黄海宁，林 闯．无线传感器网络[J]．软件学报，2013，14(7)：1282-1291．

[5] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks[A]. System Sciences Proceedings of Annual Hawaii International Conference on[C]. 2000，8(8)：8020.

[6] 张足生，袁华强，于峰崎．无线传感器网络动态重传算法[J]．传感技术学报，2013，10(7)：1019-1024．

[7] 朱全政，杨 乐．能量角度联合自适应路由修复新算法[J]．计算机应用研究，2014，31(6)：1779-1782．

[8] Manjeshwar A, Agrawal D P. TEEN：a protocol for enhanced efficiency in wireless sensor networks[A]. Proceedings of International Workshop on Parallel & Distributed Computing Issues in Wireless Networks & Mobile Computing[C]. 2001：2009 - 2015.

[9] 刘志伟. 收入分配不公平程度测度方法综述[J]. 统计与信息论坛,2003,18(5)：28-32.

[10] 王志远. 基于节点稳定性和路由失效预测的SP_AODV路由协议的研究与实现[D].沈阳：东北大学,2010：22-23.

[11] 胡祖光. 基尼系数理论最佳值及其简易计算公式研究[J]. 经济研究,2004,(9)：60-69.

[12] 刘 杰,王 玲,王 杉，等. 基于能量有效的逆向AODV路由协议研究[J]. 计算机应用研究,2015,32(6)：1849-1851.

[13] 荀宝铖,罗军勇. 基于TTL值异常的源地址伪造报文检测方法[J]. 计算机应用研究,2006,12：127-128.

[14] 王永胜, 吴德伟, 刘 勇. 基于NS2网络仿真研究[J]. 计算机仿真, 2004, 21(11)：257-259.

[15]罗玉宏,王建新,陈松乔. 一种基于链路稳定的能量有效AODV路由协议[J]. 电路与系统学报,2008,(6):141-147.[16]吕 涛,朱清新,张路桥. 一种基于LEACH协议的改进算法[J]. 电子学报,2011,(6):1405-1409.

[17]林 恺,赵 海,尹震宇，等.无线传感器网络路由中的能量预测及算法实现[J].通信学报,2006,27(5)：21-27.

Research on Energy-balanced AD Hoc Network Routing Protocols

Liu Hong,Xia Weijun,Wang Qitao

(School of Electrical Engineering and Automation,Jiangxi University of Science and Technology，Ganzhou 341000,China)

The unbalanced node energy of traditional AD Hoc routing protocol causes alarger network energy,and it reduces network lifecycle.The article presents a energy optimization of Ad Hoc Network Routing Protocol (EOARP protocol) from the point of energy balance.Through the introduction of public economics Lorenz index to the average energy consumption of each node in the network,combined with the busy degree in communication and residual energy of nodes to establish cost functionPEQ.Select residual energy of the node relatively high,communication link routes is lesser busy, so as to achieve a energy-balanced network.As the simulation results EOARP routing protocol has improvement indexs such as data transmission performance, energy balance, and network node residual energy, so effectively prolongs the network life cycle.

wireless sensor network; routing protocol;energy balance;energy optimization

2015-09-13；

2015-10-20。

国家自然科学基金资助项目(61163063)。

刘 宏(1968-)，男，江西萍乡人，副教授，硕士研究生导师，主要从事无线传感器网络基础设施的理论和技术方向的研究。

1671-4598(2016)03-0204-04DOI：10.16526/j.cnki.11-4762/tp

TP

A