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

張雅楠 仇洪冰

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

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

1 引言

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

無人機(jī)的高移動性導(dǎo)致了網(wǎng)絡(luò)拓?fù)漕l繁變化，位置信息能更好地輔助路由決策，因此在UANET中普遍使用基于地理位置的路由協(xié)議[7]。Karp等人[8]提出了經(jīng)典的貪婪周邊無狀態(tài)路由協(xié)議(Greedy Perimeter Stateless Routing, GPSR)，通過鄰居周期性廣播的位置信息結(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é)議在動態(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ù)雜場景中的自適應(yīng)能力。在此基礎(chǔ)上Liu等人[11]提出了基于Q學(xué)習(xí)的多目標(biāo)優(yōu)化路由協(xié)議(Q-learning based Multi- objective optimization Routing protocol, QMR)，在路由選擇過程中周期性更新鄰居狀態(tài)并結(jié)合新的探索-利用機(jī)制，選擇更可靠的下一跳。然而，上述協(xié)議主要致力于提升高速移動網(wǎng)絡(luò)中的網(wǎng)絡(luò)服務(wù)質(zhì)量，卻沒有考慮異常節(jié)點(diǎn)對網(wǎng)絡(luò)造成的潛在影響。

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

針對上述問題，本文提出了一種基于深度強(qiáng)化學(xué)習(xí)的無人機(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)特征，將路由選擇過程建模成馬爾可夫決策過程(Markov Decision Process, MDP)，然后使用DRL算法進(jìn)行決策。DTGR在包含異常節(jié)點(diǎn)的場景中能顯著降低端到端時延、提升包遞交率。DTGR的主要貢獻(xiàn)點(diǎn)如下：

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

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

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

2 系統(tǒng)模型

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

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

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

丟包率η：表示節(jié)點(diǎn)丟包的概率，通過統(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é)存儲節(jié)點(diǎn)的δ與η并通過式(1)計(jì)算節(jié)點(diǎn)的信任度，在每次通信前，節(jié)點(diǎn)通過可信第三方獲取其他節(jié)點(diǎn)的信任度并在整個通信過程中使用，在通信結(jié)束后基于本次服務(wù)對其他節(jié)點(diǎn)的信任度進(jìn)行更新。信任度更新方式見式(2)

2.2 路由選擇

2.3 馬爾可夫決策過程

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

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

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

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

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

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

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

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

3.2 DTGR協(xié)議

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

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

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

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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