無人機自組網(wǎng)按需尋路的可靠OLSR協(xié)議

胡 春，任 智，崔忠林

1(重慶郵電大學 通信與信息工程學院，重慶 400065) 2(電子科技集團公司第三十八研究所，合肥 230000)

1 引 言

無人機自組網(wǎng) (UAV Ad-Hoc Network，UANET)是移動自組網(wǎng)的一個特例[1]，無人機自組網(wǎng)具有功能多樣性、靈活性、易于安裝部署和相對較小的運營費用等優(yōu)勢，在軍事和民用領域得到廣泛應用[2-4].應用在無人機自組網(wǎng)中的OLSR協(xié)議是Ad Hoc網(wǎng)絡中廣泛使用的路由協(xié)議的一種[5-7]，OLSR協(xié)議是先驗式路由的一種，時延較小，適合于節(jié)點數(shù)較多，拓撲變化不太劇烈的場景[8].AODV路由協(xié)議是按需路由協(xié)議的一種，在路由發(fā)生錯誤，超時的情況下，會啟動路由維護機制，保證通信的正常[9,10].針對無人機自組網(wǎng)的應用場景，在OLSR路由協(xié)議中引入按需路由機制，能夠更好的結(jié)合兩類協(xié)議的優(yōu)點.目前基于按需路由OLSR協(xié)議已經(jīng)有了一定的研究.文獻[10]提出基于下一跳機制的OLSR協(xié)議，提高了OLSR協(xié)議對動態(tài)變化網(wǎng)絡結(jié)構(gòu)的適應能力以及局部重載時的自動調(diào)節(jié)能力.文獻[12]提出了基于集合運算的MPR集選擇算法，找到了一種最新、最有效的MPR選擇算法，但是該算法比經(jīng)典OLSR協(xié)議增加了時延.文獻[13]利用OLSR協(xié)議中Hello消息報文，獲取鄰居節(jié)點的健康指數(shù)，建立路由修復機制.文獻[15]提出了將時延容忍網(wǎng)絡和自組織網(wǎng)絡結(jié)合，把時延容忍網(wǎng)絡中的機會路由思想引入OLSR協(xié)議，在數(shù)據(jù)包沒有下一條路由時，不是直接丟棄，而是借鑒機會路由思想，將數(shù)據(jù)包發(fā)給連接度高的一跳鄰居，提高發(fā)包成功率.

按需路由和OLSR協(xié)議的結(jié)合，提高OLSR協(xié)議在各種應用場景中的性能[16,17].本文根據(jù)文獻[15]的思路，針對該協(xié)議中機會路由無法保證低時延的缺點，在仔細研究OLSR協(xié)議和AODV路由協(xié)議的基礎上，將AODV的鏈路維護機制和OLSR協(xié)議相結(jié)合，提出了一種基于按需尋路的可靠OLSR協(xié)議(Reliable OLSR protocol for on-demand pathfinding of drone ad hoc networks，ODR-OLSR).

2 無人機自組網(wǎng)OLSR協(xié)議的問題

無人機自組網(wǎng)場景中，由于無人機移動速度快和無線信道的特點，傳統(tǒng)的OLSR協(xié)議存在如下問題：

2.1 無人機移動速度快造成鏈路中斷

由于無人機移動速度快，網(wǎng)絡拓撲變化快，造成多跳鏈路通信失敗.如圖 1所示，1號節(jié)點和4號節(jié)點進行通信，由于3號無人機的快速移動，與2號和4號的通信距離超過通信范圍，導致通信鏈路中斷，通信失敗.在無人機自組網(wǎng)應用環(huán)境中，通信中斷可能性，隨著通信跳數(shù)增加.

圖1 鏈路模型Fig.1 Link model

2.2 新入網(wǎng)節(jié)點無發(fā)及時與全網(wǎng)通信

由于無人機的高動態(tài)性，可能造成無人機頻繁脫網(wǎng)和入網(wǎng).OLSR協(xié)議主要是靠定期廣播HELLO消息和TC消息，維持全網(wǎng)路由信息.新入網(wǎng)無人機無發(fā)接收足夠多的TC消息，因此無法得到全網(wǎng)路由，導致通信失敗，嚴重影響網(wǎng)絡的通信需求.

3 改進協(xié)議ODR-OLSR介紹

針對無人機自組網(wǎng)中的問題，ODR-OLSR協(xié)議提出了以下改進：

3.1 機制1：基于TC消息尋路機制

針對多跳鏈路中斷問題，提出當節(jié)點發(fā)現(xiàn)鏈路中斷時，借鑒AODV協(xié)議中的RREQ路由維護機制，節(jié)點主動發(fā)送基于TC消息的路由維護消息.

由于OLSR協(xié)議會定期全網(wǎng)泛洪TC消息，但是沒有尋路功能，AODV協(xié)議利用全網(wǎng)泛洪的RREQ消息進行尋路，因此當節(jié)點發(fā)現(xiàn)鏈路中斷，利用TC消息攜帶目的地址，進行尋路.具體步驟如下：

1)鏈路中斷的判斷：多跳鏈路進行通行時，中間節(jié)點執(zhí)行鏈路監(jiān)控的功能.MAC層傳遞數(shù)據(jù)幀時，存在重傳機制，當重傳次數(shù)達到上限，即判定鏈路中斷.

2)鏈路維護機制啟動：發(fā)生鏈路中斷的節(jié)點啟動鏈路維護，立刻向全網(wǎng)廣播TC消息，并利用TC消息中的保留字段Reserved攜帶目的地址，進行尋路，并修改消息類型為TC尋址消息.每個節(jié)點在一個TC周期內(nèi)，只能進行一次TC尋址，避免反復向全網(wǎng)泛洪TC消息，減小控制開銷.

3)TC尋址消息的處理：其他節(jié)點在接收到TC尋址消息后，除了進行正常的TC消息處理程序，還需將保留字段Reserved的值與節(jié)點自身地址進行比較，如果兩者相等，立刻啟動TC尋址回復機制，向全網(wǎng)廣播TC消息，并修改消息類型為TC回復消息.

4)生成臨時路由：啟動鏈路維護機制的節(jié)點可能會收到多個轉(zhuǎn)發(fā)來的TC回復消息，節(jié)點在接收第一個TC回復消息時，將轉(zhuǎn)發(fā)節(jié)點定義為通往目的節(jié)點的下一跳路由.

3.2 機制2：基于HELLO消息尋址機制

針對新入網(wǎng)節(jié)點由于缺乏全網(wǎng)的路由信息，導致無發(fā)及時通信問題，提出基于HELLO消息尋址機制，通過HELLO消息攜帶目的地址，向周圍一跳鄰居進行尋址，形成一條臨時路由，縮短路由獲取時間.其具體步驟如下：

1)HELLO尋址消息生成：當節(jié)點網(wǎng)絡層接收到上層數(shù)據(jù)流時，發(fā)現(xiàn)目的地址路由缺失，啟動HELLO尋址機制，立刻發(fā)送HELLO消息，利用HELLO消息保留字段Reserved攜帶目的地址，同時修改消息類型為HELLO尋址消息.

2)HEELLO尋址消息的處理：周圍一跳鄰居接收到HELLO尋址消息后，除了進行正常HELLO消息處理程序外，還查詢Reserved字段的值，如果存在到達目的節(jié)點的路由，啟動HELLO回復機制，立即發(fā)送HELLO消息，利用HELLO消息保留字段Reserved攜帶目的地址，并將消息類型改為HELLO回復消息.

3)生成臨時路由：發(fā)起HELLO尋址機制的節(jié)點可能會收到多個HELLO回復消息，節(jié)點接收第一個HELLO回復消息時，將發(fā)送節(jié)點定義為通往目的地址的下一跳路由.

3.3 控制消息的動態(tài)發(fā)送

原始的OLSR協(xié)議控制消息是定期發(fā)送，由于機制1和機制2會利用HELLO消息和TC消息進行臨時尋路，如果不調(diào)整控制消息的發(fā)送時間會導致控制開銷增加.因此引入控制消息的動態(tài)發(fā)送.如圖2所示，正?？刂葡橹芷谛园l(fā)送，周期為T，在[t0，t0+3T]時間段發(fā)送了4次控制消息.

圖2 控制消息發(fā)送時刻表Fig.2 Control message sending schedule

當節(jié)點發(fā)送尋路控制消息，采取動態(tài)發(fā)送機制，如圖3所示，t1時刻發(fā)送了尋址控制消息，原來t0+T時刻發(fā)送的控制消息取消，則在[t0，t0+3T]時間段發(fā)送了4次控制消息，和固定發(fā)送機制數(shù)量一樣，保證了控制開銷總量不變.

圖3 控制消息動態(tài)發(fā)送時刻表Fig.3 Control message dynamic schedule

4 理論性能分析

按需路由機制的引入是在沒有增加控制開銷的前提下，使OLSR協(xié)議在發(fā)包成功率和吞吐量得到明顯改善，具體分析如下：

4.1 控制開銷分析

改進前的HELLO消息和TC消息都是定期發(fā)送的，改進后采用動態(tài)發(fā)送機制，保證控制開銷和改進前保持一致.

4.2 發(fā)包成功率分析

引理1.一跳鏈路節(jié)點移動速度越快，鏈路中斷可能性越高.

定義：S為發(fā)包成功率，p為單跳鏈路中斷概率，L為鏈路連通概率，V為節(jié)點速度，n為通信跳數(shù).

由引理1可知：

p∝V

(1)

有單跳鏈路和多跳鏈路連通性關系：

(2)

發(fā)包成功率S和鏈路連通概率L成正比，則有：

S∝L

(3)

由公式(1)-公式(3)可知：發(fā)包成功率S與鏈路跳數(shù)n和節(jié)點移動速度V相關，當節(jié)點移動速度越快，通信跳數(shù)越長，多跳鏈路越容易中斷，發(fā)包成功率越低.

機制一在鏈路發(fā)生中斷時，及時啟動鏈路維護機制，發(fā)送TC消息進行尋路，維護了多跳鏈路的連通，并且該機制性能隨著鏈路跳數(shù)和節(jié)點速度增加而增加，因此ODR-OLSR協(xié)議在發(fā)包成功率上優(yōu)于OLSR協(xié)議，則有SODR-OLSR>SOLSR.

4.3 吞吐量分析

吞吐量定義為：成功接收數(shù)據(jù)量/總時間，則有

(4)

式(4)中：H為吞吐量，Mrcv為接收數(shù)據(jù)總量，Msend為發(fā)送數(shù)據(jù)總量，T為總時間，S為發(fā)包成功率.由于ODR-OLSR協(xié)議發(fā)包成功率更高,在發(fā)送數(shù)據(jù)量和時間相等時，有公式(5)：

HODR-OLSR>HOLSR

(5)

4.4 時延分析

由于節(jié)點在缺失路由或者鏈路中斷時，對于上層的數(shù)據(jù)包通常采取的先保存在緩沖區(qū)，通過公式(6)可知，發(fā)包時延由傳輸時延和緩沖區(qū)時延構(gòu)成.由于ODR-OLSR協(xié)議增加路由維護機制和路由獲取的途徑，減小了緩沖區(qū)時延，減小了數(shù)據(jù)包總時延.

Dall=Dtransfer+Dbuffer

(6)

其中Dall為總時延，Dtransfer為傳輸時延，Dbuffer為緩沖區(qū)時延.

5 仿真驗證

選取OLSR協(xié)議，ODR-OLSR協(xié)議和文獻[15]中的DTN-OLSR協(xié)議作為比較對象，通過仿真實驗分析它們在發(fā)包成功率，時延，控制開銷，吞吐量等指標上的區(qū)別.

5.1 仿真參數(shù)設置

使用Windows XP平臺上的OPNET仿真軟件,設置了5個仿真場景，節(jié)點數(shù)分別為20，40，60，80，100個，節(jié)點在1500m×1500m的矩形區(qū)域均勻分布，節(jié)點最大移動速度為10m/s,最大通信距離為200m，節(jié)點通信最大跳數(shù)為15跳.仿真參數(shù)設置如表1所示，MAC層使用IEEE 802.11標準.每個場景實驗做5次，取平均值.

表1 仿真參數(shù)設置Table 1 Simulation parameter setting

5.2 仿真結(jié)果分析

5.2.1 控制開銷分析

圖4表明，ODR-OLSR協(xié)議在控制開銷方面和OLSR協(xié)議基本相等.原因在于：基于HELLO消息尋址機制和基于TC消息尋址機制沒有引入新的字段攜帶目的地址，保證了控制消息報文大小和OLSR協(xié)議相等.通過控制消息的動態(tài)發(fā)送機制能有效保證在總時間內(nèi)發(fā)送控制報文次數(shù)和OLSR協(xié)議相等，因此ODR-OLSR協(xié)議在不帶來額外開銷的同時，提高其他指標的性能.

圖4 控制開銷比較Fig.4 Control overhead comparison

5.2.2 端到端時延分析

圖5表明，ODR-OLSR協(xié)議在端到端時延方面較OLSR和DTN-OLSR協(xié)議有著明顯改善.其中可以發(fā)現(xiàn)DTN-OLSR協(xié)議在時延性能上比較差，原因是DTN-OLSR協(xié)議引入機會路由機制，在無人機自組網(wǎng)環(huán)境下的通信業(yè)務一般都是低時延業(yè)務，通過增大時延來提高網(wǎng)絡的性能可能需要修正.ODR-OLSR協(xié)議引入路由維護機制，縮小了緩沖區(qū)等待時間，提高了網(wǎng)絡端到端時延性能.

5.2.3 發(fā)包成功率分析

圖6表明，DTN-OLSR協(xié)議和ODR-OLSR協(xié)議在發(fā)包成功率相比OLSR協(xié)議有較明顯改善，其中在20節(jié)點和40節(jié)點場景下，DTN-OLSR協(xié)議發(fā)包成功率比ODR-OLSR協(xié)議性能更加優(yōu)秀，但是在節(jié)點密度更高的場景中，發(fā)包成功率低于ODR-OLSR協(xié)議.原因是機會路由存在傳播時延或者跳數(shù)的限制，隨著節(jié)點密度增加，通信跳數(shù)增加，機會路由由于最大傳播時延和最大跳數(shù)限制，導致性能下降.而ODR-OLSR協(xié)議隨著通信跳數(shù)的增大，鏈路中斷可能性增大，增加了啟動鏈路維護機制的概率，提高了網(wǎng)絡的性能.

圖6 成功率比較Fig.6 Success rate comparison

5.2.4 吞吐量分析

圖7表明，DTN-OLSR協(xié)議和ODR-OLSR協(xié)議在吞吐量相比OLSR協(xié)議有較明顯改善.通過控制開銷，時延，發(fā)包成功率，吞吐量分析可知，DTN-OLSR協(xié)議是通過犧牲端到端時延為代價換取發(fā)包成功率和吞吐量的提高.但是隨著網(wǎng)絡規(guī)模的擴大，由于機會路由最大時延和最大跳數(shù)的限制，導致DTN-OLSR協(xié)議的性能不如預期.在無人機自組網(wǎng)環(huán)境下通信業(yè)務要求低時延，因此DTN-OLSR協(xié)議還需進一步改進.

圖7 吞吐量比較Fig.7 Throughput comparison

5.2.5 通信跳數(shù)對發(fā)包成功率的影響

圖8 跳數(shù)對發(fā)包成功率的影響Fig.8 Impact of hops on packet success rate

圖8表明，ODR-OLSR協(xié)議從4跳-9跳相比OLSR協(xié)議成功率分別提高了：1%，1%，2%，5%，7%，9%.說明隨著通信跳數(shù)的增加，ODR-OLSR協(xié)議對發(fā)包成功率的改善更加明顯.其中發(fā)現(xiàn)：OLSR協(xié)議的發(fā)包成功率隨著通信跳數(shù)的增加快速下降，因為在無人機自組網(wǎng)中隨著通信跳數(shù)越長，通信鏈路中斷的可能性越大.因此在多跳通信中引入鏈路維護機制更有使用價值.

6 結(jié)束語

本文提出一種基于按需路由的OLSR路由協(xié)議(ODR-OLSR路由協(xié)議)，當節(jié)點進行通信時，發(fā)現(xiàn)路由信息丟失，及時發(fā)送HELLO尋址消息和TC尋址消息，增加路由的獲取途徑.理論分析和仿真實驗表明：ODR-OLSR協(xié)議在保持控制開銷不變的基礎上，明顯改善時延，發(fā)包成功率和吞吐量.但是HELLO消息尋址和TC消息尋址都要依賴保留字段Reserved攜帶目的地址，Reserved字段長度為16bit，標準的OLSR協(xié)議網(wǎng)絡地址為32bit，因此按需尋址機制適用于地址范圍為0～216-1的網(wǎng)絡.在未來工作中，將深入研究ODR-OLSR協(xié)議地址范圍問題，解決OLSR路由協(xié)議的不足.