周長家，周建國

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

0 概述

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

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

1 相關研究

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

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

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

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

2 UAV-OLSR 算法設計

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

UAV-OLSR 基于OLSR 設計實現(xiàn)，路由設計包含無人機集群狀態(tài)感知、MPR 節(jié)點選取、多徑路由設計以及數(shù)據(jù)轉發(fā)策略4 個部分。

2.1 無人機集群狀態(tài)感知

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

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

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

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

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

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

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

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

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

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

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

2.2 MPR 節(jié)點選取

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

為實現(xiàn)可靠的MPR 節(jié)點選取，在UAV-OLSR 中定義如下3 個參量：

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

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

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

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

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

其中：nnb_c（n2nb_c）為當前的一跳（兩跳）鄰居節(jié)點數(shù)目。

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

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

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

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

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

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

2.3 多徑路由設計

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

2.3.1 路徑度量

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

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

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

其中：nsym為對稱一跳鄰居節(jié)點數(shù)量；nall為一跳鄰居節(jié)點總數(shù)量。

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

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

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

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

2.3.2 多徑計算

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

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

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

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

其中：M=h為路徑上的節(jié)點個數(shù)（不含源節(jié)點和目的節(jié)點）；E為長度為h的數(shù)組，若路徑a與b中第j個節(jié)點一致（不含源節(jié)點和目的節(jié)點），則E中位置j處的元素為1，反之為0；n(i)表示E中連續(xù)i個1 出現(xiàn)的次數(shù)，例如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，則該組路徑記為失效，從路由表中將其刪除。

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

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

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

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

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

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

2.4 數(shù)據(jù)轉發(fā)策略

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

3 仿真分析

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

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

表1 部分仿真參數(shù)Table 1 Some simulation parameters

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

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

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

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

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

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

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

圖4 數(shù)據(jù)包投遞率對比Fig.4 Comparison of packet delivery rate

4 結束語

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