基于多重竞争的无线传感器网络簇头选择算法*

贾银亮，张驰宇，梁康武

(南京航空航天大学 自动化学院，江苏 南京 210016)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)是由部署在监测区域内的大量传感器节点，通过无线通信方式形成的一个多跳自组织网络[1]。其依赖于传感器、无线通信、嵌入式系统等技术，具有低功耗、低成本、分布式和自组织等特点。随着节点体积的缩小、能耗的降低和性能的提升，无线传感器网络已开始投入实用。

在无线传感器网络的研究中，能效一直是热点问题。为了延长网络生存周期，相关的软硬件得到了大量的研究。分簇算法可以有效延长网络生存周期，而分簇算法中，簇头的选择对网络能耗有较大影响[2]。本文对分簇算法的簇头选择进行研究，提出了一种新的算法。

1 相关工作

LEACH算法[2,3]使用轮的概念，一轮由所有节点分簇的建立阶段，和数据采集、传递、处理的稳定阶段组成。在建立阶段，各个节点产生0～1之间的随机数。对节点i而言，若该数小于阈值T(i)，则该节点成为簇头

(1)

式中p为簇头对存活节点的占比；r为当前循环的轮次；G为在最近 1/p轮中未成为簇头的节点集合[4]。LEACH算法随机性较强，实际工作中,由于簇头的能耗各不相同，仍会带来节点能耗不均问题[5]。

针对LEACH算法的缺点，国内外的研究者提出了许多改进方案。根据节点剩余能量来选择簇头可以延长网络生存周期。文献[6]引入仿生学，模仿蜜蜂的行为来选择簇头；文献[7]根据平均能量预测和历史能耗来选择簇头；文献[8]通过对节点剩余能量的估算实现对簇头选举机制的优化，并提出“生命游戏”睡眠调度模型和利用邻居节点作为转发节点的多跳通信方式；文献[9]通过簇内进一步细分将整个网络划分为3个层次。上述算法在不同程度上提高了网络生存周期，但较为复杂，增加了节点的负担。

由于LEACH协议分簇的随机性，不同轮簇头数量不同，簇头的能耗也不同。LEACH-MAC从减少能耗的角度研究了最佳簇头数k，在选择簇头时逐个选择，直到簇头数量达到k[10]，从而提高了网络生存周期。

文献[11]提出了WRECS(weighted residual energy-based cluster head selection)算法，根据簇内节点数量的不同，使簇头节点在之后若干轮不能再次成为簇头，从而达到了平衡节点能耗的目的。

本文提出了一种基于多重竞争的簇头(multiple competitive cluster head,MCCH)选择算法，根据簇头的剩余能量、邻节点数、到已选定簇头的距离等因素选择簇头，提高了网络的生存周期。

2 网络模型

对无线传感器网络的节点假设如下:

1)节点随机布设在边长为L的正方形区域内，位置信息未知。节点能量有限，并能感知自身的剩余能量。

2)节点可以收发数据，发送信号的强度可变。节点可以感知接收信号的强度，通过与发送信号的强度比较，可以估算到发送节点的距离。

3)节点工作相互独立，各个节点具有唯一的ID，均可成为簇头。簇头直接发送信息到汇聚节点。

4)汇聚节点位置固定，具有较强的处理能力。相对于一般节点，汇聚节点的能量可以认为无限。

文献[12]采用的能量模型比较典型，即当传输距离为d，发送数据长度为qbit时，能量消耗如式(2)

(2)

式中ETx,ERx分别为收、发能耗；Eelec为发送或接收电路每完成1 bit数据收发消耗的能量。dcorssover为阈值，若d

3 MCCH选择算法

MCCH是一种分簇算法，将网络的工作状态划分成轮，一轮包括建立阶段和稳定阶段。建立阶段的主要工作是选举本轮的簇头。

(3)

ηi=1-min[ni×p,1]

(4)

为了使ni大的节点优先成为簇头，设置延时时间

ti=(ηi+γ)×t0

(5)

式中t0为选定的时间;γ为随机数且γ∈[0,1]。对于节点i，若其可以成为簇头，则在簇头选取时首先延时ti。ti到时若簇头选取仍未结束，则i成为簇头。

一般来说，簇头均匀分布可以减少能耗[13]，本文通过调整ti来促使簇头均匀分布。若一个节点成为簇头，则以事先选定的强度发送建簇信息。其他节点接收该信息，根据接收信号的强度估算到该簇头的距离l。并按式(6)更新延时时间

(6)

算法步骤如下：

3)延时结束时该节点成为簇头，广播建簇信息，信息中包含自身的ID。其他节点接收建簇信息，估算距离，按式(6)更自身延时时间。

4)汇聚节点接收建簇信息，当收到P×N个建簇信息后广播簇头选举结束信息。未成为簇头的节点收到该信息后，根据收到的信号强度，加入最近的簇头，向其发送入簇信息并附上自身ID。簇头接收入簇信息，向发出请求的节点返回一确认信息，完成簇的建立。

5)节点采集信息，通过时分多址(time division multiple access,TDMA)方式送给簇头并附上自身剩余能量信息。簇头进行数据融合后发给汇聚节点。

6)汇聚节点接收采集的信息数据并收集和各个节点的剩余能量信息。一轮结束后返回步骤(1)循环执行。

4 系统仿真

使用NS2进行仿真，比较了LEACH，WRECS，LEACH-MAC和MCCH 4种算法的效果。仿真的具体环境为100个节点分布在边长100 m的正方形区域内，汇聚节点在正方形中心，其他参数设置：εfs为10 pJ/bit/m2，εmp为0.001 3 pJ/bit/m4，Eelec为50 nJ/bit，dcorssover为87 m，p为0.05。

图1通过仿真数据比较了4种算法在随机选取的10轮中每一轮的能耗。LEACH算法在簇头数量、位置上存在较大的随机性，且未考虑剩余能量，所以，能耗最大且不同轮的能耗差异较大。WRECS算法优先选择剩余能量高的节点做簇头，在一定程度上实现了节点间的能耗均匀，但该算法不能降低能耗。LEACH-MAC算法可以确保合适的簇头数量，从而减少了能耗和不同轮之间的能耗差异。MCCH算法根据剩余能量、邻节点数、簇头位置等因素进行竞争，在一定程度上实现了簇头的均匀分布，所以能耗较小。

图1 网络能耗对比

图2为4种算法网络生命周期的仿真结果。从图中可见，LEACH算法的生命周期最短。WRECS算法考虑了节点能耗的均匀，在一定程度上延迟了节点开始死亡的时间，但由于该算法不能降低能耗，所以,节点全部死亡的时间早于LEACH算法。LEACH-MAC算法稳定了簇头数量，从而减少了能耗，但由于簇头分布不均匀等因素，网络寿命提高幅度有限。MCCH算法在剩余能量较多的节点中选择簇头，并优先选择邻节点多且到已选定簇头距离合适的节点成为新的簇头，从而提高了网络的生存周期。

图2 存活节点数对比

5 结 论

提出了MCCH算法,算法中节点根据多种因素进行竞争成为簇头，剩余能量较多，选择邻节点多，到已选定簇头距离合适的节点成为簇头的可能性更大。通过仿真证明了该算法能延长网络生存周期。下一步的工作可以研究簇覆盖范围与能耗的关系，根据能耗动态的调整簇覆盖范围。

[1] Kulkarni R V,FöRster A,Venayagamoorthy G K.Computational intelligence in wireless sensor networks:A survey[J].IEEE Communications Surveys & Tutorials,2011,13(1):68-96.

[2] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2000,1(4):660-670.

[3] Al-Karaki J N,Kamal A E.Routing techniques in wireless sensor networks:A survey[J].IEEE Wireless Communications,2004,11(6):6-28.

[4] Nayebi A,Sarbazi-Azad H.Performance modeling of the LEACH protocol for mobile wireless sensor networks[J].Journal of Parallel & Distributed Computing,2011,71(6):812-821.

[5] Roseline R A,Sumathi P.Local clustering and threshold sensitive routing algorithm for wireless sensor networks[C]∥2012 International Conference on Devices,Circuits and Systems(ICDCS),IEEE,2012:365-369.

[6] Saleem M,Ullah I,Farooq M.BeeSensor:An energy-efficient and scalable routing protocol for wireless sensor networks[J].Information Sciences,2012,200(2):38-56.

[7] 洪 榛,俞 立,张贵军.多级异构无线传感网高效动态聚簇策略研究[J].自动化学报,2013,39(4):454-460.

[8] 杨永健,贾 冰,王 杰.无线传感器网络中LEACH协议的改进[J].北京邮电大学学报,2013,36(1):105-109.

[9] Chen Y L,Wang N C,Shih Y N.Improving low-energy adaptive cllustering hierarchy architectures with sleep mode for wireless sensor networks[J].Wireless Personal Communications，2014,75(1)：349-368.

[10] Batra P K,Kant K.LEACH-MAC:A new cluster head selection algorithm for wireless sensor networks[J].Wireless Networks,2016,22(1):1-12.

[11] Bao X,Xie J,Nan L,et al.WRECS:An improved cluster heads selection algorithm for WSNs[J].Journal of Software,2014,9(2):78-89.

[12] Kumar D, Aseri T C, Patel R B.EEHC:Energy efficient heterogeneous clustered scheme for wireless sensor networks[J].Computer Communications, 2009, 32(4):662-667.

[13] Su J S,Guo W Z,Yu C L,et al.Fault-tolerance clustering algorithm with load-balance aware in wireless sensor networks[J].Chinese Journal of Computers,2014,37(2):445-456.