一種適用于軍用無(wú)線自組網(wǎng)的可靠多徑路由協(xié)議

夏 輝，王辛果，杜曉明

(1.海軍裝備研究院，上海 200436；2.中國(guó)西南電子技術(shù)研究所，成都 610036；3.中國(guó)北方工業(yè)公司，北京 100053)

1 引 言

由于作戰(zhàn)應(yīng)用的特殊需求，軍用無(wú)線自組網(wǎng)對(duì)通信路徑的可靠性和穩(wěn)定性要求極高。如何在動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)渲薪M足QoS(Quality of Service)需求的通信路徑是無(wú)線自組網(wǎng)研究的關(guān)鍵問(wèn)題之一[1]。多徑路由協(xié)議在源和目的節(jié)點(diǎn)之間維護(hù)多條路徑，與單徑路由相比具有更高的可靠性和穩(wěn)定性[2]。

與民用無(wú)線自組網(wǎng)相比，軍用無(wú)線自組網(wǎng)還具有一些特性需要在設(shè)計(jì)路由協(xié)議時(shí)予以充分考慮：無(wú)線通信環(huán)境更加惡劣，經(jīng)常會(huì)受到外部的嚴(yán)重干擾；節(jié)點(diǎn)移動(dòng)的群體性更強(qiáng)，屬于同一編隊(duì)的節(jié)點(diǎn)運(yùn)動(dòng)軌跡相關(guān)性較高；節(jié)點(diǎn)移動(dòng)速率高，斷鏈可能會(huì)頻繁發(fā)生；節(jié)點(diǎn)通常具有地理定位模塊，地理位置信息易于獲取。

在多徑路由中，除了優(yōu)化每條路徑的路徑指標(biāo)外，還應(yīng)讓連接相同源和目的節(jié)點(diǎn)的路徑之間保持低相關(guān)性，以提升路由可靠性。本文首先分析了路徑相關(guān)性與網(wǎng)絡(luò)拓?fù)涞年P(guān)系，定義了一種新的基于地理位置的路徑相關(guān)因子來(lái)進(jìn)一步量化路徑之間的相關(guān)程度；然后，提出了一種最小化路徑相關(guān)性的多徑路由協(xié)議，該協(xié)議選擇多條既能滿足給定的單路徑指標(biāo)又具有最低相關(guān)性的路徑，從而最大程度保證多徑路由的可靠性和穩(wěn)定性。

2 選路指標(biāo)

2.1 路徑指標(biāo)

路徑指標(biāo)主要包括可靠性和穩(wěn)定性，路徑由多跳鏈路組成，因而路徑指標(biāo)取決于鏈路指標(biāo)。

2.1.1 可靠性

鏈路質(zhì)量指標(biāo)[3](Link Quality Indication,LQI)為鏈路的一次性傳輸?shù)某晒β剩撝档挠?jì)算方法如下：

(1)

其中，Nrx是接收方正確接收的消息數(shù)量；Ntx是發(fā)送方發(fā)送的消息數(shù)量。每個(gè)節(jié)點(diǎn)通過(guò)周期性廣播的HELLO消息向相鄰節(jié)點(diǎn)反饋本節(jié)點(diǎn)正確接收的消息數(shù)量。

路徑質(zhì)量指標(biāo)(Path Quality Indication,PQI)則為路徑上所有鏈路的一次性傳輸成功率的乘積：

PQI=∏LQIk

(2)

將路徑質(zhì)量指標(biāo)PQI作為可靠性指標(biāo)。

2.1.2 穩(wěn)定性

如圖1所示，在評(píng)估從節(jié)點(diǎn)i到節(jié)點(diǎn)j的鏈路失效時(shí)間時(shí)，建立以節(jié)點(diǎn)i的位置為原點(diǎn)的三維垂直坐標(biāo)系。鏈路失效時(shí)間(Link Expiration Time,LET)定義為按照節(jié)點(diǎn)間目前的相對(duì)運(yùn)動(dòng)速度，節(jié)點(diǎn)j離開i的通信半徑范圍R所需的時(shí)間。

圖1 鏈路失效時(shí)間估計(jì)模型Fig.1 LET estimation model

通過(guò)交換位置和速度信息，可以計(jì)算得到當(dāng)前時(shí)刻節(jié)點(diǎn)i和j之間的距離d以及它們之間的相對(duì)運(yùn)動(dòng)速度向量v與向量ij的夾角θ。根據(jù)余弦定理，可以得到

(3)

當(dāng)θ小于90°時(shí)，平臺(tái)i與j將相向運(yùn)動(dòng)，鏈路失效時(shí)間相對(duì)較長(zhǎng)；否則，平臺(tái)i與j將背向運(yùn)動(dòng)，鏈路失效時(shí)間相對(duì)較短。

路徑失效時(shí)間(Path Expiration Time,PET)則定義為路徑上所有鏈路的失效時(shí)間的最小值：

PET=min {LETk}

(4)

將路徑失效時(shí)間PET作為穩(wěn)定性指標(biāo)。

2.2 路徑相關(guān)性

路徑相關(guān)性是指兩條路徑之間在可靠性和穩(wěn)定性方面的相關(guān)程度，路由協(xié)議選擇多條路徑時(shí)應(yīng)選擇路徑兩兩之間的相關(guān)性盡可能低的路徑集[4]。如圖2所示，按照是否具有相同的轉(zhuǎn)發(fā)節(jié)點(diǎn)，路徑的關(guān)系可以分為相交和不相交，前者的相關(guān)性顯然高于后者。

圖2 路徑相關(guān)性Fig.2 Path correlation

對(duì)于相交的兩條路徑，根據(jù)具有相同的轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量化它們的相關(guān)性，路徑具有的相同轉(zhuǎn)發(fā)節(jié)點(diǎn)越多，路徑的相關(guān)性就越高；對(duì)于不相交的兩條路徑，根據(jù)路徑之間的空間距離量化它們的相關(guān)性。在實(shí)際網(wǎng)絡(luò)中，距離越近的多跳鏈路越有可能因受到來(lái)自相同干擾源的干擾而造成多條路徑同時(shí)失效，距離越近的節(jié)點(diǎn)越有可能屬于同一編隊(duì)而同時(shí)離開目前所在區(qū)域造成多跳路徑同時(shí)斷開。因此，距離越近的路徑之間的相關(guān)性越高，反之亦然。

假設(shè)路徑Pi上的節(jié)點(diǎn)依次為s,r1,r2,…,rm,d。其中，s為源節(jié)點(diǎn)，d為目的節(jié)點(diǎn)，轉(zhuǎn)發(fā)節(jié)點(diǎn)集Ri為。根據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)的地理位置，采用剪枝搜索算法計(jì)算得到Ri對(duì)應(yīng)的凸包集Qi=，顯然Qi?Ri。計(jì)算凸包集Qi的質(zhì)心ci的地理位置。同理，可計(jì)算路徑Pj的質(zhì)心位置。進(jìn)一步，可計(jì)算不相交路徑Pi和Pj的質(zhì)心距得到相關(guān)因子PCFi,j。

如圖3所示，路徑i和j的相關(guān)因子PCFi,j的正式定義如下：

PCFi,j=

(5)

其中，H為網(wǎng)絡(luò)中最大節(jié)點(diǎn)間距離。路徑相交時(shí)，相關(guān)因子等于兩條路徑具有的相同轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)量，PCF≥1；路徑不相交時(shí)，相關(guān)因子取決于兩條路徑的質(zhì)心距和H的比值，0≤PCF<1 。

圖3 路徑相關(guān)因子Fig.3 Path correlation factor

3 路由協(xié)議

3.1 選路算法

多徑路由算法選出滿足給定的可靠性和穩(wěn)定性要求且任兩條路徑的相關(guān)性盡可能低的L(L≥2)條路徑，該路徑集合記為P。選路算法可以建模為下面的優(yōu)化問(wèn)題：

(6)

s.t. |P|=L
PQIi≥γ,PQIj≥γ,?i,j∈P
PETi≥τ,PETj≥τ,?i,j∈P

其中，γ為最低鏈路可靠性，τ為最小路徑持續(xù)時(shí)間。優(yōu)化目標(biāo)為最小化L條路徑的互相關(guān)因子的最大值。第一個(gè)約束條件是必須選出L條路徑，第二和第三個(gè)約束條件分別是選擇的路徑的可靠性和穩(wěn)定性指標(biāo)必須滿足要求。

假設(shè)滿足可靠性和穩(wěn)定性要求的路徑共有N條，路徑集合為P，路徑的轉(zhuǎn)發(fā)節(jié)點(diǎn)集為。假設(shè)N≥L，否則，表示算法無(wú)法選出L條符合條件的路徑，則將L減1作為算法輸入。將P中所有路徑的轉(zhuǎn)發(fā)節(jié)點(diǎn)集的交集R1∩R2…∩RN記為C。問(wèn)題(6)的求解過(guò)程如下：

步驟1：進(jìn)行如下操作，直至C=?或|P|=L:

(2)將路徑s從路徑集P中刪除，重新計(jì)算C;

(3)如果C=?，則進(jìn)行步驟2)，如果|P|=L，則算法結(jié)束;

步驟2：經(jīng)過(guò)步驟1后，路徑集P中僅剩下不相交路徑，進(jìn)行如下操作，直至|P|=L，算法結(jié)束:

(1)找到路徑集P中PCF最大的路徑對(duì)；

(2)如果maxPCFi,k∈{P-{i,j}}>maxPCFj,k∈{P-{i,j}}，將路徑i從P中刪除；

(3)否則，將路徑j(luò)從P中刪除。

3.2 協(xié)議細(xì)節(jié)

RMRP協(xié)議采用先應(yīng)式的路由策略，每個(gè)節(jié)點(diǎn)通過(guò)與其他鄰居節(jié)點(diǎn)不斷地交換鏈路狀態(tài)消息，獲取全網(wǎng)的拓?fù)湫畔?，并維護(hù)本節(jié)點(diǎn)到網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)的L條最優(yōu)路徑。

3.2.1 鏈路建立

網(wǎng)絡(luò)中所有節(jié)點(diǎn)周期性地廣播HELLO消息，獲取與本節(jié)點(diǎn)鄰接的鏈路狀態(tài)。該消息中包含本節(jié)點(diǎn)地址、本節(jié)點(diǎn)的地理位置和運(yùn)動(dòng)速度、本節(jié)點(diǎn)在統(tǒng)計(jì)窗口內(nèi)收到的來(lái)自鄰居節(jié)點(diǎn)的HELLO消息數(shù)列表等信息。收到HELLO消息后，計(jì)算鄰居節(jié)點(diǎn)到本節(jié)點(diǎn)的鏈路傳輸質(zhì)量和鏈路失效時(shí)間。HELLO消息的傳播距離為一跳，僅用于感知鄰接鏈路狀態(tài)和快速建立鏈路。

3.2.2 拓?fù)涓兄?/p>

網(wǎng)絡(luò)中所有節(jié)點(diǎn)周期性地廣播TC(Topology Control)消息共享鄰接鏈路狀態(tài)信息，從而獲取全網(wǎng)的拓?fù)湫畔ⅰC消息包含鏈路的發(fā)送地址和接收地址、時(shí)間戳、鏈路質(zhì)量指標(biāo)、鏈路持續(xù)時(shí)間。節(jié)點(diǎn)在全網(wǎng)拓?fù)浔碇芯S護(hù)所有感知到的鏈路狀態(tài)，并在拓?fù)浔戆l(fā)生變化時(shí)調(diào)用選路算法。

RMRP協(xié)議采用與OLSR(Optimized Link State Routing)[5]協(xié)議中多點(diǎn)中繼類似的拓?fù)湫畔V播機(jī)制，以減少TC消息的廣播次數(shù)，降低控制開銷。每個(gè)節(jié)點(diǎn)從其一跳鄰居節(jié)點(diǎn)集中挑選一部分節(jié)點(diǎn)作為MPR(Multi-Point Relay)節(jié)點(diǎn)。MPR節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合的并集全包含源節(jié)點(diǎn)的兩跳鄰居節(jié)點(diǎn)集，保證可通過(guò)MPR節(jié)點(diǎn)到達(dá)所有兩條鄰居節(jié)點(diǎn)。節(jié)點(diǎn)廣播TC消息后，只有被選為MPR的鄰居節(jié)點(diǎn)才負(fù)責(zé)轉(zhuǎn)發(fā)TC消息。

3.2.3 多徑路由

多徑選路算法計(jì)算L條連接源節(jié)點(diǎn)和目的節(jié)點(diǎn)的相關(guān)性低的路徑。為確保該性質(zhì)，采用源路由方式，即源節(jié)點(diǎn)將路徑上所有節(jié)點(diǎn)的地址包含在消息中，中間節(jié)點(diǎn)轉(zhuǎn)發(fā)消息時(shí)直接從消息的頭部中查找下跳節(jié)點(diǎn)。為保持負(fù)載均衡和網(wǎng)絡(luò)公平性，源節(jié)點(diǎn)在每次發(fā)送消息時(shí)從L條路徑中隨機(jī)選擇之一作為傳輸路徑。

4 仿真實(shí)驗(yàn)及結(jié)果分析

采用OPNET網(wǎng)絡(luò)仿真平臺(tái)[6]比較RMRP、DT-MAODV[7]在投送成功率和端到端時(shí)延方面的性能。DT-MAODV是為Ad Hoc網(wǎng)絡(luò)設(shè)計(jì)的多徑路由協(xié)議，該協(xié)議通過(guò)選擇不相交的多條路徑來(lái)提升傳輸可靠性。不失一般性，仿真場(chǎng)景為邊長(zhǎng)為800 km的正方形區(qū)域，節(jié)點(diǎn)總數(shù)為200，節(jié)點(diǎn)通信半徑設(shè)為100 km。節(jié)點(diǎn)采用參考點(diǎn)組移動(dòng)模型[8]作隨機(jī)運(yùn)動(dòng)。在該模型中，屬于同一個(gè)組的在指定的參考點(diǎn)區(qū)域內(nèi)隨機(jī)運(yùn)動(dòng)。參考點(diǎn)的運(yùn)動(dòng)采用RWP(Random Way Point)模型，最大運(yùn)動(dòng)速率為680 m/s。所有仿真結(jié)果均為10次仿真實(shí)驗(yàn)的統(tǒng)計(jì)平均值。協(xié)議配置參數(shù)為L(zhǎng)=3，γ=0.9，τ=20 s。應(yīng)用層采用CBR(Constant Bit Rate)流量模型，源節(jié)點(diǎn)產(chǎn)生消息的間隔為0.1 s，每條消息的大小為512 B，消息的目的接收節(jié)點(diǎn)為隨機(jī)產(chǎn)生。

投送成功率定義為目的節(jié)點(diǎn)收到消息數(shù)與源節(jié)點(diǎn)發(fā)送消息數(shù)的比值，該指標(biāo)是路由協(xié)議可靠性的重要指標(biāo)。如圖4所示，兩種協(xié)議的投送成功率均隨鏈路干擾比例上升或節(jié)點(diǎn)運(yùn)動(dòng)速率增加而下降。由于RMRP協(xié)議能夠選擇相關(guān)性更低的多條路徑，端到端傳輸?shù)目煽啃愿摺Ｔ谙嗤W(wǎng)絡(luò)場(chǎng)景配置下，RMRP的投送成功率比DT-MAODV更高，鏈路干擾比例越高或者節(jié)點(diǎn)的運(yùn)動(dòng)速率越大，RMRP的優(yōu)勢(shì)越明顯。當(dāng)鏈路干擾比例為0.4時(shí)，RMRP的投送成功率比DT-MAODV 高46.7%；當(dāng)節(jié)點(diǎn)的運(yùn)動(dòng)速率為680 m/s時(shí)，RMRP的投送成功率比DT-MAODV高23.7%。

圖4 投送成功率Fig.4 Delivery ratio

在傳輸層增加可靠傳輸機(jī)制，并考察消息的端到端時(shí)延。該時(shí)延定義為從源節(jié)點(diǎn)應(yīng)用層開始產(chǎn)生消息到目的節(jié)點(diǎn)應(yīng)用層收到消息的總時(shí)延。如圖5所示，鏈路干擾比例越高或運(yùn)動(dòng)速率越大，所有消息的平均端到端時(shí)延越高。在相同網(wǎng)絡(luò)場(chǎng)景配置下，RMRP的端到端時(shí)延比DT-MAODV更低，鏈路干擾比例越高或者節(jié)點(diǎn)的運(yùn)動(dòng)速率越大，RMRP的優(yōu)勢(shì)越明顯。當(dāng)鏈路干擾比例為0.4時(shí)，RMRP的端到端時(shí)延比DT-MAODV 低60.1%；當(dāng)節(jié)點(diǎn)的運(yùn)動(dòng)速率為680 m/s時(shí)，RMRP的端到端時(shí)延比DT-MAODV低37.1%。

圖5 端到端時(shí)延Fig.5 End-to-end delay

5 總 結(jié)

本文針對(duì)軍用無(wú)線自組網(wǎng)的通信環(huán)境和平臺(tái)移動(dòng)特性設(shè)計(jì)了一種可靠多徑路由協(xié)議，即RMRP協(xié)議。首先，定義了路徑的可靠性和穩(wěn)定性指標(biāo)以及路徑之間的相關(guān)因子；接著，提出了一種保證可靠性和穩(wěn)定性要求且相關(guān)性盡可能低的多徑選擇算法。仿真結(jié)果表明，RMRP比DT-MAODV具有更高的投送成功率和更低的端到端時(shí)延。如何利用RMRP提供的L條路徑進(jìn)一步提升投送成功率是值得繼續(xù)深入研究的問(wèn)題。

[1] Zhang N,Anpalagan A.Comparative Review of qos-aware on-demand routing in ad hoc wireless networks [J].Wireless Sensor Network,2010(2):274-284.

[2] Mareo A,Gareia-Luna-Aeeves J J.Improving route discovery in on-demand routing protocols using two-hop connected dominating sets [J].Ad Hoc Networks,2006,4(4):509-531.

[3] Wang Y,Liu J.A backup multipath routing protocol for ad hoc networks with dynamic topology[C] / / Proceedings of 2012 IEEE ICSEM Conference.Guiyang:IEEE,2012:237-241.

[4] Biswas S,Morris R.ExOR:Opportunistic multi-hop routing for wireless networks[C] / / Proceedings of 2005 ACM SIGCOMM Conference.Philadelphia,PA,USA:IEEE,2005:133-143.

[5] RFC 3626,Optimized Link State Routing Protocol(OLSR) [S].

[6] 龍華.OPNET Modeler與計(jì)算機(jī)網(wǎng)絡(luò)仿真[M].西安:西安電子科技大學(xué)出版社,2006.

LONG Hua.OPNET Modeler and Computer Network Simulation[M].Xi′an:Xidian University Press,2006.(in Chinese)

[7] Sahu R K,Saha R,Chaudhari N S.Fault Tolerant Reliable Multipath Routing Protocol for Ad hoc Network[C] / / Proceedings of 2012 IEEE CICN Conference.Mathura,India:IEEE,2012:117-121.

[8] 徐鑫鑫.無(wú)線移動(dòng)Ad hoc網(wǎng)絡(luò)移動(dòng)模型研究[D].長(zhǎng)沙：國(guó)防科技大學(xué),2008.

XU Xin-xin.Research of Mobility Model in Wireless Mobile Ad Hoc Network[D].Changsha:National University of Defense Technology,2008.(in Chinese)