面向無人機網絡快速路由恢復的改進OLSR協議

劉青昕，朱小軍，董 超 *，劉世超

(1.南京航空航天大學 電子信息工程學院，江蘇 南京211106；2.南京航空航天大學 計算機科學與技術學院，江蘇 南京 211106)

0 引言

近年來，無人機由于其低成本、小體積、易攜帶等優勢，在各領域都有了越來越多的應用[1]，在實時監控、遠程檢測、搜尋救援甚至是戰場偵察[2]與協同作戰[3]等方面都有著出色的表現。相比單架無人機，無人機群協同配合能夠更加有效、迅速、靈活地完成數量更多、更復雜的任務。

FANET[4]將移動自組網的應用拓展到空中，為無人機群的可靠通信提供了一種可行的解決方案，使得無人機群能夠協同配合完成各項任務。通過FANET，無人機之間無需通過基礎設施就可以直接進行通信。此外，部分無人機可以與地面站或衛星進行通信。但由于無人機節點的高動態性、拓撲結構易發生變化等特點[5]，導致網絡的鏈路狀態更加頻繁地發生變化，在網絡開銷增加的同時，還會導致端到端時延增加、數據包投遞率下降等，甚至造成路由協議失效的情況[6]。因此FANET對路由協議提出了很大的挑戰，路由性能的好壞直接影響著網絡的性能。移動自組織網絡中的路由協議因為沒有考慮無人機的高移動性、劇烈變化的網絡拓撲和間歇性連接的通信鏈路，因此不能直接應用于無人機網絡[7]。

OLSR[8]是針對移動無線網絡需求而形成的經典鏈路狀態算法的優化，是自組織網絡中廣泛使用的協議之一。多點中繼(MPR)是在洪泛過程中轉發廣播信息的選定節點，與傳統的洪泛機制相比，該協議通過使用MPR技術大大減少了消息開銷。協議中節點需要周期性地交換各種控制信息，通過分布式計算來更新和建立自己的網絡拓撲圖，被鄰居節點選為MPR的節點需要周期性地向網絡廣播控制信息。通過這些機制，OLSR一定程度上保證了節點不會使用過時的路由表，保證了一定的實時性。然而，其對拓撲變化頻繁的網絡不夠敏感，當網絡中鏈路突然出現故障時，網絡的平均吞吐量、端到端時延等性能指標將有所惡化。

1 相關工作

考慮到移動自組織網絡經常發生鏈路和節點故障，AOLSR[9]將DSR與OLSR進行結合，并基于改進的Dijkstra算法實現路由恢復功能。文獻[10]在OLSR的基礎上，實驗了一種定時器管理技術Pop-Routing。其利用中間性和中心性的概念，根據網絡中節點的位置調整參數，使得網絡在總體開銷不變的情況下，更快地恢復導致較大流量損失的故障。MP-OLSR[11]路由中的每一個節點檢查下一跳是否仍在鄰居表中，并通過多徑路由來為下一跳不在鄰居表中的節點規劃新的路由。在MP-OLSR的基礎上，一種改進的MP-OLSR[12]被提出以優化其路徑選擇。VANET QoS-OLSR[13]考慮車輛自組織網絡，通過蟻群優化算法選擇MPR，并在此基礎上提出MPR恢復算法。當節點未收到來自MPR的預期TC消息時啟動恢復算法以處理故障鏈路。

還有一些研究嘗試對OLSR進行優化以適應FANET。D-OLSR[14]是一種針對配有定向天線的無人機所設計的協議。該協議提出了一種新的轉發機制：無人機在每次向目標發送數據時，會測試與目標無人機的距離，若距離小于定向天線最大通信距離的一半且全向天線可用，則使用全向天線；否則，使用定向天線。通過上述機制，該協議減少了所需MPR的數量。P-OLSR[15]在OLSR的基礎上，引入了GPS信息。該協議將GPS信息包含在報文中，節點接收到信息時，可以基于此計算出兩個節點的相對速度，從而評估節點間的通信鏈路質量，進而選擇質量更高的鏈路進行通信。進一步地，ML-OLSR[16]考慮了移動與負載感知。與P-OLSR類似，ML-OLSR通過移動感知算法，考慮與鄰居節點的相對速度和位置以避免選擇高速移動的節點作為MPR。同時，還引入了負載感知算法，考慮每架無人機上的數據包負載，以發現更穩定的路線，避免通過擁塞節點進行路由。與ML-OLSR相似，LTA-OLSR[17]考慮鏈路質量和流量負載感知。該協議提出了一種鏈路質量方案，通過使用接收信號強度的統計信息來區分節點與其鄰居節點之間的鏈路質量。還提出了一種流量負載方案，通過考慮信道利用率和緩沖負載來確保較輕的負載路徑，然而該協議存在高開銷和高計算復雜度的問題。

雖然已有研究對OLSR做出了改進以適應FANET的特點，然而他們主要將目標集中于丟包率與端到端時延。對于FANET中經常出現的節點和鏈路故障，研究較少。OLSR由于其超時管理機制，當鏈路斷開時，需要較長的時間才能恢復，無法將時間保持在可接受的范圍內。因此，需要對OLSR進行優化以使其能夠更快地對故障進行反應。

2 路由恢復時間測量與評估

2.1 路由恢復時間測量方法

為了衡量對鏈路或節點故障反應的快慢，本文使用了路由恢復時間這一概念。路由恢復時間是指自某一時刻網絡中發生故障開始，至網絡完全刪除這一故障的影響為止所經歷的時間，該指標能夠衡量整個網絡對鏈路或節點故障的敏感性。

在實際運行的無人機網絡中，測量路由恢復時間是困難的。原因在于獲取準確的故障發生時刻是困難的，故障既可能源自節點自身，也可能源自環境的變化和惡意的干擾。同時對于分布式的無人機網絡，信道質量難以保證，單個節點或地面站難以實時獲取整個網絡的路由表。因此，提出了一種測量方法以檢測路由恢復時間。為每一張路由表添加了時刻，如圖1所示，首先在故障發生后，記錄故障和發生的時刻，然后在每次路由表發生更新時進行檢查，直至路由中的故障鏈路或節點完全刪除且不存在回路的影響，記錄該時刻與故障發生時刻的差值即為路由恢復時間。應當指出，在實際運行中不需要執行這些操作以測量路由恢復時間，僅在對協議進行評估時需要測量。

圖1 測量方法流程Fig.1 Measurement method flowchart

其測量方法可表述為如下步驟：

① 當網絡中鏈路或節點發生故障時，記錄故障鏈路或節點IP，記錄當前時刻為故障發生時刻。

② 當網絡中路由表發生變化時，獲取路由表(包含目的IP、下一跳和跳數)和當前時刻。

③ 遍歷路由表，查看是否存在故障鏈路或節點。若存在，返回步驟②。

④ 對于每一個節點路由表的每一個目的IP，按照如下規則進行路由查找以驗證路由是否正確：

a. 記錄當前節點、下一跳、目的IP、跳數；

b. 節點變為當前節點的下一跳，跳數減一；

c. 比較記錄的跳數和新的當前節點的跳數，若不相等，則返回步驟②；

d. 若跳數不等于一，則返回步驟a；否則，返回步驟④。

⑤ 當路由表被遍歷完畢后，輸出當前時刻與故障發生時刻的差值作為路由恢復時間。

路由恢復時間測量方法偽代碼如算法1所示。

算法1 路由恢復時間測量方法輸入:故障鏈路Rerr或故障節點IPerr、故障發生時刻terr輸出:路由恢復時間1.R←getRoutingTable();∥讀取全網路由表R2.whileRoutingTableChangedo3. R←getRoutingTable();4. tcur←getCurretTime();∥記錄當前路由表時刻tcur5. ifRcontainsRerrorIPerrthen6. gotoline2;7. endif8. 初始化矩陣Q使得Q[i,j]為false,其中i,j分別表示路由起始節點和目的節點9. foreachRijwithQ[i,j]=falsedo∥從R中獲取i到j的路由Rij10. hops←hopsij;∥hopsij表示路由表中從i到j的跳數11. Q[i,j]←true;12. whilehops>1do13. i←nextij;∥獲取下一跳節點14. ifQ[i,j]then15. gotoline10;∥該路由已被查驗16. endif17. hops←hops-1;18. ifhops≠hopsijthen19. gotoline2;20. endif21. Q[i,j]←true;22. endwhile23. endfor24. returntcur-terr;25.endwhile

定理1：算法1能夠正確檢測路由恢復時間，其時間復雜度為O(kn2)，其中k為故障發生后至路由恢復時路由表發生變化的次數，n為網絡中節點的數量。

證明：當路由表中存在故障鏈路或故障節點時，算法將在第6行重新開始下一輪檢測。當路由表中存在環路或過時的路由時，算法將在第19行重新開始下一輪檢測。當算法執行至第24行時，路由表中不存在故障鏈路或節點，同時不存在環路。因此，算法1能夠正確檢測路由恢復時間。

對于最外層的while循環，算法1運行k輪。在每一輪中，第3～8行運行一次，復雜度為O(n2)；由于第21行會將一個Q中元素從false置為true，而Q共有O(n2)個元素，因此第9～23行的for循環的時間復雜度至多為O(n2)。因此，算法1的時間復雜度為O(kn2)。

2.2 OLSR路由恢復分析與評估

對于網絡中路由的更新，OLSR主要受到以下參數的影響[18]：① HELLO消息的發送間隔(Hello Interval，HI)；② 鄰居保持時間(Neighbor Hold Time，NHT)；③ TC消息發送間隔(TC Inteval，TCI)；④ 拓撲保持時間(Topology Hold Time，THT)。在默認設置中，HI=2 s，TCI=5 s，NHT與THT分別被設置為HI與TCI的3倍。在每個網絡接口，節點會廣播HELLO消息以發現鄰居節點，將鄰居節點添加到自己的鄰居表中，并在HELLO消息過期后將鄰居刪除。HELLO消息僅在一跳范圍內傳播，不會被其他節點轉發。另外，每個MPR節點廣播TC消息以更新路由。TC消息在整個網絡中傳播，使得每個節點建立并維護拓撲表。一旦節點失效，所有包含該節點的路由將失效，在新的TC消息廣播至網絡或者TC消息過期之前，還可能會導致臨時的路由環路。具體而言，不同參數影響路由恢復時間的原理如下。

HELLO消息被每個節點以HI為周期廣播，節點接收到HELLO消息后NHT時間內將該信息視為有效信息。HELLO消息承擔鄰居檢測任務，通過類似3次握手的機制完成鄰居檢測。一旦節點與鄰居節點完成鄰居檢測，則將鄰居節點記錄在鄰居表中，并開放接口連接鄰居節點；如果鄰居檢測失敗，則刪除記錄。HELLO消息還承擔著鏈路感應任務，節點在每個接口上檢測和鄰居接口之間的鏈路。節點會在每個接口上廣播其一跳鄰居，為了鏈路感應的目的，每個節點到每個鄰居的鏈路具有“對稱”“非對稱”和“丟失”的狀態。“對稱”表示到該鄰居節點的鏈路已被驗證為雙向，即可以在兩個方向上傳輸數據。“非對稱”表示已經接收到來自該節點的HELLO消息，但無法確認該節點是否能接收消息。“丟失”表示節點和鄰居接口之間的鏈路已斷開。通過交換HELLO消息，OLSR維護一張鄰居表，其中包含一跳鄰居地址、鏈路狀態、有效時間，以及通過該一跳鄰居可達的2跳鄰居地址與有效時間。每當收到新的HELLO消息時，節點便會更新鄰居表中的條目，并將更新條目的過期時刻設置為當前時刻加上NHT。OLSR會周期性地更新鄰居表以刪除其中過期的條目。因此，NHT的長短決定了節點對鏈路斷開的敏感性，NHT越長，鄰居表中條目的有效時間越長，發現鏈路過期越慢，反之，NHT越短，鄰居表中條目的有效時間越短，發現鏈路過期的越快。由于OLSR的鄰居發現機制，NHT不應小于3倍HI，所以NHT應與HI一同調整。

基于鄰居表，每個節點選擇出MPR節點集。網絡中的節點會向其他節點以TCI為周期廣播TC消息，其中包含所有選擇該節點為MPR的節點的地址(稱作MPR selector)。被選作MPR的節點按照規則生成和轉發TC消息等控制消息，通過控制MPR集的大小可以減少洪泛的開銷。其他節點收到TC消息后THT時間內將該消息視為有效。基于TC消息的交換，各個節點維護一張拓撲表。同樣的，拓撲表中條目的過期時刻為收到TC消息的時刻+THT。網絡中的節點通過TC消息保持拓撲表更新，通過拓撲表和鄰居表可以計算出全局路由。通過減小TCI，能夠使節點更頻繁地廣播TC消息，從而更快地更新網絡中節點的拓撲表。通過減小THT，能夠防止即使在TC消息丟失等情況下，也不至于使用過時的拓撲信息。

基于以上分析，測試了改變以上參數時OLSR的路由恢復性能。采用了經典的環形拓撲，每個節點只能與相鄰兩個節點進行通信，在EXata 5.1上進行了多次重復仿真，每次仿真持續60 s，并設定其中一個節點在第20 s時離線，仿真結果如圖3所示。從圖中可以發現，默認的OLSR路由恢復時間較長，網絡中節點難以及時更新拓撲信息，這對于無人機網絡是難以忍受的。另一方面，相較于OLSR的默認設置，當節點數量較少時，減小TCI與THT對減少路由恢復時間效果不明顯，隨著節點數量的增加，情形逐漸好轉。而減小HI與NHT能夠顯著且迅速地減少路由恢復時間，可以認為減小HI與NHT效果比減小TCI與THT更明顯。當以上參數同時減小為默認值的一半時，取得了最好的路由恢復性能，但是這會增加大量額外的控制開銷。因此，急需對OLSR進行優化以加速網絡的路由恢復。

圖2 不同參數OLSR路由恢復時間對比Fig.2 Comparison of OLSR routing recovery time with different parameters

3 FR-OLSR協議

3.1 協議描述

在2.2節中分析了OLSR路由恢復的影響因素，注意到OLSR節點鄰居表中條目過期后，并不會實時更新鄰居表，同時更新后的MPR selector需要等待TC消息周期性廣播至整個網絡，這大大增加了OLSR的路由恢復時間。考慮到無人機計算資源與能源的緊張性，也不宜頻繁地計算路由信息。因此，提出快速路由恢復協議FR-OLSR，其核心機制如下：

每次節點生成HELLO消息時，檢測HELLO消息中是否有與鄰居類型為對稱節點或MPR節點的鏈路狀態為鏈路丟失。若有，則在HELLO消息發送后，更新鄰居表與路由表，生成并發送一個新的TC消息。實際上，實時監測鄰居表，每當鄰居表中存在過期條目時更新鄰居表與路由表能夠使鄰居節點更快路由恢復。然而，對于擁有多個接口多個鄰居的節點，由于鄰居表中還包含2跳鄰居節點，鄰居表中條目狀態變化是頻繁的。實時監測鄰居表并更新會導致計算開銷成倍甚至是幾十倍的增長。僅在生成的HELLO消息中進行檢測，在檢測到鏈路丟失時額外發送一個TC消息，能夠在多條鏈路頻繁丟失時也僅在HI時間內額外生成一個TC消息，有效控制額外的開銷。

當節點收到HELLO消息后，同樣檢測HELLO消息中是否有與鄰居類型為對稱節點或MPR節點的鏈路狀態為鏈路丟失。若有，則記錄當前時刻，并在NHT秒后更新鄰居表與路由表。對于運行OLSR的小規模網絡，當發生節點或鏈路故障時，2跳鄰居節點總是最后路由恢復的。通過檢測接收的HELLO消息中的鏈路丟失信息，能夠在不監測鄰居表中2跳鄰居信息的同時，有效加速路由恢復。偽代碼如算法2所示。

算法2 FR-OLSR核心機制輸入:事件類型eventType1.ifeventType=GenerateHelloMessagethen2. foreachneighborinhellomessagedo3. ifneighborType=SYMorMPRandlinkStatus=LostLinkthen∥檢測到與鄰居類型為對稱節點或MPR節點的鏈路狀態為丟失4. sendHelloMessage();5. refreshNeighborTable();6. calculateRoutingTable();7. generateTCMessage();8. sendTCMessage();9. endif10. endfor11.elseifeventType=ReceiveHelloMessagethen12. foreachneighborinhellomessagedo13. ifneighborType=SYMorMPRandlinkStatus=LostLinkthen14. refreshNeighborTable(NHT);∥NHT秒后更新鄰居表15. calculateRoutingTable(NHT);∥NHT秒后計算路由表16. endif17. endfor18.endif

3.2 協議分析

引理1：OLSR的路由恢復時間為max(2NHT+Tnh-Terr,Ttc-Terr+to)，其中Terr為故障發生時刻，Tnh為故障發生后下一次鄰居表更新時刻，Ttc為鄰居節點路由恢復后下一次TC消息發送時刻，to為新生成的TC消息廣播至所有節點所花費的時間。

證明：當節點故障或是鏈路突然斷開，對于OLSR網絡的路由恢復，可以分為3種節點：鄰居節點、2跳鄰居節點和其他節點。鄰居節點在上一次接收到對應的HELLO消息NHT時間后故障鏈路過期，并在之后最近一次的鄰居表更新計時器到期時更新路由。則鄰居節點的路由恢復時間為：

trn=NHT+Tnh-Terr。

(1)

由于在鄰居節點故障鏈路過期前，2跳鄰居節點會收到鄰居節點周期性廣播的含有該鏈路的HELLO消息，因此2跳鄰居節點的路由恢復時間為：

tr2n=trn+NHT=2NHT+Tnh-Terr。

(2)

其他節點則會在收到故障鏈路鄰居節點的TC消息時將故障鏈路刪除，即其他節點的路由恢復時間為：

tro=Ttc-Terr+to。

(3)

如圖3所示，網絡的路由恢復時間為：

tr=max(trn,tr2n,tro)=max(tr2n,tro)。

(4)

圖3中，Xi為OLSR周期性廣播TC消息時刻，Yi為鄰居表更新計時器到期時刻。

定理2：FR-OLSR的路由恢復時間為max(t′rn+NHT,t′rn+to)，路由恢復性能優于OLSR，其中t′rn為鄰居節點路由恢復時間。

證明：對于運行FR-OLSR的節點，鄰居節點的路由恢復時間為：

t′rn=min(NHT+Th-Terr,NHT+Tnh-Terr)，

(5)

式中，Th為故障發生后下一次發送HELLO消息的時刻。

圖3 OLSR路由恢復時間示意圖Fig.3 Schematic diagram of OLSR routing recovery time

2跳鄰居節點的路由恢復時間為：

t′r2n=t′rn+NHT。

(6)

其他節點的路由恢復時間為：

t′ro=t′rn+to。

(7)

如圖4所示，網絡的路由恢復時間為：

t′r=max(t′r2n,t′ro)。

(8)

圖4中,Zi為OLSR周期性廣播HELLO消息時刻。

因為t′r2n-t′ro=NHT-to，所以當toNHT時，TC消息由于丟包或網絡規模擴大，無法迅速廣播至全網，路由恢復時間取決于TC消息廣播至全網的時間。

圖4 FR-OLSR路由恢復時間示意圖Fig.4 Schematic diagram of OLSR routing recovery time

考慮到Th∈[0,HI)、Tnh∈[0,NHT)，因此tr2n-t′r2n=trn-t′rn∈[0,NHT)，即對于鄰居節點和2跳鄰居節點，FR-OLSR能夠比OLSR路由恢復時間減少[0,NHT)。考慮到Ttc-Terr-trn∈[0,TCI)，因此tro-t′ro∈[0,NHT+TCI)，即對于其他節點，FR-OLSR能夠比OLSR路由恢復時間減少[0,NHT+TCI)。綜上，在參數相同的情況下，FR-OLSR能夠比OLSR路由恢復時間減少[0,NHT+TCI)。

4 實驗評估

4.1 仿真設置

本文基于EXata 5.1進行仿真，網絡拓撲如圖5所示，分別為正方形環形拓撲與網狀拓撲，調整傳輸功率使節點僅能與相鄰節點進行通信(即圖5中虛線所示)。每個節點物理層采用802.11b協議，設置路徑損耗模型為兩徑模型，每次仿真時間為60 s，并在第20 s時其中一個節點離線。

(a) 環形拓撲

4.2 仿真結果

為了評估FR-OLSR的性能，本文選擇了EXata中的OLSR-INRIA作為對比協議，從路由恢復時間和協議開銷兩個方面，針對兩種拓撲不同節點數量進行了多次重復實驗。本文對兩種協議均設置了默認參數和高性能參數進行仿真。對于OLSR,默認參數為HI=2 s，NHT=6 s，TCI=5 s，THT=15 s，高性能參數(OLSR*)為HI=1 s，NHT=3 s，TCI=2.5 s，THT=7.5 s；對于FR-OLSR,默認參數為HI=2 s，NHT=6 s，TCI=5 s，THT=15 s，高性能參數(FR-OLSR*)為HI=1 s，NHT=3 s，TCI=5 s，THT=15 s。

圖6(a)給出了環形拓撲下隨著節點數量增加OLSR和FR-OLSR路由恢復時間的變化曲線，由圖可知，FR-OLSR能加快路由恢復，減小突然斷開的鏈路對網絡的影響。同時，路由恢復時間與節點數量呈現出單調增加的趨勢。因為在該拓撲下，網絡中路由最大跳數較大，TC消息廣播至整個網絡所需時間較長，路由恢復時間主要受該因素影響。圖6(b)給出了網狀拓撲下隨著節點數量增加OLSR和FR-OLSR路由恢復時間的變化曲線，由圖可知，當節點數量較小時，兩種協議的路由恢復時間均維持在一定范圍內。因為TC消息能夠較快的廣播至整個網絡，路由恢復時間主要取決于2跳鄰居節點的恢復時間。

圖7展示了兩種拓撲下不同協議不同參數每個節點平均生成的TC消息數量。可以發現相較于同參數的OLSR，FR-OLSR僅生成極少的額外TC消息。而減小TC消息發送間隔，顯而易見的，會生成更多的TC消息，帶來更多的開銷。

圖8展示了兩種拓撲下不同協議不同參數每個節點平均轉發的TC消息數量。結合之前的圖表進行分析，減小TC消息發送間隔，OLSR僅能夠有限地減少路由恢復時間，但會帶來大量的額外開銷，大幅占用無人機有限的資源。

(a) 環形拓撲

(a) 環形拓撲

(a) 環形拓撲

表1展示了不同協議不同參數每個節點生成的HELLO消息數量。實際上，這一指標僅與HI有關。由于HELLO消息僅在一跳范圍內傳播，不會被接收到的節點轉發。因此，減小HELLO消息發送間隔，僅會帶來少量額外開銷。

表1 HELLO消息平均生成數量Tab.1 Average number of HELLO messages generated

綜上所述，相較于OLSR，在均為默認參數的情況下，FR-OLSR可以在增加5%控制開銷的情況下，將路由恢復時間降低25%。而通過將FR-OLSR的HI與NHT減小為原來的一半，FR-OLSR能夠在增加15%控制開銷的情況下，將路由恢復時間降低50%。

5 結論

傳統的OLSR協議是針對移動無線網絡需求而形成的經典鏈路狀態算法的優化，但在FANET中，由于其超時管理機制，當鏈路斷開時，需要較長的時間才能恢復，無法將時間保持在可接受的范圍內。本文給出了路由恢復時間的一種全新測量方法，分析了OLSR協議中影響路由恢復時間的因素，并提出了FR-OLSR以快速恢復網絡中的路由。EXata仿真結果表明，相較于OLSR，FR-OLSR能夠在增加少量通信開銷的同時，減少路由恢復時間，加快網絡的路由恢復。