高效的多無人直升機自組織網絡路由算法研究

梁 濤,伍心皓

(1.海軍裝備部裝備采購中心，北京 100071；2.中國直升機設計研究所，江西 景德鎮 333001)

0 引言

隨著電子技術、傳感器技術和通信技術的不斷發展，無人直升機系統的性能也取得了長足的進步，現代無人直升機可以進行自主飛行，也可以由工作人員進行遠程操作控制。由于其功能較多、飛行動作靈活、安裝容易和操作簡單等優點，無人直升機逐漸應用于各種任務，例如搜索救援、邊界監視、野火監視、風力估計、災難監測、遙感和交通監控等任務。

由于無人直升機網絡拓撲的頻繁變化、無人直升機的快速移動和無線鏈路質量的不穩定，現有的移動自組織網絡路由不適用于無人直升機網絡。文獻[1]在兩個微型無人機和地面站的網絡中評估OLSR協議，發現OLSR路由協議無法應對快速變化的拓撲結構。文獻[2]提出基于BATMAN的路由，結果顯示由于其收斂時間較長，拓撲結構的頻繁變化會損害該算法的效率。相比傳統的先應式路由和反應式路由，基于地理信息的路由無需路由表，也不需要反復查找最短路徑，因此其耗費較低。對于地面車輛，DTNgeo[3]算法充分利用了導航信息和存儲-攜帶-運輸的技術，該方法通過引入擺渡無人機提高路由效率。 LAROD是一種基于位置的飛行器路由算法[4]，將地理信息路由與存儲-攜帶-轉發機制相結合，在較低的開銷下確保了與Epedemic路由相當的分組投遞率。在稀疏節點網絡中基于地理信息路由轉發的性能結果證實：單純的基于地理信息的貪婪轉發方案通常只適用于非關鍵應用[5]。因此，將基于地理信息轉發與其他機制結合是更佳的途徑。

文獻[6]對無人機的移動軌跡進行預測，利用該信息進行數據保持或數據發送路由選擇，相比AODV和LAR算法，提升了吞吐量。完整軌跡感知路由的主要優點是多跳路徑的優化，其缺點在于在整個任務期間需要知道所有無人機的路徑。

本文針對多無人直升機自組織網絡的拓撲變化快，頻繁中斷連接的特點，結合DTN路由機制與基于地理信息的路由方法，提出了一種高效的多無人直升機自組織網絡路由算法。仿真試驗結果表明所提出的算法都能很好地適應多無人直升機自組織網絡的間歇連接性特征，在投遞率方面優于現有的算法。

1 網絡路由算法

多無人直升機自組織網絡與其他移動自組織網絡不同的是，無人直升機節點是飛行的機器，而且它們的移動與動作具有高度的任務驅動性。而且，每個無人直升機的地理位置通常是已知的。本節首先給出多無人機直升機自組織網絡模型，在該模型的基礎上提出多無人直升機自組織網絡路由算法。

1.1 網絡模型

本文引入兩種鏈路：“實鏈路(real links)”和“虛鏈路(virtual links)”，其中實鏈路代表普通傳輸數據的無線鏈路，虛鏈路則為一個假設存在的鏈路，代表在數據傳輸前需要被攜帶運輸的鏈路。

1)實鏈路

當某兩個節點ni和nj的地理距離為d，同時兩個節點經由實鏈路連接，D為每個節點的通信傳輸距離，那么d≤D。在加權圖G中，wij代表這條鏈路的邊的權值，其實際意義為這條鏈路上的ni和nj之間的預期數據傳輸延遲：

(1)

式中：Mdata代表需要被傳輸的數據的大小，s(ni,nj)代表節點ni與nj之間的吞吐量。在連通的網絡中進行路由轉發時，加權圖被用于計算消息傳輸的最短路徑，該路徑具有最小的傳輸延遲。

2)虛鏈路

(2)

(3)

1.2 DTNclose算法

為了解決現有算法存在的問題，本文提出基于位置預測的DTNclose算法。因為每個無人直升機當前的位置、方向和速度都是可用的，所以本文對無人直升機的運動進行預測，得到時間F后無人直升機的位置，根據該位置信息，選擇新的下一跳節點，被選擇的節點應當是未來離目標更近的無人直升機。由此，可以有效避免被選擇的無人直升機在接收到數據后朝著遠離目標的方向運動，從而增加網絡傳輸的效率。

假設某個無人直升機標記為n，那么在整個無人直升機網絡中有部分節點與無人直升機n存在端到端鏈路，即這部分無人直升機可以通過中繼節點和無人直升機n連通。將這部分無人直升機節點的集合標記為M，對于DTNclose算法而言，選出的下一跳節點m必須滿足以下條件：

dm(S,t+F)

arg mindm(S,t+F),m∈M.

(4)

式中，t為當前時間，F為預測的時間間隔，dm(S,t+F)為時間t+F時節點m和目標S的距離，arg min保證選擇的節點m為時間t+F時集合M中距離目標S最近的一個，同時，dm(S,t+F)

在完成預測之后，使用得到的位置信息計算t+F時刻集合M中各個節點以及當前節點n到目標節點的虛鏈路權值，找到其中權值最小的一個無人直升機節點。如果該節點為當前節點n，則不進行數據傳輸，無人直升機節點n將存儲該數據并繼續攜帶飛行；否則，當前節點n將開始向被選擇的無人直升機節點傳輸數據，被選擇的無人直升機節點即為下一跳。

1.3 基于DTNclose的改進算法DTNmul

DTNgeo與DTNclose都是單副本傳輸。每個消息網絡中都只有一個副本，一旦數據包傳輸出錯，或者某個消息副本傳輸的跳數過多且仍未到達目的地，都有可能導致該副本被丟棄，從而影響無人直升機數據傳輸的效果。

為了解決該問題，提出一種基于多消息拷貝的DTNmul算法。DTNmul算法在DTNclose算法基礎上借鑒Epidemic算法的泛洪傳播方式，其路由選擇方式與DTNclose一致。區別在于DTNclose算法中每個無人直升機在發送完一個數據包后，不會繼續保存這個數據包，而DTNmul對這一點進行優化，無人直升機可以繼續保存已經發送的數據包。為了盡可能減少網絡的負載，DTNmul算法會在某個消息到達消息的最終目的節點后，刪除這個消息在整個網絡中的副本，從此該消息只有在目標節點中才存在唯一的副本，因此可以大量減少網絡的負載。

2 試驗

本文在ONE仿真平臺中實現DTNgeo、DTNclose和DTNmul三個算法，比較三個算法的運行結果。仿真試驗的相關參數設置見表1。

表1 仿真試驗相關參數

首先，設置DTNclose的預測時間F=4s，在ONE平臺完成仿真試驗后，可以生成一個報告文件MessageDeliveryReport.txt。該文件記錄了從仿真開始到仿真結束的全網絡數據交付比，因此可以得到折線圖(如圖1)，橫坐標為仿真時間，縱坐標為該時間整個無人直升機網絡數據包的交付比，即仿真時間內成功傳輸到目的節點的數據包的數量占這段時間全部創建數據包的比率。

圖1 三種路由算法交付比

由圖1可知，總體的交付比DTNclose>DTNmul>DTNgeo，三種算法在高峰期都擁有95%以上的交付比，可見折線起伏較大。這是由于數據包傳輸到地面站只能通過擺渡無人直升機，所以當擺渡無人直升機進入地面站的通信范圍內，會有一大批數據包傳輸到目的地，交付比會大幅上升；反之，當沒有擺渡無人直升機在地面站的通信范圍內時，不會有數據包到達目的地，但是各個無人直升機還在產生數據包，因此交付比會持續下降，直到下一個擺渡無人直升機進入地面站的通信范圍。

5 結論

為了設計實現適合多無人直升機自組織網絡的路由算法，本文利用無人直升機的位置信息和移動信息，提出了一種高效的多無人直升機自組織網絡路由算法。該算法結合了地理信息路由和延遲容忍網絡路由，能同時處理存在端到端鏈路、鏈路連接中斷這兩種情況；利用無人直升機的位置信息和移動信息，對無人直升機未來的位置進行預測，以選擇更優的路徑進行消息發送；考慮到多無人直升機網絡頻繁中斷的特點，提出了多副本消息傳輸的策略。仿真試驗結果表明，兩種路由算法都能很好地適應多無人直升機自組織網絡的間歇連接性特征，同時，對該算法的兩種改進能有效提升算法性能。