徐 震,楊 蕾,周 龍
(武漢輕工大學(xué) 電氣與電子工程學(xué)院,湖北 武漢430023)
低占空比無(wú)線(xiàn)傳感網(wǎng)絡(luò)中端到端的時(shí)延路由協(xié)議設(shè)計(jì)
徐 震,楊 蕾*,周 龍
(武漢輕工大學(xué) 電氣與電子工程學(xué)院,湖北 武漢430023)
低占空比無(wú)線(xiàn)傳感網(wǎng)絡(luò)可以有效地提高網(wǎng)絡(luò)中節(jié)點(diǎn)的生存周期。但是它卻帶來(lái)一些額外的問(wèn)題,如較長(zhǎng)的等待延時(shí)等。另外,由于鏈路質(zhì)量的原因,一些數(shù)據(jù)需要多次傳輸才能成功,這不僅增加能量消耗,而且導(dǎo)致較大的時(shí)延問(wèn)題。為解決這些問(wèn)題,筆者提出了一種新穎的算法(DEtoERA),通過(guò)計(jì)算不同傳輸模式下的時(shí)延和傳輸成功率選出最佳傳輸方式,在滿(mǎn)足延時(shí)要求的情況下節(jié)省能量。仿真結(jié)果表明,相對(duì)于ESL算法,這種算法能更好地節(jié)省能量和降低時(shí)延。
無(wú)線(xiàn)傳感網(wǎng)絡(luò);低占空比;能量;時(shí)延
無(wú)線(xiàn)傳感器網(wǎng)絡(luò)( Wireless Sensor Network, WSN)是由部署在監(jiān)測(cè)區(qū)域的大量體積小、成本低、具有無(wú)線(xiàn)通信、傳感、數(shù)據(jù)處理的傳感器節(jié)點(diǎn)通過(guò)自組織方式組成的一種網(wǎng)絡(luò)。無(wú)線(xiàn)傳感器節(jié)點(diǎn)通常由電池供電,傳感網(wǎng)絡(luò)大多部署在人煙稀少或是人類(lèi)無(wú)法到達(dá)的地區(qū),這給節(jié)點(diǎn)更換電池變得尤為困難。為解決這個(gè)關(guān)鍵問(wèn)題,需要降低節(jié)點(diǎn)的能量消耗,使之獲得更長(zhǎng)的網(wǎng)絡(luò)生命周期[1]。然而,在環(huán)境監(jiān)測(cè)預(yù)警系統(tǒng)等很多諸如此類(lèi)應(yīng)用中,對(duì)信息的采集實(shí)時(shí)性要求較高。因此,針對(duì)此類(lèi)無(wú)線(xiàn)傳感網(wǎng)絡(luò)應(yīng)用進(jìn)行網(wǎng)絡(luò)協(xié)議設(shè)計(jì)時(shí),需要綜合考慮能量和時(shí)延兩種因素。
為了降低傳感節(jié)點(diǎn)的能量消耗,一種有效的節(jié)能方法是使節(jié)點(diǎn)盡可能多地進(jìn)入睡眠模式。Crossbow公司的數(shù)據(jù)[2]表明,如果節(jié)點(diǎn)一直保持在活躍模式下只能存活 100~120 h,而在1%的占空比下工作,其壽命可達(dá)一年以上。因此,低占空比 WSN 可以克服節(jié)點(diǎn)能量消耗問(wèn)題,滿(mǎn)足長(zhǎng)期監(jiān)測(cè)應(yīng)用的需求。然而,由于每個(gè)節(jié)點(diǎn)的周期性睡眠,會(huì)產(chǎn)生較長(zhǎng)的延遲,因?yàn)榘l(fā)送節(jié)點(diǎn)必須等到它的鄰居節(jié)點(diǎn)醒來(lái)才能轉(zhuǎn)發(fā)數(shù)據(jù)包,這段等待時(shí)間被稱(chēng)為等待時(shí)延。等待時(shí)延由設(shè)定的占空比周期決定。等待時(shí)延在低占空比WSN的端到端時(shí)延中占了主導(dǎo)。而且如果永遠(yuǎn)選擇最先蘇醒的網(wǎng)絡(luò)節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn),可能導(dǎo)致其與被選節(jié)點(diǎn)間的鏈路質(zhì)量差,從而消耗更多的能量,所以在進(jìn)行低占空比無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由算法設(shè)計(jì)時(shí),需要綜合考慮能量和時(shí)延兩種因素。
低占空比下的實(shí)時(shí)數(shù)據(jù)傳輸問(wèn)題已經(jīng)引起許多學(xué)者的關(guān)注,文獻(xiàn)[3][4][5][6]提出了一些問(wèn)題的解決方案。文獻(xiàn)[3]針對(duì)鏈?zhǔn)骄W(wǎng)絡(luò)和樹(shù)狀網(wǎng)絡(luò),分別利用動(dòng)態(tài)規(guī)劃和免疫遺傳算法通過(guò)增加節(jié)點(diǎn)的工作時(shí)隙以滿(mǎn)足端到端時(shí)延的約束。文獻(xiàn)[4]提出了一種利用2跳鄰居信息動(dòng)態(tài)切換的實(shí)時(shí)路由協(xié)議框架來(lái)實(shí)現(xiàn)任意端到端之間的實(shí)時(shí)數(shù)據(jù)傳輸。文獻(xiàn)[5]提出了一種能夠有效解決時(shí)延的路由算法ESL,它通過(guò)尋找備用節(jié)點(diǎn)來(lái)減少多次重傳所帶來(lái)的時(shí)延,一旦傳輸失敗后,傳輸節(jié)點(diǎn)傳輸數(shù)據(jù)給備用節(jié)點(diǎn),而不是重傳,這樣就減少低占空比下的等待延時(shí),但是如果備選節(jié)點(diǎn)的鏈路質(zhì)量都較低時(shí),會(huì)造成傳輸次數(shù)增加,也會(huì)造成較大的延時(shí)。文獻(xiàn)[6]等人提出了一種LES算法這種算法采用增加節(jié)點(diǎn)時(shí)隙的方式來(lái)減少延時(shí),但由于時(shí)隙增加過(guò)多,導(dǎo)致能力過(guò)多消耗。為此,本文提出了一種DEtoERA算法,該算法能夠更好地解決低占空比網(wǎng)絡(luò)中的時(shí)延問(wèn)題。
2.1 模型假設(shè)
(1)整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)時(shí)間是同步的。
(2)節(jié)點(diǎn)的工作調(diào)度表都是周期性的,一個(gè)工作周期被劃分成許多的時(shí)隙,每個(gè)時(shí)隙的持續(xù)時(shí)間是相同的。每一個(gè)時(shí)隙持續(xù)的時(shí)間長(zhǎng)度能夠發(fā)送一個(gè)數(shù)據(jù)包或者接收一個(gè)探針包。由于數(shù)據(jù)包比探針包大很多,如果接收節(jié)點(diǎn)成功的接收了數(shù)據(jù)包,那么它能夠成功接收探針包。
(3)節(jié)點(diǎn)間的鏈路質(zhì)量基本保持不變。
(4)如果一個(gè)節(jié)點(diǎn)沒(méi)有數(shù)據(jù)需要傳輸,那么它在一個(gè)工作周期內(nèi)只蘇醒一次;但是如果它有數(shù)據(jù)需要傳輸,它可以在一個(gè)周期內(nèi)蘇醒多次。
(5)在傳輸數(shù)據(jù)時(shí),無(wú)線(xiàn)傳感網(wǎng)絡(luò)中的數(shù)據(jù)沿著節(jié)點(diǎn)跳數(shù)減小的方向傳輸。
2.2 節(jié)點(diǎn)工作調(diào)度表的建立
節(jié)點(diǎn)工作調(diào)度表由上而下從sink節(jié)點(diǎn)開(kāi)始建立,建立好工作調(diào)度表之后,該節(jié)點(diǎn)會(huì)將其工作調(diào)度表廣播到整個(gè)網(wǎng)絡(luò)。節(jié)點(diǎn)和鄰居共享其工作調(diào)度表。節(jié)點(diǎn)在更新其工作調(diào)度表之后會(huì)通知所有鄰居節(jié)點(diǎn),在確定其所有鄰居節(jié)點(diǎn)都知道新的工作調(diào)度表后,該節(jié)點(diǎn)會(huì)在下一次蘇醒時(shí)啟動(dòng)新的工作調(diào)度表。
2.3 數(shù)據(jù)傳輸模型
無(wú)線(xiàn)傳感網(wǎng)絡(luò)中,傳感器節(jié)點(diǎn)依據(jù)BFS(Breadth First Search)算法由各節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的跳數(shù)分成不同的層,跳數(shù)相同的節(jié)點(diǎn)位于同一層。傳輸數(shù)據(jù)包時(shí),無(wú)線(xiàn)傳感網(wǎng)絡(luò)中的數(shù)據(jù)沿著節(jié)點(diǎn)跳數(shù)減小的方向傳輸,此時(shí)傳輸路徑所包含的節(jié)點(diǎn)數(shù)目最少,為最短傳輸路徑。圖1為一個(gè)簡(jiǎn)易的數(shù)據(jù)傳輸模型,節(jié)點(diǎn)A為源節(jié)點(diǎn),假設(shè)在WA時(shí)刻節(jié)點(diǎn)A有一個(gè)數(shù)據(jù)包需要發(fā)送給sink節(jié)點(diǎn),它需要通過(guò)其鄰居節(jié)點(diǎn)B, C, D中繼轉(zhuǎn)發(fā)來(lái)完成數(shù)據(jù)包的傳輸。則節(jié)點(diǎn)A需要從傳輸路徑PAB, PAC, PAD中選擇一條來(lái)傳輸數(shù)據(jù)。
圖1 基于鏈路質(zhì)量的傳輸模型
如上圖1所示,這里有四個(gè)節(jié)點(diǎn)A, B, C, D。取周期T為100,他們的蘇醒時(shí)刻分別為WA、WB、WC、WD,圓圈下面的整數(shù)表示節(jié)點(diǎn)的工作時(shí)隙, 鏈路上面的數(shù)字表示鏈路質(zhì)量。只有鏈路質(zhì)量高于閾值θ,該條鏈路才存在。因?yàn)槊總€(gè)節(jié)點(diǎn)在一個(gè)周期內(nèi)只有一個(gè)工作時(shí)隙,為避免延遲過(guò)大,設(shè)定重傳不能超過(guò)2次。圖1所示的模型中有三種傳輸方法:
1、A到B,期望傳輸成功率和時(shí)延期望值分別為:
2、A到C,期望傳輸成功率和時(shí)延期望值分別為:
3、A到D,期望傳輸成功率和時(shí)延期望值分別為:
本文所要解決的問(wèn)題是如何用較少的節(jié)點(diǎn)能量消耗來(lái)滿(mǎn)足端到端的延遲約束要求。根據(jù)傳輸能耗研究[9],鏈路質(zhì)量反應(yīng)了數(shù)據(jù)傳輸?shù)哪芰肯某杀?。該?wèn)題可以轉(zhuǎn)換為一個(gè)優(yōu)化問(wèn)題,目標(biāo)是節(jié)點(diǎn)增加最少數(shù)量的工作時(shí)隙slot_num,約束條件是端到端延遲dij滿(mǎn)足給定的時(shí)延約束Δ。該優(yōu)化問(wèn)題可以用式(1)(2)(3)(4)描述。
Φ+Ψ=1
(1)
ETRij≥θ
(2)
min(Φ*EDRij+Ψ*100/ETRij)
(3)
min(slot_num)
(4)
式(1)和(2)表明我們需要綜合考慮期望傳輸成功率和期望時(shí)延這兩個(gè)因素來(lái)選出一條最優(yōu)路徑。期望傳輸成功率因素會(huì)優(yōu)先選擇鏈路質(zhì)量好的路徑,而期望時(shí)延因素優(yōu)先選擇等待時(shí)延最低的路徑,兩者在目標(biāo)實(shí)現(xiàn)上可能會(huì)存在沖突。為此我們根據(jù)具體的網(wǎng)絡(luò)環(huán)境分別給期望傳輸成功率和期望時(shí)延分配不同的權(quán)重Φ和Ψ。在式(2)中,如果選定的傳輸方式的期望傳輸時(shí)延小于這個(gè)閾值,則需要增加節(jié)點(diǎn)蘇醒時(shí)隙。但是一味地增加時(shí)隙,會(huì)導(dǎo)致節(jié)點(diǎn)的能量過(guò)多地消耗,降低節(jié)點(diǎn)的壽命,因此盡量少地增加時(shí)隙。
在圖1所示的傳輸模型中,節(jié)點(diǎn)A在上一層節(jié)點(diǎn)中有B, C和D,鏈路LAB,LAC和LAD對(duì)應(yīng)的期望傳輸成功率分別為0.78,0.94和0.88,對(duì)應(yīng)的時(shí)延期望值分別為80.76,97.74和107.67。三條傳輸路徑的時(shí)延期望值均滿(mǎn)足式(2)中的約束條件。根據(jù)式(4)三條路徑的計(jì)算結(jié)果分別為1.19,1.11和0.92,取最大值,即可得出這三條傳輸路徑中的最優(yōu)選擇。
將選中路徑的期望傳輸時(shí)延與期望傳輸時(shí)延閾值進(jìn)行比較。若期望傳輸時(shí)延高于閾值,則需要增加時(shí)隙,增加時(shí)隙之后,節(jié)點(diǎn)在一個(gè)周期內(nèi)可以蘇醒2次,傳輸過(guò)程中的等待時(shí)延就會(huì)大大降低,數(shù)據(jù)的傳輸時(shí)延也會(huì)大大的降低。
在節(jié)點(diǎn)C的一個(gè)周期T上增加一個(gè)時(shí)隙。如圖2所示。
圖2 增加時(shí)隙后的傳輸模型
增加時(shí)隙后:
增加一個(gè)時(shí)隙之后,傳輸時(shí)延由原來(lái)的80.76降為現(xiàn)在的15.76。此時(shí),由于節(jié)點(diǎn)在一個(gè)周期內(nèi)蘇醒2次,則三個(gè)周期最多可以傳輸6次。我們可以進(jìn)行多次傳輸,這樣可以增大期望傳輸成功率,減少丟包率。因此,增加一個(gè)時(shí)隙能夠很好的解決低占空比無(wú)線(xiàn)傳感網(wǎng)絡(luò)中的時(shí)延問(wèn)題。DEtoERA路由算法:見(jiàn)表1所示:
據(jù)調(diào)查,全市3個(gè)規(guī)模為100畝左右的糧食家庭農(nóng)場(chǎng),稻麥兩熟一年純收入約8-12萬(wàn)元,家庭農(nóng)場(chǎng)盈利能力明顯高于普通農(nóng)戶(hù)。而部分流轉(zhuǎn)面積在200畝左右,以經(jīng)營(yíng)秧草、蔬菜、花木等設(shè)施農(nóng)業(yè)為主的農(nóng)地合作社,盈利能力比以種糧為主的家庭農(nóng)場(chǎng)還要更高些,除通過(guò)項(xiàng)目獲得國(guó)家財(cái)政補(bǔ)助外,其經(jīng)營(yíng)性收入每畝地每年可凈贏利1500元左右。
表1 DEtoERA路由算法
輸入:無(wú)線(xiàn)網(wǎng)絡(luò)模型G=(V,E);權(quán)重系數(shù)Φ,Ψ;閾值Δ.輸出:最低時(shí)延傳輸路徑Rmin.1.以匯聚節(jié)點(diǎn)S為根,通過(guò)BFS算法將節(jié)點(diǎn)V進(jìn)行分層;2.從源節(jié)點(diǎn)A開(kāi)始,計(jì)算其到鄰居節(jié)點(diǎn)的EDRij和ETRij;3.排除不滿(mǎn)足傳輸成功率閾值的傳輸路徑;if(ETRij<θ)刪除該P(yáng)ij;4.計(jì)算每條路徑的優(yōu)化函數(shù):Φ?EDRij+Ψ?ETRij,取最小值獲得最優(yōu)傳輸路徑;5.對(duì)于選出的路徑Pij,if(EDRij>Δ),增加一個(gè)時(shí)隙slot,重新計(jì)算路徑時(shí)延是否滿(mǎn)足閾值,如果滿(mǎn)足約束條件則停止增加時(shí)隙;6.最低時(shí)延傳輸路徑Pmin為最終的傳輸路徑。
在本節(jié),我們將通過(guò)仿真實(shí)驗(yàn)來(lái)驗(yàn)證DEtoERA算法的各項(xiàng)性能,通過(guò)各項(xiàng)性能指標(biāo)將其與ESL算法來(lái)對(duì)比分析。
4.1 評(píng)價(jià)方法
對(duì)于DEtoERA算法,我們主要從以下兩個(gè)方面評(píng)估它的性能。
(1)數(shù)據(jù)單跳傳輸時(shí)延:在無(wú)線(xiàn)傳感網(wǎng)絡(luò)中,節(jié)點(diǎn)間數(shù)據(jù)傳輸是沿跳數(shù)逐漸減少的方向,本文主要考慮數(shù)據(jù)傳輸?shù)较乱惶?jié)點(diǎn)的時(shí)延。
(2)網(wǎng)絡(luò)壽命:從仿真開(kāi)始到網(wǎng)絡(luò)中節(jié)點(diǎn)因能量耗盡而被廢棄的節(jié)點(diǎn)的數(shù)量超過(guò)30%所持續(xù)的時(shí)間。
4.2 仿真實(shí)驗(yàn)參數(shù)
表2 仿真平臺(tái)參數(shù)
平臺(tái)參數(shù)取值節(jié)點(diǎn)個(gè)數(shù)100個(gè)鏈路質(zhì)量40%—95%節(jié)點(diǎn)周期100s節(jié)點(diǎn)時(shí)隙1s單次傳輸耗能1節(jié)點(diǎn)總能量50000
4.3 網(wǎng)絡(luò)性能仿真評(píng)價(jià)
在不同占空比條件下對(duì)DEtoERA算法的傳輸時(shí)延和網(wǎng)絡(luò)生命進(jìn)行仿真模擬。
低占空比無(wú)線(xiàn)傳感網(wǎng)絡(luò)中,傳輸時(shí)延與節(jié)點(diǎn)的占空比有著很大的關(guān)系,占空比越大,則節(jié)點(diǎn)的工作時(shí)隙越多,傳輸時(shí)延越小。
圖3 節(jié)點(diǎn)占空比和傳輸時(shí)延
圖3顯示了兩種算法的延時(shí)期望隨著節(jié)點(diǎn)占空比變化的變化曲線(xiàn)。由仿真結(jié)果可知,節(jié)點(diǎn)的占空比從 1%變化到 5%。隨著占空比的增加,兩種算法的平均端到端延遲均顯著地降低,但DEtoERA算法的平均端到端時(shí)延一直保持最低,尤其是在占空比很低的情況下。
在低占空比無(wú)線(xiàn)傳感網(wǎng)絡(luò)中,網(wǎng)絡(luò)的壽命隨著節(jié)點(diǎn)占空比的增大而減小,占空比越高,節(jié)點(diǎn)的壽命越短。
圖4 節(jié)點(diǎn)占空比和網(wǎng)絡(luò)壽命
圖4顯示了兩種算法的網(wǎng)絡(luò)壽命隨著節(jié)點(diǎn)占空比變化的變化曲線(xiàn)。根據(jù)仿真結(jié)果可以看出,網(wǎng)絡(luò)的生命周期隨著節(jié)點(diǎn)占空比的增大而減少,但基于DEtoERA算法的網(wǎng)絡(luò)壽命始終保持著優(yōu)勢(shì),尤其是在占空比很低的情況下,這是因?yàn)镋SL算法采用尋找備選節(jié)點(diǎn)傳輸?shù)姆绞?,但這種方式一旦遇到較低的鏈路質(zhì)量時(shí),重傳次數(shù)增大,也浪費(fèi)更多的能量。而DEtoERA算法在選出最優(yōu)傳輸路徑的基礎(chǔ)上考慮是否需要增加時(shí)隙,這樣可以在保證延時(shí)較低的基礎(chǔ)上節(jié)省了能量,所以DEtoERA算法更能延長(zhǎng)網(wǎng)絡(luò)的壽命。
本文針對(duì)低占空比無(wú)線(xiàn)傳感網(wǎng)絡(luò)存在節(jié)能和時(shí)延問(wèn)題提出了一種新穎的算法(DEtoERA)。該算法通過(guò)計(jì)算不同傳輸路徑的期望時(shí)延和期望傳輸成功率來(lái)挑選出最佳傳輸方式,并在選出最佳傳輸方式的基礎(chǔ)上考慮是否需要增加時(shí)隙減少延時(shí)。仿真實(shí)驗(yàn)結(jié)果表明本算法相比ESL算法能更好的節(jié)省能量和降低延時(shí)。
[1] 畢玉婷,陳 昕. 低占空比無(wú)線(xiàn)傳感器網(wǎng)絡(luò)能量感知路由算法[J].北京信息科技大學(xué)學(xué)報(bào), 2012, 27(6): 93-98.
[2] Mote battery life calculator[EB/OL]. http://www.xbow.com/Support/wAppNotes.aspx,2013.01.05
[3] 李燕君,孫揚(yáng). 低占空比傳感網(wǎng)的端到端延遲控制方法[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版),2013(7): 171-175 .
[4] 陳權(quán),高宏. 低占空比無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中基于動(dòng)態(tài)切換的實(shí)時(shí)路由協(xié)議[J]. 通信學(xué)報(bào),2015, 36(10): 224-234.
[5] Zuzhi Fan. Delay-Driven Routing for low-duty-cycle sensor networks[J]. International Journal of Distributed Sensor Networks,2013:1-11
[6] 陳良銀, 王金磊等. 低占空比 WSN 中一種節(jié)點(diǎn)休眠調(diào)度算法[J]. 軟件學(xué)報(bào), 2014, 25(3): 631-641.
[7] 段軼, 吳小兵, 陳貴海. 低占空比無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的動(dòng)態(tài)數(shù)據(jù)傳輸協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展, 2011(s2):145-151
[8] R. Liu, K. Fan, P. Sinha, Locally scheduled packet bursting for data collection in wireless sensor networks[J]. Ad Hoc Networks, 2009,7 (5) :904-917
[9] Zhen Xu, Gao Lu. Energy-efficient and QoS-aware routing protocol for wireless sensor networks[C].In Proceedings of 7th International Symposium on Wireless and Pervasive Computing,2012:1-5.
[10] 劉婭,石雄. 基于高速公路的無(wú)線(xiàn)傳感網(wǎng)絡(luò)簡(jiǎn)單串行通信協(xié)議的設(shè)計(jì)[J]. 武漢工業(yè)學(xué)院學(xué)報(bào), 2011,30(1): 52-54.
[11] Zuzhi Fan, Shi Bai, et al. Delay-bounded transmission power control for low-duty-cycle sensor networks[J]. IEEE Transactions on Wireless Communications, 2015,14(6): 3157-3170
[12] Zhong Shen, Hai Jiang, et al. Fast data collection in linear duty-cycled wireless sensor networks[J]. IEEE Transactions on Vehicular Technology, 2014,63(4):1951-1957
An energy saving and low-latency scheduling algorithm in low-duty-cycle WSN
XU Zhen , YANG Lei, ZHOU Long
(School of electrical and electronic engineering, Wuhan polytechnic university,Wuhan 430023, China)
Low duty cycle of wireless sensor networks can be effective to improve the life of node in the network. But it brings some problems, such as a longer waiting delay. In addition, as a result of the unreliable link quality, some data need to be transported for many times, so it is not only waste of energy, but also have a long time delay. To solve this problem, a novel algorithm (DEtoERA) by calculating of time delay of different transport modes and transfer rate to select the best transmission mode has been raising. Saving energy under the satisfying the requirement of time delay. The simulation results show that compared with the ESL algorithm, this algorithm can better save energy and reduce the delay.
wireless sensor networks; Low Duty Cycle; energy; delay
2016-10-15.
徐震(1974-),博士,副教授,碩士生導(dǎo)師,E-mail:390667859@qq.com.
楊蕾(1979-),博士,副教授,E-mail:31477715@qq.com.
國(guó)家自然科學(xué)基金(61373091)
2095-7386(2016)04-0073-05
10.3969/j.issn.2095-7386.2016.04.014
TP 393
A