王辛果

(中國西南電子技術研究所，成都 610036)

?

一種適用于異步無線傳感器網(wǎng)絡的機會路由機制*

王辛果**

(中國西南電子技術研究所，成都 610036)

無線傳感器網(wǎng)絡通常使用低占空比的異步睡眠調(diào)度來降低節(jié)點能耗。由于發(fā)送節(jié)點在接收節(jié)點醒來后才能向其發(fā)送數(shù)據(jù)，這將引入額外的等待時延。在最近的一些任播路由機制中，發(fā)送節(jié)點動態(tài)地選擇最先醒來的候選節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，以最小化等待時延。但是，由于從最先醒來的候選節(jié)點到基站的時延可能并不低，任播路由機制并不一定能最小化端到端總時延。為此，提出了一種適用于異步無線傳感器網(wǎng)絡的機會路由機制，將路由決策建模為強馬爾科夫過程，并根據(jù)最優(yōu)停止理論推導出該過程一種簡化的停止規(guī)則。仿真結果表明，節(jié)點到基站的最大端到端時延僅為基于地理位置的機會路由的68.5%。

無線傳感器網(wǎng)絡;異步睡眠調(diào)度;機會路由;低時延

1 引 言

無線傳感器網(wǎng)絡中的節(jié)點相互合作，將收集的數(shù)據(jù)通過多跳中繼的方式傳輸至基站作進一步處理。由于節(jié)點通常僅由電池供電，如何降低節(jié)點能耗是無線傳感器網(wǎng)絡協(xié)議需要重點考慮的問題。在采用睡眠調(diào)度的介質(zhì)訪問控制(Medium Access Control,MAC)協(xié)議中，節(jié)點僅在有數(shù)據(jù)傳輸時才切換至活躍狀態(tài)，無線通信模塊在大部分時間內(nèi)處于睡眠狀態(tài)，能大幅降低節(jié)點能耗。

根據(jù)節(jié)點間是否需要時間同步，睡眠調(diào)度分為同步和異步兩種。在同步睡眠調(diào)度中，相鄰節(jié)點需要頻繁地切換到活躍狀態(tài)進行時鐘同步。在異步睡眠調(diào)度中，每個節(jié)點獨立地進行狀態(tài)切換，節(jié)點在沒有數(shù)據(jù)發(fā)送時，只需偶爾醒來一小段時間來確定是否需要幫助相鄰節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。文獻[1]指出由于占空比更低，異步睡眠調(diào)度在低流量網(wǎng)絡中的能量效率更高。

在異步睡眠調(diào)度協(xié)議中，發(fā)送節(jié)點在接收節(jié)點醒來之后才能向其發(fā)送數(shù)據(jù)，這會引入額外的等待時延。最近的一些研究文獻[1-2]利用無線傳感器網(wǎng)絡中節(jié)點高密度部署的特點，采用任播路由機制降低異步睡眠調(diào)度引入的等待時延。在任播路由機制中，每個節(jié)點維護多個候選的轉(zhuǎn)發(fā)節(jié)點，并動態(tài)地選擇第一個醒來的候選節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。如果每個節(jié)點有N個候選節(jié)點，任播路由的平均等待時延僅為傳統(tǒng)的確定路由的1/N。與文獻[3]為了提升路由可靠性而選擇多個轉(zhuǎn)發(fā)節(jié)點不同，任播路由每次只選擇一個轉(zhuǎn)發(fā)節(jié)點，不占用額外的網(wǎng)絡容量。

由于沒有考慮從各候選節(jié)點到基站這部分時延的差異性，任播路由雖能最小化每一跳的等待時延，但不一定能最小化整條路徑上的端到端總時延。比如，任播路由可能會增加路徑跳數(shù)，從而增加端到端時延。文獻[4]考慮了異步睡眠調(diào)度的影響，設計了一種基于地理位置信息的機會路由機制。該路由機制使用節(jié)點的地理位置信息估計路徑跳數(shù)，動態(tài)地選擇第一個醒來且滿足地理前進門限α的候選節(jié)點，并通過調(diào)整門限α對單跳等待時延和路徑總跳數(shù)進行平衡，從而達到降低端到端時延的目的。但是，除了路徑跳數(shù)和等待時延，實際的端到端時延還取決于路徑質(zhì)量、待傳輸數(shù)據(jù)包的大小等，所以該協(xié)議也不能最小化端到端時延。

本文為異步無線傳感器網(wǎng)絡設計了一種能最小化端到端總時延的機會路由機制。發(fā)送節(jié)點評估通過已醒候選節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)到基站的總時延和等待更多候選節(jié)點醒來的額外時延，動態(tài)地決定何時停止繼續(xù)等待以最小化總時延。由于各個候選節(jié)點醒來的時間隨機，該路由決策過程被建模為強馬爾科夫過程。采用最優(yōu)停止理論推導出了路由決策過程的一種簡化的最優(yōu)停止準則。仿真結果表明，發(fā)送節(jié)點根據(jù)最優(yōu)停止準則在異步調(diào)度的網(wǎng)絡中進行機會路由能最小化端到端總時延。

2 系統(tǒng)模型

2.1 異步睡眠調(diào)度

假設除了基站一直處于活躍狀態(tài)，網(wǎng)絡中其余節(jié)點采用基于異步睡眠調(diào)度的MAC協(xié)議。如圖1所示，當沒有數(shù)據(jù)發(fā)送時，節(jié)點獨立地在活躍和睡眠狀態(tài)之間進行切換。節(jié)點在切換到活躍狀態(tài)后首先廣播發(fā)送信標消息向鄰居節(jié)點通告本節(jié)點已經(jīng)醒來[5]，并繼續(xù)保持活躍一小段時間以確定是否有其他節(jié)點向本節(jié)點發(fā)送數(shù)據(jù)。當節(jié)點有數(shù)據(jù)發(fā)送時，切換到活躍狀態(tài)，等待轉(zhuǎn)發(fā)節(jié)點醒來接收數(shù)據(jù)。節(jié)點處于睡眠狀態(tài)的時間是服從參數(shù)為λ的指數(shù)分布的隨機時間ts。為降低能耗，節(jié)點的活躍時間一般極短，而睡眠時間相對較長。在采用異步睡眠調(diào)度的MAC協(xié)議中，節(jié)點之間不需要進行時鐘同步，節(jié)點僅在有數(shù)據(jù)發(fā)送時的活躍時間較長，因而在數(shù)據(jù)流量相對較少的無線傳感器網(wǎng)絡中能大幅降低節(jié)點能耗。由于發(fā)送節(jié)點在接收節(jié)點醒來后才能向其發(fā)送數(shù)據(jù)，這將引入額外的等待時延[6]。

圖1 異步MAC協(xié)議

Fig.1 Asynchronous MAC protocol

2.2 異步網(wǎng)絡中的路由

在異步調(diào)度的網(wǎng)絡中進行路由時，除了考慮轉(zhuǎn)發(fā)節(jié)點的傳統(tǒng)路徑時延指標[7-8]，還應考慮到轉(zhuǎn)發(fā)節(jié)點醒來的時間。轉(zhuǎn)發(fā)節(jié)點醒來的時間越晚，數(shù)據(jù)轉(zhuǎn)發(fā)過程中引入的等待時延也就越長。

如圖2所示，假設發(fā)送節(jié)點s有N個候選轉(zhuǎn)發(fā)節(jié)點，記為R={r1,r2,…,rN}，分別通過N個候選節(jié)點轉(zhuǎn)發(fā)當前數(shù)據(jù)到基站的時延，記為TD={td1,td2,…,tdN}。由于采用異步睡眠調(diào)度，發(fā)送節(jié)點s不知道這些候選節(jié)點準確的醒來時間，只知道它們的睡眠調(diào)度參數(shù)λ。假設發(fā)送節(jié)點s在時間0有數(shù)據(jù)要發(fā)送，N個候選節(jié)點的醒來時間記為TW={tw1,tw2,…,twN}。如果節(jié)點s選擇第i個節(jié)點，則節(jié)點s發(fā)送本次數(shù)據(jù)到基站d的期望總時延為tt=twi+tdi。

圖2 路由決策

Fig.2 Routing decisions

如圖3所示，在傳統(tǒng)的確定路由機制[9]中，發(fā)送節(jié)點s選擇td值最小的轉(zhuǎn)發(fā)節(jié)點，不管該節(jié)點何時醒來，可能造成tw值太大；在任播路由機制[10]中，發(fā)送節(jié)點s選擇tw值最小的轉(zhuǎn)發(fā)節(jié)點，即最先醒來的節(jié)點，而不管該節(jié)點的td值大小。上述兩種路由協(xié)議都只關注了時延的一方面，機會路由則是綜合考慮TW和TD，動態(tài)地做出最優(yōu)的路由決策，選擇tt值最小的轉(zhuǎn)發(fā)節(jié)點。

圖3 路由機制比較

Fig.3 Routing schemes comparison

3 機會路由

3.1 路由過程

顯然，發(fā)送節(jié)點應該從所有已經(jīng)醒來的候選節(jié)點中選擇td值最小的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點。發(fā)送節(jié)點等待的時間越長，醒來的轉(zhuǎn)發(fā)節(jié)點越多，最終的td值越小，但tw值也越大。發(fā)送節(jié)點等待下一個候選節(jié)點醒來引入的額外等待時延期望值為(Nλ)-1。最優(yōu)機會路由決策應根據(jù)候選節(jié)點的數(shù)量N、TD分布和睡眠參數(shù)λ，決定何時停止繼續(xù)等待，以最小化端到端總時延tt。

將X(T)記為截止到時間T已經(jīng)醒來的轉(zhuǎn)發(fā)節(jié)點中最小的td值:

X(T)=min {tdi|i=1,2,…,M}。

(1)

式中：M是在[0,T]時間段內(nèi)醒來的節(jié)點數(shù)。顯然，X(T)是一個強馬爾科夫過程。

最優(yōu)機會路由應該最小化端到端總時延的期望值，即

minΨT=E[X(T)+T]。

(2)

如果發(fā)送節(jié)點s在時間0停止等待，此時沒有任何候選節(jié)點醒來。因此，假設X(0)為極大值，這能保證發(fā)送節(jié)點必須至少等待一個候選節(jié)點醒來。

3.2 最優(yōu)停止規(guī)則

由于轉(zhuǎn)發(fā)節(jié)點醒來的時間TW為隨機變量，可以將TD視為N個獨立同分布的隨機變量。根據(jù)最優(yōu)停止理論，將式(2)進行簡單推導后，可以得到

(3)

其中:

(4)

函數(shù)G(x)的物理意義是當已醒的候選節(jié)點中的最小td值為x時，繼續(xù)等待更多節(jié)點能夠獲得的td下降值的期望;F是TD的概率分布函數(shù)。

定理1：下面的等式有唯一解:

G(X(T))=(Nλ)-1。

(5)

證明：如果G(X(0))<(Nλ)-1，則意味著第一個醒來的轉(zhuǎn)發(fā)節(jié)點帶來的td下降值比等待第一個節(jié)點醒來導致的tw增加值還小，這與X(0)為極大值的假設矛盾。因此，可以認為G(X(0))≥(Nλ)-1必然成立。由于G是非正的、連續(xù)的、嚴格遞減的凸函數(shù)，所以等式(5)有唯一解，得證。

定理2：機會路由過程的最優(yōu)停止規(guī)則為

X(T)≤η。

(6)

式中：η是等式(5)中關于X的唯一解。

證明：假設To是等式(5)中關于T的解。由于G(x)隨x嚴格遞減而X(T)隨T不增，則G(X(T))隨T不減。當T≤To時，NλG(X(T))-1≥0，ΨT隨T不增；當T>To時，NλG(X(T))-1<0，ΨT隨T不減。ΨT在時間To處取最小值，不等式(6)是最優(yōu)停止規(guī)則，得證。

定理2表明，當X(T)≤η成立時，也即G(X(T))<(Nλ)-1時，應停止繼續(xù)等待。該條件蘊含的物理意義是當繼續(xù)等待能夠獲得的td下降值小于相應的tw增加值時，應該停止繼續(xù)等待。

當X(T)≤η成立時，已醒的候選節(jié)點數(shù)服從參數(shù)為F(η)的幾何分布，因而可以得到此時已醒節(jié)點數(shù)的期望值

(7)

和最優(yōu)停止時間的期望值

(8)

進一步可以計算得到采用最優(yōu)停止規(guī)則進行機會路由的端到端總時延期望值

(9)

4 仿真實驗

發(fā)送節(jié)點經(jīng)過候選轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)到基站的時延，依賴于較多的隨機變量，如每跳的等待時延、鏈路可靠性、候選節(jié)點數(shù)量等。因此，根據(jù)中心極限定理，可以認為TD大致服從正態(tài)分布。在網(wǎng)絡運行過程中，發(fā)送節(jié)點s根據(jù)統(tǒng)計的歷史信息估算TD的參數(shù):

(10)

首先，在Matlab平臺上進行數(shù)值仿真，驗證最優(yōu)停止規(guī)則的有效性。在仿真實驗中，發(fā)送節(jié)點有20個候選的轉(zhuǎn)發(fā)節(jié)點，每個轉(zhuǎn)發(fā)節(jié)點的睡眠參數(shù)λ設為1，即每個節(jié)點平均每1s醒來一次?？紤]兩組實驗場景，μ分別設為3和30。場景一中TD的均值相對較小，代表轉(zhuǎn)發(fā)節(jié)點離基站較近或發(fā)送數(shù)據(jù)長度較小的情形；場景二中TD的均值相對較大，代表轉(zhuǎn)發(fā)節(jié)點離基站較遠或發(fā)送數(shù)據(jù)長度較大的情形。

每組場景各運行1 000次，將仿真結果取平均值。橫軸為最優(yōu)停止時間，單位為已醒節(jié)點數(shù);縱軸表示的是發(fā)送節(jié)點到基站的端到端總時延，單位為秒。曲線的最低點表示路由過程的最優(yōu)停止時間點。

場景一:σ分別為0.1和0.3。如圖4所示，σ=0.1時，最優(yōu)的喚醒節(jié)點數(shù)為2；σ=0.3時，最優(yōu)的喚醒節(jié)點數(shù)為4。根據(jù)式(6)提供的停止規(guī)則進行路由時，喚醒的平均節(jié)點數(shù)分別為2.1和3.8，與最優(yōu)的喚醒節(jié)點數(shù)極其接近，相應的端到端總時延分別為3.044s和2.916s?？傮w來看，由于μ并不比λ-1大多少，發(fā)送節(jié)點很快就會停止繼續(xù)等待。μ相同的情況下，σ越大，各候選轉(zhuǎn)發(fā)節(jié)點之間的td值差異越大，發(fā)送節(jié)點在路由時越值得等待更長時間。

圖4 最優(yōu)停止時間(μ=3)

Fig.4Optimalstoppingtime(μ=3)

場景二:σ分別為1和3。如圖5所示，由于μ比λ-1大很多，路由時間相比場景一更長。具體來說，σ=1時，最優(yōu)的喚醒節(jié)點數(shù)為7;σ=3時，最優(yōu)的喚醒節(jié)點數(shù)為12。根據(jù)式(6)提供的停止規(guī)則進行路由時，喚醒的平均節(jié)點數(shù)分別為6.7和11.5，與最優(yōu)的喚醒節(jié)點數(shù)極其接近，相應的端到端總時延期望值分別為29.07s和25.91s。同樣，σ值越大，發(fā)送節(jié)點越值得等待更長時間。

圖5 最優(yōu)停止時間(μ=30)

Fig.5Optimalstoppingtime(μ=30)

接下來，通過NS2(Network-Simulationv2)網(wǎng)絡仿真平臺比較本文提出的機會路由與任播路由[10]、傳統(tǒng)路由[9]、基于地理位置的機會路由[4]的端到端時延。不失一般性，在半徑為1 000m的圓形區(qū)域內(nèi)，隨機部署800個通信半徑為150m的節(jié)點，基站位于圓心位置。節(jié)點的睡眠參數(shù)設為λ=1，通信速率為250kb/s。為保持公平性，根據(jù)數(shù)據(jù)包大小，分為小數(shù)據(jù)場景(長度為103B)和大數(shù)據(jù)場景(長度為105B)。每條鏈路的丟包率為均勻隨機生成，取值范圍為0.05～0.2。

如圖6所示，在小數(shù)據(jù)場景中，由于等待時延的權重高于數(shù)據(jù)傳輸時延，而傳統(tǒng)路由沒有考慮等待時延，其平均端到端時延遠高于其他3種路由機制；在大數(shù)據(jù)場景，由于數(shù)據(jù)傳輸時延的權重高于等待時延，而任播路由沒有考慮數(shù)據(jù)傳輸時延，其平均端到端時延最大。在上述兩種場景中，本文提出的機會路由的端到端時延均小于文獻[4]中的基于地理位置信息的機會路由。由于后者未考慮鏈路質(zhì)量對時延的影響，這種優(yōu)勢在大數(shù)據(jù)場景中尤為明顯，前者的最大端到端時延僅約為后者的68.5%。

圖6 端到端時延比較

Fig.6 End-to-end delay comparison

5 結 論

本文首先介紹了異步睡眠調(diào)度機制及其對無線傳感器網(wǎng)絡的重要性;接下來設計了一種適用于異步無線傳感器網(wǎng)絡的機會路由機制,根據(jù)候選轉(zhuǎn)發(fā)節(jié)點數(shù)、候選轉(zhuǎn)發(fā)節(jié)點的睡眠時間參數(shù)、統(tǒng)計得到的轉(zhuǎn)發(fā)時延分布動態(tài)選擇下一跳轉(zhuǎn)發(fā)節(jié)點;然后，將該路由決策過程建模為強馬爾科夫隨機過程，并推導出了一種簡化的最優(yōu)停止準則。仿真結果表明，機會路由能最小化發(fā)送節(jié)點到基站的端到端總時延。本文提出的機會路由機制有效且實現(xiàn)簡單，具有較強的實用性。

[1] WU Y. Energy-efficient wake-up scheduling for data collection and aggregation[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(2)：275-287.

[2] MERLIN C J，HEINZELMAN W B. Duty cycle control for low power listening MAC protocols[J].IEEE Transactions on Mobile Computing,2010,9(11)：1509-1521.

[3] 夏輝,王辛果,杜曉明. 一種適用于軍用無線自組網(wǎng)的可靠多徑路由協(xié)議[J].電訊技術,2014,54(11)：1549 -1553. XIA Hui,WANG Xinguo,DU Xiaoming. A reliable multipath routing protocol for military wireless ad hoc networks[J].Telecommunication Engineering,2014,54(11)：1549-1553.(in Chinese)

[4] NAVEEN K P，KUMAR A. Relay selection for geographical forwarding in sleep-wake cycling wireless sensor networks[J].IEEE Transactions on Mobile Computing,2013,12(3)：475-488.

[5] SUN Y,GUREWITZ O,JOHNSON D B. RI-MAC:a receiver initiated asynchronous duty cycle MAC protocol for dynamic traffic load[J]//Proceedings of the 6th ACM Conference on Embedded Networked Sensor Systems. Raleigh,USA：IEEE,2008：1-14.

[6] LI Z J,LI M O,LIU Y H. Towards energy-fairness in asynchronous duty-cycling sensor networks[J]//Proceedings of IEEE INFOCOM 2012. Orlando,USA：IEEE,2012：801-809.

[7] NITHYA R，MAHENDRAN N. A survey:duty cycle based routing and scheduling in wireless sensor networks[J]//Proceedings of 2015 IEEE International Conference on Electronics,Circuits,and System.Cairo,Egypt：IEEE,2015：813-817.

[8] ABRARDO A,BALUCANTI L,MECOCCI A. Distributed duty cycling optimization for asynchronous wireless sensor networks[J]//Proceedings of 2012 IEEE International Conference on Communications.Ottawa,Canada：IEEE,2012：637-641.

[9] LIU K，ABU-GHAZALEH N. Stateless and guaranteed geometric routing on virtual coordinate systems[J]//Proceedings of IEEE MASS 2008. Atlanta,USA：IEEE,2008：340-346.

[10] KIM J. Optimal anycast technique for delay-sensitive energy-constrained asynchronous sensor networks[J].IEEE Transactions on Networking,2011,19(2)：484-497.

王辛果(1983—)，男，四川遂寧人，2011年于中國科技大學獲工學博士學位，現(xiàn)為工程師，主要研究方向為戰(zhàn)術數(shù)據(jù)鏈、無線自組網(wǎng)等。

WANG Xinguo was born in Suining,Sichuan Province,in 1983. He received the Ph.D. degree from University of Science and Technology of China in 2011. He is now an engineer. His research concerns tactic data link,wireless ad hoc networks,etc.

Email:xinguowang911@163.com

An Opportunistic Routing Scheme for Asynchronous Wireless Sensor Networks

WANG Xinguo

(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

Wireless sensor networks usually adopt low duty-cycle asynchronous sleep schedule to reduce energy consumption of node. Since a sender can’t send data packet until the receiver wakes up,additional waiting delay will be introduced. In some recent anycast routing schemes,a sender dynamically selects the first candidate to wake up to forward data packet,in order to minimize the waiting delay. However,the delay from the first candidate to the base station may not be low,so anycast routing can not necessarily minimize the total end-to-end delay.For this problem,an opportunistic routing scheme is proposed for asynchronous wireless sensor networks,where routing decision is modeled as a strong-Markov process and a simplified stopping rule of this process is derived through optimal stopping theory. Simulation results show that the maximal end-to-end delay from the sender to the base station is only 68.5% of the opportunistic routing based on geographical location.

wireless sensor networks;asynchronous sleep schedule;opportunistic routing;low delay

10.3969/j.issn.1001-893x.2016.07.006

王辛果.一種適用于異步無線傳感器網(wǎng)絡的機會路由機制[J].電訊技術，2016,56(7):750-754.[WANG Xinguo.An opportunistic routing scheme for asynchronous wireless sensor networks[J].Telecommunication Engineering,2016,56(7):750-754.]

2016-03-23；

2016-06-06 Received date:2016-03-23；Revised date：2016-06-06

TN915.04;TN923

A

1001-893X(2016)07-0750-05

**通信作者：xinguowang911@163.com Corresponding author：xinguowang911@163.com