基于多重竞争的无线传感器网络簇头选择算法*
2018-01-27贾银亮张驰宇梁康武
贾银亮,张驰宇,梁康武
(南京航空航天大学 自动化学院,江苏 南京 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 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)循环执行。 使用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 存活节点数对比 提出了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.3 MCCH选择算法
4 系统仿真
5 结 论