無線傳感器網絡中l(wèi)ech協(xié)議能量均衡算法

無線傳感器網絡中l(wèi)ech協(xié)議能量均衡算法

無線傳感器網絡（wsd）被認為是本世紀最具影響力的21個技術和變化世界的前21個技術之一。wsd是大量小型傳感器節(jié)點在特定區(qū)域提供的信息。無線通信模式下，可以創(chuàng)建網絡、感知、收集和處理環(huán)境信息或監(jiān)測對象信息。由于節(jié)點體積大、成本低、部署方便，無線傳感器網絡具有許多應用價值。例如，軍事國防、災難報警、環(huán)境準備、醫(yī)療和工業(yè)。傳感器網絡節(jié)點通常采用電池供電,監(jiān)測周期往往較長,所以低功耗研究一直是WSN的一個熱點,如何高效使用能量來最大化網絡生命周期是WSN的關鍵.WSN的路由協(xié)議可以分成平面路由協(xié)議和分層路由協(xié)議兩種.由于平面路由協(xié)議需要維持較大的路由表,占據較多的存儲空間,從而需要消耗較多的能量;而分層路由協(xié)議卻可以在一定程度上解決這個問題.LEACH(Low-energyadaptiveclusteringhierarchy)是比較成熟的分簇算法,它采用分層的網絡結構,由中心、簇首和簇內成員共同構成兩層關系的網絡.各節(jié)點獨立地按照一定概率自行決定是否成為簇首,并且周期性地進行簇首選舉和網絡重組,以避免簇首節(jié)點能耗過多,影響整個網絡壽命.LEACH算法是一種比較成熟的算法,通過對LEACH協(xié)議進行改進優(yōu)化,又衍生出如:LEACH_C和LEACH_M等算法.MIT學者Heinzelman等在LEACH算法的基礎上提出了LEACH-C算法,解決了LEACH算法中“節(jié)點根據隨機數(shù)決定是否當選為簇首”以及“每輪產生的簇首沒有確定的數(shù)量和位置”等方面的問題,大大提高了簇的生成質量.但由于每個節(jié)點都須向基站周期性地報告它們的能量和位置等信息,成簇開銷較大,網絡流量、時間延遲以及信號干擾的概率都會增加.LEACH-M算法綜合LEACH協(xié)議的不足,為了使簇首比較均勻的分布在網絡中,并且防止能量少的節(jié)點成為簇首,LEACH-M算法采用遺傳模擬退火算法來提高簇的生成質量.該算法中每個節(jié)點把自身地理位置和當前能量報告給基站,基站根據所有節(jié)點的報告計算平均能量,當前能量低于平均能量的節(jié)點不能成為候選簇首,由于LEACH-M的算法在每輪簇首選舉中仍然需要每個節(jié)點對中心通信,LEACH-M的成簇開銷和信號干擾概率仍然是一個問題.LEACH-C算法和LEACH-M算法成簇開銷大,全網節(jié)點與中心通信不可避免地加大了信號干擾,本文提出一種簡化的簇頭選舉改進算法LEACH-ER,在簇頭選舉階段網絡產生多于期望值的候選簇頭,由這些節(jié)點向中心匯報信息,普通節(jié)點在此階段進入睡眠狀態(tài)以節(jié)省能量損耗.同時中心節(jié)點基于各候選簇首的動態(tài)權值選擇較優(yōu)的簇頭組合,所以在簇頭選舉階段只需少量的候選簇首與中心通信匯報信息,從而避免了全網節(jié)點與中心通信.仿真證明,LEACH-ER算法與LEACH算法相比,優(yōu)化了簇首分布,提高了能量利用率,延長了網絡生命周期.1基于le未來的多跳路由和分簇的可選擇性評估LEACH是為WSN設計的一種低功耗自適應分層路由協(xié)議.算法中,相鄰節(jié)點動態(tài)形成簇,并隨機地由簇中的某個節(jié)點擔任簇首.所有非簇首節(jié)點把數(shù)據發(fā)送到簇首,簇首對接收到的數(shù)據進行處理后將結果發(fā)送到匯聚節(jié)點.LEACH定義了“輪”的概念,每一輪由簇首準備階段和穩(wěn)態(tài)階段組成.在簇首準備階段,傳感器節(jié)點n根據當前節(jié)點狀態(tài)計算T(n),并隨機產生一個(0,1)之間的隨機數(shù)與T(n)比較,如果小于該閾值則當選簇首.T(n)按照下列公式計算:T(n)={p1?p×(rmod(1p)),n∈G0,n?G(1)Τ(n)={p1-p×(rmod(1p)),n∈G0,n?G(1)p是算法希望每輪選舉節(jié)點成為簇首的概率,r是當前的輪數(shù),G是最近rmod(1p)rmod(1p)輪內未當選簇首的節(jié)點.簇首節(jié)點選定后廣播自己成為簇首的消息,其他未成為簇首的節(jié)點根據收到消息的信號強度決定加入哪個簇,簇首收到其他節(jié)點的請求后根據TDMA方式為其分配一個傳輸數(shù)據的時隙.在穩(wěn)定階段,節(jié)點持續(xù)采集監(jiān)測數(shù)據并傳送到簇首,由簇首對數(shù)據進行必要的融合處理之后,發(fā)送到匯聚節(jié)點.期間,簇內成員按只能在特定的時隙內向簇首節(jié)點發(fā)送數(shù)據.簇首節(jié)點收集數(shù)據進行數(shù)據融合后將信息傳送給匯聚中心.穩(wěn)定階段結束后,網絡重新進入下一輪的簇首準備階段,重新選舉簇首,不斷循環(huán).LEACH與一般的平面多跳路由協(xié)議和靜態(tài)分簇算法相比,較好地解決了能量有效問題,它可以將網絡生存時間延長15%.但是,隨機產生簇首并不能保證每輪簇首節(jié)點的數(shù)目和分布,LEACH忽略節(jié)點剩余能量和地理位置信息,容易造成距離基站遠的簇首節(jié)點能耗大、網絡內節(jié)點能量損耗不均等問題,降低網絡能量的利用率,影響網絡的整體性能.具體而言,在簇首選舉算法上LEACH協(xié)議存在的兩大缺點有:1)簇首數(shù)目不確定.在LEACH協(xié)議中,通過計算及仿真驗證了對于大型傳感器網絡,5%的節(jié)點作為簇首是最優(yōu)的結果,此時網絡性能可以達到最好,產生的簇首過多或過少都會降低能量利用率.LEACH協(xié)議采用隨機選舉簇首的方式雖然避免了簇首選舉時的能量消耗,但采用隨機的方式選舉簇首存在一定的方差,實驗表明在100個節(jié)點組網的例子中產生簇首數(shù)目與最優(yōu)簇首數(shù)相同的概率只有約12%.2)簇首選舉忽略簇首剩余能量和簇首之間的地理位置分布.所有節(jié)點以相同的概率成為簇首缺乏對節(jié)點能量特性的考慮,簇首選舉時忽略簇首的地理位置,節(jié)點的分布往往是不規(guī)則的,這可能導致某些簇的成員個數(shù)過于龐大,簇首因能量消耗過快而失效,在極端情況下還可能導致網絡的某一區(qū)域因為失效節(jié)點過多而失去感知信息的能力.單純依靠隨機方式產生簇首雖然大大減少了控制信息帶來的消耗,但付出的代價是能量利用率的下降.2cch的信號處理針對第一節(jié)提出的LEACH存在的兩個問題本文提出基于候選簇首的剩余能量和候選簇首間地理位置RSSI信息的簇首選舉改進算法LEACH-ER(LEACHbaseonenergyandRSSI),設全網節(jié)點數(shù)為N,與LEACH算法不同的是LEACH-ER算法以2p的概率產生候選簇首,中心節(jié)點根據候選簇首的權值從中選出k個簇首,其中k=N×p,算法流程如圖1所示,具體算法描述如下,為敘述方便下文提到的候選簇首用CCH表示,最終簇首用FCH表示:1)組網開始時,各節(jié)點按照概率決定自己是否為CCH,若是則向中心發(fā)送CCHAnoce,同時偵聽截獲其余CCH的信息,比較選出離自身最近的兩個鄰簇首的RSSI信息.2)各CCH構造關聯(lián)鄰簇首信息表NeibCCHList并發(fā)給中心節(jié)點,NeibCCHList格式如下:(Ei,NeiborCH1,NeiborCHRSSI1,NeiborCH2,NeiborCHRSSI2),(2)其中Ei表示第i個CCH的剩余能量,NeiborCH1,NeiborCH2為離本CCH最近的兩個鄰居CCH的ID.NeiborCHRSSI1,NeiborCHRSSI2表示這兩個鄰居CCH到本CCH的信號強度,該值標識兩個鄰簇首與當前簇首在地理位置上的關聯(lián)程度.3)中心節(jié)點收集各CCH的信息,根據權值公式計算每個CCH的初始權值.Wi=α(Ei)+β(RSSIi),(3)其中Wi表示第i個CCH的初始權值,RSSIi表示第i個CCH到達中心節(jié)點的接收信號強度,α,β為權系數(shù).考慮到簇首個數(shù)的隨機性,當網絡產生的CCH個數(shù)不超過k時,直接轉入步驟5).4)中心節(jié)點根據每個CCH的初始權值Wi開始選舉本輪的FCH,算法選出權值最大的一個CCH并授權其為FCH,同時查找其關聯(lián)的兩個鄰CCH,參照修正權值公式(4)降低它的權值,降低已選簇首最近的兩個簇首的權值,以期得到一個均勻分布的簇首組合.WNeiborCH′=WNeiborCH-β(NeiborCHRSSI).(4)修正權值之后,繼續(xù)本步驟選舉簇首直到k個FCH全部選出.5)產生k個簇首之后,中心節(jié)點廣播FCH列表信息,其余落選CCH轉為普通節(jié)點.本算法在初始權值的基礎上根據已選簇首修正其最近鄰CCH的權值,使得最終確定下來的簇首組合分布均勻,并且剩余能量相近的情況下偏遠節(jié)點當選簇首的概率較小.3leah改進算法的模擬和分析3.1ns3軟件簡介NS3(Networksimulator3)是為了符合更多、更有彈性的網絡模擬需求所設計的一套新的模擬軟件,并非是延續(xù)NS2的版本.NS3的設計始于2006年7月,到目前為止已經發(fā)布了3個版本.NS3與目前流行的網絡模擬器NS2相比最大的差異是NS3再也沒有Tcl,OTcl了,NS2采用分裂對象模型,使用C++和腳本語言OTCL完成,軟件結構相對松散,各個分析工具軟件‘各自為政’,學習起來有相當?shù)碾y度,NS3改用C++或pythonscript來撰寫代碼.NS3具有的便捷性符合WSN協(xié)議的靈活多變的特點,所以本文選擇NS3作為仿真軟件.3.2基于leah協(xié)議的建模和模擬3.2.1sn的基本原理在對LEACH協(xié)議和改進算法LEACH-ER進行仿真之前,必須對能量消耗模型進行建模.本文假設在該WSN中,發(fā)送機和接收機的框圖如圖2所示,接收一條長為l的數(shù)據包,接收機消耗能量如公式(5),其中Eelec為電路消耗:ERX(l)=Eelecl.(5)發(fā)射機發(fā)送一條長l為的數(shù)據包,消耗能量如公式(6),其中具體參數(shù)說明見表1.ETX(l,d)=Eelecl+εampld2.(6)3.2.2基于nsma/ca的數(shù)據沖突機制在簇頭選舉階段,各節(jié)點按照CSMA/CA退避算法選擇并接入簇頭,在數(shù)據傳輸階段各節(jié)點在所分配的時隙里與簇頭通信,所以數(shù)據沖突與重發(fā)主要集中在簇頭選舉階段,本文利用NS3仿真軟件的內核機制和C++編程的靈活性構建了CSMA/CA信道訪問機制.MAC層信道機制的完善保證了本文仿真的可靠性和仿真結果的準確性.3.2.3中心節(jié)點位置參數(shù)值仿真場景中將100個節(jié)點隨機分布在(0,0)為圓心,以80m為半徑的圓形區(qū)域內,中心節(jié)點在圓心處,節(jié)點靜止.其他參數(shù)值為:Gt=Gr=1,其中Gt表示發(fā)送方天線增益;Gr表示接收方天線增益.3.2.4網絡運行期仿真本文仿真了LEACH-ER協(xié)議,并將其與LEACH協(xié)議進行對比.在相同的初始條件下分別仿真對比算法改進前后網絡各方面的性能.在比較網絡壽命時,本文仿真記錄網絡前40個節(jié)點失效的時間及順序.圖3是算法改進前后網絡存活節(jié)點數(shù)的對比.由圖可見,與原始的LEACH算法相比算法改進后性能明顯提高,若以網絡第一個節(jié)點數(shù)失效為時間參考點LEACH-ER算法第一個節(jié)點數(shù)失效的時間比LEACH算法延長了9.19%,這一結果顯示了算法在均衡網絡節(jié)點能量負荷方面的貢獻.圖4是網絡運行初期各候選簇首節(jié)點和當選簇首節(jié)點的分布圖,由于網絡運行初期各節(jié)點剩余能量相近,所以此對比主要驗證LEACH-ER在均衡簇首地理位置方面的性能.由于LEACH算法是隨機產生期望值為k的簇首,每輪產生的簇首數(shù)目會在k值附近波動,并且隨機方式產生簇首容易導致簇首分布過密或偏遠節(jié)點當選為簇首等問題.LEACH-ER簇首選舉算法通過修正的權重算法避免了簇首節(jié)點分布過密或當選簇首偏遠等問題,優(yōu)化了簇首地理位置分布.假設當網絡中的40%的網絡節(jié)點失效時網絡正常工作的終止時間,同時設定LEACH和LEACH-ER的網絡運行周期一致,即每個loop的時長相同,本文對比了算法改進前后網絡正常工作期間網絡節(jié)點的總能量,從圖5(a)仿真曲線可見,LEACH-ER算法有效地節(jié)約了能量.圖5(b)將圖5(a)中網絡運行后期的能量對比放大,可以更清楚地看出網絡中第40個節(jié)點失效時采用LEACH-ER算法的網絡壽命遠大于LEACH算法,仿真數(shù)據表明,算法改進后網絡壽命延長了.另外LEACH-ER最后時刻的總剩余能量也低于LEACH,這說明在均衡節(jié)點能耗方面,LEACH-ER有較優(yōu)的性能.綜上所述,雖然LEACH-ER在簇首選舉時需要額外的交互信令,但選擇一組剩余能量較多,地理位置分布合理的簇首節(jié)點有利于均衡網