基于能量預(yù)測的無線傳感器網(wǎng)絡(luò)能量優(yōu)化分簇算法

基于能量預(yù)測的無線傳感器網(wǎng)絡(luò)能量優(yōu)化分簇算法

1節(jié)點(diǎn)級結(jié)構(gòu)的轉(zhuǎn)變,使無線傳感器在網(wǎng)絡(luò)上的應(yīng)用更加容易造成網(wǎng)絡(luò)的互通和融合.在網(wǎng)絡(luò)無線傳感器技術(shù)、嵌入式技術(shù)和微信傳感器技術(shù)的快速發(fā)展和成熟，使大量成本傳感器能夠通過無線通信通道自組織成為無線傳感器網(wǎng)絡(luò)（w傳感器網(wǎng)絡(luò)）。與現(xiàn)有的無線傳感器網(wǎng)絡(luò)有很多相似之處，但同時也存在很大差異。最顯著的是，無線傳感器節(jié)點(diǎn)通常采用隨機(jī)一次性傳輸，并且不同于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)通常提供連續(xù)的能量，因此應(yīng)用程序受到能耗的限制。無線傳感器網(wǎng)絡(luò)的任何操作、計算和通信都消耗了傳感器節(jié)點(diǎn)的電池能量。當(dāng)一些節(jié)點(diǎn)，尤其是一些重要節(jié)點(diǎn)的電池資源不足時，它們將失敗，整個無線傳感器網(wǎng)絡(luò)的連接以及整個網(wǎng)絡(luò)的監(jiān)控任務(wù)將順利進(jìn)行。同時,由于無線傳感器網(wǎng)絡(luò)不依賴于固定的基礎(chǔ)設(shè)施,當(dāng)節(jié)點(diǎn)數(shù)目比較大,網(wǎng)絡(luò)規(guī)模太大的時候,高效率的路由算法顯得尤為重要.現(xiàn)在國內(nèi)外流行的一種解決辦法就是采用分級結(jié)構(gòu)將網(wǎng)絡(luò)劃分成若干個簇,在分簇的基礎(chǔ)上進(jìn)行路由.在這種結(jié)構(gòu)中每個簇由一個簇頭節(jié)點(diǎn)和多個簇內(nèi)成員節(jié)點(diǎn)組成,簇內(nèi)成員節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的采集,并將采集到的數(shù)據(jù)傳送給它所屬的簇的簇頭,簇頭節(jié)點(diǎn)對簇內(nèi)成員傳送過來的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合處理,然后將融合后的數(shù)據(jù)傳送給遠(yuǎn)方的基站或觀察者;或者這些簇頭節(jié)點(diǎn)再形成更高一級的網(wǎng)絡(luò),重新進(jìn)行簇的劃分,簇頭選舉,簇的數(shù)據(jù)傳送等等.這一模式的不斷重復(fù)形成簇的分級,最高級別的簇頭節(jié)點(diǎn)直接向基站匯報.事實(shí)證明,這種分簇結(jié)構(gòu)有利于無線傳感器網(wǎng)絡(luò)平衡能源負(fù)載,且在網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)融合非常便利.LEACH算法是無線傳感器網(wǎng)絡(luò)分簇算法的典型代表,其他如TEEN、APTEEN、PEGASIS等算法都由此而來.由于簇頭節(jié)點(diǎn)所承擔(dān)任務(wù)遠(yuǎn)多于簇內(nèi)成員節(jié)點(diǎn),所以必須由簇內(nèi)成員輪流當(dāng)選簇頭節(jié)點(diǎn)以避免簇頭節(jié)點(diǎn)因能耗過多而提早失效.現(xiàn)有的分簇算法在簇頭輪換時僅依靠隨機(jī)性進(jìn)行能源負(fù)載的平衡,沒有充分考慮到備選節(jié)點(diǎn)的剩余能量,會導(dǎo)致某些節(jié)點(diǎn)過快耗盡電池能量而縮短系統(tǒng)壽命,簇頭節(jié)點(diǎn)的選舉方式有待于改進(jìn).針對此問題,本文提出了一種基于能量預(yù)測參數(shù)的分簇算法,算法建立了節(jié)點(diǎn)工作狀態(tài)轉(zhuǎn)換模型并由此得到能量預(yù)測參數(shù)ΔE,對隨機(jī)性簇頭選擇的閥值進(jìn)行改進(jìn),使簇頭的選擇更加合理.2打造隨機(jī)性質(zhì)控制點(diǎn),增加自適應(yīng)識別機(jī)制LEACH(Low-EnergyAdaptiveClusteringHierarchy)算法由MIT的Heinzelman等人提出的,它是第一種基于分簇結(jié)構(gòu)和分層技術(shù)的無線傳感器網(wǎng)絡(luò)算法,在無線傳感器網(wǎng)絡(luò)路由算法中占有重要地位,LEACH的操作分成“輪”(Round)來進(jìn)行,每一輪具有兩個運(yùn)行階段:簇建立階段(Set-upPhase)和穩(wěn)定運(yùn)行階(Steady-statePhase).為減少算法開銷,穩(wěn)定運(yùn)行階段的持續(xù)時間要長于簇建立階段,其過程如圖所示.在簇建立階段,將所有節(jié)點(diǎn)劃分為若干簇,每個簇隨機(jī)選舉一個簇頭.通過隨機(jī)性確保簇頭與Sink節(jié)點(diǎn)之間數(shù)據(jù)傳輸?shù)母吣芎某杀揪鶆虻胤謹(jǐn)偟剿袀鞲衅鞴?jié)點(diǎn).具體產(chǎn)生機(jī)制是:每個傳感器節(jié)點(diǎn)生成一個(0,1)之間的隨機(jī)數(shù),如果該數(shù)小于閥值T,則選該節(jié)點(diǎn)為簇頭.T的計算方法如下:T(n)={P1?P[rmod(1?P)]0,,n∈Gn?G(1)Τ(n)={Ρ1-Ρ[rmod(1-Ρ)],n∈G0,n?G(1)式中P是網(wǎng)絡(luò)中簇頭數(shù)與總節(jié)點(diǎn)數(shù)的百分比;r是當(dāng)前的選舉輪數(shù);G是最近1/P輪沒有當(dāng)選簇頭的節(jié)點(diǎn)集.一旦簇頭節(jié)點(diǎn)被選定,它們便主動向所有節(jié)點(diǎn)廣播這一消息.依據(jù)接收信號的強(qiáng)度,節(jié)點(diǎn)選擇它所要加入的簇,并告知相應(yīng)的簇頭節(jié)點(diǎn).基于時分復(fù)用(TDMA)的方式,簇頭為其簇內(nèi)的每個成員分配通信時隙.在穩(wěn)定運(yùn)行階段,簇內(nèi)成員節(jié)點(diǎn)持續(xù)采集監(jiān)測數(shù)據(jù),傳與簇頭節(jié)點(diǎn),進(jìn)行必要的融合處理之后,發(fā)送到sink節(jié)點(diǎn),這種工作模式有利于減小網(wǎng)絡(luò)中的數(shù)據(jù)量.持續(xù)一段時間以后,整個網(wǎng)絡(luò)進(jìn)入下一輪工作周期,重新選擇簇頭節(jié)點(diǎn).LEACH算法對于簇頭節(jié)點(diǎn)的選取,并未考慮到節(jié)點(diǎn)的剩余電池能量,這樣的負(fù)載均衡策略是不完備的.按照一個預(yù)先定義的概率隨機(jī)地決定節(jié)點(diǎn)的“角色”,盡管一個節(jié)點(diǎn)在一個工作周期中只有一次機(jī)會成為簇頭,但是在LEACH的下一工作周期中,所有的節(jié)點(diǎn)還是具有同樣的機(jī)會成為簇頭,那些電池能量已經(jīng)在警戒線以下的節(jié)點(diǎn)會因為成為簇頭而很快地耗盡電池能量.3馬爾可夫鏈下的能量消耗率預(yù)測模型無線傳感器網(wǎng)絡(luò),節(jié)點(diǎn)的能量消耗取決于不同的工作方式.無線傳感器節(jié)點(diǎn)消耗能量的模塊包括無線傳感器模塊、處理器模塊和無線通信模塊.圖2是DeborahEstrin在Mobicom2002會議上的特邀報告中所描述的傳感器節(jié)點(diǎn)各部分能量消耗情況.傳感器節(jié)點(diǎn)通過工作狀態(tài)的轉(zhuǎn)換使通信模塊在沒有任務(wù)時盡量進(jìn)入睡眠狀態(tài),以此降低節(jié)點(diǎn)的能耗.這種節(jié)點(diǎn)工作狀態(tài)的轉(zhuǎn)換對于WSN是有效也是必需的,同時也增加了預(yù)測能量消耗的難度.為此,本文采用通過馬爾可夫鏈預(yù)測節(jié)點(diǎn)剩余能量的數(shù)學(xué)模型.能量預(yù)測模型中定義了節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移的概念,即傳感器節(jié)點(diǎn)工作模式的相互轉(zhuǎn)換,并以此進(jìn)行預(yù)測.利用此模型,傳感器節(jié)點(diǎn)可以預(yù)測出自己在一段時間后的剩余能量.在此預(yù)測模型中,我們利用馬爾可夫鏈對每個傳感器節(jié)點(diǎn)的運(yùn)作方式進(jìn)行模擬.這樣,節(jié)點(diǎn)的運(yùn)作方式通過馬爾可夫鏈的不同狀態(tài)呈現(xiàn)出來,如果一個節(jié)點(diǎn)有M種運(yùn)作方式,則可通過馬爾可夫鏈的M種狀態(tài)進(jìn)行模擬.使用這種模型,每個傳感器節(jié)點(diǎn)都由一系列隨機(jī)數(shù)X0;X1;X2;…代表其在每個時期所處的狀態(tài).如果Xn=i,則節(jié)點(diǎn)在第n個time-step處于狀態(tài)i(每個time-step節(jié)點(diǎn)只能有一個狀態(tài)).假如節(jié)點(diǎn)在某個time-step處于狀態(tài)i,則節(jié)點(diǎn)會以某個固定的概率Pij,在下個time-step轉(zhuǎn)為狀態(tài)j,這個概率定義為傳感器節(jié)點(diǎn)的一步狀態(tài)轉(zhuǎn)移概率,可通過Pij=P{Xm+1=j|Xm=i}來表示.進(jìn)一步可以定義N步轉(zhuǎn)移概率P(n)ijij(n),一個在狀態(tài)i的節(jié)點(diǎn)在N次狀態(tài)轉(zhuǎn)換后,轉(zhuǎn)為狀態(tài)j的概率:P(n)ijij(n)=∑k=1M∑k=1ΜP(r)ikik(r)P(n?r)kjkj(n-r),對于任何的0<r<n.得知傳感器節(jié)點(diǎn)的P(n)ijij(n)和節(jié)點(diǎn)的初始狀態(tài),就可以使用這些轉(zhuǎn)移概率來預(yù)測節(jié)點(diǎn)的能量下降.完成這個預(yù)測首先是要計算出接下來的T個time-step內(nèi),一個節(jié)點(diǎn)會處在狀態(tài)s的time-step數(shù).如果節(jié)點(diǎn)處在狀態(tài)i,則一個節(jié)點(diǎn)在接下來T個time-step內(nèi)處在狀態(tài)s的數(shù)目可計算為∑t=1T∑t=1ΤP(t)isis(t).設(shè)Es是一個節(jié)點(diǎn)停留在狀態(tài)s一個time-step所消耗的能量,這樣在接下來的T個time-steps內(nèi)所預(yù)計出消耗的能量總量ET(i):ET=∑s=1M(∑t=1TP(t)is)∑s=1Μ(∑t=1ΤΡis(t))×Es(2)利用式(1),每個傳感器節(jié)點(diǎn)可以計算出自己的能量消耗率參數(shù)ΔE:ΔE=ET/T,ΔE代表接下來的T個time-step內(nèi),平均每個time-step的節(jié)點(diǎn)消耗能量.由此,通過ΔE,傳感器節(jié)點(diǎn)就可以預(yù)測出自己在接下來的T時間內(nèi)的能量消耗.有兩個因素影響運(yùn)用ΔE進(jìn)行預(yù)測的準(zhǔn)確性:一是所建立轉(zhuǎn)移概率矩陣的正確性;二是各狀態(tài)能耗計算的準(zhǔn)確性.4chec算法4.1節(jié)點(diǎn)型睡眠狀態(tài)為在CHEP算法中有效進(jìn)行能量預(yù)測,本文提出一種非簇頭傳感器節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換模型,模型中節(jié)點(diǎn)共有5種工作狀態(tài).休眠狀態(tài):傳感器模塊關(guān)閉,通信模塊睡眠,能量消耗最小;感知狀態(tài):傳感器模塊開啟,通信模塊睡眠,節(jié)點(diǎn)僅感知事件發(fā)生;偵聽狀態(tài):傳感器模塊開啟,通信模塊處于空閑態(tài);接收狀態(tài):傳感器模塊開啟,通信模塊接收;發(fā)送狀態(tài):傳感器模塊開啟,通信模塊發(fā)送.工作狀態(tài)的轉(zhuǎn)換發(fā)生在當(dāng)前time-step結(jié)束時.圖3所示模型中狀態(tài)之間轉(zhuǎn)換關(guān)系如下:(1)偵聽?wèi)B(tài)進(jìn)入睡眠態(tài)處于休眠態(tài)的傳感器節(jié)點(diǎn)設(shè)置定時器TS,當(dāng)定時器超時后,節(jié)點(diǎn)由休眠態(tài)進(jìn)入偵聽?wèi)B(tài);處于偵聽?wèi)B(tài)的節(jié)點(diǎn)設(shè)置定時器Ti,此時節(jié)點(diǎn)的通信模塊處于空閑狀態(tài),通過監(jiān)聽信道檢查是否有數(shù)據(jù)發(fā)送給自己,當(dāng)定時器超時后,節(jié)點(diǎn)由偵聽?wèi)B(tài)以概率PS進(jìn)入休眠態(tài).(2)時發(fā)數(shù)據(jù)存儲處于感知態(tài)的節(jié)點(diǎn)設(shè)置定時器Tf,感知事件發(fā)生,并將監(jiān)測數(shù)據(jù)保存在本地存儲器.當(dāng)定時器超時后,節(jié)點(diǎn)由感知態(tài)進(jìn)入偵聽?wèi)B(tài);處于偵聽?wèi)B(tài)的節(jié)點(diǎn)在定時器Ti超時后,以概率1-PS進(jìn)入感知態(tài).(3)節(jié)點(diǎn)接收trt處于偵聽?wèi)B(tài)的節(jié)點(diǎn)除感知事件外,其通信模塊在定時器Ti超時前,如果監(jiān)聽到有消息發(fā)送給自己,節(jié)點(diǎn)進(jìn)入接收態(tài);當(dāng)消息接收完畢且不需要發(fā)送消息,節(jié)點(diǎn)立刻由接收態(tài)進(jìn)入偵聽?wèi)B(tài),定時器Ti重新計時.(4)段節(jié)點(diǎn)發(fā)送信息在簇建立階段,非簇頭傳感器節(jié)點(diǎn)向簇頭發(fā)送入簇信息后,節(jié)點(diǎn)由發(fā)送態(tài)進(jìn)入偵聽?wèi)B(tài)并設(shè)立定時器Tw,監(jiān)測確認(rèn)消息的到來.如果Tw超時,仍然沒有收到確認(rèn)消息,節(jié)點(diǎn)再次進(jìn)入發(fā)送態(tài),重新發(fā)送入簇信息,節(jié)點(diǎn)在重發(fā)k次后停止發(fā)送,停留在偵聽?wèi)B(tài),定時器Ti重新計時.簇運(yùn)行階段,簇內(nèi)成員節(jié)點(diǎn)在自己的通信時隙內(nèi),處于偵聽?wèi)B(tài)的節(jié)點(diǎn)在定時器Ti超時前,如果需要向簇頭節(jié)點(diǎn)發(fā)送信息,節(jié)點(diǎn)由偵聽?wèi)B(tài)進(jìn)入發(fā)送態(tài).(5)非簇頭節(jié)點(diǎn)工作轉(zhuǎn)換模型傳感器節(jié)點(diǎn)在簇建立階段如接收到新簇頭發(fā)來的消息,則由接收態(tài)進(jìn)入發(fā)送態(tài),向所要加入的簇頭發(fā)送入簇消息.基于此非簇頭傳感器節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換模型,CHEP算法中的非簇頭節(jié)點(diǎn)可以實(shí)現(xiàn)對自己的能耗預(yù)測.需要指出的是,簇頭節(jié)點(diǎn)的工作方式于簇內(nèi)成員節(jié)點(diǎn)不同,但由于簇頭節(jié)點(diǎn)能耗較大且所處工作時間相對傳感器節(jié)點(diǎn)的生存時間來說很短,所以本文沒有設(shè)計簇頭節(jié)點(diǎn)的工作轉(zhuǎn)換模型,其處理方式詳見4.2節(jié).4.2計算假設(shè)為考慮到LEACH中公式(1)存在的不足,CHEP中將對剩余的預(yù)測作為簇頭節(jié)點(diǎn)選擇的重要參數(shù).修改后的閥值計算公式如下:Te(n)={P1?P[rmod(1?P)](EPEn?max)?0,n∈Gn?G(3)Τe(n)={Ρ1-Ρ[rmod(1-Ρ)](EΡEn-max)?n∈G0,n?G(3)EP=En-current-Er(4)其中EP是一個傳感器節(jié)點(diǎn)作為簇內(nèi)節(jié)點(diǎn)經(jīng)過一輪時間后的剩余能量,由公式(4)計算得出;Er是每一輪的能耗預(yù)測,由公式(2)中T等于一輪時間得出,En-current,是某輪開始時傳感器節(jié)點(diǎn)的能量.En-max是傳感器節(jié)點(diǎn)的初始能量.只有近1/P輪沒有被選的節(jié)點(diǎn)才有成為簇頭節(jié)點(diǎn)的可能.為防止預(yù)測誤差帶來的影響,需要設(shè)定一個誤差門限d,當(dāng)某輪結(jié)束時傳感器節(jié)點(diǎn)發(fā)現(xiàn)其剩余能量真實(shí)值和本輪開始時的預(yù)測值誤差超過d,則重新計算ΔE.通過分析可知,將剩余能量預(yù)測參數(shù)Ep引入閥值會使具有較高剩余能量且耗能較慢的節(jié)點(diǎn)當(dāng)選簇頭節(jié)點(diǎn)的可能性大大增加,平衡了網(wǎng)絡(luò)的能量消耗.值得注意的一點(diǎn)是,由于一個傳感器節(jié)點(diǎn)擔(dān)任簇頭的時間遠(yuǎn)少于擔(dān)任簇內(nèi)成員節(jié)點(diǎn)的時間,且作為簇頭的能耗遠(yuǎn)高于作為簇內(nèi)成員節(jié)點(diǎn),CHEP算法中如果一個節(jié)點(diǎn)成為簇頭節(jié)點(diǎn),其工作狀態(tài)會改變,在其再次轉(zhuǎn)為非簇頭節(jié)點(diǎn)時重新計算能量消耗率參數(shù)ΔE.這在保證了預(yù)測準(zhǔn)確性的同時,也避免了因節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換概率的計算公式中n值較大造成的計算量龐大.簇頭節(jié)點(diǎn)選取過程中,節(jié)點(diǎn)生成(0,1)之間的隨機(jī)數(shù),如果該數(shù)小于自己的閥值Te(n),且沒有收到其他節(jié)點(diǎn)當(dāng)選簇頭的消息則發(fā)送廣播告知其他節(jié)點(diǎn)自己當(dāng)選簇頭.其余節(jié)點(diǎn)根據(jù)收到簇頭節(jié)點(diǎn)消息信號的強(qiáng)弱,選擇信號較強(qiáng)的簇頭加入該簇.進(jìn)入穩(wěn)定運(yùn)行階段后,簇內(nèi)成員節(jié)點(diǎn)持續(xù)采集監(jiān)測數(shù)據(jù),傳與簇頭節(jié)點(diǎn)后發(fā)送到sink節(jié)點(diǎn).持續(xù)一段時間以后,整個網(wǎng)絡(luò)進(jìn)入下一輪工作周期,重新選擇簇頭節(jié)點(diǎn).5shef的模擬和分析5.1節(jié)點(diǎn)數(shù)、能量消耗為了分析CHEP的有效性,利用ns-2模擬了100×100米范圍內(nèi)采用CHEP算法的100個傳感器節(jié)點(diǎn)運(yùn)行狀況,并在相同的實(shí)驗環(huán)境中對CHEP、Static-clustering、LEACH、LEACH-F算法的存活節(jié)點(diǎn)數(shù)、能量消耗的進(jìn)行比較.其中LEACH-F是LEACH的一種改進(jìn)算法,簇建立一次后簇內(nèi)節(jié)點(diǎn)將不再變化,該算法簡化了每輪的簇建立過程,但所選簇頭的位置出現(xiàn)在簇邊緣的機(jī)率高.本文實(shí)驗中事件的發(fā)生符合λ=0.2的泊松分布,每個節(jié)點(diǎn)的初始能量為2J,每輪持續(xù)20s.每個節(jié)點(diǎn)根據(jù)其工作況建立自身的狀態(tài)轉(zhuǎn)移矩陣.文中使用的參數(shù)見表1.5.2網(wǎng)絡(luò)能耗分析圖4中的correct表示實(shí)驗中一個傳感器節(jié)點(diǎn)能量隨時間下降的真實(shí)情況,仿真結(jié)果表明在900s內(nèi)CHEP算法中由公式(4)預(yù)測的剩余能量值非常接近于真實(shí)值,在45輪內(nèi)僅有3次誤差超過3%,該值作為參數(shù)引入閥值的合理性得到保證.圖5描述了不同分簇算法下網(wǎng)絡(luò)能源的耗散情況,可以看出,隨時間的流逝,Static-clustering由于采用固定簇頭的機(jī)制,在簇頭能量耗光后,網(wǎng)絡(luò)雖剩余大量能量,但因無法工作而實(shí)效.CHEP、LEACH、LEACH-F耗光了所有的網(wǎng)絡(luò)能量,它們采用的簇頭輪換機(jī)制使得這些算法不會出現(xiàn)Static-clustering因簇頭耗光能量后其簇隨即失效,以致大部分網(wǎng)絡(luò)能源無法得以利用的情況.特別地,與LEACH、LEACH-F相比,CHEP算法在網(wǎng)絡(luò)總能源相同的情況下,網(wǎng)絡(luò)能耗率較低,運(yùn)行的時間較長.圖6顯示了仿真時間內(nèi)各算法存活節(jié)點(diǎn)的總數(shù).存活節(jié)點(diǎn)為零的時刻定義為網(wǎng)絡(luò)的最大生存時間.由圖中可以看出,CHEP算法與LEACH,LEACH-F相比,出現(xiàn)節(jié)點(diǎn)死亡的時間和節(jié)點(diǎn)全部死亡的時間都晚得多,而且這兩個時間差很短,體現(xiàn)出采用CHEP算法,網(wǎng)絡(luò)中節(jié)點(diǎn)的不僅能耗較低而且均衡性更好.6基于能量預(yù)測的chep算法無線傳感器網(wǎng)絡(luò)分簇算法采用