喬冠華,吳 麒,王 翔,潘俊男,張易新,丁 建

(1.中國西南電子技術(shù)研究所 成都 610036;2.重慶郵電大學 通信與信息工程學院,重慶 400065)

0 引 言

無人機具有體積小、移動速度快、靈活性強等優(yōu)點,在軍事和公共管理等領(lǐng)域的應用十分廣泛。在美軍無人機[1]和無人機系統(tǒng)[2]規(guī)劃中,無人機作為全球信息系統(tǒng)的一個重要節(jié)點,與地面無人機系統(tǒng)、海上無人機系統(tǒng)構(gòu)成一體化的無人作戰(zhàn)系統(tǒng)。無人機自組網(wǎng)不僅具有傳統(tǒng)自組織網(wǎng)絡的無中心化、動態(tài)網(wǎng)絡拓撲、多跳路由、資源受限等共性,還具有能量受限、節(jié)點移動速度快、傳輸實時性高等特點。

目前,無線網(wǎng)絡的路由協(xié)議主要有:基于路由表的主動路由協(xié)議,如DSDV[3]和OLSR[4]路由協(xié)議;按需響應協(xié)議,如AODV[5]、DSR[6]、TORA[7]路由協(xié)議;混合路由協(xié)議,如ZRP[8]協(xié)議;機會路由協(xié)議,如基于強化學習的路由算法[9];基于位置的路由協(xié)議,如GPSR路由協(xié)議[10]?；趶娀瘜W習的路由算法在復雜網(wǎng)絡中顯示出強大優(yōu)勢,得到了廣泛的關(guān)注與研究。

傳統(tǒng)方法當中,文獻[11]提出了適用于無人機自組網(wǎng)的基于最短路徑的改進路由算法。該算法可以實現(xiàn)多路徑傳輸,并且從丟包率、端到端時延和抖動3個方面評估性能,但沒有考慮動態(tài)場景的情況。文獻[12]提出了一種具有負載感知和網(wǎng)絡拓撲變動感知能力的多指標多徑優(yōu)化鏈路狀態(tài)路由協(xié)議。該協(xié)議在成功率、端到端時延和吞吐量性能上均有明顯提高,進而證明所提多徑路由方案的合理性。

在現(xiàn)有的基于深度強化學習的研究成果中,文獻[13]首次提出基于強化學習的Q-Learning算法[14]的逐跳路由算法。該算法實現(xiàn)自適應路由,并且在動態(tài)變化的網(wǎng)絡中表現(xiàn)良好。當網(wǎng)絡負載水平、流量模式和拓撲結(jié)構(gòu)隨時間變化時,其性能都優(yōu)于傳統(tǒng)的路由協(xié)議。

在Q-Routing算法的基礎上,又出現(xiàn)了多種改進算法,如PQ-R[15],SQ-R[16]等。但是,Q-Routing算法及其擴展方案應用到復雜的無線網(wǎng)絡中時存在明顯缺陷?；赒-Routing的路由算法要維護Q表,需要消耗大量的時間和空間成本,并且無法擴展到較大的動作和狀態(tài)空間。

文獻[17]提出的TQNGPSR是基于GPSR和Q網(wǎng)絡的流量感知無人機ad-hoc網(wǎng)絡路由協(xié)議。該協(xié)議利用鄰居節(jié)點的擁塞信息實現(xiàn)流量平衡,并用Q網(wǎng)絡算法評價當前節(jié)點每條無線鏈接的質(zhì)量。基于對鏈接的評估,該協(xié)議可在多個選擇中作出合理決定,降低網(wǎng)絡時延和丟包率。

文獻[18]提出一種基于深度強化學習的集中式無線多跳網(wǎng)絡能量高效機會路由算法,通過機會路由的方式減少傳輸時間,同時平衡能耗、延長網(wǎng)絡壽命。文獻[19]提出了一種基于強化學習的分布式和能量高效無線物聯(lián)網(wǎng)路由算法,通過仿真評估了算法的失效率、頻譜和功率效率。文獻[20]提出了基于演示的優(yōu)先級記憶深度Q學習來加速收斂和減少內(nèi)存占用。文獻[21]針對現(xiàn)有智能路由算法收斂速度慢、平均時延高、帶寬利用率低等問題,提出了一種基于深度強化學習的多路徑智能路由算法RDPG-Route。該算法采用循環(huán)確定性策略梯度作為訓練框架,引入長短期記憶網(wǎng)絡作為神經(jīng)網(wǎng)絡,相比于其他智能路由算法降低了平均端到端時延,提高了吞吐量,減少了丟包率。

路由算法大多基于固定的路由規(guī)則,面對未來無人機自組網(wǎng)復雜多變的網(wǎng)絡環(huán)境,難以根據(jù)實時的網(wǎng)絡狀態(tài)與實際的應用場景需要,自適應地作出智能化的路由決策?，F(xiàn)有基于強化學習的無人機路由解決方案中,大部分基于集中式的深度強化學習方法,使用具有集中式的智能體學習整個網(wǎng)絡環(huán)境的狀態(tài),給網(wǎng)絡中的每個節(jié)點發(fā)送對應的動作。一旦整個網(wǎng)絡路由決策的控制中心受到干擾甚至癱瘓,就會嚴重影響整個網(wǎng)絡路由的性能,這在無人機對抗場景中是十分致命的。

為解決上述問題,本文使用深度強化學習技術(shù)研究并設計一種分布式的符合無人機網(wǎng)絡路由特性的聯(lián)合路由方案,將無人機網(wǎng)絡的機會路由問題建模為強化學習問題,包括系統(tǒng)模型的定義、狀態(tài)空間、動作空間,以及獎勵函數(shù)的設計,使得智能體根據(jù)當前狀態(tài)選擇最佳的動作,不斷與網(wǎng)絡環(huán)境進行交互,最終學習到一個保證路由性能、延長網(wǎng)絡壽命的路由策略,并解決多智能體深度強化學習中維度過大以及多智能體之間相互影響的問題。仿真結(jié)果驗證了本文算法的有效性。

1 網(wǎng)絡建模

1.1 無人機自組網(wǎng)建模

無人機自組網(wǎng)中的網(wǎng)絡節(jié)點在部署之后將自動組網(wǎng)。本文將具有N個節(jié)點的無人機自組網(wǎng)建模成一個連通圖G=(V,E),其中的每一個頂點v?V對應一個無人機節(jié)點,每一條邊e?E對應兩個無人機節(jié)點之間的通信鏈路。數(shù)據(jù)包可在網(wǎng)絡節(jié)點之間的無線鏈路發(fā)送,網(wǎng)絡中每個節(jié)點既可以是源節(jié)點,也可以是目的節(jié)點。當源節(jié)點s?V向目的節(jié)點d?V發(fā)送大小為L的數(shù)據(jù)包p到達中繼節(jié)點j時,如果j=d,說明數(shù)據(jù)包已經(jīng)到達目的節(jié)點,數(shù)據(jù)包的路由過程結(jié)束;否則,數(shù)據(jù)包將被轉(zhuǎn)發(fā)到由當前智能體節(jié)點學習的路由策略選擇的下一跳鄰居節(jié)點上。

在路由的過程中,由節(jié)點i發(fā)往下一跳節(jié)點j的數(shù)據(jù)包傳輸時間ti,j定義為數(shù)據(jù)包在節(jié)點i的隊列中的等待時間和無線鏈路的轉(zhuǎn)發(fā)時間之和,即

(1)

(1)式中,數(shù)據(jù)包在節(jié)點隊列的等待時間wi為數(shù)據(jù)包進入節(jié)點隊列到離開節(jié)點隊列的時間差,無線鏈路的轉(zhuǎn)發(fā)時間通過數(shù)據(jù)包的大小L和鏈路的最大傳輸速率Bi,j的比值來衡量。每個無人機節(jié)點具備一定的初始能量,當一個節(jié)點有數(shù)據(jù)包要發(fā)送或者排隊時,就視為工作狀態(tài)消耗能量;否則,節(jié)點處于休眠狀態(tài),即不消耗能量。使用ei表示節(jié)點i的剩余能量,為初始能量與消耗能量之差。當節(jié)點能量低于給定的閾值時,該節(jié)點被視為不活躍節(jié)點,并不可到達。能量為0時,刪除該節(jié)點。

1.2 智能體狀態(tài)設定

將無人機自組網(wǎng)的分布式路由問題建模為馬爾可夫決策過程(Markov decision process,MDP)。MDP基于一組交互對象,即智能體和環(huán)境進行構(gòu)建,所具有的要素包括狀態(tài)、動作、策略和獎勵。在模擬過程中,智能體感知當前狀態(tài),按策略對環(huán)境實施動作,從而改變環(huán)境狀態(tài)并得到獎勵,獎勵隨時間的累積被記作回報。由于本次研究的是分布式路由協(xié)議,因而將網(wǎng)絡中每個無人機節(jié)點視為一個智能體,智能體根據(jù)網(wǎng)絡環(huán)境的狀態(tài)智能地作出決策,選擇動作。馬爾可夫決策過程通常情況由四元組(S,A,P,R)來定義,其中S是狀態(tài)的有限集合,A是動作的有限集合,P是智能體在t時刻執(zhí)行動作at后從狀態(tài)st轉(zhuǎn)移到狀態(tài)st+1的轉(zhuǎn)移概率,R是智能體在執(zhí)行動作at之后獲得的即時獎勵,代表當前動作在當前意義上的好壞程度。本文采用無模型的強化學習方法,在狀態(tài)轉(zhuǎn)移概率矩陣P未知的前提下,也可以優(yōu)化改進策略。下面給出狀態(tài)空間、動作空間和獎勵函數(shù)的詳細定義。

獎勵函數(shù):獎勵函數(shù)rt(st,at)指智能體在t時刻執(zhí)行動作at后由狀態(tài)st轉(zhuǎn)移到狀態(tài)st+1時環(huán)境給予智能體的即時獎勵。本文提出一種分布式的獎勵策略。一方面,獎勵函數(shù)包括描述個體之間相互作用的局部獎勵,即關(guān)于兩個相鄰節(jié)點之間的信息。另一方面,引入全局獎勵來反映執(zhí)行動作的質(zhì)量,即數(shù)據(jù)包的傳輸方向。具體地,使用所有的數(shù)據(jù)包最終路徑計算獎勵,之后將獎勵分配給路徑中的每個智能體節(jié)點計算每個節(jié)點的價值,最后計算全局獎勵。本文將數(shù)據(jù)包i最后一跳動作的即時獎勵定義為

(2)

通過定義狀態(tài)空間、動作空間以及獎勵函數(shù),可以將無人機自組網(wǎng)路由問題表述為MDP。智能體的目標是找到確定性的最佳策略π,使總累積獎勵最大化?；谇笆龉?可將基于深度強化學習的無人機組網(wǎng)路由問題定義為最大化未來累積獎勵Gt=rdes+γrdes-1+γ2rdes-2+…,為了估計未來的累計獎勵,將Q函數(shù)表示為累計未來獎勵的期望,即

Qπ(st,at)=E[Gt|st=s,at=a]=

E[rdes+γrdes-1+γ2rdes-2+…|st=s,at=a],

?st∈S

(3)

2 算法設計

2.1 方法選擇

采用強化學習方法(Q-learning)需要把所有的Q值存放在Q表中,在大規(guī)模無人機協(xié)同網(wǎng)絡中, Q表會異常龐大。無人機硬件的限制導致Q表進行數(shù)據(jù)存儲和更新的效率低下,從而影響任務的執(zhí)行效能。利用深度Q網(wǎng)絡(deep Q-network, DQN)算法將基于強化學習的 Q-learning算法中的Q表更新過程轉(zhuǎn)化為函數(shù)擬合問題,可以解決 Q-learning算法不適用于高維狀態(tài)動作空間的問題。DQN算法如圖1所示。

圖1 DQN算法示意圖Fig.1 DQN algorithm diagram

本文總體使用分布式設計,每一個無人機節(jié)點都可根據(jù)觀測到的網(wǎng)絡狀態(tài)信息st,并根據(jù)ε-greedy原則選擇動作at。以概率ε隨機選擇鄰居節(jié)點作為下一跳,以概率1-ε選擇Q值最大的鄰居節(jié)點作為下一跳。之后智能體會獲得獎勵rt(st,at),并進入下一狀態(tài)st+1。經(jīng)驗信息(st,at,rt,st+1)被存放在智能體的經(jīng)驗回放記憶單元。

2.2 方法結(jié)構(gòu)描述

強化學習產(chǎn)生的數(shù)據(jù)樣本之間是相互關(guān)聯(lián)的,使智能體的訓練難以收斂。隨機采樣經(jīng)驗回放記憶單元中的樣本可以消除經(jīng)驗數(shù)據(jù)之間的相關(guān)性,還允許智能體使用新舊經(jīng)驗來進行訓練,使得智能體的訓練更加高效。在訓練過程中,Q值將被改變,如果使用不斷變化的值來更新Q網(wǎng)絡,那么估計值會難以控制,導致算法不穩(wěn)定。為了解決這個問題,使用一個目標神經(jīng)網(wǎng)絡來頻繁但緩慢地更新訓練神經(jīng)網(wǎng)絡的 Q值,顯著降低目標值和估計值之間的相關(guān)性,從而穩(wěn)定算法。智能體框架如圖2所示。

圖2 智能體框架圖Fig.2 Agent framework diagram

圖3展示了DQN利用評估網(wǎng)絡的Q估計值來近似真實Q值的模型形式。該模型包括:1個輸入層、1個輸出層和2個隱藏層。輸入層由負責將信息發(fā)送到隱藏層的輸入神經(jīng)元組成。隱藏層負責將數(shù)據(jù)發(fā)送到輸出層。每個神經(jīng)元都有加權(quán)的輸入、激活函數(shù)(在給定輸入的前提下定義輸出)和一個輸出。

圖3 智能體神經(jīng)網(wǎng)絡結(jié)構(gòu)Fig.3 Agent neural network structure

令θ表示訓練神經(jīng)網(wǎng)絡的參數(shù),θ-表示目標神經(jīng)網(wǎng)絡的參數(shù)。神經(jīng)網(wǎng)絡的訓練過程是最優(yōu)化損失函數(shù),即目標值和網(wǎng)絡輸出的估計值之間的偏差。DQN智能體最小化損失函數(shù)定義為

LDQN(θ)=E[(y-Q(s,a,θ))2]

(4)

y=r+γmaxQ(s′,a′,θ-)

(5)

(4)—(5)式中:Q(s,a,θ)是訓練神經(jīng)網(wǎng)絡輸出的估計值;y是目標神經(jīng)網(wǎng)絡計算的目標值。本文采用梯度下降法以學習率α更新訓練神經(jīng)網(wǎng)絡的參數(shù)θ,即

?LDQN(θ)=E[(y-Q(s,a,θ))?Q(s,a,θ)]

(6)

θ←θ+α?LDQN(θ)

(7)

通過將多步訓練神經(jīng)網(wǎng)絡的參數(shù)復制到目標神經(jīng)網(wǎng)絡,以此更新目標神經(jīng)網(wǎng)絡的參數(shù)。該算法主要分為預訓練和策略學習兩個階段。

算法初始化:初始化具有隨機權(quán)重θ的訓練神經(jīng)網(wǎng)絡和具有權(quán)重θ-的目標神經(jīng)網(wǎng)絡、經(jīng)驗回放記憶單元Dreplay、數(shù)據(jù)采樣比例η和預訓練的步驟k、收集數(shù)據(jù)并以(st,at,rt,st+1)的形式存儲在演示數(shù)據(jù)緩沖區(qū)Ddemo中。

預訓練階段:首先,從演示數(shù)據(jù)緩沖區(qū)Ddemo中采樣部分數(shù)據(jù)對智能體進行訓練;其次,用目標神經(jīng)網(wǎng)絡計算損失函數(shù)LDQN;然后,用梯度下降法更新訓練神經(jīng)網(wǎng)絡參數(shù)θ←θ+α?LDQN(θ),每C步更新目標神經(jīng)網(wǎng)絡參數(shù)θ-=θ,循環(huán)k次。

策略學習階段:智能體收集網(wǎng)絡信息獲得狀態(tài)st,根據(jù)ε-greedy選擇動作at,獲得獎勵rt,并進入下一狀態(tài)st+1;將狀態(tài)轉(zhuǎn)移對(st,at,rt,st+1)作為經(jīng)驗數(shù)據(jù)被添加到經(jīng)驗回放記憶單元Dreplay中,再從演示數(shù)據(jù)Ddemo和回放記憶單元Dreplay隨機采樣訓練智能體,之后使用目標神經(jīng)網(wǎng)絡計算損失函數(shù);最后,使用梯度下降方法更新訓練神網(wǎng)絡參數(shù),每C步更新目標神經(jīng)網(wǎng)絡參數(shù)θ-=θ,這個過程一直循環(huán)到訓練結(jié)束。

3 仿真分析

3.1 仿真流程及參數(shù)設置

本文仿真使用Python3.6編寫事件驅(qū)動模擬器的代碼,以Pytorch作為深度學習框架來實現(xiàn)基于DQN的路由算法,并基于NetworkX來搭建無人機組網(wǎng)網(wǎng)絡環(huán)境。

為評估算法在實際無人機組網(wǎng)下的性能,需要在具有自定義數(shù)量節(jié)點的無人機網(wǎng)絡上重復進行訓練。為了契合無人機集群作戰(zhàn)的實際場景,設定每個節(jié)點都有隨機數(shù)量的鄰居節(jié)點,并且隨時有可能脫離鄰居節(jié)點的有效通信范圍。初始化每個節(jié)點的隊列長度、發(fā)送隊列長度,以及節(jié)點之間的無線鏈路數(shù)據(jù)傳輸速率、數(shù)據(jù)包大小;設定最大壽命為節(jié)點總數(shù)的一半,每個數(shù)據(jù)包的源節(jié)點和目的節(jié)點隨機生成。具體的參數(shù)設置如表1所示,仿真流程如圖4所示。

表1 仿真參數(shù)設置

圖4 仿真流程圖Fig.4 Simulation flow chart

典型的無人機自組網(wǎng)場景如圖5所示。假定任務區(qū)域內(nèi)的無人機數(shù)量為50—110 架,每一架無人機被視為一個網(wǎng)絡節(jié)點和智能體,都能夠根據(jù)實時的網(wǎng)絡狀態(tài)和學習到的最優(yōu)策略發(fā)送和接收數(shù)據(jù)包,且網(wǎng)絡拓撲高度動態(tài),鏈路會隨機斷裂與恢復。

圖5 任務場景Fig.5 Task scenario

仿真開始后,系統(tǒng)創(chuàng)建一個模擬數(shù)據(jù)包路由的過程,在一系列時間步長上離散更新。在仿真的一個回合中,鏈路隨機斷裂,并在每個時間步長隨機恢復。此外,鏈路權(quán)重以近似正弦方式波動。回合開始時,網(wǎng)絡上會生成許多數(shù)據(jù)包,每個數(shù)據(jù)包都有一個隨機的源節(jié)點和目標節(jié)點。每發(fā)送完成一個數(shù)據(jù)包,即有一個新的數(shù)據(jù)包在若干時間步長后初始化。一旦在網(wǎng)絡上生成并成功傳遞了一定數(shù)量的數(shù)據(jù)包,當前回合就結(jié)束了。仿真要求路由過程根據(jù)一種路由算法確定每個數(shù)據(jù)包的路徑。本文通過Dijkstra算法探索最短路徑,采用各種獎勵函數(shù)探索分布式Q學習以及深度Q學習。

3.2 仿真結(jié)果

圖6給出了在50個節(jié)點、訓練個回合下數(shù)據(jù)包傳輸時間的收斂性能情況,該場景考慮了每一個回合下的傳輸性能。從圖6可以看出,隨著訓練的進行,數(shù)據(jù)包平均傳輸時間在0—500 個回合中快速下降,在1 000個回合后逐漸平穩(wěn)趨于收斂,從而驗證了本文算法具有很好的收斂性能。

圖6 傳輸時間收斂性能Fig.6 Transmission time convergence performance

圖7展示了端到端傳輸時延對比情況。由圖7可見,本文算法隨著節(jié)點數(shù)量的增加時延緩慢上升,與AODV協(xié)議以及Q-Routing的時延差距顯著,表明本文算法更適用于大規(guī)模無人機集群場景。

圖7 不同算法端到端時延對比Fig.7 Algorithm end-to-end delay comparison

圖8為控制開銷對比。從圖8可以看出,基于本文算法的路由協(xié)議具有較小的控制開銷,而AODV路由協(xié)議控制開銷較大,從而使得網(wǎng)絡中發(fā)送的控制消息較多。本文算法能在相同情況下減少控制消息發(fā)送的大小,從而提升了網(wǎng)絡的性能。

圖8 控制開銷對比Fig.8 Control overhead comparison

圖9給出了在50個節(jié)點、不同算法最大隊列長度對比。從圖9可以看出,AODV協(xié)議的最大隊列長度在140左右浮動,而本算法的最大隊列長度隨著數(shù)據(jù)包數(shù)量的增大,從40逐步上升到140。網(wǎng)絡數(shù)據(jù)包排隊長度越大,說明網(wǎng)絡擁塞程度越高。當數(shù)據(jù)包數(shù)量越來越多,算法性能也會逐漸下降。在數(shù)據(jù)包4 000—5 000區(qū)域內(nèi),各算法波動較小,已達到各算法的較大性能。

圖9 最大隊列長度對比Fig.9 Maximum queue length comparison

圖10給出了不同算法的平均傳輸時間對比。從圖10可以看出,本文的算法具有較低的平均傳輸時間,并且增長幅度較為平穩(wěn);最短路徑算法的傳輸時間較長,并且隨著數(shù)據(jù)包數(shù)量的增多,傳輸時間的增長幅度也會變大。這印證了本文算法具有更優(yōu)異傳輸性能的結(jié)論。

圖10 平均傳輸時間(步)對比Fig.10 Average delivery time(step) comparison

圖11展示了不同業(yè)務量大小的滿負載節(jié)點占比大小的對比。從圖11可以看出,本文算法在相同業(yè)務量下滿負載節(jié)點(擁塞節(jié)點)所占比例明顯更低。擁塞節(jié)點比例越高,說明網(wǎng)絡的擁塞程度越高,從而導致網(wǎng)絡更易擁塞降低用戶服務質(zhì)量。因此,也證明了本文算法擁有較好的網(wǎng)絡傳輸性能。

圖11 擁塞節(jié)點比例對比Fig.11 Percent of working nodes at capacity comparison

綜上所述,本文算法在端到端傳輸時延、控制開銷、擁塞性能方面均優(yōu)于AODV路由協(xié)議以及Q-Routing。這是因為本文算法利用深度強化學習感知學習無人機節(jié)點移動性、鏈路連接特性、網(wǎng)絡拓撲動態(tài)變化,無人機節(jié)點通過不斷地與環(huán)境進行交互,探索學習最優(yōu)行動(路由)策略,根據(jù)學習結(jié)果找到滿足要求的路由,并能通過存儲的經(jīng)驗知識,維護端到端路由,賦予無人機網(wǎng)絡智能化重構(gòu)和快速修復的能力,提高路徑的穩(wěn)定度,降低路由建立和維護開銷,增強網(wǎng)絡的魯棒性。

4 結(jié) 論

國內(nèi)外關(guān)于無人機自組網(wǎng)路由協(xié)議的研究表明,深度強化學習是提高無線網(wǎng)絡性能的一個很有前途的方式。目前關(guān)于無人機自組網(wǎng)和深度強化學習的研究大多是獨立進行的,無法充分利用強化學習技術(shù)的學習能力來自適應地優(yōu)化網(wǎng)絡路由,這極大地限制了深度強化學習技術(shù)改善無人機網(wǎng)絡性能的潛力。為了體現(xiàn)深度強化學習技術(shù)在無人機自組織網(wǎng)絡中的優(yōu)勢,進一步提高無人機網(wǎng)絡的智能化程度,滿足未來無人機網(wǎng)絡發(fā)展與實戰(zhàn)化的需求,本文提出了一種基于深度強化學習的分布式無人機自組網(wǎng)高效路由算法。該算法能夠通過訓練網(wǎng)絡中每一個網(wǎng)絡節(jié)點來學習路由策略,使用了更適用于大規(guī)模無人機組網(wǎng)的DQN算法,摒棄了傳統(tǒng)集中式訓練的思想,可顯著增強網(wǎng)絡的魯棒性,減少數(shù)據(jù)包的傳輸時間與跳數(shù),減少丟包率,同時有效地平衡能耗與網(wǎng)絡負載以延長網(wǎng)絡壽命。此外,本文算法解決了多智能體強化學習的學習速度慢、多智能體間相互影響及動作維度爆炸等問題,更加適用于未來無人機集群作戰(zhàn)的場景。