基于環的節點非均勻分布分簇算法

孫 超，彭 力，朱雪芳

(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