徐一航,王 傲,楊錦彬,李大鵬
(南京郵電大學(xué) 通信與信息工程學(xué)院,江蘇 南京 210003)
無(wú)人機(jī)自組織網(wǎng)絡(luò)(Unmanned Aerial Vehicles Ad Hoc Network,UANET)具有靈活動(dòng)態(tài)組網(wǎng)、自愈性與抗攻擊強(qiáng)的特點(diǎn)[1-3],它將每個(gè)無(wú)人機(jī)作為通信節(jié)點(diǎn)[4],用于各個(gè)無(wú)人機(jī)之間實(shí)現(xiàn)各種信息交互,是大規(guī)模無(wú)人機(jī)作戰(zhàn)效能的根本保障。在高速移動(dòng)的無(wú)人機(jī)場(chǎng)景下,UANET具有鏈路變化快[5]、時(shí)延敏感的特點(diǎn),導(dǎo)致了UANET拓?fù)渥兓l繁,路由信息易丟失。傳統(tǒng)的路由協(xié)議用于高速運(yùn)動(dòng)的無(wú)人機(jī)自組網(wǎng)時(shí)會(huì)導(dǎo)致鏈路中斷,將嚴(yán)重影響集群飛行控制與集群編隊(duì)任務(wù)的完成[6],需要在原有路由協(xié)議的基礎(chǔ)上設(shè)計(jì)新的路由協(xié)議。
目前,國(guó)內(nèi)外對(duì)于移動(dòng)自組織網(wǎng)絡(luò)的研究主要集中于路由協(xié)議的優(yōu)化,而基于移動(dòng)自組織網(wǎng)絡(luò)衍生出的無(wú)人機(jī)自組織網(wǎng)絡(luò)與傳統(tǒng)移動(dòng)自組織網(wǎng)絡(luò)的不同在于各節(jié)點(diǎn)移動(dòng)速度較高[7]。受制于各無(wú)人機(jī)節(jié)點(diǎn)通信距離的限制,快速移動(dòng)的無(wú)人機(jī)節(jié)點(diǎn)會(huì)嚴(yán)重影響數(shù)據(jù)包分組到達(dá)率、端到端時(shí)延等關(guān)鍵性能指標(biāo),傳統(tǒng)的網(wǎng)絡(luò)協(xié)議無(wú)法適用[8-9]。李玉龍等人[10]提出了基于移動(dòng)預(yù)測(cè)與鏈路保持的路由協(xié)議,該協(xié)議綜合考量了節(jié)點(diǎn)位置與鏈路質(zhì)量來(lái)選擇下一跳,減緩了節(jié)點(diǎn)高速移動(dòng)帶來(lái)的不利因素;郭科兵等人[11]對(duì)節(jié)點(diǎn)已有路徑進(jìn)行貪婪轉(zhuǎn)發(fā),進(jìn)行偏移地修正,能有效減少控制包開(kāi)銷(xiāo);王廣彧等人[12]使用了基于卡爾曼濾波的位置預(yù)測(cè)模型來(lái)預(yù)測(cè)鄰居節(jié)點(diǎn)的位置;文獻(xiàn)[13-15]基于機(jī)器學(xué)習(xí)技術(shù)提出了節(jié)點(diǎn)位置預(yù)測(cè)算法,此類(lèi)算法的預(yù)測(cè)精度較傳統(tǒng)算法有了一定的提升;白曉萌等人[16]提出了改進(jìn)的周界無(wú)狀態(tài)路由算法,該算法考慮了節(jié)點(diǎn)的速度和方向,并根據(jù)節(jié)點(diǎn)的當(dāng)前速度計(jì)算之后某一時(shí)間內(nèi)節(jié)點(diǎn)的位置選擇最佳中繼節(jié)點(diǎn);王沁飛等人[17]使用了灰度預(yù)測(cè)-WNN聯(lián)合預(yù)測(cè)模型來(lái)獲得節(jié)點(diǎn)移動(dòng)狀態(tài)評(píng)價(jià)因子,并綜合該因子設(shè)計(jì)了一個(gè)分簇路由協(xié)議。
為了提高鄰居節(jié)點(diǎn)信息的準(zhǔn)確性,加強(qiáng)節(jié)點(diǎn)間鏈路的穩(wěn)定性,兼顧預(yù)測(cè)模型的復(fù)雜度,本文提出了一個(gè)基于卡爾曼-DNN位置預(yù)測(cè)的路由協(xié)議。
卡爾曼-DNN位置預(yù)測(cè)模型由兩部分組成:第一部分是卡爾曼濾波對(duì)節(jié)點(diǎn)位置進(jìn)行預(yù)測(cè),第二部分是基于DNN神經(jīng)網(wǎng)絡(luò)修正卡爾曼預(yù)測(cè)的位置。
s(n)=[x,vx,y,vy]T。
(1)
無(wú)人機(jī)的運(yùn)動(dòng)模型[18]為:
(2)
式(2)中,設(shè):
(3)
(4)
式中,Ti為UANET協(xié)議中離散時(shí)間事件處理的時(shí)間間隔,θ為無(wú)人機(jī)節(jié)點(diǎn)在n時(shí)刻的相對(duì)偏轉(zhuǎn)角。則狀態(tài)轉(zhuǎn)移矩陣A可根據(jù)式(4)表示為:
(5)
卡爾曼觀測(cè)向量即為n時(shí)刻實(shí)際的位置與速度向量x(n)。x(n)可由觀測(cè)系數(shù)矩陣C、獨(dú)立同分布的零均值白噪聲向量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時(shí)刻預(yù)測(cè)輸出誤差協(xié)方差矩陣為P(n),白噪聲過(guò)程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ù)測(cè)輸出s(n+1|n+1)可表示為:
s(n+1|n+1)=A·s(n|n)+
Gn·[x(n)-A·C·s(n|n)]。
(11)
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é)點(diǎn)在下一時(shí)刻的實(shí)際位置。設(shè)網(wǎng)絡(luò)的學(xué)習(xí)率為lr,則反向傳播過(guò)程中權(quán)值更新公式可表示為:
(15)
在節(jié)點(diǎn)工作階段,當(dāng)節(jié)點(diǎn)的位置信息經(jīng)卡爾曼濾波計(jì)算獲得預(yù)測(cè)值后,輸入到DNN神經(jīng)網(wǎng)絡(luò)中,再經(jīng)過(guò)DNN的前向傳播,最終獲得節(jié)點(diǎn)在下一時(shí)刻位置預(yù)測(cè)修正值[x″,y″]T。
圖1 基于卡爾曼-DNN的位置預(yù)測(cè)模型Fig.1 Structure diagram of prediction model
定義以下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ù)雜度的定義,對(duì)卡爾曼濾波復(fù)雜度、卡爾曼-DNN復(fù)雜度以及RNN循環(huán)神經(jīng)網(wǎng)絡(luò)的復(fù)雜度進(jìn)行計(jì)算。為簡(jiǎn)便分析,設(shè)卡爾曼輸入的維度為n×1,狀態(tài)轉(zhuǎn)移矩陣A的維度為n×n;DNN的輸入為n個(gè)神經(jīng)元,隱藏層有兩層,分別有i個(gè)神經(jīng)元與j個(gè)神經(jīng)元;循環(huán)神經(jīng)網(wǎng)絡(luò)RNN輸入為k個(gè)神經(jīng)元,隱藏層設(shè)u。復(fù)雜度計(jì)算結(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ù)測(cè)模型,卡爾曼-DNN預(yù)測(cè)模型復(fù)雜度增加了104。
現(xiàn)有的路由算法中,鄰居節(jié)點(diǎn)大多依靠周期的廣播路由信令包來(lái)獲取鄰居節(jié)點(diǎn)信息。若在廣播周期內(nèi),節(jié)點(diǎn)快速移動(dòng),鄰居節(jié)點(diǎn)可能已經(jīng)離開(kāi)本節(jié)點(diǎn)的通信范圍,但本節(jié)點(diǎn)并不能探測(cè)到這種情況?;诖?,本文以GPSR路由協(xié)議為基礎(chǔ),根據(jù)卡爾曼-DNN節(jié)點(diǎn)位置預(yù)測(cè)結(jié)果更新鄰居表與路由信息。
假設(shè)無(wú)人機(jī)節(jié)點(diǎn)工作在二維平面。各個(gè)無(wú)人機(jī)節(jié)點(diǎn)開(kāi)機(jī)后,每個(gè)節(jié)點(diǎn)首先廣播Hello包發(fā)現(xiàn)鄰居。Hello包中含發(fā)送節(jié)點(diǎn)的節(jié)點(diǎn)號(hào)、鄰居表、節(jié)點(diǎn)的位置與速度信息、鏈路質(zhì)量值PQ。當(dāng)無(wú)人機(jī)節(jié)點(diǎn)收到自身一跳鄰居的發(fā)現(xiàn)信令后,如果鄰居表中沒(méi)有對(duì)應(yīng)的節(jié)點(diǎn)號(hào),節(jié)點(diǎn)會(huì)為該鄰居建立鄰居表,并根據(jù)Hello包中的鄰居表建立本節(jié)點(diǎn)的兩跳鄰居信息。此外節(jié)點(diǎn)還會(huì)額外建立一個(gè)記錄各鄰居節(jié)點(diǎn)位置與速度信息的表Ta(x,vx,y,vy);如果收到的Hello包對(duì)應(yīng)的節(jié)點(diǎn)已經(jīng)存在與本節(jié)點(diǎn)的鄰居表中,則更新PQ值與位置信息。
(16)
計(jì)算與鄰居節(jié)點(diǎn)的距離。設(shè)節(jié)點(diǎn)當(dāng)前的位置為(x,y),如果D小于某個(gè)閾值th,則暫時(shí)不廣播Hello包;如果D>th則判定該一跳鄰居在下一時(shí)刻失效,節(jié)點(diǎn)會(huì)啟動(dòng)一個(gè)定時(shí)器,定時(shí)的時(shí)長(zhǎng)t為:
(17)
式中,V為節(jié)點(diǎn)移動(dòng)的速度。當(dāng)定時(shí)器超時(shí)事件發(fā)生后,節(jié)點(diǎn)刪除失效的一跳鄰居節(jié)點(diǎn);若D大于2th,同樣刪除失效的兩跳鄰居節(jié)點(diǎn)。更新完成后,節(jié)點(diǎn)需要廣播包含新鄰居信息的Hello包,其他節(jié)點(diǎn)在接收到該Hello包后更新相關(guān)鄰居信息,并重新計(jì)算PQ值。PQ值將作為路由轉(zhuǎn)發(fā)的依據(jù),PQ值的定義為:
(18)
式中,PQ0為當(dāng)前節(jié)點(diǎn)鄰居表中對(duì)應(yīng)的鄰居節(jié)點(diǎn)所記錄的PQ值,PQ1為鄰居信令包中存儲(chǔ)的PQ值。信令包中存儲(chǔ)的PQ值為該鄰居節(jié)點(diǎn)內(nèi)的PQ值。除了本節(jié)點(diǎn)到本節(jié)點(diǎn)的PQ初始值設(shè)置設(shè)為PQ_MAX以外,本節(jié)點(diǎn)到其他節(jié)點(diǎn)的PQ值均設(shè)為PQ_MIN。每當(dāng)節(jié)點(diǎn)收到Hello包時(shí),PQ值會(huì)根據(jù)式(18)進(jìn)行更新;如果PQ大于等于存儲(chǔ)于本節(jié)點(diǎn)路由表所對(duì)應(yīng)的信令包源節(jié)點(diǎn)的PQ值,表示該鏈路質(zhì)量更優(yōu),使用該P(yáng)Q值替換當(dāng)前節(jié)點(diǎn)一跳鄰居表內(nèi)的PQ0。
如果某個(gè)節(jié)點(diǎn)的鄰居一直沒(méi)有超出通信范圍,該節(jié)點(diǎn)將長(zhǎng)時(shí)間不廣播Hello包。當(dāng)一個(gè)新的節(jié)點(diǎn)移動(dòng)到本節(jié)點(diǎn)的通信范圍內(nèi),會(huì)導(dǎo)致這個(gè)新加入的節(jié)點(diǎn)長(zhǎng)時(shí)間收不到自身鄰居節(jié)點(diǎn)的信令而無(wú)法更新該節(jié)點(diǎn)的鄰居信息。因此需要設(shè)置一個(gè)定時(shí)器,當(dāng)節(jié)點(diǎn)在定時(shí)時(shí)間TIMER_UPDATE_MSG內(nèi)都沒(méi)有鄰居節(jié)點(diǎn)更新事件發(fā)生,則廣播一個(gè)Hello包,其他節(jié)點(diǎn)收到該Hello包后按照上述方式?jīng)Q定是否更新鄰居表與PQ值。
基于卡爾曼-DNN位置預(yù)測(cè)的鄰居發(fā)現(xiàn)流程如圖2所示。
圖2 基于卡爾曼-DNN位置預(yù)測(cè)的鄰居發(fā)現(xiàn)流程Fig.2 Flowchart of neighbor tablediscovery based on Kalman and DNN
本文在GPSR協(xié)議的基礎(chǔ)上通過(guò)基于位置預(yù)測(cè)的鄰居發(fā)現(xiàn)方法,以貪婪模式與周邊模式完成數(shù)據(jù)分組的轉(zhuǎn)發(fā),提高了數(shù)據(jù)分組傳輸?shù)目煽啃?。各?jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組的步驟如下:
① 節(jié)點(diǎn)存在待發(fā)送的數(shù)據(jù)分組時(shí),判斷目的節(jié)點(diǎn)是否在本節(jié)點(diǎn)的一跳鄰居范圍內(nèi);若是則將該數(shù)據(jù)分組發(fā)送至目的節(jié)點(diǎn),否則轉(zhuǎn)到②。
② 檢查鄰居節(jié)點(diǎn)是否存在路由空洞,若存在,根據(jù)一跳與兩跳鄰居表尋找比該鄰居節(jié)點(diǎn)到目的節(jié)點(diǎn)更近的節(jié)點(diǎn),若沒(méi)有找到這樣的節(jié)點(diǎn),根據(jù)周邊轉(zhuǎn)發(fā)尋找下一跳。若不存在路由空洞,則按照貪婪模式,結(jié)合鄰居節(jié)點(diǎn)中較大的PQ值尋找節(jié)點(diǎn)的下一跳地址。按照上述方式,若尋找到下一跳地址,轉(zhuǎn)到④;否則,轉(zhuǎn)到③。
③ 將該數(shù)據(jù)分組存入到節(jié)點(diǎn)待發(fā)送數(shù)據(jù)隊(duì)列中。當(dāng)存在鄰居節(jié)點(diǎn)加入到本節(jié)點(diǎn)的一跳鄰居范圍時(shí),轉(zhuǎn)到①。
④ 數(shù)據(jù)分組轉(zhuǎn)發(fā)至下一跳。沿用上述轉(zhuǎn)發(fā)策略直至數(shù)據(jù)分組到達(dá)目的節(jié)點(diǎn)。
本文使用QualNet平臺(tái)對(duì)基于卡爾曼-DNN位置預(yù)測(cè)的路由協(xié)議(KDPR)進(jìn)行仿真驗(yàn)證,并與GPSR協(xié)議以及基于卡爾曼濾波預(yù)測(cè)的路由協(xié)議(KFN)進(jìn)行對(duì)比分析。節(jié)點(diǎn)的移動(dòng)方式采用隨機(jī)移動(dòng)(Random Waypoint);通信方式采用跳頻模式。具體參數(shù)如表2所示。
表2 仿真參數(shù)配置Tab.2 Simulation parameter settings
實(shí)驗(yàn)中以仿真方式模擬節(jié)點(diǎn)在2 km×2 km的區(qū)域中移動(dòng)。首先收集在該區(qū)域內(nèi)節(jié)點(diǎn)移動(dòng)的信息,接著將位置信息作為卡爾曼濾波的輸入,經(jīng)卡爾曼濾波處理后得到預(yù)測(cè)輸出向量s=[x′,v′x,y′,v′y]T,即DNN的訓(xùn)練輸入,并根據(jù)觀測(cè)值更新卡爾曼相關(guān)參數(shù)。DNN神經(jīng)網(wǎng)絡(luò)將下一刻節(jié)點(diǎn)位置的實(shí)際值作為神經(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個(gè)指標(biāo)衡量基于KDPR的路由協(xié)議的性能:端到端時(shí)延、分組投遞率和鄰居錯(cuò)誤率。設(shè)jm為節(jié)點(diǎn)m的所有鄰居個(gè)數(shù),im為節(jié)點(diǎn)m鄰居表中不是m的鄰居但沒(méi)有被刪除的節(jié)點(diǎn)的個(gè)數(shù),平均鄰居錯(cuò)誤率AVGNER定義為:
(19)
圖3表示對(duì)一個(gè)節(jié)點(diǎn)的10個(gè)連續(xù)離散時(shí)刻位置使用卡爾曼、卡爾曼-DNN和RNN三種預(yù)測(cè)模型產(chǎn)生的預(yù)測(cè)誤差。設(shè)RNN的輸入k為2,隱藏層u為28,根據(jù)表1可計(jì)算RNN的復(fù)雜度為1 652。從圖3可以看出,卡爾曼-DNN與RNN的平均預(yù)測(cè)誤差相較于卡爾曼預(yù)測(cè)誤差有所降低??柭?DNN平均預(yù)測(cè)誤差為2.24,RNN平均預(yù)測(cè)誤差為1.87,二者預(yù)測(cè)精度相差0.37 m,而卡爾曼-DNN模型復(fù)雜度相較于RNN模型降低了1 160。在預(yù)測(cè)精度相差不大的情況下,相較于RNN預(yù)測(cè)模型,卡爾曼-DNN在模型復(fù)雜度上的優(yōu)勢(shì)較為明顯。
圖3 預(yù)測(cè)誤差Fig.3 Error of prediction
圖4表示無(wú)人機(jī)移動(dòng)速度在10~40 m/s時(shí)的鄰居錯(cuò)誤率。在不同的節(jié)點(diǎn)移動(dòng)速度場(chǎng)景下,基于KDPR的路由協(xié)議相較于KFN協(xié)議與GPSR協(xié)議降低了鄰居發(fā)現(xiàn)的錯(cuò)誤率。由于加入了鄰居預(yù)測(cè)機(jī)制,使得KDPR協(xié)議與KFN協(xié)議能夠更準(zhǔn)確地發(fā)現(xiàn)將要離開(kāi)自身一跳、兩跳范圍的鄰居節(jié)點(diǎn)。
圖4 鄰居平均錯(cuò)誤率Fig.4 Average neighbor error rate
圖5表示無(wú)人機(jī)移動(dòng)速度在10~40 m/s時(shí)的分組投遞率,由圖中可以看出,KDPR路由相較于GPSR與KFN提高了網(wǎng)絡(luò)整體的分組投遞率。在節(jié)點(diǎn)移動(dòng)速度較高時(shí),節(jié)點(diǎn)在鏈路預(yù)測(cè)機(jī)制的作用下減少了分組的轉(zhuǎn)發(fā)次數(shù),相較于其他兩種算法有一定的性能優(yōu)勢(shì)。而GPSR沒(méi)有對(duì)鄰居節(jié)點(diǎn)進(jìn)行預(yù)測(cè),這導(dǎo)致在節(jié)點(diǎn)移動(dòng)速度較高時(shí),轉(zhuǎn)發(fā)數(shù)據(jù)分組無(wú)法找到本節(jié)點(diǎn)的中繼節(jié)點(diǎn),需要重新發(fā)送信令包尋路,影響網(wǎng)絡(luò)整體的分組投遞率。
圖5 分組投遞率Fig.5 Packet delivery fraction
圖6表示無(wú)人機(jī)移動(dòng)速度在10~40 m/s時(shí)不同協(xié)議端到端的傳輸時(shí)延。隨著節(jié)點(diǎn)移動(dòng)速度的升高,端到端時(shí)延不斷增加。移動(dòng)速度較低時(shí),相較于KFN算法并沒(méi)有明顯改善。但在節(jié)點(diǎn)移動(dòng)速度相對(duì)較高時(shí),由于KDPR路由協(xié)議提高了鏈路選擇的準(zhǔn)確性,因此,平均端到端時(shí)延相較于GPSR算法與KFN算法有了一定的改善。
圖6 端到端時(shí)延Fig.6 End-to-end delay
在對(duì)場(chǎng)景進(jìn)行仿真實(shí)驗(yàn)可以看出,算法在平均鄰居發(fā)現(xiàn)錯(cuò)誤率上要優(yōu)于經(jīng)典算法和相關(guān)改進(jìn)算法,表明在使用節(jié)點(diǎn)預(yù)測(cè)后的協(xié)議可以提升協(xié)議的性能。此外,由于鄰居被正確的發(fā)現(xiàn),提高了路由正確率,降低了鄰居信息的錯(cuò)誤概率,特別是在鄰居節(jié)點(diǎn)移動(dòng)速度較高時(shí)較為明顯。但每當(dāng)節(jié)點(diǎn)預(yù)測(cè)自己的鄰居節(jié)點(diǎn)發(fā)生變化時(shí),都需要向自身的鄰居節(jié)點(diǎn)發(fā)送Hello包,而如果某個(gè)節(jié)點(diǎn)在預(yù)測(cè)周期內(nèi)都產(chǎn)生了鄰居更新事件,那么頻繁地發(fā)送Hello包將會(huì)加重路由的開(kāi)銷(xiāo)。未來(lái)需要對(duì)上述問(wèn)題進(jìn)行分析。
本文在現(xiàn)有的節(jié)點(diǎn)位置預(yù)測(cè)路由協(xié)議研究與分析的基礎(chǔ)上,提出了一種新的節(jié)點(diǎn)位置預(yù)測(cè)模型,并設(shè)計(jì)了KDPR路由協(xié)議。在協(xié)議工作的過(guò)程中,每個(gè)節(jié)點(diǎn)根據(jù)自身的鄰居節(jié)點(diǎn)特性預(yù)測(cè)各鄰居的位置,能夠改善因節(jié)點(diǎn)快速移動(dòng)導(dǎo)致鏈路中斷的問(wèn)題。最后,分析了本協(xié)議相較于其他協(xié)議的優(yōu)點(diǎn),同時(shí)提出了本研究存在的問(wèn)題以及后續(xù)需要進(jìn)一步攻關(guān)的方向。