無線傳感器網(wǎng)絡(luò)分簇路由算法phc

無線傳感器網(wǎng)絡(luò)分簇路由算法phc

1節(jié)點(diǎn)能量水平低無線傳感器網(wǎng)絡(luò)（wsd）是由大量廉價(jià)微傳感器節(jié)點(diǎn)組成的跳過式網(wǎng)絡(luò)。它是由無線通信模式形成的一個(gè)跳躍自組織網(wǎng)絡(luò)系統(tǒng)。目標(biāo)是合作感知、收集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對象的信息，并將其發(fā)送給支持者。WSN雖然與無線自組織網(wǎng)有相似之處,但同時(shí)也存在很大的差別:(1)節(jié)點(diǎn)數(shù)目更為龐大,且節(jié)點(diǎn)易出現(xiàn)故障;(2)在通常情況下,大多數(shù)節(jié)點(diǎn)是固定不動(dòng)的,節(jié)點(diǎn)的故障/死亡和環(huán)境干擾是造成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的主要原因;(3)節(jié)點(diǎn)的能量、處理能力、通信能力十分有限,易因能量耗盡而死亡;(4)WSN要求在提供一定服務(wù)的條件下盡可能降低節(jié)點(diǎn)能源消耗,提高網(wǎng)絡(luò)的生命周期。目前,國內(nèi)外研究人員針對WSN已經(jīng)提出了許多路由協(xié)議,按網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以分為平面路由協(xié)議和分簇路由協(xié)議。由于節(jié)點(diǎn)通信能量的損耗同傳送的數(shù)據(jù)量以及與目標(biāo)的距離的n次方(n=2~4)成正比,因此分簇的路由協(xié)議相對平面路由協(xié)議具有更好的擴(kuò)展性和節(jié)能性。分簇路由協(xié)議的基本思想是將傳感節(jié)點(diǎn)進(jìn)行分簇,簇內(nèi)通信由簇頭節(jié)點(diǎn)完成。簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合來減少信息傳輸量,最后把融合后的數(shù)據(jù)傳送給sink節(jié)點(diǎn)。低能耗自適應(yīng)遞階分簇算法(Low-EnergyAdaptiveClusteringHierarchy,LEACH)是最早提出的WSN分簇路由協(xié)議,其他的分簇路由協(xié)議大多是對LEACH進(jìn)行改進(jìn),如HEED,DCHS和EECS等。目前已有的分簇路由協(xié)議雖然能較好地符合WSN協(xié)議設(shè)計(jì)的目標(biāo),但都未能考慮節(jié)點(diǎn)的能量補(bǔ)給問題。由于節(jié)點(diǎn)的能源是有限的,WSN為了最大限度地延長網(wǎng)絡(luò)的生命周期,必然會(huì)以犧牲網(wǎng)絡(luò)的部分服務(wù)質(zhì)量為代價(jià)?，F(xiàn)有的采能技術(shù)已經(jīng)能為節(jié)點(diǎn)提供適量的能量補(bǔ)給,從而使得WSN中節(jié)點(diǎn)的能量水平相應(yīng)地起伏變化,所以需要針對這一情況研究新的WSN路由協(xié)議。本文在LEACH的基礎(chǔ)上,考慮到節(jié)點(diǎn)能夠通過周圍的環(huán)境(如太陽能、車輛或橋梁的振動(dòng)等)實(shí)現(xiàn)能量的采集,提出了一種具有能量補(bǔ)給的分簇路由算法(Power-HarvestingClustering,PHC)。2隨機(jī)簇頭選擇機(jī)制LEACH的基本思想是通過隨機(jī)循環(huán)選擇簇頭,將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)節(jié)點(diǎn),從而降低網(wǎng)絡(luò)能量消耗、延長網(wǎng)絡(luò)生命周期。LEACH的執(zhí)行是周期循環(huán)的,每一個(gè)周期稱為一輪(round),每輪包括2個(gè)階段,即簇形成階段和數(shù)據(jù)傳輸階段。在簇形成階段,節(jié)點(diǎn)i根據(jù)自身的閾值T(i)和隨機(jī)數(shù)來決定其是否成為簇頭。LEACH的隨機(jī)簇頭選擇機(jī)制雖然具有很好的自組織特性,但其本身存在一些不足:(1)簇頭是隨機(jī)選擇出來的,簇頭選擇的閾值主要根據(jù)節(jié)點(diǎn)是否成為過簇頭來設(shè)定,沒有考慮節(jié)點(diǎn)自身的能量水平,不能保證能量的均衡分布,而且能量補(bǔ)給技術(shù)的引入使得節(jié)點(diǎn)能量水平會(huì)出現(xiàn)起伏變化。(2)LEACH認(rèn)為所有節(jié)點(diǎn)在擔(dān)任簇頭時(shí)消耗的能量相等,但實(shí)際上因簇內(nèi)節(jié)點(diǎn)數(shù)目不同,和簇頭與sink節(jié)點(diǎn)之間的距離不一致,所以并不能真正保證整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)節(jié)點(diǎn)。2.2節(jié)點(diǎn)能量收集WSN中的節(jié)點(diǎn)既要實(shí)現(xiàn)信息的采集、處理和收發(fā),又要具有路由功能。節(jié)點(diǎn)一般都由電池供電,受工作環(huán)境因素(惡劣、危險(xiǎn)、遠(yuǎn)程等)、節(jié)點(diǎn)體積、成本因素的限制,難以進(jìn)行電池更換或電能補(bǔ)充。因此,電池能量是決定WSN性能和生命周期的關(guān)鍵因素,從節(jié)點(diǎn)所處環(huán)境獲取能量來實(shí)現(xiàn)自供電是解決能量問題的有效途徑?？紤]到環(huán)境能量采集技術(shù)的迅速發(fā)展,具有能量補(bǔ)給的節(jié)點(diǎn)將成為WSN中研究熱點(diǎn)。節(jié)點(diǎn)從所處環(huán)境中捕獲其他形式的能量并轉(zhuǎn)換為可用電能的過程稱為能量采收。目前可用的采能技術(shù)比較多,主要的能量來源有太陽能、振動(dòng)、溫度、氣流和壓力變化等。各種采能技術(shù)的采能效率如表1所示。隨著采能技術(shù)和傳感器硬件技術(shù)的不斷發(fā)展,具有能量補(bǔ)給的傳感器節(jié)點(diǎn)將日益普及。具有采能單元的傳感器節(jié)點(diǎn)由于能量得到了補(bǔ)充,其能量水平因補(bǔ)給而發(fā)生起伏變化,不再是單一降低。雖然傳感器節(jié)點(diǎn)能源受限的狀況將會(huì)得到一定的改善,但也不能滿足節(jié)點(diǎn)高功耗不間斷工作的需求,所以設(shè)計(jì)具有能量補(bǔ)給的WSN路由協(xié)議將十分重要。3第1階段:節(jié)點(diǎn)形成和傳輸階段本文提出具有能量補(bǔ)給的分簇路由算法PHC按輪循環(huán)進(jìn)行,每一輪分為簇形成階段和數(shù)據(jù)傳輸階段。在簇形成階段,PHC算法在考慮能量補(bǔ)給的因素下改進(jìn)了現(xiàn)有的簇頭選擇機(jī)制和非簇頭歸屬機(jī)制;在數(shù)據(jù)傳輸階段與LEACH相似。3.1節(jié)點(diǎn)初始能量進(jìn)行簇頭選擇時(shí),為避免能量較低的節(jié)點(diǎn)成為簇頭,PHC根據(jù)能量的補(bǔ)給情況以及節(jié)點(diǎn)自身的能量水平進(jìn)行簇頭的選擇,改善了現(xiàn)有的簇頭選擇機(jī)制。PHC算法對節(jié)點(diǎn)被選為簇頭的閾值進(jìn)行修正,使得能量水平高的節(jié)點(diǎn)獲選幾率更大,而能量水平低的節(jié)點(diǎn)獲選幾率更小。在第r輪節(jié)點(diǎn)i的閾值為其中,P為簇頭的百分比(即P=k/N);Eresidual(i)為節(jié)點(diǎn)i在當(dāng)前輪剩余的能量;Estart表示節(jié)點(diǎn)的初始能量;Eharvest(i,r-1)表示節(jié)點(diǎn)在上一輪所能獲取的能量。由于每個(gè)節(jié)點(diǎn)所處的能量采集環(huán)境并非恒定不變,因此其節(jié)點(diǎn)i在k個(gè)單位時(shí)間內(nèi)能量采集率表示為αi(k),節(jié)點(diǎn)i在第r-1輪中所能獲取的能量水平為由于每個(gè)節(jié)點(diǎn)所處的環(huán)境有所差異,可能導(dǎo)致在單位時(shí)間內(nèi)通過環(huán)境振動(dòng)所獲取的能量各不相同,因此在考慮節(jié)點(diǎn)當(dāng)前能量水平的同時(shí),閾值與節(jié)點(diǎn)的能量補(bǔ)給情況相關(guān)。在計(jì)算閾值之后,節(jié)點(diǎn)i產(chǎn)生一個(gè)隨機(jī)數(shù),如果隨機(jī)數(shù)小于閾值,則節(jié)點(diǎn)確定為簇頭,并向周圍發(fā)布廣播消息(消息內(nèi)容包含其與sink節(jié)點(diǎn)間的距離);否則節(jié)點(diǎn)i成為非簇頭節(jié)點(diǎn),等待廣播信息的到來。如上所述,可以看出改善后的簇頭選擇機(jī)制在選擇簇頭節(jié)點(diǎn)時(shí)不僅依據(jù)網(wǎng)絡(luò)所需要的簇頭節(jié)點(diǎn)總數(shù)和每個(gè)節(jié)點(diǎn)已成為簇頭的次數(shù),還要取決于上一輪節(jié)點(diǎn)的能量殘留值、節(jié)點(diǎn)的初始能量和節(jié)點(diǎn)采集的能量。在第r輪簇的建立過程中,每個(gè)節(jié)點(diǎn)首先記錄當(dāng)前的剩余能量值和自身節(jié)點(diǎn)的初始能量,并根據(jù)能量采集狀況來計(jì)算節(jié)點(diǎn)上一輪中所捕獲的能量。如果節(jié)點(diǎn)的剩余能量和補(bǔ)給的能量均有限,則降低其在r+1輪中成為簇頭的概率,以避免其因負(fù)載過大而死亡;反之,當(dāng)節(jié)點(diǎn)自身能量和補(bǔ)給的能量較充足時(shí),則提高其成為簇頭的概率。3.2非簇頭節(jié)點(diǎn)的代價(jià)函數(shù)圖1給出了本文改進(jìn)后的簇形成階段的過程。在完成簇頭選擇之后,所有的非簇頭需要根據(jù)其所收到的廣播信息決定自己的歸屬。在LEACH算法中,非簇頭節(jié)點(diǎn)選擇離自身最近的簇頭,PHC對此進(jìn)行了修正。本文所采用的通信模型為Heinzelman提出的一階無線通信模型(firstorderradiomodel)。假設(shè)發(fā)送或接收電路消耗為Eelec,傳輸功放為εamp,信號(hào)傳輸則根據(jù)傳輸距離采用自由空間模型(εamp=εfriss-amp)或多徑衰減模型(εamp=εtwo-ray-amp)。據(jù)此模型,傳輸長度為l(單位為bit)數(shù)據(jù)且距離為d時(shí)消耗的能量為由上述通信模型可以看出,在傳輸相同數(shù)據(jù)的情況下,遠(yuǎn)離sink節(jié)點(diǎn)的簇頭所消耗的能量遠(yuǎn)遠(yuǎn)超過了靠近sink節(jié)點(diǎn)的簇頭。故當(dāng)非簇頭節(jié)點(diǎn)收到多個(gè)廣播信息之后,根據(jù)廣播信息來計(jì)算相應(yīng)的代價(jià)函數(shù):其中,D1表示本節(jié)點(diǎn)與發(fā)布廣播信息的簇頭之間的距離;D2表示發(fā)布廣播信息的簇頭與sink節(jié)點(diǎn)之間的距離;A表示簇頭進(jìn)行數(shù)據(jù)融合或壓縮的比率。非簇頭節(jié)點(diǎn)在計(jì)算不同簇的代價(jià)函數(shù)后,選擇加入代價(jià)最小的簇。通過上式可以看出,節(jié)點(diǎn)i在選擇簇頭時(shí),不是單純從節(jié)省自身能量消耗的角度出發(fā),而是從整個(gè)網(wǎng)絡(luò)的能量均衡性出發(fā)。代價(jià)函數(shù)與數(shù)據(jù)在整個(gè)網(wǎng)絡(luò)中傳輸所消耗的能量成正比,使得選擇節(jié)點(diǎn)i時(shí)要平衡節(jié)點(diǎn)與簇頭之間的距離和簇頭與sink節(jié)點(diǎn)的距離2個(gè)因素,從而確保遠(yuǎn)離sink節(jié)點(diǎn)的簇頭所包含的節(jié)點(diǎn)數(shù)目不會(huì)過多,將非簇頭節(jié)點(diǎn)數(shù)據(jù)在整個(gè)網(wǎng)絡(luò)傳輸過程中所消耗的能量降至最低。4網(wǎng)絡(luò)仿真實(shí)驗(yàn)無線傳感器網(wǎng)絡(luò)仿真軟件較多,本文在Linux+Omnet++的平臺(tái)下進(jìn)行仿真。仿真場景是在頂點(diǎn)坐標(biāo)為(0,0),(100,0),(0,100),(100,100)的100×100m2的正方形區(qū)域內(nèi)隨機(jī)分布100個(gè)傳感器節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)周期性地產(chǎn)生信息包,信息包通過不同的路徑傳輸?shù)骄W(wǎng)絡(luò)中的sink節(jié)點(diǎn)。仿真中采用Heinzelman的參數(shù)和能量模型,節(jié)點(diǎn)通過振動(dòng)獲取能量,采收率為服從正態(tài)分布的隨機(jī)變量(μ=275μW/cm3,σ2=100),其電源體積考慮為2節(jié)AA(5號(hào))電池大小(約9cm3)。Heinzelman參數(shù)如表2所示。在上述仿真環(huán)境下,本文對PHC和LEACH進(jìn)行性能比較,主要考慮網(wǎng)絡(luò)中死亡節(jié)點(diǎn)數(shù)和剩余能量這2個(gè)參數(shù)指標(biāo)。圖2給出了網(wǎng)絡(luò)運(yùn)行1000輪后網(wǎng)絡(luò)中節(jié)點(diǎn)存活的數(shù)目,圖3給出了在網(wǎng)絡(luò)運(yùn)行1000輪之后網(wǎng)絡(luò)總體剩余的能量。通過圖2和圖3可以看出,雖然LEACH與PHC采用了相同的能量補(bǔ)給規(guī)律,PHC路由算法的網(wǎng)絡(luò)中最終存活的節(jié)點(diǎn)數(shù)目和整體殘留能量均高于LEACH。由于采用LEACH路由算法的網(wǎng)絡(luò)簇頭只是隨機(jī)地選取,沒有考慮到節(jié)點(diǎn)當(dāng)前的能量以及能量補(bǔ)給的水平,因此可能導(dǎo)致部分能量水平較低的節(jié)點(diǎn)成為簇頭,從而使得節(jié)點(diǎn)能量消耗不均衡,部分節(jié)點(diǎn)過早地因能量耗盡而死亡。在PHC中,對簇頭選擇閾值的修正保證了簇頭具有較高的能量水平,避免了低能量水平節(jié)點(diǎn)因當(dāng)選簇頭節(jié)點(diǎn)而過早死亡的現(xiàn)象。同樣,非簇頭節(jié)點(diǎn)選擇歸屬簇時(shí),PHC通過代價(jià)計(jì)算來選擇所屬簇,改善了整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)負(fù)載的平衡,使得一輪中每個(gè)簇頭的能量消耗相對均衡,所以最終網(wǎng)絡(luò)中存活的節(jié)點(diǎn)數(shù)目和整體殘留能量比LEACH要高,從而延長了網(wǎng)絡(luò)的生命周期。圖4給出了在網(wǎng)絡(luò)運(yùn)行50輪仿真之后,網(wǎng)絡(luò)中存活節(jié)點(diǎn)的剩余能量水平。通過圖4(a)可以看出,采用LEACH路由算法的網(wǎng)絡(luò)在經(jīng)過一定時(shí)間的網(wǎng)絡(luò)仿真后,在遠(yuǎn)離sink節(jié)點(diǎn)(節(jié)點(diǎn)x坐標(biāo)值小于60)區(qū)域內(nèi)節(jié)點(diǎn)基本都已因能量耗盡而死亡,在靠近sink節(jié)點(diǎn)區(qū)域內(nèi)的節(jié)點(diǎn)整體能量水平也不高,能量水平大都低于1J;而圖4(b)中由于PHC中簇頭選擇機(jī)制和非簇頭歸屬機(jī)制的改善,60%節(jié)點(diǎn)的剩余能量都具有較高的能量水平(大于1J),整個(gè)網(wǎng)絡(luò)區(qū)域內(nèi)能量分布較為平衡,在減少了能量消耗的情況下改善了能量消耗的均衡性。5c網(wǎng)絡(luò)模型考慮到傳感器節(jié)點(diǎn)能夠從環(huán)境中采集能量,本文提出了一種具有能量補(bǔ)給的分簇路由算法PHC。