袁 學(xué) 松

(安徽機(jī)電職業(yè)技術(shù)學(xué)院 信息工程系,安徽 蕪湖 241001)

0 引 言

無人機(jī)(UAV,Unmanned Aerial Vehicle)是利用無線電遙控設(shè)備和自身的相關(guān)程序控制裝置操縱的一種飛行器[1]。當(dāng)前民用無人機(jī)多用在農(nóng)業(yè)、植保、航拍、災(zāi)難救援等方面。隨著航空技術(shù)、無線電技術(shù)的發(fā)展，無人機(jī)的各種用途正在被開發(fā)出來，逐漸由單一作業(yè)轉(zhuǎn)變?yōu)榧夯l(fā)展態(tài)勢(shì)[2]。無人機(jī)自組網(wǎng)的概念也隨之被提出，在車聯(lián)網(wǎng)中較成熟的Vanet技術(shù)[3-4]也逐步被應(yīng)用到UAV上。和車聯(lián)網(wǎng)相比UAV具有更多變化的運(yùn)行軌跡，網(wǎng)絡(luò)拓?fù)涓硬环€(wěn)定，UAV只可以靠電池供電，不能像Vanet一樣忽略其能耗。同時(shí)，其運(yùn)行場(chǎng)景是三維的，這給設(shè)計(jì)相關(guān)路由算法帶來很多不便。但是UAV信號(hào)的傳播不會(huì)受到建筑物或者相關(guān)樹木的遮擋，工作場(chǎng)景較為單一。在UAV上會(huì)有相關(guān)設(shè)備如:全球定位裝置(北斗導(dǎo)航裝置、GPS等)，電子地圖，機(jī)載各種控制傳感器(如:風(fēng)速傳感器、溫濕度傳感器等)和無線通信裝置等來實(shí)現(xiàn)UAV直接相互數(shù)據(jù)通信或和地面控制裝置的相互通信。針對(duì)UAV工作場(chǎng)景設(shè)計(jì)出多跳數(shù)據(jù)安全路由傳輸逐漸成為當(dāng)前的研究熱點(diǎn)。

在經(jīng)典的車聯(lián)網(wǎng)場(chǎng)景中，由于車輛大多工作在二維的空間中，傳統(tǒng)的路由協(xié)議主要有:基于拓?fù)涞穆酚蒁SR[5]、DSDV[6]、AODV[7]等，該類路由發(fā)送消息時(shí)，各節(jié)點(diǎn)都必須記錄臨時(shí)路由表，發(fā)送節(jié)點(diǎn)根據(jù)回傳的消息選擇最短的路徑進(jìn)行傳輸消息。但在網(wǎng)絡(luò)拓?fù)渥兓^快的情況下就不太適合，節(jié)點(diǎn)會(huì)失效，導(dǎo)致斷路的情況出現(xiàn)；基于電子地圖的路由算法，如:GeoSVR[8]這類路由協(xié)議主要是將電子地圖引入到算法中，通過電子地圖輔助預(yù)測(cè)相關(guān)節(jié)點(diǎn)位置進(jìn)行數(shù)據(jù)傳輸，UAV工作模式不支持安裝大型電子地圖和定期對(duì)電子地圖進(jìn)行數(shù)據(jù)更新；基于運(yùn)行軌跡的路由算法，如:VADD[9]，它是根據(jù)道路的方向和車輛的相關(guān)運(yùn)行方向和軌跡來預(yù)測(cè)車輛節(jié)點(diǎn)的位置，其也不適合在無人機(jī)的工作場(chǎng)景中使用；基于地理位置的路由算法GPSR[10]，隨著北斗等全球定位系統(tǒng)的逐步完善，基于地理位置的車聯(lián)網(wǎng)路由算法近年來不斷發(fā)展，由于定位系統(tǒng)可以測(cè)量節(jié)點(diǎn)的經(jīng)度、緯度和海拔等信息，許多學(xué)者將經(jīng)典的算法進(jìn)行改進(jìn)，把其應(yīng)用在復(fù)雜道路或者城市立體交通中。GPSR算法是將要傳輸?shù)臄?shù)據(jù)盡量轉(zhuǎn)發(fā)給最靠近的鄰居中繼節(jié)點(diǎn)，不僅可以減少轉(zhuǎn)發(fā)跳數(shù)，也可以提高轉(zhuǎn)發(fā)效率減輕網(wǎng)絡(luò)的負(fù)載。由于無人機(jī)節(jié)點(diǎn)大多處于高速飛行狀態(tài)，且運(yùn)行軌跡也不像汽車有規(guī)律，如果發(fā)送節(jié)點(diǎn)發(fā)送的分組數(shù)據(jù)未能找到轉(zhuǎn)發(fā)鄰居節(jié)點(diǎn)或在轉(zhuǎn)發(fā)鄰居節(jié)點(diǎn)過程中，鄰居節(jié)點(diǎn)已經(jīng)超出信號(hào)傳輸范圍。這樣就會(huì)導(dǎo)致發(fā)送節(jié)點(diǎn)重新尋找相關(guān)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，重發(fā)的分組數(shù)據(jù)加大網(wǎng)絡(luò)負(fù)載，使網(wǎng)絡(luò)性能下降明顯。

針對(duì)UAV的工作場(chǎng)景，引入了MALM[11]移動(dòng)位置輔助管理策略。通過建立UAV的運(yùn)動(dòng)模型，對(duì)其運(yùn)動(dòng)規(guī)律進(jìn)行分析。使用Hello包來交換網(wǎng)絡(luò)中各節(jié)點(diǎn)的運(yùn)動(dòng)狀態(tài)信息，并使用MALM預(yù)測(cè)出自己所有鄰居節(jié)點(diǎn)的下一時(shí)刻的位置，更新節(jié)點(diǎn)鄰居表。當(dāng)遇到稀疏節(jié)點(diǎn)和故障節(jié)點(diǎn)的情況時(shí)，使用攜帶信息方式存儲(chǔ)信息，當(dāng)節(jié)點(diǎn)Hello包檢測(cè)到相關(guān)鄰居節(jié)點(diǎn)時(shí)，仍使用GPSR算法中的貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)機(jī)制對(duì)數(shù)據(jù)進(jìn)行傳輸。

1 UAV運(yùn)動(dòng)場(chǎng)景中相關(guān)問題描述

算法默認(rèn)所有集群無人機(jī)節(jié)點(diǎn)均安裝有GPS、北斗或其他類似全球定位裝置。節(jié)點(diǎn)可以通過機(jī)載各種類型傳感器獲取運(yùn)動(dòng)節(jié)點(diǎn)精確的位置信息(經(jīng)度、緯度和海拔等)，節(jié)點(diǎn)的實(shí)時(shí)速度、運(yùn)動(dòng)方向、當(dāng)前的風(fēng)速及方向等，同時(shí)能夠獲得統(tǒng)一的時(shí)間信息。

1.1 GPSR傳輸節(jié)點(diǎn)失效問題

節(jié)點(diǎn)在三維的空間中高速運(yùn)動(dòng)中，使用類似地理位置路由如(GPSR)算法經(jīng)常會(huì)出現(xiàn)所要傳輸?shù)闹欣^路由節(jié)點(diǎn)失效情況。如圖1所示UAV節(jié)點(diǎn)A在t時(shí)刻想與節(jié)點(diǎn)D進(jìn)行數(shù)據(jù)傳輸。首先A通過自身的傳感器獲取自己的位置信息,也就是自己的經(jīng)度、緯度和海拔高度信息，然后查找相關(guān)的鄰居表。根據(jù)GPSR協(xié)議，數(shù)據(jù)將被一次轉(zhuǎn)發(fā)至離自己最遠(yuǎn)，離節(jié)點(diǎn)D最近，且在當(dāng)前通信范圍之內(nèi)的節(jié)點(diǎn)B。節(jié)點(diǎn)A從查找到獲得信道進(jìn)行傳輸操作需要Δt時(shí)間，在這個(gè)時(shí)間內(nèi)(圖2)。B節(jié)點(diǎn)已超出A節(jié)點(diǎn)的通信范圍，A無法將數(shù)據(jù)發(fā)給B，這樣就會(huì)造成了路由節(jié)點(diǎn)的失效問題。如果路由節(jié)點(diǎn)失效A就需要再去找別的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)操作，這樣大大加重了網(wǎng)絡(luò)的負(fù)載。

圖1 t時(shí)刻無人機(jī)二維場(chǎng)景圖Fig. 1 Two-dimensional scene map of UAV at t-time

圖2 t+Δ t時(shí)刻無人機(jī)二維場(chǎng)景圖Fig. 2 Two-dimensional scene map of UAV for time t+Δ t

為了避免節(jié)點(diǎn)失效問題，擬使用較為成熟的MALM技術(shù)，來預(yù)測(cè)無人機(jī)節(jié)點(diǎn)的實(shí)時(shí)位置。這種預(yù)測(cè)方法是根據(jù)卡爾曼濾波器的原理來實(shí)現(xiàn)的，同時(shí)減少了整個(gè)網(wǎng)絡(luò)為計(jì)算節(jié)點(diǎn)位置信息帶來的網(wǎng)絡(luò)開銷。MALM技術(shù)只用來預(yù)測(cè)節(jié)點(diǎn)的位置，而不用來決定一跳路由。

1.2 貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)問題

在圖3中可以看到在t時(shí)刻A節(jié)點(diǎn)想傳輸數(shù)據(jù)給D節(jié)點(diǎn)，在A節(jié)點(diǎn)的傳輸范圍內(nèi)沒有任何節(jié)點(diǎn)比A節(jié)點(diǎn)更加接近于D節(jié)點(diǎn)的了。這是GPSR算法就不可以在根據(jù)貪婪轉(zhuǎn)發(fā)的方式來發(fā)送數(shù)據(jù)，形成了路由的“空洞”。這時(shí)它就會(huì)進(jìn)行周邊轉(zhuǎn)發(fā)的方式進(jìn)行數(shù)據(jù)分組的傳輸。首先(如圖3所示)它會(huì)根據(jù)“右手準(zhǔn)則”發(fā)送給節(jié)點(diǎn)C，節(jié)點(diǎn)C再根據(jù)貪婪轉(zhuǎn)發(fā)的方式發(fā)送給節(jié)點(diǎn)C′(如果還有路由黑洞還是進(jìn)行周邊轉(zhuǎn)發(fā))，直至傳送給目的節(jié)點(diǎn)。在整個(gè)過程中也有可能會(huì)出現(xiàn)傳輸節(jié)點(diǎn)失效問題。下面將對(duì)整個(gè)算法進(jìn)行描述。

圖3 GPSR協(xié)議路由“空洞”時(shí)無人機(jī)二維場(chǎng)景圖Fig. 3 Two-dimensional scene map of UAV in routing“hollow” by GPSR Protocol

1.3 使用一跳Hello分組發(fā)現(xiàn)并維護(hù)節(jié)點(diǎn)鄰居表

節(jié)點(diǎn)的鄰居表在算法中尤為重要，它是節(jié)點(diǎn)進(jìn)行一跳轉(zhuǎn)發(fā)的重要依據(jù)。在很多車聯(lián)網(wǎng)的地理位置路由算法中，鄰居節(jié)點(diǎn)的預(yù)測(cè)大多使用電子地圖結(jié)合自身定位來預(yù)測(cè)節(jié)點(diǎn)是否失效，并進(jìn)行路由轉(zhuǎn)發(fā)。在算法中，設(shè)計(jì)了一種使用周期廣播Hello信標(biāo)建立并維護(hù)鄰居表的方法?，F(xiàn)將著重介紹算法鄰居表的建立過程和維護(hù)方案。

假設(shè)網(wǎng)絡(luò)拓?fù)淙鐖D1所示，發(fā)送節(jié)點(diǎn)A需發(fā)送分組給節(jié)點(diǎn)D，首先拓?fù)渲械母鱾€(gè)節(jié)點(diǎn)會(huì)根據(jù)自己的位置、速度矢量傳感器、風(fēng)速傳感器等獲取當(dāng)前狀態(tài)下的位置信息Pa(Xa,Ya,Ha)、當(dāng)前的矢量速度，當(dāng)前矢量風(fēng)速，并獲得自身的能耗信息(用于判斷節(jié)點(diǎn)的健康程度)。生成廣播信息包。Hello廣播信息包包結(jié)構(gòu)的設(shè)計(jì)如圖4所示。Hello包中使用2個(gè)字節(jié)表示ID，用于對(duì)發(fā)送包的無人機(jī)節(jié)點(diǎn)進(jìn)行唯一性標(biāo)識(shí)。使用6個(gè)字節(jié)標(biāo)識(shí)自身節(jié)點(diǎn)的經(jīng)度、緯度和海拔等信息(各占2個(gè)字節(jié))，2個(gè)字節(jié)標(biāo)識(shí)合成速度和相關(guān)夾角值，2個(gè)字節(jié)標(biāo)識(shí)時(shí)間戳(發(fā)送該Hello信令的時(shí)間)，使用1個(gè)字節(jié)來標(biāo)識(shí)節(jié)點(diǎn)的健康狀態(tài)(無人機(jī)節(jié)點(diǎn)的電量狀態(tài))。

圖4 Hello包結(jié)構(gòu)Fig. 4 The structure of Hello package

圖5 三維場(chǎng)景下速度合成圖Fig. 5 Velocity composition map in three-dimensional scene

表1 算法的節(jié)點(diǎn)鄰居表結(jié)構(gòu)Table 1 Neighbor table format of a node in algorithm

1.4 使用決策函數(shù)來確定路由

上文對(duì)無人機(jī)節(jié)點(diǎn)的鄰居表的建立和退出進(jìn)行了相關(guān)的描述。無人機(jī)節(jié)點(diǎn)需要通過查找鄰居表來判斷把數(shù)據(jù)轉(zhuǎn)發(fā)給誰。算法采用決策函數(shù)的方法來完成節(jié)點(diǎn)路由的選擇。假設(shè)節(jié)點(diǎn)A的鄰居表中有i個(gè)節(jié)點(diǎn)信息，使用(i=1,2,3，…)來表示對(duì)應(yīng)的節(jié)點(diǎn)。節(jié)點(diǎn)要傳輸數(shù)據(jù)給下個(gè)節(jié)點(diǎn)，不僅僅需要看在下一個(gè)時(shí)刻其是否失效，也不僅僅看節(jié)點(diǎn)間的距離，而是需要綜合各方面的因素來判定的。算法中第i個(gè)節(jié)點(diǎn)的決策函數(shù)設(shè)置為F(i)=ω1f1(i)+ω2f2(i)+ω3f3(i)，其中f1(i)為距離因素也就是鄰居表中的距離值，ω1為距離的權(quán)重因子。f2(i)為信道質(zhì)量的值，ω2為信道質(zhì)量權(quán)重因子。f3(i)為節(jié)點(diǎn)健康情況的值，ω3為節(jié)點(diǎn)健康的權(quán)重因子。其中ω1+ω2+ω3=1。

2 GPSR-HRU路由算法的描述

GPSR-HRU路由算法引入無線自組網(wǎng)的GPSR協(xié)議中來預(yù)測(cè)節(jié)點(diǎn)的移動(dòng)位置。同時(shí)，算法通過定義新的Hello信標(biāo)，設(shè)計(jì)帶有冗余傳輸節(jié)點(diǎn)的數(shù)據(jù)傳輸方式來提高數(shù)據(jù)傳輸?shù)目煽啃?。具體算法如圖6 所示。

圖6 節(jié)點(diǎn)路由選擇流程圖Fig. 6 Node routing flow diagram

各節(jié)點(diǎn)數(shù)據(jù)分組發(fā)送的步驟如下:

(1) 當(dāng)開始傳輸數(shù)據(jù)時(shí)，發(fā)送節(jié)點(diǎn)根據(jù)權(quán)值決策函數(shù)計(jì)算出節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)的代價(jià)。同時(shí)查找自己的鄰居表看目的節(jié)點(diǎn)是否在鄰居表內(nèi)。

(2) 目的節(jié)點(diǎn)在鄰居表內(nèi)且通過MALM來判斷這個(gè)節(jié)點(diǎn)在傳輸過程中不會(huì)失效，就會(huì)直接轉(zhuǎn)發(fā)給節(jié)點(diǎn)直至傳輸結(jié)束。如果通過預(yù)測(cè)節(jié)點(diǎn)在傳輸過程中會(huì)失效，或者目的節(jié)點(diǎn)不在鄰居表中。則進(jìn)入步驟(3)。

(3) 使用MALM來預(yù)測(cè)各節(jié)點(diǎn)的位置信息，查找鄰居表篩選哪些在傳輸過程中不失效的節(jié)點(diǎn)進(jìn)行操作，找到是否有貪婪轉(zhuǎn)發(fā)的節(jié)點(diǎn)，如果有進(jìn)入步驟(4)，如果沒有進(jìn)入步驟(5)。

(4) 通過決策函數(shù)的計(jì)算，并結(jié)合貪婪轉(zhuǎn)發(fā)規(guī)則，找到函數(shù)值最大的鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，并找到函數(shù)值第二大的鄰居節(jié)點(diǎn)設(shè)置為備選。在發(fā)送節(jié)點(diǎn)上設(shè)置超時(shí)定時(shí)器，如果在規(guī)定時(shí)間內(nèi)數(shù)據(jù)未轉(zhuǎn)發(fā)成功，找備用節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，同樣設(shè)置超時(shí)定時(shí)器，如果還是未發(fā)送成功則轉(zhuǎn)至步驟(1)。如果發(fā)送成功則轉(zhuǎn)至步驟(6)。

(5) 找到是否有周邊轉(zhuǎn)發(fā)節(jié)點(diǎn)，如果有周邊轉(zhuǎn)發(fā)節(jié)點(diǎn)，同樣根據(jù)決策函數(shù)值找到主備傳輸節(jié)點(diǎn)，設(shè)置定時(shí)器進(jìn)行傳輸。如果傳輸失敗轉(zhuǎn)到步驟(1)，如果傳輸成功轉(zhuǎn)到步驟(6)。

(6) 在轉(zhuǎn)發(fā)至節(jié)點(diǎn)后，再次使用GPSR-HRU直至數(shù)據(jù)分組轉(zhuǎn)發(fā)至目的節(jié)點(diǎn)。

在整個(gè)算法過程中一直在周期性的進(jìn)行鄰居的加入和更新，傳輸數(shù)據(jù)和鄰居表的維護(hù)互不沖突。

3 實(shí)例仿真分析與應(yīng)用

將所描述的GPSR-HRU算法應(yīng)用在集群無人機(jī)工作場(chǎng)景中。將協(xié)議與經(jīng)典的GPSR算法和錯(cuò)開空洞的改進(jìn)的GPSR-AD[12]算法進(jìn)行性能的比較。由于無人機(jī)的工作特殊性，在集群工作情況下節(jié)點(diǎn)個(gè)數(shù)幾乎是不變的，沒有考慮在三維空間中節(jié)點(diǎn)密度變化的情況。仿真實(shí)驗(yàn)考察在節(jié)點(diǎn)密度不變的情況下，通過改變各個(gè)節(jié)點(diǎn)的飛行速度范圍，判斷其在不同速度區(qū)間內(nèi)，端到端的平均傳輸時(shí)延和數(shù)據(jù)包投遞成功率等性能。

實(shí)驗(yàn)仿真使用離散節(jié)點(diǎn)生成器Vanet Mobi Sim[13-14](Vehicular Ad Hoc Networks Mobility Simulator)來生成無人機(jī)不同速度區(qū)間節(jié)點(diǎn)運(yùn)動(dòng)模型。同時(shí)使用移動(dòng)位置輔助管理策略進(jìn)行節(jié)點(diǎn)位置的預(yù)測(cè)和管理。仿真場(chǎng)景為一個(gè)三維的長(zhǎng)2KM*2KM*2KM的立方體空間。整個(gè)實(shí)驗(yàn)在NS-3[15]仿真平臺(tái)下完成。具體參數(shù)見表2。

表2 實(shí)驗(yàn)仿真參數(shù)設(shè)置Table 2 Experimental simulation parameter setting

從圖7在不同速度區(qū)間的節(jié)點(diǎn)數(shù)據(jù)包投遞成功率可以看出，在節(jié)點(diǎn)運(yùn)動(dòng)速度較慢的場(chǎng)景中，這3種算法的數(shù)據(jù)包投遞率都達(dá)到了90%左右。隨著節(jié)點(diǎn)速度的增加，整個(gè)拓?fù)浣Y(jié)構(gòu)變得不再穩(wěn)定。節(jié)點(diǎn)間在經(jīng)典的GPSR算法中會(huì)出現(xiàn)很多“空洞”和節(jié)點(diǎn)失效的情況，GPSR-AD很好地解決了這些問題，所以直到節(jié)點(diǎn)速度在100～120之間GPSR-AD還具有很好的投遞成功率。隨著節(jié)點(diǎn)運(yùn)動(dòng)速度再次加快，算法的穩(wěn)定性就體現(xiàn)出來了。在仿真實(shí)驗(yàn)中可以看到在速度140～200區(qū)間內(nèi)，GPSR-AD投遞成功率急速下降，而算法則保持穩(wěn)定。這再次驗(yàn)證了算法設(shè)計(jì)備用節(jié)點(diǎn)和決策函數(shù)推舉路由的優(yōu)點(diǎn)。

圖7 不同速度區(qū)間的數(shù)據(jù)包投遞成功率Fig. 7 Packet delivery success rate under different speed ranges

圖8 不同速度區(qū)間端到端的平均傳輸時(shí)延Fig. 8 Average end-to-end transmission delay under different speed ranges

4 結(jié) 語

在無人機(jī)集群可靠無線通信中，有很多算法已經(jīng)表現(xiàn)出了良好特性。提出了一種使用MALM來預(yù)測(cè)和管理高速運(yùn)動(dòng)節(jié)點(diǎn)，同時(shí)使用一跳Hello信令來交換鄰居表信息的方法并將其應(yīng)用到GPSR路由算法中。當(dāng)節(jié)點(diǎn)通過算法傳輸數(shù)據(jù)時(shí)，會(huì)根據(jù)相關(guān)的決策函數(shù)來選取主傳送節(jié)點(diǎn)和備用傳送節(jié)點(diǎn)，大大降低了鏈路由于拓?fù)洳环€(wěn)定導(dǎo)致的斷路重發(fā)問題。經(jīng)仿真實(shí)驗(yàn)證明，算法在無人機(jī)集群節(jié)點(diǎn)相對(duì)穩(wěn)定的情況下，較同類算法有較低的平均端到端延時(shí)、較輕的網(wǎng)絡(luò)負(fù)載、數(shù)據(jù)包投遞的成功率明顯高于其他算法。由于某些原因，在一個(gè)三維空間內(nèi)，無人機(jī)節(jié)點(diǎn)在不同空間區(qū)域的密度可能不同，可能會(huì)導(dǎo)致稀疏節(jié)點(diǎn)下的傳輸問題。同時(shí)，在算法中自行定義了決策函數(shù)的權(quán)重值，這只能適應(yīng)特定的場(chǎng)景，下一步將重點(diǎn)研究如何根據(jù)不同的場(chǎng)景自適應(yīng)的生成權(quán)重值，進(jìn)一步改進(jìn)協(xié)議性能。