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

王辛果

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

?

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

王辛果**

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

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

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

1 引 言

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

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

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

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

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

2 系統(tǒng)模型

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

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

圖1 異步MAC協(xié)議

Fig.1 Asynchronous MAC protocol

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

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

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

圖2 路由決策

Fig.2 Routing decisions

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

圖3 路由機(jī)制比較

Fig.3 Routing schemes comparison

3 機(jī)會路由

3.1 路由過程

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

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

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

(1)

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

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

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

(2)

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

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

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

(3)

其中:

(4)

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

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

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

(5)

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

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

X(T)≤η。

(6)

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

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

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

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

(7)

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

(8)

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

(9)

4 仿真實驗

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

(10)

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

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

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

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

Fig.4Optimalstoppingtime(μ=3)

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

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

Fig.5Optimalstoppingtime(μ=30)

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

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

圖6 端到端時延比較

Fig.6 End-to-end delay comparison

5 結(jié) 論

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

[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].電訊技術(shù),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年于中國科技大學(xué)獲工學(xué)博士學(xué)位，現(xiàn)為工程師，主要研究方向為戰(zhàn)術(shù)數(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)絡(luò)的機(jī)會路由機(jī)制[J].電訊技術(shù)，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