基于動(dòng)態(tài)簇半徑的非均勻分簇算法

熊 煉，葉建光，劉曉彤

(重慶郵電大學(xué) 通信工程應(yīng)用新技術(shù)研究所，重慶400065)

基于動(dòng)態(tài)簇半徑的非均勻分簇算法

熊 煉，葉建光，劉曉彤

(重慶郵電大學(xué) 通信工程應(yīng)用新技術(shù)研究所，重慶400065)

在無線傳感器網(wǎng)絡(luò)分簇路由算法中，針對(duì)節(jié)點(diǎn)能耗不均衡所引發(fā)的“熱區(qū)”問題，提出了基于動(dòng)態(tài)簇半徑的非均勻分簇算法(UCDCR)。該算法在簇組建階段，對(duì)網(wǎng)絡(luò)進(jìn)行區(qū)域劃分，不同區(qū)域的候選簇首通過簇競爭半徑來構(gòu)建大小不同的簇，使簇首隨網(wǎng)絡(luò)的運(yùn)行動(dòng)態(tài)的改變簇競爭半徑，為數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留更多能量。仿真結(jié)果表明：與EEUC算法和CUCRA算法相比，UCDCR算法更加有效地均衡了節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)生命的周期。

無線傳感器網(wǎng)絡(luò)；動(dòng)態(tài)；簇半徑；非均勻分簇

0 引言

隨著無線通信和微電子工藝的快速發(fā)展，無線傳感器網(wǎng)絡(luò)成為了國際上的研究熱點(diǎn)。傳感器節(jié)點(diǎn)能量有限，且不容易更換電池，如何減少節(jié)點(diǎn)的能量消耗，延長網(wǎng)絡(luò)的生存時(shí)間成為無線傳感器網(wǎng)絡(luò)中的研究熱點(diǎn)[1]。無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸模式為多對(duì)一(many-to-one)模型[2-3]，但由于靠近Sink的傳感器節(jié)點(diǎn)需要轉(zhuǎn)發(fā)外層的數(shù)據(jù)[4-5]，這決定著網(wǎng)絡(luò)中的負(fù)載必然會(huì)出現(xiàn)不平衡，產(chǎn)生“熱區(qū)”問題[6]。

為了解決“熱區(qū)”問題，Soro等[7]首次提出了非均勻分簇思想，主要是通過預(yù)設(shè)簇首為超級(jí)節(jié)點(diǎn)從而達(dá)到均衡網(wǎng)絡(luò)負(fù)載的目的，但簇頭位置是事先計(jì)算好的，無法動(dòng)態(tài)建簇，適應(yīng)性較弱。李成法等在文獻(xiàn)[8]提出了EEUC算法，該算法采用了非均勻競爭半徑分簇方法，在同一競爭區(qū)域內(nèi)比較剩余能量多少，剩余能量多的節(jié)點(diǎn)當(dāng)選簇首。算法在一定程度上緩解了“熱區(qū)問題”，但如果簇半徑保持不變，隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)的剩余能量逐漸減少，維持原來的競爭半徑，會(huì)過快地消耗簇首的能量，熱區(qū)問題仍然存在。文獻(xiàn)[9]對(duì)文獻(xiàn)[8]的算法進(jìn)行了改進(jìn)，提出了CUCRA算法。CUCRA[9]也是采用競爭半徑的思想選擇簇首，并且考慮了節(jié)點(diǎn)的剩余能量因素，使節(jié)點(diǎn)的競爭半徑隨著節(jié)點(diǎn)的能量減少而變小。但隨著算法的運(yùn)行，競爭半徑越來越小，導(dǎo)致簇首數(shù)增多，傳輸時(shí)延變長。本文在以上研究基礎(chǔ)上，提出了基于動(dòng)態(tài)簇半徑的非均勻分簇算法(Uneven Clustering Algorithm Based on Dynamic Cluster Radius，UCDCR)。UCDCR算法創(chuàng)新之處：把網(wǎng)絡(luò)區(qū)域劃分為“熱點(diǎn)區(qū)域”和“非熱點(diǎn)區(qū)域”，定義不同區(qū)域簇半徑，使不同區(qū)域的簇首合理利用能量，有效改善網(wǎng)絡(luò)時(shí)延和能量均衡問題；對(duì)算法的路由進(jìn)行了改進(jìn)，均衡了網(wǎng)絡(luò)的能耗，很好地解決了“熱區(qū)”問題。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

整個(gè)網(wǎng)絡(luò)由一個(gè)匯聚節(jié)點(diǎn)和N個(gè)節(jié)點(diǎn)組成，并做如下假定：

① 網(wǎng)絡(luò)中只有一個(gè)匯聚節(jié)點(diǎn)，其他節(jié)點(diǎn)隨機(jī)分布在一個(gè)大小固定的區(qū)域。匯聚節(jié)點(diǎn)位于區(qū)域外面，且所有節(jié)點(diǎn)部署后不能移動(dòng)；

② 所有節(jié)點(diǎn)具有相同的屬性和功能，每一個(gè)節(jié)點(diǎn)都有一個(gè)唯一標(biāo)識(shí)符；

③ 節(jié)點(diǎn)沒有GPS功能去獲取精確的位置信息；

④ 所有節(jié)點(diǎn)傳輸功率可控，節(jié)點(diǎn)可以根據(jù)距離動(dòng)態(tài)地調(diào)整發(fā)射功率；

⑤ 鏈路是對(duì)稱的，如果發(fā)射功率已知，節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)度計(jì)算出發(fā)送者到自己的近似距離[10]。

1.2 能耗模型

本文主要采用與文獻(xiàn)[11]相同的能耗模型。向距離為d的節(jié)點(diǎn)發(fā)送lbit數(shù)據(jù)的能量消耗如式(1)所示：

ETx(l,d)=ETx-elec(l)+ETx-amp(l,d)=

(1)

節(jié)點(diǎn)接收lbit數(shù)據(jù)的能耗如式(2)所示：

ERx(l,d)=l*Eelec，

(2)

2 UCDCR算法

針對(duì)網(wǎng)絡(luò)中的“熱區(qū)”和簇半徑不能自適應(yīng)調(diào)整的問題，UCDCR算法將從層次網(wǎng)絡(luò)結(jié)構(gòu)、成簇機(jī)制、多跳路由三個(gè)方面進(jìn)行討論。

2.1 層次網(wǎng)絡(luò)結(jié)構(gòu)

當(dāng)傳感器節(jié)點(diǎn)部署在感應(yīng)區(qū)域后，基站在感應(yīng)區(qū)內(nèi)廣播一條“hello”消息，把整個(gè)區(qū)域分成m個(gè)等寬區(qū)域，離基站最近的區(qū)域?yàn)槎x為“熱點(diǎn)區(qū)域”，其他區(qū)域定義為“非熱點(diǎn)區(qū)域”[12]，同時(shí)定義區(qū)域數(shù)值隨著遠(yuǎn)離基站而增大，即“熱點(diǎn)區(qū)域”為1區(qū)域，以此類推，如圖1所示。

圖1 區(qū)域結(jié)構(gòu)圖

節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度，計(jì)算出自身與基站之間的距離，決定了自身所在的區(qū)域?；靖鶕?jù)式(3)和式(4)計(jì)算每個(gè)區(qū)域的上下邊界：

(3)

(4)

式中，UBi、LBi分別是第i個(gè)區(qū)域的上下邊界，dmax、dmin分別是監(jiān)控區(qū)域中節(jié)點(diǎn)到達(dá)基站的最大距離和最小距離。假設(shè)節(jié)點(diǎn)j距離基站的距離為dj，如果LBi

2.2 成簇機(jī)制

在成簇過程中，算法使用了基于距離和能量的競爭機(jī)制，每個(gè)節(jié)點(diǎn)在每輪開始時(shí)調(diào)整自己的競爭半徑，隨后網(wǎng)絡(luò)進(jìn)入簇頭選舉階段。節(jié)點(diǎn)si的競爭半徑如式(5)和式(6)所示。

“熱點(diǎn)區(qū)域”的競爭半徑Rcmp：

(5)

“非熱點(diǎn)區(qū)域”競爭半徑Rcmp：

(6)

因?yàn)榇厥啄芎南倪^快，UCDCR算法在2個(gè)簇之間的交匯部分選擇中繼節(jié)點(diǎn)來充當(dāng)2簇首的數(shù)據(jù)轉(zhuǎn)發(fā)的橋梁，減少簇首消耗。首先交匯節(jié)點(diǎn)向簇首發(fā)送成為中繼節(jié)點(diǎn)的請(qǐng)求消息，簇首根據(jù)式(7)選擇函數(shù)值較大的節(jié)點(diǎn)為中繼節(jié)點(diǎn)：

(7)

式中，Erem為交匯節(jié)點(diǎn)的剩余能量，d為交匯節(jié)點(diǎn)和簇首之間的距離。

在選舉開始時(shí)，設(shè)置一個(gè)額定值為T的概率閾值，隨機(jī)數(shù)值(0～1)

圖2 UCDCR分簇結(jié)構(gòu)

UCDCR算法在分簇階段的偽代碼如下所示：

Foreverynodeinthenetwork

1.α←RAND(0,1)

2.Ifα

3.beTentativeHead←true

4.Endif

5.IfbeTentativeHead=truethen

6.BroadcastCOMPETE_HEAD_MSG

7.Endif

8.OnreceivingaCOMPETE_HEAD_MSGfromsj

10.Addsjtosi.SCH

11.End if

12.While beTentativeHead=true do

13.If?sj∈si.SCHandsi.ResidueEnergy>sj.ResidueEnergythen

14.siBroadcastFINAL_HEAD_MSGandthenexit

15.Endif

16.Endwhile

2.3 多跳傳輸

當(dāng)簇組結(jié)束后，無線傳感器網(wǎng)絡(luò)進(jìn)入數(shù)據(jù)傳輸階段。主要包括2部分：簇內(nèi)數(shù)據(jù)傳輸和簇間數(shù)據(jù)傳輸。本文簇內(nèi)數(shù)據(jù)傳輸與LEACH簇內(nèi)數(shù)據(jù)傳輸方式相同。簇間數(shù)據(jù)傳輸策略如下：

① 如果簇首節(jié)點(diǎn)si位于熱點(diǎn)區(qū)域內(nèi)，那么它將數(shù)據(jù)直接傳遞給基站；

(8)

式中，u、v、w為0～1的常量，Nnember、N分別是簇內(nèi)節(jié)點(diǎn)數(shù)和總節(jié)點(diǎn)數(shù)。

3 算法分析

UCDCR算法的消息復(fù)雜度為O(N)，N為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。

證明：假設(shè)網(wǎng)絡(luò)中有C個(gè)交互節(jié)點(diǎn)，且普通節(jié)點(diǎn)成為候選簇首的概率為T，成為簇首的概率為P。算法開始時(shí)，有N×T個(gè)節(jié)點(diǎn)成為候選簇首并發(fā)送N×T條COMPETE_HEAD_MSG消息，競選成功的候選簇首節(jié)廣播一條FINISH_ELECT_MSG消息，而沒有競選成功的候選簇首則廣播一條競選失敗消息退出選舉；N×P個(gè)節(jié)點(diǎn)成為簇首并發(fā)送一條CH_V_MSG消息，N(1-P)個(gè)普通節(jié)點(diǎn)接收到來自簇首的CH_V_MSG消息后發(fā)送申請(qǐng)入簇消息，簇首接收到申請(qǐng)消息，同意后并回復(fù)申請(qǐng)者入簇的消息，交匯節(jié)點(diǎn)發(fā)送C個(gè)消息。所以，網(wǎng)絡(luò)每輪總開銷為N×T+N×T+N×P+N×(1-P)+C=(2T+1)N+C。綜上所述，算法的復(fù)雜度為O(N)。因此，UCDCR算法的網(wǎng)絡(luò)開銷比較小。

UCDCR算法采用非均勻分簇路由，通過對(duì)網(wǎng)絡(luò)區(qū)域劃分，動(dòng)態(tài)地改變簇半徑來均衡簇首的能耗?！盁狳c(diǎn)區(qū)域”的簇競爭半徑Rcmp考慮簇首的剩余能量，使得靠近基站的簇半徑減小，簇首能量消耗減少，減少“熱點(diǎn)區(qū)域”節(jié)點(diǎn)過多死亡的現(xiàn)象，有效解決“熱區(qū)問題”，“非熱點(diǎn)區(qū)域”的簇競爭半徑綜合考慮節(jié)點(diǎn)到基站的距離、剩余能量，位置和全網(wǎng)的平均能量的因素，引進(jìn)中繼節(jié)點(diǎn)，避免了簇首能耗過快而死亡，延長了網(wǎng)絡(luò)的生命周期。

4 仿真分析

本文使用MATLAB軟件對(duì)UCDCR算法進(jìn)行模擬實(shí)驗(yàn)，并與EEUC[4]算法和CUCRA[5]算法進(jìn)行對(duì)比分析。網(wǎng)絡(luò)參數(shù)如表1所示，除非特別指出，本算法的其他參數(shù)為T=0.4，R0=90 m，DIS_MAX=140 m，ΔR=1.7。

表1 網(wǎng)絡(luò)參數(shù)設(shè)置

本文將從以下3方面對(duì)UCDCR和EEUC、CUCRA算法進(jìn)行性能對(duì)比。

4.1 節(jié)點(diǎn)的平均能耗

圖3為3個(gè)算法隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)的平均能耗曲線圖。從圖中能夠看出，EEUC算法的平均能耗高于CUCRA算法，而兩者都高于UCDCR算法，說明UCDCR算法選舉的簇首分布均勻，降低了簇間傳輸和簇內(nèi)傳輸?shù)哪芎?，使得?jié)點(diǎn)的平均能耗低于其他2個(gè)算法。

圖3 節(jié)點(diǎn)平均能耗

4.2 傳輸時(shí)延

圖4給出了CUCRA、UCDCR算法的傳輸時(shí)延?？梢钥闯?，隨著算法的運(yùn)行，CUCRA的傳輸時(shí)延越來越大，這是因?yàn)榫W(wǎng)絡(luò)中簇首數(shù)目隨著網(wǎng)絡(luò)運(yùn)行而增多，導(dǎo)致傳輸時(shí)延增大；而本文提出的UCDCR算法雖然同樣進(jìn)行了簇競爭半徑調(diào)節(jié)，但并沒有出現(xiàn)CUCRA算法的現(xiàn)象，說明本文提出的算法是可行的。

圖4 傳輸時(shí)延

4.3 節(jié)點(diǎn)存活數(shù)

本文將第1個(gè)節(jié)點(diǎn)死亡的時(shí)間定義為網(wǎng)絡(luò)的生命周期。從圖5中可以看出，EEUC、CUCRA和UCDCR3種算法生命周期分別為586、704和808。所以，UCDCR算法網(wǎng)絡(luò)生命周期分別比EEUC算法和CUCRA算法提升了27%和13%。因?yàn)镋EUC算法不同于CUCRA和UCDCR算法，沒有簇競爭半徑的調(diào)整過程，所以，EEUC出現(xiàn)第1個(gè)死亡節(jié)點(diǎn)的時(shí)間要比它們?cè)?，而CUCRA算法的簇競爭半徑雖然考慮了節(jié)點(diǎn)的剩余能量，但并沒有對(duì)簇首的位置加以限制，本算法通過“熱點(diǎn)區(qū)域”和“非熱點(diǎn)區(qū)域”對(duì)節(jié)點(diǎn)位置精確限制，保證選舉出最優(yōu)簇首，所以網(wǎng)絡(luò)生命周期長。但CUCRA算法的存活節(jié)點(diǎn)數(shù)數(shù)量呈曲線下降趨勢(shì)，在1 140～1 300輪之間，其存活節(jié)點(diǎn)數(shù)多余UCDCR算法，這是因?yàn)殡S著算法的運(yùn)行，網(wǎng)絡(luò)中節(jié)點(diǎn)能量越來越少，其簇競爭半徑逐漸減小，使得簇首數(shù)目逐漸增多。如圖4所示，網(wǎng)絡(luò)中的簇間傳輸距離減少，降低了節(jié)點(diǎn)的能耗速率，但增加了傳輸時(shí)延。

圖5 節(jié)點(diǎn)存活數(shù)

5 結(jié)束語

本文提出了一種能耗均衡的UCDCR算法，通過網(wǎng)絡(luò)區(qū)域劃分、簇競爭半徑動(dòng)態(tài)調(diào)整來均衡網(wǎng)絡(luò)中簇首的能耗，以解決無線傳感器網(wǎng)絡(luò)中的“熱區(qū)”問題。生命周期比EEUC算法和CUCRA算法分別延長了27%和13%。同時(shí)，比CUCRA算法傳輸時(shí)延更低，保證了數(shù)據(jù)的實(shí)時(shí)性。但是，UCDCR算法采用隨機(jī)的方式選擇簇簇首，可能造成簇首的分配不合理，今后的工作會(huì)對(duì)該問題進(jìn)行修改。

[1] 朱永利,于永華,李麗芬.數(shù)據(jù)收集傳感器網(wǎng)絡(luò)的多模層次網(wǎng)絡(luò)構(gòu)建[J].計(jì)算機(jī)工程,2011,37(2)：111-113.

[2]WuX,ChenG,DasSK.AvoidingEnergyHolesinWirelessSensorNetworkswithNonuniformNodeDistribution[J].ParallelandDistributedSystems,IEEETransactionson,2008,19(5): 710-720.

[3]LiJ,MohapatraP.AnAnalyticalModelfortheEnergyHoleProbleminMany-to-oneSensorNetworks[C]∥IEEEVehicularTechnologyConference.IEEE，1999,2005,62(4): 2721-2725.

[4]XueY,ChangX,ZhongS,etal.AnEfficientEnergyHoleAlleviatingAlgorithmforWirelessSensorNetworks[J].IEEETransactionsonConsumerElectronics,2014,60(3): 347-355.

[5]LiuAF,WuXY,ChenZG,etal.ResearchontheEnergyHoleProblemBasedonUnequalCluster-radiusforWirelessSensorNetworks[J].Computercommunications,2010,33(3): 302-321.

[6]LiuAF,ZhangPH,ChenZG.TheoreticalAnalysisoftheLifetimeandEnergyHoleinClusterBasedWirelessSensorNetworks[J].JournalofParallelandDistributedComputing,2011,71(10): 1327-1355.

[7]SoroS,HeinzelmanWB.ProlongingtheLifetimeofWirelessSensorNetworksViaUnequalClustering[C]∥InProceedingsof19thInternationalParallelandDistributedProcessingSymposium(IPDPS05),2005:1-8.

[8] 李成法,陳貴海,葉 懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議 [J].計(jì)算機(jī)學(xué)報(bào),2007,30(1): 27-36.

[9]TongW,JiyiW,HeX,etal.ACrossUnequalClusteringRoutingAlgorithmforSensorNetwork[J].MeasurementScienceReview,2013,13(4): 200-205.

[10]KuipersF,VanMieghemP,KorkmazT,etal.AnOverviewofConstraint-basedPathSelectionAlgorithmsforQoSRouting[J].IEEECommunicationsMagazine,2002,40 (12):50-55.

[11]HeinzelmanWR,ChandrakasanA,BalakrishnanH.Energy-efficientCommunicationProtocolforWirelessMicrosensorNetworks[C]∥Proceedingsofthe33rdAnnualHawaiiInternationalConferenceon.IEEE,2000: 3005-3014.

[12] 許曉天,李德敏,周 凡,等.基于簇半徑差異化和節(jié)點(diǎn)能量區(qū)間的分簇算法[J].2015，24(2):170-173.

Uneven Clustering Algorithm Based on Dynamic Cluster Radius

XIONG Lian,YE Jian-guang,LIU Xiao-tong

(New Technology Research Institute of Communication Engineering,Chongqing University of Post and Communications (CQUPT),Chongqing 40065,China)

In wireless sensor network clustering routing algorithm,an uneven clustering algorithm based on dynamic cluster radius (UCDCR) is put forward in view of “hot spot” caused by unbalanced node energy consumption.In clustering stage,the network is divided into different areas,and the condidate cluster head uses the competition radius of cluster to build clusters with different size.So the cluster head can dynamicallychange competition radius of cluster to reserve more energy for data forwarding.The simulation experiments show that the UCDCR algorithm can effectively balance the energy consumption of nodes and prolong the network life cycle compared with EEUC algorithm and CUCRA algorithm.

wireless sensor network; dynamic; cluster radius; uneven clustering

10.3969/j.issn.1003-3114.2017.01.13

熊 煉，葉建光，劉曉彤.基于動(dòng)態(tài)簇半徑的非均勻分簇算法[J].無線電通信技術(shù),2017,43(1):51-55.

2016-10-11

長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃 (IRT1299)(cstc2013yykfA40010)作者簡介:熊 煉(1968—)，男，碩士生導(dǎo)師，主要研究方向：移動(dòng)通信技術(shù)。葉建光(1989—)，男，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)。

TP212.9

A

1003-3114(2017)01-51-5