基于移動(dòng)預(yù)測(cè)的無人機(jī)自組網(wǎng)GPSR—NMP協(xié)議

張國峰+李暉

摘要：本文針對(duì)無人機(jī)自組網(wǎng)內(nèi)部成員的運(yùn)動(dòng)特性，提出一種適用于無人機(jī)平滑飛行環(huán)境的移動(dòng)預(yù)測(cè)算法；針對(duì)節(jié)點(diǎn)的稀疏性，提出了一種適合用于無人機(jī)自組網(wǎng)的鄰節(jié)點(diǎn)篩選算法。鑒于GPSR協(xié)議周期性信標(biāo)交換算法在無人機(jī)自組網(wǎng)中存在的不足，重新定義信標(biāo)，結(jié)合鄰居列表維護(hù)機(jī)制及本預(yù)測(cè)算法對(duì)其進(jìn)行改進(jìn)，以使改進(jìn)的路由協(xié)議（命名為GPSR-for Sparsity UAV Ad Hoc network based on Neighbors' number and MobD/tv Predication，以下簡(jiǎn)稱GPSR-NMP）適用于無人機(jī)自組網(wǎng)環(huán)境。NS2的仿真結(jié)果表明，GPSR-NMP協(xié)議在無人機(jī)自組網(wǎng)中具有良好的適用性。

關(guān)鍵詞：無人機(jī)自組網(wǎng)；GPSR；位置預(yù)測(cè)；稀疏性

O 引言

無人機(jī)具有集群化的發(fā)展態(tài)勢(shì)，也就是向無人機(jī)白組網(wǎng)方向發(fā)展。無人機(jī)白組網(wǎng)是一種無人機(jī)動(dòng)態(tài)形成的無需借助任何中心站的多跳無線移動(dòng)通信網(wǎng)絡(luò)，多跳無線網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)同時(shí)具備收發(fā)器功能以及路由器功能，利用多跳方式將數(shù)據(jù)轉(zhuǎn)發(fā)距離較遠(yuǎn)的節(jié)點(diǎn)。因?yàn)闊o人機(jī)自身具有白組網(wǎng)節(jié)點(diǎn)的高移動(dòng)性，反應(yīng)路由不是最優(yōu)的，同時(shí)先應(yīng)路由維持路由表的方式產(chǎn)生大量的控制開銷。由于節(jié)點(diǎn)自身具備了定位計(jì)算能力，基于地理位置的不需要維護(hù)路由表的GPSR路由協(xié)議展現(xiàn)出了廣闊的應(yīng)用前景，但需結(jié)合具體場(chǎng)景進(jìn)一步改進(jìn)，以使其適用于高速運(yùn)動(dòng)的無人機(jī)網(wǎng)絡(luò)。隨后提出了參考期望域后再次改進(jìn)而得的先進(jìn)算法GPSR-EZ將GPSR算法以目標(biāo)節(jié)點(diǎn)的具體地理位置為主要依據(jù)的單點(diǎn)定向傳輸數(shù)據(jù)模式轉(zhuǎn)為區(qū)域多點(diǎn)傳送模式，以盡量避免目標(biāo)節(jié)點(diǎn)移動(dòng)情況下不能及時(shí)進(jìn)行數(shù)據(jù)內(nèi)容的傳輸突發(fā)狀況的發(fā)生。以位置矢量依據(jù)研究改良過的GPSR算法在深入探究GPSR-EZ算法后隨即指出，一旦選擇縮減期望域范圍，那么將會(huì)大大降低“多點(diǎn)轉(zhuǎn)發(fā)”的運(yùn)算實(shí)際工作量。提出的以不同距離、角度為參考的GPSR算法進(jìn)一步改進(jìn)后的以錯(cuò)開路由空洞為基本目標(biāo)的GPSR-AD算法，最大程度的利用地理位置信息提高網(wǎng)絡(luò)擴(kuò)展力度以達(dá)到無狀態(tài)路由數(shù)據(jù)傳輸?shù)哪康?。繞開了周邊模式的多跳與不可以及時(shí)回退的缺陷。提出的以極大轉(zhuǎn)發(fā)角為基礎(chǔ)的GPSR改進(jìn)協(xié)議GPSR-MAT的核心思想是：當(dāng)源節(jié)點(diǎn)發(fā)出數(shù)據(jù)內(nèi)容后，如果可沿路從路由空洞的切線處傳遞數(shù)據(jù)內(nèi)容，則更利于錯(cuò)開路由空洞；此協(xié)議可先進(jìn)行大量轉(zhuǎn)發(fā)，等遇到空洞后再轉(zhuǎn)入邊沿轉(zhuǎn)發(fā)，盡快找到最大角接點(diǎn)，再根據(jù)此節(jié)點(diǎn)向源節(jié)點(diǎn)所在方向傳遞數(shù)據(jù)內(nèi)容和情況反饋，在此之后，若在同一節(jié)點(diǎn)重復(fù)遇到路由空洞，則可選擇錯(cuò)開路由空洞再進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

1 問題描述

GPSR是以地理位置信息奠定基礎(chǔ)的無需進(jìn)行維護(hù)路由表工作的路由協(xié)議，網(wǎng)絡(luò)系統(tǒng)中各節(jié)點(diǎn)可依據(jù)自身定位設(shè)備來獲得具體位置信息，并將此位置信息以軸系性廣播的信標(biāo)傳送出去，在接收范圍內(nèi)的節(jié)點(diǎn)接收該信息以獲取鄰節(jié)點(diǎn)的地理位置信息，用以維護(hù)鄰居表。但周期性信標(biāo)僅適用于低速白組織網(wǎng)絡(luò)，對(duì)于高速變化的稀疏性無人機(jī)網(wǎng)絡(luò)，信標(biāo)不能反映出網(wǎng)絡(luò)稠密程度，導(dǎo)致無效跳數(shù)增加；驗(yàn)證了GPSR算法僅適用于部署密度較高的網(wǎng)絡(luò)；GPSR不具備預(yù)測(cè)白適應(yīng)過濾無效節(jié)點(diǎn)能力，導(dǎo)致錯(cuò)誤路由決策。GPSR信標(biāo)格式見表1。

2 提出協(xié)議算法

為從無人機(jī)自組織網(wǎng)絡(luò)稀疏性和節(jié)點(diǎn)運(yùn)動(dòng)性這兩方面解決無人機(jī)飛行環(huán)境中的鄰居表維護(hù)問題，分別從信標(biāo)隱藏信息、位置預(yù)測(cè)以及信表信息適當(dāng)提取等三個(gè)方面進(jìn)一步優(yōu)化GPSR協(xié)議，協(xié)議優(yōu)化后稱之為GPSR-NMP。

2.1 信標(biāo)交換算法

定義信標(biāo)形式及內(nèi)容，信標(biāo)內(nèi)包含節(jié)點(diǎn)標(biāo)識(shí)id，用于標(biāo)識(shí)節(jié)點(diǎn)唯一識(shí)別號(hào)；即時(shí)地理信息、快速預(yù)測(cè)地理信息以及自身速度信息，適用于相鄰節(jié)點(diǎn)進(jìn)行信標(biāo)處理時(shí)運(yùn)動(dòng)性白適應(yīng)過濾鄰節(jié)點(diǎn)；鄰居數(shù)量信息，用于稀疏性白適應(yīng)過濾鄰節(jié)點(diǎn)；時(shí)間戳，用于標(biāo)識(shí)信標(biāo)發(fā)出時(shí)間。網(wǎng)絡(luò)中所有節(jié)點(diǎn)的通信半徑均相同。如圖1數(shù)據(jù)包轉(zhuǎn)發(fā)路徑所示。

S為源節(jié)點(diǎn)，D為目的節(jié)點(diǎn)，A有鄰居節(jié)點(diǎn)B和C，B僅有鄰居節(jié)點(diǎn)A，C有鄰居節(jié)點(diǎn)A、E、F，且節(jié)點(diǎn)B與目的節(jié)點(diǎn)D之間的距離比C與D之間的距離更近，由于轉(zhuǎn)發(fā)節(jié)點(diǎn)A檢測(cè)到鄰居節(jié)點(diǎn)B的鄰居節(jié)點(diǎn)數(shù)量是1，鄰居節(jié)點(diǎn)C的鄰居節(jié)點(diǎn)數(shù)量多于1，那么轉(zhuǎn)發(fā)節(jié)點(diǎn)A將選擇節(jié)點(diǎn)C為下一跳進(jìn)行數(shù)據(jù)傳輸。如果轉(zhuǎn)發(fā)節(jié)點(diǎn)A的鄰居節(jié)點(diǎn)B僅有轉(zhuǎn)發(fā)節(jié)點(diǎn)A-個(gè)鄰居節(jié)點(diǎn)，那么節(jié)點(diǎn)B無法作為下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。此時(shí)使用的轉(zhuǎn)發(fā)方式是，加入轉(zhuǎn)發(fā)節(jié)點(diǎn)距離目的節(jié)點(diǎn)比之轉(zhuǎn)發(fā)節(jié)點(diǎn)距離其它轉(zhuǎn)發(fā)節(jié)點(diǎn)都近，由此轉(zhuǎn)發(fā)節(jié)點(diǎn)將首先篩選鄰居列表中顯示鄰居節(jié)點(diǎn)數(shù)量不低于1的鄰居節(jié)點(diǎn)，于鄰居節(jié)點(diǎn)數(shù)量不低于1的鄰居節(jié)點(diǎn)中選擇與目的節(jié)點(diǎn)距離最近的節(jié)點(diǎn)當(dāng)作下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)；在實(shí)際轉(zhuǎn)發(fā)過程中不會(huì)選用平面化這種算法，而會(huì)選擇使用貪婪方式進(jìn)行轉(zhuǎn)發(fā)，并且允許下一跳節(jié)點(diǎn)距離目的節(jié)點(diǎn)比自己距離目的節(jié)點(diǎn)更遠(yuǎn)。轉(zhuǎn)發(fā)節(jié)點(diǎn)工作流程如圖2示。

各節(jié)點(diǎn)實(shí)施信標(biāo)封裝傳送時(shí)，需將自己的ID信息、實(shí)時(shí)地理位置信息、快速預(yù)測(cè)位置信息、自身速度及鄰居節(jié)點(diǎn)數(shù)量填入直接信標(biāo)幀，信標(biāo)即時(shí)發(fā)送時(shí)間為探索自身實(shí)時(shí)地理位置取得一定時(shí)間，如表2信標(biāo)幀形式。

2.2 節(jié)點(diǎn)位置預(yù)測(cè)

因?yàn)镚PSR-NMP協(xié)議選擇使用周期性信標(biāo)，所以可將無人機(jī)駕駛地理坐標(biāo)與時(shí)間之間的關(guān)系記為表3的形式。

逐步分解節(jié)點(diǎn)飛行軌跡，如圖3，對(duì)x軸，假設(shè)描述節(jié)點(diǎn)在X軸方向隨時(shí)間t的運(yùn)動(dòng)軌跡為x（t），是由方程（1）描述的一個(gè)N階多項(xiàng)式：

如果用的前k個(gè)時(shí)刻的值x（t-K+l），…，x（t）來預(yù)測(cè)多項(xiàng)式（1）將來值x，即

式（2）是以（k=0，1，…，K-l）為系數(shù)的有限長沖擊響應(yīng)（FIR）濾波器。采用式（2）中預(yù)測(cè)濾波器來建立適合多項(xiàng)式方式的信號(hào)時(shí)，均采用該多項(xiàng)式先驗(yàn)信息：

當(dāng)T=l，N=2時(shí)，

式中：k=0，l….，K-l。根據(jù)下方式子分析，分別采用五組數(shù)值來預(yù)測(cè)解算，K=5，那么對(duì)v軸方向應(yīng)用龍格庫塔算法有：endprint

K₁，K₂，K₃，K₄分別是（X_t-4，X_t-3），（X_t-3，X_t-2），（X_t-2，x_t-1），（x_t-1一.x_t）區(qū)間的直線斜率。

2.3 信標(biāo)消息提取與鄰居列表更新

如圖4節(jié)點(diǎn)運(yùn)動(dòng)信息示意圖所示，B是A的實(shí)時(shí)鄰居節(jié)點(diǎn)，A，J是B的實(shí)時(shí)鄰居節(jié)點(diǎn)，A'是A下一時(shí)刻的預(yù)測(cè)位置，J'是J下一時(shí)刻的預(yù)測(cè)位置，節(jié)點(diǎn)B發(fā)送信標(biāo)前將白身的ID、實(shí)時(shí)地理信息、一步預(yù)測(cè)地理信息，鄰居節(jié)點(diǎn)數(shù)量信息加入信標(biāo)幀。

對(duì)應(yīng)于信標(biāo)消息實(shí)測(cè)位置為（nxi，nyl），預(yù)測(cè)位置為（nX₂，ny₂），速度為nv；接收節(jié)點(diǎn)實(shí)測(cè)位置為（myx₁，myy₁），預(yù)測(cè)位置為（myx₂，myy₂），速度為myv。接收節(jié)點(diǎn)在收到信標(biāo)后，獲取自己的鄰居信息。結(jié)合自身速度、信標(biāo)速度以及通信半徑R的結(jié)合實(shí)施節(jié)點(diǎn)白行適應(yīng)過濾，過濾系數(shù)為M。則鄰居節(jié)點(diǎn)運(yùn)動(dòng)步長：接收信標(biāo)節(jié)點(diǎn)運(yùn)動(dòng)步長：分別對(duì)預(yù)測(cè)位置（X，Y）進(jìn)行修正：則，計(jì)算修正后的節(jié)點(diǎn)A和節(jié)點(diǎn)B之間的預(yù)測(cè)距離nmL：若（nmL-R）<0，則再結(jié)合信標(biāo)中顯示的鄰居節(jié)點(diǎn)數(shù)量，按照3.1節(jié)中的方法篩選過濾后提取符合傳輸要求的鄰居信息，將其添入鄰居列表，鄰節(jié)點(diǎn)白適應(yīng)篩選過程如圖5。然后更新自身的鄰居節(jié)點(diǎn)數(shù)量。鄰居表存儲(chǔ)格式見表4。

4 仿真結(jié)果

圖6是GPSR-NMP協(xié)}義在不同速率下，不同的鄰節(jié)點(diǎn)的鄰居數(shù)量限制下（以下簡(jiǎn)稱限制數(shù)量）與投遞成功率的關(guān)系圖。GPSR-NMP加入了鄰居節(jié)點(diǎn)鄰居數(shù)量檢測(cè)機(jī)制，在轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)下一跳節(jié)點(diǎn)優(yōu)先選擇無鄰居節(jié)點(diǎn)即鄰居數(shù)量為0時(shí)的協(xié)議。并將所檢測(cè)轉(zhuǎn)發(fā)節(jié)點(diǎn)的鄰居表中是否存在目的節(jié)點(diǎn)條目，若存在則選擇目的節(jié)點(diǎn)作為下一跳，即將數(shù)據(jù)包交付給目的節(jié)點(diǎn)；與之相反即不存在則選擇檢查轉(zhuǎn)發(fā)節(jié)點(diǎn)中剩余鄰居條目，首先檢查鄰居條目中的鄰居數(shù)量是否多余1，若不多余1則跳過，若多余1則選擇距離目的節(jié)點(diǎn)位置最近的鄰居節(jié)點(diǎn)作為下一跳進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。當(dāng)限制數(shù)量設(shè)定為2時(shí)，轉(zhuǎn)發(fā)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)除轉(zhuǎn)發(fā)節(jié)點(diǎn)以外，還存在一個(gè)鄰居節(jié)點(diǎn)；如果不設(shè)置上限數(shù)量，那么轉(zhuǎn)發(fā)節(jié)點(diǎn)在選擇下一跳只有轉(zhuǎn)發(fā)節(jié)點(diǎn)是其鄰居節(jié)點(diǎn)，徒增跳數(shù)以及投遞成功率下降。結(jié)果表明，在檢測(cè)機(jī)制設(shè)置限制數(shù)量為2時(shí)，投遞成功率是最好的。

圖7是GPSR-NMP.GPSR和GPSR-I三種協(xié)議速度與投遞成功率的關(guān)系圖。GPSR-NMP協(xié)議中采用了重新定義的信標(biāo)，結(jié)合移動(dòng)預(yù)測(cè)算法，使維護(hù)的鄰居表更為逼近于真實(shí)的無人機(jī)網(wǎng)絡(luò)成員空間分布，減少了無效跳數(shù)，投遞成功率有效提升。與高速場(chǎng)景相比，低速場(chǎng)景很少發(fā)生鄰居節(jié)點(diǎn)移動(dòng)情況，因此仿真結(jié)果顯示的三種協(xié)議之間的投遞成功率相差很微弱；由于速率的提高，鄰居節(jié)點(diǎn)移動(dòng)越發(fā)頻繁，此時(shí)具備移動(dòng)預(yù)測(cè)能力的GPSR-NMP協(xié)議顯現(xiàn)了其投遞成功率的優(yōu)勢(shì)。

圖8是GPSR-NMP.GPSR和GPSR-I三種協(xié)議速度與時(shí)延的關(guān)系圖。由于相對(duì)于高速場(chǎng)景，在低速場(chǎng)景中，極少出現(xiàn)鄰居節(jié)點(diǎn)移動(dòng)的情況，因此仿真結(jié)果顯示三種協(xié)議的投遞成功率差距十分微弱；由于速率的提高，鄰居節(jié)點(diǎn)移動(dòng)頻率越發(fā)頻繁，擁有移動(dòng)預(yù)測(cè)能力的GPSR-NMP協(xié)議開始展示了其投遞成功率的優(yōu)勢(shì)。

圖9是GPSR-NMP.GPSR和GPSR-I三種協(xié)議速度與平均吞吐量的關(guān)系圖。與GPSR和GPSR-I兩

種協(xié)議相比，GPSR-NMP協(xié)議維護(hù)的鄰居信息十分精確；由于節(jié)點(diǎn)速率加快，平均吞吐量皆逐漸開始顯H{下降趨勢(shì)，但GPSR-NMP協(xié)議平均吞吐量的下降趨勢(shì)整體低于另外兩種協(xié)議，特別是在高速場(chǎng)景中圖8平均端對(duì)端時(shí)延對(duì)比這種優(yōu)勢(shì)更為明顯。

圖10是GPSR-NMP，GPSR和GPSR-I三種協(xié)議在[20，200]m/s速率區(qū)間內(nèi)，6000*6000米拓?fù)浞秶鷥?nèi)節(jié)點(diǎn)數(shù)量與平均吞吐量的關(guān)系圖。由圖中信息可以得知，在節(jié)點(diǎn)密度較低的情況下，三種協(xié)議吞吐量均較低；節(jié)點(diǎn)密度為21個(gè)/3 6l∞2時(shí)，GPSR-NMP協(xié)議的吞吐量與GPSR協(xié)議相比，GPSR-I吞吐量明顯提升；由于節(jié)點(diǎn)密度的不斷提高，GPSR-NMP協(xié)議的平均吞吐量趨勢(shì)逐漸緩和，與之相反，GPSR，GPSR-I協(xié)議的吞吐量卻穩(wěn)步提升，當(dāng)節(jié)點(diǎn)密度水平較高時(shí)，三種協(xié)議的平均吞吐量幾乎相同。仿真結(jié)果表明，GPSR-NMP協(xié)議與GPSR，GPSR-I協(xié)議先比，其對(duì)稀疏性無人機(jī)網(wǎng)絡(luò)具有更好的性能。

5 結(jié)束語

本文提出了基于移動(dòng)預(yù)測(cè)的無人機(jī)白組網(wǎng)GPSR-NMP協(xié)議，并重點(diǎn)研究分析了限制數(shù)量和移動(dòng)預(yù)測(cè)對(duì)GPSR協(xié)議性能的影響。使用NS2對(duì)GPSR，GPSR-I和GPSR-NMP三種算法在不同速率、限制數(shù)下實(shí)施仿真輸出跟蹤數(shù)據(jù)，并采用awk語言分析時(shí)延，統(tǒng)計(jì)分析不同算法下吞吐量及投遞成功率，運(yùn)用gnuplot畫圖工具以圖像形式呈現(xiàn)結(jié)果；根據(jù)仿真結(jié)果圖像表明，本文根據(jù)無人機(jī)白組網(wǎng)特性深入研究，之后提出具備移動(dòng)預(yù)測(cè)能力的稀疏性GPSR-NMP協(xié)議，其投遞成功率的提升、吞吐量和時(shí)延降低方面有著較好的性能。endprint