低占空比無線傳感網(wǎng)絡(luò)中端到端的時延路由協(xié)議設(shè)計

徐 震，楊 蕾，周 龍

(武漢輕工大學 電氣與電子工程學院，湖北 武漢430023)

低占空比無線傳感網(wǎng)絡(luò)中端到端的時延路由協(xié)議設(shè)計

徐 震，楊 蕾*，周 龍

(武漢輕工大學 電氣與電子工程學院，湖北 武漢430023)

低占空比無線傳感網(wǎng)絡(luò)可以有效地提高網(wǎng)絡(luò)中節(jié)點的生存周期。但是它卻帶來一些額外的問題，如較長的等待延時等。另外，由于鏈路質(zhì)量的原因，一些數(shù)據(jù)需要多次傳輸才能成功，這不僅增加能量消耗，而且導(dǎo)致較大的時延問題。為解決這些問題，筆者提出了一種新穎的算法(DEtoERA)，通過計算不同傳輸模式下的時延和傳輸成功率選出最佳傳輸方式，在滿足延時要求的情況下節(jié)省能量。仿真結(jié)果表明，相對于ESL算法，這種算法能更好地節(jié)省能量和降低時延。

無線傳感網(wǎng)絡(luò)；低占空比；能量；時延

1 引言

無線傳感器網(wǎng)絡(luò)( Wireless Sensor Network， WSN)是由部署在監(jiān)測區(qū)域的大量體積小、成本低、具有無線通信、傳感、數(shù)據(jù)處理的傳感器節(jié)點通過自組織方式組成的一種網(wǎng)絡(luò)。無線傳感器節(jié)點通常由電池供電，傳感網(wǎng)絡(luò)大多部署在人煙稀少或是人類無法到達的地區(qū)，這給節(jié)點更換電池變得尤為困難。為解決這個關(guān)鍵問題，需要降低節(jié)點的能量消耗，使之獲得更長的網(wǎng)絡(luò)生命周期[1]。然而，在環(huán)境監(jiān)測預(yù)警系統(tǒng)等很多諸如此類應(yīng)用中，對信息的采集實時性要求較高。因此，針對此類無線傳感網(wǎng)絡(luò)應(yīng)用進行網(wǎng)絡(luò)協(xié)議設(shè)計時，需要綜合考慮能量和時延兩種因素。

為了降低傳感節(jié)點的能量消耗，一種有效的節(jié)能方法是使節(jié)點盡可能多地進入睡眠模式。Crossbow公司的數(shù)據(jù)[2]表明，如果節(jié)點一直保持在活躍模式下只能存活 100～120 h，而在1%的占空比下工作，其壽命可達一年以上。因此，低占空比 WSN 可以克服節(jié)點能量消耗問題，滿足長期監(jiān)測應(yīng)用的需求。然而，由于每個節(jié)點的周期性睡眠，會產(chǎn)生較長的延遲，因為發(fā)送節(jié)點必須等到它的鄰居節(jié)點醒來才能轉(zhuǎn)發(fā)數(shù)據(jù)包，這段等待時間被稱為等待時延。等待時延由設(shè)定的占空比周期決定。等待時延在低占空比WSN的端到端時延中占了主導(dǎo)。而且如果永遠選擇最先蘇醒的網(wǎng)絡(luò)節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，可能導(dǎo)致其與被選節(jié)點間的鏈路質(zhì)量差，從而消耗更多的能量，所以在進行低占空比無線傳感器網(wǎng)絡(luò)路由算法設(shè)計時，需要綜合考慮能量和時延兩種因素。

低占空比下的實時數(shù)據(jù)傳輸問題已經(jīng)引起許多學者的關(guān)注，文獻[3][4][5][6]提出了一些問題的解決方案。文獻[3]針對鏈式網(wǎng)絡(luò)和樹狀網(wǎng)絡(luò)，分別利用動態(tài)規(guī)劃和免疫遺傳算法通過增加節(jié)點的工作時隙以滿足端到端時延的約束。文獻[4]提出了一種利用2跳鄰居信息動態(tài)切換的實時路由協(xié)議框架來實現(xiàn)任意端到端之間的實時數(shù)據(jù)傳輸。文獻[5]提出了一種能夠有效解決時延的路由算法ESL，它通過尋找備用節(jié)點來減少多次重傳所帶來的時延，一旦傳輸失敗后，傳輸節(jié)點傳輸數(shù)據(jù)給備用節(jié)點，而不是重傳，這樣就減少低占空比下的等待延時，但是如果備選節(jié)點的鏈路質(zhì)量都較低時，會造成傳輸次數(shù)增加，也會造成較大的延時。文獻[6]等人提出了一種LES算法這種算法采用增加節(jié)點時隙的方式來減少延時，但由于時隙增加過多,導(dǎo)致能力過多消耗。為此，本文提出了一種DEtoERA算法，該算法能夠更好地解決低占空比網(wǎng)絡(luò)中的時延問題。

2 系統(tǒng)模型

2.1 模型假設(shè)

(1)整個網(wǎng)絡(luò)中所有節(jié)點時間是同步的。

(2)節(jié)點的工作調(diào)度表都是周期性的，一個工作周期被劃分成許多的時隙，每個時隙的持續(xù)時間是相同的。每一個時隙持續(xù)的時間長度能夠發(fā)送一個數(shù)據(jù)包或者接收一個探針包。由于數(shù)據(jù)包比探針包大很多，如果接收節(jié)點成功的接收了數(shù)據(jù)包，那么它能夠成功接收探針包。

(3)節(jié)點間的鏈路質(zhì)量基本保持不變。

(4)如果一個節(jié)點沒有數(shù)據(jù)需要傳輸，那么它在一個工作周期內(nèi)只蘇醒一次；但是如果它有數(shù)據(jù)需要傳輸，它可以在一個周期內(nèi)蘇醒多次。

(5)在傳輸數(shù)據(jù)時，無線傳感網(wǎng)絡(luò)中的數(shù)據(jù)沿著節(jié)點跳數(shù)減小的方向傳輸。

2.2 節(jié)點工作調(diào)度表的建立

節(jié)點工作調(diào)度表由上而下從sink節(jié)點開始建立，建立好工作調(diào)度表之后，該節(jié)點會將其工作調(diào)度表廣播到整個網(wǎng)絡(luò)。節(jié)點和鄰居共享其工作調(diào)度表。節(jié)點在更新其工作調(diào)度表之后會通知所有鄰居節(jié)點，在確定其所有鄰居節(jié)點都知道新的工作調(diào)度表后，該節(jié)點會在下一次蘇醒時啟動新的工作調(diào)度表。

2.3 數(shù)據(jù)傳輸模型

無線傳感網(wǎng)絡(luò)中，傳感器節(jié)點依據(jù)BFS(Breadth First Search)算法由各節(jié)點到匯聚節(jié)點的跳數(shù)分成不同的層，跳數(shù)相同的節(jié)點位于同一層。傳輸數(shù)據(jù)包時，無線傳感網(wǎng)絡(luò)中的數(shù)據(jù)沿著節(jié)點跳數(shù)減小的方向傳輸，此時傳輸路徑所包含的節(jié)點數(shù)目最少，為最短傳輸路徑。圖1為一個簡易的數(shù)據(jù)傳輸模型，節(jié)點A為源節(jié)點，假設(shè)在WA時刻節(jié)點A有一個數(shù)據(jù)包需要發(fā)送給sink節(jié)點，它需要通過其鄰居節(jié)點B, C, D中繼轉(zhuǎn)發(fā)來完成數(shù)據(jù)包的傳輸。則節(jié)點A需要從傳輸路徑PAB, PAC, PAD中選擇一條來傳輸數(shù)據(jù)。

圖1 基于鏈路質(zhì)量的傳輸模型

3 路由協(xié)議設(shè)計

如上圖1所示，這里有四個節(jié)點A, B, C, D。取周期T為100，他們的蘇醒時刻分別為WA、WB、WC、WD，圓圈下面的整數(shù)表示節(jié)點的工作時隙， 鏈路上面的數(shù)字表示鏈路質(zhì)量。只有鏈路質(zhì)量高于閾值θ，該條鏈路才存在。因為每個節(jié)點在一個周期內(nèi)只有一個工作時隙，為避免延遲過大，設(shè)定重傳不能超過2次。圖1所示的模型中有三種傳輸方法：

1、A到B，期望傳輸成功率和時延期望值分別為：

2、A到C，期望傳輸成功率和時延期望值分別為：

3、A到D，期望傳輸成功率和時延期望值分別為：

本文所要解決的問題是如何用較少的節(jié)點能量消耗來滿足端到端的延遲約束要求。根據(jù)傳輸能耗研究[9]，鏈路質(zhì)量反應(yīng)了數(shù)據(jù)傳輸?shù)哪芰肯某杀?。該問題可以轉(zhuǎn)換為一個優(yōu)化問題，目標是節(jié)點增加最少數(shù)量的工作時隙slot_num，約束條件是端到端延遲dij滿足給定的時延約束Δ。該優(yōu)化問題可以用式(1)(2)(3)(4)描述。

Φ+Ψ=1

(1)

ETRij≥θ

(2)

min(Φ*EDRij+Ψ*100/ETRij)

(3)

min(slot_num)

(4)

式(1)和(2)表明我們需要綜合考慮期望傳輸成功率和期望時延這兩個因素來選出一條最優(yōu)路徑。期望傳輸成功率因素會優(yōu)先選擇鏈路質(zhì)量好的路徑，而期望時延因素優(yōu)先選擇等待時延最低的路徑，兩者在目標實現(xiàn)上可能會存在沖突。為此我們根據(jù)具體的網(wǎng)絡(luò)環(huán)境分別給期望傳輸成功率和期望時延分配不同的權(quán)重Φ和Ψ。在式(2)中，如果選定的傳輸方式的期望傳輸時延小于這個閾值，則需要增加節(jié)點蘇醒時隙。但是一味地增加時隙，會導(dǎo)致節(jié)點的能量過多地消耗，降低節(jié)點的壽命，因此盡量少地增加時隙。

在圖1所示的傳輸模型中，節(jié)點A在上一層節(jié)點中有B, C和D，鏈路LAB，LAC和LAD對應(yīng)的期望傳輸成功率分別為0.78，0.94和0.88，對應(yīng)的時延期望值分別為80.76，97.74和107.67。三條傳輸路徑的時延期望值均滿足式(2)中的約束條件。根據(jù)式(4)三條路徑的計算結(jié)果分別為1.19，1.11和0.92，取最大值，即可得出這三條傳輸路徑中的最優(yōu)選擇。

將選中路徑的期望傳輸時延與期望傳輸時延閾值進行比較。若期望傳輸時延高于閾值，則需要增加時隙，增加時隙之后，節(jié)點在一個周期內(nèi)可以蘇醒2次，傳輸過程中的等待時延就會大大降低，數(shù)據(jù)的傳輸時延也會大大的降低。

在節(jié)點C的一個周期T上增加一個時隙。如圖2所示。

圖2 增加時隙后的傳輸模型

增加時隙后：

增加一個時隙之后，傳輸時延由原來的80.76降為現(xiàn)在的15.76。此時，由于節(jié)點在一個周期內(nèi)蘇醒2次，則三個周期最多可以傳輸6次。我們可以進行多次傳輸，這樣可以增大期望傳輸成功率，減少丟包率。因此，增加一個時隙能夠很好的解決低占空比無線傳感網(wǎng)絡(luò)中的時延問題。DEtoERA路由算法：見表1所示：

據(jù)調(diào)查，全市3個規(guī)模為100畝左右的糧食家庭農(nóng)場，稻麥兩熟一年純收入約8-12萬元，家庭農(nóng)場盈利能力明顯高于普通農(nóng)戶。而部分流轉(zhuǎn)面積在200畝左右，以經(jīng)營秧草、蔬菜、花木等設(shè)施農(nóng)業(yè)為主的農(nóng)地合作社，盈利能力比以種糧為主的家庭農(nóng)場還要更高些，除通過項目獲得國家財政補助外，其經(jīng)營性收入每畝地每年可凈贏利1500元左右。

表1 DEtoERA路由算法

輸入：無線網(wǎng)絡(luò)模型G=(V，E)；權(quán)重系數(shù)Φ，Ψ；閾值Δ．輸出：最低時延傳輸路徑Rmin．1．以匯聚節(jié)點S為根，通過BFS算法將節(jié)點V進行分層；2．從源節(jié)點A開始，計算其到鄰居節(jié)點的EDRij和ETRij；3．排除不滿足傳輸成功率閾值的傳輸路徑；if(ETRij<θ)刪除該Pij；4．計算每條路徑的優(yōu)化函數(shù)：Φ?EDRij+Ψ?ETRij，取最小值獲得最優(yōu)傳輸路徑；5．對于選出的路徑Pij，if(EDRij>Δ)，增加一個時隙slot，重新計算路徑時延是否滿足閾值，如果滿足約束條件則停止增加時隙；6．最低時延傳輸路徑Pmin為最終的傳輸路徑。

4 仿真實驗與性能評價

在本節(jié)，我們將通過仿真實驗來驗證DEtoERA算法的各項性能，通過各項性能指標將其與ESL算法來對比分析。

4.1 評價方法

對于DEtoERA算法，我們主要從以下兩個方面評估它的性能。

(1)數(shù)據(jù)單跳傳輸時延：在無線傳感網(wǎng)絡(luò)中，節(jié)點間數(shù)據(jù)傳輸是沿跳數(shù)逐漸減少的方向，本文主要考慮數(shù)據(jù)傳輸?shù)较乱惶?jié)點的時延。

(2)網(wǎng)絡(luò)壽命:從仿真開始到網(wǎng)絡(luò)中節(jié)點因能量耗盡而被廢棄的節(jié)點的數(shù)量超過30%所持續(xù)的時間。

4.2 仿真實驗參數(shù)

表2 仿真平臺參數(shù)

平臺參數(shù)取值節(jié)點個數(shù)100個鏈路質(zhì)量40%—95%節(jié)點周期100s節(jié)點時隙1s單次傳輸耗能1節(jié)點總能量50000

4.3 網(wǎng)絡(luò)性能仿真評價

在不同占空比條件下對DEtoERA算法的傳輸時延和網(wǎng)絡(luò)生命進行仿真模擬。

低占空比無線傳感網(wǎng)絡(luò)中，傳輸時延與節(jié)點的占空比有著很大的關(guān)系，占空比越大，則節(jié)點的工作時隙越多，傳輸時延越小。

圖3 節(jié)點占空比和傳輸時延

圖3顯示了兩種算法的延時期望隨著節(jié)點占空比變化的變化曲線。由仿真結(jié)果可知，節(jié)點的占空比從 1%變化到 5%。隨著占空比的增加，兩種算法的平均端到端延遲均顯著地降低，但DEtoERA算法的平均端到端時延一直保持最低，尤其是在占空比很低的情況下。

在低占空比無線傳感網(wǎng)絡(luò)中，網(wǎng)絡(luò)的壽命隨著節(jié)點占空比的增大而減小，占空比越高，節(jié)點的壽命越短。

圖4 節(jié)點占空比和網(wǎng)絡(luò)壽命

圖4顯示了兩種算法的網(wǎng)絡(luò)壽命隨著節(jié)點占空比變化的變化曲線。根據(jù)仿真結(jié)果可以看出，網(wǎng)絡(luò)的生命周期隨著節(jié)點占空比的增大而減少，但基于DEtoERA算法的網(wǎng)絡(luò)壽命始終保持著優(yōu)勢，尤其是在占空比很低的情況下，這是因為ESL算法采用尋找備選節(jié)點傳輸?shù)姆绞?，但這種方式一旦遇到較低的鏈路質(zhì)量時，重傳次數(shù)增大，也浪費更多的能量。而DEtoERA算法在選出最優(yōu)傳輸路徑的基礎(chǔ)上考慮是否需要增加時隙，這樣可以在保證延時較低的基礎(chǔ)上節(jié)省了能量，所以DEtoERA算法更能延長網(wǎng)絡(luò)的壽命。

5 結(jié)束語

本文針對低占空比無線傳感網(wǎng)絡(luò)存在節(jié)能和時延問題提出了一種新穎的算法(DEtoERA)。該算法通過計算不同傳輸路徑的期望時延和期望傳輸成功率來挑選出最佳傳輸方式，并在選出最佳傳輸方式的基礎(chǔ)上考慮是否需要增加時隙減少延時。仿真實驗結(jié)果表明本算法相比ESL算法能更好的節(jié)省能量和降低延時。

[1] 畢玉婷，陳 昕. 低占空比無線傳感器網(wǎng)絡(luò)能量感知路由算法[J].北京信息科技大學學報, 2012, 27(6): 93-98.

[2] Mote battery life calculator[EB/OL]. http://www.xbow.com/Support/wAppNotes.aspx,2013.01.05

[3] 李燕君，孫揚. 低占空比傳感網(wǎng)的端到端延遲控制方法[J]. 中南大學學報(自然科學版),2013(7): 171-175 .

[4] 陳權(quán)，高宏. 低占空比無線傳感器網(wǎng)絡(luò)中基于動態(tài)切換的實時路由協(xié)議[J]. 通信學報,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ào)度算法[J]. 軟件學報, 2014, 25(3): 631-641.

[7] 段軼, 吳小兵, 陳貴海. 低占空比無線傳感器網(wǎng)絡(luò)中的動態(tài)數(shù)據(jù)傳輸協(xié)議[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ǎng)絡(luò)簡單串行通信協(xié)議的設(shè)計[J]. 武漢工業(yè)學院學報, 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.

國家自然科學基金(61373091)

2095-7386(2016)04-0073-05

10.3969/j.issn.2095-7386.2016.04.014

TP 393

A