鐘達(dá)夫,薛晶晶,唐懿芳,趙仕俊

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

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

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

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

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

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

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

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

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

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

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

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

2 算法描述

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

圖2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

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

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

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

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

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

3.1 仿真設(shè)置

仿真實(shí)驗(yàn)采用NS2仿真平臺(tái),主要仿真參數(shù)設(shè)置如表1.

表1 仿真參數(shù)

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

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

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

3.2 仿真結(jié)果

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

圖4 存活節(jié)點(diǎn)個(gè)數(shù)

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

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

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

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

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

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

4 結(jié)論

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