基于深度強(qiáng)化學(xué)習(xí)的無(wú)人機(jī)可信地理位置路由協(xié)議

張雅楠 仇洪冰

(桂林電子科技大學(xué)信息與通信學(xué)院 桂林 541004)

(廣西無(wú)線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室 桂林 541004)

1 引言

近年來(lái)，隨著高精密模具、服務(wù)器、通信設(shè)備、傳感器的高速發(fā)展，無(wú)人機(jī)(Unmanned Aerial Vehicle, UAV)在物聯(lián)網(wǎng)中的應(yīng)用越來(lái)廣泛，例如火災(zāi)檢測(cè)[1]、應(yīng)急通信[2]、智慧農(nóng)業(yè)[3]。在復(fù)雜場(chǎng)景中，無(wú)人機(jī)通常使用自組織的方式構(gòu)成網(wǎng)絡(luò)(UAV Ad hoc NETwork, UANET)，UANET具有部署靈活、魯棒性高的優(yōu)點(diǎn)。為了高效協(xié)同的完成任務(wù)，UANET中無(wú)人機(jī)采用多跳方式轉(zhuǎn)發(fā)數(shù)據(jù)、傳遞信息[4]。無(wú)人機(jī)節(jié)點(diǎn)一般會(huì)按照系統(tǒng)分配的任務(wù)完成數(shù)據(jù)包收發(fā)，但也有一些存在異常，這包括：老化、設(shè)備故障、自私行徑和惡意攻擊[5]。與異常節(jié)點(diǎn)進(jìn)行通信會(huì)導(dǎo)致時(shí)延增加或者丟包，降低網(wǎng)絡(luò)性能。因此路由協(xié)議需要建立節(jié)點(diǎn)的信任管理機(jī)制[6]，在路由選擇時(shí)綜合考慮鄰居的網(wǎng)絡(luò)拓?fù)?、異常程度等信息做出最?yōu)決策，保障UANET的安全性和可靠性?；谝陨戏治?，作為UANET中的關(guān)鍵技術(shù)，亟需設(shè)計(jì)一種高效且可信的無(wú)人機(jī)路由協(xié)議。

無(wú)人機(jī)的高移動(dòng)性導(dǎo)致了網(wǎng)絡(luò)拓?fù)漕l繁變化，位置信息能更好地輔助路由決策，因此在UANET中普遍使用基于地理位置的路由協(xié)議[7]。Karp等人[8]提出了經(jīng)典的貪婪周邊無(wú)狀態(tài)路由協(xié)議(Greedy Perimeter Stateless Routing, GPSR)，通過(guò)鄰居周期性廣播的位置信息結(jié)合貪婪算法進(jìn)行路由選擇。在此基礎(chǔ)上，Jung等人[9]提出了基于Q學(xué)習(xí)的地理路由協(xié)議(Q-learning-based Geographic routing protocol, QGeo)，引入強(qiáng)化學(xué)習(xí)(Reinforcement Learning, RL)與Q表格法，并使用鏈路與位置誤差輔助路由選擇，使協(xié)議在動(dòng)態(tài)變化的環(huán)境下逼近最優(yōu)解。Lyu等人[10]提出了基于GPSR的Q網(wǎng)絡(luò)增強(qiáng)地理路由協(xié)議(Q-Network enhanced geographic routing protocol based on GPSR,QNGPSR)，采用深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning, DRL)算法，構(gòu)建深度Q網(wǎng)絡(luò)并結(jié)合鄰居拓?fù)湫畔f(xié)助路由選擇，提升了協(xié)議在復(fù)雜場(chǎng)景中的自適應(yīng)能力。在此基礎(chǔ)上Liu等人[11]提出了基于Q學(xué)習(xí)的多目標(biāo)優(yōu)化路由協(xié)議(Q-learning based Multi- objective optimization Routing protocol, QMR)，在路由選擇過(guò)程中周期性更新鄰居狀態(tài)并結(jié)合新的探索-利用機(jī)制，選擇更可靠的下一跳。然而，上述協(xié)議主要致力于提升高速移動(dòng)網(wǎng)絡(luò)中的網(wǎng)絡(luò)服務(wù)質(zhì)量，卻沒有考慮異常節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)造成的潛在影響。

為了感知異常節(jié)點(diǎn)，主流研究方案采用節(jié)點(diǎn)信任度衡量節(jié)點(diǎn)的異常程度，Zhu等人[12]提出了異常行為概率檢測(cè)模型(iTrust)，使用可信授權(quán)機(jī)構(gòu)在通信過(guò)程中收集節(jié)點(diǎn)的路由證據(jù)并檢查出錯(cuò)概率，評(píng)估節(jié)點(diǎn)信任度。Cho等人[13]提出了基于源的延遲容忍網(wǎng)絡(luò)信任模型(PROVEnance-baSed Trust model, PROVEST)，將證據(jù)插入到數(shù)據(jù)包中，通過(guò)包的傳播來(lái)收集證據(jù)，以此降低網(wǎng)絡(luò)開銷。不過(guò)PROVEST對(duì)證據(jù)的分析僅限于目的節(jié)點(diǎn)，且可能因?yàn)閬G包或空洞區(qū)域而丟失證據(jù)。Ge等人[14]使用分布式信任模型UAV-pro解決了上述難題，通過(guò)來(lái)源感知技術(shù)和消息完整性，對(duì)節(jié)點(diǎn)行為進(jìn)行記錄并生成觀測(cè)證據(jù)，評(píng)估節(jié)點(diǎn)信任度并標(biāo)記惡意節(jié)點(diǎn)。然而上述研究需要在通信過(guò)程中檢測(cè)證據(jù)，引入了額外的檢測(cè)開銷，并且需要在決策前更新節(jié)點(diǎn)的信任度，降低了網(wǎng)絡(luò)性能。

針對(duì)上述問(wèn)題，本文提出了一種基于深度強(qiáng)化學(xué)習(xí)的無(wú)人機(jī)可信地理位置路由協(xié)議(Deep reinforcement learning based Trusted Geographic Routing protocol, DTGR)。DTGR使用信任度衡量節(jié)點(diǎn)異常程度，結(jié)合目標(biāo)節(jié)點(diǎn)的地理位置、鄰居拓?fù)湫畔⒆鳛闋顟B(tài)特征，將路由選擇過(guò)程建模成馬爾可夫決策過(guò)程(Markov Decision Process, MDP)，然后使用DRL算法進(jìn)行決策。DTGR在包含異常節(jié)點(diǎn)的場(chǎng)景中能顯著降低端到端時(shí)延、提升包遞交率。DTGR的主要貢獻(xiàn)點(diǎn)如下：

(1) 提出了新的節(jié)點(diǎn)的信任度模型。使用可信第三方提供、更新節(jié)點(diǎn)的信任度。降低了評(píng)估開銷；

(2) 優(yōu)化了文獻(xiàn)[10]中對(duì)鄰居拓?fù)湫畔⒌奶幚?，減少了輸入特征的維度，降低計(jì)算開銷；

(3) 使用信任度結(jié)合深度強(qiáng)化學(xué)習(xí)模型輔助路由決策，改進(jìn)了獎(jiǎng)勵(lì)函數(shù)，讓節(jié)點(diǎn)更智能地選擇最優(yōu)下一跳，提升網(wǎng)絡(luò)性能。

2 系統(tǒng)模型

2.1 節(jié)點(diǎn)信任度模型

節(jié)點(diǎn)信任度用來(lái)反映節(jié)點(diǎn)的服務(wù)能力，是一個(gè)標(biāo)量。它用來(lái)評(píng)估鄰居在通信過(guò)程中出現(xiàn)積極或者消極行為的概率，通常使用網(wǎng)絡(luò)相關(guān)的性能參數(shù)進(jìn)行量化[15]。假定傳播時(shí)延和信道干擾相對(duì)于處理時(shí)延忽略不計(jì)，并且節(jié)點(diǎn)在每次通信中具有相似的表現(xiàn)，從兩個(gè)維度考慮單個(gè)節(jié)點(diǎn)的服務(wù)能力：

時(shí)延偏差δ：表示節(jié)點(diǎn)從接收到轉(zhuǎn)發(fā)數(shù)據(jù)包之間的理論時(shí)延、實(shí)際時(shí)延差值與理論時(shí)延之比。理論時(shí)延視為數(shù)據(jù)包大小的函數(shù)，該函數(shù)參數(shù)是固定值，由節(jié)點(diǎn)的計(jì)算能力決定。而實(shí)際時(shí)延通過(guò)在數(shù)據(jù)包中添加字段進(jìn)行記錄[10]。影響δ的主要因素為：排隊(duì)時(shí)延和節(jié)點(diǎn)異常。

丟包率η：表示節(jié)點(diǎn)丟包的概率，通過(guò)統(tǒng)計(jì)節(jié)點(diǎn)轉(zhuǎn)發(fā)成功和轉(zhuǎn)發(fā)失敗的總數(shù)據(jù)包數(shù)計(jì)算得到，影響η的主要因素為：緩沖區(qū)溢出和節(jié)點(diǎn)異常。

節(jié)點(diǎn)的信任度T定義為關(guān)于δ和η的函數(shù)

可信第三方負(fù)責(zé)存儲(chǔ)節(jié)點(diǎn)的δ與η并通過(guò)式(1)計(jì)算節(jié)點(diǎn)的信任度，在每次通信前，節(jié)點(diǎn)通過(guò)可信第三方獲取其他節(jié)點(diǎn)的信任度并在整個(gè)通信過(guò)程中使用，在通信結(jié)束后基于本次服務(wù)對(duì)其他節(jié)點(diǎn)的信任度進(jìn)行更新。信任度更新方式見式(2)

2.2 路由選擇

2.3 馬爾可夫決策過(guò)程

使用MDP 4元組〈S,A,P,R〉來(lái)描述路由決策過(guò)程，并使用智能體(agent)代表決策的實(shí)體。則S表示智能體所處的狀態(tài)集合，A為動(dòng)作集合，P用來(lái)描述狀態(tài)轉(zhuǎn)移的概率，R為即時(shí)獎(jiǎng)勵(lì)函數(shù)。當(dāng)節(jié)點(diǎn)接收到數(shù)據(jù)包時(shí)，路由選擇過(guò)程的決策任務(wù)是在其所有鄰居集中選擇下一跳節(jié)點(diǎn)并轉(zhuǎn)發(fā)此數(shù)據(jù)包。執(zhí)行完動(dòng)作后狀態(tài)由當(dāng)前節(jié)點(diǎn)轉(zhuǎn)移至下一跳，不斷重復(fù)以上過(guò)程直至到達(dá)終點(diǎn)或投遞失敗。根據(jù)以上分析可以建立以下的決策過(guò)程：

轉(zhuǎn)移概率P：由真實(shí)環(huán)境決定，在本文中P是隨機(jī)且未知的。

獎(jiǎng)勵(lì)函數(shù)R：為了讓智能體能夠感知下一跳的異常程度從而輔助決策，在獎(jiǎng)勵(lì)函數(shù)中引入信任度，當(dāng)節(jié)點(diǎn)選擇信任度為Tx的 鄰居節(jié)點(diǎn)x作為下一跳時(shí)，使用R e(x)給出信任值對(duì)應(yīng)的獎(jiǎng)勵(lì)：

其中，τ是信任權(quán)重且取值為正。使用信任度改進(jìn)后的即時(shí)獎(jiǎng)勵(lì)函數(shù)R(x)定義為

3 基于深度強(qiáng)化學(xué)習(xí)的無(wú)人機(jī)可信地理位置路由協(xié)議設(shè)計(jì)

3.1 深度強(qiáng)化學(xué)習(xí)算法

相比較于傳統(tǒng)算法，強(qiáng)化學(xué)習(xí)訓(xùn)練的智能體可以自動(dòng)適應(yīng)不斷變化的環(huán)境，并在交互中更新決策，優(yōu)化路由性能。算法首先考慮策略函數(shù)π

RL算法的最終目標(biāo)是讓智能體在訓(xùn)練中習(xí)得最優(yōu)策略π?，最大化累積獎(jiǎng)勵(lì)

3.2 DTGR協(xié)議

結(jié)合DRL算法設(shè)計(jì)DTGR協(xié)議，DTGR主要包含鄰居表建立和路由選擇過(guò)程。

鄰居表建立：和GPSR類似[8]，通信中的節(jié)點(diǎn)c在通信時(shí)會(huì)通過(guò)信標(biāo)周期性的廣播Lc和N Fc信息至鄰居節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)u收 到來(lái)自v的信標(biāo)時(shí)，還會(huì)通過(guò)可信第三方獲得Tv， 進(jìn)而更新自身的鄰居表NTu和鄰居拓?fù)湫畔 Fu。

路由選擇：當(dāng)節(jié)點(diǎn)c接收到數(shù)據(jù)包p時(shí)，執(zhí)行以下路由選擇算法如表1所示。

表1 DTGR路由選擇算法(算法1)

圖1 本文構(gòu)建的DQN模型

通過(guò)對(duì)輸入特征向量的優(yōu)化，將位置相關(guān)的特征從5維減少至4維，減少了通信過(guò)程中神經(jīng)網(wǎng)絡(luò)中輸入的數(shù)據(jù)量，使整體計(jì)算開銷降低20%。

提出的DTGR協(xié)議的主要架構(gòu)如圖2所示，無(wú)人機(jī)通過(guò)鄰居廣播的信標(biāo)獲得鄰居信息并基于這些信息構(gòu)建鄰居表，當(dāng)發(fā)送數(shù)據(jù)包時(shí)，通過(guò)鄰居表和數(shù)據(jù)包信息構(gòu)建狀態(tài)空間，并使用DQN網(wǎng)絡(luò)輸出路由決策，從而選擇合適的下一跳。

圖2 DTGR協(xié)議架構(gòu)

4 仿真分析

為了驗(yàn)證無(wú)人機(jī)路由協(xié)議的性能，通過(guò)平均端到端時(shí)延和包遞交率這兩個(gè)網(wǎng)絡(luò)性能指標(biāo)對(duì)GPSR,QGeo,QNGPSR和DTGR 4組基于地理位置的路由協(xié)議進(jìn)行仿真對(duì)比。

在仿真實(shí)驗(yàn)中，QGeo采用等寬法對(duì)輸入特征進(jìn)行離散化。每個(gè)維度的特征值被均勻地劃分成5個(gè)區(qū)間，每個(gè)特征值用最近的端點(diǎn)表示，對(duì)應(yīng)Q值表的狀態(tài)大小被設(shè)置為55=3125。

4.1 實(shí)驗(yàn)設(shè)置

使用Python3.6仿真實(shí)現(xiàn)多無(wú)人機(jī)的底層通信、DRL決策模型以及路由協(xié)議。具體而言，在一個(gè)2000 m×2000 m的地圖內(nèi)隨機(jī)生成40～120個(gè)無(wú)人機(jī)節(jié)點(diǎn)，按照一定比例產(chǎn)生異常節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)類型對(duì)應(yīng)的閾值隨機(jī)初始化每個(gè)節(jié)點(diǎn)的時(shí)延偏差、丟包率，然后計(jì)算信任度。無(wú)人機(jī)的通信半徑為350 m、移動(dòng)速度為3～10 m/s、移動(dòng)方向隨機(jī)。廣播信標(biāo)的周期為0.5 s。DTGR中構(gòu)建的DQN網(wǎng)絡(luò)共4層，神經(jīng)元個(gè)數(shù)為5×16×4×1，輸入特征采用最大最小標(biāo)準(zhǔn)化方法處理，并使用SELU作為激活函數(shù)。在DQN的訓(xùn)練過(guò)程中使用Adam作為優(yōu)化器且學(xué)習(xí)率α設(shè)置為0.001，更新時(shí)使用小批量梯度下降法，批大小為32。仿真實(shí)驗(yàn)的主要參數(shù)見表2。

表2 仿真實(shí)驗(yàn)參數(shù)

4.2 實(shí)驗(yàn)結(jié)果和分析

上述基于RL算法的路由協(xié)議包含訓(xùn)練階段和測(cè)試階段，實(shí)驗(yàn)中每個(gè)回合對(duì)應(yīng)100 s的仿真時(shí)間，訓(xùn)練階段共100個(gè)回合且每回合使用不同的地圖。為了保證算法不會(huì)因?yàn)橐苿?dòng)導(dǎo)致的丟包而無(wú)法收斂，訓(xùn)練階段中的無(wú)人機(jī)節(jié)點(diǎn)是靜止的，而測(cè)試階段進(jìn)行隨機(jī)移動(dòng)。為了展示算法的泛化性能，測(cè)試階段采用的地圖與訓(xùn)練階段的地圖均不相同。在訓(xùn)練階段選擇總節(jié)點(diǎn)數(shù)為100、異常節(jié)點(diǎn)數(shù)比例為0.15作為基準(zhǔn)值。

不同協(xié)議的訓(xùn)練曲線見圖3，圖3展示了4個(gè)協(xié)議(GPSR是非學(xué)習(xí)算法故用直線表示)在訓(xùn)練過(guò)程中的平均端到端時(shí)延變化。在收斂速度上，DTGR在訓(xùn)練了1～2回合后即趨向收斂并且波動(dòng)較小，而QGeo算法則需要5個(gè)回合以后。另外DTGR擁有最好的訓(xùn)練性能，曲線位于圖形的最下方，說(shuō)明DTGR能夠適應(yīng)無(wú)人機(jī)自組網(wǎng)中動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)渑c異常的節(jié)點(diǎn)，通過(guò)與環(huán)境的交互學(xué)習(xí)最優(yōu)路由決策，降低時(shí)延。

圖3 不同協(xié)議的訓(xùn)練曲線

選擇異常節(jié)點(diǎn)數(shù)比例為0.05,0.1,0.15,0.2和0.25對(duì)協(xié)議進(jìn)行測(cè)試，驗(yàn)證DTGR在不同異常節(jié)點(diǎn)比例下的平均端到端時(shí)延和包遞交率，結(jié)果如圖4所示?？梢钥闯霎?dāng)異常節(jié)點(diǎn)比例升高時(shí)，所有協(xié)議的時(shí)延都在上升、包遞交率都在下降。這與直覺相符，因?yàn)楫?dāng)總節(jié)點(diǎn)數(shù)量固定時(shí)，異常節(jié)點(diǎn)數(shù)量越多則傳輸鏈路包含異常節(jié)點(diǎn)的概率增大、轉(zhuǎn)發(fā)成功的概率減小、傳輸時(shí)延提升。另外DTGR相比于其他協(xié)議擁有最低的時(shí)延、最高的包遞交率。其原因是DTGR能夠感知節(jié)點(diǎn)的信任度。當(dāng)鄰居節(jié)點(diǎn)具有不同位置和信任度時(shí)，GPSR和QNGPSR的路由選擇過(guò)程等價(jià)于最短路近似算法，異常節(jié)點(diǎn)被選擇的概率增多，造成更多的丟包和時(shí)延的增加。而DTGR利用神經(jīng)網(wǎng)絡(luò)評(píng)估每個(gè)節(jié)點(diǎn)潛在的路由能力，選擇網(wǎng)絡(luò)性能最優(yōu)的下一跳。實(shí)驗(yàn)結(jié)果說(shuō)明了DTGR在異常節(jié)點(diǎn)的密度發(fā)生改變時(shí)，相較其他協(xié)議能進(jìn)行更優(yōu)的路由決策，保障網(wǎng)絡(luò)性能。

圖4 異常節(jié)點(diǎn)比例對(duì)協(xié)議性能的影響

圖5展示了總節(jié)點(diǎn)數(shù)量為40,60,80,100,120時(shí)，不同協(xié)議的性能。從圖5可以看出，當(dāng)節(jié)點(diǎn)數(shù)量在60及以上時(shí)，DTGR擁有最優(yōu)的平均端到端時(shí)延和包遞交率。總節(jié)點(diǎn)數(shù)量為40時(shí)DTGR包遞交率略低于GPSR和QNGPSR，這是因?yàn)镈TGR不具備周邊轉(zhuǎn)發(fā)模式[8]。周邊轉(zhuǎn)發(fā)模式會(huì)在節(jié)點(diǎn)無(wú)可選下一跳時(shí)，嘗試重傳數(shù)據(jù)包給已轉(zhuǎn)發(fā)過(guò)的節(jié)點(diǎn)，在節(jié)點(diǎn)數(shù)量稀疏、可達(dá)鏈路很少時(shí)此模式能顯著增加包遞交率。但重復(fù)選擇異常節(jié)點(diǎn)會(huì)引入額外的時(shí)延增加通信開銷，故DTGR放棄使用周邊轉(zhuǎn)發(fā)模式。此外，DTGR和QNGPSR協(xié)議在節(jié)點(diǎn)數(shù)量為60和80時(shí)，平均端到端時(shí)延大幅低于GPSR，這是因?yàn)橥ㄐ胚^(guò)程中存在大量空洞區(qū)域[10]。這一結(jié)果也驗(yàn)證了本文對(duì)鄰居拓?fù)湫畔⒌膬?yōu)化是合理正確的，DTGR能夠使用降維后的位置特征評(píng)估兩跳節(jié)點(diǎn)的位置優(yōu)勢(shì)，減少進(jìn)入空洞區(qū)域的概率，最終降低時(shí)延。在總節(jié)點(diǎn)數(shù)量較大的UANET中，采用DTGR算法的網(wǎng)絡(luò)性能更好。

圖5 總節(jié)點(diǎn)數(shù)量對(duì)協(xié)議性能的影響

5 結(jié)論

無(wú)人機(jī)路由協(xié)議需要考慮頻繁變化的網(wǎng)絡(luò)拓?fù)浜彤惓９?jié)點(diǎn)的評(píng)估，本文提出一種基于深度強(qiáng)化學(xué)習(xí)的可信無(wú)人機(jī)地理路由協(xié)議DTGR。利用可信第三方提供節(jié)點(diǎn)信任度，減少了檢測(cè)成本。改進(jìn)了鄰居拓?fù)湫畔?，降低了?jì)算開銷。仿真實(shí)驗(yàn)表明，DTGR能夠在高移動(dòng)性且存在異常節(jié)點(diǎn)的網(wǎng)絡(luò)中根據(jù)節(jié)點(diǎn)特征選擇最優(yōu)下一跳。在端到端時(shí)延和包遞交率兩個(gè)指標(biāo)上，DTGR的表現(xiàn)均優(yōu)于其他協(xié)議。此外，DTGR能夠適應(yīng)異常節(jié)點(diǎn)數(shù)量和密度的改變，自適應(yīng)做出有效且高效的路由決策，魯棒性好。DTGR為無(wú)人機(jī)自組網(wǎng)提供了高效可靠的網(wǎng)絡(luò)通信方案。