基于动态竞争的能量均衡非均匀路由协议

王宣懿，曾子维，王 刚

（辽宁科技大学 计算机与软件工程学院，辽宁 鞍山 114051）

无线传感器网络（Wireless sensor networks，WSN）由路由感知通信与计算能力的传感器节点组成，节点以自组织方式组成多到一的通信网络，再把采集到的数据以多跳的方式发送到sink 节点［1］。传感器节点主要靠电池提供能量，因此WSN 中能量消耗很受重视，降低能耗与提高网络寿命是路由协议研究的重点之一［2-3］。

为了延长网络生存周期，已提出很多分簇和多跳路由算法。最著名的分簇算法为Heinzelmen研究的LEACH（Low-energy adaptive clustering hierarchy）［4］。每一轮分为初始化阶段和稳定工作阶段。但在LEACH算法中簇间通信采用单跳，全部节点都可和汇聚点直接通信，距离基站较远的节点都会进行远距离通信［5］。因此，簇头能耗不均从而导致部分节点过早死亡。并且簇头选举的次数过于频繁，消耗了较多能量。在选举过程中也未考虑节点的剩余能量与位置分布。之后，PEGASIS［6］、EECS［7］、HEED［8］等优化算法被陆续提出，簇间多跳也陆续被广泛应用。多跳导致靠近基站的簇头节点需承载较多的转发任务，能耗高从而过早死亡，出现“热区”现象。为解决这一问题，蒋畅江等［9］提出 EEUC（Energy efficient uneven cluster）算法，该算法采用簇间多跳模式节省网络能耗，候选簇头通过节点位置采用竞争半径不同的非均匀构造簇策略，形成大小不等的簇。但是，在边缘区域中转发数据量很少，该算法仅考虑距离不考虑剩余能量作为负载大小不够全面，并仅以到基站的距离和竞争半径作为确定下一跳簇头集合的这种方式总能耗较大。针对此问题，文献［10］提出高效的非均匀分簇EUCA（Efficient uneven cluster）算法。熊科等［11］提出一种采用双簇头均衡能量消耗的非均匀分簇算法。在采用非均匀分簇思想时均需要基于竞争半径理论，但现有分簇路由协议中仍存在簇头选举不当和网络能耗不均等问题。因此，本文从提高簇头选举质量和提升簇间路由效率出发，针对现有计算阈值和竞争半径的方法，提出基于概率模型的分簇路由算法（Energy optimized uneven cluster routing，EOUCR）。EOUCR算法在分簇前通过动态的设定阈值，得到优质候选簇头，再基于各节点的动态竞争半径选出真正簇头。根据路由代价函数计算出各邻居节点路由代价值，选择函数代价最优的簇头节点担任中继节点，得到全局最优路径。期望在网络运行过程中能有效均衡节点能耗，延长网络寿命。

1 系统模型和定义

1.1 节点能耗模型

节点能耗由感知、通信、数据处理三方面构成，其中通信能耗占最大比例。采用Heinzelman［12］的简单能量模型，依据通信距离长短分为自由空间模型和多路径衰减模型。在实际应用中，传输能量基于一个阈值距离d0，当通信距离小于d0时，此时考虑为自由空间模型；否则将使用多路径衰减模型。

节点发送l比特数据到离自身距离为d的节点所消耗的能量计算式

节点接收l比特的数据需消耗的能量计算式为

式中：Eelec代表发送与收发单位能量消耗，nJ/bit；d为传输距离，m；εfs代表采用空间自由模型功率放大损耗，pJ/（bit·m-2）；εmp代表采用多路径衰减模型功率放大损耗，pJ/（bit·m-2）。

1.2 网络模型

假设本文网络中的节点在以下环境中：基站与网络中的节点随机部署，部署后位置固定，基站能量充足。同构节点初始能量相同且节点间可自由通信。节点分布均匀，具有相同的概率成为簇头。节点可根据接收到的RSSI（Received signal strength indication）信号强弱计算自身到节点的距离［13］，并可根据需要调整发射功率。本算法试图将网络采用非均匀分簇，使距离基站较近的簇范围较小，远离基站的簇范围较大，调整簇间转发数据平衡达到均衡网络的效果。

1.3 网络生存时间

采用数据发送的轮数来表示网络生存时间，每一轮数据传输，节点将监测到的全部信息都发送给sink节点，统计节点发送数据所消耗的能量，监控节点剩余能量，记载第一个节点剩余能量为零的轮数或死亡节点到达一定比例时的轮数。

2 基于动态竞争的非均匀分簇路由协议

EOUCR协议是一个分布式的并行成簇算法，有良好的扩充性。在成簇过程中采用轮循环方法，每一轮包含两个阶段：设置簇阶段和稳态路由转发阶段。本算法主要工作是对网络实现非均匀分簇，在候选簇头的选举和竞争以及簇间路由选择上进行协作设计。

（1）设置簇阶段：分为簇头选择和构成分簇两方面。首先通过与本文提出的阈值T(n)比较，得出候选簇头。参考相对剩余能量和位置参数得到簇竞争半径选举出最终簇头，既避免低能节点担任簇头，也通过监测位置使通信过程传输能耗降低且均衡，减少时延。

（2）稳态路由转发阶段：由簇内通信和簇间到基站通信组成。采用簇内单跳簇间多跳相结合的方式，以减少能耗为目的设计簇间路由。

节点在第r轮时理想状态下通信半径平均值

式中：在一正方形M×M监测区域，随机部署N个节点，且每个节点被选作簇头的概率为p；Nr为第r轮时网络中存活节点的个数。

基于理想通信半径平均值范围内的存活节点集合。节点的完美邻居节点集合定义

式中：d(i,j)为通讯半径内各节点i与j之间的距离，m；为节点j的剩余能量，J；V代表全部节点集合。

2.1 候选簇头的生成策略

LEACH 算法在簇头选举阶段，节点随机生成［0，1］之间的随机数，当随机数小于阈值T(n)时，该节点被选做簇头。阈值计算式为

式中：p为每一轮中期望的簇头数在网络节点总数的比值；r为当前所在的选举轮数；G为剩下的1/p轮中没有被选为簇头的全部节点集合。

通过对LEACH 算法的不足及其改进算法的研究，结合EEUC 提出的成簇思想，在EOUCR 选取候选簇头时引入相对剩余能量因子、相对簇内节点密度因子和同簇节点汇聚度因子。

（1）相对剩余能量因子：单独考虑剩余能量不能准确判定剩余多少，因此在阈值定义中加入相对剩余能量，其值会随着运行轮数变化波动，使阈值定义更为合理具有实时性。

（2）相对簇内节点密度因子：理想通信半径内的实际节点个数与监测范围内所有节点数的比。用来体现实际簇内成员数量值。比值越大说明实际邻居节点数量越大，被选为候选簇头的概率越大。

（3）同簇节点汇聚度因子：节点i的完美邻居节点集合内的所有节点到i的距离的平均值与理想通信半径的比值。其值代表簇内节点汇聚紧密程度体现了簇结构，当比值越大说明汇聚程度差，簇内通信时延大。

传感器节点预先根据阈值选出候选簇头节点，阈值T(n)计算式

式中：p为存活节点成为簇头的期望；r为当前循环轮数；G为最近1/p轮中未被选为簇头的节点集合；Er表示当前节点的剩余能量，J；Eavg为当前所有存活节点的平均剩余能量，J；Ni为节点通信半径内的节点数；Nnum为总的节点数；Di-avg为节点i的理想邻居节点集合内各节点到i节点的平均距离，m；Ri为理想平均半径；χ1、χ2、χ3代表三项因子的权重值并且χ1+χ2+χ3=1。

新的阈值T(n)特点：

（1）已成为过候选簇头的节点在往后的1/p轮循环中均不能选为簇头。

（2）随着轮循环增加未当选过候选簇头的节点选为簇头的概率逐渐升高。

（3）未成为簇头的普通节点根据收到广播信号的强弱加入信号最强的簇。

由于簇间多跳导致距离基站近的簇头承担的数据转发量大且能量消耗高，因而失效概率较大。为缓解这种现象，本文提出的算法使靠近基站区域选举的簇头数较多，成簇规模较小。即减少簇内通信能耗用于簇间转发，从而达到簇间能耗平衡。远离基站则相反。算法为每一个候选簇头设定了竞争半径，可以监控簇头在网络中的位置分布，即竞争范围Rc

式中：R是提前设定的最大竞争半径；dmax代表网络中节点到达BS的最大距离，m；dmin代表节点到达BS 的最小距离，m；α、β为位于0～1 之间的常量用于控制竞争半径取值范围。

2.2 簇头节点的确定

簇头节点的选择决定了网络能量均衡和数据收集效率。竞选簇头的算法内容为，每个候选簇头以范围和相对应的功率进行广播自身报文，内容包含节点自身ID、当前剩余能量Eres、竞争半径。同理也能获知其他邻居节点广播信息。参与竞选的所有候选簇头节点都建立自己的邻候选簇头集合并维护一张邻居节点信息集合表，内容包含邻居节点的ID、邻居节点剩余能量Eres、邻居节点竞争半径。候选簇头Si的邻居节点集合

将剩余能量与簇头集合中节点剩余能量进行比较，决定能否担任真正簇头。当候选节点竞争成功时，向邻居节点广播胜任消息，邻居候选簇头节点接收消息后退出竞选。簇头竞争规则如图1所示。R为相对应的竞争半径，Y1和Y3不在彼此邻居范围内，Y4位于Y2的竞争范围内为其邻居节点。因此Y1、Y3相互不影响，可同时成为簇头，而Y2成为簇头后Y4便退出竞选。

确定簇头节点后，簇头向全网广播竞选成功消息。普通节点解除睡眠状态，查看保存的通讯范围内簇头信息表，当只保存一个簇头信息表时，直接加入其簇。当保存多个簇头信息表时，根据接收信号强度大小，选择强度最大且通信代价最小的簇头节点并发送申请加入消息。距离相等则加入通讯半径更大的簇。

分簇结构如图2所示，实现整个监测区域网络的非均匀分簇，可以发现越是靠近基站的簇，成簇面积越小。在此基础上簇头对节点收集到的信息进行融合，以多跳的方式将数据发送给基站，进入数据通讯阶段即路由传输阶段。

2.3 EOUCR算法设计实现

在分簇阶段，首先监测范围内的所有节点并通过函数rand（0，1）生成随机数R。当随机数小于阈值T(n)时，其节点成为候选簇头，进行下一阶段的竞选。候选簇头节点通过式（7）计算出竞争半径Rc和簇头剩余能量，并以广播形式发送竞选簇头的消息Elect_msg。当候选簇头接收到其它的竞选簇头消息时，比较两节点的距离，若小于两者中任意一个节点的竞争半径，将该节点存储到自己的邻居表内，对比邻居表中节点的剩余能量大小，如其值均小于自己，则当选真正的簇头，否则退出竞选。竞选成功的簇头在通信范围内广播竞选成功信息Competehead_msg，普通节点若同时收到多个簇头消息，根据接收信号的强度大小，即选择距自己近的簇头申请加入。若普通节点没有收到任何簇头消息，则自己成簇头。直到监测区域的所有节点都加入簇，成簇阶段就结束了。本算法流程图如图3所示。

2.4 簇间基于能量代价多跳路由协议

当设置簇阶段过程结束后，WSN 进入稳态路由转发阶段，此阶段的主要目标是在簇间选择最优的路径进行数据传输，从而达到提升网络性能的目的。EOUCR算法在传输距离较远时，簇头选出适合自己的其他簇头节点作为中继节点，通过中继节点将数据转发到基站。因此提前建立多跳传输路径，选择出可靠性高、能耗均衡的最优路径。详细步骤如下：

首先节点采集数据，并将采集数据以TDMA的方式发送给自己的簇头节点。簇头把采集到的信息通过数据融技术进行融合然后转发到汇聚节点或基站。当簇头有发送或转发数据任务时，簇头查看邻居节点与基站的距离，选择比自身更接近基站的向前邻居簇头节点并计算路由代价函数，选择代价函数最优的节点进行数据转发。当节点成为下一跳时，数据会成功地发送到该节点，直至数据转发成功，形成可靠性高的最优路径。

向前邻居节点的定义

路由代价函数

式中：ETx(l,d(i,j))为i和j节点间发送比特数据所消耗的能量，J；d(j,BS)是节点j与基站之间的距离，m；c1～c3为加权参数且满足c1+c2+c3=1，经反复实验将其值设为0.4，0.3，0.3。

由式（10）可知，簇头节点有更大概率成为下一跳节点的条件为：

（1）簇头节点剩余能量高。（2）发送数据所需能量越少。（3）簇头与基站的距离更近。（4）簇头间的距离更短。

由于簇头承担了网络中大量数据的通信与转发，因此均衡各簇头间的能量消耗是路由重要考虑因素之一，本文提出基于簇头剩余能量以及发送数据消耗能量和簇头间距离等因素来确定路由代价函数，动态选择并调整下一跳簇头节点，相比于EEUC等算法在均衡能耗方面更加出色。

3 仿真实验与结果分析

3.1 仿真方法及参数设置

本文在MATLAB 平台进行仿真实验，将400个无线传感器节点随机部署在一个200 m×200 m的监测区域内，节点分布均匀且基站设立在坐标（200 m，250 m）处，基站能量充足不做考虑。能量参数如表1所示［12］。

3.2 能耗均衡性

在算法比较时，考虑到文献［13］定义网络死亡节点数超过20%以上时将影响网络正常工作。因此实验记录死亡节点占比超过20%时，网络节点分布情况图4所示。

表1 仿真场景及参数Tab.1 Simulation scenarios and parameters

LEACH 协议采用随机选举簇头，选举过程中缺少对剩余能量和距离的考虑，使节点死亡过于集中，当网络面积较大时，较边缘的簇头数据传输消耗能量较多，因此能量耗尽的节点更多分布在远离基站的位置。在EEUC算法中，将稳定传输阶段的TDMA 优化为CSMA，但没有进行能量均衡化优化，因此死亡节点的位置也相对集中在基站附近。本文算法结合了基于概率模型的阈值公式和动态竞争半径，对簇头选举进行了优化，死亡节点在整个数据中是均匀分布的，解决了热区问题，使网络能耗更均匀。

3.3 网络生命周期

三种算法存活节点数的变化状态如图5 所示。本文提出的算法相对其他两种算法有更长的网络生命周期。本算法采用近基站范围设立较多簇头分担每个节点转发任务量，从而达到均衡能耗。所以本算法的第一个节点的死亡时间和网络失效时间均晚于其他两种算法。

3.4 算法稳定性

在网络拓扑结构固定后，判断分簇协议的稳定性指标是看每轮选举出的簇头数目偏差大小。本文分别从LEACH 算法、EEUC 算法和EOUCR算法运行过程中随机抽取100轮，抛洒节点增至到600 个，统计每个协议簇头的数目，如图6 所示。LEACH算法的簇头数目分布在55～104区间，分布零散且相差悬殊，这是由于LEACH算法采取随机生成数和阈值竞选簇头的方法导致。EEUC 算法中采用局部竞选机制，使簇头生成的簇头数目值相差较小，分布在15～23区间。而本文提出的算法簇头数目集中分布在42～50 之间，成簇稳定，因为本文采用均衡能量划分非均匀分簇，靠近基站的簇范围小，簇头个数相对较多，整体生成簇头数目差异小。

综上所述，本节对三种算法进行了对比分析，得出本文提出的算法生成的簇头数目更稳定，具有更高的可靠性。

4 结 论

本文算法以均衡能耗，延长WSNs的网络生命周期为目标，并针对现有分簇路由算法存在的缺点和不足进行改进，提出了一种基于动态竞争的能量均衡非均匀路由协议。本算法的核心是对簇头选举阈值T(n)进行重新定义，加入相对剩余能量，相对簇内节点密度和同簇节点汇聚度因子来约束候选簇头的形成，以解决现有分簇过程中簇头分布不合理和簇内结构松散等不合理现象。协议利用阈值与竞争半径共同协作的方式，合理化分簇均衡能耗，平衡网络负担；在簇间稳态路由转发阶段，通过能量代价函数，建立能耗代价最低的路由传输协议。

实验结果表明，本文算法具有较好的稳定性，能够充分均衡传输任务达到均衡网络能耗的效果，同时也显著延长了网络节点的生存周期。但实际环境中节点会有移动和结构不同现象，下一步工作是对其进行改进，使其更适用于实际场合。