基于分簇的無線傳感器網(wǎng)絡(luò)編碼算法①

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

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

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

3(企業(yè)信息化與物聯(lián)網(wǎng)測控技術(shù)四川省高校重點實驗室,自貢 643099)

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

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

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

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

1 隨機線性網(wǎng)絡(luò)編碼原理

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

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

圖1 傳統(tǒng)方法和隨機線性網(wǎng)絡(luò)編碼方法的信息傳輸比較

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

2 算法描述

基于簇的線性網(wǎng)絡(luò)編碼算法適用的網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖2,考慮基于簇的無線傳感器網(wǎng)絡(luò),網(wǎng)絡(luò)中大量的節(jié)點在單位時間內(nèi)采集的數(shù)據(jù)由簇頭傳輸給網(wǎng)關(guān)節(jié)點.從圖2可以看出,本文將網(wǎng)絡(luò)分為兩層.第一層中節(jié)點被分成許多簇,簇內(nèi)成員節(jié)點發(fā)送數(shù)據(jù)給簇頭節(jié)點.第二層是簇頭節(jié)點之間的通信,將采集的信息傳輸給基站.

圖2 網(wǎng)絡(luò)拓撲結(jié)構(gòu)

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

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

(2) 數(shù)據(jù)采集階段: 在數(shù)據(jù)采集階段,簇內(nèi)的每個節(jié)點發(fā)送自己的數(shù)據(jù)包給簇頭節(jié)點,簇頭完成相應(yīng)數(shù)據(jù)包的網(wǎng)絡(luò)編碼.簇頭節(jié)點在它的緩沖區(qū)內(nèi)采用隨機線性網(wǎng)絡(luò)編碼對N個數(shù)據(jù)包進行編碼,然后廣播編碼完成后的數(shù)據(jù)包.網(wǎng)絡(luò)編碼有許多優(yōu)點: 減少傳輸能量、提高網(wǎng)絡(luò)吞吐量.

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

中間的簇頭節(jié)點作為中繼節(jié)點將數(shù)據(jù)包成功的傳輸?shù)骄W(wǎng)關(guān)節(jié)點.在接收到n個獨立的編碼數(shù)據(jù)包后,在網(wǎng)關(guān)節(jié)點處通過線性方程被譯碼.

3 算法的仿真與結(jié)果分析

3.1 仿真設(shè)置

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

表1 仿真參數(shù)

在仿真過程中,本文假定節(jié)點部署之后是靜止的,所有節(jié)點是同構(gòu)的.網(wǎng)關(guān)節(jié)點的位置固定且離整個網(wǎng)絡(luò)較遠,數(shù)據(jù)經(jīng)過簇頭節(jié)點傳輸給網(wǎng)關(guān)節(jié)點.數(shù)據(jù)源為CBR 流,分別為 20、40、60、80、100.

網(wǎng)絡(luò)節(jié)點采用隨機分布方式進行布置,100節(jié)點分布如圖3所示.

圖3 網(wǎng)絡(luò)節(jié)點分布圖

3.2 仿真結(jié)果

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

圖4 存活節(jié)點個數(shù)

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

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

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

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

圖5 分組投遞率與源節(jié)點數(shù)的關(guān)系圖

圖6 端到端延時與源節(jié)點個數(shù)關(guān)系圖

4 結(jié)論

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