高效的多無人直升機(jī)自組織網(wǎng)絡(luò)路由算法研究

梁 濤,伍心皓

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

0 引言

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

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

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

本文針對多無人直升機(jī)自組織網(wǎng)絡(luò)的拓?fù)渥兓?，頻繁中斷連接的特點，結(jié)合DTN路由機(jī)制與基于地理信息的路由方法，提出了一種高效的多無人直升機(jī)自組織網(wǎng)絡(luò)路由算法。仿真試驗結(jié)果表明所提出的算法都能很好地適應(yīng)多無人直升機(jī)自組織網(wǎng)絡(luò)的間歇連接性特征，在投遞率方面優(yōu)于現(xiàn)有的算法。

1 網(wǎng)絡(luò)路由算法

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

1.1 網(wǎng)絡(luò)模型

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

1)實鏈路

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

(1)

式中：Mdata代表需要被傳輸?shù)臄?shù)據(jù)的大小，s(ni,nj)代表節(jié)點ni與nj之間的吞吐量。在連通的網(wǎng)絡(luò)中進(jìn)行路由轉(zhuǎn)發(fā)時，加權(quán)圖被用于計算消息傳輸?shù)淖疃搪窂剑撀窂骄哂凶钚〉膫鬏斞舆t。

2)虛鏈路

(2)

(3)

1.2 DTNclose算法

為了解決現(xiàn)有算法存在的問題，本文提出基于位置預(yù)測的DTNclose算法。因為每個無人直升機(jī)當(dāng)前的位置、方向和速度都是可用的，所以本文對無人直升機(jī)的運動進(jìn)行預(yù)測，得到時間F后無人直升機(jī)的位置，根據(jù)該位置信息，選擇新的下一跳節(jié)點，被選擇的節(jié)點應(yīng)當(dāng)是未來離目標(biāo)更近的無人直升機(jī)。由此，可以有效避免被選擇的無人直升機(jī)在接收到數(shù)據(jù)后朝著遠(yuǎn)離目標(biāo)的方向運動，從而增加網(wǎng)絡(luò)傳輸?shù)男省?/p>

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

dm(S,t+F)

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

(4)

式中，t為當(dāng)前時間，F(xiàn)為預(yù)測的時間間隔，dm(S,t+F)為時間t+F時節(jié)點m和目標(biāo)S的距離，arg min保證選擇的節(jié)點m為時間t+F時集合M中距離目標(biāo)S最近的一個，同時，dm(S,t+F)

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

1.3 基于DTNclose的改進(jìn)算法DTNmul

DTNgeo與DTNclose都是單副本傳輸。每個消息網(wǎng)絡(luò)中都只有一個副本，一旦數(shù)據(jù)包傳輸出錯，或者某個消息副本傳輸?shù)奶鴶?shù)過多且仍未到達(dá)目的地，都有可能導(dǎo)致該副本被丟棄，從而影響無人直升機(jī)數(shù)據(jù)傳輸?shù)男Ч?/p>

為了解決該問題，提出一種基于多消息拷貝的DTNmul算法。DTNmul算法在DTNclose算法基礎(chǔ)上借鑒Epidemic算法的泛洪傳播方式，其路由選擇方式與DTNclose一致。區(qū)別在于DTNclose算法中每個無人直升機(jī)在發(fā)送完一個數(shù)據(jù)包后，不會繼續(xù)保存這個數(shù)據(jù)包，而DTNmul對這一點進(jìn)行優(yōu)化，無人直升機(jī)可以繼續(xù)保存已經(jīng)發(fā)送的數(shù)據(jù)包。為了盡可能減少網(wǎng)絡(luò)的負(fù)載，DTNmul算法會在某個消息到達(dá)消息的最終目的節(jié)點后，刪除這個消息在整個網(wǎng)絡(luò)中的副本，從此該消息只有在目標(biāo)節(jié)點中才存在唯一的副本，因此可以大量減少網(wǎng)絡(luò)的負(fù)載。

2 試驗

本文在ONE仿真平臺中實現(xiàn)DTNgeo、DTNclose和DTNmul三個算法，比較三個算法的運行結(jié)果。仿真試驗的相關(guān)參數(shù)設(shè)置見表1。

表1 仿真試驗相關(guān)參數(shù)

首先，設(shè)置DTNclose的預(yù)測時間F=4s，在ONE平臺完成仿真試驗后，可以生成一個報告文件MessageDeliveryReport.txt。該文件記錄了從仿真開始到仿真結(jié)束的全網(wǎng)絡(luò)數(shù)據(jù)交付比，因此可以得到折線圖(如圖1)，橫坐標(biāo)為仿真時間，縱坐標(biāo)為該時間整個無人直升機(jī)網(wǎng)絡(luò)數(shù)據(jù)包的交付比，即仿真時間內(nèi)成功傳輸?shù)侥康墓?jié)點的數(shù)據(jù)包的數(shù)量占這段時間全部創(chuàng)建數(shù)據(jù)包的比率。

圖1 三種路由算法交付比

由圖1可知，總體的交付比DTNclose>DTNmul>DTNgeo，三種算法在高峰期都擁有95%以上的交付比，可見折線起伏較大。這是由于數(shù)據(jù)包傳輸?shù)降孛嬲局荒芡ㄟ^擺渡無人直升機(jī)，所以當(dāng)擺渡無人直升機(jī)進(jìn)入地面站的通信范圍內(nèi)，會有一大批數(shù)據(jù)包傳輸?shù)侥康牡?，交付比會大幅上升；反之，?dāng)沒有擺渡無人直升機(jī)在地面站的通信范圍內(nèi)時，不會有數(shù)據(jù)包到達(dá)目的地，但是各個無人直升機(jī)還在產(chǎn)生數(shù)據(jù)包，因此交付比會持續(xù)下降，直到下一個擺渡無人直升機(jī)進(jìn)入地面站的通信范圍。

5 結(jié)論

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