基于短時軌跡交互的稀疏UANET貪婪路由協議*

陳秉試

（廈門海洋職業技術學院，福建 廈門 361012）

0 引 言

無人機自組網絡（UAV Ad Hoc Network，UANET）在軍民用方面都發揮著重要作用[1-2]。無人機自組網絡以無人機作為基本節點，通常配備地面通信設備輔助通信或作為后臺數據管控，不僅具有常規移動自組網絡的一般特點，如移動性﹑自組織性﹑可擴展性以及多跳路由等，也具有自身的特點，如三維空間運動特性﹑節點密度稀疏性﹑能量有限性等。因此，在多跳數據傳輸時，應當結合UANET自身特點設計路由協議。

文獻[3]以按需距離矢量路由協議AODV（Ad hoc On-demand Distance Vector Routing）路由為基礎，加入閾值衡量無人機節點間的鏈路質量，提高了傳輸路徑的選擇可靠性。但是，AODV中路徑探索和傳輸分離使得其難以適應高度動態的拓撲環境。表驅動式優化鏈路狀態路由協議OLSR（Optimized Link State Routing）在無人機網絡中得到廣泛應用并進行了改良。文獻[4]提出了P-OLSR路由協議，通過裝載在無人機上的全球定位系統（Global Positioning System，GPS）獲取節點位置，并通過節點運動軌跡預測選擇中繼節點，同時在Linux開發板中完成硬件實現。文獻[5]在OLSR路由中加入節點速度和能量信息，并對節點的willingness進行分級，從而優化多點中繼（Multi Point Relay，MPR）集合。文獻[6]則在OLSR路由中考慮了節點連接時間﹑鏈路層擁塞度以及節點剩余能量，提出了MPEAOLSR路由協議，改善了數據傳輸性能。但是，基于OLSR及其改進的路由協議均需要不斷維護并更新MPR集，網絡開銷較大。

貪婪周邊無狀態路由協議（Greedy Perimeter Stateless Routing，GPSR）以節點空間位置為依據，在無人機網絡多跳數據傳輸中體現出了優異性能，特別是在節點密度較大的場景下[7-8]，且原理簡單﹑網絡開銷較小。但是，該機制并不能完全適用于無人機自組網特點。文獻[9]從無人機節點位置﹑速度和方向等角度考慮，綜合篩選中繼節點，具有開銷小﹑可靠性高的優點。文獻[10]提出基于移動預測和鏈路保持時間的路由協議MP-GPSR，緩解高度動態拓撲變化對鏈路鏈接情況的影響，并利用兩跳節點信息提高右手準則在處理路由空洞時的效率。然而，目前應用在UANET的GPSR及其改進并未充分考慮三維空間關系，且對于節點移動性的預測都以當前瞬時運動狀態為依據，預測準確度有待提高。本文將針對三維空間關系進行位置關系計算，節點還將根據自身運動軌跡完成短時軌跡的曲線擬合并交互擬合階數和系數，通過少量的網絡開銷提高了移動預測準確度，從而提高數據包傳輸交付率。此外，針對稀疏環境下時常出現路由空洞導致右手準則難以發揮的問題，本文將采用攜帶轉發的方法降低開銷。

1 系統模型

設所研究的UANET中共包含N個節點，每個節點通信半徑均為R。對于節點i(i=1,2,…,N)，其通信半徑內的所有節點稱為節點i的一跳鄰居。節點i位置可以通過機載GPS獲取，可用三維坐標(xi,yi,zi)表示，其中xi表示經度，yi表示維度，zi表示海拔高度。于是，它與節點j之間的距離可以表示為：

顯然，若dij＜R，則節點i與節點j互為一跳鄰居節點，即相互成為潛在的中繼節點。節點將周期發送信標，包含節點ID﹑空間坐標﹑速度等，發送周期設定為ΔtB。一跳鄰居節點之間可通過周期信標感知相互位置，并根據運動慣性利用曲線擬合完成移動性預測。由于節點運動狀態通常連續變化，且在一段短時范圍內將按規劃軌跡和運動狀態飛行，設節點i從當前時刻在未來時間間隔Δt內在其軌跡liΔt上將以viΔt做勻速曲線運動，則節點將Δt﹑liΔt﹑viΔt等短時軌跡運動信息以及時間戳﹑節點ID﹑坐標信息加載在數據包字段中發送給其他節點，以實現更精確的拓撲變化感知。然而，若所有節點都將此信息加載在周期信標中必然將大大增大網絡負載，因此短時軌跡運動信息將由發出數據請求的節點加載在請求包中擴散，以尋找數據源。若有節點含有該請求包對應的數據，則成為源節點，而發出請求的節點成為目的節點，且響應包從源節點發出，利用路由協議傳輸至目的節點。這樣從目的節點發出請求包到源節點準備發出響應包，通常需要比信標周期長得多的時間間隔。源節點僅根據目的節點發送請求包時的位置﹑速度﹑角度等信息預測將導致較大偏差，特別是在節點運動速度較大的無人機網絡環境中。因此，目的節點通過發送短時軌跡運動信息可顯著提高移動預測準確率。

2 GR-TTI路由協議

2.1 總體流程

發起數據請求的節點i擬合liΔt，并將擬合參數與其他標記自身狀態和數據請求信息加入請求包piΔt發出。發出請求的節點若在發出請求包后等待Δt仍未收到響應包，則重新發送請求。重復發送nr次請求若未收到響應包，則放棄請求。相應的流程圖如圖1所示。

圖1 節點請求流程

在稀疏節點密度環境下，請求包將以泛洪方式擴散。其他節點在接收到請求包piΔt后，先檢測當前時刻與請求包內時間戳的差值是否超過時間間隔Δt/2。若超過，則說明當響應包傳回時目的節點已飛出可預測軌跡，因此丟棄請求包；若未超過，則檢測本地是否有對應的響應包。若有，則采用貪婪轉發或攜帶轉發傳給目的節點；否則，泛洪請求。

為減少網絡中相同請求包的冗余，中繼節點在轉發請求包后若收到其他節點轉發來的相同請求包則丟棄。類似地，為減少網絡中相同響應包轉發冗余，中繼節點在轉發響應包后若收到其他節點轉發相同的響應包，則丟棄。節點針對請求包的處理流程如圖2所示。

圖2 請求包接收后處理流程

2.2 貪婪轉發

請求節點即為目的節點，發送響應包的節點即可視為源節點。當源節點或中繼節點按照圖2進入貪婪轉發時，根據請求包或者上一跳節點告知的請求時間戳﹑Δt以及目的節點軌跡信息計算當前時刻目的節點位置，并根據鄰居信標信息評估下一跳距離目的節點最近的節點并轉發響應包，同時告知其目的節點運動和軌跡信息。在稀疏場景下可能出現路由空洞，即暫無下一跳節點或者不存在比自己距離目的節點更近的鄰居節點，則采用攜帶轉發。

2.3 短時軌跡交互

無人機節點的軌跡可事先根據任務采用傳統經典算法或現代智能算法規劃完成，其中傳統經典算法包括數學歸納法﹑動態歸納法﹑最優控制法以及導數相關法等。現代智能算法包括遺傳算法﹑人工神經網絡算法和蟻群算法等[11]。但是，UANET中節點常由于突發情況臨時修改軌跡，如某些節點電量不足返程充電﹑某些節點由于故障返程維修或者某些節點之間臨時需要相互支援等。因此，節點之間交互短時軌跡信息即可。一方面提高預測精確度，另一方面增大拓撲變化靈活度。

設節點A在t0時刻發送請求包，則其將[t0,t0+Δt]時間段內軌跡進行w階多項式擬合，表示為：

其中，t∈[t0,t0+Δt]，且{αr,…,α0}﹑{βr,…,β0}﹑{γr,…,γ0}分別是經緯度和海拔位置坐標和時間的擬合多項式系數。通過發布時間戳﹑時間間隔和三組多項式系數，即可使得源節點與中繼節點快速預測目的節點位置。

2.4 攜帶轉發

稀疏場景下，當某個中繼節點的鄰居節點中已無距離目的節點更近的下一跳節點時，則形成路由空洞。若采用傳統GPSR右手準則轉發，可能下一跳節點仍然無法擺脫路由空洞，甚至由于局部節點密度過低形成臨時的孤立節點。因此，在本文提出的協議中，節點將采用攜帶轉發[12]策略緩解響應包轉發途中出現的路由空洞問題，即節點遇到路由空洞時將待轉發的數據存儲于本地緩存中，通過對鄰居節點運動軌跡預測發現存在距離目的節點更近的下一跳節點，完成響應包轉發。若緩存時間超過一定時間無法找到目的節點或者更優中繼節點，則丟棄數據包。

3 仿真及分析

3.1 仿真條件

在MATLAB仿真平臺上搭建UANET模型，設定仿真物理空間為經緯方向各3 km，海拔高度100～500 m。無人機通信半徑為500 m，飛行時間300 s，飛行半徑1 km，節點個數3～15，每個節點均勻速曲線運動，但速度取值為[5，30] m/s中的均勻隨機值。不失一般性，各節點在海拔高度上隨機分布于100～500 m。為保證無人機之間不相撞，各節點飛行高度不同，且各自保持設定高度飛行。飛行軌跡簡化為圓周運動，圓周半徑1 km。為增大拓撲動態，節點在圓周軌跡上將隨機選擇順時針飛行或者逆時針飛行。選定某個飛行方向后，將保持10～20 s再重新隨機選擇飛行方向，該保持時間即為各節點請求包中的Δt。設定處于攜帶轉發狀態的節點緩存數據包時間為30 s。節點信標發送周期為1 s，最大請求次數為3次。仿真將評估GRTTI與傳統GPSR路由協議在不同節點個數下的數據包到達率和請求-響應延遲方面的性能。為了抵消運動和通信過程的隨機性，將重復100次后取平均值。

3.2 數據包到達率

數據包到達率定義為平均每個請求節點獲得的響應包和發出的請求包的比值。該指標可驗證路由協議的有效性。圖3為節點個數從3增加到15時GR-TTI和GPSR數據包到達率性能曲線。

圖3 數據包到達率

從圖3可以看出，在節點密度總體稀疏的環境下，隨著節點個數增加，兩個路由協議數據包到達率均增加。這是由于更多的節點可使網絡中具有更多潛在中繼可提供轉發，而節點過于稀疏時常導致斷鏈或者孤立節點。同時可以看到，所提的GRTTI協議的數據包到達率性能在不同節點數下均優于GPSR。因為當出現孤立節點或者斷鏈時，GPSR并無緩存措施只能丟棄數據包，而GR-TTI可通過攜帶轉發模式等待目的節點或者中繼節點出現，延長了響應包的生命周期，使得越稀疏的情況下GRTTI的數據包到達率性能優勢越明顯。且GR-TTI具有更準確的移動預測，從而更合理選擇下一跳中繼節點，實現更高的數據包到達率。

3.3 平均請求-響應延遲

當目的節點發出一次或多次請求后收到響應包，應統計其平均請求-響應延遲。該指標定義為對于有響應的請求，從第一次發出請求包時間到對應響應包到達目的節點的平均時間間隔。需要說明的是，發出請求而無法獲得響應的情況已體現在數據包到達率上，平均請求-響應延遲則表征成功獲得所需數據包的平均等待時長。圖4為節點從3增加到15時GR-TTI和GPSR平均請求-響應延遲性能曲線。

圖4 平均請求-響應延遲

從圖4可以看出，在節點密度稀疏的場景下，隨著節點數增大，兩個協議的平均請求-響應延遲均呈下降趨勢。因為節點數增多，源節點更容易尋找到合適的下一跳節點將數據傳給目的節點。同時也可以看到，GR-TTI的平均請求-響應延遲低于GPSR，因為GR-TTI能更準確預測目的節點位置，從而使得響應包更快抵達目的節點。

4 結 語

節點密度稀疏的無人機自組網絡容易造成鏈路不穩定和路由空洞，為了提高數據傳輸效率，提出了基于短時軌跡交互的貪婪路由協議。目的節點通過對自身短時軌跡的多項式曲線擬合，完成短時軌跡描述，并通過發布軌跡和運動信息的方式，使得源節點和中繼節點能更準確判斷其位置，從而增加數據包到達率。同時，修正傳統的貪婪轉發和攜帶轉發機制，以適應節點密度稀疏環境下拓撲高度動態變化﹑鏈路生存期短和路由空洞的問題。

[1] 卓琨,張衡陽,鄭博等.無人機自組網研究進展綜述[J].電信科學,2015,31 (04):128-138.

ZHUO Kun,ZHANG Heng-yang,ZHENG Bo,et al.Progress of UAV Ad Hoc Network:A Survey[J].Telecommunications Science,2015,31(04):128-138.

[2] 謝相博,徐光輝,范凱鑫等.基于4G的無人機遠程巡邏系統[J].通信技術,2015,48(11):1305-1309.

XIE Xiang-bo,XU Guang-hui,FAN Kai-xin,et al.UAV Remote Patrol System based on 4G[J].Communications Technology,2015,48(11):1305-1309.

[3] 王頂,趙頤軒,馬娟.無人機網絡環境下AODV協議的優化[J].計算機測量與控制,2013,21(06):1580-1583.

WANG Ding,ZHAO Yi-xuan,MA Juan.Optimization of AODV Routing Protocol for UAV Network[J].Computer Measurement & Control,2013,21(06):1580-1583.

[4] ROSATI S,KRU?ELECKI K,HEITZ G,et al.Dynamic Routing for Flying Ad Hoc Networks[J].IEEE Transactions on Vehicular Technology,2014,65(03):1690-1700.

[5] 劉濟銘,孟凡計,王玉文.一種具有速度與能量意識的路由協議[J].通信技術,2013,46(01):63-66.

LIU Ji-ming,MENG Fan-ji,WANG Yu-wen.Routing Protocol with Speed and Energy Awareness[J].Communications Technology,2013,46(01):63-66.

[6] 董思妤,張洪,王路.無人機自組網OLSR路由協議的優化[J].軍械工程學院學報,2017,29(02):67-70.

DONG Si-yu,ZHANG Hong,WANG Lu.Optimization of OLSR Routing Protocol in UAV Ad Hoc Network[J].Journal of Ordnance Engineering College,2017,29(02):67-70.

[7] HYLAND M T,MULLINS B E,BALDWIN R O,et al.Simulation-Based Performance Evaluation of Mobile Ad Hoc Routing Protocols in a Swarm of Unmanned Aerial Vehicles[C].International Conference on Advanced Information NETWORKING and Applications Workshops IEEE,2007:249-256.

[8] SHIRANI R,ST-HILAIRE M,KUNZ T,et al.The Performance of Greedy Geographic Forwarding in Unmanned Aeronautical Ad-Hoc Networks[C].Ninth Communication Networks and Services Research Conference,IEEE Computer Society,2011:161-166.

[9] 石祥濱,王鋒.無人機自組網絡多媒體數據傳輸路由算法研究[J].沈陽航空航天大學學報,2012,29(02):33-36.

SHI Xiang-Bin,WANG Feng.A Routing Algorithm for UAV Ad Hoc Networks Multimedia Data Transmission[J].Journal of Shenyang Institute of Aeronautical Engineering,2012,29(02):33-36.

[10] 李玉龍,黃國策,張衡陽等.移動預測的無人機自組網路由協議[J].空軍工程大學學報:自然科學版,2015,16(03):61-65.

LI Yu-long,HUANG Guo-ce,ZHANG Heng-yang,et al.A Routing Protocol Based on Mobility Prediction in UAV Ad Hoc Networks[J].Journal of Air Force Engineering University(Natural Science Edition),2015,16(03):61-65.

[11] 王俊,周樹道,朱國濤等.無人機航跡規劃常用算法[J].火力與指揮控制,2012,37(08):5-8.

WANG Jun,ZHOU Shu-dao,ZHU Guo-tao,et al.Research of Common Route Planning Algorithms for Unmanned Air Vehicle[J].Fire Control & Command Control,2012,37(08):5-8.

[12] 安瑩,王建新,劉耀等.延遲容忍網絡中一種基于概率接納和丟棄的擁塞控制算法[J].系統工程與電子技術,2014,36(03):553-563.

AN Ying,WANG Jian-xin,LIU Yao,et al.A Congestion Control Algorithm Based on Probabilistic Acceptance and Drop in Delay Tolerant Network[J].Systems Engineering and Electronics,2014,36(03):553-563.