一种基于分环的能量高效无线传感器网络分簇路由协议*

吴玉成，李伟琪，胡 真，谢 璐

(重庆大学 通信工程学院，重庆400030)

0 引 言

节点能量受限是无线传感器网络(wireless sensor networks，WSNs)的重要特征，设计能量高效的WSNs 路由协议对延长网络生命周期尤为重要［1～3］。

基于分簇(clustering)的WSNs 路由协议是提高网络能量效率的有效途径［4～6］。现有分簇式路由协议主要包括:Heinzelman W 等人提出的低功耗自适应集簇分层(low energy adaptive clustering hierarchy，LEACH)协议［7］;为进一步提高成簇质量，Heinzelman W 等人又提出了集中式成簇算法LEACH－C 和考虑了几点剩余能量的算法LEACH－E。Lidsey S 等 人 提 出 的PEGASIS(power－efficient gathering in sensor information system)算法［8］以链状拓扑组织节点，该算法需要预知节点位置信息。Younis O 等人提出的HEED(hybrid energy efficient distributed clustering)协议［9］是针对LEACH 协议中簇首分布不均匀的问题提出的改进，但成簇机制需要多次消息迭代。上述三种算法没有考虑到簇间的能耗均衡，容易造成“热区”［10］。Soro S 等人最先提出了基于非均匀分簇的UCS(unequal clustering size)协议［11］来解决“热区”问题，该方法采用两层同心环状拓扑，外环中的簇规模比内环中簇规模大。但该方法中的簇首节点及其位置是预先选定的，也没有成簇机制。李成法、陈贵海等人提出了EEUC(energy－efficient uneven clustering)协议［12］，解决了多跳模式下簇首能耗不均衡引起的“热区”问题，但簇首选取时未考虑节点的剩余能量和位置，影响了最终簇首的质量和簇的分布。

针对上述算法的缺陷，本文从全网能耗均衡出发，提出了一种基于分环的能量高效WSNs 分簇路由(ring－based energy－efficient clustering routing，RECR)协议。采用同心环状网络模型，根据节点的剩余能量和与环中线的距离选举簇首，改善了簇在网络中的分布;采用主次簇首轮换机制，减少了每轮成簇所带来的能量开销。仿真结果表明:与LEACH 和HEED 协议相比，本文所提算法能够优化簇的规模与分布，缓解“热区”问题，有效均衡了全网能耗并延长网络生命周期。

1 网络与能耗模型

1.1 网络模型

本文采用等间隔同心环状网络模型，N 个传感器节点均匀且随机分布在以Sink 节点为圆心的原型监测区域内，网络一经部署不再移动，所有节点具有相同功能和唯一ID，节点不具备定位功能，在已知发送方发射功率的前提下根据接收信号强度指示(received signal strength indication，RSSI)计算发送方和自身之间距离。

1.2 能耗模型

本文采用与LEACH 相同的无线通信能量消耗模型。节点发送k bit 数据到距离为d 出所消耗的能量由发射电路损耗和功率放大损耗两部分构成，即

其中，Eelec为发射电路损耗的能量;当传输距离小于阈值d0时，功率放大损耗采用自由空间模型;当传输距离大于等于阈值d0时，采用多路径衰减模型。εfs，εmp分别为这两种模型中功率放大所需的能量。传感器接收k bit 数据所消耗的能量为

数据融合也消耗一定的能量，用EDA表示融合1 bit 数据消耗的能量。

2 RECR 协议

2.1 簇首选取

本文所提算法中，簇首的选取分为3 个步骤:

1)确定最优簇首个数

文献［13］推导了等间隔同心环形网络模型中各环的簇首个数对网络能耗的影响，根据文献［13］的分析，本文以均衡各环簇间能耗和最小化第一环节点能耗为目标，推导各环中最优的簇首个数。网络模型如图1 所示，半径为R 的圆形区域被等分为S 个间隔为h 的环。设第k 环内簇的数目为mk，第k 环节点总数为Nk。

图1 RECR 的网络模型Fig 1 Network model for RECR

第一环最优簇首个数为

再以均衡各环簇首平均能耗出发，需满足Echk=Ech1，即

根据式(3)和式(4)可得各环最优簇首个数。其中，N为 节 点 总 数，k = 1，2，…，S。E表示第k 环中的簇首到第k－1 环中的簇首距离平方的期望。

2)选取候选簇首

首先，网络中所有节点根据接收到的Sink 节点的信号强度判断自身处于环状模型中的第几环，然后进行候选簇首的竞选。各环中的节点竞选候选簇首的概率为

其中，pk(i)为第k 环中的节点i 称为候选簇首的概率;pk为第k 环中簇首节点占环内节点总数的百分比，即pk=mk/Nk;k 是当前的轮数;Eres(i)为节点i 当前剩余能量;Eave－k为第k 环内节点平均剩余能量;s(t)·dist 表示节点i到Sink 节点的物理距离;Lk表示第k 环的环中心线;β 为(0，1)间的随机数。网络中所有的节点参与候选簇首的竞选，若节点i 产生的随机数小于pk(i)，则竞选成功，并以环间距h 为半径广播竞选成功消息，该广播消息内容包括:节点ID，节点所在环号，节点当前剩余能量。

3)确定最终簇首若候选簇首s(i)剩余能量比其邻里(h/2 半径内)同属一环的其他候选簇首的能量都高，则s(i)当选为最终簇首，并以2h 为半径广播获胜消息，消息内容包括:节点的ID，剩余能量，与Sink 节点的物理距离，所在环数。非簇首节点根据该消息选择最近的簇加入。

2.2 主次簇首轮换

各环在每1/pk轮在全环进行簇首的重新选取，其余轮次采用主次簇首轮换机制。主次簇首轮换的过程为:每一轮簇内数据传输阶段，非簇首节点将感知到的数据信息以数据包的形式发送给本簇簇首，并在数据包包头插入自身信息，包括ID 号，剩余能量。本簇簇首(主簇首)根据各个包头信息选择下一轮簇首(次簇首)，并单播发送消息告知被当选的次簇首节点。次簇首的选取原则如下

其中，dtoCH(i)为非簇首节点到其所属簇首节点的距离。主簇首选取T(i)值最大的非簇首节点为次簇首。

3 仿真与性能分析

3.1 仿真环境

本文以LEACH 和HEED 协议作为对比，在Matlab 中验证分析RECR 协议的性能。仿真环境如下:监测区域为半径R=240 m 的圆形区域，分为环距h=80 m 的3 个环形区域，随机部署1 000 个传感器节点。根据2.1 中的最优簇首个数公式计算出第一环簇首数为10，第二环为17，第三环为21。簇首选举算法中的参数β 无闭合表达式，本文通过大量仿真实验确定其最优值为0.8。节点初始能量设置为1 J，数据报长度为4 000 bit，Eelec=50 J/bit，εfs=10 pJ/(bit·m2)，εmp=0.001 3 pJ/(bit·m2)，EDA=5 nJ/bit，d0=87 m。

3.2 仿真结果与分析

1)网络生命周期

图2 比较了RECR，LEACH，HEED 网络中存活的节点数随轮次的变化。如图所示，RECR 第一个节点死亡的时间和最后一个节点死亡的时间都晚于其他两种协议，并且RECR 第一个节点死亡与全网节点死亡的时间跨度更小。这是因为RECR 算法选择剩余能量高且离环中心线较近的节点为簇首，避免了LEACH 协议中低能量节点当选簇首而过早死亡和HEED 协议在簇首选举过程中反复迭代造成的能量开销。图3 分别对RECR，LEACH，HEED 三种协议的第一个节点死亡时间(FND)、节点死亡50%的时间(HND)、节点全部死亡的时间(LND)进行比较。显然，RECR 的性能较优。

图2 存活节点数目随轮次的变化Fig 2 Variation of survival node number with round

图3 节点死亡时间比较Fig 3 Comparison of node death time

2)全网剩余能量

图4 比较了RECR，LEACH，HEED 全网剩余能量随时间变化的情况。由于RECR 协议采用了主次簇首轮换机制，从而节约了大量能量。由图可见，RECR 协议的全网剩余能量随轮次的增加而近似呈线性下降，性能显著优于其他两种算法。

图4 全网剩余能量比较Fig 4 Comparison of global network residual energy

3)簇首消耗的能量

图5 比较了RECR，LEACH，HEED 簇首消耗的总能量随时间变化的情况。LEACH，HEED 每轮产生的簇首数目大于RECR，并且每轮均进行簇首重选，导致了簇首能量消耗较大。RECR 协议的簇首个数少且数目稳定，不需每轮重选簇首而产生额外的能量开销，因而，簇首消耗能量之和波动小。

图5 簇首消耗能量之和比较Fig 5 Comparison of cluster head energy consumption summation

4)簇首能耗方差

算法是否较好地均衡了簇首的能耗，可以通过簇首能耗的方差反映出来。图6 比较了RECR，LEACH、HEED 簇首方差随时间变化的情况。从图6 明显看出:RECR 簇首的方差最低且波动较小，较稳定，因此相比较LEACH，HEED 最好地均衡了簇首的能耗。LEACH 因为是随机产生簇，簇首分布不均匀，导致簇首能量消耗不均匀。HEED中未被覆盖的节点独立成簇，导致某些簇可能只含有一个节点即簇首本身，因此，导致全网簇首负载不均衡，能量消耗差别较大。

图6 簇首消耗的能量方差比较Fig 6 Comparison of cluster head energy consumption variation

4 结 论

本文在分析了几种典型随机分簇型路由协议的基础上，提出了一种RECR 算法。该算法将监测区域分成等间隔的多个环形区域，在各环中根据各环最优簇首数目、节点剩余能量、节点距离环中心线的距离进行簇首的选择，使得网络成簇均匀合理。同时，引入了主次簇首轮换机制，降低簇首重选频率以节省能耗，有效地延长了网络生命周期。

［1］ Liang Yuzhu，Zhang Aili，Li Yongzhen.An energy effective routing protocol efficiency constructs cluster topology for WSNs［C］∥Proceedings of the 2013 Third International Conference on Instrumentation，Measurement，Computer，Communication and Control(IMCCC)，Shenyang:IEEE，2013:1097－1100.

［2］ Pantazis N A，Nikolidakis S A，Vergados D D.Energy－efficient routing protocols in wireless sensor networks:A survey［J］.Communications Surveys＆Tutorials，2013，15(2):551－591.

［3］ Yi Xiushuang，Jiang Peijun，Wang Xingwei，et al.Survey of energy－saving protocols in wireless sensor networks［C］∥Proceedings of the 2011 First International Conference on Robot，Vision and Signal Processing(RVSP)，Kaohsiung:IEEE，2011:208－211.

［4］ Soua R，Minet P.A survey on energy efficient techniques in wireless sensor networks［C］∥Proceedings of 2011 4th Joint IFIP Wireless and Mobile Networking Conference(WMNC)，Toulouse:IEEE，2011:1－9.

［5］ Doddapaneni K，Omondi F A，Ever E，et al.Deployment challenges and developments in wireless sensor networks clustering［C］∥Proceedings of 2014 28th International Conference on Advanced Information Networking and Applications Workshops(WAINA)，Victoria，BC，IEEE，2014:227－232.

［6］ Liu Mengyao，Zhang Yangyan，Li Xia.Ring－based security energy－efficient routing protocol for WSNs［C］∥Proceedings of The 26th Chinese Control and Decision Conference，2014 CCDC，Changsha:IEEE，2014:1892－1897.

［7］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless micro sensor networks［C］∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，Maui，HI，2000:1－10.

［8］ Lidsey S，Raghavendra C S.PEGASIS:Power－efficient gathering in sensor information systems［C］∥Proeeedings of the IEEE Aerospace Conference，Montana，USA，2002:1125－1130.

［9］ Younis O，Fahmy S.HEED:A hybrid，energy－efficient，distributed clustering approach for Ad－Hoc sensor networks［J］.IEEE Transaction on Mobile Computing，2004，3(4):660－669.

［10］Baker D J，Ephremides A.The architectural organization of a mobile radio network via a distributed algorithm［J］.IEEE Trans Commun，1981，29(11):1694－1701.

［11］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥Proceedings of 19th IEEE International Conference on Parallel and Distributed Processing，2005:1－8.

［12］李成法，陈贵海，叶 懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30(1):27－36.

［13］刘 志，裘正定.基于分环多跳的无线传感网分簇路由算法［J］.通信学报，2008，29(3):104－113.