基于分簇的無線傳感器網絡編碼算法①

鐘達夫,薛晶晶,唐懿芳,趙仕俊

1(廣東科學技術職業學院 計算機工程技術學院(軟件學院),珠海 519090)

2(延安大學 物理與電子信息學院,延安 716000)

3(企業信息化與物聯網測控技術四川省高校重點實驗室,自貢 643099)

4(中國石油大學(華東) 信息與控制工程學院,青島 266580)

近幾年來,無線傳感器網絡(WSN)得到了廣泛關注,大量低成本的感知、處理器件以及有效的無線通信協議出現,使得該項技術被應用在各個領域,包括基礎設施保護、工業檢測和診斷、戰場和環境監測、家庭自動化、智能辦公、智能交通等[1–3].由于傳感器節點體積較小,所以攜帶的電池能量有限,存儲能力不足.通常節點部署在人無法直接到達的惡劣環境,無法給電池充電或者更換電池,當電池能量耗盡,這個節點就會“死亡”,在一定程度上影響整個網絡性能,所以在設計算法時需要考慮能量使用效率從而提高網絡性能,并有效延長網絡的使用壽命.目前,很多學者已經提出了最大化網絡使用壽命的若干算法.在多種方法中,成簇機制能夠有效節省節點能量,減少能耗,從而提高網絡使用壽命[4,5].

組網過程中,節點以成簇的方式被分成若干組[6],每組包括簇頭節點和簇內成員節點,簇內成員節點負責數據的采集并轉發給簇頭節點,并由網關節點轉發到基站.簇頭節點負責數據的轉發和融合,因此比其他節點消耗更多的能量.同時,如果簇頭在轉發來自簇內成員節點的數據時不經過處理,那么會消耗更多的能量.因此,本文中,在選擇簇頭節點時將節點剩余能量考慮在內,并使簇頭節點對收到的信息進行網絡編碼,從而優化網絡吞吐量,減少網絡負載.

分簇算法和隨機線性網絡編碼相結合,可以實現對采樣數據壓縮的目的,從而進一步節省網絡能量消耗.華國剛[7]于2005年提出將分布式信源編碼應用于連狀簇的方案,沿著信號路徑進行相關信源編碼.Mounir[8]在2010年提出將分布式信源編碼應用于多跳簇的方案,同時給出了兩種數據融合方式,即沿著信號路徑向前融合和向后融合.但是這兩種方案僅僅利用了兩個相鄰節點間的相關信息,壓縮效率較低,解碼比較復雜,同時在簇的形成過程中沒有考慮節點剩余能量.針對上述不足,本文嘗試將隨機線性網絡編碼應用到分簇的無線傳感器網絡中,由此延長網絡的生命周期,均衡網絡能量消耗.

1 隨機線性網絡編碼原理

隨機線性網絡編碼方法的核心思想是利用節點的運算能力,在發送節點處用線性編碼組合不同的信息包,在接收節點處獲得足夠的線性編碼組合后,通過運算得到原始信息包,其推廣了網絡編碼理論的應用范圍[9,10].

將傳統傳輸和隨機線性網絡編碼傳輸進行比較如圖1所示,無線節點B1需要發送信息包X、Y、Z.圖1(a)表示了傳統傳輸的情況,發送節點逐一發送信息包X、Y、Z; 圖1(b)表示了隨機線性網絡編碼傳輸的情況,當節點具有編碼能力,可以選取隨機參數編碼組合α1X+α2Y+α3Z、β1X+β2Y+β3Z、γ1X+γ2Y+γ3Z(其中的參數隨機獲得,參數值寫入編碼包中發送),廣播逐一發送編碼包,接收節點接收到三個編碼組合包后,通過線性運算可以解出原始信息包X、Y、Z完成信息傳輸.

圖1 傳統方法和隨機線性網絡編碼方法的信息傳輸比較

采用隨機線性網絡編碼方法,接收節點處理的問題從是否收到完整信息包,轉換為是否收到足夠多的滿足可解性條件的編碼包.通過研究發現[11–13],隨機線性編碼組合發送可以帶來良好的吞吐量、魯棒性、安全性等方面的增益,為網絡性能的改善提供了一種新的途徑.

2 算法描述

基于簇的線性網絡編碼算法適用的網絡拓撲結構如圖2,考慮基于簇的無線傳感器網絡,網絡中大量的節點在單位時間內采集的數據由簇頭傳輸給網關節點.從圖2可以看出,本文將網絡分為兩層.第一層中節點被分成許多簇,簇內成員節點發送數據給簇頭節點.第二層是簇頭節點之間的通信,將采集的信息傳輸給基站.

圖2 網絡拓撲結構

本文提出的算法被分為兩個階段,分別為簇形成階段與數據采集階段.

(1) 簇形成階段: 簇頭節點選擇同時考慮節點自身ID和剩余能量.在簇形成的開始階段,節點ID設為1,2,…,n,節點將其ID存入節點區.節點廣播的消息中包含節點自身ID值和剩余能量,在通信范圍內的節點會收到該消息.算法初始階段,節點剩余能量相同,簇頭選擇按照ID值,如果自身的ID值大于接收到節點的ID,該節點就會廣播簇頭當選通告.當一個采樣周期結束后,以節點剩余能量來選擇,如果自身的剩余能量大于接收到的節點的剩余能量,就會廣播簇頭當選通告.簇頭選擇好后,該節點會發布相應的當選消息,該消息包括自身ID值.網絡內的所有節點在時間Tw內收到簇頭競選通告.時間Tw后,如果一個節點只收到一個簇頭競選通告,即MCH_advertise=1,則該節點加入該簇,成為簇內成員,并向簇頭發送連接消息.如果一個節點接收到兩個以上的簇頭廣播通告,即MCH_advertise>1,則該節點根據接收信號強度(RSSI),選擇接收信號強度最大簇頭加入,成為其簇內成員.如果節點沒收到任何簇頭當選通告,即MCH_advertise=0,則該節點通告自己成為簇頭并形成獨立的簇.

(2) 數據采集階段: 在數據采集階段,簇內的每個節點發送自己的數據包給簇頭節點,簇頭完成相應數據包的網絡編碼.簇頭節點在它的緩沖區內采用隨機線性網絡編碼對N個數據包進行編碼,然后廣播編碼完成后的數據包.網絡編碼有許多優點: 減少傳輸能量、提高網絡吞吐量.

當從簇內節點接收到n個原始數據包(M1,M2,M3,…,Mn)后,在有限域F內隨機均勻的選擇一系列因子(g1,g2,…,gn),然后簇頭節點根據以下方程進行編碼:

中間的簇頭節點作為中繼節點將數據包成功的傳輸到網關節點.在接收到n個獨立的編碼數據包后,在網關節點處通過線性方程被譯碼.

3 算法的仿真與結果分析

3.1 仿真設置

仿真實驗采用NS2仿真平臺,主要仿真參數設置如表1.

表1 仿真參數

在仿真過程中,本文假定節點部署之后是靜止的,所有節點是同構的.網關節點的位置固定且離整個網絡較遠,數據經過簇頭節點傳輸給網關節點.數據源為CBR 流,分別為 20、40、60、80、100.

網絡節點采用隨機分布方式進行布置,100節點分布如圖3所示.

圖3 網絡節點分布圖

3.2 仿真結果

為了驗證和評估提出的算法,將標準協議AODV(Ad hoc On-demand Distance Vector routing)[14–16]和本文提出的算法在網絡生命周期、分組投遞率、網絡延時方面做了比較,圖4顯示了仿真時間內存活節點的總數,存活節點為0時刻定義為網絡的最大生存周期,由圖4可以看出,本文提出的算法和AODV協議相比,第一個節點死亡的時間和全部節點死亡都較晚,體現了本文提出的算法不僅使節點能耗降低而且能量消耗更加均衡.

圖4 存活節點個數

分組投遞率表示網絡使用該協議能夠支持的最大吞吐量,詳細刻畫了協議的性能和正確性.圖5(a)、(b)、(c)分別反映了源節點發送數據包的速率分別為2、10、20個分組時,兩個協議在不同數量源節點時的分組投遞率.

從圖5可以看出,本文提出的算法分組投遞率比AODV協議大,分組發送率是2時,結果不是很明顯,但是當分組發送率為10和20時,本文算法的分組投遞率遠大于AODV協議.這表明,本文協議在處理大負載的數據包時,丟包率更低,網絡穩定性、魯棒性也較好.

仿真結果表明,本文提出的協議網絡能耗更加均衡,有效延長了網絡生命周期,同時在分組投遞率和端到端延遲方面性能都比較優,而且更適用于大負載的無線網絡環境中.

圖6(a)、圖6(b)、圖6(c)分別反映了源節點發送數據包的速率分別為2、10、20個分組時,兩個協議源節點數量改變時端到端的延時圖.從圖6可以看出,當分組發送率為2時,本文提出的算法在源節點數量為20～60時延遲大于AODV,這是因為簇頭節點將數據包保存在自己的緩沖區,直到超過一定的數量才進行傳輸.然而當源節點數量超過60時,本文提出的協議明顯優于AODV.圖6(b)、圖6(c)表明,當源節點數量小于40時,本文提出的協議和AODV協議性能相同,但是當超過60后,本文的協議明顯優于AODV協議,這表明,本文的協議更適用于大負載的網絡環境中.

圖5 分組投遞率與源節點數的關系圖

圖6 端到端延時與源節點個數關系圖

4 結論

本文提出了基于簇的網絡編碼協議.通過讓簇頭節點進行網絡編碼,同時在選擇簇頭節點過程中,考慮節點剩余能量,從而均衡了網絡能量消耗,延長網絡生命周期,增加整個網絡的吞吐量; 只有簇頭節點進行網絡編碼并將數據包傳輸給網關節點,這樣能夠節省簇內成員節點的能量消耗.仿真結果表明本文提出的算法在延長網絡生命周期,均衡能量消耗,分組投遞率和端到端延遲方面明顯優于AODV協議,并且更適用于大負載的網絡環境.