能量感知非均匀成簇路由优化算法

侯 华，宋 彬，周武旸

(1.河北工程大学 移动通信研究室，河北 邯郸 056038；2.中国科学技术大学 无线信息网络实验室，安徽 合肥 230027)

能量感知非均匀成簇路由优化算法

侯 华1，宋 彬1，周武旸2

(1.河北工程大学 移动通信研究室，河北 邯郸 056038；2.中国科学技术大学 无线信息网络实验室，安徽 合肥 230027)

无线传感器网络(WSN)具有的能量有限，其能量利用效率的高低直接影响着网络的生命周期。为了提高无线传感器网络的能量利用效率，提出了一种能量感知非均匀成簇路由优化算法(Energy Awareness Unequal Clustering Routing Optimization Algorithm，EUCR)。该算法通过节点在网络中所处的位置确定各节点的邻居节点，并以局部能量选举簇头，各簇头根据其邻居节点构建非均匀分簇网络。同时该算法在路由阶段考虑了簇头的剩余能量和转发代价。仿真结果表明，EUCR算法能有效提高网络的能量利用效率，并延长网络的生命周期。

无线传感器网络；能量感知；非均匀分簇；多跳路由

无线传感器网络(Wireless Sensor Network，WSN)因其快速方便的部署特性和完备的监控能力被广泛应用于军事、救灾、环境、医疗、智能家居等领域[1]。但由于传感器节点采用电池供电的模式，且节点一旦部署之后，其电池不可更换，因此如何延长网络的生命周期是WSN面临的主要问题之一[2-3]。

以LEACH[4]和空间信息与梯度协议[5]为代表的分簇算法均衡了节点的能量消耗，但由于该类协议采用的都是单跳路由模型，因此在大规模网络中所提算法涉及到的距离基站比较远的节点能量消耗比较快，很容易使这类节点过早死亡。文献[6-7]采用多跳的路由协议，克服了上述单跳路由模型中部分节点过早死亡的不足。但多跳路由模型容易出现能量空洞现象。

为了解决能量空洞问题，本文提出了能量感知非均匀成簇路由优化算法(EUCR)算法。该算法采用先寻找邻居节点，再成簇的思想，提高了成簇效率。同时，EUCR算法通过局部能量选举簇头，使能量大的节点尽可能地当选为簇头，提高了网络的能量利用效率。在数据传输阶段，EUCR算法将节点的剩余能量和转发代价[7]的比值作为寻找路由的依据，使得选出的簇头更适合担当数据转发任务。通过仿真验证，该算法能有效地均衡网络中各节点之间的能量消耗，延长网络的生命周期。

1 系统模型

1.1 网络模型

为了便于研究，本文作出如下假设：N个节点随机地分布在一个正方形区域，网络中的第i个传感器节点用si表示，其中i={1,2,…,N}，基站位于正方形区域外的一侧。节点一旦部署之后不可再移动，且每个节点在部署时都会被分配一个唯一的ID标识符。

1.2 能量消耗模型

本文采用与文献[6]相同的能量消耗模型。传感器节点将lbit的数据发送到与其距离为d的目的节点时需要消耗的能量为

(1)

节点接收lbit数据包需要消耗的能量为

ERX(l)=lEelec

(2)

式中：Eelec代表收发电路的损耗能量，εfs和εmp为放大器系数，d0表示临界距离。当数据传输距离小于临界距离d0时，采用自由空间模型，此时的能量消耗和距离的2次方成正比；当数据传输距离大于临界距离d0时，采用多径衰落模型，此时的能量消耗和距离的4次方成正比。d0的取值为

(3)

2 算法设计

2.1 簇头选举

在LEACH协议中，网络中的每个节点产生一个随机数，若随机数大于簇头选举的阈值T(si)，则该节点就当选为簇头。每个节点参加簇头选举的阈值为

(4)

由式(4)可以看出，在LEACH协议中，每个节点参加簇头选举的概率都为P。而在无线传感器网络中，随着网络的长时间运行，网络中各节点的能量都会出现很大的差异，这时能量小的节点可能会被当选为簇头，而簇头的能量消耗要比簇内节点大很多，这会致使网络中的节点能量更加不均衡。本文利用节点的当前能量和局部最大能量的比值作为簇头选举概率P的调节参数，增大了高能量节点当选为簇头的概率。局部最大能量可由式(6)确定，在确定局部最大能量时，需要先寻找节点的邻居节点，邻居节点的确定在后文会有介绍。改进后的簇头选举概率Psi,CH如

(5)

(6)

式中：Psi,CH为网络中的任意节点si参加簇头选举的概率；Esi为节点si的当前能量；ELocalMax为节点si的邻居节点中的最大能量；NEIGHBORSsi为节点si的邻居节点集。

改进后簇头的选举阈值可表示为

广告商定义了产品的调性，消费者趋之若鹜，走进一些人满为患的性冷淡风店铺，尝试一些没多惊艳的网红食品。锦鲤的奖品就是欲望的合集，获得它，你就是拥有品位和运气的女孩。

(7)

2.2 非均匀分簇算法

为了构建非均匀分簇网络，本文提出了一个与节点在网络中位置相关的节点成簇通信半径Rsi·comp，即

(8)

式中：dmax为网络中节点距基站的最远距离；dmin为网络中节点距基站的最近距离；dsi,BS为网络中任意节点si距基站的距离。

在网络启用时的第一次成簇阶段，网络中的任意节点si在半径为Rsi·comp的通信范围内寻找自己的邻居节点。首先，节点si随机地退避一段时间，退避时间结束后，节点si发送广播消息Node_Find_Neighbor_MSG寻找自己的邻居节点，收到Node_Find_Neighbor_MSG消息的节点sj根据信号强度求得其与节点si的距离dsi,sj。为了保持网络的连通性，本文规定只有当dsi,sj≤Rsi·comp且dsi,sj≤Rsj·comp时，节点sj才为节点si的邻居节点，反之则不是。若节点sj为节点si的邻居节点，则节点sj向节点si返回一个包含自己能量信息的确认消息Node_Neighbor_ACK_MSG。节点si收到确认消息Node_Neighbor_ACK_MSG后，会将节点sj记录到自己的邻居节点集NEIGHBORSsi中。邻居节点集确定后，各节点按式(7)参加簇头选举。节点当选为簇头后，该节点与其邻居节点集就组成一个簇。对于同时属于多个簇头的邻居节点，依据式(9)判断其应加入哪个簇。

sj∈CCHsi:dsj,CHsi≤dsj,CHsk

(9)

式中：CHsi和CHsk为簇头，sj为簇头CHsi和CHsk的邻居节点，CCHsi代表簇头为CHsi的簇。

在网络经历了第一次成簇之后，网络中的各个节点都保存了一个自己的邻居节点集，由于每个节点的通信半径是固定的，所以在网络启用时的第一次成簇阶段，节点所确定的邻居节点集即为该节点的最大邻居节点集，当网络中有节点死亡时，相应的节点就会从自己的邻居节点集中删除死亡节点。在本文中，每个节点和其邻居节点集被称为一个伪簇，在网络第一次成簇之后的生存周期中，只要确定了簇头，簇头节点所确定的伪簇就自动升级为簇。这种先确定邻居节点再分簇的方法相对于传统的先确定簇头再分簇的方法，减少了成簇阶段所耗费的时间，同时也简化了成簇的复杂度，提高了成簇的效率。

2.3 路由

本文在选择下一跳路由时，对簇头的通信范围和簇头到基站的距离等参数做了限制，同时从能量利用效率的角度考虑了下一跳路由的转发代价。

(10)

3 算法评价

本文通过与LEACH和NEW-LEACH算法的仿真对比来评估EUCR算法的有效性和可行性。本文所有的仿真实验在MATLAB环境下进行。在仿真实验中，网络为200 m×200 m正方形区域，基站位于(100，250)m处，节点总数为400个，节点的初始能量为0.5 J，Eelec为50 nJ/bit，εfs为10 pJ/(bit·m2)，εamp为0.001 3 pJ/(bit·m4)，数据包大小为4 000 bit，控制包大小为200 bit。

图1为3种算法网络生命周期的对比。其中LEACH，NEW-LEACH和EUCR算法中第1个节点的死亡时间分别为220，700和921，可见EUCR的网络生命周期比NEW-LEACH的提高了32%，比LEACH的提高了319%。原因在于，在LEACH中，簇头采用单跳的方式与基站进行数据交换，使距离基站较远的簇头能量消耗较大，导致其过早死亡。而NEW-LEACH和EUCR都采用多跳的通信方式与基站进行数据交换，延长了网络的生命周期。由于EUCR算法采用的簇头选举策略和路由协议，比NEW-LEACH算法的更加合理，所以EUCR的网络生命周期比NEW-LEACH要长。

图1 网络生存周期

本文以网络中第1个节点的死亡时间和最后1个节点的死亡时间的比值作为网络生存周期的能量平衡率。算法的能量平衡率越高，网络的能量利用效率就越好。由图2可知LEACH，NEW-LEACH和EUCR算法的能量平衡率分别为36%，52%，60%。其中LEACH的能量平衡率最低，EUCR的能量平衡率较NEW-LEACH有所提高。说明EUCR的能量利用效率最高，NEW-LEACH次之，LEACH的最差。

图2 能量平衡率

本文对随机选取的20轮簇头能量消耗进行了对比，如图3所示。其中，LEACH算法中的簇头能量消耗波动较大，NEW-LEACH和EUCR两种算法中的簇头能量消耗波动较小。这说明NEW-LEACH和EUCR能更好地平衡簇头之间的能耗。由图3还可以看出，EUCR中簇头的能耗最低，说明EUCR的簇头能量利用效率最高。

图3 簇头的能耗

4 结论

本文提出的能量感知非均匀成簇路由优化算法由于只需在第一次启用网络时寻找一次邻居节点，所以与其他传统的算法相比提高了网络的成簇效率。簇头选举策略和路由的改进，提高了网络的能量利用效率。但本文提出的算法只考虑了网络的局部能量消耗，使得选出的簇头和路由不是最优的。下一步的工作，将考虑全局能量消耗对网络的影响。

[1] KUILA P，GUPTA S K，JANA P K. A novel evolutionary approach for load balanced clustering problem for wireless sensor networks[J].Swarm and Evolutionary Computation，2013(12)：48-56.[2] YAN R，SUN Hanghang，QIAN Yuning.Energy-aware sensor node design with its application in wireless sensor networks[J]. IEEE Trans. Instrumentation and Measurement，2013，62(5)：118-1191.

[3] SUN Hanghang，QIAN Yuning，YAN Ruqiang.Design and realization of an intelligent sensor node with its application in energy-aware WSNs[C]//Proc. IEEE International Conference on Instrumentation and Measurement Technology. [S.l.]：IEEE Press，2012：941- 946.

[4] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[EB/OL].[2014-12-12].IEEE Trans. Wireless Communications，2002，1(4)：660 - 670.

[5] 廖惜春，杨志高，任敬哲. 基于空间信息与梯度的WSN分簇路由算法[J].电视技术，2014，38(5)：120-123.

[6] LI Chengfa，YE Mao，CHEN Guihai，et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]//Proc. IEEE International Conference on Mobile Adhoc and Sensor Systems.[S.l.]：IEEE Press，2005：8- 604.

[7] 胡峰松，肖球.一种基于LEACH的能耗均衡多跳路由算法[J].小型微型计算机系统，2014(1)：70-73.

宋 彬(1987— )，研究生，研究方向为无线传感器网络；

周武旸(1972— )，博士，教授，博士生生导师， 研究方向为多载波技术跨层协议处理。

责任编辑：许 盈

Energy Awareness Unequal Clustering Routing Optimization Algorithm

HOU Hua1, SONG Bin1,ZHOU Wuyang2

(1.HebeiUniversityofEngineering,MobileCommunicationsResearchLaboratory,HebeiHandan056038,China;2.USTC,WirelessInformationNetworkLab,Hefei230027,China)

Wireless sensor networks (WSN) have limited energy, so its energy efficiency directly affects the life cycle of the network. In this paper, a new kind of energy awareness unequal clustering routing optimization algorithm (EUCR) is put forward. EUCR algorithm selects cluster head by local energy, and it expressly makes an optimization in clustering method and route. The simulation results show that EUCR can effectively improve the network energy efficiency, and prolong the life cycle of the network.

WSN; energy awareness; unequal clustering; multi-hop routing

【本文献信息】侯华，宋彬，周武旸.能量感知非均匀成簇路由优化算法[J].电视技术,2015，39(13).

河北省高等学校科学技术研究重点项目(ZH2011222)

TP393

A

10.16280/j.videoe.2015.13.016

侯 华(1980— )，女，博士，副教授，研究生导师，研究方向为移动通信、无线通信和认知无线电技术；

2015-01-13