張 倩，胡曦月，劉 穎

(武警工程大學(xué) 信息工程學(xué)院，西安 710086)

0 引 言

無人機(jī)自組網(wǎng)是小型無人機(jī)集群應(yīng)用的基礎(chǔ)，其性能決定了無人機(jī)集群任務(wù)完成效果。無人機(jī)自組網(wǎng)(Unmanned Aeronautical Ad Hoc Network，UAANET)作為移動自組網(wǎng)(Mobile Ad Hoc Network，MANET)的一個特例，與傳統(tǒng)MANET相比，具有節(jié)點移動性強(qiáng)、拓?fù)渥兓俣瓤?、能量受限、三維空間移動等特點[1-3]。其中，無人機(jī)自組網(wǎng)中的路由協(xié)議是網(wǎng)絡(luò)的重要組成要素，而路由判據(jù)是衡量路由協(xié)議性能指標(biāo)的重要依據(jù)，在相當(dāng)程度上影響著無人機(jī)自組網(wǎng)數(shù)據(jù)傳輸?shù)男阅埽彩羌褐懈鞒蓡T之間協(xié)調(diào)完成各項任務(wù)的基礎(chǔ)[4-5]。

當(dāng)前，絕大多數(shù)網(wǎng)絡(luò)路由算法是針對MANET設(shè)計的，這些協(xié)議都屬于主動式路由協(xié)議，即已經(jīng)提前根據(jù)判據(jù)計算出了路由表。但這種方式無法適應(yīng)無人機(jī)自組網(wǎng)的快速拓?fù)渥兓?、能量受限等特點，因此，必須設(shè)計能夠適應(yīng)UAANET網(wǎng)絡(luò)拓?fù)淇焖僮兓穆酚蓞f(xié)議。隨著定位技術(shù)的飛速發(fā)展以及終端設(shè)備的普及，基于地理位置信息的路由協(xié)議因簡單高效，在無人機(jī)自組網(wǎng)中擁有廣闊的應(yīng)用前景[6]。以經(jīng)典的航空路由協(xié)議(The Aeronautical Routing Protocol，AeroRP)為例，它是一種專為高度動態(tài)機(jī)載網(wǎng)絡(luò)設(shè)計的、適用于特定領(lǐng)域的路由協(xié)議[7]。AeroRP最早在文獻(xiàn)[8]中提出，后來在ns-3網(wǎng)絡(luò)模擬器中進(jìn)行了建模和分析，結(jié)果表明其在吞吐量和分組交付率方面優(yōu)于傳統(tǒng)的MANET路由協(xié)議[9-11]。但是AeroRP路由協(xié)議針對的是大型動態(tài)機(jī)載網(wǎng)絡(luò)，沒有考慮小型無人機(jī)節(jié)點飛行時間較短、節(jié)點數(shù)量過多時所帶來的問題。

為此，本文針對小型無人機(jī)自組網(wǎng)節(jié)點數(shù)量多、位置變化快和續(xù)航時間短等特點，對AeroRP協(xié)議中的判距進(jìn)行改進(jìn)，設(shè)計了一種基于節(jié)點生存時間的路由判據(jù)(Routing Metric Based on Node Survival-time，RMBNS)，綜合考慮了網(wǎng)絡(luò)內(nèi)各無人機(jī)的剩余飛行時間、移動速度矢量、與源節(jié)點之間距離以及源節(jié)點的最大傳輸距離等參數(shù)，將生存時間內(nèi)到達(dá)源節(jié)點先后順序作為度量尺度，實現(xiàn)了最優(yōu)下一跳節(jié)點的選擇，克服了傳統(tǒng)判距可能選擇無效節(jié)點導(dǎo)致數(shù)據(jù)傳輸中斷的問題。

1 AeroRP協(xié)議

AeroRP是為高度動態(tài)的機(jī)載網(wǎng)絡(luò)設(shè)計的路由協(xié)議，與其他端到端的MANET路由協(xié)議不同，它只進(jìn)行逐跳路由決策，這種方式可以避免機(jī)載網(wǎng)絡(luò)中因節(jié)點高速移動而導(dǎo)致在確定端到端路徑后鏈路中斷的問題[6-7]。

AeroRP的運行主要分為鄰居發(fā)現(xiàn)和數(shù)據(jù)轉(zhuǎn)發(fā)兩個階段。

(1)鄰居發(fā)現(xiàn)階段

在鄰居發(fā)現(xiàn)階段，機(jī)載節(jié)點TA通過以下三種機(jī)制盡可能多地收集有關(guān)網(wǎng)絡(luò)拓?fù)涞男畔ⅰ?/p>

主動偵聽：在主動偵聽機(jī)制中，節(jié)點偵聽正在其他節(jié)點之間交換的數(shù)據(jù)包，從中提取位置信息，并建立或更新其鄰居表。為此，必須啟用節(jié)點網(wǎng)絡(luò)接口上的主動探測。這樣收集的位置信息僅在“鄰居保持時間”(neighborHoldTime)指定的時間間隔內(nèi)有效。在此時間間隔內(nèi)，如果未收到新的位置更新，將清除節(jié)點存儲的位置信息。這有助于在高度動態(tài)的環(huán)境中跟蹤所有活躍的鄰居。

Hello信標(biāo)：當(dāng)節(jié)點不傳輸任何數(shù)據(jù)時，Hello信標(biāo)由節(jié)點傳輸。這確保了其鄰接節(jié)點知道它的存在。這些消息通常通過“Hello更新間隔”(helloUpdatelnterval)所規(guī)定的時間間隔定期廣播。

地面站更新：地面站更新機(jī)制用于在執(zhí)行某些任務(wù)中增強(qiáng)或替代主動偵聽，這些任務(wù)具有預(yù)先確定的飛行計劃。這些更新定期廣播，并在網(wǎng)絡(luò)中的所有節(jié)點之間交換。

(2)數(shù)據(jù)轉(zhuǎn)發(fā)階段

在此階段，發(fā)送方節(jié)點通過使用鄰居發(fā)現(xiàn)階段中構(gòu)建的拓?fù)浔韥泶_定轉(zhuǎn)發(fā)分組的下一跳。截獲時間(Time-to-Intercept，TTI)路由判據(jù)用于確定下一跳鄰居[9-10,12]。對于拓?fù)浔碇械拿總€節(jié)點，TTI計算如公式(1)所示：

(1)

式中：Δd是節(jié)點鄰居表中鄰節(jié)點的當(dāng)前位置和目的地位置之間的歐氏距離，R是所有節(jié)點的通用傳輸范圍，Sd是記錄的速度分量。選擇具有最低TTI值的鄰節(jié)點作為下一跳節(jié)點，并將數(shù)據(jù)包轉(zhuǎn)發(fā)給該節(jié)點。

若當(dāng)前節(jié)點自身具有最佳TTI，但其仍不在與目的節(jié)點數(shù)據(jù)傳輸?shù)姆秶鷥?nèi)，針對這種情況，AeroRP有三種處理模式：一是擺渡模式，即將數(shù)據(jù)包無限期地存儲在自身緩存隊列中，直到找到具有較低TTI的節(jié)點后進(jìn)行轉(zhuǎn)發(fā)；二是緩存模式，即排隊時間有一定限制，超時后仍未找到具有更低TTI的節(jié)點，則丟棄；三是丟包模式，即直接將數(shù)據(jù)包丟棄?？紤]到小型無人機(jī)的機(jī)載數(shù)據(jù)處理存儲能力有限、續(xù)航時間短的特點，并且為了保證網(wǎng)絡(luò)中數(shù)據(jù)的可靠傳輸，本文選擇緩沖模式進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

2 路由判據(jù)改進(jìn)算法

2.1 路由判據(jù)步驟

如前文所示，經(jīng)典的AeroRP協(xié)議中的TTI路由判據(jù)只考慮了相關(guān)節(jié)點的運動速度和距離信息，對于續(xù)航時間有限的小型無人機(jī)自組織網(wǎng)絡(luò)不適合。為了避免因選擇能量即將耗完或者所剩能量不足以維持?jǐn)?shù)據(jù)轉(zhuǎn)發(fā)的“潛在無效”節(jié)點作為下一跳節(jié)點的問題，這里提出基于生存時間的路由判據(jù)。判據(jù)為一種啟發(fā)式度量，記為RMBNS，其物理含義是在網(wǎng)內(nèi)所有節(jié)點中，某一節(jié)點在其生存時間內(nèi)出現(xiàn)在源節(jié)點的通信傳輸范圍內(nèi)的先后順序。具體步驟如下：

Step1 給定一個鄰居節(jié)點Ni，已知節(jié)點的地理坐標(biāo)為(xi，yi),速度為(vxi，vyi)，Ni的速度向量vi計算如公式(2)所示：

(2)

Step2 計算節(jié)點Ni正x軸與Ni速度矢量之間的夾角α：

(3)

Step3 給定目的地D的地理坐標(biāo)為(xd，yd)。Ni的正x軸與Ni和D連接的直線之間的角度α′為

(4)

Step4 計算v：

v=vicos(α-α′)。

(5)

源節(jié)點和目的地之間基于速度分量v是RMBNS計算的一個重要部分，數(shù)值為正表示該鄰節(jié)點正在靠近目的地移動，數(shù)值為負(fù)則表示鄰節(jié)點正在向目的地相反的方向移動，絕對值越大表明節(jié)點的運動速度越大。

Step5 在三維空間中，對于給定的源節(jié)點地理坐標(biāo)(xi，yi，zi)和目的地的地理坐標(biāo)(xd，yd，zd),計算源節(jié)點與目的地之間的歐氏距離Δd：

(6)

Step6 獲取節(jié)點Ni鄰居表中鄰居節(jié)點的剩余飛行時間ΔT：

ΔT=E/P-T。

(7)

式中：E是單個無人機(jī)的總能量，P是無人機(jī)的功率，T是無人機(jī)已飛行的時間。

Step7 根據(jù)公式(5)～(7)計算RMBNS，如公式(8)所示：

(8)

式中：R是指節(jié)點的數(shù)據(jù)傳輸范圍。

Step8 選取具有最大RMBNS的鄰節(jié)點作為下一跳節(jié)點。RMBNS=0是一種特殊情況，表示永遠(yuǎn)不要選擇這個鄰居節(jié)點作為下一跳，因為算法不會選擇遠(yuǎn)離目的地、不在傳輸范圍內(nèi)，且生存時間低于門限值的鄰居節(jié)點。

2.2 改進(jìn)判據(jù)在AeroRP協(xié)議中的實現(xiàn)

AeroRP協(xié)議是在沒有完整源節(jié)點到目的節(jié)點的端到端路由信息，即沒有掌握網(wǎng)絡(luò)全局路由信息的情況下進(jìn)行路由決策的，因此這種路由決策是按跳進(jìn)行。在實現(xiàn)路由判據(jù)時，每個節(jié)點都維護(hù)一張鄰居表，用于存儲當(dāng)前在其通信范圍內(nèi)的節(jié)點信息。初始化時，N代表鄰居表中鄰節(jié)點數(shù)量，令N為零。節(jié)點收到任意數(shù)據(jù)包時，它會對其鄰居表進(jìn)行更新。如果收到的數(shù)據(jù)包是來自于節(jié)點Ni的主動偵聽數(shù)據(jù)包或者是“Hello”通告數(shù)據(jù)包，那么當(dāng)前節(jié)點會認(rèn)為節(jié)點Ni在其通信范圍內(nèi)，并將節(jié)點Ni加入到它的鄰居表中，使得N=N∪{Ni}，節(jié)點列表同時獲取節(jié)點Ni的位置、軌跡等信息，并以數(shù)組的形式存于鄰居表中。當(dāng)前節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包時，它會遍歷其鄰居表，并計算每個鄰節(jié)點包括其自己的RMBNS值，如果某一鄰節(jié)點具有最大的RMBNS值，當(dāng)前節(jié)點會將數(shù)據(jù)包轉(zhuǎn)發(fā)給該節(jié)點。算法偽代碼如下：

輸入Input：location(my_x,my_y,my_z,my_vx,my_vy,my_T,dx,dy,dz)

輸出Output：NextHop

初始化Inital：

RMBNS_neighbor *temp =head_//從鄰居表的頭部開始遍歷

RMBNS =getRMBNS(location)//初始化RMBNS

nsaddr_t NextHop =-1//沒有下一跳的傳輸

程序 Procedure RMBNS：，

Repeat

tempRMBNS =getRMBNS(temp->x_,temp->y_,temp->z_,temp->T,temp->v dx,dy,dz)

if(tempRMBNS >RMBNS)

RMBNS =tempRMBNS

ReturnNextHop//遍歷鄰居表，如果找到最大的RMBNS，則返回對應(yīng)的下一跳地址

3 仿真實驗與性能分析

使用ns-3平臺對改進(jìn)判據(jù)的性能進(jìn)行仿真驗證，比較其與TTI判據(jù)的性能差別，同時對比兩種判據(jù)下的AeroRP協(xié)議與經(jīng)典主動路由協(xié)議OLSR的性能。仿真所模擬的應(yīng)用場景為一個典型的多機(jī)單站小型無人機(jī)集群，網(wǎng)絡(luò)由10～100個位置隨機(jī)分布的節(jié)點組成，其中地面控制站作為固定的匯聚節(jié)點位于區(qū)域的中心位置，網(wǎng)絡(luò)數(shù)據(jù)鏈路層協(xié)議選擇IEEE802.11b。如前所述，實驗使用AeroRP協(xié)議的緩沖模式，根據(jù)網(wǎng)絡(luò)傳輸數(shù)據(jù)包大小設(shè)置緩沖區(qū)為200，最大緩沖時間設(shè)置為5 s。緩沖時間到期后，數(shù)據(jù)包將被清除。實驗適用隨機(jī)運動模型，傳輸層協(xié)議為UDP，其他相關(guān)參數(shù)設(shè)置如表1所示。

表2 實驗參數(shù)

在實驗中，分別從以下三個方面對判據(jù)進(jìn)行測試：一是吞吐量，即單位時間內(nèi)成功地傳送數(shù)據(jù)包的數(shù)量；二是準(zhǔn)確度，即目的節(jié)點成功接收的數(shù)據(jù)包數(shù)除以發(fā)送端MAC層發(fā)送的數(shù)據(jù)包數(shù)，該指標(biāo)是根據(jù)分組選擇的路由是否在目的地成功接收來進(jìn)行測量；三是延遲，即數(shù)據(jù)包從源節(jié)點在MAC層傳輸數(shù)據(jù)包與目的地MAC層接收數(shù)據(jù)包之間的時間差。同一節(jié)點數(shù)量均進(jìn)行30次仿真實驗，結(jié)果取平均值。

圖1給出了節(jié)點數(shù)量與網(wǎng)絡(luò)平均吞吐量的關(guān)系，可以看出網(wǎng)絡(luò)的節(jié)點密度對三種路由判據(jù)都有一定影響。當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)量較少時，由于OLSR根據(jù)已經(jīng)建立好的完整的端到端路由項進(jìn)行快速數(shù)據(jù)轉(zhuǎn)發(fā)，因此吞吐量比其他兩者要高。但是，隨著節(jié)點的增多，網(wǎng)絡(luò)規(guī)模變大，OLSR事先建立的路由表中，一些節(jié)點由于隨機(jī)運動超出了傳輸范圍，或者生存時間不足以支持轉(zhuǎn)發(fā)數(shù)據(jù)包，造成鏈路中斷，最終導(dǎo)致吞吐量性能開始下降。相比之下，AeroRP TTI在少于70個節(jié)點的時候吞吐量比RMBNS的性能更優(yōu)，吞吐量隨著節(jié)點數(shù)的增加而增加，但當(dāng)節(jié)點數(shù)接近70或更高時RMBNS判據(jù)的吞吐量比 AeroRP增長更快。這說明由于AeroRP的TTI判據(jù)選擇下一跳時，只根據(jù)速度矢量和距離進(jìn)行判斷，隨著節(jié)點的增加，所選的下一跳是一個生存時間即將耗盡的無人機(jī)節(jié)點的概率增大，這樣會導(dǎo)致數(shù)據(jù)無法傳遞，使得吞吐量增長減慢；而RMBNS選擇下一跳將無人機(jī)生存時間也考慮在內(nèi)，所以在節(jié)點數(shù)量較大的場合下可以提高網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)姆€(wěn)定性，吞吐量穩(wěn)定增長，這非常適用于未來無人機(jī)的“蜂群”應(yīng)用場景。

圖1 節(jié)點密度對吞吐量的影響

不同節(jié)點數(shù)量下三種路由判據(jù)對路由準(zhǔn)確度的影響如圖2所示。仿真結(jié)果表明，無論節(jié)點數(shù)量如何，AeroRP的TTI、RMBNS和OLSR的準(zhǔn)確率均超過了70%。隨著節(jié)點數(shù)的增加，由于OLSR路由表中存在失效的節(jié)點，所以準(zhǔn)確度不再提高。而AeroRP隨著節(jié)點數(shù)量的增加，對數(shù)據(jù)包的轉(zhuǎn)發(fā)和準(zhǔn)確度接近100%，這說明了AeroRP能夠準(zhǔn)確地傳遞數(shù)據(jù)包；而RMBNS在準(zhǔn)確度上也一直優(yōu)于AeroRP的TTI判據(jù)。這在很大程度上說明RMBNS判據(jù)更適合在節(jié)點快速移動、飛行時間、能量受限的環(huán)境下準(zhǔn)確傳輸數(shù)據(jù)。

圖2 節(jié)點密度對準(zhǔn)確度的影響

節(jié)點密度對數(shù)據(jù)包傳輸延遲的影響情況如圖3所示。由于OLSR路由已根據(jù)判據(jù)計算出了路由表，因此在節(jié)點較少的情況下延遲比其他兩者要低，但是OLSR隨著節(jié)點的增加延遲一直在增大，說明這種主動式路由不適合動態(tài)的無人機(jī)網(wǎng)絡(luò)環(huán)境；而隨著節(jié)點密度的增加，AeroRP中的TTI判據(jù)的延遲在逐漸減小，當(dāng)節(jié)點接近75甚至更多時，延遲進(jìn)一步降低。RMBNS判據(jù)在延遲上一直比AeroRP的TTI較高，這是由判據(jù)設(shè)計的復(fù)雜度決定的。盡管RMBNS的延遲隨著節(jié)點的增加也呈下降趨勢，但是在提高準(zhǔn)確度和吞吐量的前提下，犧牲一點延遲對于對實時性要求不高的應(yīng)用是可以容忍的。

圖3 節(jié)點密度對延遲的影響

4 結(jié) 論

小型無人機(jī)自組網(wǎng)有著廣泛的應(yīng)用前景，因其具有拓?fù)鋭討B(tài)變化、能耗要求高等特點，在設(shè)計網(wǎng)絡(luò)路由協(xié)議和判據(jù)時也存在著一定的挑戰(zhàn)。在網(wǎng)絡(luò)層利用地理信息進(jìn)行路由，可以提高路由協(xié)議的性能。本文所提出的面向小型無人機(jī)的路由判據(jù)RMBNS是基于網(wǎng)絡(luò)層共享物理層的地理位置信息和生存時間等信息，從而實現(xiàn)小型無人機(jī)網(wǎng)絡(luò)路由的穩(wěn)定性和健壯性。通過仿真發(fā)現(xiàn)，基于RMBNS的AeroRP協(xié)議性能明顯優(yōu)于經(jīng)典的OLSR，并且與經(jīng)典AeroRP協(xié)議中的TTI相比，RMBNS判據(jù)在路由吞吐量和準(zhǔn)確度上都有所提升，更加適合小型無人機(jī)自組織網(wǎng)絡(luò)路由的選擇。