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

17目錄摘 要-ABSTRACT-引 言-1相關(guān)工作-12問題描述-33基于非均勻分簇的路由機制-54 EEUC的分析-95實驗結(jié)果及分析-116結(jié)論和進一步工作-15致謝-16參考文獻-17摘要在路由協(xié)議中利用分簇技術(shù)可以提高無線傳感器網(wǎng)絡(luò)的可擴展性。當(dāng)簇首以多跳通信的方式將數(shù)據(jù)傳輸至數(shù)據(jù)匯聚點時，靠近匯聚點的簇首由于轉(zhuǎn)發(fā)大量數(shù)據(jù)而負(fù)載過重，可能過早耗盡能量而失效，這將導(dǎo)致網(wǎng)絡(luò)分割。該文提出一種新穎的基于非均勻分簇的無線傳感器網(wǎng)絡(luò)多跳路由協(xié)議。它的核心是一個用于組織網(wǎng)絡(luò)拓?fù)涞哪芰扛咝У姆蔷鶆蚍执厮惴?，其中候選簇首通過使用非均勻的競爭范圍來構(gòu)造大小不等的簇，靠近匯聚點的簇的規(guī)模小于遠(yuǎn)離匯聚點的簇，因此靠近匯聚點的簇首可以為簇間的數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留能量。模擬實驗結(jié)果表明，該路由協(xié)議有效地平衡了簇首的能量消耗，并顯著地延長了網(wǎng)絡(luò)的存活時間。關(guān)鍵詞：無線傳感器網(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ǎng)絡(luò)路由協(xié)議引言隨著微電子工藝和無線通信技術(shù)的飛速發(fā)展，無線傳感器網(wǎng)絡(luò)的研究越來越受到人們的重視。傳感器網(wǎng)絡(luò)是由部署在觀測環(huán)境內(nèi)的大量微型傳感器節(jié)點通過無線通信方式組成的一種無線網(wǎng)絡(luò)。組成傳感器網(wǎng)絡(luò)的節(jié)點包括數(shù)據(jù)匯聚點和傳感器節(jié)點。傳感器節(jié)點通常是由能量十分有限的電池供電，而且在部署后難以二次補充能量，因此傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問題。所以，傳感器網(wǎng)絡(luò)協(xié)議的首要設(shè)計目標(biāo)就是要高效地使用傳感器節(jié)點的能量，延長網(wǎng)絡(luò)的存活時間。傳感器節(jié)點中消耗能量的模塊有傳感器模塊、處理器模塊和無線通信模塊等，其中無線通信消耗了大部分的能量?；诜执氐膶哟问铰酚煞椒ㄔ谔岣呔W(wǎng)絡(luò)的可擴展性方面特別有效。在以分簇方式組織的傳感器網(wǎng)絡(luò)中，傳感器節(jié)點的角色分為簇首和簇成員兩種。簇首作為簇的中心負(fù)責(zé)簇結(jié)構(gòu)的建立，收集簇成員的數(shù)據(jù)，經(jīng)融合處理后發(fā)送給匯聚點。由于簇首距離匯聚點的距離一般較遠(yuǎn)，已有研究（如文獻3等）表明在簇首與匯聚點之間通信時采取多跳的方式（即通過簇首組成的骨干網(wǎng)實現(xiàn)多跳路由）更有利于節(jié)約能量。然而這種做法帶來了一個能量消耗不均衡的問題：在這種所有傳感器節(jié)點的數(shù)據(jù)都發(fā)送到匯聚點的“多對一”數(shù)據(jù)傳輸模式中，靠近匯聚點的節(jié)點由于需要轉(zhuǎn)發(fā)大量來自其它簇的數(shù)據(jù)而負(fù)擔(dān)過重，過早耗盡自身能量而失效，造成網(wǎng)絡(luò)分割，降低網(wǎng)絡(luò)存活時間。研究者稱這個問題為“熱區(qū)”（hot spots）問題。本文設(shè)計并分析了一種新穎的基于分簇的傳感器網(wǎng)絡(luò)路由協(xié)議，其核心是一個能量高效的非均勻分簇(Energy-Efficient Uneven Clustering,EEUC)算法。路由的組織分為簇內(nèi)通信和簇首與匯聚點間通信兩部分：簇內(nèi)通信采用單跳的方式，簡單易實現(xiàn)；簇首與匯聚點間通信采用多跳的方式，避免長距離數(shù)據(jù)傳輸造成能量浪費。EEUC算法利用非均勻的競爭半徑，使得靠近匯聚點的簇的成員數(shù)目相對較小，從而簇首能夠節(jié)約能量以供數(shù)據(jù)轉(zhuǎn)發(fā)使用，達(dá)到均衡簇首能量消耗的目的。此外，在簇首選擇其路由的下一跳節(jié)點時，不僅考慮候選節(jié)點相對匯聚點的位置，還考慮候選節(jié)點的剩余能量實驗結(jié)果表明，該路由協(xié)議有效地解決了多跳通信方式下簇首能量消耗不均衡的問題，優(yōu)化了網(wǎng)絡(luò)中各節(jié)點的能量消耗，顯著地延長了網(wǎng)絡(luò)的存活時間。本文第1節(jié)介紹相關(guān)工作；第2節(jié)給出網(wǎng)絡(luò)的模型，并討論能量消耗的不均衡問題；第3節(jié)全面闡述EEUC算法和簇間的多跳路由算法；第4節(jié)對EEUC算法的性質(zhì)進行了分析；第5節(jié)通過實驗分析了該路由協(xié)議的性能；最后是工作總結(jié)和對未來工作的展望。1 相關(guān)工作近年來，研究人員提出了多種傳感器網(wǎng)絡(luò)的分簇協(xié)議。Heinzelman等人提出一種稱為LEACH的分簇協(xié)議5。在每個數(shù)據(jù)收集的周期（一個周期也稱為一輪）開始，一小部分節(jié)點隨機成為簇首。在數(shù)據(jù)傳輸階段，簇首以單跳通信的方式將融合后的數(shù)據(jù)傳輸給匯聚點。為了提高簇的生成質(zhì)量，Heinzelman等人又提出了集中式的簇構(gòu)造算法LEACH-C以及考慮節(jié)點能量的算法（本文稱其為LEACH-E)6等人提出的PEGASIS 算法將網(wǎng)絡(luò)中的節(jié)點組織為鏈狀，數(shù)據(jù)在鏈上經(jīng)融合處理，最后傳輸至匯聚點；算法需要知道每個節(jié)點的位置信息。Dasgupta等人提出一種基于分簇的啟發(fā)式算法來最大化網(wǎng)絡(luò)的存活時間，算法需要知道節(jié)點的位置信息和能量信息。Choi等人提出兩階段分簇協(xié)議TPC,在簇內(nèi)構(gòu)造多跳路由鏈路以節(jié)約能量。Younis等人提出一種混合式的分簇協(xié)議HEED。算法首先根據(jù)節(jié)點的剩余能量來概率性地選取一些候選簇首，然后以簇內(nèi)部通信代價的高低來競爭產(chǎn)生最終簇首。與LEACH不同的是，它的簇生成算法需要在簇半徑內(nèi)進行多次消息迭代，由此帶來的通信開銷比較顯著。上述的這些協(xié)議均通過周期性地重新分簇，讓節(jié)點輪流擔(dān)任簇首，來達(dá)到網(wǎng)絡(luò)中的節(jié)點比較均衡地消耗能量的目的。 然而，從均衡節(jié)點的能量消耗以延長網(wǎng)絡(luò)的存活時間這個目標(biāo)看，先前的研究主要集中于均衡簇成員節(jié)點之間的能量消耗，沒有考慮到簇首間的能量消耗均衡問題。Soro等人研究了傳感器網(wǎng)絡(luò)多跳路由中的“熱區(qū)”問題，并首次提出利用非均勻分簇的思想來解決這個“熱區(qū)”問題。文中所假設(shè)的網(wǎng)絡(luò)拓?fù)涫黔h(huán)繞匯聚點的兩層同心圓環(huán)，內(nèi)圓環(huán)中的簇首由于靠近匯聚點，需要承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)的任務(wù)，因此通過減小它的簇成員數(shù)目來降低其在簇內(nèi)處理中消耗的能量，為簇首間數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留能量。但是他們考慮的是一個異構(gòu)網(wǎng)絡(luò)，簇首為超級節(jié)點，而且位置是事先計算好的，無需動態(tài)構(gòu)造簇的操作。在單跳通信的網(wǎng)絡(luò)中，由于簇首距離匯聚點遠(yuǎn)近的差異，也存在簇首負(fù)載不均衡的問題。在我們的先前工作EE-CS中，節(jié)點在選擇簇首時不是簡單地選擇距離自身最近的簇首，而是考慮了候選簇首到匯聚點的距離遠(yuǎn)近，構(gòu)造出大小非均勻的簇，均衡簇首的負(fù)載。由于傳感器網(wǎng)絡(luò)與移動自組網(wǎng)絡(luò)在應(yīng)用場景上有較大差別，需要為傳感器網(wǎng)絡(luò)設(shè)計優(yōu)化的路由協(xié)議。Intanagonwiwat等人提出的定向擴散協(xié)議是一種基于查詢的路由機制。匯聚點發(fā)出查詢消息，形成反向的從數(shù)據(jù)源到匯聚點的數(shù)據(jù)傳輸梯度。數(shù)據(jù)沿著梯度傳送到匯聚點。Schurgers等人提出了定向擴散的一個變種即基于梯度的路由算法GBR,并設(shè)計了三種動態(tài)調(diào)整節(jié)點梯度的策略，以實現(xiàn)均衡的流量分布。然而這些查詢或事件驅(qū)動的協(xié)議都不適用于連續(xù)性數(shù)據(jù)收集場景下的“多對一”數(shù)據(jù)傳輸，因此也不適合在簇首間進行數(shù)據(jù)轉(zhuǎn)發(fā)使用。與已有的研究工作相比較，本文提出的分簇協(xié)議具有下列創(chuàng)新之處：(1)首次提出一個非均勻分簇的分布式算法，來解決傳感器網(wǎng)絡(luò)多跳路由中的“熱區(qū)”問題。(2)不同于LEACH,簇首通過局部競爭的方式產(chǎn)生，而且不同于HEED,算法無需迭代。(3)不同于EECS,通過選舉出非均勻分布的簇首，節(jié)點組成了Voronoi圖結(jié)構(gòu)的簇。(4)為簇首間進行多跳數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)計了一個能量高效的路由算法。2 問題描述在這一部分，首先給出本文采用的網(wǎng)絡(luò)模型，然后闡述用非均勻分簇機制來解決“熱區(qū)”問題的思想。2.1 網(wǎng)絡(luò)模型考慮一個由N個隨機部署的傳感器節(jié)點形成的網(wǎng)絡(luò)，其應(yīng)用場景為周期性的數(shù)據(jù)收集用Si表示第i個節(jié)點，相應(yīng)的節(jié)點集合為S=s1,s2,sN,|S|=N.我們假設(shè)：(1) 數(shù)據(jù)匯聚點位于一個方形觀測區(qū)域A的外側(cè)。傳感器節(jié)點和匯聚點DS在部署后均不再發(fā)生位置移動。(2) 所有節(jié)點都是同構(gòu)的，具備數(shù)據(jù)融合的功能。每個節(jié)點都有一個唯一的標(biāo)識(ID)。 (3)根據(jù)接收者的距離遠(yuǎn)近，節(jié)點可以自由調(diào)整其發(fā)射功率以節(jié)約能量消耗。(4)鏈路是對稱的。若已知對方發(fā)射功率，節(jié)點可以根據(jù)接收信號的強度RSSI計算出發(fā)送者到自己的近似距離。我們采用與文獻6相同的無線通信能量消耗模型。節(jié)點發(fā)射犾比特的數(shù)據(jù)到距離為d的位置，消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，即其中Eelec表示發(fā)射電路損耗的能量。若傳輸距離小于閾值d0功率放大損耗采用自由空間模型；當(dāng)傳輸距離大于等于閾值d0時，采用多路徑衰減模型。fs、mp分別為這兩種模型中功率放大所需的能量。節(jié)點接收l比特的數(shù)據(jù)消耗的能量為數(shù)據(jù)融合也消耗一定的能量，用EDF表示融合單位比特數(shù)據(jù)消耗的能量。我們假設(shè)鄰近節(jié)點采集的數(shù)據(jù)具有較高的冗余度，簇首可以將其成員的數(shù)據(jù)融合成一個長度固定的數(shù)據(jù)包，然后發(fā)送給匯聚點。2.2 能量消耗不均勻問題傳感器網(wǎng)絡(luò)路由協(xié)議的一個重要目標(biāo)，就是要合理高效地使用網(wǎng)絡(luò)中各傳感器節(jié)點的能量，延長網(wǎng)絡(luò)的存活時間。在以分簇方式組織的傳感器網(wǎng)絡(luò)中，路由分為簇內(nèi)通信和簇首與匯聚點間通信（有時也稱作簇首間通信）兩部分。當(dāng)簇成員與簇首之間傳輸數(shù)據(jù)時，可以采用單跳通信的方式，這樣易于調(diào)度各成員的數(shù)據(jù)傳輸。當(dāng)簇首向匯聚點進行長距離數(shù)據(jù)傳輸時，已有研究表明采用多跳路由的方式更為實際，且顯著降低能量消耗。本文將簇首節(jié)點組成一個多跳路由的骨干網(wǎng)?？拷鼌R聚點的簇首在把自身數(shù)據(jù)傳輸給匯聚點的同時，還轉(zhuǎn)發(fā)來自遠(yuǎn)離匯聚點的簇首的數(shù)據(jù)。在每一輪中，簇首消耗的能量包括簇內(nèi)部處理和簇之間處理兩部分。已有的分簇算法通常都是構(gòu)造大小均勻的簇，以均衡簇首在簇內(nèi)部進行數(shù)據(jù)處理時消耗的能量。然而由于靠近匯聚點的簇首承擔(dān)了額外的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，因此其在簇首間通信的過程中將消耗更多的能量。所以，若采用均勻分簇的方式，在每一輪中，靠近匯聚點的簇首將消耗更多的能量，造成節(jié)點過早能量耗盡而失效，降低了網(wǎng)絡(luò)的存活時間。 在傳統(tǒng)的同構(gòu)網(wǎng)絡(luò)分簇協(xié)議中，通過周期性地重新選擇簇首(如LEEACH、HEED)，可以平衡簇首與簇成員節(jié)點之間的能量消耗，但不能解決上述的“熱區(qū)”問題。以節(jié)點的剩余能量為依據(jù)選擇簇首的方法(如EECS)也不能完全解決這個問題，因為它只是在網(wǎng)絡(luò)的局部比較節(jié)點剩余能量，無法從整體上協(xié)調(diào)節(jié)點的能量消耗以解決“熱區(qū)”問題?？梢哉J(rèn)為上述兩種方法都是以被動的方式來均衡網(wǎng)絡(luò)中節(jié)點的能量消耗，即在網(wǎng)絡(luò)中出現(xiàn)能量消耗不均衡之后方采取措施來均衡能量消耗。在結(jié)合這兩種技術(shù)的基礎(chǔ)上，本文創(chuàng)新地設(shè)計了一種基于非均勻分簇的層次式路由協(xié)議。與前人的方法相比，本文提出的方法以主動的方式來均衡網(wǎng)絡(luò)中所有節(jié)點的能量消耗，特別是均衡簇首的能量消耗。3 基于非均勻分簇的路由機制在網(wǎng)絡(luò)部署階段，匯聚點需要用一個給定的發(fā)送功率向網(wǎng)絡(luò)內(nèi)廣播一個信號。每個傳感器節(jié)點在接收到此信號后，根據(jù)接收信號的強度計算它到匯聚點的近似距離。獲得這個距離不僅有助于傳感器節(jié)點向匯聚點傳輸數(shù)據(jù)時選擇合適的發(fā)送功率以節(jié)約能量消耗，而且它還是算法構(gòu)造大小非均勻的簇的必需信息之一。本節(jié)分兩部分描述非均勻分簇算法EEUC和簇首間的多跳路由協(xié)議。圖1給出本文提出的基于非均勻分簇的路由協(xié)議的示意，其中大小不等的圓表示簇首節(jié)點的大小非均勻的競爭范圍，帶箭頭的粗線表示簇首間的多跳數(shù)據(jù)傳輸。3.1 EEUC算法 EEUC是一個分布式的競爭算法，以節(jié)點的剩余能量為主要比較依據(jù)。在采用分簇的傳感器網(wǎng)絡(luò)中，簇首是最重要的節(jié)點。它不僅需要管理所屬簇成員，協(xié)調(diào)成員的數(shù)據(jù)傳輸，還要融合簇成員收集的數(shù)據(jù)，再將處理后的數(shù)據(jù)發(fā)送給匯聚點。由于簇首的負(fù)擔(dān)較重，EEUC算法在每個數(shù)據(jù)收集周期的開始重新構(gòu)造簇，選擇剩余能量較高的節(jié)點作為簇首。下面闡述競爭選取簇首的算法。算法1給出了任意節(jié)點Si在簇首競選過程中執(zhí)行的算法偽碼。下面是對算法1的具體解釋。首先，依概率在網(wǎng)絡(luò)中選出部分節(jié)點成為候選簇首，參與競選。普通節(jié)點成為候選簇首的概率為T，它是一個預(yù)先設(shè)置的閾值。未參與競選的節(jié)點進入睡眠狀態(tài)，直到簇首競選過程結(jié)束。令Si為任意的一個候選簇首。Si根據(jù)自身到匯聚點的距離信息計算它的競爭區(qū)域，區(qū)域的半徑記作Rc，下面定義候選簇首之間競爭的規(guī)則規(guī)則 1. 在競選過程中，若候選簇首Si宣布其競選獲勝，則在Si的競爭半徑Rc內(nèi)的所有候選簇首均不能成為最終簇首，需要退出競選過程算法 1. EEUC的簇首競選算法。 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，其中大小不同的圓代表候選簇首的競爭區(qū)域。按照規(guī)則1的要求，S1和S2可以同時成為最終簇首，而S3和S4則不能同時成為最終簇首，因為S4位于S3的競爭區(qū)域內(nèi)部。如前文所分析的，算法的目標(biāo)是讓靠近匯聚點的簇的成員較少，使其簇首能夠預(yù)留部分能量供簇首間通信使用。因此，靠近匯聚點的候選簇首的競爭半徑應(yīng)該較小。亦即，隨著候選簇首到匯聚點距離的減小，其競爭半徑應(yīng)該隨之減小。記候選簇首的競爭半徑的最大取值為R0c,算法需要控制競爭半徑的取值范圍，使得距離匯聚點最近的節(jié)點的競爭半徑為（-c）R0c,其中c是用于控制取值范圍的參數(shù)，在01之間取值候選簇首Si確定其競爭半徑Si.Rc的計算公式如下：其中dmax和dmin分別代表網(wǎng)絡(luò)中的節(jié)點到匯聚點的距離的最大值和最小值，d(Si,DS)代表節(jié)點Si到匯聚點的距離。競爭半徑與節(jié)點到匯聚點的距離呈線性遞減關(guān)系。舉個例子，取c=1/3時，競爭半徑的取值范圍是2/3 R0cR0c.每個候選簇首維護一個鄰簇首集合SCH在這個集合內(nèi)依據(jù)當(dāng)前各節(jié)點的剩余能量高低競爭選出最終簇首候選簇首Si的鄰簇首集合包括與Si具有規(guī)則1所約束的競爭關(guān)系的所有候選簇首節(jié)點，其定義如下。定義 1. 在EEUC簇首競選算法中，候選簇首Si的鄰簇首集合Si. SCH為Si. SCH=sj| sj是候選簇首，且d(Si, sj)max(Si,Rc, sj,Rc). 在此算法中，每個節(jié)點均以同樣的功率發(fā)送廣播消息，為了節(jié)約能量，這個廣播半徑設(shè)為R0c即可（這保證了節(jié)點能夠與鄰簇首集合內(nèi)的所有節(jié)點正常通信）。在算法1的第56行，每個競選節(jié)點廣播競選消息COMPETE_HEAD_MSG，消息的內(nèi)容為節(jié)點的ID、競爭半徑Rc和當(dāng)前剩余能量RE.在第1013行，節(jié)點根據(jù)收到的廣播消息構(gòu)建其鄰簇首集合SCH當(dāng)SCH構(gòu)建完成后，在1426行，節(jié)點做出其是否能擔(dān)任簇首的決策。節(jié)點需要等待其鄰簇首集合中所有能量比它大的節(jié)點先做出決策，然后才能確定自身是否能擔(dān)任簇首在1517行，一旦sj發(fā)現(xiàn)它的剩余能量比其鄰簇首集合中的節(jié)點的剩余能量都高，則它將贏得競選，并廣播獲勝消息FINAL_HEAD_MSG以通知它的鄰簇首在1821行，如果Si收到來自sj的獲勝消息，且sj是Si. SCH中的一個節(jié)點，則Si立即退出競選，并廣播消息QUIT_ELECTION_MSG通知它的鄰簇首在2225行，如果Si收到來自sj的退出消息，且sj是Si. SCH中的一個節(jié)點，則Si將sj從其鄰簇首集合中刪除。 算法1過程結(jié)束后，之前未參與競選的節(jié)點從睡眠狀態(tài)喚醒，接著競選產(chǎn)生的簇首向全網(wǎng)廣播其競選獲勝的消息CH_ADV_MSG.普通節(jié)點選擇簇內(nèi)通信代價最小亦即接收信號強度最大的簇首，發(fā)送加入消息JOIN_CLUSTER_MSG通知該簇首。這樣，網(wǎng)絡(luò)中的節(jié)點組成了Voronoi圖結(jié)構(gòu)的簇。接下來進入簇內(nèi)部的數(shù)據(jù)傳輸階段。簇首構(gòu)建TDMA調(diào)度，然后簇成員向簇首傳輸數(shù)據(jù)。本文采用與LEACH相同的組織方式，在此不再贅述。3.2 簇首間多跳路由協(xié)議在簇首將數(shù)據(jù)傳輸?shù)絽R聚點這個階段，簇首先對簇成員的數(shù)據(jù)進行融合處理，然后將數(shù)據(jù)以多跳通信的方式發(fā)送至匯聚點。由于傳感器網(wǎng)絡(luò)的這種獨特的“多對一”的數(shù)據(jù)傳輸模式，移動自組網(wǎng)絡(luò)中成熟的路由協(xié)議在此無法適用，傳感器網(wǎng)絡(luò)中已有的路由協(xié)議中也鮮有針對本文場景設(shè)計的算法。在有些文獻提出的傳感器網(wǎng)絡(luò)的多跳路由協(xié)議中，中繼節(jié)點對收到的數(shù)據(jù)進行數(shù)據(jù)融合，然后再繼續(xù)發(fā)送。本文假設(shè)數(shù)據(jù)的冗余度有限，來自不同簇的數(shù)據(jù)無法進一步融合，中繼簇首節(jié)點只是簡單轉(zhuǎn)發(fā)來自其它簇首的數(shù)據(jù)，如圖1所示。引入一個閾值TD_MAX.若簇首到匯聚點的距離小于TD_MAX,則它直接與匯聚點進行通信；否則應(yīng)該盡量使用多跳路由的方式將數(shù)據(jù)傳送給匯聚點。在路由算法開始時，每個簇首以相同的功率向全網(wǎng)廣播一條消息NODE_STATE_MSG,包含其ID、當(dāng)前剩余能量和它到匯聚點的距離。簇首Si收到簇首sj廣播的消息后，可以計算出它們之間的近似距離下文敘述當(dāng)d(Si,DS)TD_MAX時，簇首Si的路由選擇策略。Kawadia等在文獻指出，選擇鄰近的節(jié)點作為下一跳節(jié)點有利于減少通信干擾。本文將路由候選節(jié)點的選取范圍限制在比其自身更鄰近匯聚點的一個區(qū)域內(nèi)。4 EEUC的分析這一節(jié)給出非均勻分簇算法EEUC的一些分析和說明。該算法是消息驅(qū)動的，因此首先來分析它的消息復(fù)雜度。性質(zhì) 1. 在整個網(wǎng)絡(luò)中，EEUC算法的消息復(fù)雜度為O(N)。證明. 在算法開始，有NT個節(jié)點成為候選簇首而參與競選，共廣播NT條COMPETE_HEAD_MSG消息。然后，每個候選簇首或者廣播一條消息FINAL_HEAD_MSG以宣布其競選成功，或者廣播一條消息QUIT_ELECTION_MSG以宣布其退出競選。假設(shè)共選出k個簇首，則它們廣播k條CH_ADV_MSG消息，而N-K個簇成員廣播N-K條JOIN_CLUSTER_MSG消息。因此，網(wǎng)絡(luò)中總的消息開銷為NN+NT+k+N-k=(2T+1)N所以消息復(fù)雜度為0(N). 證畢。性質(zhì)1說明EEUC算法的消息開銷較小，能量高效。HEED的分簇算法也是消息驅(qū)動的，其消息交換次數(shù)的上界為NiterN, Niter是消息迭代的次數(shù)。因為EEUC避免了消息迭代，因此消息開銷低于HEED.由性質(zhì)1的證明可知，閾值T決定算法的消息開銷。選擇合適的T既可以讓大量剩余能量較高的節(jié)點參與競選過程，又不至于導(dǎo)致消息開銷過大。關(guān)于T的優(yōu)化取值，我們在先前工作中通過實驗給出了詳細(xì)的分析。接下來分析EEUC算法中的參數(shù)R0c和c的取值對網(wǎng)絡(luò)存活時間的影響。簇的成員數(shù)目之間的非均勻程度由c決定。c的值越大，候選簇首的競爭半徑的差異越大，因此簇的成員數(shù)目間的差異越明顯。而當(dāng)c等于0時，候選簇首的競爭半徑相同，算法將生成大小均勻的簇算法中所生成簇的數(shù)目由R0c和c共同決定。固定c,當(dāng)R0c增大時，每個候選簇首的競爭半徑隨之增大，因此所生成的簇的數(shù)目隨之減??；固定R0c，當(dāng)c增大時，每個候選簇首的競爭半徑隨之減小，因此所生成的簇的數(shù)目隨之增加。R0c和c的優(yōu)化取值可以優(yōu)化網(wǎng)絡(luò)中節(jié)點的能量消耗，延長網(wǎng)絡(luò)的存活時間。本文致力于設(shè)計非均勻分簇的算法，用理論化的方法選擇最優(yōu)的參數(shù)還在進一步的研究之中。在算法1中，候選節(jié)點需要等待其鄰簇首集合中所有能量比它大的節(jié)點先做出決策，然后才能確定自身能否擔(dān)任簇首。這要求算法確定一個全局一致的等待時間，超過此時間后算法終止。以圖3所示的網(wǎng)絡(luò)拓?fù)錇槔?，分析影響等待時間的因素。在圖3中，假設(shè)5個節(jié)點S1S5的剩余能量依次遞增。因此下列事件依次先后發(fā)生：S5宣布其成為簇首，S4退出競選，S3宣布其成為簇首，S2退出競選，S1宣布其成為簇首。算法從開始到結(jié)束共持續(xù)了4條消息的傳遞時間。這個例子說明算法需要等待的時間由網(wǎng)絡(luò)中候選節(jié)點構(gòu)成的單調(diào)能量鏈的最大長度決定。候選節(jié)點的剩余能量分布呈現(xiàn)隨機性，所以這條鏈越長，其出現(xiàn)的概率越低在文獻中，Basagni研究了移動自組網(wǎng)中一個分簇算法中類似的問題，并指出等待時間與網(wǎng)絡(luò)中的節(jié)點個數(shù)無關(guān)，而與網(wǎng)絡(luò)的能量拓?fù)溆嘘P(guān)。在本算法的實現(xiàn)中，我們將等待時間設(shè)為傳遞5次消息所需的時間，并且發(fā)現(xiàn)所有候選節(jié)點在這段時間內(nèi)都能正常做出競選決策。這說明EEUC分簇算法的時間開銷也較小。5 實驗結(jié)果及分析我們用C語言編寫模擬程序?qū)诜蔷鶆蚍执厮惴‥EUC的路由協(xié)議進行性能分析與評估。首先研究EEUC分簇算法所選擇的簇首的特征，然后分析協(xié)議的能量效率。為簡單起見，假設(shè)采用理想的MAC協(xié)議，忽略無線鏈路中可能發(fā)生的丟包錯誤。實驗中統(tǒng)計傳感器節(jié)點接收數(shù)據(jù)、融合數(shù)據(jù)和發(fā)送數(shù)據(jù)所消耗的能量，計算網(wǎng)絡(luò)的存活時間（用輪數(shù)表示），來分析協(xié)議的能量效率。為了證明本文提出的路由協(xié)議的能量高效，我們將EEUC與LEACH、LEACH-E、HEED和HEED-M 4種基于分簇的路由協(xié)議進行比較。為便于下文的分析，表1對這5種協(xié)議的特征進行了概括。在LEACH-E中，每個節(jié)點需要估計當(dāng)前網(wǎng)絡(luò)中所有節(jié)點的剩余能量之和；本文的實現(xiàn)方法是在每一輪的結(jié)束，簇成員將自己的剩余能量匯報給簇首，簇首將所有簇成員（包括自身）剩余能量之和匯報給匯聚點，然后匯聚點計算整個網(wǎng)絡(luò)的能量和，并廣播至所有節(jié)點。 實驗中所用的參數(shù)如表2所示，其中能量消耗模型相關(guān)的參數(shù)取自文獻6。除非特別指出，本協(xié)議的參數(shù)設(shè)置為T=0.4，R0c=90m,c=0.5,TD_MAX=140m.其它協(xié)議中的參數(shù)通過運行多次實驗來找出其最優(yōu)取值。5.1 簇首的特征由前一節(jié)的分析可知，EEUC分簇算法選取的簇首的數(shù)目由參數(shù)R0c和c共同決定。圖4顯示了c取兩個不同的值時，簇首的數(shù)目與R0c之間的關(guān)系。它驗證了前一節(jié)的分析，即競爭半徑越小，算法生成的簇首的數(shù)目越大在圖中，c0.5時對應(yīng)的曲線高于c=0時對應(yīng)的曲線這是因為當(dāng)R0c固定時，c的增大導(dǎo)致候選簇首的競爭半徑變小，因此簇首的數(shù)目增大。接著說明EEUC分簇算法的穩(wěn)定性。在網(wǎng)絡(luò)拓?fù)涔潭ǖ那闆r下，一個穩(wěn)定的分簇協(xié)議應(yīng)該生成數(shù)目比較一致的簇首，來優(yōu)化網(wǎng)絡(luò)的能量消耗。文獻6推導(dǎo)了單跳網(wǎng)絡(luò)中最優(yōu)簇首數(shù)目的近似計算公式。從每種分簇協(xié)議的模擬過程中隨機選出100輪，統(tǒng)計所生成的簇首個數(shù)的分布情況，結(jié)果見圖5.由圖可見，每種協(xié)議生成的簇首的數(shù)目都有一個期望值，它是協(xié)議在此場景下最優(yōu)的簇首數(shù)目。LEACH和LEACH-E的簇首數(shù)目的波動范圍比較大，這是因為LEACH和LEACH-E單純性地采用隨機數(shù)與閾值的機制產(chǎn)生簇首，因此簇首的數(shù)目變化比較明顯。HEED和EEUC的簇首數(shù)目非常集中于期望值，這是因為HEED和EEUC均采用了候選簇首在局部區(qū)域進行競爭的方法，有效地控制了算法所生成的簇首的數(shù)目。值得注意的是，EEUC生成的簇首數(shù)目多于HEED生成的簇首數(shù)目，這是因為EEUC構(gòu)造大小非均勻的簇，在靠近匯聚點的區(qū)域產(chǎn)生更多的簇首?？偟膩碚f，EEUC通過簡單的競爭算法生成了數(shù)目穩(wěn)定的簇，可靠性好。最后來比較各種分簇協(xié)議對網(wǎng)絡(luò)存活時間的影響。圖9顯示了網(wǎng)絡(luò)中存活的節(jié)點數(shù)目隨時間變化的情況。顯然，無論是第一個節(jié)點死亡的時間還是最后一個節(jié)點死亡的時間，EEUC均優(yōu)于其它4種協(xié)議。從第一個節(jié)點死亡到最后一個節(jié)點死亡的時間跨度可以反映出網(wǎng)絡(luò)中節(jié)點的能量均衡情況，跨度越短說明網(wǎng)絡(luò)的能量使用越高效。EEUC不僅顯著地延長了網(wǎng)絡(luò)的存活時間，而且時間跨度也遠(yuǎn)小于其它協(xié)議，這說明EEUC很好地均衡了網(wǎng)絡(luò)中所有節(jié)點的能量消耗。LEACH-E在選取簇首時雖然考慮了節(jié)點的剩余能量，但由于傳播能量消息帶來的開銷，其性能還略差于LEACH.HEED的第一個節(jié)點死亡時間明顯早于LEACH，但最后一個節(jié)點死亡的時間晚于LEACH，這表明HEED并沒有較好地均衡節(jié)點的能量消耗，造成有些節(jié)點過早死亡，這在圖7中也有對應(yīng)的說明。HEED-M由于采用了多跳通信，性能與HEED相比有了提高，但和EEUC仍有較大差距，這是因為它沒有考慮簇首的能量消耗均衡，造成部分節(jié)點過早失效。 總結(jié)實驗結(jié)果，本文提出的基于非均勻分簇的路由協(xié)議具有以下優(yōu)點：(1)分簇算法穩(wěn)定，所生成簇的數(shù)目波動??；(2)能量消耗低，且有效平衡了簇首的能量消耗；(3)顯著延長了網(wǎng)絡(luò)的存活時間?？傊?，用網(wǎng)絡(luò)的存活時間這一重要指標(biāo)來衡量，其性能明顯優(yōu)于其它四種分簇協(xié)議。6 結(jié)論和進一步的工作本文提出了一種新穎的基于分簇的傳感器網(wǎng)絡(luò)路由協(xié)議，其核心思想是利用一個能量高效的非均勻分簇算法EEUC將網(wǎng)絡(luò)組織成大小非均勻的簇，以解決多跳路由的傳感器網(wǎng)絡(luò)中常見的“熱區(qū)”問題。實驗表明，本路由協(xié)議優(yōu)化了網(wǎng)絡(luò)中的能量消耗，較好地解決了“熱區(qū)”問題；和已有的幾個分簇協(xié)議相比，顯著地延