能量均衡的无线传感器网络多跳非均匀分簇算法

马威风，陈桂芬

(长春理工大学 电子信息工程学院，吉林 长春 130022)

0　引言

无线传感器网络(Wireless Sensor Networks, WSNs)是由部署在监测区域内大量廉价的微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统[1]。随着传感器、嵌入式计算、通信和计算机网络等技术的日趋成熟，无线自组织网络的各种应用逐渐成为可能，成为21世纪信息产业的重要支柱[2]。WSNs节点作为微小器件只能配备有限电源，而且多数部署在危险地带或人难以到达的环境中，后期维护难以实现，使节点寿命很大程度上依赖电池寿命，因此，如何减少节点的能量消耗对于传感器网络而言至关重要[3]，同时也是设计协议时面临的重要问题之一。

WSNs中节点布设密度大，节点感知到的数据存在大量的冗余信息[4]，而通信耗能为总能耗的主要部分。因此，必须严格控制数据包传输量来减少不必要的开销。以LEACH[5]为典型代表的分簇算法将节点分为簇头和簇内节点，簇内节点负责采集数据，而簇头负责管理簇内节点，并进行簇内节点信息的采集、融合及转发[6]。LEACH算法在一定程度上实现了能耗均衡，但存在簇头分布位置的随机性、选取簇头未考虑节点剩余能量以及与基站直接进行数据传输导致能耗过大的问题[7]。

EEUC[8]算法采用非均匀分簇和簇间多跳的方式。网络被划分为大小不等的簇，远离基站的簇内节点较多，避免过快消耗能量，而且簇间多跳路由方式可以进一步均衡簇头能量消耗[9]，较好地解决了“热区”问题[10]。

DEEUC[11]算法在EEUC基础上优化了簇头选举和路由选择，算法中候选簇头由上一轮簇头根据簇内剩余能量选出，再通过能量因素选出最终簇头。下一跳路由簇头选择正向单位能量消耗最小的邻簇首，有效地提高簇头间传输数据的效率。

本文基于非均匀分簇算法提出一种能量均衡多跳非均匀分簇算法(Energy Balance Multi-hops Uneven Clustering, EBMUC)，算法首先比较节点剩余能量与邻节点平均剩余能量选出候选簇头，再考虑距离、能量和邻节点数因素选出最终簇头；簇构造在节点入簇公式[12]中加入簇头剩余能量；簇间选择中继节点协助传输数据，数据通过中继节点和邻簇头多跳传输到基站(BS)，进一步延长网络生存时间。

1　相关理论

1.1　网络模型

正方形监测区域内随机分布N个周期性收集数据的WSNs节点，假设：(1)BS位于监测区域边缘，BS和节点部署后位置不再变动；(2)节点具有全网络唯一的标识ID号，节点同构且具备一定的存储能力，可以由信号强度估算距离；(3)BS能够与全网络的节点通信，通信方式为半双工；(4)无线信道对称，数据传输过程中融合数据减少数据量，融合单位数据耗能相同；(5)忽略外界影响，节点周期性采集数据并始终有数据传输到BS。

1.2　能量模型

本文采用文献[13]中的无线通信能耗模型，kbit的数据包发送到距离d的一个节点，能耗主要由无线信号收发和功率放大产生，功放器件的耗能与环境和距离密切相关，可分为自由空间模型和多径衰落模型。发送模块能耗计算如式(1)所示：

(1)

ERx(k)=kEelec

(2)

1.3　最优簇数目和最优簇通信半径

采用文献[13]中的方法计算最优簇数目(mopt)，假定在一个M×M的区域内均匀部署N个节点，产生m个簇，m个簇的总能耗如式(3)所示：

(3)

对式(3)中m求导并令式等于0, 求出mopt，由mopt计算均匀分簇情况下最优簇通信半径ropt、最优跳数τopt，如式(4)所示，式中为向上取整。

(4)

2　EBMUC协议算法设计

(1)簇头选择：BS首先广播初始化消息(包括mopt、ropt和d0)。节点收到消息后由信号强度估算到BS的距离dtoBS(i)，然后节点以ropt为半径向周围邻节点广播消息(包括节点剩余能量和到BS距离)，节点收到邻节点消息后建立邻节点信息表并统计邻节点个数，计算其邻节点平均剩余能量。若节点剩余能量大于邻节点平均剩余能量，则当选候选簇头并广播消息，反之节点进入休眠。候选簇头收到邻候选簇头的消息后建立邻候选簇头信息表，然后计算并广播适应值(如式(5)所示)，通过交换适应值选择值最大的候选簇头为最终簇头并广播当选消息，休眠中的节点收到最终簇头的消息后唤醒。

f(i)=w1N+w2E+w3D

(5)

(2)簇结构形成：①簇内结构。节点收到最终簇头当选消息后建立簇头信息表并估算到各簇头距离，对每个簇头的饱和度进行判断(即表达式P2)，由式(6)选择值大于0的簇头发送加入消息(包括剩余能量和基站距离)。

Add(i, CHj)=αP1+(1-α)P2

(6)

簇头记录节点发送的加入消息(若收到竞选簇头失败的候选簇头的消息则将其标记为副簇头)，根据成员节点数分配发送数据帧间隔。成员数较少的簇对应帧时间间隔较大，反之，帧时间间隔较小，以此来保证单位时间内不同簇内数目不同的节点传输的数据次数相同。最后，簇头采用TDMA方式向簇内成员广播工作时隙。

②簇间结构。簇头收到周围其他最终簇头当选消息后建立邻簇头信息表，计算并广播簇间数据转发代价值(如式(7)所示)，通过比较代价值来决定下一跳簇头。

(7)

下一跳簇头确定后，若簇头间距离大于d0，则在传输数据的簇内选择靠近下一跳簇头的中继节点辅助传输数据，反之则簇头间传输数据。中继节点由节点剩余能量与到两簇头间的距离两因素确定(如式(8)所示)，其中Erel、drel to CHj分别为中继节点剩余能量和到下一跳簇头距离。

(8)

(3)数据传输：簇成员节点在分配的时隙段向距离自己最近的副簇头传输数据(若无副簇头，则通过邻节点，若无邻节点则增大功率与簇头之间通信，将数据多跳传输至簇头)，副簇头收集并融合数据后向簇头转发，每次多跳传输过程中都有数据融合，数据传输后簇成员节点进入休眠状态；对于簇间数据传输则根据簇头间的距离情况选择中继节点辅助数据传输。同样，到BS距离小于d0的节点以单跳形式向BS传输数据，大于则多跳传输到BS。此外，靠近BS的簇头或普通节点并不是有数据就立即向BS传输，而是等待数据量汇聚到一定程度后再向BS传输，这样阶段地一次性向BS传送数据，大大减少了数据包的发送次数，从而使得距离BS较远的节点可以向基站附近汇聚更多信息量的数据。网络整体示意图如图1所示。

图1　EBMUC协议节点示意图

3　仿真实验与分析

3.1　仿真实验

在1 000 m×1 000 m区域中仿真比较了LEACH、EEUC、DEEUC和EBMUC，节点数为1 000个，初始能量为0.5 J，BS坐标为(1 000,500)。成簇权值α=0.6，w1、w2与w3分别取0.3、0.4和0.3，距离常数d0为87 m。其他参数见表1。

表1　仿真相关参数

3.2　仿真实验结果分析

通过仿真网络的生存时间、BS接收数据量和网络剩余能量来研究本文算法的性能。

3.2.1网络生存时间

网络生存时间是衡量网络性能的重要指标之一[14]，表2统计了图2中四种算法的第一个死亡节点(FND)和死亡一半节点(HND)的轮数,若是以HND作为网络生存时间评判标准，四种算法网络生存时间分别为215、273、297和362，与LEACH比较，EEUC采用了非均匀分簇的方式，很好地解决了“热区”问题，延迟了FND的出现；DEEUC在EEUC的基础上优化了簇头选取以及最小正向单位路由选择，能耗比EEUC算法得到进一步降低；而本文的EBMUC算法在由候选簇头选取簇头时，考虑了能量、距离以及邻节点数等因素，比DEEUC由候选簇头通过能量因素竞争选取出的簇头更为合理，出现FND轮数也更迟。EEUC、DEEUC以及本文算法会在某个时间段出现节点迅速死亡，产生这种现象的原因是由于这三种算法覆盖面积远大于LEACH，网络中节点能量得到均衡消耗，会在某一刻存活的节点少于LEACH中的节点数。EBMUC由于中继节点的加入，数据多跳传输到BS，更好地均衡了簇间能量消耗，所以后期节点死亡速度略快于DEEUC。

图2　存活节点数对比图

算法名称FND轮数HND轮数LEACH34215EEUC201273DEEUC236297EBMUC298362

3.2.2基站BS接收数据量

图3为四种算法BS接收数据量对比图，在FND之前，EBMUC中基站收到的数据包总量约是LEACH算法的1.5倍，约是EEUC与DEEUC的1.3、1.1倍。这是因为EBMUC改进的簇头选择与簇间通信方式，延长了网络的生命周期，使数据量有所增加，在EBMUC的HND之前，LEACH、EEUC和DEEUC中的大部分节点已经死亡，网络存在覆盖率低的区域，节点难以将数据传输到BS。

图3　基站BS接收数据量对比图

3.2.3网络剩余能量

图4比较了四种算法的网络剩余能量随运行轮数的变化情况。EEUC、DEEUC和EBMUC的多跳非均匀策略比单跳均匀的LEACH有明显的节能优势。EBMUC网络剩余能量在700轮之前大于其他三种算法，体现了本文算法的能量利用高效性。之后，由于EBMUC覆盖面积较大，消耗了一定的网络剩余能量，因此小于LEACH算法，同样地，EEUC和DEEUC也出现了这种情况。EEUC、DEEUC和EBMUC相比，DEEUC中簇头指定能量最高的节点为下轮的簇头，均衡了节点间能耗同时也避免多个节点成为候选簇头参与最终簇头竞争，节省了网络能量。而EBMUC是先选择候选簇头，再由候选簇头综合考虑能量、距离以及邻节点数来竞争最终簇头，得到的簇头更为合理，同时在节点入簇时考虑了簇头能量与簇规模，有效地减轻了簇头负担，降低了网络能耗。

图4　网络剩余能量对比图

4　结论

本文在研究现有的非均匀分簇算法基础上，设计了一种能量均衡的多跳非均匀分簇算法，算法考虑了节点的距离、能量以及邻居数等因素来选取最终的簇头节点。节点入簇阶段考虑了簇头的能量与距离，同时也考虑了簇头的邻节点数，避免形成的簇结构规模过大。为了防止簇头间出现远距离传输数据的情况，采取选择待传输数据簇内最远处的节点作为中继节点来辅助数据传输，缩短数据传输路径，最小化簇间数据通信开销。与LEACH、EEUC和DEEUC算法相比，本文算法平衡了节点能耗，延缓了网络中死亡节点的出现轮数，从而延长了网络生存时间。

[1] 苏兵,张钰婧.基于非均匀分簇的无线传感器网络路由协议[J].计算机测量与控制,2016, 24(2):325-327.

[2] 刘半藤,周莹,陈友荣,等.基于移动-能量代价函数的无线自组织网络路由策略研究[J].传感技术学报, 2017,30(2):302-305.

[3] 林德钰,王泉,刘伎昭.无线传感网的移动与静态sink相结合的节能策略[J].哈尔滨工业大学学报, 2016,48(11):162-168.

[4] 张策,张霞,李鸥,等.基于CS的无线传感器网络动态分簇数据收集算法[J].计算机研究与发展,2016, 53(9):2000-2008.

[5] ZHANG X L, LI Q, FU Y, et al. An energy balancing LEACH algorithm for wireless sensor network[C]. International Conference on Electrical, Computer Engineering and Electronics, 2015:752-756.

[6] 张军强,王汝传,黄海平.基于分簇的无线多媒体传感器网络数据聚合方案研究[J].电子与信息学报, 2014,36(1):8-14.

[7] SALMABADI H, ADIBNIA F, SARRAM M A. An improvement on LEACH protocol (EZ-LEACH)[C]. International Conference on Knowledge-Based Engineering and Innovation(KBEI)，2015:956-970.

[8] LI C F, YE M, CHEN G H, et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]. IEEE International Conference on Mobile Ad-hoc and Sensor Systems Conference， IEEE, 2005:597-604.

[9] 刘洲洲,王福豹,张克旺.基于混合蛙跳算法的非均匀分簇WSNs路由协议[J].计算机应用研究,2013,30(7):2173-2176.

[10] 岳丽颖, 戴月明, 吴定会. 一种能量优化WSNs非均匀分簇路由协议[J]. 计算机工程与应用, 2015(15)： 80-85.

[11] 曾华圣, 熊庆宇, 杜敏,等. 一种分布式能量高效的WSNs非均匀分簇路由协议[J]. 传感器与微系统, 2014, 33(3):146-149.

[12] 江禹生, 李萍, 马超. 一种能量高效的无线传感器网络拓扑控制算法[J]. 传感器与微系统, 2014, 33(2):146-149.

[13] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[14] 刘半藤, 周莹, 陈友荣,等. 基于加权路由思想的无线自组织网络生存时间优化算法研究[J]. 传感技术学报, 2017,30(3):463-466.