楊桂松,梁聽聽,何杏宇

1(上海理工大學 光電信息與計算機工程學院,上海 200093)2(上海理工大學 公共實驗中心,上海 200093)

1 引 言

無線傳感器網(wǎng)絡(Wireless Sensor Networks,WSNs)是由隨機部署在監(jiān)測區(qū)域并通過無線網(wǎng)絡連接的大量傳感器節(jié)點組成,因其低功耗、低成本、分布式和自組織的特點使得其在軍事、環(huán)境、醫(yī)療與空間探索等領域得到了廣泛的應用[1].

在無線傳感器網(wǎng)絡通信中,路由算法不僅決定著數(shù)據(jù)傳輸?shù)穆窂?同時也影響著網(wǎng)絡性能[2].然而,傳感器節(jié)點通信能力、能量受限和應用環(huán)境不穩(wěn)定等因素的存在,使得實際網(wǎng)絡中的通信鏈路不可靠,因此經(jīng)常出現(xiàn)節(jié)點故障導致網(wǎng)絡不可達和鏈路不可靠導致數(shù)據(jù)丟失等問題[3,4].例如,文獻[5]對無線鏈路時延和可靠性的模糊性、隨機性以及時變性進行統(tǒng)一建模,來反映真實的鏈路狀態(tài).文獻[6]提出了一種基于全局和局部可靠性的無線傳感器網(wǎng)絡路由協(xié)議,該協(xié)議中,通過定義節(jié)點的中介度和依賴度來分別反映節(jié)點的全局可靠性和局部可靠性,其中節(jié)點依賴度的定義與相鄰節(jié)點之間的鏈路質量有關,在考慮節(jié)點的全局可靠性與局部可靠性的同時,保證了數(shù)據(jù)傳輸?shù)木W(wǎng)絡可靠性.

而機會路由也是無線傳感器網(wǎng)絡中數(shù)據(jù)傳輸可靠性的一種常用的方法,它是由Biswas S和Morris R首次提出的[7],其主要思想是在源節(jié)點向目的節(jié)點發(fā)送數(shù)據(jù)包的過程中選擇一系列候選轉發(fā)節(jié)點集,并且為其中的每個節(jié)點分配優(yōu)先級.源節(jié)點首先將數(shù)據(jù)包發(fā)送給第一跳候選轉發(fā)節(jié)點集,在轉發(fā)節(jié)點集中收到數(shù)據(jù)包且具有最有優(yōu)先級的節(jié)點將轉發(fā)到下一跳候選轉發(fā)集,如果數(shù)據(jù)包已由較高優(yōu)先級的節(jié)點轉發(fā),則較低優(yōu)先級的節(jié)點將丟棄該數(shù)據(jù)包,按此重復,直到目的節(jié)點收到數(shù)據(jù)包.

目前已有大量的文獻對機會路由進行了研究,比如文獻[8]提出機會路由通過充分利用無線信道的廣播特性,通過多個潛在中繼競爭、自主智能判斷進行下一跳選擇,進而提高吞吐量和傳輸可靠性.文獻[9]利用機會路由算法,中間節(jié)點協(xié)作以完成分組轉發(fā),提高了傳輸可靠性和網(wǎng)絡吞吐量.文獻[10]提出了一種基于多跳最優(yōu)位置的機會路由算法,源節(jié)點將選擇目標節(jié)點附近的鄰居作為候選轉發(fā)集,并選擇其間最短距離和最小跳數(shù)的路徑.文獻[11]提出節(jié)能機會路由,通過組合節(jié)點到匯聚節(jié)點的距離及其自身的剩余能量,在一維隊列的網(wǎng)絡模型中找到最優(yōu)的中繼節(jié)點位置.

文獻[12]結合機會路由和網(wǎng)絡編碼各自的優(yōu)勢,不僅在網(wǎng)絡中同時傳輸多個段的數(shù)據(jù)包,而且提高了網(wǎng)絡吞吐量.文獻[13]提出一種感知服務質量的機會路由協(xié)議來選擇轉發(fā)集并對其排序,通過實驗驗證該協(xié)議在能量效率、延遲和時間復雜度方面都適合于無線傳感器網(wǎng)絡.文獻[14]基于能耗最優(yōu)傳輸距離和節(jié)點剩余能量,構建了聯(lián)合優(yōu)化目標函數(shù),并根據(jù)數(shù)據(jù)包的時間敏感性相應調整發(fā)射功率.在文獻[15]中,作者提出了一種基于連通性的節(jié)能機會魯棒路由協(xié)議,該協(xié)議中,在計算數(shù)據(jù)轉發(fā)的預期成本時,它強調高度的網(wǎng)絡連接,以確保網(wǎng)絡的正常運行.文獻[16]針對網(wǎng)絡中節(jié)點忙或失效造成的數(shù)據(jù)丟失,設計了一種基于多路徑的可靠路由協(xié)議,將失效路徑上正在轉發(fā)的數(shù)據(jù)轉移到另一條有效的路徑,以保證數(shù)據(jù)傳輸可靠性.文獻[17]針對傳統(tǒng)的基于地理位置的重傳代價大,節(jié)點能耗高等挑戰(zhàn),提出了一種基于傳輸方向的機會路由算法,即一種新的候選集選擇算法來有效減小機會路由中候選轉發(fā)集的大小,進而減少網(wǎng)絡中的通信開銷.

與上述相關工作相比,本文強調節(jié)點在數(shù)據(jù)傳輸中的相鄰節(jié)點之間連通性的重要性,旨在選擇具有較大節(jié)點依賴指數(shù)的節(jié)點作為中繼以保證網(wǎng)絡可靠性.而大多數(shù)相關工作,例如文獻[10]和文獻[17],在做出路由決策時沒有考慮網(wǎng)絡中節(jié)點的連通性.另外,在本文的路由算法設計中,在選擇下一跳節(jié)點時,本文不僅考慮了候選轉發(fā)集中每個節(jié)點的節(jié)點依賴指數(shù)對網(wǎng)絡可靠性的影響,而且考慮了每個節(jié)點在作為候選中繼時對整體網(wǎng)絡可靠性的貢獻大小,最終選定了最優(yōu)中繼以保證網(wǎng)絡可靠性.

在本文提出的基于節(jié)點連通性的機會路由算法中,首先,根據(jù)節(jié)點間的依賴程度定義了節(jié)點依賴指數(shù)來量化傳輸數(shù)據(jù)過程中節(jié)點的重要性[18],建立了網(wǎng)絡模型;然后,定義了節(jié)點連通性的計算公式,并找到節(jié)點的候選轉發(fā)集使其能滿足網(wǎng)絡可靠性的要求;最后,通過仿真實驗的性能分析可知,數(shù)據(jù)傳輸可靠性機會路由使其既能滿足目標可靠性又能降低網(wǎng)絡能耗.

本文的其余部分如下:第2小節(jié)描述了使用的網(wǎng)絡模型,第3小節(jié)給出了詳細的路由算法的設計思想,所提方案的性能分析在第4小節(jié)展示,第5小節(jié)總結了本文的工作.

2 網(wǎng)絡模型

本文的目標是利用機會路由的思想在無線傳感器網(wǎng)絡中設計可靠的機會路由算法,找到合適的候選轉發(fā)集并設定候選轉發(fā)集節(jié)點的優(yōu)先級別.

源節(jié)點S把數(shù)據(jù)包以廣播方式發(fā)送后,可能有多個鄰居節(jié)點接收到數(shù)據(jù)包,只是因為節(jié)點間鏈路不可靠的因素導致了各節(jié)點間節(jié)點連通性的差異.為了計算任意兩點間的節(jié)點連通性,我們定義了節(jié)點依賴指數(shù)(Dependency Index,DI),以找出無線傳感器網(wǎng)絡中節(jié)點i與其鄰居j之間連通率P的關系.節(jié)點DI表示節(jié)點和其鄰居之間的依賴關系,以量化每個節(jié)點在轉發(fā)包的過程中對傳遞過程的重要性.當其他節(jié)點較多地依賴于該節(jié)點接收數(shù)據(jù)包時,此節(jié)點的重要性增加.

節(jié)點i與其鄰居j之間的依賴程度在其相應的節(jié)點連通性的影響下,與它們之間交換包的數(shù)量有關,則DIij的計算公式如下:

(1)

其中,Reci表示i擁有的所有數(shù)據(jù)包,Sendi表示i發(fā)送出去的數(shù)據(jù)包,SendS表示S發(fā)送出去的數(shù)據(jù)包,Recj表示j擁有的所有數(shù)據(jù)包.

基于上述定義,當鄰居j接收到節(jié)點i發(fā)出的所有數(shù)據(jù)包,并且j沒有接收到i未發(fā)送的數(shù)據(jù)包時,可以看出i和j之間有較高的依賴性.公式(1)的基本原理是,如果發(fā)送者對鄰居具有更高的依賴性,則表明發(fā)送者的其他鄰居不能以更高的概率轉發(fā)來自它的數(shù)據(jù)包.

針對節(jié)點i和其鄰居j之間的依賴指數(shù)DI的基本性質及三種可能情況,我們定義了其與網(wǎng)絡中節(jié)點連通性Pij相對應關系的三條規(guī)則,即網(wǎng)絡中所有節(jié)點及其鄰居均滿足以下三條規(guī)則:

規(guī)則1:若DIij=0,i和j之間的節(jié)點連通性Pij=0;

規(guī)則2:若DIij=1,i和j之間的節(jié)點連通性Pij=1;

規(guī)則3:若0

Pij=αP0·DIij+(1-α)P0

(2)

其中α是權重系數(shù).

根據(jù)以上規(guī)則,無線傳感器網(wǎng)絡的拓撲結構可以表示為基于節(jié)點依賴指數(shù)的加權圖,假設節(jié)點間兩兩通信且相互獨立,節(jié)點間依賴指數(shù)遵循其與節(jié)點連通性的三條規(guī)則.

3 路由算法

通過以上網(wǎng)絡模型的建立及其相關定義,我們可以計算出模型中任意兩點間的節(jié)點連通性,之后利用其性質,進行節(jié)點候選轉發(fā)集的選擇以及優(yōu)先級排序.

源節(jié)點S有數(shù)據(jù)包要發(fā)送到目的節(jié)點D,假設i為當前節(jié)點,記錄其所有鄰居jx及位置信息.首先將鄰居根據(jù)自身與目的節(jié)點的距離大小降序排列,記為Dist(jx,D),即節(jié)點jx與目的節(jié)點之間的距離,并且指定距離越小的節(jié)點優(yōu)先進行判斷,有如下假設:

Dist(j1,D)≥Dist(j2,D)≥…
≥Dist(jX-1,D)≥Dist(jX,D)

(3)

根據(jù)每對節(jié)點間節(jié)點連通性的計算,我們選擇候選轉發(fā)集的主要步驟如下.

步驟1.首先將i到jX的節(jié)點連通性記為PijX=pijX,將節(jié)點jX加入到i的候選轉發(fā)集listi中.從剩下的節(jié)點jx(x=1,2,3,…,X-1)中選出一個節(jié)點,按照距離優(yōu)先的原則選定節(jié)點jX-1,此時從i經(jīng)過jX-1到達jX的路徑連通性如下:

PijX-1jX=pijX-1·pjX-1jX

(4)

步驟2.若PijX≥PijX-1jX,則設定i與jX-1之間的直接鏈路不可靠,即進行如下操作:

Pmax=PijX

(5)

否則,則步驟3;

步驟3.則設定i與jX之間的直接鏈路不可靠,即進行如下操作:

Pmax=PijX-1jX

(6)

步驟4.按照距離優(yōu)先的原則從剩下的鄰居jx(x=1,2,3,…,X-2)中選出節(jié)點jX-2,用同樣的方法判斷i經(jīng)過jX-2到達jX的路徑連通性PijX-2jX,與之前選出的Pmax進行比較,同樣,較小的一方則設置所選中間節(jié)點與jX之間不可靠.

從i的所有鄰居節(jié)點jx(x=1,2,3,…,X)選出一個最大的路徑連通率的中間節(jié)點時,需要做(X-1)次判斷,假定找到的中間節(jié)點為jmax,即從節(jié)點i的鄰居集合中任選一個節(jié)點加入到點i到jX路徑中的情況下,選定節(jié)點jmax的路徑連通性PijmaxjX最大,并將其加入到候選轉發(fā)集Listi中,并將除jmax之外的其他鄰居節(jié)點與i之間的直接鏈路都設定為不可靠.

步驟5.若X=max,則說明從節(jié)點i到節(jié)點jX路徑上,在i的鄰居集合中沒有合適的節(jié)點可供選擇,則候選轉發(fā)集的選擇結束,為Listi={jX};否則,步驟6;

步驟6.令i=max(1≤max≤X-1),返回步驟1;

根據(jù)以上步驟,我們選定了節(jié)點i的候選轉發(fā)集Listi,此時i進行數(shù)據(jù)傳輸時,可實現(xiàn)的網(wǎng)絡可靠性如下:

(7)

圖1中,節(jié)點i有4個鄰居節(jié)點j1,j2,j3,j4,任意兩點間的節(jié)點連通性已經(jīng)給出,如圖1(a)所示.首先,將節(jié)點j4加入到候選轉發(fā)集Listi={j4}中,有pij4=0.4.按照距離優(yōu)先的原則,將鄰居j3加入到路徑中,路徑連通性Pij3j4=0.3×0.9=0.27<0.4,則將j3與i之間的直接鏈路設定為不可靠.之后,

將節(jié)點j2加入到路徑中,路徑連通性有Pij2j4=0.8×0.6=0.48>0.4,故i與j4之間的直接鏈路設定為不可靠.將節(jié)點j1加入到路徑中,路徑連通性Pij1j4=0.7×0.5=0.35<0.4,故j1與i之間的直接鏈路設定為不可靠.

經(jīng)過上述步驟,將節(jié)點j2加入到候選轉發(fā)集Listi={j4,j2},如圖1(b)所示.接下來需要在j2和j4之間找到連通性最大的路徑,有pj2j4=0.6.先將節(jié)點j3加入到j2與j4之間的路徑,路徑連通性Pj2j3j4=0.7×0.9=0.63>0.6,故將j2與j4之間的直接鏈路設定為不可靠.之后將j1加入,有路徑連通性Pj1j2j4=0.9×0.6=0.54<0.6,將j1與j2之間的直接鏈路設定為不可靠,選定節(jié)點j3加入到j2與j4之間的路徑,如圖1(c)所示.

節(jié)點j3加入到候選轉發(fā)集Listi={j4,j2,j3},需要判斷j3和j4之間連通性最大的路徑,有pj3j4=0.9,將節(jié)點j1加入到其路徑中有Pj1j3j4=0.6×0.9=0.54 < 0.9,令j1與j3之間的直接鏈路為不可靠,如圖1(d)所示.最后,i與j4之間連通性最大的路徑已經(jīng)確定為i-j2-j3-j4,此時i的候選轉發(fā)集Listi={j4,j3,j2}.因此,根據(jù)公式(7),節(jié)點i進行數(shù)據(jù)傳輸時,可實現(xiàn)的網(wǎng)絡可靠性為Ri=1-(1-0.8)×(1-0.3)×(1-0.4).

基于節(jié)點連通性的機會路由算法偽代碼如下.

算法1.基于節(jié)點連通性的機會路由算法

1.輸入:節(jié)點i和鄰居jx(x=1,2,…,X);

2. 初始化:listi=null;

3. 按照鄰居與目的節(jié)點之間的距離大小降序排列,記為{j1,j2,j3,…,jX};

4.for(n=1;n<=X;n++)

5. 計算pijX;

6.Pmax=PijX;

7.for(m=X-1;m<=1;m--)

8. 計算PijmjX=pijm·pjmjX;//公式(3)

9.if(PijmjX>Pmax)

10.Pmax=PijmjX;//公式(6)

11.endif

12.endfor

13. //選擇候選轉發(fā)集

14.listi=listi∪{jm};

15.if(PijX==Pmax)

16. break;

17.else

18.i=jm;

19.endif

20. end for

21. 計算網(wǎng)絡可靠性Ri;//公式(7)

22.while(Nodeibroadcaststhepackets)

23. sort the listlistiin increasing order based on the distance node and the destination node;

24.for(k=1;k<=|listi|;n++)

25.if(Thekth node inlistireceived the packets from nodei)

26. Thekth node is selected as the next hop to forward the packets;

27. The other nodes inlistiwill drop the packets;

28.end

29.endfor

30.endwhile

4 性能分析

我們的模擬實驗在MATLAB下進行.在該模擬中,傳感器節(jié)點在網(wǎng)絡區(qū)域中隨機部署.本文中,我們將提出的基于節(jié)點連通性的機會路由算法NCOR與POFA路由算法[19]和ExOR路由算法[7]進行比較,分別評估其在網(wǎng)絡可靠性和能耗方面的性能.部分參數(shù)選擇如表1所示.

表1 實驗室的網(wǎng)絡環(huán)境參數(shù)
Table 1 Network environment parameters

參數(shù)取值檢測區(qū)域范圍(0,0)-(400,400)m節(jié)點通信半徑30m節(jié)點個數(shù)200,400,600,800,1000,1200初始化能量1J節(jié)點依賴指數(shù)0.55,0.6,0.65,0.7,0.75,0.8,0.85,0.9,0.95εamp0.0013Pj/bit/m4εfs10Pj/bit/m4數(shù)據(jù)包大小512bytes傳輸速率1MbpsMACIEEE802.11

在圖2中,所有算法的網(wǎng)絡可靠性均隨著節(jié)點依賴指數(shù)的增加而增加,且NCOR優(yōu)于其他路由算法.原因是節(jié)點之間的依賴指數(shù)的增加說明節(jié)點之間包的交互增加,而包交互和鏈路質量緊密相關,這直接提高了節(jié)點之間的連通性,也因此提高了網(wǎng)絡可靠性.POFA僅使用預期的傳送概率度量來選擇一些能夠保證可靠性的節(jié)點作為下一跳以確保網(wǎng)絡可靠性.

圖3中,我們驗證了節(jié)點數(shù)的變化對網(wǎng)絡可靠性的影響,當節(jié)點數(shù)量在200到1600之間增加時,與POFA和ExOR算法相比,NCOR實現(xiàn)的網(wǎng)絡可靠性較高,而且隨著節(jié)點個數(shù)的增加,網(wǎng)絡可靠性曲線呈現(xiàn)上升趨勢.因為節(jié)點數(shù)量的增加,增加了節(jié)點間的連通性,提高了節(jié)點成功傳輸數(shù)據(jù)包的概率,進而改善了網(wǎng)絡可靠性.如圖3所示,隨著網(wǎng)絡中節(jié)點數(shù)的增加,POFA算法所實現(xiàn)的網(wǎng)絡可靠性總是優(yōu)于ExOR算法.事實上,POFA是一種改進的泛洪算法,其主要思想就是在傳輸數(shù)據(jù)包的過程中,可以充分選擇收到數(shù)據(jù)包的節(jié)點作為中繼完成數(shù)據(jù)包的傳輸,而隨著網(wǎng)絡中節(jié)點個數(shù)的增加,參與數(shù)據(jù)包的傳輸?shù)墓?jié)點數(shù)也隨之增加,因此,相較于ExOR算法,POFA算法能獲得較高的網(wǎng)絡可靠性.

能耗是指網(wǎng)絡在數(shù)據(jù)傳輸過程中節(jié)點消耗的總能量,能耗越小,說明算法在綜合情況下的能量消耗越小.

圖4中,隨著節(jié)點依賴指數(shù)的增加,所有算法的能耗均呈現(xiàn)下降趨勢.從節(jié)點依賴指數(shù)的定義可知,它與相鄰之間數(shù)據(jù)包的交互有關,而包的交互受到節(jié)點間鏈路質量的影響,因此,節(jié)點依賴指數(shù)越大,說明鏈路質量較好,因此保證了數(shù)據(jù)包的可靠傳輸,降低了節(jié)點的能耗.

圖5說明的是網(wǎng)絡中能耗隨著節(jié)點個數(shù)的變化趨勢,NCOR的能耗相較POFA和ExOR較低,且POFA的能耗高于ExOR.ExOR算法的中繼是由候選轉發(fā)集中的節(jié)點的競爭產(chǎn)生,每個接收者依據(jù)它在列表里的位置在發(fā)送確認包之前延遲一段時間,各個節(jié)點查看收到的確認包集合來決定是否轉發(fā)包.在ExOR算法每一次路由中繼選擇的過程中,均會選擇一個最優(yōu)的節(jié)點進行數(shù)據(jù)包的傳輸,而在POFA算法中,收到數(shù)據(jù)包的節(jié)點均可被中繼節(jié)點繼續(xù)數(shù)據(jù)包的傳輸過程,且隨著節(jié)點依賴指數(shù)或者網(wǎng)絡中節(jié)點數(shù)的增加,該過程造成了大量的冗余傳輸,產(chǎn)生大量的消耗.因此,相比于POFA算法,ExOR算法的能耗較低.

剩余能量對網(wǎng)絡生命周期有直接影響,如果具有較少剩余能量的節(jié)點總是被選為中繼節(jié)點,則它將很快耗盡,造成網(wǎng)絡壽命大幅度減少.因此,圖6和圖7分別驗證了節(jié)點依賴指數(shù)以及網(wǎng)絡中的節(jié)點數(shù)對節(jié)點的剩余能量的影響.在該實驗中,我們記錄了多輪源節(jié)點與目的節(jié)點之間所有中繼節(jié)點的剩余能量,并以所有節(jié)點在所有輪次中的剩余能量的平均值作為輸出結果,最終得到了剩余能量隨著節(jié)點依賴指數(shù)以及節(jié)點數(shù)的變化趨勢.

如圖6所示,隨著節(jié)點依賴指數(shù)的增加,三種算法中所呈現(xiàn)的剩余能量均為上升趨勢,其中,隨著節(jié)點依賴指數(shù)的增加,NCOR的剩余能量一直高于ExOR和POFA算法,而且POFA算法中節(jié)點的剩余能量要低于ExOR算法.根據(jù)公式(2)中的定義,我們可知,節(jié)點依賴指數(shù)越大,則相鄰節(jié)點間的連通性則越來越好,在該相鄰節(jié)點之間的數(shù)據(jù)包成功傳輸概率也越來越高,因此節(jié)省了冗余傳輸帶來的節(jié)點傳輸數(shù)據(jù)包所消耗的能量,即節(jié)點本身的剩余能量隨著節(jié)點依賴指數(shù)的增加而增加.

圖7中,隨著網(wǎng)絡中節(jié)點個數(shù)的增加,三種算法中的剩余能量均呈現(xiàn)下降趨勢,其中,隨著節(jié)點個數(shù)的增加,NCOR的剩余能量一直高于ExOR和POFA算法,而且POFA算法中節(jié)點的剩余能量要低于ExOR算法.

經(jīng)驗證,隨著節(jié)點數(shù)的增加,相對于其他兩種算法,NCOR算法的性能一直保持最優(yōu)狀態(tài),受到網(wǎng)絡密度的影響較小,而且與經(jīng)典的機會路由算法ExOR相比,NCOR算法的性能較優(yōu).POFA算法是對傳統(tǒng)泛洪算法的一種改進,其最大的缺點仍然是隨著節(jié)點個數(shù)的增加,參與數(shù)據(jù)包傳輸?shù)墓?jié)點也隨之增加,因此造成了網(wǎng)絡中大量冗余數(shù)據(jù)包的傳輸,因此其節(jié)點的剩余能量加速減少.

5 總 結

在本文中,我們提出了一種基于節(jié)點連通性的機會路由算法,該算法在選擇候選轉發(fā)節(jié)點時考慮了相鄰節(jié)點之間的節(jié)點連通性,以保證數(shù)據(jù)傳輸?shù)目煽啃?仿真結果表明,該算法在網(wǎng)絡可靠性和網(wǎng)絡能耗方面優(yōu)于現(xiàn)有的經(jīng)典路由算法.未來的研究工作是設計一種更可靠的路由算法,促進傳感器節(jié)點之間的協(xié)同工作,保證數(shù)據(jù)傳輸中更高的節(jié)點可靠性,如使用信譽補償將數(shù)據(jù)傳輸?shù)狡渌细竦墓?jié)點[20].