無人機自組網按需尋路的可靠OLSR協議

胡 春，任 智，崔忠林

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

1 引 言

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

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

2 無人機自組網OLSR協議的問題

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

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

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

圖1 鏈路模型Fig.1 Link model

2.2 新入網節點無發及時與全網通信

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

3 改進協議ODR-OLSR介紹

針對無人機自組網中的問題，ODR-OLSR協議提出了以下改進：

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

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

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

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

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

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

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

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

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

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

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

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

3.3 控制消息的動態發送

原始的OLSR協議控制消息是定期發送，由于機制1和機制2會利用HELLO消息和TC消息進行臨時尋路，如果不調整控制消息的發送時間會導致控制開銷增加.因此引入控制消息的動態發送.如圖2所示，正常控制消息為周期性發送，周期為T，在[t0，t0+3T]時間段發送了4次控制消息.

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

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

圖3 控制消息動態發送時刻表Fig.3 Control message dynamic schedule

4 理論性能分析

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

4.1 控制開銷分析

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

4.2 發包成功率分析

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

定義：S為發包成功率，p為單跳鏈路中斷概率，L為鏈路連通概率，V為節點速度，n為通信跳數.

由引理1可知：

p∝V

(1)

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

(2)

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

S∝L

(3)

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

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

4.3 吞吐量分析

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

(4)

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

HODR-OLSR>HOLSR

(5)

4.4 時延分析

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

Dall=Dtransfer+Dbuffer

(6)

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

5 仿真驗證

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

5.1 仿真參數設置

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

表1 仿真參數設置Table 1 Simulation parameter setting

5.2 仿真結果分析

5.2.1 控制開銷分析

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

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

5.2.2 端到端時延分析

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

5.2.3 發包成功率分析

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

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

5.2.4 吞吐量分析

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

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

5.2.5 通信跳數對發包成功率的影響

圖8 跳數對發包成功率的影響Fig.8 Impact of hops on packet success rate

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

6 結束語

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