基于卡爾曼-DNN預測的UANET路由協議

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

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

0 引言

無人機自組織網絡(Unmanned Aerial Vehicles Ad Hoc Network,UANET)具有靈活動態組網、自愈性與抗攻擊強的特點[1-3]，它將每個無人機作為通信節點[4]，用于各個無人機之間實現各種信息交互，是大規模無人機作戰效能的根本保障。在高速移動的無人機場景下，UANET具有鏈路變化快[5]、時延敏感的特點，導致了UANET拓撲變化頻繁，路由信息易丟失。傳統的路由協議用于高速運動的無人機自組網時會導致鏈路中斷，將嚴重影響集群飛行控制與集群編隊任務的完成[6]，需要在原有路由協議的基礎上設計新的路由協議。

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

為了提高鄰居節點信息的準確性，加強節點間鏈路的穩定性，兼顧預測模型的復雜度，本文提出了一個基于卡爾曼-DNN位置預測的路由協議。

1 基于卡爾曼-DNN的節點位置預測

卡爾曼-DNN位置預測模型由兩部分組成：第一部分是卡爾曼濾波對節點位置進行預測，第二部分是基于DNN神經網絡修正卡爾曼預測的位置。

1.1 基于卡爾曼的節點位置預測

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

(1)

無人機的運動模型[18]為：

(2)

式(2)中，設：

(3)

(4)

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

(5)

卡爾曼觀測向量即為n時刻實際的位置與速度向量x(n)。x(n)可由觀測系數矩陣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)

設n時刻預測輸出誤差協方差矩陣為P(n)，白噪聲過程w(n)與k(n)的協方差矩陣分別為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)

則卡爾曼最佳預測輸出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修正卡爾曼的預測值

H=f(w·s+b)。

(12)

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

(13)

神經網絡的訓練使用樣本空間u且以最小均方誤差E為準則進行：

(14)

式中，p為節點在下一時刻的實際位置。設網絡的學習率為lr,則反向傳播過程中權值更新公式可表示為：

(15)

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

1.3 模型結構

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

1.4 復雜度分析

定義以下3種矩陣運算的復雜度：

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

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

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

根據上述矩陣運算復雜度的定義，對卡爾曼濾波復雜度、卡爾曼-DNN復雜度以及RNN循環神經網絡的復雜度進行計算。為簡便分析，設卡爾曼輸入的維度為n×1，狀態轉移矩陣A的維度為n×n；DNN的輸入為n個神經元，隱藏層有兩層，分別有i個神經元與j個神經元；循環神經網絡RNN輸入為k個神經元，隱藏層設u。復雜度計算結果如表1所示。

表1 模型復雜度Tab.1 Model complexity

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

2 基于卡爾曼-DNN預測的路由協議

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

2.1 基于位置預測的鄰居發現方法

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

(16)

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

(17)

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

(18)

式中，PQ0為當前節點鄰居表中對應的鄰居節點所記錄的PQ值，PQ1為鄰居信令包中存儲的PQ值。信令包中存儲的PQ值為該鄰居節點內的PQ值。除了本節點到本節點的PQ初始值設置設為PQ_MAX以外，本節點到其他節點的PQ值均設為PQ_MIN。每當節點收到Hello包時，PQ值會根據式(18)進行更新；如果PQ大于等于存儲于本節點路由表所對應的信令包源節點的PQ值，表示該鏈路質量更優，使用該PQ值替換當前節點一跳鄰居表內的PQ0。

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

基于卡爾曼-DNN位置預測的鄰居發現流程如圖2所示。

圖2 基于卡爾曼-DNN位置預測的鄰居發現流程Fig.2 Flowchart of neighbor tablediscovery based on Kalman and DNN

2.2 路由轉發策略

本文在GPSR協議的基礎上通過基于位置預測的鄰居發現方法，以貪婪模式與周邊模式完成數據分組的轉發，提高了數據分組傳輸的可靠性。各節點轉發數據分組的步驟如下：

① 節點存在待發送的數據分組時，判斷目的節點是否在本節點的一跳鄰居范圍內；若是則將該數據分組發送至目的節點，否則轉到②。

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

③ 將該數據分組存入到節點待發送數據隊列中。當存在鄰居節點加入到本節點的一跳鄰居范圍時，轉到①。

④ 數據分組轉發至下一跳。沿用上述轉發策略直至數據分組到達目的節點。

3 仿真與分析

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

表2 仿真參數配置Tab.2 Simulation parameter settings

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

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

(19)

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

圖3 預測誤差Fig.3 Error of prediction

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

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

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

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

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

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

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

4 結論

本文在現有的節點位置預測路由協議研究與分析的基礎上，提出了一種新的節點位置預測模型，并設計了KDPR路由協議。在協議工作的過程中，每個節點根據自身的鄰居節點特性預測各鄰居的位置，能夠改善因節點快速移動導致鏈路中斷的問題。最后，分析了本協議相較于其他協議的優點，同時提出了本研究存在的問題以及后續需要進一步攻關的方向。