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

17目錄摘 要-ABSTRACT-引 言-1相關(guān)工作-12問(wèn)題描述-33基于非均勻分簇的路由機(jī)制-54 EEUC的分析-95實(shí)驗(yàn)結(jié)果及分析-116結(jié)論和進(jìn)一步工作-15致謝-16參考文獻(xiàn)-17摘要在路由協(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é)議。它的核心是一個(gè)用于組織網(wǎng)絡(luò)拓?fù)涞哪芰扛咝У姆蔷鶆蚍执厮惴ǎ渲泻蜻x簇首通過(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ò)；能量高效；非均勻分簇；路由；多跳通ABSTRACTEmploying clustering techniques in routing protocols can increase the scalability of Wireless sensor networks.When cluster heads transmit their data to the data sink via multi-hop communication,the cluster heads closer to the sink are burdened with heavy relay trffic and tend to die early,causing network partitions.This paper presents a novel uneven cluster-based routing protocol for wireless sensor networks.Its core is an Energy-Efficient Uneven Clustering (EEUC) algorithm for network topology organization,in which tentative cluster heads use uneven competition ranges to construct clusters of uneven sizes.The clusters closer to the sink have smaller sizes than those farther away from the sink,thus the cluster heads closer to the sink can preserve some energy for the inter-cluster data forwarding.Simulation results show that the routing protocol effectively balances the energy consumption among cluster heads and achieves an obvious improvenment on the network lifetime.Keywords wireless sensor networks; energy efficient; uneven clustering; routing; multi-hop communication一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議引言隨著微電子工藝和無(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)。傳感器節(jié)點(diǎn)通常是由能量十分有限的電池供電，而且在部署后難以二次補(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ú)線通信消耗了大部分的能量?；诜执氐膶哟问铰酚煞椒ㄔ谔岣呔W(wǎng)絡(luò)的可擴(kuò)展性方面特別有效。在以分簇方式組織的傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的角色分為簇首和簇成員兩種。簇首作為簇的中心負(fù)責(zé)簇結(jié)構(gòu)的建立，收集簇成員的數(shù)據(jù)，經(jīng)融合處理后發(fā)送給匯聚點(diǎn)。由于簇首距離匯聚點(diǎn)的距離一般較遠(yuǎn)，已有研究（如文獻(xiàn)3等）表明在簇首與匯聚點(diǎn)之間通信時(shí)采取多跳的方式（即通過(guò)簇首組成的骨干網(wǎng)實(shí)現(xiàn)多跳路由）更有利于節(jié)約能量。然而這種做法帶來(lái)了一個(gè)能量消耗不均衡的問(wèn)題：在這種所有傳感器節(jié)點(diǎn)的數(shù)據(jù)都發(fā)送到匯聚點(diǎn)的“多對(duì)一”數(shù)據(jù)傳輸模式中，靠近匯聚點(diǎn)的節(jié)點(diǎn)由于需要轉(zhuǎn)發(fā)大量來(lái)自其它簇的數(shù)據(jù)而負(fù)擔(dān)過(guò)重，過(guò)早耗盡自身能量而失效，造成網(wǎng)絡(luò)分割，降低網(wǎng)絡(luò)存活時(shí)間。研究者稱這個(gè)問(wèn)題為“熱區(qū)”（hot spots）問(wèn)題。本文設(shè)計(jì)并分析了一種新穎的基于分簇的傳感器網(wǎng)絡(luò)路由協(xié)議，其核心是一個(gè)能量高效的非均勻分簇(Energy-Efficient Uneven Clustering,EEUC)算法。路由的組織分為簇內(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á)到均衡簇首能量消耗的目的。此外，在簇首選擇其路由的下一跳節(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í)間。本文第1節(jié)介紹相關(guān)工作；第2節(jié)給出網(wǎng)絡(luò)的模型，并討論能量消耗的不均衡問(wèn)題；第3節(jié)全面闡述EEUC算法和簇間的多跳路由算法；第4節(jié)對(duì)EEUC算法的性質(zhì)進(jìn)行了分析；第5節(jié)通過(guò)實(shí)驗(yàn)分析了該路由協(xié)議的性能；最后是工作總結(jié)和對(duì)未來(lái)工作的展望。1 相關(guān)工作近年來(lái)，研究人員提出了多種傳感器網(wǎng)絡(luò)的分簇協(xié)議。Heinzelman等人提出一種稱為L(zhǎng)EACH的分簇協(xié)議5。在每個(gè)數(shù)據(jù)收集的周期（一個(gè)周期也稱為一輪）開(kāi)始，一小部分節(jié)點(diǎn)隨機(jī)成為簇首。在數(shù)據(jù)傳輸階段，簇首以單跳通信的方式將融合后的數(shù)據(jù)傳輸給匯聚點(diǎn)。為了提高簇的生成質(zhì)量，Heinzelman等人又提出了集中式的簇構(gòu)造算法LEACH-C以及考慮節(jié)點(diǎn)能量的算法（本文稱其為L(zhǎng)EACH-E)6等人提出的PEGASIS 算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)組織為鏈狀，數(shù)據(jù)在鏈上經(jīng)融合處理，最后傳輸至匯聚點(diǎn)；算法需要知道每個(gè)節(jié)點(diǎn)的位置信息。Dasgupta等人提出一種基于分簇的啟發(fā)式算法來(lái)最大化網(wǎng)絡(luò)的存活時(shí)間，算法需要知道節(jié)點(diǎn)的位置信息和能量信息。Choi等人提出兩階段分簇協(xié)議TPC,在簇內(nèi)構(gòu)造多跳路由鏈路以節(jié)約能量。Younis等人提出一種混合式的分簇協(xié)議HEED。算法首先根據(jù)節(jié)點(diǎn)的剩余能量來(lái)概率性地選取一些候選簇首，然后以簇內(nèi)部通信代價(jià)的高低來(lái)競(jìng)爭(zhēng)產(chǎn)生最終簇首。與LEACH不同的是，它的簇生成算法需要在簇半徑內(nèi)進(jìn)行多次消息迭代，由此帶來(lái)的通信開(kāi)銷比較顯著。上述的這些協(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)題。文中所假設(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ù)留能量。但是他們考慮的是一個(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)題。在我們的先前工作EE-CS中，節(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)景上有較大差別，需要為傳感器網(wǎng)絡(luò)設(shè)計(jì)優(yōu)化的路由協(xié)議。Intanagonwiwat等人提出的定向擴(kuò)散協(xié)議是一種基于查詢的路由機(jī)制。匯聚點(diǎn)發(fā)出查詢消息，形成反向的從數(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)均衡的流量分布。然而這些查詢或事件驅(qū)動(dòng)的協(xié)議都不適用于連續(xù)性數(shù)據(jù)收集場(chǎng)景下的“多對(duì)一”數(shù)據(jù)傳輸，因此也不適合在簇首間進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)使用。與已有的研究工作相比較，本文提出的分簇協(xié)議具有下列創(chuàng)新之處：(1)首次提出一個(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圖結(jié)構(gòu)的簇。(4)為簇首間進(jìn)行多跳數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)計(jì)了一個(gè)能量高效的路由算法。2 問(wèn)題描述在這一部分，首先給出本文采用的網(wǎng)絡(luò)模型，然后闡述用非均勻分簇機(jī)制來(lái)解決“熱區(qū)”問(wèn)題的思想。2.1 網(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è)唯一的標(biāo)識(shí)(ID)。 (3)根據(jù)接收者的距離遠(yuǎn)近，節(jié)點(diǎn)可以自由調(diào)整其發(fā)射功率以節(jié)約能量消耗。(4)鏈路是對(duì)稱的。若已知對(duì)方發(fā)射功率，節(jié)點(diǎn)可以根據(jù)接收信號(hào)的強(qiáng)度RSSI計(jì)算出發(fā)送者到自己的近似距離。我們采用與文獻(xiàn)6相同的無(wú)線通信能量消耗模型。節(jié)點(diǎn)發(fā)射犾比特的數(shù)據(jù)到距離為d的位置，消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，即其中Eelec表示發(fā)射電路損耗的能量。若傳輸距離小于閾值d0功率放大損耗采用自由空間模型；當(dāng)傳輸距離大于等于閾值d0時(shí)，采用多路徑衰減模型。fs、mp分別為這兩種模型中功率放大所需的能量。節(jié)點(diǎn)接收l(shuí)比特的數(shù)據(jù)消耗的能量為數(shù)據(jù)融合也消耗一定的能量，用EDF表示融合單位比特?cái)?shù)據(jù)消耗的能量。我們假設(shè)鄰近節(jié)點(diǎn)采集的數(shù)據(jù)具有較高的冗余度，簇首可以將其成員的數(shù)據(jù)融合成一個(gè)長(zhǎng)度固定的數(shù)據(jù)包，然后發(fā)送給匯聚點(diǎn)。2.2 能量消耗不均勻問(wèn)題傳感器網(wǎng)絡(luò)路由協(xié)議的一個(gè)重要目標(biāo)，就是要合理高效地使用網(wǎng)絡(luò)中各傳感器節(jié)點(diǎn)的能量，延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間。在以分簇方式組織的傳感器網(wǎng)絡(luò)中，路由分為簇內(nèi)通信和簇首與匯聚點(diǎn)間通信（有時(shí)也稱作簇首間通信）兩部分。當(dāng)簇成員與簇首之間傳輸數(shù)據(jù)時(shí)，可以采用單跳通信的方式，這樣易于調(diào)度各成員的數(shù)據(jù)傳輸。當(dāng)簇首向匯聚點(diǎn)進(jìn)行長(zhǎng)距離數(shù)據(jù)傳輸時(shí)，已有研究表明采用多跳路由的方式更為實(shí)際，且顯著降低能量消耗。本文將簇首節(jié)點(diǎn)組成一個(gè)多跳路由的骨干網(wǎng)?？拷鼌R聚點(diǎn)的簇首在把自身數(shù)據(jù)傳輸給匯聚點(diǎn)的同時(shí)，還轉(zhuǎn)發(fā)來(lái)自遠(yuǎn)離匯聚點(diǎn)的簇首的數(shù)據(jù)。在每一輪中，簇首消耗的能量包括簇內(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ò)周期性地重新選擇簇首(如LEEACH、HEED)，可以平衡簇首與簇成員節(jié)點(diǎn)之間的能量消耗，但不能解決上述的“熱區(qū)”問(wèn)題。以節(jié)點(diǎn)的剩余能量為依據(jù)選擇簇首的方法(如EECS)也不能完全解決這個(gè)問(wèn)題，因?yàn)樗皇窃诰W(wǎng)絡(luò)的局部比較節(jié)點(diǎn)剩余能量，無(wú)法從整體上協(xié)調(diào)節(jié)點(diǎn)的能量消耗以解決“熱區(qū)”問(wèn)題?？梢哉J(rèn)為上述兩種方法都是以被動(dòng)的方式來(lái)均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，即在網(wǎng)絡(luò)中出現(xiàn)能量消耗不均衡之后方采取措施來(lái)均衡能量消耗。在結(jié)合這兩種技術(shù)的基礎(chǔ)上，本文創(chuàng)新地設(shè)計(jì)了一種基于非均勻分簇的層次式路由協(xié)議。與前人的方法相比，本文提出的方法以主動(dòng)的方式來(lái)均衡網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗，特別是均衡簇首的能量消耗。3 基于非均勻分簇的路由機(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é)議的示意，其中大小不等的圓表示簇首節(jié)點(diǎn)的大小非均勻的競(jìng)爭(zhēng)范圍，帶箭頭的粗線表示簇首間的多跳數(shù)據(jù)傳輸。3.1 EEUC算法 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，它是一個(gè)預(yù)先設(shè)置的閾值。未參與競(jìng)選的節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)，直到簇首競(jìng)選過(guò)程結(jié)束。令Si為任意的一個(gè)候選簇首。Si根據(jù)自身到匯聚點(diǎn)的距離信息計(jì)算它的競(jìng)爭(zhēng)區(qū)域，區(qū)域的半徑記作Rc，下面定義候選簇首之間競(jìng)爭(zhēng)的規(guī)則規(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) IfT then beTentativeHeadtrue End if If be TentativeHead=true then Broadcast COMPETE_HEAD_MSG(ID,Rc,RE) Else Exit End if On receiving a COMPETE_HEAD_MSG form sj If d(Si, sj) sj,Rc or d d(Si, sj) sj,RE then Broadcast FINAL_HEAD_MSG(ID) and then exit End if On receiving a FINAL_HEAD_MSG form sj If sjSi, SCH then Broadcast QUIT_ELECTION_MSG(ID) and then exit21 End if22 On receiving a QUIT_ELECTION_MSG form sj23 If sjSi, SCH then24 Remove sj form Si. SCH25 End if26 End while圖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)半徑的取值范圍，使得距離匯聚點(diǎn)最近的節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑為（-c）R0c,其中c是用于控制取值范圍的參數(shù)，在01之間取值候選簇首Si確定其競(jìng)爭(zhēng)半徑Si.Rc的計(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/3 R0cR0c.每個(gè)候選簇首維護(hù)一個(gè)鄰簇首集合SCH在這個(gè)集合內(nèi)依據(jù)當(dāng)前各節(jié)點(diǎn)的剩余能量高低競(jìng)爭(zhēng)選出最終簇首候選簇首Si的鄰簇首集合包括與Si具有規(guī)則1所約束的競(jìng)爭(zhēng)關(guān)系的所有候選簇首節(jié)點(diǎn)，其定義如下。定義 1. 在EEUC簇首競(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)建完成后，在1426行，節(jié)點(diǎn)做出其是否能擔(dān)任簇首的決策。節(jié)點(diǎn)需要等待其鄰簇首集合中所有能量比它大的節(jié)點(diǎn)先做出決策，然后才能確定自身是否能擔(dān)任簇首在1517行，一旦sj發(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中的一個(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)選擇簇內(nèi)通信代價(jià)最小亦即接收信號(hào)強(qiáng)度最大的簇首，發(fā)送加入消息JOIN_CLUSTER_MSG通知該簇首。這樣，網(wǎng)絡(luò)中的節(jié)點(diǎn)組成了Voronoi圖結(jié)構(gòu)的簇。接下來(lái)進(jìn)入簇內(nèi)部的數(shù)據(jù)傳輸階段。簇首構(gòu)建TDMA調(diào)度，然后簇成員向簇首傳輸數(shù)據(jù)。本文采用與LEACH相同的組織方式，在此不再贅述。3.2 簇首間多跳路由協(xié)議在簇首將數(shù)據(jù)傳輸?shù)絽R聚點(diǎn)這個(gè)階段，簇首先對(duì)簇成員的數(shù)據(jù)進(jìn)行融合處理，然后將數(shù)據(jù)以多跳通信的方式發(fā)送至匯聚點(diǎn)。由于傳感器網(wǎng)絡(luò)的這種獨(dú)特的“多對(duì)一”的數(shù)據(jù)傳輸模式，移動(dòng)自組網(wǎng)絡(luò)中成熟的路由協(xié)議在此無(wú)法適用，傳感器網(wǎng)絡(luò)中已有的路由協(xié)議中也鮮有針對(duì)本文場(chǎng)景設(shè)計(jì)的算法。在有些文獻(xiàn)提出的傳感器網(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收到簇首sj廣播的消息后，可以計(jì)算出它們之間的近似距離下文敘述當(dāng)d(Si,DS)TD_MAX時(shí)，簇首Si的路由選擇策略。Kawadia等在文獻(xiàn)指出，選擇鄰近的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)有利于減少通信干擾。本文將路由候選節(jié)點(diǎn)的選取范圍限制在比其自身更鄰近匯聚點(diǎn)的一個(gè)區(qū)域內(nèi)。4 EEUC的分析這一節(jié)給出非均勻分簇算法EEUC的一些分析和說(shuō)明。該算法是消息驅(qū)動(dòng)的，因此首先來(lái)分析它的消息復(fù)雜度。性質(zhì) 1. 在整個(gè)網(wǎng)絡(luò)中，EEUC算法的消息復(fù)雜度為O(N)。證明. 在算法開(kāi)始，有NT個(gè)節(jié)點(diǎn)成為候選簇首而參與競(jìng)選，共廣播NT條COMPETE_HEAD_MSG消息。然后，每個(gè)候選簇首或者廣播一條消息FINAL_HEAD_MSG以宣布其競(jìng)選成功，或者廣播一條消息QUIT_ELECTION_MSG以宣布其退出競(jìng)選。假設(shè)共選出k個(gè)簇首，則它們廣播k條CH_ADV_MSG消息，而N-K個(gè)簇成員廣播N-K條JOIN_CLUSTER_MSG消息。因此，網(wǎng)絡(luò)中總的消息開(kāi)銷為NN+NT+k+N-k=(2T+1)N所以消息復(fù)雜度為0(N). 證畢。性質(zhì)1說(shuō)明EEUC算法的消息開(kāi)銷較小，能量高效。HEED的分簇算法也是消息驅(qū)動(dòng)的，其消息交換次數(shù)的上界為NiterN, Niter是消息迭代的次數(shù)。因?yàn)镋EUC避免了消息迭代，因此消息開(kāi)銷低于HEED.由性質(zhì)1的證明可知，閾值T決定算法的消息開(kāi)銷。選擇合適的T既可以讓大量剩余能量較高的節(jié)點(diǎn)參與競(jìng)選過(guò)程，又不至于導(dǎo)致消息開(kāi)銷過(guò)大。關(guān)于T的優(yōu)化取值，我們?cè)谙惹肮ぷ髦型ㄟ^(guò)實(shí)驗(yàn)給出了詳細(xì)的分析。接下來(lái)分析EEUC算法中的參數(shù)R0c和c的取值對(duì)網(wǎng)絡(luò)存活時(shí)間的影響。簇的成員數(shù)目之間的非均勻程度由c決定。c的值越大，候選簇首的競(jìng)爭(zhēng)半徑的差異越大，因此簇的成員數(shù)目間的差異越明顯。而當(dāng)c等于0時(shí)，候選簇首的競(jìng)爭(zhēng)半徑相同，算法將生成大小均勻的簇算法中所生成簇的數(shù)目由R0c和c共同決定。固定c,當(dāng)R0c增大時(shí)，每個(gè)候選簇首的競(jìng)爭(zhēng)半徑隨之增大，因此所生成的簇的數(shù)目隨之減??；固定R0c，當(dāng)c增大時(shí)，每個(gè)候選簇首的競(jìng)爭(zhēng)半徑隨之減小，因此所生成的簇的數(shù)目隨之增加。R0c和c的優(yōu)化取值可以優(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的剩余能量依次遞增。因此下列事件依次先后發(fā)生：S5宣布其成為簇首，S4退出競(jìng)選，S3宣布其成為簇首，S2退出競(jìng)選，S1宣布其成為簇首。算法從開(kāi)始到結(jié)束共持續(xù)了4條消息的傳遞時(shí)間。這個(gè)例子說(shuō)明算法需要等待的時(shí)間由網(wǎng)絡(luò)中候選節(jié)點(diǎn)構(gòu)成的單調(diào)能量鏈的最大長(zhǎng)度決定。候選節(jié)點(diǎn)的剩余能量分布呈現(xiàn)隨機(jī)性，所以這條鏈越長(zhǎng)，其出現(xiàn)的概率越低在文獻(xiàn)中，Basagni研究了移動(dòng)自組網(wǎng)中一個(gè)分簇算法中類似的問(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)銷也較小。5 實(shí)驗(yàn)結(jié)果及分析我們用C語(yǔ)言編寫模擬程序?qū)诜蔷鶆蚍执厮惴‥EUC的路由協(xié)議進(jìn)行性能分析與評(píng)估。首先研究EEUC分簇算法所選擇的簇首的特征，然后分析協(xié)議的能量效率。為簡(jiǎn)單起見(jiàn)，假設(shè)采用理想的MAC協(xié)議，忽略無(wú)線鏈路中可能發(fā)生的丟包錯(cuò)誤。實(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、LEACH-E、HEED和HEED-M 4種基于分簇的路由協(xié)議進(jìn)行比較。為便于下文的分析，表1對(duì)這5種協(xié)議的特征進(jìn)行了概括。在LEACH-E中，每個(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)。 實(shí)驗(yàn)中所用的參數(shù)如表2所示，其中能量消耗模型相關(guān)的參數(shù)取自文獻(xiàn)6。除非特別指出，本協(xié)議的參數(shù)設(shè)置為T=0.4，R0c=90m,c=0.5,TD_MAX=140m.其它協(xié)議中的參數(shù)通過(guò)運(yùn)行多次實(shí)驗(yàn)來(lái)找出其最優(yōu)取值。5.1 簇首的特征由前一節(jié)的分析可知，EEUC分簇算法選取的簇首的數(shù)目由參數(shù)R0c和c共同決定。圖4顯示了c取兩個(gè)不同的值時(shí)，簇首的數(shù)目與R0c之間的關(guān)系。它驗(yàn)證了前一節(jié)的分析，即競(jìng)爭(zhēng)半徑越小，算法生成的簇首的數(shù)目越大在圖中，c0.5時(shí)對(duì)應(yīng)的曲線高于c=0時(shí)對(duì)應(yīng)的曲線這是因?yàn)楫?dāng)R0c固定時(shí)，c的增大導(dǎo)致候選簇首的競(jìng)爭(zhēng)半徑變小，因此簇首的數(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.由圖可見(jiàn)，每種協(xié)議生成的簇首的數(shù)目都有一個(gè)期望值，它是協(xié)議在此場(chǎng)景下最優(yōu)的簇首數(shù)目。LEACH和LEACH-E的簇首數(shù)目的波動(dòng)范圍比較大，這是因?yàn)長(zhǎng)EACH和LEACH-E單純性地采用隨機(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)定的簇，可靠性好。最后來(lái)比較各種分簇協(xié)議對(duì)網(wǎng)絡(luò)存活時(shí)間的影響。圖9顯示了網(wǎng)絡(luò)中存活的節(jié)點(diǎn)數(shù)目隨時(shí)間變化的情況。顯然，無(wú)論是第一個(gè)節(jié)點(diǎn)死亡的時(shí)間還是最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間，EEUC均優(yōu)于其它4種協(xié)議。從第一個(gè)節(jié)點(diǎn)死亡到最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間跨度可以反映出網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡情況，跨度越短說(shuō)明網(wǎng)絡(luò)的能量使用越高效。EEUC不僅顯著地延長(zhǎng)了網(wǎng)絡(luò)的存活時(shí)間，而且時(shí)間跨度也遠(yuǎn)小于其它協(xié)議，這說(shuō)明EEUC很好地均衡了網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗。LEACH-E在選取簇首時(shí)雖然考慮了節(jié)點(diǎn)的剩余能量，但由于傳播能量消息帶來(lái)的開(kāi)銷，其性能還略差于LEACH.HEED的第一個(gè)節(jié)點(diǎn)死亡時(shí)間明顯早于LEACH，但最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間晚于LEACH，這表明HEED并沒(méi)有較好地均衡節(jié)點(diǎn)的能量消耗，造成有些節(jié)點(diǎn)過(guò)早死亡，這在圖7中也有對(duì)應(yīng)的說(shuō)明。HEED-M由于采用了多跳通信，性能與HEED相比有了提高，但和EEUC仍有較大差距，這是因?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é)議。6 結(jié)論和進(jìn)一步的工作本文提出了一種新穎的基于分簇的傳感器網(wǎng)絡(luò)路由協(xié)議，其核心思想是利用一個(gè)能量高效的非均勻分簇算法EEUC將網(wǎng)絡(luò)組織成大小非均勻的簇，以解決多跳路由的傳感器網(wǎng)絡(luò)中常見(jiàn)的“熱區(qū)”問(wèn)題。實(shí)驗(yàn)表明，本路由協(xié)議優(yōu)化了網(wǎng)絡(luò)中的能量消耗，較好地解決了“熱區(qū)”問(wèn)題；和已有的幾個(gè)分簇協(xié)議相比，顯著地延