第43卷第6期2020年12月V ol.43No.6Dec.2020
辽宁科技大学学报Journal of University of Science and Technology Liaoning 基于动态竞争的能量均衡非均匀路由协议 王宣懿，曾子维，王刚
（辽宁科技大学计算机与软件工程学院，辽宁鞍山114051）
摘要：针对无线传感器网络成簇规模不合理，负载不均造成的“热区”问题，提出基于动态竞争的能量均衡非 均匀分簇路由协议。该算法定义了理想通信半径和完美邻居节点，提出综合衡量动态剩余能量、节点汇聚度和
节点密度参数的基于概率模型的阈值公式，使局部区域内剩余能量多的候选簇头成为簇头，考虑位置和能量计 算竞争半径。构建多跳路由时，根据向前邻居节点与现节点和的距离，剩余能量和通信能耗确定路由代价
函数，选择函数代价最优的簇头担任中继节点。仿真结果表明，与其他算法相比，本算法有较好的自适应性和稳
定性，能有效均衡网络能耗并延长网络生命周期。
关键词：无线传感器网络；簇头选举；非均匀分簇；能量代价函数；路由协议
中图分类号：TP311文献标识码：A 文章编号：1674-1048（2020）06-0444-07
DOI ：10.13988/j.ustl.2020.06.008
磨料加工
广东省环保局无线传感器网络（Wireless sensor networks ，WSN ）由路由感知通信与计算能力的传感器节点组成，节点以自组织方式组成多到一的通信网络，再把采集到的数据以多跳的方式发送到sink 节点［1］。传感器节点主要靠电池提供能量，因此WSN 中能量消耗很受重视，降低能耗与提高网络寿命是路由协议研究的重点之一［2-3］。为了延长网络生存周期，已提出很多分簇和多跳路由算法。最著名的分簇算法为Heinzelmen 研究的LEACH （Low-energy adaptive clustering hi-erarchy ）［4］。每一轮分为初始化阶段和稳定工作阶段。但在LEACH 算法中簇间通信采用单跳，全部节点都可和汇聚点直接通信，距离较远的节点都会进行远距离通信［5］。因此，簇头能耗不均从而导致部分节点过早死亡。并且簇头选举的次数过于频繁，消耗了较多能量。在选举过程中也未考虑节点的剩余能量与位置分布。之后，PEGA-SIS ［6］、EECS ［7］、HEED ［8］等优化算法被陆续提出，簇间多跳也陆续被广泛应用。多跳导致靠近的簇头节点需承载较多的转发任务，能耗高从而过早死亡，出现“热区”现象。为解决这一问题，蒋畅江等［9］提出EEUC （Energy efficient uneven cluster ）算法，该算法采用簇间多跳模式节省网络能耗，候选簇头通过节点位置采用竞争半径不同的非均匀构造簇策略，形成大小不等的簇。但是，在边缘区域中转发数据量很少，该算法仅考虑距离不考虑剩余能量作为负载大小不够全面，并仅以到的距离和竞争半径作为确定下一跳簇头集合的这
种方式总能耗较大。针对此问题，文献［10］提出高效的非均匀分簇EUCA （Efficient uneven cluster ）算法。熊科等［11］提出一种采用双簇头均衡能量消耗的非均匀分簇算法。在采用非均匀分簇思想
时均需要基于竞争半径理论，但现有分簇路由协议中仍存在簇头选举不当和网络能耗不均等问题。因此，本文从提高簇头选举质量和提升簇间路由效率出发，针对现有计算阈值和竞争半径的方法，提出基于概率模型的分簇路由算法（Energy opti-mized uneven cluster routing ，EOUCR ）。EOUCR 算法在分簇前通过动态的设定阈值，得到优质候选簇头，再基于各节点的动态竞争半径选出真正簇头。根据路由代价函数计算出各邻居节点路由代价值，选择函数代价最优的簇头节点担任中继收稿日期：2020-09-07。
imperator fla
作者简介：王宣懿（1994—），女，辽宁鞍山人。
通讯作者：曾子维（1963—），男，辽宁鞍山人，
教授。
第6期节点，得到全局最优路径。期望在网络运行过程中能有效均衡节点能耗，延长网络寿命。1系统模型和定义1.1节点能耗模型节点能耗由感知、通信、数据处理三方面构成，其中通信能耗占最大比例。采用Heinzelman ［12］的简单能量模型，依据通信距离长短分为自由空间模型和多路径衰减模型。在实际应用中，传输能量基于一个阈值距离d 0，当通信距离小于d 0时，此时考虑为自由空间模型；否则将使用多路径衰减模型。节点发送l 比特数据到离自身距离为d 的节点所消耗的能量计算式E Tx (l ,d )=ìíîlE elec +lεfs d 2d <d
0lE elec +lεmp d 4d ≥d 0（1）
节点接收l 比特的数据需消耗的能量计算式为E Rx (l )=lE elec （2）式中：E elec 代表发送与收发单位能量消耗，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 轮时理想状态下通信半径平均值
R i
=
（3）式中：在一正方形M ×M 监测区域，随机部署N 个节点，且每个节点被选作簇头的概率为p ；N r 为第
r 轮时网络中存活节点的个数。
基于理想通信半径平均值范围内的存活节点集合。节点的完美邻居节点集合定义
N (i )={}j |j ∈V ,d (i ,j )≤R i
∪E j
res >0（4）式中：d (i ,j )为通讯半径内各节点i 与j 之间的距离，m ；E j
res 为节点j 的剩余能量，J ；V 代表全部节点集合。
2.1候选簇头的生成策略
LEACH 算法在簇头选举阶段，节点随机生成［0，1］之间的随机数，当随机数小于阈值T (n )时，
该节点被选做簇头。阈值计算式为
T (n )=ìíîïïp
1
-p [r mod(1/p )]if n ∈G 0otherwise （5）式中：p 为每一轮中期望的簇头数在网络节点总数的比值；r 为当前所在的选举轮数；G 为剩下的
1/p 轮中没有被选为簇头的全部节点集合。王宣懿，等：基于动态竞争的能量均衡非均匀路由协议··
445
辽宁科技大学学报第43卷通过对LEACH 算法的不足及其改进算法的研究，结合EEUC 提出的成簇思
想，在EOUCR 选取候选簇头时引入相对剩余能量因子、相对簇内节点密度因子和同簇节点汇聚度因子。（1）相对剩余能量因子：单独考虑剩余能量不能准确判定剩余多少，因此在阈值定义中加入相对剩余能量，其值会随着运行轮数变化波动，使阈值定义更为合理具有实时性。（2）相对簇内节点密度因子：理想通信半径内
的实际节点个数与监测范围内所有节点数的比。用来体现实际簇内成员数量值。比值越大说明实际邻居节点数量越大，被选为候选簇头的概率越大。（3）同簇节点汇聚度因子：节点i 的完美邻居节点集合内的所有节点到i 的距离的平均值与理想通信半径的比值。其值代表簇内节点汇聚紧密程度体现了簇结构，当比值越大说明汇聚程度差，簇内通信时延大。传感器节点预先根据阈值选出候选簇头节点，阈值T (n )计算式T (n )new =ìíîïïp ⋅Φ1-p [r mod(1/p )]if n ∈G 0otherwise Φ=χ1E r E avg +χ2N i
N num +χ3D i -avg
R i （6）式中：p 为存活节点成为簇头的期望；r 为当前循环轮数；G 为最近1/p 轮中未被选为簇头的节点集合；E r 表示当前节点的剩余能量，J ；E avg 为当前所
有存活节点的平均剩余能量，J ；N i 为节点通信半
径内的节点数；N num 为总的节点数；D i -avg 为节点i
的理想邻居节点集合内各节点到i 节点的平均距离，m ；R i 为理想平均半径；χ
1、χ
2、χ3代表三项因子的权重值并且χ1+χ2+χ3=1。新的阈值T (n )特点：（1）已成为过候选簇头的节点在往后的1/p 轮循环中均不能选为簇头。（2）随着轮循环增加未当选过候选簇头的节点选为簇头的概率逐渐升高。（3）未成为簇头的普通节点根据收到广播信号的强弱加入信号最强的簇。由于簇间多跳导致距离近的簇头承担的数据转发量大且能量消耗高，因而失效概率较大。为缓解这种现象，本文提出的算法使靠近区域选举的簇头数较多，成簇规模较小。即减
滴泪痣小说少簇内通信能耗用于簇间转发，从而达到簇间能耗平衡。远离则相反。算法为每一个候选簇头设定了竞争半径，可以监控簇头在网络中的位置分布，即竞争范围
R c R c =æèçöø÷1-αd max -d (s i ,BS )d max -d min +βE res -E rave E rave R （7）式中：R 是提前设定的最大竞争半径；d max 代表网络中节点到达BS 的最大距离，m ；d min 代表节点到达BS 的最小距离，m ；α、β为位于0~1之间的常
量用于控制竞争半径取值范围。
2.2簇头节点的确定
簇头节点的选择决定了网络能量均衡和数据收集效率。竞选簇头的算法内容为，每个候选簇头以R i c 范围和相对应的功率进行广播自身报文，
内容包含节点自身ID 、当前剩余能量E res 、竞争半径R i c 。同理也能获知其他邻居节点广播信息。参
与竞选的所有候选簇头节点都建立自己的邻候选
簇头集合S i
CH 并维护一张邻居节点信息集合表，内
容包含邻居节点的ID 、邻居节点剩余能量E res 、邻
居节点竞争半径R i
c 。候选簇头S i 的邻居节点集
合
S i CH ={}S j |S j 是候选簇头,d (S i ,S j )<R i c （8）
将剩余能量与簇头集合中节点剩余能量进行比较，决定能否担任真正簇头。当候选节点竞争
成功时，向邻居节点广播胜任消息，邻居候选簇头
节点接收消息后退出竞选。簇头竞争规则如图1所示。R 为相对应的竞争半径，Y
1和Y 3不在彼此
邻居范围内，Y
4位于Y 2的竞争范围内为其邻居节
点。因此Y 1、Y 3相互不影响，可同时成为簇头，而
Y
2成为簇头后Y 4便退出竞选。
确定簇头节点后，簇头向全网广播竞选成功
消息。普通节点解除睡眠状态，查看保存的通讯
范围内簇头信息表，当只保存一个簇头信息表时，直接加入其簇。当保存多个簇头信息表时，根据
接收信号强度大小，选择强度最大且通信代价最小的簇头节点并发送申请加入消息。距离相等则
··
446
第6期
加入通讯半径更大的簇。图1簇头的竞争规则
Fig.1Competition rules for cluster heads
分簇结构如图2所示，实现整个监测区域网络
的非均匀分簇，可以发现越是靠近的簇，成簇
面积越小。在此基础上簇头对节点收集到的信息
进行融合，以多跳的方式将数据发送给，进入
数据通讯阶段即路由传输阶段。
图2分簇结构Fig.2Cluster structure 2.3EOUCR 算法设计实现在分簇阶段，首先监测范围内的所有节点并通过函数rand （0，1）生成随机数R 。当随机数小于阈值T (n )时，其节点成为候选簇头，进行下一阶段的竞选。候选簇头节点通过式（7）计算出竞争半径R c 和簇头剩余能量，并以广播形式发送竞选簇头的消息Elect_msg 。当候选簇头接收到其它的竞选簇头消息时，比较两节点的距离，若小于两者中任意一个节点的竞争半径，将该节点存储到自己的邻居表内，对比邻居表中节点的剩余能量大小，如其值均小于自己，则当选真正的簇头，否则退出竞选。竞选成功的簇头在通信范围内广播竞
选成功信息Competehead_msg ，普通节点若同时收
到多个簇头消息，根据接收信号的强度大小，即选
择距自己近的簇头申请加入。若普通节点没有收
到任何簇头消息，则自己成簇头。直到监测区域
的所有节点都加入簇，成簇阶段就结束了。本算
法流程图如图3
所示。
图3算法流程图
Fig.3Flow chart of algorithm
2.4簇间基于能量代价多跳路由协议
当设置簇阶段过程结束后，WSN 进入稳态路由转发阶段，此阶段的主要目标是在簇间选择最优的路径进行数据传输，从而达到提升网络性能的目的。EOUCR 算法在传输距离较远时，簇头选出适合自己的其他簇头节点作为中继节点，通过中继节点将数据转发到。因此提前建立多跳传输路径，选择出可靠性高、能耗均衡的最优路径。详细步骤如下：
首先节点采集数据，并将采集数据以TDMA 的方式发送给自己的簇头节点。簇头把采集到的
王宣懿，等：基于动态竞争的能量均衡非均匀路由协议··
447
辽宁科技大学学报第43卷信息通过数据融技术进行融合然后转发到汇聚节点或。当簇头有发送或转发数据任务时，簇头查看邻居节点与的距离，选择比自身更接近的向前邻居簇头节点并计算路由代价函数，选择代价函数最优的节点进行数据转发。当节点成为下一跳时，数据会成功地发送到该节点，直至数据转发成功，形成可靠性高的最优路径。向前邻居节点的定义
smzbFN (i )={}j |j ∈N (i ),d (j ,BS )<d (i ,BS )（9）
路由代价函数
V (i ,j )=c 1E Tx (l ,d (i ,j ))E j res
+c 2d (j ,BS )+c 3d (i ,j )（10）
式中：E Tx
(l ,d (i ,j ))为i 和j 节点间发送比特数据所消耗的能量，J ；d (j ,BS )是节点j 与之间的距离，m ；c 1
~c 3为加权参数且满足c 1+c 2+c 3=1，经反
复实验将其值设为0.4，0.3，0.3。由式（10）可知，簇头节点有更大概率成为下一跳节点的条件为：
（1）簇头节点剩余能量高。（2）发送数据所需能量越少。（3）簇头与的距离更近。（4）簇头间的距离更短。
由于簇头承担了网络中大量数据的通信与转发，因此均衡各簇头间的能量消耗是路由重要考虑因素之一，本文提出基于簇头剩余能量以及发送数据消耗能量和簇头间距离等因素来确定路由代价函数，动态选择并调整下一跳簇头节点，相比于EEUC 等算法在均衡能耗方面更加出。3仿真实验与结果分析
3.1仿真方法及参数设置
本文在MATLAB 平台进行仿真实验，将400个无线传感器节点随机部署在一个200m×200m 的监测区域内，节点分布均匀且设立在坐标（200m ，250m ）处，能量充足不做考虑。能量参数如表1所示［12］。
营销网络的建设3.2能耗均衡性
在算法比较时，考虑到文献［13］定义网络死亡节点数超过20%以上时将影响网络正常工作。因此实验记录死亡节点占比超过20%时，网络节点分布情况图4所示。表1仿真场景及参数Tab.1Simulation scenarios and parameters 参数区域面积/m 2位置/m E elec /（nJ·bit -1）εfs /（pJ ·（bit·m -2）-
1）εmp /（pJ ·（bit·m -2）-1）数据包长度/bit 数值200×200（200，250）5060.00134000参数E 0/J
p d 0/m R α,βc 1,c 2,c 3数值
0.5
0.1
8760
0.5，0.5
0.4，0.3，
0.3
图4死亡节点分布图Fig.4Distribution map of dead nodes LEACH 协议采用随机选举簇头，选举过程中缺少对剩余能量和距离的考虑，使节点死亡过于··
448
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议