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

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

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