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

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

0 引言

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

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

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

1 相關工作

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

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

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

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

2.1 路由恢復時間測量方法

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

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

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

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

① 當網(wǎng)絡中鏈路或節(jié)點發(fā)生故障時，記錄故障鏈路或節(jié)點IP，記錄當前時刻為故障發(fā)生時刻。

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

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

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

a. 記錄當前節(jié)點、下一跳、目的IP、跳數(shù)；

b. 節(jié)點變?yōu)楫斍肮?jié)點的下一跳，跳數(shù)減一；

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

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

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

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

算法1 路由恢復時間測量方法輸入:故障鏈路Rerr或故障節(jié)點IPerr、故障發(fā)生時刻terr輸出:路由恢復時間1.R←getRoutingTable();∥讀取全網(wǎng)路由表R2.whileRoutingTableChangedo3. R←getRoutingTable();4. tcur←getCurretTime();∥記錄當前路由表時刻tcur5. ifRcontainsRerrorIPerrthen6. gotoline2;7. endif8. 初始化矩陣Q使得Q[i,j]為false,其中i,j分別表示路由起始節(jié)點和目的節(jié)點9. foreachRijwithQ[i,j]=falsedo∥從R中獲取i到j的路由Rij10. hops←hopsij;∥hopsij表示路由表中從i到j的跳數(shù)11. Q[i,j]←true;12. whilehops>1do13. i←nextij;∥獲取下一跳節(jié)點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為故障發(fā)生后至路由恢復時路由表發(fā)生變化的次數(shù)，n為網(wǎng)絡中節(jié)點的數(shù)量。

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

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

2.2 OLSR路由恢復分析與評估

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

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

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

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

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

3 FR-OLSR協(xié)議

3.1 協(xié)議描述

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

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

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

算法2 FR-OLSR核心機制輸入:事件類型eventType1.ifeventType=GenerateHelloMessagethen2. foreachneighborinhellomessagedo3. ifneighborType=SYMorMPRandlinkStatus=LostLinkthen∥檢測到與鄰居類型為對稱節(jié)點或MPR節(jié)點的鏈路狀態(tài)為丟失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 協(xié)議分析

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

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

trn=NHT+Tnh-Terr。

(1)

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

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

(2)

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

tro=Ttc-Terr+to。

(3)

如圖3所示，網(wǎng)絡的路由恢復時間為：

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

(4)

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

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

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

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

(5)

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

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

2跳鄰居節(jié)點的路由恢復時間為：

t′r2n=t′rn+NHT。

(6)

其他節(jié)點的路由恢復時間為：

t′ro=t′rn+to。

(7)

如圖4所示，網(wǎng)絡的路由恢復時間為：

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

(8)

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

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

圖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)，即對于鄰居節(jié)點和2跳鄰居節(jié)點，F(xiàn)R-OLSR能夠比OLSR路由恢復時間減少[0,NHT)?？紤]到Ttc-Terr-trn∈[0,TCI)，因此tro-t′ro∈[0,NHT+TCI)，即對于其他節(jié)點，F(xiàn)R-OLSR能夠比OLSR路由恢復時間減少[0,NHT+TCI)。綜上，在參數(shù)相同的情況下，F(xiàn)R-OLSR能夠比OLSR路由恢復時間減少[0,NHT+TCI)。

4 實驗評估

4.1 仿真設置

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

(a) 環(huán)形拓撲

4.2 仿真結果

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

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

圖7展示了兩種拓撲下不同協(xié)議不同參數(shù)每個節(jié)點平均生成的TC消息數(shù)量?？梢园l(fā)現(xiàn)相較于同參數(shù)的OLSR，F(xiàn)R-OLSR僅生成極少的額外TC消息。而減小TC消息發(fā)送間隔，顯而易見的，會生成更多的TC消息，帶來更多的開銷。

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

(a) 環(huán)形拓撲

(a) 環(huán)形拓撲

(a) 環(huán)形拓撲

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

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

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

5 結論

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