王 碩， 周 陽， 陳英偉， 周 桃， 嚴(yán)晞雋

(北京宇航系統(tǒng)工程研究所，北京 100076)

戰(zhàn)術(shù)無線自組網(wǎng)中穩(wěn)定多徑路由協(xié)議

王 碩， 周 陽， 陳英偉， 周 桃， 嚴(yán)晞雋

(北京宇航系統(tǒng)工程研究所，北京 100076)

在戰(zhàn)術(shù)通信網(wǎng)絡(luò)中，節(jié)點快速移動會導(dǎo)致網(wǎng)絡(luò)拓?fù)渥兓^快，從而頻繁觸發(fā)新的路由發(fā)現(xiàn)進(jìn)程，導(dǎo)致網(wǎng)絡(luò)穩(wěn)定性下降。提出了一種穩(wěn)定纏繞多徑路由協(xié)議SWMR，在利用源路由信息建立節(jié)點不相交多徑路由的同時，利用無線通信特性，構(gòu)建纏繞主路由間的備份路徑，減少網(wǎng)絡(luò)路由開銷，增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性。仿真結(jié)果表明，在網(wǎng)絡(luò)拓?fù)淇焖僮兓瘓鼍跋?，SWMR協(xié)議在快速移動發(fā)送成功率、平均端到端延時和歸一化路由開銷等方面與AOMDV和AODV協(xié)議相比具有一定優(yōu)勢。

戰(zhàn)術(shù)通信網(wǎng)絡(luò)； 自組網(wǎng)； 纏繞路徑； 多徑路由

0 引言

戰(zhàn)術(shù)無線自組網(wǎng)絡(luò)是一種在戰(zhàn)術(shù)環(huán)境下無需基礎(chǔ)設(shè)施的多跳臨時性無線自組移動網(wǎng)絡(luò)，具有無中心、自組織、多跳路由、獨(dú)立組網(wǎng)、節(jié)點移動等特點。在戰(zhàn)術(shù)無線自組網(wǎng)中，節(jié)點作為路由器需要轉(zhuǎn)發(fā)來自其他節(jié)點的分組信息。但是受移動性、通信范圍的限制，特別是在節(jié)點高速移動的情況下，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化很快，會頻繁觸發(fā)路由發(fā)現(xiàn)過程，增加路由開銷。

為了提高網(wǎng)絡(luò)路由的穩(wěn)定可靠性，戰(zhàn)術(shù)無線自組網(wǎng)中多采用多徑路由。在多徑路由協(xié)議中，只有當(dāng)所有路徑均失效后才會啟動新的路由發(fā)現(xiàn)，大大減少了路由開銷[1]。文獻(xiàn)[2]利用節(jié)點的地理位置信息將網(wǎng)絡(luò)劃分成不相交區(qū)域，快速建立最大限度不相交多徑路由；文獻(xiàn)[3]通過選擇鄰居節(jié)點變化率和路由長度低的節(jié)點來提高路由穩(wěn)定性；文獻(xiàn)[4]利用鏈路狀態(tài)感知信息及時切換備用路徑，以降低路由延時。但在以上路由協(xié)議中，當(dāng)某一段鏈路失效時，即使該路由上其他鏈路仍處于完好狀態(tài)，仍會導(dǎo)致該路由中斷，降低網(wǎng)絡(luò)性能。

為充分利用既有仍處于完好狀態(tài)的路由信息，增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性，本文提出了穩(wěn)定纏繞多徑路由協(xié)議(Stable Wrapped Multipath Routing，SWMR)。SWMR協(xié)議在源路由信息的基礎(chǔ)上，充分利用無線信道廣播通信的特性，在源-目的節(jié)點間的節(jié)點不相交主路由旁邊建立多條備份路徑，以實現(xiàn)對完好路徑的充分利用。

1 多徑路由穩(wěn)定性分析

網(wǎng)絡(luò)的路徑穩(wěn)定性同許多因素有關(guān)，比如說無線信道干擾、地理位置、節(jié)點移動性等。在本文的穩(wěn)定性分析中，不考慮其他因素，只考慮節(jié)點的移動性以及路徑相關(guān)性對路徑穩(wěn)定所產(chǎn)生的影響。

1.1 參考模型

節(jié)點S和D之間的多徑路由MP0，包括路徑P=(A1,A2,…,An)和路徑P=(B1,B2,…,Bn)，多徑路由MP1包括路徑P=(C1,C2,…,Cn)和路徑P=(E1,E2,…,En)。MP0與MP1有相同的跳數(shù)，但MP0是節(jié)點不相關(guān)的，而MP1是鏈路不相關(guān)(有共享節(jié)點)[5]。

假設(shè)每個節(jié)點的移動概率相同，均為p。對路徑P=(A1,A2,…,An)，其中斷概率為

p(Pbreak)=1-(1-p)n

(1)

其穩(wěn)定性概率為

p(Pstability)=(1-p)n。

(2)

定義MPi為包含兩條路徑的多徑路由,其中,i值為2條路徑的共享中間節(jié)點數(shù)。設(shè)其中第1條路徑的跳數(shù)為n，第2條為m。

對于MPi的穩(wěn)定性分析，可計算MPi2條路徑均中斷的概率。定義p(MPi)為MPi2條路徑均中斷的概率。

當(dāng)i=0時，

p(MP0)=p[Pbreak(A1,A2,…,An)]∩p[Pbreak(B1,B2,…,Bn)]=[1-(1-p)n][1-(1-p)m] 。

(3)

當(dāng)i=1時，

p(MP1)=p[Pbreak(C1,C2,…,Cn)]∩p[Pbreak(E1,E2,…,Em)]=[1-(1-p)n-1][1-(1-p)m-1]+p。

(4)

將p(MP1)和p(MP0)相減，即

f1(p)=p(MP1)-p(MP0)=p[1-(1-p)n-1-

(1-p)m-1+(2-p)(1-p)n-1(1-p)m-1]≥0 。

(5)

將p(MP2)和p(MP1)相減，即

f2(p)=p(MP2)-p(MP1)=p[1-(1-p)n-2-

(1-p)m-2+(2-p)(1-p)n-2(1-p)m-2]≥0 。

(6)

由式(5)、式(6)結(jié)果，對i值擴(kuò)展后可以得出

p(MPk)≥…≥p(MPl)≥…≥p(MP0)

(7)

式中,k>l>0，k

1.2 結(jié)論分析

從對上述節(jié)點不相關(guān)路徑和鏈路不相關(guān)路徑的穩(wěn)定性分析中，可以得出如下兩個結(jié)論。

1) 多徑路由的中斷概率與中間節(jié)點的移動性以及中間節(jié)點的個數(shù)相關(guān)。

2) 多徑路由的中斷概率還與路徑的相關(guān)性有聯(lián)系，即多徑路由中共用的節(jié)點數(shù)越少，其中斷的概率就越小。節(jié)點不相關(guān)的多徑路由，其穩(wěn)定性要好于鏈路不相關(guān)的多徑路由。

2 SWMR路由協(xié)議

為了減少由路由失效而導(dǎo)致額外的路由發(fā)現(xiàn)開銷，SWMR協(xié)議在每一對源-目的節(jié)點間構(gòu)建了2條節(jié)點不相交的主路由和若干纏繞在主路由周圍的備份路徑。當(dāng)源-目的節(jié)點主路由某一段鏈路失效斷開后，SWMR協(xié)議會啟用纏繞主路由周圍的備份路徑快速恢復(fù)主路由，從而避免整條主路由失效，減少重啟路由發(fā)現(xiàn)次數(shù)，從而減少網(wǎng)絡(luò)路由開銷。SWMR協(xié)議可分為路由建立和路由維護(hù)2部分。

2.1 路由建立

當(dāng)源節(jié)點有數(shù)據(jù)包發(fā)送但沒有到達(dá)目的節(jié)點的路由信息時，SWMR協(xié)議則啟動路由建立機(jī)制。SWMR路由建立機(jī)制主要完成在源-目的節(jié)點間發(fā)現(xiàn)和建立2條節(jié)點不相交的主路由和若干圍繞在主路由周邊的備份路徑。

SWMR協(xié)議路由建立可分為兩部分：1) 尋找從源節(jié)點s到目的節(jié)點d間可達(dá)路徑的路徑發(fā)現(xiàn)過程；2) 構(gòu)建從目的節(jié)點d到源節(jié)點s的不相交多徑路由及纏繞主路由間的備份路由的路徑構(gòu)建過程。

2.1.1 路徑發(fā)現(xiàn)

源節(jié)點首先廣播發(fā)送路由請求包RREQ，并建立路由表。網(wǎng)絡(luò)中間節(jié)點第1次從接收到的RREQ中獲取到所經(jīng)歷的路由信息后，將其前向廣播給鄰居節(jié)點。對后續(xù)接收到的RREQ，中間節(jié)點在判斷其跳數(shù)不大于第1個RREQ且與第1個RREQ經(jīng)過的路徑無交叉的情況下將其前向廣播，否則丟棄。

在AODV協(xié)議中，當(dāng)中間節(jié)點自身存在到達(dá)目的節(jié)點路由信息時，接收到路由請求RREQ后會直接向源節(jié)點發(fā)送路由回復(fù)包RREP。但如此一來，目的節(jié)點則可能收集不到足夠的RREQ所帶的路由探測信息，從而無法建立節(jié)點不相交多徑路由。因此，SWMR協(xié)議中只有目的節(jié)點才能給源節(jié)點發(fā)送路由回復(fù)包。

2.1.2 路徑構(gòu)建

當(dāng)目的節(jié)點接收到路由請求包RREQ后，按照接收時間順序從中選取2條節(jié)點不相交的主路由，然后通過主路由分別回傳路由回復(fù)包RREP。路由回復(fù)包可分為主路由回復(fù)包RREP和備份路由回復(fù)包RREP_AP。

在無線通信網(wǎng)絡(luò)中，節(jié)點通過電磁波在空間廣播的方式進(jìn)行信號傳輸，在電磁波通信范圍內(nèi)其他節(jié)點均能監(jiān)聽到該信息。借助該特性，SWMR協(xié)議在中繼回傳路由回復(fù)包RREP過程中構(gòu)建圍繞主路由的備份路徑。

圖1給出了SWMR協(xié)議建立圍繞主路由的備份路徑的過程示意。其具體過程如下。

1) 目的節(jié)點d接收到源節(jié)點s發(fā)起的多個路由請求RREQ，而a，b，c，e，f等中間節(jié)點在前傳RREQ的同時獲取了各自到達(dá)源節(jié)點的反向路由。

2) 目的節(jié)點d優(yōu)選出s-a-b-c-d作為主路由后，向節(jié)點c發(fā)送路由回復(fù)包RREP。

3) 目的節(jié)點d的鄰居節(jié)點c，g，j同時接收到該RREP。節(jié)點c接收到后記錄下主路由信息，并向節(jié)點b廣播。節(jié)點g，j監(jiān)聽到該RREP后，發(fā)現(xiàn)其存在到達(dá)主路由下一跳節(jié)點b的路由，則構(gòu)建一條到目的節(jié)點的備份路徑，并向節(jié)點b發(fā)送備份路由回復(fù)RREP_AP。RREP_AP只在1跳范圍內(nèi)傳播。

4) 節(jié)點b接收到RREP_AP后，將節(jié)點g， f作為備份路徑的下一跳記錄在路由表中。節(jié)點f，i接收到該RREP_AP后，發(fā)現(xiàn)自己不在主路由中，則丟棄該數(shù)據(jù)包。

5) 當(dāng)源節(jié)點s接收到節(jié)點a發(fā)送的RREP和節(jié)點e，h發(fā)送的RREP_AP后，則構(gòu)建s-a-b-c-d的主路由及纏繞期間的備份路徑，見圖1c，路徑構(gòu)建過程完畢。

圖1 主/備份路由建立過程Fig.1 Primary routes and backup routes construction

2.2 路由維護(hù)

在節(jié)點快速運(yùn)動導(dǎo)致網(wǎng)絡(luò)拓?fù)渥兓⒙酚墒r，SWMR協(xié)議啟動路由維護(hù)過程，主要面臨的情況有2種。

1) 前向發(fā)送數(shù)據(jù)包失敗。當(dāng)節(jié)點i向主路由下一跳節(jié)點j傳輸數(shù)據(jù)包失敗時，首先節(jié)點i從路由表中刪除經(jīng)節(jié)點j轉(zhuǎn)發(fā)的所有路由信息，然后查詢是否存在到達(dá)目的節(jié)點的備份路徑信息。如存在備份路徑則節(jié)點i通過已有的備份路徑轉(zhuǎn)發(fā)數(shù)據(jù)包;如不存在備份路徑或所有備份路徑均失效的情況下，節(jié)點i中止轉(zhuǎn)發(fā)數(shù)據(jù)包，并向源節(jié)點發(fā)送路由錯誤包RERR。

2) 接收到路由錯誤包RERR。當(dāng)中間節(jié)點i接收到節(jié)點j回傳的路由錯誤包RERR后，節(jié)點i從路由表中刪除經(jīng)節(jié)點j到達(dá)目的節(jié)點的路由信息，并回傳RERR。源節(jié)點收到RERR后，刪除該主路由信息，并將網(wǎng)絡(luò)負(fù)載重新分配到另一條主路由上。當(dāng)源-目的節(jié)點間所有路由均失效時，源節(jié)點啟動新一輪路由建立過程。

3 仿真環(huán)境及性能指標(biāo)

3.1 仿真環(huán)境設(shè)置

本文采用OPNET 14.5作為仿真平臺。節(jié)點隨機(jī)分布在仿真場景中，每個節(jié)點從仿真時間10 s開始產(chǎn)生數(shù)據(jù)分組直至仿真結(jié)束，數(shù)據(jù)源類型為CBR。數(shù)據(jù)鏈路層采用OPNET提供的IEEE 802.11 DCF無線接入?yún)f(xié)議，傳輸速率設(shè)置為2.4 Mbit/s。仿真的其他參數(shù)如表1所示[6-10]。

表1 仿真參數(shù)表

本文選擇經(jīng)典的單徑路由協(xié)議AODV和多徑路由協(xié)議AOMDV與SWMR協(xié)議進(jìn)行對比仿真分析。每個仿真結(jié)果為5個不同仿真種子實驗下仿真結(jié)果的平均。

3.2 仿真性能指標(biāo)

1) 發(fā)送成功率：接收端接收的數(shù)據(jù)包數(shù)/發(fā)送端發(fā)送的數(shù)據(jù)包數(shù),反映了網(wǎng)絡(luò)傳輸?shù)目煽啃裕瑪?shù)值越大可靠性越高。

2) 平均端到端延時：目的節(jié)點收到數(shù)據(jù)包的時間與源節(jié)點發(fā)送數(shù)據(jù)包的時間差,值越小網(wǎng)絡(luò)反應(yīng)越快，網(wǎng)絡(luò)質(zhì)量越令人滿意。

3) 歸一化路由開銷：單位數(shù)據(jù)包個數(shù)所引起的額外路由包個數(shù)，反映了路由協(xié)議的運(yùn)行效率。

4 仿真結(jié)果分析

仿真試驗中網(wǎng)絡(luò)節(jié)點運(yùn)動速率分別為0 m/s，5 m/s，10 m/s，15 m/s，20 m/s，主要測試SWMR，AOMDV，AODV 3種協(xié)議在不同網(wǎng)絡(luò)移動性下的網(wǎng)絡(luò)性能差異。從圖2中可以看出，隨著網(wǎng)絡(luò)拓?fù)渥兓涌?，路由失效概率增大?種協(xié)議的發(fā)送成功率降低。由于SWMR協(xié)議構(gòu)建了節(jié)點不相交的主路由和纏繞其間的備份路由，降低了路由失效次數(shù)，在部分路徑失效后能夠通過備份路由快速修復(fù)，因此其發(fā)送成功率高于AOMDV和AODV。

圖2 發(fā)送成功率對比Fig.2 Packet delivery ratio vs velocity

圖3顯示隨著節(jié)點移動速率增加，3種協(xié)議的平均端到端時延增加，但SWMR協(xié)議的時延增加幅度最小。當(dāng)節(jié)點移動速率較小時，AOMDV和AODV協(xié)議延時比SWMR協(xié)議小，這是由于中間節(jié)點不回復(fù)路由和目的節(jié)點多徑選擇而延遲回復(fù)RREP所導(dǎo)致。當(dāng)節(jié)點移動速率較大時，SWMR協(xié)議延時比AOMDV,AODV協(xié)議低。究其原因是，由不相交多徑路由和備份路由構(gòu)建的穩(wěn)定傳輸鏈路減少了路由中斷次數(shù)，有效地減少因路由失效而引起的數(shù)據(jù)包緩存數(shù)量，降低了排隊時延。

圖3 平均端到端延時對比Fig.3 Average delay vs velocity

圖4顯示當(dāng)節(jié)點低速率移動時，3種協(xié)議的路由開銷較小，但隨著節(jié)點移動速率增加，網(wǎng)絡(luò)拓?fù)洳环€(wěn)定，路由開銷增大。

圖4 歸一化路由開銷對比Fig.4 Normalized routing load vs velocity

SWMR協(xié)議中，減少了由中間節(jié)點發(fā)送的RREP數(shù)量，同時增加了用于建立備份路由的RREP_AP。因而在移動速度較低時，3種協(xié)議路由開銷大致相同。而隨著速度增加，SWMR協(xié)議路由開銷遠(yuǎn)小于AOMDV,AODV協(xié)議。這是由于構(gòu)建的穩(wěn)定路由降低了由于某一段鏈路中斷而導(dǎo)致新路由發(fā)現(xiàn)啟動次數(shù)，從而減少了路由開銷。

5 結(jié)束語

本文提出的穩(wěn)定纏繞多徑路由SWMR協(xié)議，在路由發(fā)現(xiàn)過程中構(gòu)建2條節(jié)點不相交主路由，并利用無線信道廣播特性以較小的開銷建立若干纏繞在主路由邊的備份路徑，形成了較為穩(wěn)定的路由網(wǎng)絡(luò)，使其能較好地適應(yīng)戰(zhàn)術(shù)移動網(wǎng)絡(luò)應(yīng)用場景。仿真結(jié)果表明，相比AOMDV和AODV協(xié)議，在節(jié)點移動速度較快時，SWMR協(xié)議具有更高的發(fā)送成功率，更低的端到端平均延時和路由開銷。SWMR協(xié)議的提出為設(shè)計和優(yōu)化多徑路由協(xié)議提供了一種新的思路，在流媒體網(wǎng)絡(luò)方面擁有較好的應(yīng)用前景。

[1] RADI M,DEZFOULI B,BAKAR K.A,et al.Multipath routing in wireless sensor networks:survey and research challenges [J].Sensors,2012,12(1):650-685.

[2] 董萍,錢煥延,魏曉飛,等.Ad Hoc網(wǎng)絡(luò)基于平面區(qū)域劃分的多徑路由協(xié)議[J].計算機(jī)應(yīng)用研究,2014,31(5):1554-1557.

[3] 王頂,王珊珊,席效禹.基于路由長度的多徑路由協(xié)議[J].計算機(jī)工程，2014,40(9):82-86.

[4] 謝忠明,何華冰,李云飛,等.一種基于鏈路狀態(tài)感知的Zigbee多徑路由算法[J].微電子學(xué)與計算機(jī)，2015,32(9):65-69.

[5] 袁博.Ad Hoc網(wǎng)絡(luò)多路路由研究[D].杭州:浙江大學(xué),2005.

[6] LEE Y O,NARASIMHA A L.Constructing disjoint paths for failure recovery and multipath routing [J].Computer Networks,2012,56(2):719-730.

[7] 潘勝利,楊析儒,張志勇,等.單源多徑路由網(wǎng)絡(luò)擁塞鏈路識別[J].電子與信息學(xué)報,2015,37(9):2232-2237.

[8] 趙科莉,李錚,李皓,等.基于OPNET的多數(shù)據(jù)鏈組網(wǎng)設(shè)計與仿真[J].電光與控制,2014,21(9):61-64.

[9] PERKINS C E,ROYER E M.Ad-Hoc on-demand distance vector routing(AODV)[R].California:University of California,2013.

[10] JOHNSON D,HU Y,MALTZ D.RFC4728 on the Dyna-mic Source Routing protocol (DSR) for mobile Ad Hoc networks for IPv4[EB/OL].[2007-02-13].http://www.ietf.org/rfc/rfc4728.txt.

StableMulti-pathRoutingProtocolinTacticalAdHocNetwork

WANG Shuo, ZHOU Yang, CHEN Ying-wei, ZHOU Tao, YAN Xi-jun

(Beijing Institute of Astronautics System Engineering,Beijing 100076,China)

Nodes moving with high speed can bring rapid topology change in tactical communication network,which may invoke new route discovery processes and lead to network performance degradation.To alleviate this problem,a novel Stable Wrapped Multi-path Routing (SWMR) protocol is proposed,which uses source routing approach to establish node-disjoint primary routes,and builds up several backup paths among each primary route synchronously by utilizing overheard route reply packets.By constructing such multi-path routes,the protocol not only provides higher network stability,but also reduces route discovery latency and routing overheads.Simulation results show that:compared with AOMDV and AODV,SWMR has a better routing performance in packet delivery ratio,average delay and normalized load metrics when the network topology changes rapidly.

tactical communication network; Ad Hoc; wrapped path; multi-path routing

TP393

A

1671-637X(2017)03-0085-04

2016-09-14

2016-10-19

王 碩(1985 —),男，湖北荊州人，碩士，工程師，研究方向為戰(zhàn)術(shù)通信網(wǎng)絡(luò)技術(shù)。