基于能耗梯度的无线传感器网络路由算法*

刘　帅，李正炜，吴元昊，王　斌，杨永健

（1.中国科学院长春光学精密机械与物理研究所，长春130033；2.吉林大学计算机科学与技术学院，长春130012）

基于能耗梯度的无线传感器网络路由算法*

刘帅1*，李正炜1，吴元昊1，王斌1，杨永健2

（1.中国科学院长春光学精密机械与物理研究所，长春130033；2.吉林大学计算机科学与技术学院，长春130012）

无线传感器网络中的节点能量有限且较难补给，网络生命周期难以保证，这大大影响了其应用的场景和范围。为解决上述问题，提出了一种新的路由算法EDROPL，算法通过将网络进行区域划分，引入能耗梯度概念，采用适当的评价函数指导簇首节点的选择，同时采用簇首之间层次转发数据等方法优化路由。仿真实验表明，EDROPL相对于LEACH算法以及LEACH-A算法、HRPNC等其他能耗模型算法能更好的均衡网络能耗，提高网络生命周期。

无线传感器网络；路由；能耗梯度；网络生命周期

无线传感器网络（WSNs）是一种通过将大量节点以自组织的方式进行连接，节点之间相互通信，从而实现信息发送和采集的目的［1］网络结构。由于WSNs的自组织特性［2］，其通常被安排在操作环境比较恶劣，不方便人为干预的地点工作［3］。WSNs中的节点一般由传感器、处理器和无线收发模块组成，由于WSNs工作环境的特殊性，其能耗供给方式大多为采用电池提供［4-5］，因此降低网络能耗是提高网络生命周期的关键。

WSNs的节点中，无线收发模块会消耗90%以上的能量，因此采用合适的路由算法优化节点收发信息时采用的功率可以最大限度的降低网络能耗，提高网络生命周期［6］。

目前主流的路由算法可以分为平面路由算法和层次路由算法［7］。平面路由算法由于其高昂的路由建立和维护代价而渐渐地被层次路由算法所替代［8］。最经典层次路由算法是由MIT的Heinzelman提出LEACH算法［9］。该算法通过一定的簇首选举和入簇策略，建立多个层次结构，通过簇间转发的方式，降低通信能耗。文献［10］通过一种非均匀成簇方法（UCA）来以降低能耗。文献［3］提出了一种对节点进行能耗分级的非均匀分簇算法CHCI，在网络生存时间方面有了一定的提升。文献［11］采用了抑制低能量节点的数据发送量，簇内可变通信周期等策略，提出了ACPSEB-LEACH算法，该算法可以减少部分节点的能量消耗。文献［12］提出的HRPNC算法通过分层机制及竞争半径机制选取簇首，使簇首节点分布更加合理，能有效均衡节点的能量消耗。采用能量模型的路由算法中，由刘永超等提出的A-LEACH算法［13］比较有代表性。A-LEACH算法综合考虑了节点剩余能量和节点密集程度在簇首节点选择中的分量，在一定程度上提高了网络的生命周期。本文主要针对大部分层次路由算法在均衡能耗［14］和延长网络生命周期的不足，提出了综合考虑能耗，节点密度和基站位置的EDROPL算法。

本文提出的EDROPL算法将节点通信距离和节点能耗梯度加入到簇首选举代价函数，并在簇首之间采取多跳传输方式实现网络通信。能在网络能耗，网络生命有效周期和吞吐量方面有较好的提高。

1　典型层次路由算法简介

1.1LEACH

LEACH是最早被提出的层次路由算法，算法的建簇工作采用以下方式进行。在每一轮次开始时，每个存活的节点产生一个（0，1）区间上的随机数，如果该随机数小于阈值T（n），则节点n当选为簇首节点。T（n）的计算方法如公式1.1所示。

其中，r是当前轮次，p是网络中簇首节点的比例，G是一个集合，其中的元素是最近1/p轮次内没有当选过簇首的节点。从公式中可以看出，在每一个1/p轮次之内，随着轮次的增加，T（n）的值越来越大，则节点成为簇首节点的概率也更大。一旦节点成为簇首，则在接下来的1/p轮次之内其将不再参与簇首的竞选。当簇首选举结束之后，网络中的其他节点根据自己到簇首节点的距离采用就近原则加入簇内，成簇工作完毕。

LEACH算法的簇首选择方法在一定程度上保证了网络的公平性。使得节点都相对均匀的成为簇首，防止了某些节点多次成为簇首而导致的过早死亡。但LEACH算法也存在一些不足，主要包括：①稳定性比较差，选择簇首时采用的随机策略，导致每一轮次的簇首数量变化比较剧烈；②没有考虑簇首节点密度的问题，导致可能出现某一区域簇首节点聚集或十分稀少的现象；③不能动态调节簇首的选择，某些能量低的节点在纯随机的选举策略下仍然有概率成为簇首［15］。

1.2A-LEACH

A-LEACH算法是一种典型的采用能耗和距离模型的WSNs路由算法。该算法的过程主要分为以下几个阶段。

①分区阶段

算法根据网络中的节点到基站的距离将节点分入不同的区域，簇首只在本区域内招募簇内成员。

②簇首选举阶段

A-LEACH算法综合考虑了节点的剩余能量以及与邻居节点的紧密程度，给出了一个节点当选簇首的概率计算函数：

其中，c1，c2是权重系数，E（i）是节点目前轮次的剩余能量，Eave代表所有节点能量的平均值，Nneigh（i）是节点的密集程度，nalive是网络中存活的节点数量。每一轮次计算每个节点的P值，选最大的节点作为簇首，其他节点按照就近原则选择自己加入的簇。

③信息传输阶段

采用簇首接收簇内成员消息，进行融合操作，之后将融合结果通过距离基站更近的节点转发的方式，传输到基站节点。

A-LEACH算法创新性地将节点剩余能量比的概念引入到路由算法之中，用节点的剩余能量作为选举簇首时的重要参数，在一定程度上保证了节点之间能耗的公平性，提高了网络生存周期。但节点的剩余能量并不能很好地预测该节点未来的能耗速度和预期存活时间。

1.3HRPNC

文献［11］提出了一种采用增加分层机制和竞争半径机制，从而节约能耗的层次路由算法。

该算法的主要工作过程如下：

层次划分：将整个网络区域按照距离基站的距离进行区域划分，将小于d0的区域划分为第一区域，之后按照划分间隔进行其他区域的划分。

①计算簇首数量

按照一定的百分比为各个区域分配一定数量的簇首。

②计算竞争半径

采用式（3）计算出基准竞争半径。其中Ak是区域k的面积，mk是该区域的簇首节点数量。再根据式（4）计算出每个节点的竞争半径。其中ri为节点与基站的距离，rmin，rmax分别为该层次距离基站的最近和最远距离，K1=0.5，K2=2。

③成簇

选择和LEACH算法相同的簇首候选方法，即根据式（1）选出候选簇首，之后候选簇首判断在自己的竞争半径中是否存在其他候选簇首，如果不存在则自己当选簇首，其他的节点按照就近原则加入簇内。

HRPNC算法能在一定程度上保证簇首分布的均匀性，提高了路由效率。该算法的局限性在于只考虑了簇首的分布对能耗的影响，没有将能耗速度作为另外的参考标准，使得对能耗速度控制不足。

2　基于能耗梯度的EDROPL算法

EDROPL算法，本质上是一种采用功率控制手段达到网络拓扑建立的方法。其要求无线传感器网络具备以下几个特点：①由相同的传感器节点组成网络（同构性）；②传感器节点拥有自己的位置信息；③网络中存在唯一的基站；④网络中节点拥有唯一标识号。

2.1区域划分

首先根据各个节点到基站的距离，将整个网络区域进行划分。划分方法为基站向整个网络广播自己的位置信息和区域划分策略；该划分策略的主要参数是节点到基站的距离以及与基站之间的相对位置关系。节点收到该广播信息之后，通过自己的位置和基站的位置，计算自己与基站之间的距离，同时计算自己相对于基站的方位，并根据广播中的区域划分策略将自己归入固定的区域之内，保存区域信息。分区效果如图1所示。

从图1中的区域划分方法可以看出EDROPL算法和A-LEACH算法在网络分区部分的处理方式基本相同。

图1　区域划分结果

2.2簇首选举和节点入簇

簇首的选举工作在各个区域内同时进行。首先引入选举簇首评价函数，如式（5）所示。

其中，α，β，γ为权重系数，Edrop是节点能耗梯度值；D是节点密度，ls是节点到基站的距离评价值。Edrop的计算方法如公式（6）所示。

其中，EΔr代表第r轮次开始之前和第r-1轮次开始之前，节点的剩余能量的差，Er代表当前第r轮次开始之前，网络中节点的总剩余能量，k用来控制梯度精度，成为能耗梯度系数，nalives代表当前网络中剩余的存活节点的数量。因此Edrop就代表了节点最近k轮次的平均能耗速度，相对于整个生存周期而言，它可以称为r轮次附近的瞬时能耗速度，反映了当前节点的存活时间的期望。

D的计算方法如式（7）所示。

其中dij是节点i与在邻域Δ为范围内的邻居节点j的距离，A是网络区域的规模。D体现了节点i与其邻居节点在位置上的紧密程度，其值越小代表与邻居节点越紧密。

ls的计算方法如式（8）所示。

其中Dis是节点i到达基站的距离，A是网络区域的规模。ls体现了节点i到达基站的距离评价。

所有节点根据自己的当前信息，利用式（15）来计算自己的评价函数值Wi，并生成一个四元组，其中Si为i节点所属的区域编号，idi是节点编号，posi是节点的位置信息。当节点j接收到来自于节点i的四元组信息时，首先通过Si判断i节点是否与自己属于同一个区域，如果Si≠Sj，则j节点将此消息忽略；网络中所有节点都维护一个评价函数排序表T，如果Si=Sj，则j节点将i节点视为候选簇首，并将idi放入表T内，其位置满足以下要求：Wi的值大于等于排在idi之前所有节点的W值，同时Wi的值小于等于排在idi之后所有节点的W值。按照这种方法，当所有节点完成四元组的发送和接收之后，任意一个节点都保存着与其属于同一个区域的邻居节点的评价函数值和排序结果。各节点按照排序结果决定自己是否成为簇首节点。要求任意两个簇首之间的距离不能过近，否则容易出现过于集中的簇，导致网络资源浪费。

选举结束之后，当选为簇首的节点向自己的邻域内广播成为簇首的消息，各节点根据最近原则选择入簇。

2.3消息传输

簇建立结束之后，簇首要选择自己发送消息的目的节点，即下一跳簇首节点。要求簇首的下一跳节点必须处于编号更小的区域之内，即距离基站更近，当前簇首节点只考虑距离自己最近的更近区域的簇首作为下一跳节点，当节点已经处于距基站最近的区域时，下一跳节点就是基站。这里为了减少消息发送数，规定，若当前节点到基站距离d＜d0（见式（9）），则直接发送费基站，否则采用多跳方式发送。

3　仿真实验

本文采用Matlab仿真软件对EDROPL与第1小节中介绍的LEACH、A-LEACH和HRPNC算法进行仿真对比。设计的网络区域为100 m×100 m的矩形区域，表1给出了该仿真实验的具体参数。

表1　仿真实验参数

实验中的通信能耗模型采用公式（9）所示。

式（5）中取α=0.7，β=0.2，γ=0.1，这样做的目的是保证能耗梯度分量占据主要作用，网络规模A采用网络区域边长衡量。在实际应用中，我们也建议将α的值选取为三个因子中最大的，能耗梯度是指导路由的最关键因素，因子β，γ的选择依赖于原始网络的状态，若网络中存在较多的分散的节点，则取β稍大些，以更容易推荐紧密程度高的节点，而当网络中存在较多的距离基站节点超过d0的节点时，则取γ更大一些，以更容易选取距离基站更近的节点作为簇首。

实验将本文提出的 EDROPL算法和经典LEACH算法以及经典的能耗拓扑算法A-LEACH、HRPNC算法进行对比，共进行1900轮次的仿真。主要对比了各个算法在保证网络拓扑稳定性、提高生命周期和降低网络能耗等方面的表现。

图2中对比了A-LEACH、HRPNC和EDROPL算法在网络拓扑稳定方面的表现，当各个节点有比较均衡的的机会成为簇首节点时，整个网络的稳定性会相对较好，从图2可以看出，在A-LEACH和HRPNC算法中，由于网络中存在比较明显的集中分布现象，导致某些节点邻域内的节点总数一直保持较高的水平，因此导致这些节点过多的担任了簇首工作，同时存在一些节点几乎没有当选过簇首。EDROPL算法由于引入了能耗梯度的分量，能保证节点都有较为均衡的机会担任簇首，某些地理位置相对集中的节点，会导致前期更多地担任簇首工作，同时也因此导致能耗下降速度也更快，逐渐降低担任簇首的可能性。

图2　节点担任簇首次数

图3是对4种算法在各个轮次结束之后，网络中存活节点数量的对比结果。LEACH算法在第803轮次出现首个死亡节点，A-LEACH算法在623轮出现首个死亡节点，HRPNC算法在630轮出现首个死亡节点，EDROPL算法的首个死亡节点出现在716轮。当出现首个死亡节点之后，LEACH算法的死亡节点数会快速增加，存活节点数下降比较迅速，A-LEACH 和HRPNC算法的节点死亡速度要更低一些，但其在1 200和1 180轮次之前的存活节点数量都少于LEACH算法，当到达约 1 600和 1 800轮次时，A-LEACH和 HRPNC算法的节点全部死亡。EDROPL算法表现出了更低的死亡速度，且首个死亡节点较其他两种能耗算法出现的更晚，这是因为对能耗速度下降的估计，可以有效地指导簇首节点的选择，A-LEACH算法仅仅对节点的剩余能量进行评价，能耗下降速度相比剩余能量更能反映出节点的预计的生存时间。同时，当仿真轮次到达1 100轮时，EDROPL算法的节点存活数量较LEACH算法更多，并保持了更低的死亡速度。对于无线传感器网络而言，保证一定量的冗余节点是必要的，当节点存活数高于某一数值（一般为40%）时，网络就可以正常工作。图中可以看出，采用LEACH、A-LEACH和HRPNC算法时，当仿真轮次到达1 200轮时，存活节点数量减少到40个，而EDROPL算法运行至1 500轮次时，存活节点数减小到40个。所以，EDROPL较其他三种方法相比可以使网络保持更长的正常工作时间。

图3　网络节点存活数量

图4是4种算法在网络能量方面的表现。由于在仿真初期，节点剩余能量相差不大，速度下降经验值不足，导致各个算法在前450轮次的能耗表现基本相同，同时由于A-LEACH算法更多地依赖距离分量，导致前期过多节点多次担任簇首，能耗下降速度更高一些。当轮次在500轮之后，本文提出的EDROPL算法表现出使用能耗梯度经验值来选举簇首的优越性，其下降曲率逐渐低于LEACH和A-LEACH算法，在600轮之后，算法逐渐优于HRPNC。该算法能更好的保护估计剩余时间更少的节点。从图3和图4可以看出，当到达1 500轮次时，LEACH和A-LEACH算法中的节点基本全部死亡，而EDROPL算法中还38个节点存活，在1680轮次时HRPNC算法节点全部死亡，EDROPL仍然存活12个节点。

图4　网络剩余总能量

图5为4种算法中，基站收到的消息数目。可以看出，LEACH和A-LEACH算法在仿真至1 100轮次左右时开始出现数据包下降现象，说明网络中的存活节点已经不多，进而导致簇首节点减少，HRPNC在1 500轮次时消息数量开始明显减少，而EDROPL算法的表现比较好，最后发送的数据总量约为前两种算法的1.8倍，HRPNC的1.3倍，表明其可以有较好的网络吞吐量的保证。

图5　基站收到的消息数

图6是EDROPL算法运行至1 500轮次时，网络中各个节点的剩余能量直方图表示。可以看出，网络中的各个节点能量相差不多，EDROPL很好的做到了能量平均。在此之后，EDROPL又继续运行了大概400轮次，直到所有节点死亡。

图6　EDROPL算法在1500轮次时节点的剩余能量

最后我们给出式（6）中的能耗精度控制系数k的取值与节点存活率的关系。图7是当仿真运行至1 500轮次时的情况。可以看到，k的取值会比较大的影响到节点的存活率，取k=4时，存活率达到最大值，此时网络中存活节点数为38个，而其他取值，无论大于4还是小于4，存活数都更低一些。这是因为，k值直接决定了采用的能耗梯度的精度，当k值较小时，式（6）可以代表此时瞬时的能耗速度，但采样较少，代表性较低，而当k值较大时，又降低了瞬时性的意义，使得式（6）的值趋于平均化，同样降低了能耗速度的代表性。

图7　能耗梯度系数k与存活节点数的关系

4　总结

对于节点资源有限的无线传感器网络，如何降低能耗是一个重要问题。本文提出了一种采用能耗梯度作为评价参数的路由算法EDROPL。通过仿真实验的方式证明了EDROPL算法的可行性，由于引入了能耗梯度的计算，为分簇算法提供的能耗经验值可以很好的均衡网络能量。相比经典的LEACH算法、改进的A-LEACH和HRPNC算法，EDROPL算法在保证网络拓扑稳定，延长网络生命周期，降低和均衡节点能耗和提高网络吞吐量等方面有明显的提升。

［1］洪锋，褚红伟，金宗科，等.无线传感器网络应用系统最新进展综述［J］.计算机研究与发展，2010，47：81-87.

［2］宋立新，戴赫.基于蚁群算法的WSN路由协议研究［J］.哈尔滨理工大学学报，2014，16（6）：88-92.

［3］康琳，董增寿.基于簇头分级的改进非均匀分簇算法［J］.传感技术学报，2015，28（12）：1841-1844.

［4］张伟伟.无线传感器网络的拓扑控制策略研究［D］.曲阜师范大学，2009.

［5］王科强，张彦波，项伍锋，等.无线传感器网络分层带宽自适应路由协议［J］.传感器与微系统，2014，33（3）：132-134.

［6］李芳芳，王靖.一种基于LEACH协议的无线传感器网络路由算法［J］.传感技术学报，2012，25（10）：1445-1452.

［7］白凤娥，李环.能量均衡的无线传感器网络非均匀分簇算法的研究［J］.计算机与数字工程，2012，40（1）：28-31

［8］Heinzelman W B，Chandrakasan A P.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］. IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［9］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Sensor Networks［C］// Proceedings of 33th IEEE Annual Hawaii International Conference on System Sciences，2000：10.

［10］Yuan Huiyong，Liu Yongyi，Yu Jiaping.A New Energy-Efficient Unequal Clustering Algorithm for Wireless Sensor Networks［C］// IEEE Conference Proceedings，2011：431-434.

［11］叶继华，王文，江爱文，等.一种基于LEACH的异构WSN能量均衡成簇协议［J］.传感技术学报，2015，28（12）：1853-1860.

［12］黄廷辉，伊凯，崔更申，等.基于非均匀分簇的无线传感器网络分层路由协议［J］.计算机应用，2016，36（1）：66-71.

［13］刘永超，张月霞，缪旻，等.基于能量和距离的分区域选择簇首WSNs路由算法［J］.传感器与微系统，2015，34（1）：124-127.

［14］Y.Jennifer，M.Biswanath，G.Dipak.Wireless Sensor Network Survey.Computer Networks，2008（52）：2292-2330.

［15］孙建伟，王绍辰，贾军营，等.一种针对无线传感器网络LEACH协议的改进算法［J］.计算机系统应用，2015，24（12）：186-190.

刘帅（1988-），男，吉林长春人，初级研究员，硕士，现主要从事无线传感器网络路由算法，PSN网络路由算法等方向研究，149390771@qq.com；

李正炜（1988-），男，福建龙岩人，博士研究生，主要从事无线传感器网络等方面的研究；

吴元昊（1977-），男，吉林长春人，副研究员，博士，主要从事无线传感器网络，图像处理算法等方面的研究。

Routing Algorithm for Wireless Sensor Network Based on Energy Consumption Gradient*

LIU Shuai1*，LI Zhengwei1，WU Yuanhao1，WANG Bin1，YANG Yongjian2
（1.Changchun Institute of Optics，Fine Mechanics and Physics，Chinese Academy of Sciences，Changchun 130033 China；2.College of Computer Science and Technology，Jilin University，Changchun 130012，China）

The energy of the nodes in wireless sensor network is limited and difficult to be supplied，so the network life circle is hard to be ensured，which has a negative effect on being used in so fields and ranges.To overcome the disadvantages above，a new routing algorithm called EDROPL is proposed.This algorithm optimize routing by dividing sections，importing the concept of energy gradient，choosing the cluster heads by some appropriate evaluation function，and transmitting packages between cluster heads.The simulation result shows that EDROPL has a better performance in balancing the network energy consumption and improving the network life circle comparing with LEACH，LEACH-A and HRPNC energy based algorithm.

wireless sensor network；routing；energy consumption gradient；network life circle

TP393

A

1004-1699（2016）08-1247-06

EEACC：6150P10.3969/j.issn.1004-1699.2016.08.021

项目来源：国家高技术研究发展计划（863计划）项目（2013AA8083042）；国家自然科学基金项目（61272412）；教育部博士项目基金项目（20120061110044）；吉林省科技发展计划项目（20120303）

2016-01-20修改日期：2016-03-30