基于卡爾曼-DNN預(yù)測的UANET路由協(xié)議

徐一航，王 傲，楊錦彬，李大鵬

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引言

無人機(jī)自組織網(wǎng)絡(luò)(Unmanned Aerial Vehicles Ad Hoc Network,UANET)具有靈活動態(tài)組網(wǎng)、自愈性與抗攻擊強(qiáng)的特點[1-3]，它將每個無人機(jī)作為通信節(jié)點[4]，用于各個無人機(jī)之間實現(xiàn)各種信息交互，是大規(guī)模無人機(jī)作戰(zhàn)效能的根本保障。在高速移動的無人機(jī)場景下，UANET具有鏈路變化快[5]、時延敏感的特點，導(dǎo)致了UANET拓?fù)渥兓l繁，路由信息易丟失。傳統(tǒng)的路由協(xié)議用于高速運(yùn)動的無人機(jī)自組網(wǎng)時會導(dǎo)致鏈路中斷，將嚴(yán)重影響集群飛行控制與集群編隊任務(wù)的完成[6]，需要在原有路由協(xié)議的基礎(chǔ)上設(shè)計新的路由協(xié)議。

目前，國內(nèi)外對于移動自組織網(wǎng)絡(luò)的研究主要集中于路由協(xié)議的優(yōu)化，而基于移動自組織網(wǎng)絡(luò)衍生出的無人機(jī)自組織網(wǎng)絡(luò)與傳統(tǒng)移動自組織網(wǎng)絡(luò)的不同在于各節(jié)點移動速度較高[7]。受制于各無人機(jī)節(jié)點通信距離的限制，快速移動的無人機(jī)節(jié)點會嚴(yán)重影響數(shù)據(jù)包分組到達(dá)率、端到端時延等關(guān)鍵性能指標(biāo)，傳統(tǒng)的網(wǎng)絡(luò)協(xié)議無法適用[8-9]。李玉龍等人[10]提出了基于移動預(yù)測與鏈路保持的路由協(xié)議，該協(xié)議綜合考量了節(jié)點位置與鏈路質(zhì)量來選擇下一跳，減緩了節(jié)點高速移動帶來的不利因素；郭科兵等人[11]對節(jié)點已有路徑進(jìn)行貪婪轉(zhuǎn)發(fā)，進(jìn)行偏移地修正，能有效減少控制包開銷；王廣彧等人[12]使用了基于卡爾曼濾波的位置預(yù)測模型來預(yù)測鄰居節(jié)點的位置；文獻(xiàn)[13-15]基于機(jī)器學(xué)習(xí)技術(shù)提出了節(jié)點位置預(yù)測算法，此類算法的預(yù)測精度較傳統(tǒng)算法有了一定的提升；白曉萌等人[16]提出了改進(jìn)的周界無狀態(tài)路由算法,該算法考慮了節(jié)點的速度和方向,并根據(jù)節(jié)點的當(dāng)前速度計算之后某一時間內(nèi)節(jié)點的位置選擇最佳中繼節(jié)點；王沁飛等人[17]使用了灰度預(yù)測-WNN聯(lián)合預(yù)測模型來獲得節(jié)點移動狀態(tài)評價因子，并綜合該因子設(shè)計了一個分簇路由協(xié)議。

為了提高鄰居節(jié)點信息的準(zhǔn)確性，加強(qiáng)節(jié)點間鏈路的穩(wěn)定性，兼顧預(yù)測模型的復(fù)雜度，本文提出了一個基于卡爾曼-DNN位置預(yù)測的路由協(xié)議。

1 基于卡爾曼-DNN的節(jié)點位置預(yù)測

卡爾曼-DNN位置預(yù)測模型由兩部分組成：第一部分是卡爾曼濾波對節(jié)點位置進(jìn)行預(yù)測，第二部分是基于DNN神經(jīng)網(wǎng)絡(luò)修正卡爾曼預(yù)測的位置。

1.1 基于卡爾曼的節(jié)點位置預(yù)測

s(n)=[x,vx,y,vy]T。

(1)

無人機(jī)的運(yùn)動模型[18]為：

(2)

式(2)中，設(shè)：

(3)

(4)

式中，Ti為UANET協(xié)議中離散時間事件處理的時間間隔，θ為無人機(jī)節(jié)點在n時刻的相對偏轉(zhuǎn)角。則狀態(tài)轉(zhuǎn)移矩陣A可根據(jù)式(4)表示為：

(5)

卡爾曼觀測向量即為n時刻實際的位置與速度向量x(n)。x(n)可由觀測系數(shù)矩陣C、獨立同分布的零均值白噪聲向量w(n)與k(n)表示為：

x(n)=C·s(n)+k(n)。

(6)

s(n+1|n+1)=A·s(n|n)+w(n)。

(7)

設(shè)n時刻預(yù)測輸出誤差協(xié)方差矩陣為P(n)，白噪聲過程w(n)與k(n)的協(xié)方差矩陣分別為COVw和COVk，則有：

P(n)=A·U(n)·AT+COVw,

(8)

U(n)可由卡爾曼增益Gn：

Gn=P(n)·CT·[C·P(n)·CT+COVk]-1,

(9)

表示為：

U(n)=[I-C·Gn]·P(n)。

(10)

則卡爾曼最佳預(yù)測輸出s(n+1|n+1)可表示為：

s(n+1|n+1)=A·s(n|n)+

Gn·[x(n)-A·C·s(n|n)]。

(11)

1.2 DNN修正卡爾曼的預(yù)測值

H=f(w·s+b)。

(12)

當(dāng)前層的輸出即為下一層的輸入。按照式(12)進(jìn)行前向傳播最終得到DNN的輸出On。本文使用Sigmoid激活函數(shù)：

(13)

神經(jīng)網(wǎng)絡(luò)的訓(xùn)練使用樣本空間u且以最小均方誤差E為準(zhǔn)則進(jìn)行：

(14)

式中，p為節(jié)點在下一時刻的實際位置。設(shè)網(wǎng)絡(luò)的學(xué)習(xí)率為lr,則反向傳播過程中權(quán)值更新公式可表示為：

(15)

在節(jié)點工作階段，當(dāng)節(jié)點的位置信息經(jīng)卡爾曼濾波計算獲得預(yù)測值后，輸入到DNN神經(jīng)網(wǎng)絡(luò)中，再經(jīng)過DNN的前向傳播，最終獲得節(jié)點在下一時刻位置預(yù)測修正值[x″,y″]T。

1.3 模型結(jié)構(gòu)

圖1 基于卡爾曼-DNN的位置預(yù)測模型Fig.1 Structure diagram of prediction model

1.4 復(fù)雜度分析

定義以下3種矩陣運(yùn)算的復(fù)雜度：

① 矩陣乘法。S∈Rn×m,V∈Rm×k，S·V的復(fù)雜度為nmk;

② 矩陣加法。S∈Rn×m,V∈Rn×m，S+V的復(fù)雜度為nm;

③ 矩陣的逆運(yùn)算。S∈Rn×n，S-1的復(fù)雜度為n3。

根據(jù)上述矩陣運(yùn)算復(fù)雜度的定義，對卡爾曼濾波復(fù)雜度、卡爾曼-DNN復(fù)雜度以及RNN循環(huán)神經(jīng)網(wǎng)絡(luò)的復(fù)雜度進(jìn)行計算。為簡便分析，設(shè)卡爾曼輸入的維度為n×1，狀態(tài)轉(zhuǎn)移矩陣A的維度為n×n；DNN的輸入為n個神經(jīng)元，隱藏層有兩層，分別有i個神經(jīng)元與j個神經(jīng)元；循環(huán)神經(jīng)網(wǎng)絡(luò)RNN輸入為k個神經(jīng)元，隱藏層設(shè)u。復(fù)雜度計算結(jié)果如表1所示。

表1 模型復(fù)雜度Tab.1 Model complexity

文中，卡爾曼的輸入為4×1，因此n為4；DNN隱藏層i設(shè)為12，j設(shè)為4。則卡爾曼復(fù)雜度為388，卡爾曼-DNN復(fù)雜度為492。相較于卡爾曼預(yù)測模型，卡爾曼-DNN預(yù)測模型復(fù)雜度增加了104。

2 基于卡爾曼-DNN預(yù)測的路由協(xié)議

現(xiàn)有的路由算法中，鄰居節(jié)點大多依靠周期的廣播路由信令包來獲取鄰居節(jié)點信息。若在廣播周期內(nèi)，節(jié)點快速移動，鄰居節(jié)點可能已經(jīng)離開本節(jié)點的通信范圍，但本節(jié)點并不能探測到這種情況。基于此，本文以GPSR路由協(xié)議為基礎(chǔ)，根據(jù)卡爾曼-DNN節(jié)點位置預(yù)測結(jié)果更新鄰居表與路由信息。

2.1 基于位置預(yù)測的鄰居發(fā)現(xiàn)方法

假設(shè)無人機(jī)節(jié)點工作在二維平面。各個無人機(jī)節(jié)點開機(jī)后，每個節(jié)點首先廣播Hello包發(fā)現(xiàn)鄰居。Hello包中含發(fā)送節(jié)點的節(jié)點號、鄰居表、節(jié)點的位置與速度信息、鏈路質(zhì)量值PQ。當(dāng)無人機(jī)節(jié)點收到自身一跳鄰居的發(fā)現(xiàn)信令后，如果鄰居表中沒有對應(yīng)的節(jié)點號，節(jié)點會為該鄰居建立鄰居表，并根據(jù)Hello包中的鄰居表建立本節(jié)點的兩跳鄰居信息。此外節(jié)點還會額外建立一個記錄各鄰居節(jié)點位置與速度信息的表Ta(x,vx,y,vy)；如果收到的Hello包對應(yīng)的節(jié)點已經(jīng)存在與本節(jié)點的鄰居表中，則更新PQ值與位置信息。

(16)

計算與鄰居節(jié)點的距離。設(shè)節(jié)點當(dāng)前的位置為(x,y)，如果D小于某個閾值th，則暫時不廣播Hello包；如果D>th則判定該一跳鄰居在下一時刻失效，節(jié)點會啟動一個定時器，定時的時長t為：

(17)

式中，V為節(jié)點移動的速度。當(dāng)定時器超時事件發(fā)生后，節(jié)點刪除失效的一跳鄰居節(jié)點；若D大于2th，同樣刪除失效的兩跳鄰居節(jié)點。更新完成后，節(jié)點需要廣播包含新鄰居信息的Hello包，其他節(jié)點在接收到該Hello包后更新相關(guān)鄰居信息，并重新計算PQ值。PQ值將作為路由轉(zhuǎn)發(fā)的依據(jù)，PQ值的定義為:

(18)

式中，PQ0為當(dāng)前節(jié)點鄰居表中對應(yīng)的鄰居節(jié)點所記錄的PQ值，PQ1為鄰居信令包中存儲的PQ值。信令包中存儲的PQ值為該鄰居節(jié)點內(nèi)的PQ值。除了本節(jié)點到本節(jié)點的PQ初始值設(shè)置設(shè)為PQ_MAX以外，本節(jié)點到其他節(jié)點的PQ值均設(shè)為PQ_MIN。每當(dāng)節(jié)點收到Hello包時，PQ值會根據(jù)式(18)進(jìn)行更新；如果PQ大于等于存儲于本節(jié)點路由表所對應(yīng)的信令包源節(jié)點的PQ值，表示該鏈路質(zhì)量更優(yōu)，使用該P(yáng)Q值替換當(dāng)前節(jié)點一跳鄰居表內(nèi)的PQ0。

如果某個節(jié)點的鄰居一直沒有超出通信范圍，該節(jié)點將長時間不廣播Hello包。當(dāng)一個新的節(jié)點移動到本節(jié)點的通信范圍內(nèi)，會導(dǎo)致這個新加入的節(jié)點長時間收不到自身鄰居節(jié)點的信令而無法更新該節(jié)點的鄰居信息。因此需要設(shè)置一個定時器，當(dāng)節(jié)點在定時時間TIMER_UPDATE_MSG內(nèi)都沒有鄰居節(jié)點更新事件發(fā)生，則廣播一個Hello包，其他節(jié)點收到該Hello包后按照上述方式?jīng)Q定是否更新鄰居表與PQ值。

基于卡爾曼-DNN位置預(yù)測的鄰居發(fā)現(xiàn)流程如圖2所示。

圖2 基于卡爾曼-DNN位置預(yù)測的鄰居發(fā)現(xiàn)流程Fig.2 Flowchart of neighbor tablediscovery based on Kalman and DNN

2.2 路由轉(zhuǎn)發(fā)策略

本文在GPSR協(xié)議的基礎(chǔ)上通過基于位置預(yù)測的鄰居發(fā)現(xiàn)方法，以貪婪模式與周邊模式完成數(shù)據(jù)分組的轉(zhuǎn)發(fā)，提高了數(shù)據(jù)分組傳輸?shù)目煽啃浴８鞴?jié)點轉(zhuǎn)發(fā)數(shù)據(jù)分組的步驟如下：

① 節(jié)點存在待發(fā)送的數(shù)據(jù)分組時，判斷目的節(jié)點是否在本節(jié)點的一跳鄰居范圍內(nèi)；若是則將該數(shù)據(jù)分組發(fā)送至目的節(jié)點，否則轉(zhuǎn)到②。

② 檢查鄰居節(jié)點是否存在路由空洞，若存在，根據(jù)一跳與兩跳鄰居表尋找比該鄰居節(jié)點到目的節(jié)點更近的節(jié)點，若沒有找到這樣的節(jié)點，根據(jù)周邊轉(zhuǎn)發(fā)尋找下一跳。若不存在路由空洞，則按照貪婪模式，結(jié)合鄰居節(jié)點中較大的PQ值尋找節(jié)點的下一跳地址。按照上述方式，若尋找到下一跳地址，轉(zhuǎn)到④；否則，轉(zhuǎn)到③。

③ 將該數(shù)據(jù)分組存入到節(jié)點待發(fā)送數(shù)據(jù)隊列中。當(dāng)存在鄰居節(jié)點加入到本節(jié)點的一跳鄰居范圍時，轉(zhuǎn)到①。

④ 數(shù)據(jù)分組轉(zhuǎn)發(fā)至下一跳。沿用上述轉(zhuǎn)發(fā)策略直至數(shù)據(jù)分組到達(dá)目的節(jié)點。

3 仿真與分析

本文使用QualNet平臺對基于卡爾曼-DNN位置預(yù)測的路由協(xié)議(KDPR)進(jìn)行仿真驗證，并與GPSR協(xié)議以及基于卡爾曼濾波預(yù)測的路由協(xié)議(KFN)進(jìn)行對比分析。節(jié)點的移動方式采用隨機(jī)移動(Random Waypoint)；通信方式采用跳頻模式。具體參數(shù)如表2所示。

表2 仿真參數(shù)配置Tab.2 Simulation parameter settings

實驗中以仿真方式模擬節(jié)點在2 km×2 km的區(qū)域中移動。首先收集在該區(qū)域內(nèi)節(jié)點移動的信息，接著將位置信息作為卡爾曼濾波的輸入，經(jīng)卡爾曼濾波處理后得到預(yù)測輸出向量s=[x′,v′x,y′,v′y]T，即DNN的訓(xùn)練輸入，并根據(jù)觀測值更新卡爾曼相關(guān)參數(shù)。DNN神經(jīng)網(wǎng)絡(luò)將下一刻節(jié)點位置的實際值作為神經(jīng)網(wǎng)絡(luò)訓(xùn)練的標(biāo)簽p=[x,y]T，則[s,p]構(gòu)成了DNN的訓(xùn)練集。找到網(wǎng)絡(luò)收斂最佳的訓(xùn)練次數(shù)并保存網(wǎng)絡(luò)權(quán)值參數(shù)w，b。

本文使用3個指標(biāo)衡量基于KDPR的路由協(xié)議的性能：端到端時延、分組投遞率和鄰居錯誤率。設(shè)jm為節(jié)點m的所有鄰居個數(shù)，im為節(jié)點m鄰居表中不是m的鄰居但沒有被刪除的節(jié)點的個數(shù)，平均鄰居錯誤率AVGNER定義為：

(19)

圖3表示對一個節(jié)點的10個連續(xù)離散時刻位置使用卡爾曼、卡爾曼-DNN和RNN三種預(yù)測模型產(chǎn)生的預(yù)測誤差。設(shè)RNN的輸入k為2，隱藏層u為28，根據(jù)表1可計算RNN的復(fù)雜度為1 652。從圖3可以看出，卡爾曼-DNN與RNN的平均預(yù)測誤差相較于卡爾曼預(yù)測誤差有所降低?？柭?DNN平均預(yù)測誤差為2.24，RNN平均預(yù)測誤差為1.87，二者預(yù)測精度相差0.37 m，而卡爾曼-DNN模型復(fù)雜度相較于RNN模型降低了1 160。在預(yù)測精度相差不大的情況下，相較于RNN預(yù)測模型，卡爾曼-DNN在模型復(fù)雜度上的優(yōu)勢較為明顯。

圖3 預(yù)測誤差Fig.3 Error of prediction

圖4表示無人機(jī)移動速度在10～40 m/s時的鄰居錯誤率。在不同的節(jié)點移動速度場景下，基于KDPR的路由協(xié)議相較于KFN協(xié)議與GPSR協(xié)議降低了鄰居發(fā)現(xiàn)的錯誤率。由于加入了鄰居預(yù)測機(jī)制，使得KDPR協(xié)議與KFN協(xié)議能夠更準(zhǔn)確地發(fā)現(xiàn)將要離開自身一跳、兩跳范圍的鄰居節(jié)點。

圖4 鄰居平均錯誤率Fig.4 Average neighbor error rate

圖5表示無人機(jī)移動速度在10～40 m/s時的分組投遞率，由圖中可以看出，KDPR路由相較于GPSR與KFN提高了網(wǎng)絡(luò)整體的分組投遞率。在節(jié)點移動速度較高時，節(jié)點在鏈路預(yù)測機(jī)制的作用下減少了分組的轉(zhuǎn)發(fā)次數(shù)，相較于其他兩種算法有一定的性能優(yōu)勢。而GPSR沒有對鄰居節(jié)點進(jìn)行預(yù)測，這導(dǎo)致在節(jié)點移動速度較高時，轉(zhuǎn)發(fā)數(shù)據(jù)分組無法找到本節(jié)點的中繼節(jié)點，需要重新發(fā)送信令包尋路，影響網(wǎng)絡(luò)整體的分組投遞率。

圖5 分組投遞率Fig.5 Packet delivery fraction

圖6表示無人機(jī)移動速度在10～40 m/s時不同協(xié)議端到端的傳輸時延。隨著節(jié)點移動速度的升高，端到端時延不斷增加。移動速度較低時，相較于KFN算法并沒有明顯改善。但在節(jié)點移動速度相對較高時，由于KDPR路由協(xié)議提高了鏈路選擇的準(zhǔn)確性，因此，平均端到端時延相較于GPSR算法與KFN算法有了一定的改善。

圖6 端到端時延Fig.6 End-to-end delay

在對場景進(jìn)行仿真實驗可以看出，算法在平均鄰居發(fā)現(xiàn)錯誤率上要優(yōu)于經(jīng)典算法和相關(guān)改進(jìn)算法，表明在使用節(jié)點預(yù)測后的協(xié)議可以提升協(xié)議的性能。此外，由于鄰居被正確的發(fā)現(xiàn)，提高了路由正確率，降低了鄰居信息的錯誤概率，特別是在鄰居節(jié)點移動速度較高時較為明顯。但每當(dāng)節(jié)點預(yù)測自己的鄰居節(jié)點發(fā)生變化時，都需要向自身的鄰居節(jié)點發(fā)送Hello包，而如果某個節(jié)點在預(yù)測周期內(nèi)都產(chǎn)生了鄰居更新事件，那么頻繁地發(fā)送Hello包將會加重路由的開銷。未來需要對上述問題進(jìn)行分析。

4 結(jié)論

本文在現(xiàn)有的節(jié)點位置預(yù)測路由協(xié)議研究與分析的基礎(chǔ)上，提出了一種新的節(jié)點位置預(yù)測模型，并設(shè)計了KDPR路由協(xié)議。在協(xié)議工作的過程中，每個節(jié)點根據(jù)自身的鄰居節(jié)點特性預(yù)測各鄰居的位置，能夠改善因節(jié)點快速移動導(dǎo)致鏈路中斷的問題。最后，分析了本協(xié)議相較于其他協(xié)議的優(yōu)點，同時提出了本研究存在的問題以及后續(xù)需要進(jìn)一步攻關(guān)的方向。