分布式能量有效成簇路由算法研究

1設置了設置一個專門的wsn分簇作為一種新的獲取和處理形式，無線傳感器網絡（無線傳感器網絡，無線傳感器網絡）已成為國內外的研究熱點。WSN通過大量部署在監測區域內的傳感器節點,采集網絡覆蓋區域內感知對象的信息,通過多跳的無線通信方式,將收集、處理后的信息提供給終端用戶。WSN不需要固定的網絡支持,具有快速展開、抗毀性強等特點,可廣泛應用于軍事偵察、環境監測、醫療監護、農業養殖和其他商業領域,以及空間探索和災難搶險等特殊領域。在WSN體系結構中,網絡層的路由技術對WSN的性能好壞有著重要影響。隨著國內外WSN的研究發展,許多路由協議被提了出來。由于傳感器節點本身資源的限制,針對adhoc網絡的分簇算法不能被直接利用,特別是WSN節點能量更為有限,因此必須研究新的分簇算法。LEACH(low-energyadaptiveclusteringhierarchy)是WSN中最早提出的分簇路由協議。它的成簇思想貫穿于其后發展出的很多分簇路由協議中,如TEEN(thresholdsensitiveenergyefficientsensornetworkprotocol)、HEED(hybridenergy-efficientdistributedclustering)等。另外,還有一些獨立開發的分簇路由協議,如ACE(algorithmforclusterestablishment)、LSCP(lightweightsensingandcommunicationprotocols)等。2相關研究傳感器網絡成簇算法發展迅速,按照成員節點到基站的跳數,簇的結構一般分為單跳和多跳網絡。2.1基于剩余能量的分布式聯合打造LEACH是最早提出的單跳分簇算法,其基本思想是:通過等概率地隨機循環選擇簇頭,將整個網絡的能量負載平均分配到每個傳感器節點,從而達到降低網絡能量耗費、延長網絡生命周期的目的。近幾年,提出了許多LEACH的改進算法,其中包括EECS、LEACH-B等,在不同方面改進了LEACH算法的性能。在EECS中,節點在選擇簇頭時不是簡單地選擇距離自身最近的簇頭,而是考慮了候選簇頭到基站距離的遠近,構造出相應的簇,均衡簇頭的負載。但該協議只能平衡簇頭地區的能量分布,缺乏對全網消耗能量的平衡。文獻提出一種根據節點剩余能量選舉簇頭的算法,缺點在于每個節點需要知道當前網絡的總能量,而難以分布式實現。SEP則是針對二級異構網絡設計的,即網絡中只有2種不同初始能量的節點。DEEC算法針對一般性的多級異構網絡設計,不適用于同構傳感器網絡。DCHS引入了能量閾值,延長了網絡的生存周期,但該算法未考慮平衡全網能量。HEED也是一種完全分布式的成簇算法,它隨機選擇簇頭節點,選舉概率與該節點的剩余能量直接相關。HEED算法首先根據節點的剩余能量來概率性地選取一些候選簇頭,然后以簇內部通信代價的高低來競爭產生最終簇頭。簇生成算法需要在簇半徑內進行多次消息迭代,由此帶來的通信開銷比較顯著。上述的這些協議均通過周期性地重新分簇,讓節點輪流擔任簇頭,達到節點均衡地消耗能量的目的。2.2apteen協議多跳網絡的簡介PEGASIS則將節點組織成鏈的形式,鏈的形成由每一個節點或者基站計算得到,因此需要知道網絡拓撲的全局知識。文獻研究了多跳簇結構網絡,并使用一種隨機成簇方案來組織傳感器節點。TEEN協議適用于實時性要求較高的應用場合,用戶可以及時獲取感興趣的信息,它設置了硬、軟2個閾值,以減少發送數據的次數。通過調節2個閾值的大小,可以在精度要求和系統能耗之間取得合理的平衡。但TEEN存在3個缺陷:一是如果閾值不能達到,節點不會傳送任何數據;二是數據一旦符合閾值要求,節點立即傳送,容易造成信號干擾,如果采用TDMA,則會造成數據延遲;三是該協議的閾值選擇是非常困難的。APTEEN協議的功耗相對降低,增加了網絡的生命周期。對于實時性要求不高的查詢,時延可以大一些,這可以使生命周期增加近一倍,但APTEEN協議的實現難度比較大,給實際應用帶來了困難。ECMR(energy-consciousmessagerouting)是多跳的路由傳輸協議。ECMR假設簇頭預先部署,能量不受限,能與成員節點直接通信,而成員節點需多跳路由才能到簇頭。ECMR由簇頭采用Dijkstra算法求解。其中,節點i和j之間鏈路的權值定義不僅計算了它們之間的通信耗費,也考慮了節點能量、數據延遲和鏈路負載等因素。ECMR在運行過程中具有良好的節能性能、較高的吞吐量和較低的通信延遲。但是,該協議擴展性較差,需要部署新的簇頭來擴展網絡,而且對簇頭依賴性大,不支持節點移動。在文獻中,李成法等人提出了基于競爭的多跳非均勻分簇算法,仿真結果顯示了較好的效果,但該算法中的參數選取主要憑經驗給出,理論分析不夠,需要進行深入研究。另外,基于競爭產生簇頭仍然存在能量浪費問題,因為候選簇頭數量較多,需要競爭的次數較多,因此需要繼續深入研究。M-LEACH針對多跳網絡,算法比較復雜。文獻引入了能量和距離閾值以均衡全網能量消耗,但算法未考慮全網的能量分布情況。對于單跳成簇算法,操作簡單,時延小,適合于實時性較強的網絡,缺點是向基站傳輸數據時需要消耗更多的能量。多跳成簇算法一般較復雜,實現難度較大,時延較大。本文主要研究單跳成簇算法,試圖尋找一種較為合理的思路延長網絡的生命周期。然而,從均衡節點的能量消耗以延長網絡的存活時間這個目標看,先前的研究主要集中于均衡簇成員節點之間的能量消耗,沒有考慮到簇頭間的能量消耗均衡問題。本文提出的DEEUC算法是為同構單跳網絡而設計的。它借鑒了LEACH的簇頭輪轉思想,同時讓簇頭節點的選舉與節點剩余能量直接相關,避免了同構成簇算法所遇到的問題。DEEUC還保留了分布式算法的優點,不需要中心機構在網絡操作過程中提供全局信息。3基于平均能量的引領性選舉算法本文引入平均能量閾值的核心思想是根據節點的剩余能量來合理選擇簇頭,剩余能量高的優先選擇為簇頭,最終能有效地平衡全網能量,基于此,提出了基于全網平均能量的簇頭選舉算法,類似于LEACH-C,但克服了必須向基站傳送剩余能量的問題,引入估計方法,避免了LEACH-C的能量消耗問題。簇頭選好后,對于加入簇的節點來說,加入那個簇是平衡全網能量的關鍵因素,本文提出了基于距離和能量因子的能量消耗率函數,有效地延長了網絡的生命周期。3.1有節點的數據融合模型研究的網絡分布在一正方形區域內,由N個隨機分布的傳感器節點組成,其應用場景為周期性的數據收集。用in表示第i個節點,相應的節點集合為Node={n1,n2,…,nN},|Node|=N。假設如下。1)基站位于一個方形觀測區域的外側,傳感器節點和基站BS在部署后均不再發生位置移動。2)所有節點都是同構的且能量有限,具備數據融合的功能。每個節點都有唯一的標識(ID)。3)所有節點都能夠一跳到達基站(BS)。4)每個節點沒有位置信息。5)根據接收者的距離遠近,節點可以自由調整其發射功率以節約能量消耗。6)鏈路是對稱的,若已知對方發射功率,節點根據接收信號強度RSSI計算出發送者到自己的距離。采用與文獻相同的無線通信能量消耗模型,如圖1所示。節點發射Lbit的數據到距離為d的位置,消耗的能量由發射電路損耗和功率放大損耗2部分組成,即其中,Eelec表示發射電路損耗的能量。若傳輸距離小于閾值do,功率放大損耗采用自由空間模型;當傳輸距離大于等于閾值do時,采用多路徑衰減模型。εfs、εmp分別為2種模型中功率放大所需的能量。節點接收Lbit的數據消耗的能量為數據融合也消耗一定的能量,用EDF表示融合單位比特數據消耗的能量。假設鄰近節點采集的數據具有較高的冗余度,簇頭可以將其成員的數據融合成一個長度固定的數據包,然后發送給基站(BS)。3.2成簇算法deeuc在網絡建立階段,基站(BS)需要用一個給定的發送功率向網絡內廣播一個信號。每個傳感器節點在接收到此信號后,根據接收信號的強度計算它到基站的近似距離。獲得這個距離不僅有助于傳感器節點向基站傳輸數據時選擇合適的發送功率以節約能量消耗,而且它還是算法構造簇的必要信息之一。圖2給出本文提出的基于平均能量的成簇路由算法的示意圖,其中不規則的多邊形圍成的小圖形表示簇頭節點的覆蓋范圍,帶箭頭的直線表示簇頭向基站單跳數據傳輸。從圖2可以看出,成簇算法是使遠離基站的節點盡量少成為簇頭以減少能量消耗,在每一個簇頭覆蓋范圍內盡量選取能量高的作為簇頭。DEEUC每輪循環的基本過程是:在簇建立階段,基站(BS)每個節點選取一個介于0和1之間的隨機數,如果這個數小于某個閾值,該節點成為候選簇頭。然后,通過競爭算法確定最終的簇頭,簇頭向周圍節點廣播自己成為簇頭的消息。每個節點根據提出的能量消耗率函數來確定加入哪個簇,并回復該簇簇頭。在數據傳輸階段,簇內的所有節點按照TDMA(時分復用)時隙向簇頭發送數據。簇頭將數據融合之后把結果發給基站。在持續工作一段時間之后,網絡重新進入啟動階段,進行下一輪的簇頭選取并重新建立簇。3.3節點選取引領性算法候選簇頭的產生是簇形成的基礎,產生候選簇頭時,每個節點產生一個0~1之間的隨機數,如果節點n產生的隨機數小于閾值T(n),則該節點向周圍節點廣播它是候選簇頭的消息。由于LEACH算法沒有考慮剩余能量和距離因素,因此改進了LEACH的T(n)計算公式,將平均能量因素考慮進來,使能量消耗比例較低的節點優先當選為候選簇頭。在候選簇頭選舉算法中引入的關鍵參數如下:其中,E(i)residual表示第i個節點的剩余能量,E(r)表示第r輪網絡平均剩余能量。Energy因子主要用來平衡全網剩余能量。定義從第一輪選擇簇頭開始到第一個節點死亡(能量消耗盡)的輪數,稱為網絡生命周期。通過以上分析發現,引入Energy閾值因子后,能夠有效地降低全網的能量消耗,延長網絡的生命周期。式(4)給出了新構造的閾值計算公式T(n)new。其中,p是簇頭占所有節點的百分比,即節點當選簇頭的概率;r是目前循環進行的輪數;G是最近1/p輪中還未當選過簇頭的節點集合。從T(n)new可以看出,當選過候選簇頭的節點在接下來的1/p輪循環中將不能成為簇頭,剩余節點當選簇頭的閾值T(n)new增大,節點產生小于T(n)new的隨機數的概率隨之增大,所以節點當選候選簇頭的概率增大。p值決定了每輪產生的候選簇頭數量,在應用中,最佳p值的確定十分困難,這與網絡規模和節點密度有關。3.4傳感器網絡平均能量平均能量的計算需要全網節點的剩余能量信息,這是非常困難的,特別是對于節點密集型傳感器網絡。一方面要有相應的通信協議支持該數據的傳送,另一方面即使有如此協議進行通信,對于基站(BS)來說,收集如此密集數據的開銷也是十分驚人的,因此必須考慮其他途徑獲得平均能量信息。引入估計方法,對平均能量進行相應估計。假設每輪傳感器網絡消耗相同的能量,這種假設是合理的,因為每輪的簇頭數量相近,通信開銷相近。假設傳感器節點均勻分布在M×M的正方形中,節點數設為N個,初始能量相同。每輪中消耗的能量包括2部分:簇頭消耗的能量ECH和非簇頭消耗的能量Enon-CH,設傳感器網絡每輪消耗的能量為Eround,則有對于傳感器簇頭而言,在一輪中消耗的能量ECH為對于傳感器非簇頭節點而言,在一輪中消耗的能量Enon-CH為其中,k為簇頭的數量,dtoCH為節點到簇頭的平均距離,dtoCH為簇頭到基站的平均距離,如果這3個參數可以估計,那么每輪的能量Eround就可以估計。在文獻中,作者已經估計了dtoCH和參數k分別為在文獻中,作者估計了參數dtoCH為把式(6)、式(7)、式(8)、式(9)、式(10)代入式(5),從而可以粗略估計出全網一輪消耗的能量,進而估計出全網剩余的平均能量為其中,Etotal為全網初始能量,r為輪數。3.5簇頭選擇過程候選簇頭產生后,引入競爭算法獲得最終的簇頭。首先使每個候選簇頭以R(R為競爭半徑)為半徑廣播競爭消息,如果si、sj為候選簇頭,設以sj為核心,R為半徑的特定面積內的候選簇頭組成集合sj.ACH,在該面積內選擇剩余能量最多的候選簇頭作為最終簇頭(如果最大能量有多個相同,選擇第一個候選簇頭作為最終簇頭),然后將此面積內的其他候選簇頭刪除(即設置成簇成員節點),最后最終簇頭以dn_CH(簇成員節點到達特定簇頭的最大距離)為半徑廣播競選成功消息,完成簇頭選擇過程。在競爭過程中,競爭半徑的選取是非常重要的,下面作簡單說明。引入非均勻簇機制,目標是讓靠近基站(BS)的簇的成員較少,使其簇頭能夠預留部分能量供簇頭與基站間通信使用。遠離基站的簇頭的成員較多,這樣可以減少簇頭與基站之間的通信次數,降低能量消耗,因為遠距離通信消耗更多的能量。因此,靠近基站(BS)簇頭的競爭半徑應該較小。亦即,隨著候選簇頭到基站(BS)距離的減小,其競爭半徑應該隨之減小。記候選簇頭競爭半徑的最大取值為Rmax,最小取值為cR。算法需要控制競爭半徑的取值范圍,使得距離基站最遠節點的競爭半徑為(1+c)cR,其中c是用于控制取值范圍的參數,取值范圍為,c越大競爭半徑越大,簇頭消耗能量越大,根據選取的場景,c取值為1。候選簇頭si確定其競爭半徑si.R的計算公式如式(12)所示。其中,dmax和dmin分別代表網絡中的節點到基站(BS)距離的最大值和最小值,d(si,BS)代表節點si到基站(BS)的距離。競爭半徑與節點到基站的距離呈線性遞增關系。3.6獲得能量的需求簇頭選好后,節點如何加入簇頭是非常關鍵的,這直接關系到平衡當前簇頭地區的能量消耗。例如在圖2中節點i是加入簇頭5還是6,必須由能量消耗率函數決定。直觀上該節點加入簇頭5,因為距離簇頭5最近,但這不利于平衡全網能量消費。定義的能量消耗率函數f(i,j)為其中,1≤i≤CM,CM為加入第j個簇頭的簇成員數量,1≤j≤CH,CH為簇頭數量。節點i加入簇頭CHj的條件就是使能量消耗率函數f(i,j)最小。其中iE表示節點i的當前能量,ECHj表示簇頭j的當前能量。其中其中,d(CHj,BS)表示第j個簇頭到基站(BS)的距離,。d(ni,CHj)為節點i到簇頭j的距離,。提出的能量消耗率函數f既引入了距離因素,又引入了能量因素,直觀上更能有效平衡當前簇頭區的能量消耗。簡單說明如下。選擇簇成員的標準是使能量消耗率函數f(i,j)最小,則有為分析方便將常數合并,則有由于每輪中簇成員節點都要與簇頭通信,簇頭都要與基站(BS)通信,因此有等價變換為下式:上式中εfsd2(ni,CHj)是簇成員消耗能量的關鍵部分,εmpd4(CHj,BS)是簇頭消耗能量的關鍵部分。直觀上,只要能量消耗率函數最小,簇成員和簇頭消耗能量均最低,繼而全網消耗能量最低,因此能有效延長網絡的生命周期。反之,如果簇成員和簇頭消耗能量均最低,那么能量消耗率函數f(i,j)必定最小。3.7deeuc算法DEEUC是一個分布式動態算法,以節點的剩余能量和節點到簇頭的距離為主要參數來選取簇頭。在成簇算法中,簇頭是非常重要的,因為簇頭在每輪中完成最多的任務,消耗最多的能量。簇頭選舉算法包括2個階段:候選簇頭產生和最終簇頭產生階段。在選擇候選簇頭時,基站(BS)向每一個節點廣播平均能量消息,在選擇候選簇頭過程中用平均能量參數來約束候選簇頭的選擇,大于平均能量的節點優先選擇為候選簇頭,由于平均能量是全網的信息,因此可以有效地描述全網的能量狀態。當候選簇頭選好后,算法便進入最終簇頭產生階段。引入基于競爭機制的簇頭選舉算法來獲得最終的簇頭,選好的簇頭向它周圍的節點廣播加入消息,周圍節點可以根據所提出的能量消耗率函數選擇加入的簇頭,隨后節點向選擇的簇頭發送應答消息,確認自己加入該簇,完成簇的建立,最后將完全融合后的數據直接發送給基站,完成一輪的數據傳送工作,等待進入下一輪。但是對于簇成員的能量消耗也是不能忽略的,因為簇成員也有可能成為簇頭。在EECS算法中,選擇簇頭時,主要在候選簇頭里選擇真正的簇頭,但是對于候選簇頭而言并不一定是所有節點中剩余能量較高的,對于此算法而言由于引入了平均能量閾值,使得選取的候選簇頭是剩余能量最高的,保證了候選簇頭的高能量特性,因此算法具有很好的結果。算法1給出了整個算法的偽碼,sj.ACH表示以候選簇頭sj為中心,以sj.R為半徑的所有候選簇頭集合。算法1DEEUC算法偽碼在此算法中,每個節點均以同樣的功率發送廣播消息,為了節約能量,這個廣播半徑為Rmax(Rmax為最大簇頭半徑)即可。算法首先根據閾值大小和節點的剩余能量狀態,產生候選簇頭;然后通過競爭算法獲得最終簇頭;最后每個簇頭廣播HEAD_MSG消息,消息的內容為節點的ID、節點到達簇頭的最大距離dn_CH(為節約能量使dn_CH=Rmax即可)。節點根據收到的廣播消息計算能量消耗率函數f(i,j),選擇f(i,j)最小的簇頭加入,最后發送加入消息JOIN_ClusterHead_MSG,通知該簇頭。簇頭選擇完成后,節點根據能量消耗率函數選擇加入的簇頭,進入簇內數據傳輸階段,簇頭構建TDMA調度,然后簇成員向簇頭傳輸數據。性質在所選網絡中,DEEUC算法的消息復雜度為O(N)。證明首先,基站(BS)廣播一條平均能量AE_MSG消息給每個節點。其次,有N×Threshold個節點成為候選簇頭,共廣播N×Threshold條COMPETE_HEAD_MSG消息,然后每個候選簇頭廣播一條FINAL_HEAD_MSG消息宣布其競選成功,或者廣播一條QUIT_MSG消息宣布其退出競選。假設共選出k個簇頭,每個簇頭廣播一條HEAD_MSG消息,而N-k個非簇頭節點廣播一條JOIN_ClusterHead_MSG消息。因此消息開銷為所以消息復雜度為O(N)。性質說明DEEUC算法的消息開銷比較小,進而算法具有較好的能量效率。HEED的簇生成算法需要在簇半徑內進行多次消息迭代,由此帶來的通信開銷比較顯著,一般其消息交換次數的上界為Niter×N,Niter是消息迭代的次數。因為DEEUC算法避免了消息迭代,因此消息開銷低于HEED。對于EECS算法來說,消息復雜度也為O(N),與此算法相同,但由于EECS算法在選擇簇頭時未考慮簇頭到基站(BS)的距離,因此未能有效地平衡簇頭能量的消耗。4deeuc算法的性能比較為了說明算法效果,使用MATLAB對算法進行了仿真測試,選擇的仿真場景參數如表1所示。算法中能量消耗率函數參數w的選擇是十分重要的,因為w是平衡簇頭和簇成員之間的權值,從0.1到1范圍內進行實驗,結果如圖3所示,可以看出,w=0.5或w=0.6效果最好,在文中選擇w=0.6。比較LEACH-C、EECS和DEEUC3種算法。圖4是3種算法生命周期的比較,從圖中可以看出,DEEUC生命周期最長,EECS次之,LEACH-C最差,其中DEEUC比LEACH-C的生命周期至少長45%以上,比EECS的生命周期延長達到約30%。從死亡節點的數量來看,DEEUC在1200輪時死亡節點數量不到20個節點,約占總節點數的2%,EECS死亡約170個節點,占總節點數的17%,LEACH-C最多死亡約390個節點,至少占39%,死亡節點數可以反映出網絡中節點的能量均衡情況,死亡越少說明網絡的能量使用效率越高。DEEUC不僅顯著地延長了網絡的生命周期,而且死亡節點數也遠小于其他算法,這說明DEEUC很好地均衡了網絡中所有節點的能量消耗。EECS已經引入了花費函數,但其性能略差于DEEUC,原因可能主要有3點:一是候選簇頭的選取未充分考慮全網的能量利用情況;二是花費函數中僅注意到了距離因素,未考慮節點和簇頭的剩余能量因素;三是簇頭選舉時未考慮候選簇頭到基站(BS)的距離因素。LEACH-C在選取簇頭時雖然考慮了節點的剩余能量,但由于其簇頭數量波動較大,因此傳播消息帶來的能量開銷最大,導致其性能最差。圖5是簇頭數量的比較,從圖中可以看出,DEEUC和EECS算法產生的簇頭數量穩定,LEACH-C簇頭數量的波動范圍最大,這是因為LEACH-C單純性地采用隨機數與閾值的機制產生簇頭,因此簇頭的數量變化比較明顯。DEEUC和EECS的簇頭數量比較集中,這是因為2種算法均采用了候選簇頭在局部區域進行競爭的方法,有效地控制了算法所生成的簇頭的數量。但是,DEEUC算法產生的簇頭數量更集中于簇頭數量的期望值,主要原因是提出的能量消耗率函數能更有效地刻劃網絡性能,使簇頭分布和數量較為準確地描述了網絡特性,因此簇頭分布和數量能穩定更長的時間。圖6是節點到簇頭的信息量比較,從圖中可以看出,DEEUC和EECS在第一個節點死亡之前的信息量是非常接近的,但是由于EECS生命周期小于DEEUC,當存在死亡節點時,DEEUC的信息量略大于EECS,在約850輪以后,信息量明顯大于EECS,原因是EECS死亡的節點數增加很快,導致節點到簇頭的信息量