范文帝，王俊芳，黨 甜，杜龍海，陳 叢

(中國電子科技集團公司 第54研究所，石家莊 050081)

0 引言

隨著近幾年無人機在關鍵技術上的突破，在軍用和民用領域具有高機動性和低成本特性的無人機用途十分廣泛。在人們的日常生活生產活動中，無人機越來越多地出現，在精準農業(yè)、應急救援、交通管制、貨物遞送等領域發(fā)揮著重要作用[1-3]。

然而隨著無人化進程的加深，單無人機能力不足、資源有限、任務執(zhí)行低效，如同自然界中動物通過成群結伴來彌補個體能力的有限[4]，無人機集群執(zhí)行復雜任務成為無人機應用的重要模式，無人機集群信息實現實時傳遞的關鍵是無人機通信網絡。

但無人機通信網絡在實際操作中存在著眾多問題，比如，電力資源、功率資源等等都存在著資源利用率不高的問題。資源分配問題是智能場景下研究的一個熱點，一些啟發(fā)式算法被提出以解決資源分配問題，文獻[5]運用禁忌搜索算法解決火力資源分配；文獻[6]在資源分配問題上應用模擬退火算法，模擬退火算法容易實現，魯棒性強、質量高，但優(yōu)化過程所需時間較長；文獻[7]提出武器動態(tài)資源分配問題，用動態(tài)規(guī)劃的方法來解決，但是遞歸的使用在編碼過程中使得效率非常低；文獻[8]完善標準灰狼算法，提出解決資源分配難題的離散灰狼算法。群體智能算法的速度雖然與傳統(tǒng)算法相比有所提升，但僅僅針對一個問題進行解決，很難擴展到其他問題的應用，在解決動態(tài)資源分配問題上效果不佳。

在無人機通信網絡中，由于有限的頻譜資源和動態(tài)的無人機用戶需求，時隙分配最常被用來解決資源競爭和協(xié)調的問題。然而，時隙分配是一個經典的NP難題，困擾著眾多研究者。其中一些傳統(tǒng)的求解方式，如枚舉法、分支定界法、動態(tài)規(guī)劃法，這些都是很容易實現但又很緩慢的搜索方式；對于傳統(tǒng)的智能算法，如遺傳算法、差分進化算法，要想擴展有一定難度。巨大的狀態(tài)空間和不斷變化的環(huán)境使得傳統(tǒng)的決策方法在這方面的效果并不理想。

隨著各個研究領域深度強化學習技術的不斷發(fā)展，強化學習被重新應用到此項問題。更多基于深度強化學習技術解決資源分配問題的方法被提出[9-12]，強化學習算法訓練出的模型不僅決策速度快，而且擴展性強，能夠在各種場景中廣泛應用，能夠有效應對動態(tài)變化的環(huán)境，非常適用于動態(tài)資源分配問題。強化學習是一種基于經驗學習和探索的智能算法，可以通過對實時環(huán)境的反饋以及循環(huán)性訓練，不斷優(yōu)化決策結果。

文獻[13]對無人機網絡輔助移動邊緣計算執(zhí)行任務卸載策略這個領域做了一系列的研究探索，說明了基于強化學習的無人機網絡的資源分配和路徑規(guī)劃可以在當前相關研究中達到不錯性能；文獻[14]集中探討了無人機群網絡頻譜分配方面的研究，研究了使用強化學習的動態(tài)信道分配和動態(tài)時隙分配算法；文獻[15]主要探討了無人機集群中的資源分配和虛擬網絡映射問題，該文獻對現有的資源分配算法進行了分析，總結了其優(yōu)劣之處，同時提出了一種全新的資源分配算法；文獻[16]是以深度強化學習算法為基礎的資源分配問題研究，結合專家經驗與深度強化學習算法，探索引入專家數據對資源分配算法性能的影響。

為了對資源分配問題進行更好的研究，本文將在深度強化學習技術的幫助下，研究無人機通信網絡中如何更好地解決時隙分配問題。

本文基于近端策略優(yōu)化算法[17-18]，設計了一個更高效的方法求解時隙分配問題。設計方法中的PPO算法使用Kullback-Leibler(KL)散度來限制更新前后的策略變化，解決了傳統(tǒng)梯度下降優(yōu)化算法[19-20]只能用最小步長進行更新的限制，PPO算法通常能優(yōu)效地訓練智能體執(zhí)行復雜的控制任務。

1 無人機網絡時隙資源分配方案

1.1 問題描述

無人機通信網絡由M無人平臺節(jié)點組成，由集合M={1，2，…，M}表示，m∈M表示無人平臺節(jié)點的編號。其中，各無人平臺節(jié)點之間構成多跳場景，節(jié)點維護自身的一跳和兩跳鄰居表，分別用N1(m)和N2(m)表示第m無人節(jié)點的一跳和兩跳鄰居集合。為了便于表示，利用矩陣C表示所有節(jié)點的一跳鄰接矩陣：

(1)

其中：cm，n∈{0，1}表示第m節(jié)點和第n節(jié)點間是否存在鏈路，cm，n=1表示兩個節(jié)點之間存在鏈路，第m節(jié)點和第n節(jié)點互為一跳鄰居，即m∈N1(n)，否則，兩個節(jié)點之間不存在鏈路。

無人機通信網絡因其拓撲結構的動態(tài)性導致難以預先設定中心節(jié)點作為集中控制設備，進行全局的時隙資源動態(tài)分配。為了在無人機通信網絡中優(yōu)化調度時隙資源，需設計以節(jié)點為中心的時隙分配算法。在一個時隙調度周期中，假設共有K空閑數據時隙可分配給M個無人平臺節(jié)點用于發(fā)送數據，k表示時隙的編號。時隙的帶寬被表示為B。利用二元變量tm，k∈{0，1}表示第k時隙到第m無人節(jié)點的分配情況，其中，tm，k=1表示第k時隙被分配到第m無人節(jié)點用于傳輸數據，否則tm，k=0。

此時，網絡的信道利用率被定義為：

(2)

代表的是網絡分配的時隙數和所有能夠分配的時隙數的比值。

時隙分配問題可以構建為以提高信道利用率為目標的優(yōu)化問題。

另外，無人節(jié)點在請求時隙時，同時上傳自身網絡狀態(tài)信息，包括節(jié)點吞吐量、節(jié)點負載、時延等?？紤]到不同無人平臺節(jié)點上通信性能的差異性，將同一時隙分配給不同節(jié)點所帶來的網絡性能增益不同，因此為分配到節(jié)點的時隙設置效用函數。效用函數由每個時隙調度周期內節(jié)點上報的吞吐量、負載、時延等構成。為了消除不同性能指標間的量綱差異，對其進行歸一化，下面以負載為例：

負載：假設節(jié)點的負載狀態(tài)為Qm，每個節(jié)點可允許的最大負載和出現的最小負載分別是Qm，max、Qm，min，負載的歸一化指標為：

(3)

每個節(jié)點的效用函數利用Um表示，指該節(jié)點負載的歸一化指標的加權和，其表達式為：

(4)

其中：w的取值為1。

因此，為節(jié)點分配時隙的時候需要同時考慮網絡的信道利用率以及節(jié)點本身的網絡狀態(tài)。

在廣播調度問題中，存在兩個限制條件：一是非傳輸限制，即在一個調度周期內，網絡中的每個節(jié)點至少有一個時隙被調度；二是非沖突限制，即調度過程中要避免兩類沖突，第一類沖突是節(jié)點不能同時發(fā)送和接收數據，第二類沖突是一個節(jié)點不能同時接收超過一個傳輸[21]。

此時，時隙分配問題被構建為：

(5)

(6)

其中：公式(5)為加權信道利用率，式(6)中C1保障了在一個時隙調度周期內所有無人平臺節(jié)點至少存在1次時隙調度。假設兩跳以上的節(jié)點可以利用空間復用的方式避免干擾，C2約束同一個時隙不會分配給相鄰2個節(jié)點，C3約束分配到同一個時隙的節(jié)點間最多存在1條鏈路。

1)當存在中心控制節(jié)點時：

在無人機通信網絡中，當存在一個無人平臺節(jié)點是中心控制節(jié)點時，所有節(jié)點維護的鄰居表和網絡狀態(tài)等信息可以被收集到集中控制節(jié)點處，并基于這些數據對上述優(yōu)化問題進行全局求解。上述時隙分配問題是以二元時隙分配變量為優(yōu)化對象的整數線性規(guī)劃，可以利用混合整數線性規(guī)劃(MILP)求解器或者深度強化學習算法進行求解。

MILP求解器是一種計算機程序，可以解決包含整數變量的線性規(guī)劃問題。這些求解器使用分支定界法等算法來解決整數規(guī)劃問題，但它們通常比手動實現更高效。

2)當不存在中心控制節(jié)點時：

然而，由于無人機通信網絡中難以設定集中控制節(jié)點，求解上述以優(yōu)化全局網絡性能為目標的時隙分配問題時難以獲取所有節(jié)點的網絡狀態(tài)信息。為了進行時隙調度，假設節(jié)點要維護的鄰居表包括一跳和兩跳，同時還會維護一跳和兩跳鄰居的時隙分配表，可以將上述優(yōu)化問題拆分為以節(jié)點m為中心的時隙分配問題：

(7)

(8)

此時，優(yōu)化對象是所有時隙到節(jié)點m的調度情況。對于節(jié)點m而言，其一跳鄰居、兩跳鄰居、以及一跳鄰居和兩跳鄰居的時隙占用情況都是已知的。上述以節(jié)點m為中心的時隙分配問題是整數線性規(guī)劃問題，公式(8)中C1保障了在一個時隙調度周期內所有無人平臺節(jié)點至少存在1次時隙調度，C2和C3約束了變量tm，k的上界，C2約束同一個時隙不會分配給相鄰2個節(jié)點，C3約束分配到同一個時隙的節(jié)點間最多存在1條鏈路。另外，分析該優(yōu)化問題可知，對于無人平臺節(jié)點m，所分配到的時隙數量越多，其優(yōu)化目標函數越大，其變化是隨著其占用的時隙數量增加而單調遞增的。此時，節(jié)點m的時隙分配結果可以直接以貪婪的思路最終確定。

上文將全網的時隙分配問題拆分為以節(jié)點m為中心的時隙分配子問題進行求解，不再需要將所有節(jié)點的網絡狀態(tài)信息收集到集中控制設備，但是這種求解方式難以獲取全局最優(yōu)的結果。并且，值得注意的是，時隙調度的最終目標是為所有節(jié)點分配數據時隙。在以節(jié)點m為中心的時隙分配問題中，將同一時隙分配給不同節(jié)點所帶來的網絡性能增益不同，這說明節(jié)點時隙分配的順序對節(jié)點調度的公平性和穩(wěn)定性具有重要影響，為此，需要提出基于優(yōu)先級的節(jié)點時隙分配。

由于節(jié)點負載過高會導致時延提高和丟包率增加，當節(jié)點監(jiān)測到自身負載Qm超過一定閾值αm時，就需要請求更多數據時隙盡快傳輸緩存隊列的流量，此時該節(jié)點將臨時提高自身優(yōu)先級并將更新后的優(yōu)先級信息廣播給鄰居節(jié)點，這時節(jié)點的時隙分配順序也會相應的提前，有利于節(jié)點獲取占用更多時隙進行數據傳輸。當節(jié)點監(jiān)測到自身負載Qm低于一定閾值βm時，可恢復為初始優(yōu)先級，并將其更新消息廣播給其他節(jié)點。為了避免節(jié)點優(yōu)先級的頻繁變更導致時隙分配無法收斂，設置負載閾值αm和βm的取值滿足αm>βm。

當Qm≥αm時，更新節(jié)點優(yōu)先級的表達式可以定義為：

(9)

當βm

基于優(yōu)先級的節(jié)點時隙分配允許優(yōu)先級較高的節(jié)點獲得優(yōu)先進行時隙劃分的機會，通過調整時隙請求期間的參數，優(yōu)先解決高優(yōu)先級節(jié)點的時隙分配優(yōu)化問題，使得重要緊急的消息可以高效傳輸?；趦?yōu)先級的節(jié)點時隙分配流程如圖1所示。

圖1 基于優(yōu)先級的節(jié)點時隙分配流程

1.2 模型描述

為了提高多無人機網絡的通信效率和整體系統(tǒng)性能協(xié)作，本文將運用深度強化學習的研究成果，設計一種用于解決時隙資源分配問題的方案。

在2017年，OpenAI提出了PPO算法，這是一種深度強化學習算法，旨在通過使用PPO算法來讓智能體解決問題。為此，需要先建立一個MDP模型，這個模型由狀態(tài)空間(S)、動作空間(A)和獎勵函數(R)組成[22]。在t時刻，環(huán)境處于狀態(tài)St，智能體根據當前狀態(tài)選擇策略At，環(huán)境轉移到下一狀態(tài)St+1，同時智能體獲得相應的反饋獎勵Rt。

假設存在一個多無人機網絡，其中包含一組環(huán)境狀態(tài)S、動作集合A以及回報獎賞R。該網絡中共有N架無人機，并且每個周期需要分配T個時隙。具體的動態(tài)時隙分配環(huán)境映射如下所述。

環(huán)境狀態(tài)S：為了評估無人機在執(zhí)行動作后對環(huán)境狀態(tài)的影響，環(huán)境狀態(tài)主要用于描述這些影響的程度。這種程度可以包含積極的和負面的影響。根據環(huán)境狀態(tài)的變化，可以更方便地設計后續(xù)的獎勵函數[14]。環(huán)境狀態(tài)可以被定義如下：

S={s1，s2，…，sN}

在動態(tài)時隙分配的背景下，環(huán)境狀態(tài)可由多個方面來描述，即無人機節(jié)點的負載和無人機節(jié)點的鏈接拓撲等。

動作集合A：強化學習的另一個重要組成部分是動作。動作是無人機與環(huán)境交互的必備因素。通過不斷嘗試各種動作或策略，無人機可以獲取環(huán)境反饋的信息和獎勵值，以便快速了解采取何種動作或策略，以最大化環(huán)境收益[14]。動作集合可以定義如下：

A={a1，a2，…，aN×T}，ai∈{0，1}

式中，αi表示第i÷T時隙下的第imodT架無人機所采取的動作，也就是說該時隙下，無人機可以選擇兩種不同的動作再每個時隙中進行數據傳輸操作，ai=0表示無人機在該時隙中不進行數據傳輸；ai=1表示無人機在該時隙中試圖進行數據傳輸。

獎賞函數R：獎勵函數的作用是教導智能體向對環(huán)境有好處的方向前進，并且限制其行動范圍。一般來說，獎勵函數會根據環(huán)境的特點進行制定。在動態(tài)分配的情況下，通過狀態(tài)反饋來衡量環(huán)境的優(yōu)劣[14]。

為了實現讓智能體快速學習最優(yōu)時隙分配策略的優(yōu)化目標，本文設計了兩部分獎勵。第一部分是滿足三個約束條件下的評估情況，第二部分是計算網絡中通信的總負載量。

圖2展示了模型的決策流程。

圖2 決策流程圖

為了找到最佳的時隙分配策略，使得初始化狀態(tài)S的預期獎勵最大化，需要通過智能體與環(huán)境的交互來生成所有可能的時隙分配策略π*，以最大化系統(tǒng)整體的長期期望折扣獎勵：

(10)

最佳時隙分配策略可被表述為：

(11)

本文使用時隙分配系統(tǒng)時，不必考慮長遠回報。為此，我們引入衰減因子作為衰弱機制γ∈[0，1]。公式(11)中st+1描述無人機網絡環(huán)境在t+1時刻的狀態(tài)；at+1記錄智能體在t+1時刻的時隙分配行為；Rt+1(at+1，st+1)記錄t+1時刻的即時獎勵；γRt+1(at+1，st+1)表示長時間的衰減獎勵。

至此，我們已成功完成了強化學習中MDP建模的重要步驟。我們已經設計了模型中的狀態(tài)、動作和獎勵函數的三個關鍵要素。

2 基于近端策略優(yōu)化算法的時隙分配算法框架

2.1 算法框架

如圖3所示，本文所使用的PPO強化學習算法可以分為交互階段和學習階段兩個關鍵階段。

圖3 基于PPO算法的時隙分配系統(tǒng)體系結構

交互階段：智能體與環(huán)境互動，利用環(huán)境傳遞的狀態(tài)信息做出決策，環(huán)境再返回智能體下一時刻的狀態(tài)和基于該策略的獎勵。PPO算法采用經驗回放技術，運用經驗數據池D，幫助智能體更好地學習到最佳決策。該算法是一種在線學習策略，需要大量的樣本數據用于重新訓練模型。但是，數據集過大會導致訓練時間過長，收斂性較弱；而數據集過小則會影響模型的訓練效果[22]。PPO算法利用重要性采樣技術，通過創(chuàng)建一個固定大小的經驗池D，在解決上述問題時能夠重復使用樣本。

學習階段：每次進行迭代時，智能體會利用新生成的Actor網絡所提供的策略來選取動作，并與無人機網絡環(huán)境進行互動，以獲取樣本數據。當一個完整的經驗池D中的數據樣本被收集完畢后，Actor和Critic網絡會對其中的數據進行學習。策略更新的流程如圖3所示。

在每次迭代時，智能體使用新Actor網絡生成的策略選取動作與無人機網絡環(huán)境交互，得到一個(st，at，rt，st+1，πθ)樣本數據，當收集完一個完整的經驗池D的數據樣本后，Actor、Critic網絡會對經驗池D中的數據進行學習。

根據公式(10)可以計算出每個時刻的值函數：

γT-t+1rT-1+γT-tV(sT)

(12)

此時可以計算得到Critic網絡的損失函數：

(13)

進行反向傳播，以更新Critic網絡。

對于經驗池D中的每個狀態(tài)，我們將其輸入到兩個Actor網絡中，以獲得相應的正態(tài)分布。同時，我們輸入D中的每個動作以計算其在分布中的概率。通過將這些概率相除，我們得到了PPO算法的重要性采樣權重：

(14)

可以計算Actor網絡的誤差函數：

(15)

其中：ε是一個超參數，它用于限制策略更新幅度的clip函數。然后，通過反向傳播更新Actor新網絡，最終PPO的整體損失函數如下：

Lp=0.5×Lc+La

(16)

2.2 算法流程

如算法1所示是一種改進的無人機網絡時隙資源分配算法。

算法1：基于PPO算法的時隙資源分配算法

輸入: 馬爾可夫決策過程模型

輸出: 智能決策模型

1)設置模型超參數、訓練總回合數、批大小、學習率、衰減率γ,每次更新次數、最大步長、更新頻率

2)初始化經驗回放池D

3)初始化無人機網絡環(huán)境,生成網絡拓撲

4)初始化算法模型,策略網絡參數θ

5)Actor網絡參數設置采樣環(huán)境參數θold←θnew

6)fori= 1,2,…do

7) 重置環(huán)境

8) for each steptdo

9) 觀察無人機網絡初始狀態(tài)st

10) 將狀態(tài)st輸入到Actor new網絡得到動作at;

11) 在環(huán)境中執(zhí)行操作和下一個狀態(tài)st+1后得到獎勵rt,是否終止d

12) 將(st,at,rt,st+1,πθ)存入經驗回訪池D中

13) 最終狀態(tài)輸入Critic網絡中,根據公式(10)計算衰減后的獎勵

14) if 更新步驟等于經驗池D容量 then

15) 將記錄的狀態(tài)組合輸入到Critic網絡根據公式(12)估計優(yōu)勢函數

16) 使用梯度下降法優(yōu)化目標函數并更新網絡參數θnew

17) end

18) end

19) 更新舊策略模型參數θold←θnew

20)end

21)保存模型,繪制獎勵曲線和網絡損失曲線

3 仿真與分析

3.1 仿真原理及參數

仿真環(huán)境為OpenAI Gym框架，在Anoconda平臺使用Python語言實現。

在無人機網絡場景下，網絡的拓撲結構多種多樣，圖4中為典型的網絡拓撲，其中，鏈狀拓撲結構下，節(jié)點時隙復用的方式更多，三種拓撲結構同樣數量的節(jié)點下鏈狀拓撲結構運算復雜度最高，因此選取鏈狀拓撲結構進行仿真。

圖4 三種網絡拓撲圖

在仿真中設定節(jié)點數為4，5，時隙數為8，網絡拓撲為線性拓撲。下面以5節(jié)點舉例，網絡的鄰接矩陣為：

其中：Cij代表節(jié)點i、j的聯(lián)通情況，計算得到允許同時開通的矩陣：

Bij代表節(jié)點i、j是否能夠同時分配時隙。

隨機生成節(jié)點當前負載為Q=[10，12，4，4]。

對載荷進行歸一化后，U=[0.416 67，0.833 33，1，0.333 33，0.333 33]。

算法中獎勵的衰減率為0.99，PPO算法中clip參數為0.2。

3.2 仿真結果與分析

實驗的損失函數如圖5所示。

圖5 損失函數

可以看出模型的損失函數整體趨勢隨著訓練步數的增加而降低，說明模型朝預計的目標方向學習，算法收斂。

圖6為PPO算法的平均獎勵曲線，縱軸代表每輪中所有步數的獎勵之和，獎勵隨著訓練步數的增加而增大，在前150 000步的訓練中，提升幅度較大，快速得到局部最優(yōu)值，后250 000步的訓練獎勵值提升幅度較小，花銷大量時間尋找最優(yōu)獎勵。與5節(jié)點相比，4節(jié)點獎勵曲線增幅大致相同，比5節(jié)點快100 000步達到收斂得到最優(yōu)解。

圖6 獎勵函數

最終算法輸出如下時隙分配矩陣：

將負載代入公式(2)中計算加權信道利用率可得結果為21.875%。

其中200 000步時的局部最優(yōu)解的時隙分配矩陣為：

計算加權信道利用率為21.458%。使用貪心算法進行對比，優(yōu)先遍歷分配時隙，滿足一個周期至少開通一次的約束，再選擇載荷最大的節(jié)點分配時隙，得出如下時隙分配矩陣：

可知加權信道利用率為14.791%。

圖7為三種時隙分配矩陣的數據對比，其中PPO局部最優(yōu)為200 000步時的時隙分配情況，由此可見PPO算法在前200 000步即可得到局部最優(yōu)解，但尋找到最優(yōu)解需要花費翻倍的時間，以5節(jié)點網絡為例，最優(yōu)解比局部最優(yōu)解提高了1.94%，訓練步數多出200 000步，因此PPO算法最優(yōu)解與局部最優(yōu)解存在折中關系，可以根據實際需求適當縮短訓練時間得到加權信道利用率略微低于最優(yōu)解的時隙分配方案。

圖7 貪心算法、PPO算法局部最優(yōu)、最優(yōu)解加權信道利用率對比

與貪心算法對比可以看出PPO算法的局部最優(yōu)解和最優(yōu)解都顯著優(yōu)于貪心算法，與貪心算法相比，PPO算法局部最優(yōu)解加權信道利用率提高了45.07%，最優(yōu)解集權信道利用率提高了47.89%。

圖8為節(jié)點數為4、5，需分配的時隙數為5～30的PPO算法與貪心算法的加權信道利用率對比。當節(jié)點數固定時，PPO算法得到的加權信道利用率隨時隙的增加而增大；相比于5節(jié)點，4節(jié)點網絡下PPO算法得到的加權信道利用率更高；PPO算法比貪心算法加權信道利用率提高了45%左右。

圖8 貪心算法、PPO算法加權信道利用率對比

通過仿真結果對PPO算法在時隙分配優(yōu)化方面的有效性進行分析，該算法能夠收斂到最優(yōu)，最優(yōu)解與局部最優(yōu)解間存在折中關系，可以根據實際需求來選取，對比貪心算法，PPO算法有巨大優(yōu)勢。

4 結束語

近些年來隨著多無人機網絡的研究與應用的不斷深入，多無人機網絡資源分配問題具有很重要的研究意義。本文根據多無人機網絡差異化節(jié)點負載的特點，為了適配網絡業(yè)務流量，針對多無人機網絡動態(tài)時隙分配問題，將網絡拓撲結構納入考慮，提出了基于PPO算法的時隙分配方案。仿真結果表明，相比于貪心算法，提出的深度強化學習方案，有效提高了信道利用率。