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

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