面向任務的無人飛行器自組網OLSR 協議

陳立偉，簡依雯，王桐，歐陽敏，高山

1. 哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001

2. 哈爾濱工程大學 先進船舶通信與信息技術工業和信息化部重點實驗室，黑龍江 哈爾濱 150001

近年來，由于生物群體行為的啟發[1]，大規模的無人飛行器（unmanned aerial vehicle ，UAV）在各行業領域得到了廣泛的關注[2]，通過集群協作完成搜索[3]、地形勘測[4]等各項任務。為實現集群中的協同交流與數據傳輸，無人飛行器自組網應運而生。每個無人飛行器通過無線信號連接進行多跳傳輸，既是任務執行節點也是通信中繼節點。而無人飛行器多任務網絡則是以完成多項協同任務[5]為目的的無人飛行器自組網，通過多個無人飛行器分系統實現自組織的行動[6]。

優化鏈路狀態路由協議（optimized link state routing，OLSR）作為先應式路由協議[7]，查找路由時延小，與按需式路由協議相比更適合需要低時延的無人飛行器多任務網絡。同時OLSR 協議的多點中繼（multipoint relay，MPR）技術能有效減少網絡中廣播消息的泛濫，在一定程度上減輕了先應式路由協議在高速場景下網絡冗余信息占用帶寬多的問題，因此OLSR 十分適用于規模大的無人飛行器集群通信[8]。目前學者們針對OLSR 路由協議的優化，大多以提升鏈路穩定性和減少路由開銷作為直接出發點進行研究。針對無人飛行器網絡節點高速移動問題，文獻[9]提出一種按需尋路的可靠OLSR 協議，提出基于拓撲控制報文全網尋路機制和基于HELLO 鄰居尋路機制，通過增加路由獲取途徑，維護多跳鏈路的穩定性。針對OLSR 協議路由開銷大的問題，文獻[10]基于博弈論改變節點選擇意愿從而改善MPR 選擇，以此減少網絡中控制數據包的數量，但主要適用于密集型低速無人飛行器網絡。文獻[11]則在相同意愿值條件下計算節點能量消耗，從而優化MPR選擇，降低網絡平均能量消耗。這些優化算法在動態變化程度高的無人飛行器網絡中無法始終保持高性能，不能隨著應用需求、任務環境自適應變化，與實際任務匹配的靈活性差，實用性、可移植性不高。

近年對于無人飛行器網絡拓撲自適應的路由算法研究逐漸成為熱點。文獻[12]提出基于QLearning 思想的移動自組網OLSR 路由策略，通過在線學習來適應網絡高度動態變化的拓撲結構，但基于在線強化學習的優化將帶來龐大的計算量與多余的能量消耗。文獻[13]設計了基于動態拓撲的路由協議，根據卡爾曼濾波預測節點位置，預測節點的加入、退出網絡情況動態調整HELLO消息的廣播周期，從而提升網絡連通性，但該算法的實現基于無人飛行器節點在勻速不變的環境。文獻[14]中通過網絡拓撲變化情況將無人飛行器網絡分為編隊飛行與自主飛行2 種模式，從而調整HELLO 消息的廣播周期，但僅設置了高、低2 類廣播周期，拓撲自適應性程度不高。

綜上，現有對面向任務的無人組網架構研究較少，針對OLSR 的改進協議在無人飛行器高速環境下無法保持高性能的網絡通信，在多任務環境下動態適應性不夠。由此，本文具體解決方案如下：針對無人飛行器多任務網絡中任務集群拓撲變化程度高、難以度量的問題，提出基于模糊邏輯的拓撲穩定度計算方法；針對現有探測拓撲狀態方法的動態適應性不高問題，提出探測周期自適應的動態探測方法；針對OLSR 路由協議在無人飛行器集群低動態任務時冗余信息多、高動態任務時鏈路易斷開的問題，提出HELLO 控制消息的自適應廣播策略和MPR 優化選擇策略。

1 無人飛行器集群的聯盟結構

1.1 任務驅動的無人飛行器聯盟組網

聯盟結構主要出現在多智能體模型[15]及博弈過程中，用于描述智能體間的邏輯關系。同為分組結構，路由算法常用的分簇算法聚焦于如何使組內節點間盡可能擁有穩定的通信鏈路，多以通信距離、網絡連通度等加權參數為分組依據[16]；而聯盟結構則聚焦于如何使得分組后利于完成任務并最大化任務聯盟收益，其分組依據是任務分配或博弈的結果[17]。因此聯盟結構與現有分簇結構的最大差異是集群分組的驅動力不同，聯盟是面向任務的。

現有基于分簇的路由算法對拓撲變化適應能力相對較差，多適用于拓撲變化較為緩慢的網絡。在多任務環境中，無人飛行器集群網絡拓撲結構劇烈變化，采用分裂或合并策略的傳統分簇路由算法需要很大的開銷用于構建簇或者維持簇結構的穩定。但實際上此時各組無人飛行器正有序完成不同類別的協同任務，無需重新分組構建簇。因此聯盟結構更適合無人飛行器集群在多任務環境下的任務驅動特性。決策系統將滿足目標任務資源需求且通信鏈路穩定的多個無人飛行器分配給該目標任務，無人飛行器以任務分配的結果進行結盟[18]，階段性任務結束后聯盟解散，等待下一次小任務的分發及聯盟更新。同時在必要環境下可以實現同一無人飛行器分屬2 個任務聯盟[19]等復雜情況，快速響應各項不確定任務。

本文提出基于聯盟的無人飛行器集群組網架構，如圖1 所示，完成初始組網工作。

圖1 面向任務的無人飛行器自組網

在給定的任務集合的情況下，建立滿足需要的無人飛行器集群自組網有3 個重要步驟：任務量化、資源分配和聯盟劃分。

1）任務量化

通過任務分析評估，將任務細化為一系列子任務。在整體無人飛行器集群待完成的任務集合中，各任務可被視為一系列子任務的組合，例如搜索任務可被看作是數據收集任務和數據整合任務等多個子任務的組合。不同的任務對應不同的任務優先級、通信需求、資源利用優先級[20]等。因此定義子任務擁有屬性（重要性、風險性、完成所需時間級別等），規劃子任務序列執行時間線，涉及任務分解、規劃的相關算法。

2）資源分配

分析任務數據、依據子任務屬性完成資源高效分配，完成子任務與資源平臺的映射。資源主要分為無人飛行器資源與頻譜資源。無人飛行器資源分為聯盟領導無人飛行器（coalition leader UAV，CLU）與聯盟成員無人飛行器（coalition member UAV，CMU），擁有更高的硬件能力，能進行信息處理與決策制定的才能作為CLU。頻譜資源的分配即為每個任務聯盟劃分合適的帶寬。

3）聯盟劃分

建立聯盟形成博弈模型[21]，確定所有子任務的任務收益與相關約束條件，在相關約束下最大化總體任務收益，完成任務聯盟的劃分。可用相關約束有無人飛行器執行任務類型約束、任務重要性及執行順序約束、任務所需無人飛行器數目約束等，任務收益的設定與任務執行相關（燃料損失、懸停時間等），也與通信效率相關（聯盟數量、大小等）。任務驅動組網的關鍵就是形成初始穩定的無人飛行器任務聯盟。在形成穩定任務聯盟后，依據各聯盟內的子任務執行要求進行鄰居發現、建立路由，聯盟間的通信則由CLU 實現。因此，在面向無人飛行器多任務網絡中，不同聯盟針對各自任務表現出的網絡拓撲存在顯著差異。作為空中通信平臺的無人飛行器將懸停在所需區域上空[22]，鏈路與拓撲的變化是緩動態的，與此相反，完成搜索掃描任務則要求無人飛行器集群在大范圍內移動，鏈路經常中斷需要重新建立鏈接，同時任務的二次分配也會使得聯盟擁有相對高動態的拓撲變化，而目標跟蹤、有計劃編隊等類型的任務則使得聯盟擁有相對靜態的拓撲變化。

處于不同任務環境下無人飛行器的任務狀態不同，導致無人飛行器集群的飛行狀態有顯著差異，從而形成不同的拓撲結構。同時，各無人飛行器聯盟處于不同任務狀態下，聯盟的拓撲變化情況可以直觀反映出該聯盟中無人飛行器的飛行狀態，因此可以利用聯盟拓撲變化信息增強路由算法對于無人飛行器聯盟網絡的適用性。由此定義拓撲穩定度（topological stability, TS），以度量一段時間內的網絡拓撲變化程度，根據TS 對路由算法中進行自適應調整，實現整個無人飛行器集群的穩定通信。

1.2 拓撲穩定度的計算

無人飛行器集群中，節點的移動性可能會導致鄰居節點間的相對變化，引起鄰居節點間局部拓撲的改變。某聯盟中有n架無人飛行器，定義其無人飛行器節點集合U={u1,u2,...,un}，每個節點維護一個一跳鄰節點集合。無人飛行器節點i的一跳鄰節點集合記為Ni_1，一跳鄰節點數目為m。在t時刻，無人飛行器節點i相對節點j的速度為vij(t)。定義從t時刻經過T時間，節點i與其所有一跳鄰節點的平均相對速率變化因子（relative velocity change，RV）Ri為

式中：|v|max為該聯盟中允許的最大速率，Ri(t,t+T)∈[0,1]。

考慮節點i和節點j某時刻的相對運動情況，dij為兩節點間距離，如圖2 所示。將節點j視為參考節點，則節點i相對節點j的運動速度為vij，Rx為節點的最大通信半徑。則視線段L為兩節點鏈路預測保持連接的相對運動路徑，dver為節點j與線段L的距離，將節點i在線段L上運動時間視為鏈路預測存活因子，由此定義節點i與其所有一跳鄰節點的平均鏈路預測存活因子（link hold，LH）Li為

圖2 某時刻兩節點的相對運動情況

同時，計算可得Li∈[0,1]。

式（1）～（2）均使用一跳鄰節點集合中的節點進行計算，存在局限性，即無法對鄰節點失效進行判斷。在該節點無失效鄰節點變化時利用Ri(t,t+T)和Li進行計算處理后可以很好表現網絡中該節點局部飛行狀態的變化，但網絡可能存在鏈路中斷，鄰居節點失效的情況，此時已無法獲取更新該節點的變化信息。例如某場景有Ri,j(t1,t2)=0，則無法判斷t2時刻節點i與節點j是完全不存在相對移動性變化、保持穩定鏈接的情況，還是節點j已與節點i斷開連接，已經成為其失效鄰居節點。針對該局限性，加入一跳鄰節點損失因子。

定義時間T內節點i的一跳鄰居節點損失因子（neighbor loss，NL）Ni為

式中：ni_loss1(t,t+T)為t時刻到t+T時刻節點i在t時刻的鄰居集合中失效的一跳鄰節點數目；ni_1(t)為t時刻節點i的一跳鄰節點個數，Ni(t,t+T)∈[0,1]。

3 個因子均為[0,1]的值，將之作為輸入進行模糊化處理，得到該節點局部拓撲穩定度。3 個模糊輸入變量均有3 個等級{Low,Medium,High}，隸屬度函數使用三角函數及梯形函數，使用if-then規則定義27 條模糊規則完成輸入輸出映射，如表1所示。其中，輸出參數為該節點的局部穩定度，具有5 個等級{Worst,Weak,Middle,Good,Best}。圖3為輸入、輸出參數的隸屬度函數。

表1 模糊規則庫

圖3 輸入、輸出參數的隸屬度函數

使用Min-Max 決策處理所有模糊結果，再使用重心法進行解模糊運算，即得到所求節點的局部穩定度。由此，將計算出的每個節點的局部穩定度求均值，得到聯盟內網絡的拓撲穩定度為

式中：x為隸屬度函數的自變量，fi(x)為節點i隸屬度函數集。

2 TA-OLSR 算法的實現

OLSR 算法通過定期廣播控制消息中的HELLO消息來維護節點的鄰居關系，更新計算拓撲表、路由表。相對更靜態拓撲的任務過程中，無人飛行器間的動態性低，鏈路更加穩定，這種情況下高頻率的HELLO 消息的廣播不僅會帶來控制信息的冗余，造成不必要的資源浪費，增大網絡阻塞的幾率。相反，在集群內節點轉為相對高動態的情況下，HELLO 的廣播頻率依舊維持不變將難以獲取最新的鄰居關系，導致數據消息包的丟失率增大。本文通過探測無人聯盟的拓撲狀態，基于模糊邏輯計算聯盟的TS，根據TS 值實現HELLO 消息廣播周期的自適應調整。同時為增強算法的自適應程度，自適應調整無人聯盟的拓撲狀態探測周期，形成動態探測。

OLSR 協議中的MPR 技術可以有效減少網絡中的控制分組數量，主要思想是僅有MPR 集合中的節點才能轉發拓撲控制消息，因此MPR 集合的選擇將直接影響整體路由性能。原始OLSR 協議中通過節點連接度來選擇MPR 節點，選擇能盡可能多的連接其他節點的節點成為MPR 節點。但該方案應用于無人飛行器多任務網絡時，可能由于任務的高速移動性導致節點間鏈路穩定度下降，僅考慮節點間的連接度顯然不夠。因此TA-OLSR 算法在節點連接度的基礎上加入節點局部TS 值作為MPR 節點的選擇依據，在不過多增加計算量的同時提升無人飛行器聯盟網絡連接的穩定性。

TA-OLSR 算法的主要實現思路如圖4 所示。

圖4 TA-OLSR 協議實現思路

2.1 探測周期自適應與HELLO 消息廣播自適應

每個節點都維護一個本地鏈路信息表和鄰居節點信息表，它們的建立是通過周期性廣播HELLO消息進行鏈路探測得到的。以Tprobe的時間間隔探測聯盟網絡的拓撲變化，進行TS 的計算。第k次探測(k＞1)與第k?1次探測的時間間隔為

式中 μ是控制系數，用來將TS 探測周期調整至合適范圍，與整體任務情況相關。以任務信息驅動完成組網，無人飛行器快速形成聯盟，此時HELLO 廣播周期為初始常量值TH_cons，在聯盟網絡開始探測拓撲后，將自適應的改變廣播周期，即THELLO。2 次TS 探測的時間間隔根據前一次探測計算的THELLO信息反饋得出。在網絡拓撲相對動態性低的情景下，一定時間內的拓撲變化比動態性高的情景下小，因此在低動態性的網絡拓撲中應延長下一次探測的時間。在根據網絡情況調整THELLO的同時，THELLO可以反映當前時間段內網絡拓撲變化情況，從而有依據地改變下一探測的間隔時間，即實現TS 探測周期的自適應改變，如圖5 所示。

圖5 探測周期與HELLO 廣播周期的動態改變

定義 δk是無人飛行器第k次探測時的空間密度，通常來說高密度的網絡拓撲情況通常比低密度的鏈路變化情況更復雜，本文使用它來增大這種差異。Rx為該網絡中每架無人飛行器的最大通信距離，具有更長傳輸范圍的無人飛行器可以在更長HELLO 間隔內保持網絡吞吐量[23]，因此第k次探測計算HELLO 廣播周期為

式中 γ為控制系數，用來將HELLO 廣播周期調整至合適大小，在本文場景取0.01。

利用任務規劃步驟[24]中得到的任務聯盟相關數據（任務類型、無人飛行器數目等），限制聯盟最大、最小HELLO 廣播周期，可以防止過高、過低的周期出現，同時減少不必要的計算開銷。由此進一步約束為

式中：h1和h2為控制閾值，Thigh、Tlow為整體任務規劃中限制的最大、最小HELLO 廣播周期。

2.2 MPR 選擇策略的調整

針對網絡中的節點，OLSR 算法首先創建其一跳對稱鄰居集合N1={u1_1,u1_2,···,u1_n1}、兩跳對稱鄰居集合N2={u2_1,u2_2,···,u2_n2}， 用于計算MPR 集合M，首先根據N1中節點的意愿來初始化合集M，然后計算N1中節點的連接度Degree（優先選擇Degree值大的節點）用以覆蓋完全集合N2中的節點，直到集合N2為空集則該節點的MPR 集合M建立完畢。

本文在連接度的基礎上加入節點局部TS 值作為MPR 節點的選擇依據，能在避免額外增加過多計算量的情況下進一步確定待選節點的穩定性。則MPR 選擇度量改為中繼節點權重（weight of relay node，WR）Wi為

式中：Di為候選節點i的連接度大小，Ti為候選節點i當前時段的Ti(t,t+T)值。平均鏈路狀態越穩定則廣播丟包率將越低，因此使其選中可能性越大。計算出N1中每個節點的WR 值，從大到小排序用以選擇MPR 節點，直至覆蓋完全集合N2中的節點，直到集合N2為空集則該節點的MPR 集合M建立完畢。計算MPR 流程如圖6 所示。

圖6 MPR 選擇流程

3 仿真及數據分析

在本節中使用離散事件模擬器NS-3（network simulator 3）對算法進行了仿真實驗。為了更好地反映算法對無人飛行器集群的影響，仿真實驗涉及到的數據設定如表2 所示。

表2 仿真參數設置

仿真實驗中原始OLSR 算法的HELLO 廣播周期為1 s，將Thigh設定為4 s、Tlow設定為0.2 s。每次仿真設定10 條數據流，分別計算每條數據流的各項指標，再對其求均值，同時為捕捉不同拓撲情況下的性能，每個實驗均對節點取隨機起始位置進行10 次仿真取均值，以下是每條數據流的平均性能。文中將本文TA-OLSR 算法與原始OLSR算法、使用分簇的OLSR Med+[25]算法進行了比較。

圖7、圖8 分別是在節點數目變化下3 種算法平均包投遞率（packet delivery rate，PDR）和平均端到端時延的對比圖，其中無人飛行器節點的最大速度為10 m/s。

圖7 節點數目影響下的平均包投遞率

圖8 節點數目影響下的平均端到端時延

可以看出TA-OLSR 在節點數目增多的情況下仍能保持較高的包投遞率，尤其是在90 個節點情景下TA-OLSR 的PDR 相比于OLSR Med+提升了5.19%，相比于原始OLSR 則提升了17.39%。圖中3 種算法的包投遞率在節點數50～70 之間有一段明顯的上升過程，這主要是由于仿真環境中節點通信半徑設置不大，在速度低時無人飛行器密度對性能造成了很大影響，此無人飛行器數量區間形成了較為適合本仿真環境的節點密度，一定程度上促進了節點間的通信質量。因此在圖8中，此區間內網絡的平均端到端時延的增大情況也存在放緩的現象。

圖8 中可以看到，在節點數目較少時與其他2 種算法的時延差異不大，但隨著節點數目增多，原始OLSR 的平均端到端時延明顯大幅度增加，TA-OLSR 和OLSR Med+2 種算法的時延表現都優于原始算法。在節點個數為100 個時，TAOLSR 的平均端到端時延相比于OLSR Med+降低了3.93%，相較于原始OLSR 降低了31.22%。

圖9、圖10 分別是在無人飛行器節點速度影響下3 種算法的平均包投遞率和控制消息占比情況的對比圖，其中無人飛行器節點數目為50 個。

圖9 節點速度影響下的平均包投遞率

圖10 不同的速度網絡中控制消息占比變化

隨著無人飛行器速度增大，節點間動態差異增大，原始OLSR 的丟包率逐步升高，這正是高動態性對于路由性能的影響。但TA-OLSR 在高動態的復雜環境中網絡數據接收依舊良好，在無人飛行器速度40 m/s 場景中的數據包投遞率比OLAR Med+提升了17.02%，比原始OLSR 提升34.14%，這是由于在TA-OLSR 中感應到鏈路中斷情況增加時，HELLO 消息的廣播周期縮短，增加了鄰居感應力度，重建鄰居表用于路由更新，同時MPR 集合選擇了更穩定的節點進行消息轉發，減少了由于路由變更不及時導致的丟包情況。在探測網絡拓撲相對穩定時減少HELLO 等控制消息包的廣播，此時網絡路由變化情況少，相對少的HELLO 探測并不會增大丟包率，同時可以減少控制類信息在網絡中的傳播，使得消息冗余度降低，不僅能很好地節省網絡資源，同時也有效降低了冗余信息對于網絡吞吐量的影響。

圖10 中是利用控制消息長度與接收消息長度的比率衡量控制消息的開銷，當包投遞率一定時，網絡開銷越低，網絡性能更好。在節點速度為20 m/s 時TA-OLSR 的控制消息占比相較于OLSR Med+降低了19.08%，相較于原始OLSR 降低了19.90%。TA-OLSR 可以在整體動態較小時有效節省不必要的控制開銷，在節點速度增大后節省開銷的程度逐漸降低，但仍優于原始OLSR。節點最大速度為40 m/s 時，TA-OLSR 的控制消息占比相較于原始OLSR 降低了8.51%。

4 結束語

本文針對路由算法與復雜任務環境中的拓撲變化動態耦合度低導致丟包率高、冗余信息過多的問題，提出了面向任務的無人飛行器自組網的TA-OLSR 協議，通過每個任務聯盟內部的拓撲自適應實現宏觀上整個無人飛行器集群的任務自適應。仿真結果表明TA-OLSR 算法能有效改善網絡穩定性、增大網絡包投遞率與網絡吞吐量，能夠至上而下的依據無人飛行器集群任務拓撲完成路由自適應調整，實現網絡的適應性節能。

當前研究主要利用不同任務聯盟內無人飛行器間移動特征的相似度來衡量網絡拓撲的變化，從而實現路由算法在整體無人飛行器集群的任務自適應。后續研究將結合不同任務所需性能指標的差異性，進一步充實任務信息，使得路由協議在多種無人飛行器集群任務中達到更好的自適應性。本文研究了聯盟內的通信路由情況，可以進一步研究如何優化任務聯盟間的通信，使整個無人飛行器集群的通信體系更加完整。后續仿真實驗還將考慮構造多任務變化場景來進一步模擬復雜無人飛行器集群的動態任務環境，更好地研究無人飛行器集群自組網的各項數據指標。