一種基于OLSR 的無人機網絡適用路由算法

周長家，周建國

（武漢大學 電子信息學院，武漢 430072）

0 概述

近年來，無人機在搶險救災［1］、應急通信［2］、目標偵查［3］、城市交通管理［4］、中繼網絡［5］等領域得到廣泛應用。與傳統的移動自組織網絡（Mobile Ad-hoc Network，MANET）［6］相比，無人機自組網（Flying Ad-hoc Network，FANET）［7］的網絡動態性更強、鏈路變化更為劇烈且網絡穩定性更差［8-9］。此外，無人機集群的狀態存在編隊飛行和自主飛行2 種狀態，在不同的狀態下，FANET 會表現出不同的網絡特性。為了提升FANET 的網絡性能，確保較低的端到端延遲以及較高的數據包投遞率，必須針對FANET的網絡特點設計與之匹配的路由協議。

本文在優化鏈路狀態路由（Optimized Link State Routing，OLSR）［10］協議的基礎上，提出一種無人機網絡適用路由（UAV-OLSR）算法。在算法設計過程中考慮無人機集群的飛行狀態，選擇高質量的節點作為多點中繼（MPR）節點，同時引入多徑的思想，通過路徑評估選擇較優路徑進行當前數據包轉發。在數據轉發過程中，采用備選轉發機制來確保數據包能夠被正確投遞。

1 相關研究

針對FANET 的路由研究主要有2 個方向：一是對傳統MANET 路由進行改進，使其適合于FANET的網絡特性；二是結合實際應用場景的特性，針對FANET 設計一種全新的路由協議。

YI 等［11］介紹一種具備移動和負載感知的增強OLSR 路由協議（ML-OLSR），通過獲取UAV 節點的地理位置計算節點的穩定性，實現移動感知，并通過負載感知算法實現負載均衡，最后將移動感知用于MPR 選擇，將負載感知用于路徑選擇，仿真結果表明，ML-OLSR 可以有效提高數據包投遞率并降低平均端到端延遲，但是，其對比對象僅為OLSR，過于單一。OUBBATI 等［12］設計一種FANET 環境下的節能路由ECaD，其采用與AODV 類似的路由發現方法，NS2 下的仿真結果表明，ECaD 能夠有效均衡網絡中節點的能量消耗，但是，其在平均端到端延遲方面表現欠佳。

PI 等［13］提出一種全新的分布式路由算法RBDR，其主要創新點在于為每個節點定義信譽度的概念，該路由算法能夠有效降低無人機網絡節點的能量和存儲空間消耗，并能適應網絡的高動態性，但是，RBDR 降低能耗的代價是數據包平均傳輸延遲有所增加。LADTR［14］是針對災害環境下的無人機網絡設計的一種路由協議，該協議中引入了輪渡無人機，并結合定位輔助轉發與存儲轉發技術，可以有效降低端到端延遲并提高數據包投遞率，但是，輪渡無人機的負載較大，會使得網絡生存時間縮短。文獻［15］將無人機的放置與預測性路由相結合，從而提升網絡容量，但其僅適用于無人機運動軌跡可控的情況。ECoR［16］是一種能量感知路由，可以根據無人機節點的剩余能量進行任務卸載，但其重點關注延長網絡的生存時間，沒有考慮如何提升網絡性能。

上述研究工作多是針對FANET 的某一特點進行設計，具有一定的局限性。本文提出的路由策略綜合考慮無人機節點耗能、網絡服務質量（QoS）［17］等因素，進而實現較優的數據路由。

2 UAV-OLSR 算法設計

OLSR 的核心在于MPR，通過MPR 機制能夠有效降低路由開銷。OLSR 通過HELLO 消息和TC 消息感知全網拓撲，每個節點都維護一個鄰居鏈路集合Ls、一跳鄰居集合N1_s、兩跳鄰居集合N2_s以及網絡拓撲集合Ts。

UAV-OLSR 基于OLSR 設計實現，路由設計包含無人機集群狀態感知、MPR 節點選取、多徑路由設計以及數據轉發策略4 個部分。

2.1 無人機集群狀態感知

本文考慮無人機集群編隊飛行以及自主飛行2 種狀態：對于編隊飛行狀態，認為無人機集群的節點保持相對靜止狀態，網絡拓撲結構可認為保持不變；對于自主飛行狀態，無人機集群中的每個節點都有隨機的移動方向和速度，網絡的拓撲結構變化較為劇烈。

網絡的拓撲變化情況能夠直觀反映無人機集群的不同飛行狀態，因此，可以通過網絡的拓撲變化情況估計無人機集群的飛行狀態。UAV-OLSR 通過N1_s與Ts的變化情況共同感知無人機集群的飛行狀態，前者表示為Nc，后者表示為Tc，相關定義如下：

1）Nc：節點在當前HELLO 消息間隔時間內新增或刪除的一跳鄰居節點數目，計算如式（1）所示：

其中：nadded、nlost分別代表當前HELLO 消息周期間隔內新增、刪除的一跳鄰居節點數目。

2）Tc：節點在當前TC 消息間隔時間內新增或刪除的網絡拓撲鏈接數目，計算如式（2）所示：

其中：tadded代表當前TC 消息周期間隔內新增的拓撲鏈接數目；tlost代表當前TC 消息周期間隔內刪除的拓撲鏈接數目。

用符號“0”代表編隊飛行狀態，符號“1”代表自主飛行狀態，則無人機集群的飛行狀態通過式（3）確定。

其中：nnb為節點當、前的鄰居節點個數；ntp為節點當前拓撲集合中的元素個數；(i=1，2，3，4)為閾值。

S的取值進一步影響網絡中路由控制消息的發送頻率，具體地，UAV-OLSR 會根據S的值改變HELLO 消息和TC 消息的發送間隔，設置方式如式（4）所示：

其中：Ih_q、Ih_s、It_q、It_s為預設的變量值。改變消息發送間隔的同時需要改變消息的有效時間，具體地，Vhello=3Hivl，Vtc=3Tivl。

當無人機集群處于自主飛行狀態時，節點會保持較高的HELLO 消息和TC 消息發送頻率，從而確保網絡拓撲能夠及時更新；反之，節點會降低HELLO 消息和TC 消息的發送頻率，從而降低自身能耗并減少路由開銷。

2.2 MPR 節點選取

在OLSR 路由協議中，MPR 節點選取將直接影響路由開銷，并在較大程度上影響網絡路由的可靠性。因此，為了建立可靠的端到端路由，確保網絡性能，必須選擇合適的MPR 節點。在FANET 中，節點的高動態性會使得鏈路的通斷變得更加頻繁，因此，在MPR 節點的選取過程中，應考慮節點的穩定性。此外，無人機節點的能量通常較為有限［18］，為了平衡網絡中的能量消耗，在進行MPR 節點選取時，應考慮節點的能量因素。

為實現可靠的MPR 節點選取，在UAV-OLSR 中定義如下3 個參量：

1）鏈路變化率（Lcr），計算如式（5）所示：

其中：Nc的定義如式（1）所示；nnb_c為當前一跳鄰居節點的個數。

2）剩余能量百分比（Pre），計算如式（6）所示：

其中：pc為當前剩余能量；pt為節點初始能量。

3）節點中心度（Rc），計算如式（7）所示：

其中：nnb_c（n2nb_c）為當前的一跳（兩跳）鄰居節點數目。

進一步地，對上述3 個變量進行非線性映射處理，得到可用于評估節點質量的參數（i=1，2，3）。

1）對于Lcr，映射方法為：=min{Lcr，1}。

2）對于Pre，其數值越大，代表節點的能量越充足，且當其數值小到一定程度時，對網絡的影響會更加明顯，因此，采用如下的方式進行映射處理：=1-(1-Pre)3。

3）對于Rc，其值越小，代表節點所處的位置越接近網絡中心，節點的評分也就越高，因此，使用雙曲正切函數進行映射處理：=1-tanh(Rc)。

最后對各個指標進行加權求和，得到節點質量的評估結果EEP。本文采用層次分析法（AHP）［19］進行加權系數確定。在本文方案中，認為3 個參數的重要性排序為：。構造判斷矩陣A=(aij)3×3，其 中：aii=1(i=1，2，3)；a12=2；a13=3；a23=2；aij×aij=1。矩陣A的最大特征值所對應的特征向量（歸一化值）即為以及的加權系數，得到EEP的表達式如下：

在改進的MPR 選擇算法中，不再使用節點意愿度（willingness）的概念，而是使用節點質量評分EEP作為相應的標準，算法流程與標準OLSR 中的選取算法類似。

2.3 多徑路由設計

在FANET 中，高速移動的節點會降低路由的可靠性，因此，可建立多條從源到達目的端的路徑，以降低鏈路不穩定所帶來的影響。同時制定合適的路由度量標準，選擇較優的一條路徑作為當前數據包的轉發路徑。

2.3.1 路徑度量

在標準OLSR 中，通過數據包從源到達目的端所需要進行的轉發次數來對路徑進行度量，但在部分情況下最少的轉發次數并不是最佳的路徑選擇。針對該問題，有研究人員選擇期望傳輸次數（ETX）［20］、節點密度參數和干擾率［21］、能源效率度量標準（RESDN）［22］等作為路徑度量標準，以選擇較優的路徑進行數據轉發。

在UAV-OLSR 中，本文考慮影響路徑質量的多個指標，并綜合這些指標對路徑的質量進行定量描述。其中，考慮的因素包括路徑上節點的剩余能量占比（Pre）、節點的對稱一跳鄰居節點比例（Rs_n）、節點的質量評分（EEP）、節點的可用緩沖區比例（Rr_b）以及數據轉發所需跳數（HHOP）。部分參量通過在HELLO消息包和TC消息包中添加額外的字段（Pre（16 bit）、Rs_n（8 bit）、EEP（8 bit）、Rr_b（8 bit））實現全網感知。

Pre和EEP的定義分別如式（6）和式（8）所示，HHOP是指數據從源到達目的端所需要的轉發次數。Rs_n定義為節點的對稱一跳鄰居節點數量與節點的一跳鄰居數量集合中節點數量的比值：

其中：nsym為對稱一跳鄰居節點數量；nall為一跳鄰居節點總數量。

Rr_b定義為緩沖區可用的隊列長度與初始化的緩沖區隊列長度最大值的比值：

其中：qused是當前緩沖區中排隊等候的數據包數量；qall是初始化的緩沖區隊列長度最大值。

此外，在從源到目的端的路徑上，本文對除去源節點和目的節點的其余節點的Rs_n、Rr_b、Pre、EEP進行分析。對于Rr_b、Pre和EEP，取其最小值作為整條路徑的度量參數。對于Rs_n，將路徑上節點Rs_n值的乘積作為路徑度量參數。最后，分析相關參數對路徑質量的影響類型，并將它們分為加性影響和乘性影響兩類。路徑度量準則Rmeaure定義如下：

其中：αi(i=1，2，3，4)為加權系數，通過層次分析法確定；表示對所有的非源節點和目的節點n(i)取x的最小值；表示所有非源節點和目的節點的x連乘。

2.3.2 多徑計算

在UAV-OLSR 中，針對目的節點與源節點的距離制定了不同的多路徑計算策略，并采用按需計算的方法進行多路徑計算。具體地，將目的節點分為一跳可達節點、兩跳可達節點、其余類型節點三類。

對于一跳可達節點，為其建立最多2 條路徑：r1為從源到目的地的直接路徑；r2為經過一次中轉的路徑，且中轉節點也為源節點的鄰居節點。需要注意的是，r2存在的條件為目的節點既是源節點的一跳鄰居節點也是其兩跳鄰居節點。

對于兩跳可達節點，為其建立不超過3 條路徑：r1和r2都為最短路徑（轉發次數最少，下同）；r3為次短路徑（路徑長度為最短路徑長度加1）。兩跳可達節點多徑計算方法描述如算法1 所示。

路徑a和b的重復度定義如下：

其中：M=h為路徑上的節點個數（不含源節點和目的節點）；E為長度為h的數組，若路徑a與b中第j個節點一致（不含源節點和目的節點），則E中位置j處的元素為1，反之為0；n(i)表示E中連續i個1 出現的次數，例如E=[1，1，1，0，1，0]，則n(1)=4，n(2)=2，n(3)=1，n(4)=n(5)=n(6)=0。

2.3.3 多徑維護

UAV-OLSR 的多徑路由采用按需計算，因此僅對多徑路由表中已有的路由進行維護。為每組路徑（s->d）定義一個有效時間t，每隔一個HELLO 周期對t進行更新。若在當前HELLO 周期內該組路徑被使用，則t設置為最大值；反之，將t減1。若t≤0，則該組路徑記為失效，從路由表中將其刪除。

當前節點接收到HELLO 消息或TC 消息后，將對路由表進行更新。首先檢查每組路由的有效時間t，若t≤0，則將該組路徑刪除；反之，對路由項進行更新，每組路徑的更新步驟如下：

1）計算到目的節點的最短路徑所需跳數，如果該值與當前路由表中該組路由的最少跳數一致，則進入第2 步，反之進入第4 步。

2）檢查路徑的連通性，如果路徑仍連通，則進入第3 步，反之進入第4 步。

3）計算該組路徑中每條路徑的度量分數，如果其最大值小于閾值φ，則進入第4 步，反之進入第5 步。

4）按照2.3.2 節所述方法重新計算到達目的節點的多條路徑并選擇度量分數較大的路徑作為備選。

5）對每條路徑的度量分數進行更新。

2.4 數據轉發策略

在UAV-OLSR 中，多徑路由僅在源節點進行計算，且路徑信息包含在數據包的IP 頭部，中間節點根據IP頭部的路徑信息進行數據轉發。由于網絡拓撲更新存在延遲，源節點計算的路徑可能存在部分無效的情況。為解決該問題，本文在UAV-OLSR 中保留了OLSR 原有的路由表，若中間節點檢測到數據包頭部的路徑信息無效，則中間節點對數據包頭部信息進行修改，并將數據包按照標準OLSR 中的轉發方式進行轉發。

3 仿真分析

為驗證UAV-OLSR 的有效性，在NS2 中進行網絡仿真測試，并將UAV-OLSR 與AODV、OLSR 進行比較。對于自組織網絡而言，其性能參數包括數據包投遞率、端到端延遲、端到端吞吐量等，由于無人機節點的能量高度受限，因此網絡生存時間也是FANET 需要考慮的關鍵因素。

在仿真測試中，主要分析FANET 的數據包投遞率、平均數據包傳輸延遲和網絡節點剩余能量。在數據包大小已知的情況下，數據包投遞率和平均傳輸延遲也可以間接反映網絡吞吐量，網絡節點剩余能量最小值是指某一時刻網絡中所有節點的剩余能量最小值，該值越大，代表網絡的生存時間越長。仿真測試部分關鍵參數如表1 所示。

表1 部分仿真參數Table 1 Some simulation parameters

具體地，建立一個固定大小的仿真區域，隨機初始化無人機節點的位置，并讓每個節點隨機移動，在網絡中隨機生成固定數目的數據流（cbr 流），按照預設的仿真時間進行網絡仿真，并對仿真得到的數據進行處理，進而分析網絡的相關性能。

圖1 所示為某時刻的網絡拓撲，圖中不同的線條箭頭代表不同的數據流（僅列出部分）。網絡節點的移動具有較大的隨機性，因此，網絡拓撲會呈現出高度的動態性。

圖1 網絡拓撲示意圖Fig.1 Schematic diagram of network topology

在仿真過程中，節點剩余能量百分比的最小值隨時間的變化情況如圖2 所示。在仿真初始階段，由于各節點剩余能量的百分比都較大，能量均衡效果并不明顯，因此，不同路由協議的節點剩余能量之間差異較小。隨著仿真的進行，不同路由協議的能量均衡效果差異逐漸體現出來，具體表現為曲線在垂直方向上的間隔逐漸擴大，由于OLSR 接收到HELLO 消息或者TC消息后都會進行路由更新，因此其節點間的能量均衡效果優于AODV，而UAV-OLSR 采用了能量均衡設計，其性能表現更優于OLSR。

圖2 節點剩余能量百分比的最小值對比Fig.2 Comparison of minimum residual energy percentage of nodes

圖3 和圖4 所示分別為數據包的平均傳輸延遲和丟包率情況，曲線上點的縱坐標代表以當前橫坐標為中心的一個時間區間內的統計平均值。從圖3 可以看出，在仿真起始階段，因為網絡中擁塞現象不明顯，所以3 種路由協議的數據包平均延遲基本一致，在網絡仿真過程中，OLSR 路由協議的數據包平均傳輸延遲在多數情況下比AODV 路由協議低，而UAV-OLSR 協議的數據包平均傳輸延遲始終低于OLSR 和AODV。從圖4 可以看出，在仿真起始階段，3 種路由協議的性能差異并不明顯，在整個仿真過程中，OLSR 與AODV 的數據包投遞率差異不明顯，而UAV-OLSR 的數據包投遞率明顯高于OLSR 與AODV。

圖3 數據包平均傳輸延遲對比Fig.3 Comparison of average packet transmission delay

圖4 數據包投遞率對比Fig.4 Comparison of packet delivery rate

4 結束語

本文針對無人機自組網的高動態特性以及節點能量高度受限的特點，提出一種基于OLSR 的無人機網絡適用路由協議UAV-OLSR。通過無人機集群狀態感知機制調整路由協議的相關參數，進而適應無人機集群的狀態變化。根據多維度的節點質量評估和路徑評估機制選擇可靠的中間節點進行數據轉發。使用自定義的多路徑計算方法計算從源到達目的端的多條路徑，并結合路徑評估和數據轉發策略選擇較優的路徑進行數據轉發。實驗結果表明，與OLSR、AODV 等傳統移動自組網路由協議相比，UAV-OLSR 能夠提高數據包投遞率，降低數據包延遲，從而實現較好的網絡能量均衡。下一步將在UAV-OLSR 的基礎上引進節點休眠機制，以延長網絡的生存時間。