一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議

1、第30卷第1期2007年1月計(jì)算機(jī)學(xué)報(bào)CHINESEJOURNALOFCOMPUTERSVol.30No.1Jan.2007一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議李成法陳貴海葉懋吳杰1)2)1)1)1)2)(南京大學(xué)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室南京210093)(美國(guó)佛羅里達(dá)大西洋大學(xué)計(jì)算機(jī)科學(xué)與工程系佛羅里達(dá)波卡雷頓33431)摘要在路由協(xié)議中利用分簇技術(shù)可以提高無(wú)線傳感器網(wǎng)絡(luò)的可擴(kuò)展性.當(dāng)簇首以多跳通信的方式將數(shù)據(jù)傳輸至數(shù)據(jù)匯聚點(diǎn)時(shí),靠近匯聚點(diǎn)的簇首由于轉(zhuǎn)發(fā)大量數(shù)據(jù)而負(fù)載過(guò)重,可能過(guò)早耗盡能量而失效,這將導(dǎo)致網(wǎng)絡(luò)分割.該文提出一種新穎的基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)多跳路由協(xié)議.它的核心是

2、一個(gè)用于組織網(wǎng)絡(luò)拓?fù)涞哪芰扛咝У姆蔷鶆蚍执厮惴?其中候選簇首通過(guò)使用非均勻的競(jìng)爭(zhēng)范圍來(lái)構(gòu)造大小不等的簇.靠近匯聚點(diǎn)的簇的規(guī)模小于遠(yuǎn)離匯聚點(diǎn)的簇,因此靠近匯聚點(diǎn)的簇首可以為簇間的數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留能量.模擬實(shí)驗(yàn)結(jié)果表明,該路由協(xié)議有效地平衡了簇首的能量消耗,并顯著地延長(zhǎng)了網(wǎng)絡(luò)的存活時(shí)間.關(guān)鍵詞無(wú)線傳感器網(wǎng)絡(luò);能量高效;非均勻分簇;路由;多跳通信中圖法分類(lèi)號(hào)TP393AnUnevenCluster2BasedRoutingetworksLICheng2Fa1H211WUJie21)2)(StateKeyLSoftwy,NanjingUniversity,Nanjing210093)(Department

3、of,FloridaAtlanticUniversity,BocaRaton,FL33431USA)Abstracttechniquesinroutingprotocolscanincreasethescalabilityofwirelessnetworks.Whenclusterheadstransmittheirdatatothedatasinkviamulti2hopcommunication,theclusterheadsclosertothesinkareburdenedwithheavyrelaytrafficandtendtodieearly,causingnetworkpart

4、itions.Thispaperpresentsanovelunevencluster2basedroutingprotocolforwirelesssensornetworks.ItscoreisanEnergy2EfficientUnevenClustering(EEUC)algorithmfornetworktopologyorganization,inwhichtentativeclusterheadsuseunevencompe2titionrangestoconstructclustersofunevensizes.Theclustersclosertothesinkhavesma

5、llersi2zesthanthosefartherawayfromthesink,thustheclusterheadsclosertothesinkcanpreservesomeenergyfortheinter2clusterdataforwarding.Simulationresultsshowthattheroutingproto2coleffectivelybalancestheenergyconsumptionamongclusterheadsandachievesanobviousim2provementonthenetworklifetime.Keywordswireless

6、sensornetworks;energyefficient;unevenclustering;routing;multi2hopcommunication1引言隨著微電子工藝和無(wú)線通信技術(shù)的飛速發(fā)展,無(wú)線傳感器網(wǎng)絡(luò)的研究越來(lái)越受到人們的重視.傳感器網(wǎng)絡(luò)是由部署在觀測(cè)環(huán)境內(nèi)的大量微型傳感器節(jié)點(diǎn)通過(guò)無(wú)線通信方式組成的一種無(wú)線網(wǎng)絡(luò).組成傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)包括數(shù)據(jù)匯聚點(diǎn)和傳感器節(jié)點(diǎn).收稿日期:2005209227;修改稿收到日期:2006204224.本課題得到國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃項(xiàng)目基金(2006CB303004)、國(guó)家自然科學(xué)基金(60573131,60673154)、江蘇省自然科學(xué)

7、基金(BK2005208)和教育部高校青年教師獎(jiǎng)勵(lì)基金資助.李成法,男,1981年生,碩士研究生,研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò).陳貴海,男,1963年生,教授,博士生導(dǎo)師,研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)計(jì)算、組合數(shù)學(xué)等.E2mail:gchen.葉懋,男,1981年生,碩士研究生,研究方向?yàn)閷?duì)等計(jì)算、傳感器網(wǎng)絡(luò).吳杰,男,1960年生,博士,教授,研究領(lǐng)域?yàn)闊o(wú)線網(wǎng)絡(luò)與移動(dòng)計(jì)算、并行與分布式系統(tǒng)等.© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 28計(jì)算機(jī)學(xué)報(bào)2007年傳感器節(jié)點(diǎn)通常是

8、由能量十分有限的電池供電,而且在部署后難以二次補(bǔ)充能量,因此傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問(wèn)題.所以,傳感器網(wǎng)絡(luò)協(xié)議的首要設(shè)計(jì)目標(biāo)就是要高效地使用傳感器節(jié)點(diǎn)的能量,延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間.傳感器節(jié)點(diǎn)中消耗能量的模塊有傳感器模塊、處理器模塊和無(wú)線通信模塊等,其中無(wú)線通信消耗了大部分的能量1.基于分簇的層次式路由方法在提高網(wǎng)絡(luò)的可擴(kuò)展性方面特別有效.在以分簇方式組織的傳感器網(wǎng)絡(luò)中,傳感器節(jié)點(diǎn)的角色分為簇首和簇成員兩種.簇首作為簇的中心負(fù)責(zé)簇結(jié)構(gòu)的建立,收集簇成員的數(shù)據(jù),經(jīng)融合2處理后發(fā)送給匯聚點(diǎn).由于簇首距離匯聚點(diǎn)的距離一般較遠(yuǎn),已有研究(如文獻(xiàn)3等)表明在簇首與匯聚點(diǎn)之間通信時(shí)采取多跳的方式(即通過(guò)簇

9、首組成的骨干網(wǎng)實(shí)現(xiàn)多跳路由)更有利于節(jié)約能量.然而這種做法帶來(lái)了一個(gè)能量消耗不均衡的問(wèn)題:在這種所有傳感器節(jié)點(diǎn)的數(shù)據(jù)都發(fā)送到匯聚點(diǎn)的“多對(duì)一”數(shù)據(jù)傳輸模式中,數(shù)據(jù)而負(fù)擔(dān)過(guò)重,絡(luò)分割,.(hot“熱區(qū)”器網(wǎng)絡(luò)路由協(xié)議,其核心是一個(gè)能量高效的非均勻分簇(Energy2EfficientUnevenClustering,EEUC)算法4.路由的組織分為簇內(nèi)通信和簇首與匯聚點(diǎn)間通信兩部分:簇內(nèi)通信采用單跳的方式,簡(jiǎn)單易實(shí)現(xiàn);簇首與匯聚點(diǎn)間通信采用多跳的方式,避免長(zhǎng)距離數(shù)據(jù)傳輸造成能量浪費(fèi).EEUC算法利用非均勻的競(jìng)爭(zhēng)半徑,使得靠近匯聚點(diǎn)的簇的成員數(shù)目相對(duì)較小,從而簇首能夠節(jié)約能量以供數(shù)據(jù)轉(zhuǎn)發(fā)使用,達(dá)到

10、均衡簇首能量消耗的目的.此外,在簇首選擇其路由的下一跳節(jié)點(diǎn)時(shí),不僅考慮候選節(jié)點(diǎn)相對(duì)匯聚點(diǎn)的位置,還考慮候選節(jié)點(diǎn)的剩余能量.實(shí)驗(yàn)結(jié)果表明,該路由協(xié)議有效地解決了多跳通信方式下簇首能量消耗不均衡的問(wèn)題,優(yōu)化了網(wǎng)絡(luò)中各節(jié)點(diǎn)的能量消耗,顯著地延長(zhǎng)了網(wǎng)絡(luò)的存活時(shí)間.本文第2節(jié)介紹相關(guān)工作;第3節(jié)給出網(wǎng)絡(luò)的模型,并討論能量消耗的不均衡問(wèn)題;第4節(jié)全面闡述EEUC算法和簇間的多跳路由算法;第5節(jié)對(duì)EEUC算法的性質(zhì)進(jìn)行了分析;第6節(jié)通過(guò)實(shí)驗(yàn)分2相關(guān)工作近年來(lái),研究人員提出了多種傳感器網(wǎng)絡(luò)的分簇協(xié)議5212.Heinzelman等人提出一種稱(chēng)為L(zhǎng)EACH的分簇協(xié)議5.在每個(gè)數(shù)據(jù)收集的周期(一個(gè)周期也稱(chēng)為一輪)

11、開(kāi)始,一小部分節(jié)點(diǎn)隨機(jī)成為簇首.在數(shù)據(jù)傳輸階段,簇首以單跳通信的方式將融合后的數(shù)據(jù)傳輸給匯聚點(diǎn).為了提高簇的生成質(zhì)量,Heinzelman等人又提出了集中式的簇構(gòu)造算法LEACH2C以及考慮節(jié)點(diǎn)能量的算法(本文稱(chēng)其為L(zhǎng)EACH2E)6.Lindsey等人提出的PEGASIS算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)組織為鏈狀,數(shù)據(jù)在鏈上經(jīng)融合處理,最后傳輸至匯聚點(diǎn)7;算法需要知道每個(gè)節(jié)點(diǎn)的位置信息.Dasgupta等人提出一種基于分簇的啟,算法需要知道8.等人提出兩階,10.算法首先根據(jù)節(jié)點(diǎn)的剩余能量來(lái)概率性地選取一些候選簇首,然后以簇內(nèi)部通信代價(jià)的高低來(lái)競(jìng)爭(zhēng)產(chǎn)生最終簇首.與LEACH不同的是,它的簇生成算法需要在簇

12、半徑內(nèi)進(jìn)行多次消息迭代,由此帶來(lái)的通信開(kāi)銷(xiāo)比較顯著.上述的這些協(xié)議均通過(guò)周期性地重新分簇,讓節(jié)點(diǎn)輪流擔(dān)任簇首,來(lái)達(dá)到網(wǎng)絡(luò)中的節(jié)點(diǎn)比較均衡地消耗能量的目的.然而,從均衡節(jié)點(diǎn)的能量消耗以延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間這個(gè)目標(biāo)看,先前的研究主要集中于均衡簇成員節(jié)點(diǎn)之間的能量消耗,沒(méi)有考慮到簇首間的能量消耗均衡問(wèn)題.Soro等人研究了傳感器網(wǎng)絡(luò)多跳路由中的“熱區(qū)”問(wèn)題,并首次提出利用非均勻分簇的思想來(lái)解決這個(gè)“熱區(qū)”問(wèn)題11.文中所假設(shè)的網(wǎng)絡(luò)拓?fù)涫黔h(huán)繞匯聚點(diǎn)的兩層同心圓環(huán),內(nèi)圓環(huán)中的簇首由于靠近匯聚點(diǎn),需要承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)的任務(wù),因此通過(guò)減小它的簇成員數(shù)目來(lái)降低其在簇內(nèi)處理中消耗的能量,為簇首間數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留能量.但是

13、他們考慮的是一個(gè)異構(gòu)網(wǎng)絡(luò),簇首為超級(jí)節(jié)點(diǎn),而且位置是事先計(jì)算好的,無(wú)需動(dòng)態(tài)構(gòu)造簇的操作.在單跳通信的網(wǎng)絡(luò)中,由于簇首距離匯聚點(diǎn)遠(yuǎn)近的差異,也存在簇首負(fù)載不均衡的問(wèn)題.在我們的先前工作EE2CS12中,節(jié)點(diǎn)在選擇簇首時(shí)不是簡(jiǎn)單地選擇距離自身最近的簇首,而是考慮了候選簇首到匯聚點(diǎn)的距離遠(yuǎn)近,構(gòu)造出大小非均勻的簇,均衡簇首的負(fù)載.由于傳感器網(wǎng)絡(luò)與移動(dòng)自組網(wǎng)絡(luò)在應(yīng)用場(chǎng)景上析了該路由協(xié)議的性能;最后是工作總結(jié)和對(duì)未來(lái)工作的展望.© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.

14、 1期李成法等:一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議29有較大差別,需要為傳感器網(wǎng)絡(luò)設(shè)計(jì)優(yōu)化的路由協(xié)議.Intanagonwiwat等人提出的定向擴(kuò)散協(xié)議是一種基于查詢(xún)的路由機(jī)制13.匯聚點(diǎn)發(fā)出查詢(xún)消息,形成反向的從數(shù)據(jù)源到匯聚點(diǎn)的數(shù)據(jù)傳輸梯度.數(shù)據(jù)沿著梯度傳送到匯聚點(diǎn).Schurgers等人提出了定向擴(kuò)散的一個(gè)變種即基于梯度的路由算法GBR,并設(shè)計(jì)了三種動(dòng)態(tài)調(diào)整節(jié)點(diǎn)梯度的策略,以實(shí)現(xiàn)均衡的流量分布14.然而這些查詢(xún)或事件驅(qū)動(dòng)的協(xié)議都不適用于連續(xù)性數(shù)據(jù)收集場(chǎng)景下的“多對(duì)一”數(shù)據(jù)傳輸,因此也不適合在簇首間進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)使用.與已有的研究工作相比較,本文提出的分簇協(xié)議具有下列創(chuàng)新之處:(1)首

15、次提出一個(gè)非均勻分簇的分布式算法,來(lái)解決傳感器網(wǎng)絡(luò)多跳路由中的“熱區(qū)”問(wèn)題.(2)不同于LEACH,簇首通過(guò)局部競(jìng)爭(zhēng)的方式產(chǎn)生,而且不同于HEED,算法無(wú)需迭代.(3)不同于EECS,通過(guò)選舉出非均勻分布的簇首,節(jié)點(diǎn)組成了Voronoi圖15結(jié)構(gòu)的簇.(4)為簇首間進(jìn)行多跳數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)計(jì)了一個(gè)能量高效的路由算法.ETx(l,d)=2lEelec+lfsd,4lEelec+lmpd,d<doddo(1)其中Eelec表示發(fā)射電路損耗的能量.若傳輸距離小于閾值do,功率放大損耗采用自由空間模型;當(dāng)傳輸距離大于等于閾值do時(shí),采用多路徑衰減模型.mp分別為這兩種模型中功率放大所需的能量.fs、節(jié)

16、點(diǎn)接收l(shuí)比特的數(shù)據(jù)消耗的能量為(2)ERx(l)=lEelec數(shù)據(jù)融合也消耗一定的能量,用EDF表示融合單位比特?cái)?shù)據(jù)消耗的能量.我們假設(shè)鄰近節(jié)點(diǎn)采集的數(shù)據(jù)具有較高的冗余度,簇首可以將其成員的數(shù)據(jù)融合成一個(gè)長(zhǎng)度固定的數(shù)據(jù)包,然后發(fā)送給匯聚點(diǎn).312能量消耗不均衡問(wèn)題,就是要,延長(zhǎng)中,(有時(shí))兩部分.當(dāng)簇成員與簇首之間傳,可以采用單跳通信的方式,這樣易于調(diào)度各成員的數(shù)據(jù)傳輸.當(dāng)簇首向匯聚點(diǎn)進(jìn)行長(zhǎng)距離數(shù)據(jù)傳輸時(shí),已有研究表明采用多跳路由的方式更為實(shí)際,且顯著降低能量消耗.本文將簇首節(jié)點(diǎn)組成一個(gè)多跳路由的骨干網(wǎng).靠近匯聚點(diǎn)的簇首在把自身數(shù)據(jù)傳輸給匯聚點(diǎn)的同時(shí),還轉(zhuǎn)發(fā)來(lái)自遠(yuǎn)離匯聚點(diǎn)的簇首的數(shù)據(jù).在每一輪

17、中,簇首消耗的能量包括簇內(nèi)部處理和簇之間處理兩部分.已有的分簇算法通常都是構(gòu)造大小均勻的簇,以均衡簇首在簇內(nèi)部進(jìn)行數(shù)據(jù)處理時(shí)消耗的能量.然而由于靠近匯聚點(diǎn)的簇首承擔(dān)了額外的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),因此其在簇首間通信的過(guò)程中將消耗更多的能量.所以,若采用均勻分簇的方式,在每一輪中,靠近匯聚點(diǎn)的簇首將消耗更多的能量,造成節(jié)點(diǎn)過(guò)早能量耗盡而失效,降低了網(wǎng)絡(luò)的存活時(shí)間.在傳統(tǒng)的同構(gòu)網(wǎng)絡(luò)分簇協(xié)議中,通過(guò)周期性地重新選擇簇首(如LEACH、HEED),可以平衡簇首與簇成員節(jié)點(diǎn)之間的能量消耗,但不能解決上述的“熱區(qū)”問(wèn)題.以節(jié)點(diǎn)的剩余能量為依據(jù)選擇簇首的方法(如EECS)也不能完全解決這個(gè)問(wèn)題,因?yàn)樗皇窃诰W(wǎng)絡(luò)的局部

18、比較節(jié)點(diǎn)剩余能量,無(wú)法從整體上協(xié)調(diào)節(jié)點(diǎn)的能量消耗以解決“熱區(qū)”問(wèn)題.可以認(rèn)為上述兩種方法都是以被動(dòng)的方式來(lái)均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗,即在網(wǎng)絡(luò)中出現(xiàn)能量消耗不均衡之后方采取措施來(lái)均衡能量消耗.在結(jié)合這兩種技術(shù)3在這一部分,然后闡述用非均勻分簇機(jī)制來(lái)解決“熱區(qū)”問(wèn)題的思想.311網(wǎng)絡(luò)模型考慮一個(gè)由N個(gè)隨機(jī)部署的傳感器節(jié)點(diǎn)形成的網(wǎng)絡(luò),其應(yīng)用場(chǎng)景為周期性的數(shù)據(jù)收集.用si表示第i個(gè)節(jié)點(diǎn),相應(yīng)的節(jié)點(diǎn)集合為S=s1,s2,sN,|S|=N.我們假設(shè):(1)數(shù)據(jù)匯聚點(diǎn)位于一個(gè)方形觀測(cè)區(qū)域A的外側(cè).傳感器節(jié)點(diǎn)和匯聚點(diǎn)DS在部署后均不再發(fā)生位置移動(dòng).(2)所有節(jié)點(diǎn)都是同構(gòu)的,具備數(shù)據(jù)融合的功能.每個(gè)節(jié)點(diǎn)都有一個(gè)

19、唯一的標(biāo)識(shí)(ID).(3)根據(jù)接收者的距離遠(yuǎn)近,節(jié)點(diǎn)可以自由調(diào)整其發(fā)射功率以節(jié)約能量消耗.(4)鏈路是對(duì)稱(chēng)的.若已知對(duì)方發(fā)射功率,節(jié)點(diǎn)可以根據(jù)接收信號(hào)的強(qiáng)度RSSI計(jì)算出發(fā)送者到自己的近似距離16.我們采用與文獻(xiàn)6相同的無(wú)線通信能量消耗模型.節(jié)點(diǎn)發(fā)射l比特的數(shù)據(jù)到距離為d的位置,消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成,即© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 30計(jì)算機(jī)學(xué)報(bào)2007年的基礎(chǔ)上,本文創(chuàng)新地設(shè)計(jì)了一種基于非均勻分簇的層次式路由協(xié)議.與

20、前人的方法相比,本文提出的方法以主動(dòng)的方式來(lái)均衡網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗,特別是均衡簇首的能量消耗.規(guī)則1.在競(jìng)選過(guò)程中,若候選簇首si宣布其競(jìng)選獲勝,則在si的競(jìng)爭(zhēng)半徑Rc內(nèi)的所有候選簇首均不能成為最終簇首,需要退出競(jìng)選過(guò)程.算法1.EEUC的簇首競(jìng)選算法.RAND(0,1)If<TthenbeTentativeHeadtrueEndifIfbeTentativeHead=truethenBroadcastCOMPETE_HEAD_MSG(ID,Rc,RE)ElseExitEndifOnreceivingaCOMPETE_HEAD_MSGformsj Ifd(si,sj)<sj.

21、Rcord(si,sj)<si.Rcthen Addsjtosi.SCH Endif beIjsi.H.E>sj.REthenFINAL_HEAD_MSG(ID)andthenexit4基于非均勻分簇的路由機(jī)制在網(wǎng)絡(luò)部署階段,匯聚點(diǎn)需要用一個(gè)給定的發(fā)送功率向網(wǎng)絡(luò)內(nèi)廣播一個(gè)信號(hào).每個(gè)傳感器節(jié)點(diǎn)在接收到此信號(hào)后,根據(jù)接收信號(hào)的強(qiáng)度計(jì)算它到匯聚點(diǎn)的近似距離.獲得這個(gè)距離不僅有助于傳感器節(jié)點(diǎn)向匯聚點(diǎn)傳輸數(shù)據(jù)時(shí)選擇合適的發(fā)送功率以節(jié)約能量消耗,而且它還是算法構(gòu)造大小非均勻的簇的必需信息之一.本節(jié)分兩部分描述非均勻分簇算法EEUC和簇首間的多跳路由協(xié)議.圖1給出本文提出的基于非均勻分簇的路由協(xié)

22、議的示意,其中大小不等的圓表示簇首節(jié)點(diǎn)的大小非均勻的競(jìng)爭(zhēng)范圍,帶箭頭的粗線表示簇首間的多跳數(shù)據(jù)傳輸.| Endif OnreceivingaFINAL_HEAD_MSGformsj Ifsjsi.SCHthenµ BroadcastQUIT_ELECTION_MSG(ID)andthenexitµ Endif圖1基于非均勻分簇的路由協(xié)議µ OnreceivingaQUIT_ELECTION_MSGformsjµ Ifsjsi.SCHthenµ Removesjfromsi.SCHµ Endifµ Endwhile411EEU

23、C算法EEUC是一個(gè)分布式的競(jìng)爭(zhēng)算法,以節(jié)點(diǎn)的剩余能量為主要比較依據(jù).在采用分簇的傳感器網(wǎng)絡(luò)中,簇首是最重要的節(jié)點(diǎn).它不僅需要管理所屬簇成員,協(xié)調(diào)成員的數(shù)據(jù)傳輸,還要融合簇成員收集的數(shù)據(jù),再將處理后的數(shù)據(jù)發(fā)送給匯聚點(diǎn).由于簇首的負(fù)擔(dān)較重,EEUC算法在每個(gè)數(shù)據(jù)收集周期的開(kāi)始重新構(gòu)造簇,選擇剩余能量較高的節(jié)點(diǎn)作為簇首.下面闡述競(jìng)爭(zhēng)選取簇首的算法.算法1給出了任意節(jié)點(diǎn)si在簇首競(jìng)選過(guò)程中執(zhí)行的算法偽碼.下面是對(duì)算法1的具體解釋.首先,依概率在網(wǎng)絡(luò)中選出部分節(jié)點(diǎn)成為候選簇首,參與競(jìng)選.普通節(jié)點(diǎn)成為候選簇首的概率為T(mén),它是一個(gè)預(yù)先設(shè)置的閾值.未參與競(jìng)選的節(jié)點(diǎn)進(jìn)入睡眠狀態(tài),直到簇首競(jìng)選過(guò)程結(jié)束.令si為

24、任意的一個(gè)候選簇首.si根據(jù)自身到匯聚點(diǎn)的距離信息計(jì)算它的競(jìng)爭(zhēng)區(qū)域,區(qū)域的半徑記作Rc.下面定義候選簇首之間競(jìng)爭(zhēng)的規(guī)則圖2給出了一張候選簇首的拓?fù)涫疽鈭D,其中大小不同的圓代表候選簇首的競(jìng)爭(zhēng)區(qū)域.按照規(guī)則1的要求,s1和s2可以同時(shí)成為最終簇首,而s3和s4則不能同時(shí)成為最終簇首,因?yàn)閟4位于s3的競(jìng)爭(zhēng)區(qū)域內(nèi)部.如前文所分析的,算法的目標(biāo)是讓靠近匯聚點(diǎn)的簇的成員較少,使其簇首能夠預(yù)留部分能量供簇首間通信使用.因此,靠近匯聚點(diǎn)的候選簇首的競(jìng)爭(zhēng)半徑應(yīng)該較小.亦即,隨著候選簇首到匯聚點(diǎn)距離的減小,其競(jìng)爭(zhēng)半徑應(yīng)該隨之減小.記候選簇首的競(jìng)爭(zhēng)半徑的最大取值為R0c.算法需要控制競(jìng)爭(zhēng)半徑的取值范圍,使得距離匯

25、聚點(diǎn)最近的節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑為(1-c)R0c,其中c是用于控制取值范圍的參數(shù),在01之間取值.候選簇首si確定其競(jìng)爭(zhēng)半徑si.Rc的計(jì)算公式如下:© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1期李成法等:一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議31Rc=1-cdmax-dminRc(3)中的一個(gè)節(jié)點(diǎn),則si將sj從其鄰簇首集合中刪除.算法1過(guò)程結(jié)束后,之前未參與競(jìng)選的節(jié)點(diǎn)從睡眠狀態(tài)喚醒,接著競(jìng)選產(chǎn)生的簇首向全網(wǎng)廣播其競(jìng)選獲勝的消息CH_ADV_MSG.普通節(jié)點(diǎn)

26、選擇簇內(nèi)通信代價(jià)最小亦即接收信號(hào)強(qiáng)度最大的簇首,發(fā)送加入消息JOIN_CLUSTER_MSG通知該簇首.這樣,網(wǎng)絡(luò)中的節(jié)點(diǎn)組成了Voronoi圖16結(jié)構(gòu)的簇.接下來(lái)進(jìn)入簇內(nèi)部的數(shù)據(jù)傳輸階段.簇首構(gòu)建TDMA調(diào)度,然后簇成員向簇首傳輸數(shù)據(jù).本文采其中dmax和dmin分別代表網(wǎng)絡(luò)中的節(jié)點(diǎn)到匯聚點(diǎn)的距離的最大值和最小值,d(si,DS)代表節(jié)點(diǎn)si到匯聚點(diǎn)的距離.競(jìng)爭(zhēng)半徑與節(jié)點(diǎn)到匯聚點(diǎn)的距離呈線性遞減關(guān)系.舉個(gè)例子,取c=1/3時(shí),競(jìng)爭(zhēng)半徑的取值范圍是2/3R0cRc.用與LEACH相同的組織方式,在此不再贅述.412簇首間多跳路由協(xié)議在簇首將數(shù)據(jù)傳輸?shù)絽R聚點(diǎn)這個(gè)階段,簇首先對(duì)簇成員的數(shù)據(jù)進(jìn)行融合

27、處理,然后將數(shù)據(jù)以多跳通信的方式發(fā)送至匯聚點(diǎn).圖2候選簇首的競(jìng)爭(zhēng)區(qū)域獨(dú)特的“,移動(dòng)自組網(wǎng)絡(luò)中,.(如PEGASIS7)提出的傳感器網(wǎng)絡(luò)的多跳路由協(xié)議中,中繼節(jié)點(diǎn)對(duì)收到的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合,然后再繼續(xù)發(fā)送.本文假設(shè)數(shù)據(jù)的冗余度有限,來(lái)自不同簇的數(shù)據(jù)無(wú)法進(jìn)一步融合,中繼簇首節(jié)點(diǎn)只是簡(jiǎn)單轉(zhuǎn)發(fā)來(lái)自其它簇首的數(shù)據(jù),如圖1所示.引入一個(gè)閾值TD_MAX.若簇首到匯聚點(diǎn)的距離小于TD_MAX,則它直接與匯聚點(diǎn)進(jìn)行通信;否則應(yīng)該盡量使用多跳路由的方式將數(shù)據(jù)傳送給匯聚點(diǎn).在路由算法開(kāi)始時(shí),每個(gè)簇首以相同的功率向全網(wǎng)廣播一條消息NODE_STATE_MSG,包含其ID、當(dāng)前剩余能量和它到匯聚點(diǎn)的距離.簇首si收每個(gè)

28、候選簇首維護(hù)一個(gè)鄰簇首集合SCH,在這最終簇首.候選簇首sisi規(guī)則1,其定義如下.定義1.在簇首競(jìng)選算法中,候選簇首si的鄰簇首集合si.SCH為si.SCH=sj|sj是候選簇首,且d(si,sj)<max(si.Rc,sj.Rc).在此算法中,每個(gè)節(jié)點(diǎn)均以同樣的功率發(fā)送廣播消息,為了節(jié)約能量,這個(gè)廣播半徑設(shè)為R0c即可(這保證了節(jié)點(diǎn)能夠與鄰簇首集合內(nèi)的所有節(jié)點(diǎn)正常通信).在算法1的第56行,每個(gè)競(jìng)選節(jié)點(diǎn)廣播競(jìng)選消息COMPETE_HEAD_MSG,消息的內(nèi)容為節(jié)點(diǎn)的ID、競(jìng)爭(zhēng)半徑Rc和當(dāng)前剩余能量RE.在第1013行,節(jié)點(diǎn)根據(jù)收到的廣播消息構(gòu)建其鄰簇首集合SCH.當(dāng)SCH構(gòu)建完成后

29、,在1426行,節(jié)點(diǎn)做出其是否能擔(dān)任簇首的決策.節(jié)點(diǎn)需要等待其鄰簇首集合中所有能量比它大的節(jié)點(diǎn)先做出決策,然后才能確定自身是否能擔(dān)任簇首.在1517行,一旦si發(fā)現(xiàn)它的剩余能量比其鄰簇首集合中的節(jié)點(diǎn)的剩余能量都高,則它將贏得競(jìng)選,并廣播獲勝消息FINAL_HEAD_MSG以通知它的鄰簇首.在1821行,如果si收到來(lái)自sj的獲勝消息,且sj是si.SCH中的一個(gè)節(jié)點(diǎn),則si立即退出競(jìng)選,并廣播消息QUIT_ELECTION_MSG通知它的鄰簇首.在2225行,如果si收到來(lái)自sj的退出消息,且sj是si.SCH到簇首sj廣播的消息后,可以計(jì)算出它們之間的近似距離.下文敘述當(dāng)d(si,DS)TD

30、_MAX時(shí),簇首si的路由選擇策略.Kawadia等在文獻(xiàn)17指出,選擇鄰近的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)有利于減少通信干擾.本文將路由候選節(jié)點(diǎn)的選取范圍限制在比其自身更鄰近匯聚點(diǎn)的一個(gè)區(qū)域內(nèi).定義2.在簇首間多跳路由構(gòu)建過(guò)程中,簇首si的路由候選節(jié)點(diǎn)集合si.RCH為若節(jié)點(diǎn)的剩余能量相等,則以節(jié)點(diǎn)的ID作為次比較依據(jù).在LEACH中,簇首節(jié)點(diǎn)向全網(wǎng)范圍廣播此消息,以使其它節(jié)點(diǎn)能夠在全網(wǎng)范圍內(nèi)選擇位置最佳的簇加入.本文采用相同方法.© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserve

31、d. 32計(jì)算機(jī)學(xué)報(bào)2007年si.RCH=sj|d(sj,DS)<d(si,DS)且d(si,sj)ksi.Rc,其中k是使得si.RCH非空的最小整數(shù)(若不存在使si.RCH非空的整數(shù),則定義si.RCH為空集,且si將其數(shù)據(jù)以單跳方式直接傳輸至匯聚點(diǎn)).si從其路由候選節(jié)點(diǎn)集合RCH中選擇一個(gè)作為數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn).選擇剩余能量較多的節(jié)點(diǎn)作為數(shù)據(jù)中繼節(jié)點(diǎn)有利于均衡能量消耗,避免有些節(jié)點(diǎn)因?yàn)槟芰肯倪^(guò)多而較早死亡.文獻(xiàn)14中提出的GBR協(xié)議亦包含一種以剩余能量為依據(jù)來(lái)調(diào)整節(jié)點(diǎn)梯度的數(shù)據(jù)分發(fā)策略.但是單純地考慮剩余能量可能導(dǎo)致網(wǎng)絡(luò)的整體能量利用效率下降.假設(shè)si選擇sj作為其數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn).為

32、簡(jiǎn)化問(wèn)題分析,假設(shè)通信采用自由空間模型,并假設(shè)sj將數(shù)據(jù)直接傳輸至匯聚點(diǎn).則為了傳輸l比特的數(shù)據(jù)至匯聚點(diǎn),si和sj消耗的能量為E22hop=ETx(l,d(si,sj)+ERx(l)+ETx(l,d(sj,DS)2=l(Eelec+fsd(si,sj)+lEelec+2l(Eelec+fsd(sj,DS)22=3lEelec+lfs(d(si,sj)+d(sj,DS).條消息FINAL_HEAD_MSG以宣布其競(jìng)選成功,或者廣播一條消息QUIT_ELECTION_MSG以宣布其退出競(jìng)選.假設(shè)共選出k個(gè)簇首,則它們廣播k條CH_ADV_MSG消息,而N-K個(gè)簇成員廣播N-K條JOIN_CLUS

33、TER_MSG消息.因此,網(wǎng)絡(luò)中總的消息開(kāi)銷(xiāo)為N×T+N×T+k+N-k=(2T+1)N所以消息復(fù)雜度為O(N).證畢.性質(zhì)1說(shuō)明EEUC算法的消息開(kāi)銷(xiāo)較小,能量高效.HEED的分簇算法也是消息驅(qū)動(dòng)的,其消息交換次數(shù)的上界為Niter×N,Niter是消息迭代的次數(shù).因?yàn)镋EUC避免了消息迭代,因此消息開(kāi)銷(xiāo)低于HEED.由性質(zhì)1的證明可知,閾值T決定算法的消息開(kāi)銷(xiāo).選擇合適的T節(jié)點(diǎn)參與競(jìng)選過(guò)程,.關(guān)于12中通過(guò)實(shí)驗(yàn)給.算法中的參數(shù)R0c和c的取.簇的成員數(shù)目之間的非均勻程度由c決定.c的值越大,候選簇首的競(jìng)爭(zhēng)半徑的差異越大,因此簇的成員數(shù)目間的差異越明顯.而當(dāng)c等

34、于0時(shí),候選簇首的競(jìng)爭(zhēng)半徑相同,算法將生成大小均勻的簇.算法中所生成簇的數(shù)目由R0c和c共同決定.固定c,當(dāng)Rc增大時(shí),每個(gè)候選簇首的由上式可知,d2(si,sj)+d2(sj,)消耗的高低.定義3.sisj,帶來(lái)22(4)Erelay=d(si,sj)+d(sj,DS)直觀上看,若sj位于si與匯聚點(diǎn)之間,則有利于節(jié)約能量,而這時(shí)鏈路的Erelay也較小.為了綜合考慮節(jié)點(diǎn)的剩余能量和鏈路的能量開(kāi)銷(xiāo)指標(biāo)Erelay這兩個(gè)參數(shù),本文的路由策略為:si從RCH中Erelay最小的兩個(gè)節(jié)點(diǎn)中,選擇剩余能量最高的節(jié)點(diǎn)作為其路由的下一跳節(jié)點(diǎn).在路由方式確定之后,簇首節(jié)點(diǎn)組成了一棵以匯聚點(diǎn)為根節(jié)點(diǎn)的樹(shù),數(shù)

35、據(jù)沿著匯聚點(diǎn)的方向在邊上傳輸.競(jìng)爭(zhēng)半徑隨之增大,因此所生成的簇的數(shù)目隨之減小;固定R0c,當(dāng)c增大時(shí),每個(gè)候選簇首的競(jìng)爭(zhēng)半徑隨之減小,因此所生成的簇的數(shù)目隨之增加.R0c和c的優(yōu)化取值可以?xún)?yōu)化網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗,延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間.本文致力于設(shè)計(jì)非均勻分簇的算法,用理論化的方法選擇最優(yōu)的參數(shù)還在進(jìn)一步的研究之中.在算法1中,候選節(jié)點(diǎn)需要等待其鄰簇首集合中所有能量比它大的節(jié)點(diǎn)先做出決策,然后才能確定自身能否擔(dān)任簇首.這要求算法確定一個(gè)全局一致的等待時(shí)間,超過(guò)此時(shí)間后算法終止.以圖3所示的網(wǎng)絡(luò)拓?fù)錇槔?分析影響等待時(shí)間的因素.在圖3中,假設(shè)5個(gè)節(jié)點(diǎn)s1s5的剩余能量依次遞增.因此下列事件依次先后

36、發(fā)生:s5宣布其成為簇首,s4退出競(jìng)選,s3宣布其成為簇首,s2退出競(jìng)選,s1宣布其成為簇首.算法從開(kāi)始到結(jié)束共持續(xù)了4條消息的傳遞時(shí)間.這個(gè)例子說(shuō)明算法需要等待的時(shí)間由網(wǎng)絡(luò)中若si.RCH僅含一個(gè)節(jié)點(diǎn),則無(wú)條件選擇其作為下一跳節(jié)點(diǎn).5EEUC的分析這一節(jié)給出非均勻分簇算法EEUC的一些分析和說(shuō)明.該算法是消息驅(qū)動(dòng)的,因此首先來(lái)分析它的消息復(fù)雜度.性質(zhì)1.在整個(gè)網(wǎng)絡(luò)中,EEUC算法的消息復(fù)雜度為O(N).證明.在算法開(kāi)始,有N×T個(gè)節(jié)點(diǎn)成為候選簇首而參與競(jìng)選,共廣播N×T條COMPETE_HEAD_MSG消息.然后,每個(gè)候選簇首或者廣播一© 1994-2009 C

37、hina Academic Journal Electronic Publishing House. All rights reserved. 1期李成法等:一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議33候選節(jié)點(diǎn)構(gòu)成的單調(diào)能量鏈的最大長(zhǎng)度決定.因?yàn)楣?jié)點(diǎn)的剩余能量分布呈現(xiàn)隨機(jī)性,所以這條鏈越長(zhǎng),其出現(xiàn)的概率越低.在文獻(xiàn)18中,Basagni研究了移動(dòng)自組網(wǎng)中一個(gè)分簇算法中類(lèi)似的問(wèn)題,并指出等待時(shí)間與網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān),而與網(wǎng)絡(luò)的能量拓?fù)溆嘘P(guān).在本算法的實(shí)現(xiàn)中,我們將等待時(shí)間設(shè)為傳遞5次消息所需的時(shí)間,并且發(fā)現(xiàn)所有候選節(jié)點(diǎn)在這段時(shí)間內(nèi)都能正常做出競(jìng)選決策.這說(shuō)明EEUC分簇算法的時(shí)間開(kāi)銷(xiāo)也較小.

38、實(shí)驗(yàn)中所用的參數(shù)如表2所示,其中能量消耗模型相關(guān)的參數(shù)取自文獻(xiàn)6.除非特別指出,本協(xié)議的參數(shù)設(shè)置為T(mén)=014,R0c=90m,c=015,TD_MAX=140m.其它協(xié)議中的參數(shù)通過(guò)運(yùn)行多次實(shí)驗(yàn)來(lái)找出其最優(yōu)取值.表2實(shí)驗(yàn)參數(shù)參數(shù)網(wǎng)絡(luò)覆蓋區(qū)域數(shù)據(jù)匯聚點(diǎn)位置N取值(0,0)(200,200)m(100,250)m傳感器節(jié)點(diǎn)初始能量EelecfsmpdoEDF數(shù)據(jù)包大小400015J50nJ/bit10pJ/(bitm2)010013pJ/(bitm4)87m5nJ/(bitsignal)4000bits圖3由5個(gè)節(jié)點(diǎn)構(gòu)成的鏈狀拓?fù)?11簇首的特征6實(shí)驗(yàn)結(jié)果及分析我們用C簇算法EEUC.先研究EEU

39、C,然后,假設(shè)采用理想的MAC協(xié)議,.實(shí)驗(yàn)中統(tǒng)計(jì)傳感器節(jié)點(diǎn)接收數(shù)據(jù)、融合數(shù)據(jù)和發(fā)送數(shù)據(jù)所消耗的能量,計(jì)算網(wǎng)絡(luò)的存活時(shí)間(用輪數(shù)表示),來(lái)分析協(xié)議的能量效率.為了證明本文提出的路由協(xié)議的能量高效,我們將EEUC與LEACH、LEACH2E、HEED和HEED2M4種基于分簇的路由協(xié)議進(jìn)行比較.為便于下文的分析,表1對(duì)這5種協(xié)議的特征進(jìn)行了概括.在LEACH2E中,每個(gè)節(jié)點(diǎn)需要估計(jì)當(dāng)前網(wǎng)絡(luò)中所有節(jié)點(diǎn)的剩余能量之和;本文的實(shí)現(xiàn)方法是在每一輪的結(jié)束,簇成員將自己的剩余能量匯報(bào)給簇首,簇首將所有簇成員(包括自身)剩余能量之和匯報(bào)給匯聚點(diǎn),然后匯聚點(diǎn)計(jì)算整個(gè)網(wǎng)絡(luò)的能量和,并廣播至所有節(jié)點(diǎn).表15種協(xié)議的特

40、征概括協(xié)議LEACHLEACH2EHEEDHEED2MEEUC分簇算法選取的R0c.圖4顯示了c簇首的數(shù)目與R0c之間的關(guān)系.,即競(jìng)爭(zhēng)半徑越小,算法生成的簇首的數(shù)目越大.在圖中,c=015時(shí)對(duì)應(yīng)的曲線高于c=0時(shí)對(duì)應(yīng)的曲線.這是因?yàn)楫?dāng)R0c固定時(shí),c的增大導(dǎo)致候選簇首的競(jìng)爭(zhēng)半徑變小,因此簇首的數(shù)目增大.圖4EEUC生成的簇首的數(shù)目接著說(shuō)明EEUC分簇算法的穩(wěn)定性.在網(wǎng)絡(luò)拓?fù)涔潭ǖ那闆r下,一個(gè)穩(wěn)定的分簇協(xié)議應(yīng)該生成數(shù)目比較一致的簇首,來(lái)優(yōu)化網(wǎng)絡(luò)的能量消耗.文獻(xiàn)6推導(dǎo)了單跳網(wǎng)絡(luò)中最優(yōu)簇首數(shù)目的近似計(jì)算公式.從每種分簇協(xié)議的模擬過(guò)程中隨機(jī)選出100輪,統(tǒng)計(jì)所生成的簇首個(gè)數(shù)的分布情況,結(jié)果見(jiàn)圖5.由在

41、簇首與匯聚點(diǎn)之間數(shù)據(jù)傳輸?shù)碾A段,文獻(xiàn)10中HEED簇首選取算法簇首間通信方式完全隨機(jī)單跳考慮節(jié)點(diǎn)能量,隨機(jī)單跳考慮節(jié)點(diǎn)能量及簇內(nèi)通信代價(jià),單跳局部競(jìng)爭(zhēng)考慮節(jié)點(diǎn)能量及簇內(nèi)通信代價(jià),局部競(jìng)爭(zhēng)考慮節(jié)點(diǎn)能量,簇首分布非均勻,局部競(jìng)爭(zhēng)多跳多跳使用單跳通信的方式,而在文獻(xiàn)19中使用了多跳通信的方式,稱(chēng)后者為HEED2M.這是二者的唯一區(qū)別.© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 34計(jì)算機(jī)學(xué)報(bào)2007年圖可見(jiàn),每種協(xié)議生成的簇首的數(shù)目都有一個(gè)期望值,它是協(xié)議在此場(chǎng)景下

42、最優(yōu)的簇首數(shù)目.LEACH和LEACH2E的簇首數(shù)目的波動(dòng)范圍比較大,這是因?yàn)長(zhǎng)EACH和LEACH2E單純性地采用隨機(jī)數(shù)與閾值的機(jī)制產(chǎn)生簇首,因此簇首的數(shù)目變化比較明顯.HEED和EEUC的簇首數(shù)目非常集中于期望值,這是因?yàn)镠EED和EEUC均采用了候選簇首在局部區(qū)域進(jìn)行競(jìng)爭(zhēng)的方法,有效地控制了算法所生成的簇首的數(shù)目.值得注意的是,EEUC生成的簇首數(shù)目多于HEED生成的簇首數(shù)目,這是因?yàn)镋EUC構(gòu)造大小非均勻的簇,在靠近匯聚點(diǎn)的區(qū)域產(chǎn)生更多的簇首.總的來(lái)說(shuō),EEUC通過(guò)簡(jiǎn)單的競(jìng)爭(zhēng)算法生成了數(shù)目穩(wěn)定的簇,可靠性好.圖5各種協(xié)議生成的簇首數(shù)目分布統(tǒng)計(jì)612能量效率由于簇首消耗的能量占網(wǎng)絡(luò)中能量

43、消耗的最主要部分,因此首先比較5種協(xié)議所生成的簇首在一輪中所消耗的能量之和.從實(shí)驗(yàn)中隨機(jī)選取10,統(tǒng)計(jì)各輪中所有簇首消耗的能量,6.圖6,發(fā)現(xiàn)EEUC和H最低,顯著降低了能量消耗.LEACH和LEACH2E的簇首消耗的能量最高,不僅因?yàn)樗鼈儾捎脝翁ㄐ诺姆绞綄?shù)據(jù)發(fā)送至匯聚點(diǎn),而且如圖5所示,它們構(gòu)造的簇首的數(shù)量略多于HEED,與匯聚點(diǎn)通信的次數(shù)增大,導(dǎo)致能量消耗增大.另一方面,LEACH和LEACH2E都沒(méi)有控制簇首在網(wǎng)絡(luò)中的分布,而且其次研究5況.,提高能量效,.圖7顯示了在隨機(jī)選取的,.從圖中明顯地看出,EEUC的方差最低而且最穩(wěn)定,因此最好地均衡了簇首的能量消耗.LEACH、LEACH

44、2E和HEED2M的方差比較接近,HEED的方差最高,而且它們都有明顯的波動(dòng).這說(shuō)明它們都沒(méi)有采取有效的策略均衡簇首的能量消耗.在HEED中,某些簇可能只含有一個(gè)節(jié)點(diǎn)即簇首自身,因此導(dǎo)致簇首的負(fù)載不均衡,能量消耗的差異比較大.簇首的數(shù)量不夠穩(wěn)定,因此簇首消耗的能量之和有較明顯的波動(dòng).EEUC和HEED2M均克服了LEACH和LEACH2E的這些不足之處,降低了能量消耗.圖7簇首消耗的能量的方差圖6簇首消耗的能量之和本文的核心思想是利用非均勻分簇的思想來(lái)解決“熱區(qū)”問(wèn)題,延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間.現(xiàn)在來(lái)驗(yàn)證這種方法的有效性.在前一節(jié)已經(jīng)指出,簇大小的非均勻程度由c決定.我們?cè)趯?shí)驗(yàn)中從0到1變化c的取值

45、,觀察網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡的時(shí)間隨之變化的情況,結(jié)果見(jiàn)圖8.當(dāng)c等于0時(shí),算法生成大小均勻的簇.當(dāng)c從0增大到015的過(guò)程中,非均勻分簇© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1期李成法等:一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議35的算法逐漸平衡節(jié)點(diǎn)的能量消耗,因此網(wǎng)絡(luò)的存活時(shí)間持續(xù)增長(zhǎng).而當(dāng)c大于015后,網(wǎng)絡(luò)的存活時(shí)間逐漸下降,這是因?yàn)樗惴óa(chǎn)生的簇首的數(shù)目逐漸增加,增大了網(wǎng)絡(luò)的能量消耗.因此,當(dāng)其它參數(shù)確定后,存在一個(gè)最優(yōu)的c的取值.在圖8中,當(dāng)c

46、等于015左右時(shí),網(wǎng)絡(luò)的存活時(shí)間最長(zhǎng).仍有較大差距,這是因?yàn)樗鼪](méi)有考慮簇首的能量消耗均衡,造成部分節(jié)點(diǎn)過(guò)早失效.總結(jié)實(shí)驗(yàn)結(jié)果,本文提出的基于非均勻分簇的路由協(xié)議具有以下優(yōu)點(diǎn):(1)分簇算法穩(wěn)定,所生成簇的數(shù)目波動(dòng)小;(2)能量消耗低,且有效平衡了簇首的能量消耗;(3)顯著延長(zhǎng)了網(wǎng)絡(luò)的存活時(shí)間.總之,用網(wǎng)絡(luò)的存活時(shí)間這一重要指標(biāo)來(lái)衡量,其性能明顯優(yōu)于其它四種分簇協(xié)議.7結(jié)論和進(jìn)一步的工作本文提出了一種新穎的基于分簇的傳感器網(wǎng)絡(luò)路由協(xié)議,其核心思想是利用一個(gè)能量高效的非均勻分簇算法EEUC將網(wǎng)絡(luò)組織成大小非均勻的簇,“熱區(qū)”問(wèn)圖8網(wǎng)絡(luò)存活時(shí)間隨c變化的趨勢(shì)題.,耗.,雖然、低成本的要求,但因?yàn)殡姶?/p>

47、波的不穩(wěn)定,可能產(chǎn)生一定的測(cè)距誤差.本文致力于設(shè)計(jì)能量高效的路由協(xié)議,未能對(duì)算法中的參數(shù)優(yōu)化取值進(jìn)行詳細(xì)分析.下一步工作將改進(jìn)測(cè)距方法,并研究算法參數(shù)的最優(yōu)取值.致謝作者特別感謝審稿人提出的寶貴意見(jiàn)!參1最后來(lái)比較各種分簇協(xié)議對(duì)網(wǎng)絡(luò)存活時(shí)間的影響.圖9顯示了網(wǎng)絡(luò)中存活的節(jié)點(diǎn)數(shù)目隨時(shí)間變化的情況.顯然,后一個(gè)節(jié)點(diǎn)死亡的時(shí)間,4議.,跨度.EEUC不僅顯著地延長(zhǎng)了網(wǎng)絡(luò)的存活時(shí)間,而且時(shí)間跨度也遠(yuǎn)小于其它協(xié)議,這說(shuō)明EEUC很好地均衡了網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗.LEACH2E在選取簇首時(shí)雖然考慮了節(jié)點(diǎn)的剩余能量,但由于傳播能量消息帶來(lái)的開(kāi)銷(xiāo),其性能還略差于LEACH.HEED的第一個(gè)節(jié)點(diǎn)死亡時(shí)間明顯

48、早于LEACH,但最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間晚于LEACH,這表明HEED并沒(méi)有較好地均衡節(jié)點(diǎn)的能量消耗,造成有些節(jié)點(diǎn)過(guò)早死亡,這在圖7中也有對(duì)應(yīng)的說(shuō)明.HEED2M由于采用了多跳通信,性能與HEED相比有了提高,但和EEUC考文獻(xiàn)EstrinD.WirelesssensornetworkstutorialpartIV:Sensornetworkprotocols/ProceedingsoftheACMMobileCompu2tingandNetworking(MobiCom),Atlanta,GA,20022KrishnamachariB,EstrinD,WickerS.Theimpactofd

49、ataaggregationinwirelesssensornetworks/ProceedingsoftheIEEEInternationalWorkshoponDistributedEvent2BasedSystems(DEBS),Vienna,Austria,2002:5752578MhatreV,RosenbergC.Designguidelinesforwirelesssen2sornetworks:Communication,clusteringandaggregation.AdHocNetworks,2004,2(1):45263LiCF,YeM,ChenGH,WuJ.Anene

50、rgy2efficientune2qualclusteringmechanismforwirelesssensornetworks/Proceedingsofthe2ndIEEEInternationalConferenceonMobileAd2hocandSensorSystems(MASS2005),Washing2ton,DC,2005HeinzelmanW,ChandrakasanA,BalakrishnanH.Energy2efficientcommunicationprotocolforwirelessmicrosensor345圖9各種分簇協(xié)議的網(wǎng)絡(luò)存活時(shí)間© 1994

51、-2009 China Academic Journal Electronic Publishing House. All rights reserved. 36計(jì)算機(jī)學(xué)報(bào)networks/Proceedingsofthe33rdAnnualHawaiiInterna2tionalConferenceonSystemSciences,Maui,HI,2000:1210122007年YeMao,LiCheng2Fa,ChenGui2Hai,WuJie.Anenergyefficientclusteringschemeinwirelesssensornetworks.AdHoc&Senso

52、rWirelessNetworks(tobepublished)6HeinzelmanW,ChandrakasanA,BalakrishnanH.Anappli2cation2specificprotocolarchitectureforwirelessmicrosensornetworks.IEEETransactionsonWirelessCommunications,2002,1(4):660267013IntanagonwiwatC,GovindanR,EstrinD.Directeddiffu2sion:Ascalableandrobustcommunicationparadigmf

53、orsen2sornetworks/ProceedingsoftheACMMobileComputingandNetworking(MobiCom),Boston,MA,2000:562677LindseyS,RaghavendraC,SivalingamKM.Datagatheringalgorithmsinsensornetworksusingenergymetrics.IEEETransactionsonParallelandDistributedSystems,2002,13(9):924293514SchurgersC,SrivastavaMB.Energyefficientrout

54、inginwirelesssensornetworks/ProceedingsoftheIEEEMilitaryCommunicationsConference(MILCOM),McLean,VA,2001:35723618DasguptaK,KalpakisK,NamjoshiP.Anefficientcluste2ring2basedheuristicfordatagatheringandaggregationinsensornetworks/ProceedingsoftheIEEEWirelessCommu2nicationsandNetworkingConference(WCNC),N

55、ewOrle2ans,LA,2003:194821953161715PreparataFP,ShamosMI.ComputationalGeometry:AnIntroduction.NewYork:Springer2Verlag,1985GibsonJ.TheMobileCommunicationsHandbook.BocaRa2ton:CRCPress,1999KawadiaV,KumarPR.PowercontrolandclusteringinAdHocnetworks/ProceedingsoftheIEEEINFOCOM,SanFrancisco,CA,2003:45924699C

56、hoiW,ShahP,DasSK.Aframeworkforenergy2savingdatagatheringusingtwo2phaseclusteringinwirelesssensornetworks/ProceedingsoftheInternationalConferenceonMobileandUbiquitousSystems:NetworkingandServices(MOBIQUITOUS),Boston,MA,2004:203221218BasagniS.Distributedadhocnetworks/Pro2oftheonParallelAr2,(ISPAN),Frem