基于环的节点非均匀分布分簇算法

孙 超，彭 力，朱雪芳

(1.物联网应用技术教育部工程研究中心(江南大学)，江苏 无锡 214122； 2.江苏省联合职业技术学院，江苏 无锡 214028)

基于环的节点非均匀分布分簇算法

孙 超1*，彭 力1，朱雪芳2

(1.物联网应用技术教育部工程研究中心(江南大学)，江苏 无锡 214122； 2.江苏省联合职业技术学院，江苏 无锡 214028)

(*通信作者电子邮箱841963798@qq.com)

针对无线传感器网络(WSN)中基于环的节点非均匀分布网络模型下的能量空洞问题，提出了一种基于环的节点非均匀分布分簇算法(RCANND)。该算法在节点非均匀分布的网络模型下，通过每环的能耗最小化，计算每一环的最优簇首数；通过节点剩余能量、距基站距离以及与邻居节点的平均距离计算簇首选择度。在簇内以簇首选择度序列表进行簇首轮转，降低分簇次数，提高网络能量的利用效率。对提出的算法进行仿真对比实验，仿真结果表明，相同半径、不同分布模型下节点的平均能耗波动很小；相同分布模型、不同半径下节点的平均能耗波动也不明显。以网络中50%节点存活作为网络生命周期，在节点非均匀分布情况下，所提算法的网络生命周期比混合能量高效分布式不等分簇算法(UHEED)和轮转的混合能量高效分布式不等分簇算法(RUHEED)分别提高约18.1%和11.5%；在节点均匀分布模型下,所提算法的网络生命周期比基于分环的能量高效无线传感器网络分簇路由(RECR)协议提高约6.4%。所提算法有效均衡了不同分布模型下的能耗，有效延长了网络生命周期。

非均匀分布；分环；分簇；能量空洞；无线传感器网络

0 引言

无线传感网络(Wireless Sensor Network, WSN)是由大量的廉价微型传感器节点以无线通信方式组成的一个多跳自组织网络[1]。环境信息的采集和管理是无线传感器网络的主要功能，在工业、农业、军事、安全、医疗等很多领域都有广泛应用。随着无线传感器网络的应用越来越广泛，WSN中能量的高效利用成为需要解决的关键问题。大量散布的无线传感器节点一般由有限能量的电池供电，而节点电池更换困难，节点寿命有限。为了延长网络生命周期，需要能量高效、能耗均衡的无线传感器网络路由协议，否则会产生能量空洞现象[2]。在WSN中传感器节点采用多跳的方式将采集的数据发送给基站。一般情况下，传感器节点在检测区域内的分布是随机的，它们可以自组织网络。当一个节点因为能量消耗殆尽或者其他原因导致不能工作，称之为节点死亡，节点死亡就可能导致出现能量空洞现象。

能量空洞现象的避免是延长网络生命周期的重要方面，而要避免部分节点过早死亡就要很好地均衡整个网络的节点能耗[3]。在无线传感器网络中分簇路由算法相比平面路由算法具有更好的节能性，因此分簇的路由协议是研究重点。低功耗自适应集簇分层型(Low Energy Adaptive Clustering Hierarchy, LEACH)算法[4]是最早的分簇路由协议，之后很多文献对分簇协议进行了大量研究，文献[5]中提出的混合能量高效分布式不等分簇算法(Unequal Hybrid Energy Efficient Distributed algorithm, UHEED)在一种混合能量高效分布式自组织网分簇(Hybrid, Energy-Efficient, Distributed clustering approach for ad-hoc sensor network, HEED)方法[6]的基础上采用基于非均匀分簇的无线传感器网络路由(Energy-Efficient Uneven Clustering, EEUC)协议[7]的竞争半径计算方法，通过综合考虑节点到基站的距离因素进行非均匀的分簇以解决HEED算法在能量空洞问题上的不足。文献[8]中轮转的混合能量高效分布式不等分簇算法(Rotated Unequal Hybrid Energy Efficient Distributed algorithm, RUHEED)对UHEED作了进一步的改进，通过成簇后簇首轮转的方式减少簇首选举与成簇过程中的能量开销达到延长网络生命周期的目的；但是算法在簇首轮转阶段仅考虑了节点剩余能量，直到出现节点死亡才进行重新分簇，不能很好地均衡能耗，这导致节点一旦出现死亡整个网络的节点迅速死亡。

除了通过分簇路由协议提高网络的生命周期，克服能量空洞现象，也有文献提出采用同心环模型对能量空洞现象进行分析。文献[9]提出了在节点均匀分布的WSN中采用同心环模型分析能量空洞现象，验证了圆环宽度相等的情况下，路由上的能量消耗最小。文献[10]为了均衡节点能量，在同心环模型上提出部署算法，使每一环上的节点数目相等，这造成了靠近基站环的节点密度过大，浪费了能量和成本。文献[11]提出了基于同心环的分簇路由协议，对簇头位置初始化、簇头轮转选择、簇间路由协议进行了优化，没有对每环的簇首数进行优化处理；文献[12]提出了一种基于分环的能量高效无线传感器网络分簇路由(sub-Ring-based Energy-efficient Clustering Routing for WSN, RECR)算法，算法对各环的簇首数进行了优化，采用了主次簇首轮换的方式降低节点能耗。以上基于分环的算法研究仍然在均匀分布的WSN网络模型下，或者对网络节点采用部署策略，只能应用到小部分的实际环境。

现有研究主要集中在网络节点均匀分布情况或者通过采用节点部署策略来解决网络能耗不均产生的能量空洞问题。本文针对同构网络中，节点非均匀分布前提下的能量空洞问题，提出了非均匀分布的同心环传感器网络模型分簇路由算法——基于环的节点非均匀分布分簇算法(Ring-based Clustering Algorithm for Nodes Non-uniform Deployment, RCANND)。该算法在同心环网络模型基础上，针对节点非均匀分布的传感器网络研究能量均衡的分簇路由协议。在网络初始化阶段根据网络总能耗最低的原则以及每一环的节点数目对簇首数优化，得到最优簇首数后再计算每一环各自的簇首竞争半径。在簇首选举阶段，通过竞争获得最佳簇首，同时对簇内的各个成员节点计算簇首选择度，通过簇首轮转来均衡各节点能耗，减少了每轮进行簇首选举的网络能耗。最后通过簇间多跳路由实现数据传输到基站，完成通信。

1 无线传感器网络采用的模型

1.1 网络模型

在本文，对无线传感器网络模型作如下假设：1)节点同构，基站外的所有节点具有相同的特性，如初始能量、通信半径等。2)监测区域内的同构传感器节点具有唯一ID，规定以j为下标的参数均表示第j个传感器节点的参数。3)所有节点和基站部署之后都是静止的，都能根据距离调节它们的发射功率。4)同构传感器网络节点随机分布在半径为R的区域内，圆形区域内分为M个宽度相等的环形带，并且每个环形带内的传感器节点的密度是随机的；对环形带进行编号，规定用i表示第i(i=1,2,…，M)个环形带，文中下标为i的均表示第i个环形带中的参数。5)这些环形带之间节点的分布是非均匀的，每个环形带中都有着不同的节点密度参数ρi，ρi的值可以随不同的部署模型而改变。在一个环形带中，节点的个数Ni=ρi×Si，Si为该环形面积。网络节点分布模型如图1所示。

图1 网络节点分布模型

1.2 能量消耗模型

本文采用与LEACH算法相同的无线电模型。发送lb的信息量到距离d处需要消耗的能量如下：

(1)

式中：εfs表示自由空间模型的能耗系数；εamp表示多路径放大电路的能耗系数；d0是节点可以直接与基站通信的距离。为了接收lb的信息量，消耗的能量为：

ERx(l)=l×Eelec

(2)

此外，对网络中的其他能量消耗作如下假设：1)节点感知环境信息的能量消耗为Es；2)簇首消耗EDA用于数据融合。

2 RCANND设计

本文提出的WSN分簇路由算法以轮为周期运行，每一轮由优化分簇和数据传输两部分组成。优化分簇部分由三个阶段组成：第一阶段，初始化网络，对网络中每环簇首数进行优化；第二阶段，由簇首选举和簇建立组成的分簇过程阶段；第三阶段，每完成一次数据采集过程进行簇首轮转以均衡节点能耗，轮转一定次数后重新循环第二阶段到第三阶段。数据传输部分，通过簇间多跳的路由方式将数据传输到基站。

2.1 簇首数优化

在传感器网络区域内，获得最优簇首数是有效均衡网络能耗、延长网络生命周期的重要因素。在基于环的分簇路由算法中，都有对簇首数优化，但是这些算法主要是在均匀分布的网络模型基础之上。现在用k来表示期望的最优簇首数目，根据文献[13]中每簇平均面积的计算方法以及本文中的网络模型，网络监测区域内每簇的平均面积为πR2/k，那么每簇节点平均密度ρ=1/(πR2/k)，那么可以得到节点到簇首距离的平方期望是：

(3)

根据本文的能量消耗模型，当基站距离节点很近时，通信损耗认为是自由空间损耗。当传感器节点距离基站较远时认为是多路径损耗。现在总的能量损耗由文献[14]可得：

(4)

(5)

簇首到基站的平均距离估算公式为：

(6)

式中：Ri表示每一环到基站的最大半径。由此，kopt可以求得：

(7)

现在让每个环里的簇的数目是ki,ki-1,…,k1，那么：

(8)

式中：

(9)

2.2 分簇过程

Pj=c1Er/Einit+c2di/dj-toBS+c3/dj-avg

(10)

(11)

式中：Er为节点剩余能量；Einit为节点初始能量；di为该圆环到基站的平均期望距离；dj-toBS为节点到基站的距离；dj-avg为各节点与竞争半径内各节点的平均距离；c1、c2、c3为权重系数且c1+c2+c3=1。

选择度Pj考虑了节点的剩余能量、到基站的距离因素，以及与邻居节点间的距离。如果在竞争半径内，某个节点簇首选择度Pj最大，那么该节点被选为簇首。

2.3 簇头轮转策略

成簇过程完成后，簇首已经获得了各个簇成员的Pj，簇首按照Pj大小排序形成一个簇首选择序列表。簇首选择序列表作为下一轮的簇首选择依据。每一轮数据传输结束后，根据簇首选择序列中排在下一位次的节点成为簇首并在簇内广播消息，其他节点接收到消息后，下一轮将数据传送给新簇首。每经过n轮，重新进行分簇过程，产生新的簇首选择序列，以均衡网络能耗；这里n取各环中的最小值，n由式(13)给出。虽然有些节点未在本次轮转担当簇首，但是在下次竞争簇首时具备更大优势，依然能够保证整个网络的能耗均衡。

刘雁衡迟迟不动，被一个警员推了个趔趄。寒流果然来了，冷风吹到脸上，彻骨生寒。刘雁衡、吴邦雄，还有两个男生，被四个警员上上下下搜查一遍，没搜出什么。那胖大警官独自留在室内，目光犹如鼻涕虫，潮湿黏糊，在四名女学生身上刷来刷去。最后他挑出身材高挑的黄莺：“你，过来。”黄莺的脸一下子白了，站着不动。警官探出粗大的右手，目标明确地按到她腰上。

ni=Ni/ki

(12)

n=min{n1,n2，…，ni}

(13)

数据传输过程，簇首对簇内数据进行融合后，将数据传输到基站。当簇首到基站的距离小于等于直接传输距离d0时，簇首直接与基站进行通信;当距离大于d0时，采用多跳的路由方式将数据传送到基站。仿真中的具体路由算法采用文献[11]中的簇间多跳路由算法。

3 算法仿真与分析

为了验证本文算法在能耗均衡以及延长网络生命周期方面的性能，通过Matlab仿真平台，对算法进行仿真和对比。仿真中使用的网络节点分布模型如1.1节所述，传感器网络部署在一个圆形监测区域内，基站位于监测区域的中心位置。本文主要的仿真参数均采自LEACH算法[4]，主要的仿真参数如表1所示。

表1 主要仿真参数

3.1 能耗均衡性

将监测区域分成宽度相等的3环，针对不同的节点分布情况，作网络能耗变化的仿真。当节点分布模型不同时，簇首产生的数目必然不同，为了验证算法在节点分布密度变化时依然能有良好的能耗均衡性能，现在选取四种典型节点分布模型进行仿真对比。这四种分布模型分别是case1(ρ1>ρ2>ρ3)、case2(ρ2>ρ3=ρ1)、case3(ρ1<ρ2<ρ3)以及case4(ρ1=ρ2=ρ3)，本次仿真的具体取值如表2，仿真结果如图2所示。

表2 典型节点分布模型

图2 不同半径和分布情况下节点平均能耗

从图2中可以看出，相同半径下，在网络节点分布密度不同的情况下，网络的节点平均能耗的波动并不明显；算法最优簇首数的动态选择发挥了均衡整个网络能耗的作用，使得不同分布模型下的网络能耗未出现大幅变化；当半径不同时，由于半径越大，平均传输距离越大，较大半径平均能耗会略有提升。对比各个半径下、相同分布密度的网络节点平均能耗，依然波动不明显。从图2中还可以看出：不同半径下，均在第三种节点分布模型(case3)下的平均能耗最高，第三种分布模型的各环节点密度系数的关系是ρ1<ρ2<ρ3，可见最外环的节点数目最多，而最内环的节点数目最少，这导致节点与基站的平均通信距离最大，能耗自然会略有提高。

3.2 分环数与网络生命周期

讨论网络半径变化时，网络的最佳分环数。针对本文的网络模型，在网络节点分布情况不变以及半径不变的情况下，改变同心环的数量。在100m、180m、320m的半径下进行仿真，讨论不同的分环数与网络生命周期的关系，仿真结果如图3所示。从图3中可以看出，整体上，分环数过多会导致网络生命周期减少，但是同半径下使网络生命周期最长的最优分环数总是存在的。由于算法对于簇首数的优化，分环数开始增加时，网络生命周期的减少并不明显。随着同心环数量的增加，同心环的面积在减小，必然会产生更多的簇，节点的能量消耗增加，网络生命周期减少。

从3.1节中的仿真结果可知，本文算法的最优簇首数的动态选择，可以有效地均衡不同密度下的网络能耗以避免能量空洞、延长网络生命周期；但是当分环数变多导致的簇首数增加，路由的转发能量增加，仍然使网络总能耗增加，减少了网络生命周期。可见，本文算法仍然需要合理选择分环数量以有效延长网络生命周期。

图3 不同半径下分环数与网络生命周期的关系

3.3 网络生命周期对比

为了验证算法在延长网络生命周期方面的有效性，在非均匀分布的模型中，将本文算法与算法UHEED和RUHEED进行了对比；在均匀分布情况下，将本文算法与分环算法RECR进行对比，仿真结果如图4所示。

从图4(a)可以看出，本文算法解决了RUHEED在簇首轮转上导致的能耗不均衡、节点迅速死亡的问题；由于本文算法的不定周期分簇，部分轮转过程会产生较大能耗，死亡节点在后期会产生死亡速度增加现象。以50%节点存活作为网络的生命周期，在非均匀分布情况下，本文算法的网络生命周期比UHEED和RUHEED分别提高约18.1%和11.5%。由图4(b)可以看出，RECR算法采用主次簇首轮换的方式减少分簇的能耗，本文算法采用的簇首轮换机制比RECR减少了更多的分簇能耗，因而网络生命周期上比RECR算法提高了约6.4%，可见在均匀分布的情况下，本文算法在网络生命周期上也略有提高。由此可得，所提算法相比传统的分环算法，主要优势在于能适应不同的节点分布情况，能够适应更多的实际应用环境。

图4 不同算法生命周期对比

4 结语

本文在已有的分环分簇算法基础上提出了一种节点非均匀分布情况下的算法。该算法主要解决在节点非均匀分布的网络模型下的能耗均衡问题，避免产生能量空洞现象，延长了网络的生命周期。在网络初始化阶段，根据每一环的节点数目进行簇首数优化；在簇首选举阶段，通过竞争获得最佳簇首，同时对簇内的各个成员节点计算簇首选择度Pj，通过簇首轮转来均衡各节点能耗，同时避免了每轮进行簇首选举，降低了网络能耗。仿真结果表明，本文算法在不同分布模型下有效地均衡了网络能耗，延长了网络生命周期。今后可考虑针对分环的大规模网络中多跳的簇间路由算法进行进一步的研究。

)

[1]RAWATP,SINGHKD,CHAOUCHIH,etal.Wirelesssensornetworks:asurveyonrecentdevelopmentsandpotentialsynergies[J].TheJournalofSupercomputing, 2014, 68(1): 1-48.

[2]LIUXX.Asurveyonclusteringroutingprotocolsinwirelesssensornetworks[J].Sensors, 2012, 12(8): 11113-11153.

[3]PANTAZISNA,NIKOLIDAKISSA,VERGADOSDD.Energy-efficientroutingprotocolsinwirelesssensornetworks:asurvey[J].IEEECommunicationsSurveys&Tutorials, 2013, 15(2): 551-591.

[4]HEINZELMANWR,CHANDRAKASANA,BALAKRISHNANETH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]//HICSS’00:Proceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences.Washington,DC:IEEEComputerSociety, 2000: 8020.

[5]EVERE,LUCHMUNR,MOSTARDAL,etal.UHEED:anunequalclusteringalgorithmforwirelesssensornetworks[EB/OL]. [2016- 11- 10].https://core.ac.uk/download/pdf/17301738.pdf.

[6]YOUNISO,FAHMYS.HEED:ahybrid,energy-efficient,distributedclusteringapproachforadhocsensornetworks[J].IEEETransactionsonMobileComputing, 2004, 3(4): 366-379.

[7] 李成法,陈贵海,叶懋,等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(1):27-36.(LICF,CHENGH,YEM,etal.Anunevencluster-basedroutingprotocolforwirelesssensornetworks[J].ChineseJournalofComputers, 2007, 30(1): 27-36.)

[8]AIERKENN,GAGLIARDIR,MOSTARDAL,etal.RUHEED—rotatedunequalclusteringalgorithmforwirelesssensornetworks[C]//Proceedingsofthe2015IEEE29thInternationalConferenceonAdvancedInformationNetworkingandApplicationsWorkshops.Piscataway,NJ:IEEE, 2015: 170-174.

[9]OLARIUS,STOJMENOVICI.Designguidelinesformaximizinglifetimeandavoidingenergyholesinsensornetworkswithuniformdistributionanduniformreporting[C]//INFOCOM2006:Proceedingsofthe2006 25thIEEEInternationalConferenceonComputerCommunications.Piscataway,NJ:IEEE, 2006: 1-12.

[10] 任丽婕,郭忠文,唐瑞春.无线传感器网络中基于能量平衡的部署算法[J].中国海洋大学学报(自然科学版),2008,38(5):841-844.(RENLJ,GUOZW,TANGRC.Anodeplacementstrategybasedonenergy-balanceforwirelesssensornetworks[J].PeriodicalofOceanUniversityofChina, 2008, 38(5): 841-844.)

[11] 刘震,郭航.基于同心环分簇网络模型的WSN能量空洞避免方法研究[J].计算机科学,2013,40(12):147-151.(LIUZ,GUOH.Studyonconcentric-ringandcluster-basedenergyholeavoidingmethodinwirelesssensornetworks[J].ComputerScience, 2013, 40(12): 147-151.)

[12] 吴玉成,李伟琪, 胡真,等.一种基于分环的能量高效无线传感器网络分簇路由协议[J].传感器与微系统,2015,34(5):8-11.(WUYC,LIWQ,HUZ,etal.Asub-ring-basedclusteringroutingprotocolforenergy-efficientWSNs[J].TransducerandMicrosystemTechnologies, 2015, 34(5): 8-11.)

[13]HEINZELMANWB,CHANDRAKASANAP,BALAKRISHNANH.Anapplication-specificprotocolarchitectureforwirelessmicrosensornetworks[J].IEEETransactionsonWirelessCommunications, 2002, 1(4): 660-670.

[14]TRIPATHIRK,SINGHYN,VERMANK.Two-tieredwirelesssensornetworks-basestationoptimalpositioningcasestudy[J].IETWirelessSensorSystems, 2012, 2(4): 351-360.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61502204),theUniversityNaturalScienceResearchSurfaceProjectofJiangsu(16KJB510044).

SUN Chao, born in 1991, M. S. candidate. His research interests include wireless sensor network.

PENG Li, born in 1967, Ph. D., professor. His research interests include vision sensor network, artificial intelligence.

ZHU Xuefang, born in 1967, M. S., associate professor. Her research interests include communication and control.

Ring-based clustering algorithm for nodes non-uniform deployment

SUN Chao1*, PENG Li1, ZHU Xuefang2

(1.EngineeringResearchCenterofInternetofThingsApplicationTechnologyoftheMinistryofEducation(JiangnanUniversity),WuxiJiangsu214122,China; 2.JiangsuUnionTechnicalInstitute,WuxiJiangsu214028,China)

Aiming at the problem of energy hole in the nodes non-uniform deployment network model based on the ring in Wireless Sensor Network (WSN), a Ring-based Clustering Algorithm for Nodes Non-uniform Deployment (RCANND) was proposed. The number of the optimal cluster heads in each ring was calculated by minimizing the energy consumption of each ring in the nodes non-uniform deployment network model. The cluster head selectivity was calculated by using the residual energy of the nodes, the distance from the base station, and the average distance from the neighbor nodes. The cluster head rotation was carried out with the cluster head selection sequence in cluster, and the number of cluster formation phases was reduced to improve the efficiency of network energy utilization. The proposed algorithm was tested in the simulation experiments, the experimental results show that, the average energy consumption fluctuation of nodes under the same radius but different nodes deployment models is very small. The average energy consumption fluctuation of nodes under the same nodes deployment model but different radiuses is not obvious. The network lifetime was defined as the survivability of 50% network nodes. In the case of non-uniform deployment of nodes, the network lifetime of the proposed algorithm is higher than that of Unequal Hybrid Energy Efficient Distributed algorithm (UHEED) by about 18.1% while it is also higher than that of Rotated Unequal Hybrid Energy Efficient Distributed algorithm (RUHEED) by about 11.5%. In the case of uniform deployment of nodes, the network lifetime of the proposed algorithm is higher than that of sub-Ring-based Energy-efficient Clustering Routing for WSN (RECR) by about 6.4%. The proposed algorithm can effectively balance the energy consumption under different nodes deployment models and prolong the network lifetime.

non-uniform deployment; sub-ring; clustering; energy hole; Wireless Sensor Network (WSN)

2016- 12- 12;

2017- 03- 01。

国家自然科学基金资助项目(61502204);江苏省高校自然科学研究面上项目(16KJB510044)。

孙超(1991—)，男，山东青岛人，硕士研究生，主要研究方向：无线传感器网络； 彭力(1967—),男,河北唐山人, 教授, 博士, 主要研究方向:视觉传感器网络、人工智能； 朱雪芳(1967—)，女，江苏常熟人，副教授，硕士，主要研究方向：通信与控制。

1001- 9081(2017)06- 1527- 05

10.11772/j.issn.1001- 9081.2017.06.1527

TP

A