基于虛擬區(qū)域劃分的wsn網(wǎng)絡非均衡簇路由算法

基于虛擬區(qū)域劃分的wsn網(wǎng)絡非均衡簇路由算法

1熱區(qū)問題的提出路算法在無線傳感器網(wǎng)絡中起著重要的作用。什么樣的路由算法決定了數(shù)據(jù)路徑，直接影響網(wǎng)絡的整體性能。根據(jù)傳感器網(wǎng)絡的能量和資源限制的特點，最佳路由協(xié)議是非常競爭的。在以分簇方式組織的傳感器網(wǎng)絡中,傳感器節(jié)點的角色分為兩種:簇頭和簇成員.簇頭作為簇的中心負責簇結構的建立,收集簇成員的數(shù)據(jù),經融合處理后發(fā)送給匯聚節(jié)點.由于簇頭距離匯聚節(jié)點的距離一般較遠,有研究表明,采用通過簇頭組成的骨干網(wǎng)實現(xiàn)多跳路由的方式更有利于節(jié)約能量.然而這種做法帶來了一個能量消耗不均衡的問題:靠近匯聚節(jié)點的簇頭節(jié)點由于需要轉發(fā)大量來自其它簇的數(shù)據(jù)而負擔過重,過早耗盡自身能量而失效,造成網(wǎng)絡分割,降低網(wǎng)絡存活時間.研究者稱這個問題為“熱區(qū)”(Hotspots)問題.在傳統(tǒng)的同構網(wǎng)絡分簇協(xié)議中,通過周期性地重新選擇簇頭(如LEACH、HEED),可以平衡簇頭與簇成員節(jié)點之間的能量消耗,但不能解決上述的“熱區(qū)”問題.以節(jié)點的剩余能量為依據(jù)選擇簇頭的方法(如EECS)也不能完全解決這個問題,因為它只是在網(wǎng)絡的局部比較節(jié)點剩余能量,無法從整體上協(xié)調節(jié)點的能量消耗以解決“熱區(qū)”問題.可以認為上述兩種方法都是以被動的方式來均衡網(wǎng)絡中節(jié)點的能量消耗,即在網(wǎng)絡中出現(xiàn)能量消耗不均衡之后方采取措施來均衡能量消耗.在以周期性選擇簇頭的分簇協(xié)議中,往往是基于平衡簇頭與簇成員節(jié)點之間的能量消耗這一出發(fā)點考慮的,通常是所有傳感器節(jié)點動態(tài)的形成多個簇,且經過一段時間的數(shù)據(jù)傳輸之后,會進行重新分簇.這樣一來,在出現(xiàn)“熱區(qū)”問題的網(wǎng)絡中就會存在兩種情況:(1)整個網(wǎng)絡主動進行簇頭選舉工作,即存在簇頭節(jié)點即將能量耗盡之前發(fā)出重新選舉簇頭的請求,然后進入新一輪簇頭選舉階段.但是處于“熱區(qū)”中的簇頭節(jié)點能量耗費較高,當進行新一輪簇頭選舉時,處于非“熱區(qū)”中的簇頭也許此時能量還很充裕.因此,這種情況下進行這個網(wǎng)絡的簇頭選舉工作對于那些處于非“熱區(qū)”中的能量充裕的簇頭來說是不公平的.(2)整個網(wǎng)絡被動進行簇頭選舉工作,即網(wǎng)絡運行一段時間之后,不管網(wǎng)絡是否需要進行重新選擇簇頭都會進行一次新的簇頭選舉工作.此時處于“熱區(qū)”和非“熱區(qū)”的簇頭節(jié)點之間也會由于消耗能量的不同產生矛盾,當兩次簇頭選舉工作的間隔較長時,處于“熱區(qū)”中的簇頭節(jié)點會因為能量消耗過大而提前進入失效狀態(tài),從而造成網(wǎng)絡分割,降低網(wǎng)絡存活時間;當兩次簇頭選舉工作的間隔較短時,整個網(wǎng)絡會因為頻繁的進行簇頭選舉工作而消耗過多的能量,從而造成網(wǎng)絡生存時間縮短.以上兩種情況都會造成節(jié)點(簇頭節(jié)點和普通節(jié)點)寶貴能量的白白耗費.通過對傳感器節(jié)點能量消耗情況和無線傳感器網(wǎng)絡路由協(xié)議的研究,我們提出一種基于ARMA流量預測的單元格帶管理節(jié)點的分簇路由協(xié)議ACRP(ARMA-BasedClusterRoutingProtocol),該協(xié)議的主要思想是利用可補充能量的匯聚節(jié)點采用集中式方式將傳感器節(jié)點覆蓋的區(qū)域固定劃分為許多單元格,每個單元格作為一個簇.在每個簇中設置一個管理節(jié)點,管理節(jié)點基于ARMA模型的流量預測,以分布式方式實現(xiàn)每個簇中簇頭的重新選舉,以減少成簇的開銷,實現(xiàn)簇頭的均衡能量消耗,同時增強網(wǎng)絡的健壯性,延長WSN網(wǎng)絡生存時間.2節(jié)點位置.假設傳感器節(jié)點隨機分布在一個正方形監(jiān)測區(qū)域內,并且該傳感器網(wǎng)絡具有以下性質:(1)以匯聚節(jié)點為中心建立無線傳感器網(wǎng)絡環(huán)境,節(jié)點均勻分布于匯聚節(jié)點四周,以匯聚節(jié)點為原點建立坐標系.(2)匯聚節(jié)點具有較強的計算、存儲能力,且能量能無限制.(3)所有傳感器節(jié)點部署后靜止不動,并且具有相同的初始能量值,具有相似的處理通信能力,地位是對稱平等的.(4)所有節(jié)點都是同構的,具備數(shù)據(jù)融合的功能.(5)根據(jù)接收者的距離遠近,節(jié)點可以自由調節(jié)其發(fā)送功率以節(jié)約能量消耗.(6)所有節(jié)點可以獲知自己的坐標位置.2.1穩(wěn)定的流量模型簇頭更新存在的問題有網(wǎng)絡中每個簇的簇頭是否有權利發(fā)起更換簇頭的請求;每個簇的簇頭在什么樣的情況之下才能發(fā)起更換簇頭的請求;簇頭的更換是集中進行還是分布進行等.比如在簇頭與匯聚節(jié)點之間通信采用多跳方式(即通過簇頭組成的骨干網(wǎng)實現(xiàn)的多跳路由)更有利與節(jié)約能量,但是這種做法也帶來了一個能量消耗不均衡的問題:在這種所有傳感器節(jié)點的數(shù)據(jù)都發(fā)送到匯聚節(jié)點的“多對一”數(shù)據(jù)傳輸模式中,靠近匯聚節(jié)點的簇頭由于需要轉發(fā)大量來自其它簇的數(shù)據(jù)而負擔過重,在該節(jié)點擔當簇頭的一輪中,會因為更換簇頭的時間未到,或者是沒有單獨更換簇頭的權利(即分布式簇頭更替,每個簇的簇頭更替是根據(jù)自身情況進行),而過早耗盡自身能量而失效.本文基于ARMA流量預測模型應用到了主簇頭節(jié)點的更換過程中,提出了一種基于ARMA流量預測機制的主簇頭節(jié)點更換策略.流量模型必須有可管理的參數(shù)個數(shù),參數(shù)估計必須簡單.有許多隨機模型用于描述網(wǎng)絡流量,通信網(wǎng)絡中的流量模型可以分為穩(wěn)定的和不穩(wěn)定的兩種,穩(wěn)定的流量模型又分為兩類:短相關和長相關.短相關模型包括馬爾可夫過程和自回歸模型(AR),自回歸滑動平均模型(ARMA),以及自回歸求和滑動平均模型(ARIMA);長相關流量模型包括:F-ARIMA和FractionalBrownianMotion,我們采用ARMA模型,它不能建立長相關的模型,因此只能進行短期實時預測.假設數(shù)據(jù)流量序列為Χ0,Χ1,…Χi…,Xn,我們這里采用ARMA(2,1)來進行預測據(jù),其模型為其中B是后移算子,ai是白噪聲.φ1,φ2,θ1,σ2a2a(白噪聲方差)為估計參數(shù).ARMA相關矩估計方法主要有最小二乘估計方法,最大似然估計,最大熵估計等等,考慮到傳感器節(jié)點的計算能力,這里我們采用最小二乘估計方法可解出?φ1,?φ2,?θ1,?σ2a.φ?1,φ?2,θ?1,σ?2a.判斷時間序列的穩(wěn)定性,其穩(wěn)定性條件為?φ1+?φ2<1,?φ2-?φ1<1,|?φ2|<1φ?1+φ?2<1,φ?2?φ?1<1,|φ?2|<1,如果滿足此條件則視為平穩(wěn)序列.則得出ARMA擬和模型為:Xt=?φ1Xt-1+?φ2Xt-2+at-?θat-1(2)Xt=φ?1Xt?1+φ?2Xt?2+at?θ?at?1(2)進一步地,我們利用逆函數(shù)法進行一步預測,ARMA的逆函數(shù)記為I1,I2,…,In,Ι1=?φ1-?θ1,Ι2=?φ2-Ι1?θ2,Ι3=Ιj?θ1?(j＞3)(3)I1=φ?1?θ?1,I2=φ?2?I1θ?2,I3=Ijθ?1?(j＞3)(3)則一步預測模型如式(14)所示,其中m為Xt之前m次觀測值,可根據(jù)預測精度的要求取值.Xt(1)=∑m∑mIjXt+1-j(4)其多步預測模型為:?Xt(l)=?φ1?Xt(l-1)+?φ2?Xt(l-2)(5)X?t(l)=φ?1X?t(l?1)+φ?2X?t(l?2)(5)在基于ARMA模型的主簇頭節(jié)點更換算法中,主簇頭節(jié)點根據(jù)數(shù)據(jù)流量的預測,一經發(fā)現(xiàn)數(shù)據(jù)流量將超過本節(jié)點負載的電池能量消耗,則立即發(fā)送更替主簇頭節(jié)點的請求.主簇頭節(jié)點更換算法的主要思想,引入預測機制,主簇頭節(jié)點在預測其自身能量將要消耗殆盡前發(fā)出更換主簇頭節(jié)點的請求,從而避免了主簇頭因為能量完全消耗而死亡,也避免了因為主簇頭死亡而造成網(wǎng)絡分割,降低網(wǎng)絡的生存時間.為判斷模型的預測精度,我們利用Matlab7.0進行了仿真驗證.如圖1(a)所示為一個WSN中主路由上的某一傳感器節(jié)點的真實網(wǎng)絡流量,從任意時刻起在256s內,每秒采樣數(shù)據(jù)流量1一次,利用本模型可計算出其估計值,其一步預測的比較圖如圖1(b)所示.從圖中可以看出,預測曲線和真實網(wǎng)絡流量曲線比較吻合,說明ARMA預測模型能夠有效預測WSN網(wǎng)絡流量,作為一種短時相關預測模型,ARMA預測模型的一步預測取得了較好的預測效果,且模型簡單,運算為線性運算,復雜度低,能夠作為一種實時網(wǎng)絡流量預測模型預測WSN網(wǎng)絡流量.2.2節(jié)點信息傳遞在某一普通節(jié)點完成數(shù)據(jù)監(jiān)測任務后,將會傳送監(jiān)測數(shù)據(jù)至主簇頭節(jié)點,然后主簇頭節(jié)點收集簇內監(jiān)測節(jié)點采集數(shù)據(jù)后,進行數(shù)據(jù)融合,再將融合數(shù)據(jù)發(fā)送到匯聚節(jié)點.普通節(jié)點為了能夠將數(shù)據(jù)發(fā)送到主簇頭節(jié)點,將需要維護自己鄰居節(jié)點的簡單的路由信息表以及主簇頭節(jié)點和從簇頭節(jié)點的相關信息.當自身的能量消耗超過預先設定的層次閾值ΔE時,該節(jié)點會將其新的能量層次值進行廣播(NOP消息),其鄰節(jié)點收到NOP消息后,便更新自己路由信息表中的數(shù)據(jù).在本文提出的簇內數(shù)據(jù)傳遞規(guī)則中,簇內節(jié)點并不像LEACH算法那樣采用單跳方式直接傳送采集數(shù)據(jù)到主簇頭節(jié)點,它采用多跳路由的方式將數(shù)據(jù)傳送給主簇頭節(jié)點.現(xiàn)在我們以圖2中的普通節(jié)點4例,來說明如何實現(xiàn)以多跳的方式將數(shù)據(jù)傳遞給主簇頭節(jié)點.第一步:節(jié)點4查找自己的路由信息表,獲取節(jié)點3和節(jié)點2的信息.第二步:設節(jié)點4和節(jié)點3的距離為d1,節(jié)點4和節(jié)點2的距離為d3,節(jié)點3和節(jié)點2的距離為d2.假設d2323<δ(d2121+d2222),那么節(jié)點4將數(shù)據(jù)傳遞給節(jié)點2.第三步:節(jié)點2檢查自距離主簇頭節(jié)點的距離l,發(fā)現(xiàn)l<3,則直接將數(shù)據(jù)傳遞給主簇頭節(jié)點.采用如下步驟進行處理:(1)如果l<3,(z,l)節(jié)點直接傳送數(shù)據(jù)到主簇頭節(jié)點,否則轉入下一步.(2)計算節(jié)點(z,l)和節(jié)點(z,l-1)的距離d1,(θ,f,z,l)和節(jié)點(z,l-2)的距離d3,節(jié)點(z,l-1)和節(jié)點(z,-2)的距離d2.如果d2323>δ(d2121+d2222),δ是根據(jù)實際網(wǎng)絡情況確定,則傳送數(shù)據(jù)到節(jié)點(z,l-1),節(jié)點(z,l-1)將本身采集數(shù)據(jù)和所接收數(shù)據(jù)進行數(shù)據(jù)融合,然后依據(jù)該數(shù)據(jù)傳遞規(guī)則繼續(xù)發(fā)送融合數(shù)據(jù)到下一跳節(jié)點,否則轉入下一步.(3)如果l<3,則等同于第一步,否則以當前節(jié)點為源節(jié)點,轉入(2)操作.總之,節(jié)點(z,l)在傳送數(shù)據(jù)到主簇頭節(jié)點的時候,會依次判斷是否把節(jié)點(z,t),t<l作為下一跳節(jié)點.如果是,則節(jié)點(z,l)傳送采集數(shù)據(jù)到節(jié)點(z,t),節(jié)點(z,t)將采集數(shù)據(jù)與接收數(shù)據(jù)進行融合計算,進行下一步傳送;否則,節(jié)點直接傳送數(shù)據(jù)到主簇頭節(jié)點.在網(wǎng)絡運行的穩(wěn)定階段也即數(shù)據(jù)傳輸階段,主簇頭節(jié)點負責收集簇內普通節(jié)點采集的數(shù)據(jù),然后對數(shù)據(jù)進行融合計算,然后通過多跳路由方式將融合數(shù)據(jù)通過鄰居主簇頭節(jié)點轉發(fā)至匯聚節(jié)點.具體過程描述如下:假設需要傳輸數(shù)據(jù)的主簇頭節(jié)點為(0,2,0,0),記為MCHi,距離匯聚節(jié)點的距離記為Di;記主簇頭節(jié)點MCHi相鄰m個主簇頭節(jié)點集合為Sn={MCHj,…,MCHm},主簇頭節(jié)點MCHi,MCHj,…,MCHm和匯聚節(jié)點之間的距離分別為Di,Dj,…Dk.具體路由過程可描述如下:第一步:設存在主簇頭節(jié)點集合Sv={MCHv|MCHv∈SN&Dv<Di},如果集合Sv為空,則主簇頭節(jié)點直接傳送融合數(shù)據(jù)到匯聚節(jié)點,否則轉到下一步).第二步:在集合Sv中選擇能量水平值最大的主簇頭節(jié)點,如果能量水平值最大的節(jié)點是唯一的,則將該節(jié)點作為下一跳路由節(jié)點,否則從多個能量相等的主簇頭節(jié)點中挑選Dv最小的主簇頭節(jié)點作為下一跳.第三步:將該主簇頭節(jié)點作為路由起始節(jié)點,重復上述操作.這樣,在每個采集信息的普通節(jié)點和匯聚節(jié)點之間就形成了一條穩(wěn)定的路徑,如圖6所示.3節(jié)點位置仿真為了評價本文提出算法的性能,本文在NS2仿真軟件中對算法進行仿真驗證.仿真環(huán)境具體配置如下:在500m×500m的正方形區(qū)域內,假設匯聚節(jié)點的坐標為(0,0),即坐標原點.以匯聚節(jié)點為原點建立坐標系,則200個傳感器節(jié)點均勻的分布在匯聚節(jié)點周圍.并且所有的傳感器節(jié)點以固定的頻率采集數(shù)據(jù),即節(jié)點以固定的頻率發(fā)送采集數(shù)據(jù),帶寬為20kB,時延為0.1s,且數(shù)據(jù)包的大小是固定的,均為2000bit,所有節(jié)點的初始能量值相等,均為0.25J,每層簇頭個數(shù)actual-ΝCΗ(i)=α(ri+ri-1)ri-ri-1?4<α<3π?actual?NCH(i)=α(ri+ri?1)ri?ri?1?4<α<3π?仿真中α取2π,此處π為周期律,εamp=0.0013pJ/bit/m2,Eelec=50nJ/bit,β=6.3.1節(jié)點死亡節(jié)點描述在傳感器網(wǎng)絡中,傳感器節(jié)點一般采用電池供電且不可更換,因此,降低能量消耗,延長網(wǎng)絡生命周期是設計網(wǎng)絡時要考慮的重要因素之一,網(wǎng)絡的存活節(jié)點數(shù)表明了隨著時間的推移,仍然存活的節(jié)點的總數(shù),是體現(xiàn)路由協(xié)議是否屬于能源有效性協(xié)議的一個重要指標.圖4表示隨時間推移網(wǎng)絡中處于存活狀態(tài)的節(jié)點個數(shù).根據(jù)仿真結果,LEACH算法在240s時出現(xiàn)第一個死亡節(jié)點,LEACH-F算法在200s時出現(xiàn)第一個死亡節(jié)點;本文提出的UCA-M算法的第一個死亡節(jié)點推遲在430s時出現(xiàn),因為UCA-M算法利用非均衡簇結構消除了多條路由算法中的“熱區(qū)”問題,網(wǎng)絡中簇頭節(jié)點能量消耗相對平衡,此外,算法還引入了主、從簇頭的概念,使網(wǎng)絡中簇頭的更換可以分布式的進行,從而整個網(wǎng)絡的性能得到了良好的改善.從上圖中,在430s到920s之間,UCA-M算法節(jié)點死亡的速度明顯比前兩個算法要快,這是因為在UCA-M算法前期,盡量是網(wǎng)絡能量均衡消耗;而到了網(wǎng)絡運行的后期階段,由于所有節(jié)點的剩余能量水平都很低,因此節(jié)點也會在這一階段相繼死亡,網(wǎng)絡質量快速下降.3.2評估uca-m和letch-m的負載在分簇的傳感器網(wǎng)絡中,簇頭扮演著極其重要的角色,簇頭能量消耗的快慢直接影響著整個網(wǎng)絡的性能好壞.本文主要以網(wǎng)絡中簇頭節(jié)點的負載均衡度來衡量整個網(wǎng)絡的負載.具體計算公式如下:LBF=11+1mm∑i=1(ki-ˉ?)2(6)其中,ki表示第i個簇頭的負載,ˉ?表示平均負載.從圖5中我們可以很明顯的看出,UCA-M算法的LBF比LEACH算法和LEACH-C算法高,說明了UCA-M算法中簇頭節(jié)點的的負載比較均衡.這是因為UCA-M算法中,距離匯聚節(jié)點近的簇頭節(jié)點所管理的成員節(jié)點