基于多智能體強化學習的多無人機邊緣計算任務卸載

李 斌

(1.南京信息工程大學 計算機學院，江蘇 南京 210044；2.南京信息工程大學 江蘇省大氣環境與裝備技術協同創新中心，江蘇 南京 210044)

0 引言

移動邊緣計算(Mobile Edge Computing,MEC)技術能有效緩解資源受限設備執行密集型應用的壓力,可提高網絡的應用體驗[1-2]。在臨時部署通信服務的偏遠地區或聚集活動熱點地區等通信條件較差的場景,地面固定式通信設施難以提供較好的服務。利用無人機(UAV)高機動性、易部署和立體式增強覆蓋等優勢,將UAV與MEC相融合可以提供泛在的接入服務和高質量的計算服務[3-4]。

如今,UAV輔助MEC網絡成為了學術界和工業界的研究熱點,然而各類參數及用戶服務需求時刻發生著變化[5]。深度強化學習(Deep-Reinforcement Learning,DRL)作為人工智能的一種新興技術,通過與環境不斷交互學習、積累經驗,從而尋求最優策略[6]。相較于離線求解及迭代算法,采用經過訓練的DRL策略能實時地求解系統的能耗與時延等優化問題[7]。為了適應動態變化的網絡狀態與環境,結合DRL方法能夠實時進行決策的優勢,研究人員提出了一系列高效的資源管控優化算法。針對兩層UAV網絡架構,文獻[8]結合深度Q網絡(Deep Q Network,DQN)與深度確定性策略梯度(Deep Deterministic Policy Gradient,DDPG),設計了一種DRL訓練框架,以優化UAV軌跡與虛擬機配置,進而有效地降低系統時延。文獻[9]利用智能反射面的通信輔助能力,使用DDPG與雙深度Q網絡(Double Deep Q Network,DDQN)協同優化網絡資源以提高UAV邊緣計算的能效。為提升移動用戶群組的服務體驗,文 獻[10]通過聚類算法設計UAV動態部署,并采用DDPG方法優化服務關聯,從而降低了系統能耗。文獻[11]考慮了多任務調度問題,根據信道狀態、任務請求等信息以最小化加權信息年齡,設計了一種基于近端策略優化(Proximal Policy Optimization,PPO)的DRL算法。然而,DDQN、DDPG和PPO等單智能體DRL算法不能很好地應對當網絡規模較大時所帶來的狀態空間及動作空間維數過高的問題。

在實際場景中,多個移動用戶(Mobile User,MU)和多個邊緣服務器通常部署在不同的位置,易于利用分布式算法進行訓練與決策。同時,多智能體強化學習(Multi-Agent Reinforcement Learning,MARL)方法能較好地適應MEC的分布式結構。相比于單智能體DRL,MARL能夠減小狀態空間與動作空間,并可高效地做出決策。鑒于此,文獻[12]面向多UAV邊緣計算,利用MARL方法較好地解決了負載均衡問題。文獻[13]利用多智能體確定性深度策略梯度(Multi-Agent Deep Deterministic Policy Gradient,MADDPG)方法實時優化多UAV軌跡,最大化計算服務的公平性。文獻[14]面向多UAV網絡中的隱私問題,利用多智能體聯邦學習進行分布式訓練,達到了與MARL接近的效果。雖然上述工作應用了MARL的分布式結構,但尚未充分利用不同設備的功能,缺乏多類型設備、異構智能體協作優化MEC服務的研究。同時,上述工作存在服務質量不穩定、算法訓練速度慢和UAV軌跡曲折難以實現等問題。

基于此,本文考慮到任務分布式卸載的特點,采用多智能體近端策略優化(Multi-Agent Proximal Policy Optimization,MAPPO)方法,并在MARL算法引入了Beta分布以及注意力機制以提升算法的性能,加快算法的收斂速度,從而有效降低MEC服務的開銷。本文的主要工作有如下三方面:

① 研究了多架UAV輔助MEC的系統模型,綜合考慮MU的移動性、任務生成的隨機性和多UAV之間的安全距離,建立了MU和UAV的加權能耗最小化問題。該問題具有高動態特征,對優化實時性和規模擴展性提出了更高的要求。

② 設計了一種異構MARL方法,通過構建含有3種智能體的系統,基于MAPPO算法訓練MU和UAV協同完成卸載決策與資源分配。該分布式決策方法能分解較大的環境狀態與動作空間,并將決策能力下沉到各類設備,提高算法的可擴展性。

③ 在Actor網絡輸出層使用Beta分布以提高動作的探索效率和采樣性能,并向Critic網絡中引入注意力機制以提高MARL方法的值函數擬合性能。提出了基于MAPPO的能耗最小化任務卸載方法(Energy-efficient-Attention-Beta-MAPPO,E-ABMAPPO),該方法具有較快的收斂性,且系統性能優于基準方法。

1 系統模型及問題描述

本文考慮一種多UAV輔助的MEC系統模型,如圖1所示。在該系統中,MU需要將產生的計算任務卸載到UAV邊緣服務器進行計算。此系統模型有 1個地面控制中心,M架搭載邊緣服務器的UAV為K個MU提供任務卸載服務。為便于表達和分析,定義MU的集合為?{1,2,…,K},UAV集合為?{1,2,…,M}。此外,地面控制中心需要借助UAV收集通信鏈路信道信息、MU的服務需求等系統狀態,進而對邊緣網絡進行即時管控。

(1)

式中:amax為UAV的最大加速度,vmax為UAV最大飛行速度,dmin為UAV之間的最小安全距離。

假設MU初始隨機分布,且按照Gauss-Markov模型隨機移動[15]。在時隙n內,MUk的速度大小vk[n]和移動的方向角度θk[n]可表示為:

(2)

(3)

(4)

(5)

1.1 計算模型

(6)

① 本地計算:為了充分利用MU有限的計算資源并最小化能耗開銷,本地計算將采用動態電壓頻率縮放技術以給出計算頻率。在最大計算頻率限制下,本地計算頻率可表示為:

(7)

(8)

② 邊緣計算:MU可以將自身計算任務卸載至所關聯UAV邊緣服務器進行處理,具體過程如下:

首先,UAV需要分配通信信道的帶寬資源以接收來自MU的任務數據。考慮到大尺度衰落和小尺度衰落,則在時隙n內UAVm和MUk之間的信道增益可表示為:

(9)

(10)

(11)

當MU請求將任務卸載至UAV之后,UAV需分配其計算資源,完成任務的處理。記UAVm可用的計算頻率為fm,UAVm在時隙n內為MUk分配的計算資源為fm,k[n]。由此,其滿足約束:

(12)

(13)

綜上所述,MUk的任務計算時延需滿足的約束可以表示為:

(14)

式中:bk,m為帶寬分配系數,B為帶寬,σ2為噪聲功率。

1.2 能耗模型

定義MU和UAV服務器上CPU的有效電容系數為κ,則MUk的計算能耗和傳輸能耗分別為:

(15)

(16)

由上述分析可知,在時隙n內,MUk的總能耗為:

(17)

根據文獻[17],UAVm在時隙n內的飛行能耗可表示為:

(18)

式中:P0為UAVm懸停狀態下型阻功率,Pi為UAV懸停狀態下的誘導功率,v0為UAV懸停下的平均旋翼誘導速度,d0為機身阻力比,s為總葉片面積與葉片掃過面積之比,ρ0為空氣密度,A為UAV葉片掃過的面積。UAVm的計算能耗為:

(19)

2 優化問題描述

(20)

式中:?1、?2、η為能耗權重因子,∏(·)為指示函數,當條件(·)為真時值為1,否則值為0;約束條件C1～C4表示UAV的飛行軌跡,約束條件C5表示卸載關聯因子取值,約束條件C6表示每個MU至多選擇一個UAV卸載,約束條件C7～C8表示UAV帶寬資源與計算資源分配限制,約束條件C9為任務的時延約束,約束條件C10限制了任務劃分系數的范圍,約束條件C11～C12限制了UAV劃分給MU的資源,C13保證了資源分配的有效性,避免不進行任務卸載的用戶空占計算資源。

由于MU的隨機移動性、卸載關聯的離散性以及非凸約束,上述問題不僅僅是一個多變量耦合的非凸組合優化問題,更是一個需要實時決策的優化問題。DRL作為一種自適應的機器學習方法,可以從環境中不斷采樣學習,并訓練得到能部署在設備上的深度策略模型,從而根據當前狀態,做出符合長期效益的實時決策,因此適應于所研究的MEC任務卸載場景。

3 基于MAPPO的優化問題求解

3.1 MDP模型

問題(20)需要聯合優化多個MU以及多個UAV的決策信息,并且MU以及UAV在服務過程上存在協作關系,在計算和通信資源上存在競爭關系。考慮到該問題具有分布式特征,可將其建模為由多個智能體構成的MDP模型。根據決策變量與目標函數的相關性以及部署位置的差異,將MU作為一種智能體,將UAV分解為2種智能體:UAV資源分配智能體與UAV軌跡優化智能體,因此所提出的MDP模型共有3種智能體參與。

① MU智能體:MU的基本要素包括觀測ok(t)、動作ak(t)和獎勵rk(t),具體如下:

(21)

動作:MU的決策涉及卸載關聯α和任務劃分系數ρ,每個MU需要選擇關聯的UAV,決定其任務劃分系數。因此MU智能體k的動作由下式給出:

(22)

獎勵:從協作性角度,UAV的能耗負擔需要為所有關聯的MU所知。從針對性角度,需要考慮每個MU自身能耗開銷對總加權能耗的貢獻,以及自身不滿足時延要求的懲罰。因此,每個MU的獎勵應該綜合考慮MU本身和所關聯UAV的能耗,每個MU的獎勵由下式給出:

(23)

式中:mk為MUk所關聯的UAV。

MUk不滿足時延要求時的懲罰函數為:

(24)

式中:χt為懲罰系數。

② UAV資源分配智能體:每個UAV需要在MU給出卸載關聯因子及卸載量后做出決策。因此,其MDP基本要素表述如下

oK+m(t)?{qm[n],q-m[n],Ωk[n],wk[n],ρk[n],?k∈}。

(25)

動作:UAV收到MU請求后,需要根據用戶任務請求、位置等信息分配帶寬和計算資源。因此,UAV資源分配智能體m的動作為:

aK+m(t)?{bm,k[n],fm,k[n]/fm,?k∈}。

(26)

獎勵:接收MU的計算任務后,UAV從環境中獲得獎勵。作為服務提供者,每個UAV的獎勵需要考慮自身開銷和所服務的MU的能耗,在未滿足用戶時延需求時需要給出一定的懲罰,可以設計得到UAV獎勵函數如下:

(27)

③ UAV軌跡優化智能體:UAV已經獲取了有價值的狀態信息,UAV軌跡優化智能體與UAV資源分配智能體可以共享觀測,即oK+M+m(t)=oK+m(t)。其動作與獎勵如下:

動作:UAV軌跡優化智能體m需要給出UAVm的移動狀態,通過水平加速度變量控制軌跡變化,其動作為:

aK+M+m(t)?{am[n]}。

(28)

獎勵:為獲得優化效果更好的軌跡,可通過設計更加具有反饋意義的獎勵函數,進而提高動作與目標函數的相關性。當無人機嘗試飛出服務范圍時,需要給出一定懲罰,因此該種智能體的獎勵可設置為:

Po(qm[n+1]),

(29)

式中:dk,m[n′]表示MUk與UAVm在時隙n′的水平距離。上式反映了各個UAV與所服務MU的當前移動平均距離的最大值,以盡可能兼顧到所服務的MU,并促使UAV共同協作,且UAV試圖飛出寬度為W的正方形服務區域時給出的懲罰函數為:

(30)

式中:χo為懲罰系數。假設當UAV智能體輸出的動作會導致UAV飛出邊界或發生碰撞時,該動作無效,UAV將會保持在當前位置。

3.2 基于MAPPO的任務卸載算法

與基于值的DRL方法不同,MAPPO是一種基于策略的方法[18],每個智能體由Actor網絡、Critic網絡和經驗緩存區組成,能通過作為策略的Actor網絡直接輸出動作得到決策變量,因此MU和UAV可以將預訓練的Actor網絡部署到本地,并行地進行分布式決策。

(32)

(33)

式中:ξi為Critic網絡i的參數。因此,Actor網絡和Critic網絡分別根據式(31)和式(33)更新。

3.3 E-ABMAPPO訓練框架

本文所提出的E-ABMAPPO訓練框架如圖2所示,MU和UAV根據其智能體的Actor網絡所給出的動作執行任務卸載,UAV與地面控制中心同步收集狀態、動作等經驗組成部分以及系統狀態。隨后,地面控制中心通過各智能體的觀測獲得全局環境狀態,計算獎勵值,將經驗存入智能體的緩沖區,并獲得預測值。在更新Actor網絡和Critic網絡后,Actor網絡的參數被下載到UAV和MU。

圖2 E-ABMAPPO算法訓練框架Fig.2 Training framework of E-ABMAPPO algorithm

為了充分挖掘MAPPO的性能,并加速其收斂,本文在訓練中引入了Beta分布和注意力機制,具體方式如下:

① 基于Beta分布策略的Actor網絡:MEC場景中的決策變量通常是連續且有界的,因此智能體輸出的動作應盡可能滿足此條件。由于Gaussian分布無界,通過強制截斷輸出動作的越界值將會導致邊界效應,將不可避免地引入策略梯度的估計偏差[19]。為了緩解Gaussian分布策略的邊界效應影響,本文在策略網絡的輸出層使用Beta分布替換Gaussian分布。Beta概率分布密度由下式給出:

(34)

式中:Γ(·)為Gamma函數,α和β為Beta分布的參數。式(34)有界,可以減小截斷Gaussian分布帶來的策略梯度估計誤差,因此適合對有界動作進行采樣。

② 具有注意力機制的Critic網絡:對于簡單全連接層的Critic網絡而言,大量的狀態輸入會導致所需的模型復雜度快速升高,從而導致Critic網絡的收斂緩慢或者難以收斂,對Actor網絡的動作造成消極影響。本文在Critic網絡的多層感知器(Multilayer Perceptron,MLP)之前引入了多頭注意力單元,以提高模型訓練的收斂性能。對于同種類型智能體的Critic網絡,首先接受所有智能體的觀測向量,將每種智能體的觀測向量分別通過MU和UAV的MLP狀態編碼器,獲得特征值ei。然后將所有智能體的特征值ei作為qi、ki、vi輸入其多頭注意力單元,以獲得各注意力值xi,具體計算如下:

(35)

(36)

基于上述討論,本文建立了E-ABMAPPO的訓練框架,其算法實現過程如算法1所示。

算法1 基于E-ABMAPPO訓練框架的聯合優化算法輸入:最大回合數Epmax,回合長度epl,PPO更新次數PE,折扣因子γ,PPO截斷因子,GAE參數λ輸出:訓練后各智能體的Actor網絡與Critic網絡1. 初始化各類神經網絡模型參數,設置n=1,構建訓練環境; 2. FOR Episode,1≤Episode≤Epmax DO3. FOR t,1≤t≤epl DO4. MU智能體從環境中獲得觀測ok(t),?k∈;5. 執行動作ak(t),?k∈;6. UAV資源分配智能體和UAV軌跡優化智能體從環境中獲得觀測oK+m(t),oK+M+m(t),?m∈;7. 地面控制中心收集系統狀態與經驗信息,評估獎勵ri(t),?i∈;8. 將經驗 Tri(t)={oi(t),ai(t),ri(t),s(t)},?i∈放入地面控制中心經驗緩存區Bi中;9. IF n=N THEN10. 重置訓練環境;

11. END IF12. n←n mod N+1;13. END FOR14. FOR epoch,1≤epoch≤PE DO15. FOR agents i∈DO16. 根據式(31)更新Actor網絡參數θi17. 根據式(33)更新Critic網絡參數ξi;18. END FOR19. END FOR20. END FOR

4 仿真結果與分析

本節首先對實驗平臺及實驗參數進行簡單說明,然后驗證了所提算法的收斂性。在此基礎上,針對不同的網絡資源狀況與場景進行了詳細的性能實驗與評估,并與基線算法進行了對比分析。

4.1 參數設置

本實驗的仿真環境使用Python 3.7與PyTorch 1.11.0進行編寫。本實驗中設置的默認用戶數量K為30,無人機數量M為5,總帶寬B為15 MHz,任務量大小Dk[n]∈[0.5,1.5]Mb,單位比特平均計算量大小Ck[n]∈[800,1 200] cycles/b,時延約束tk[n]∈[0.7,1.0]s,權重因子設置為η=1,?1=0.001,?2=0.1?1。對于所提算法,各種智能體的策略共享Actor網絡參數,使用GAE計算優勢函數;考慮到獎勵值有界,不使用值歸一化方法。其余實驗參數與算法參數結合文獻[12,20]進行設置,如表1所示。

表1 相關參數設置Tab.1 Parameter setting

為評價E-ABMAPPO方法中各智能體獎勵的收斂性,2種基準MARL算法描述如下:

① MAPPO:該方法為不使用Beta分布-注意力機制改進方法的原始MAPPO算法,其獎勵函數、動作和狀態空間與所提算法相同[21]。

② MADDPG(Multi-Agent Deep Deterministic Policy Gradient):該方法與MAPPO都是目前較為主流和可靠的MARL算法[7]。它由雙Actor網絡與雙Critic網絡構成,其中Actor網絡的輸出即為動作值,之后加以一定探索噪聲,Critic用于擬合動作值函數。

4.2 數值分析

本文對比了MU智能體和UAV資源分配智能體如圖3和圖4所示。從圖3可以看出,對于MU智能體,所提E-ABMAPPO方法于4×104步左右收斂,收斂速度最快;MAPPO方法于8×104步左右收斂,而MADDPG方法收斂最慢,過程較為曲折,且所提算法獲得的獎勵最高,MAPPO次之,MADDPG最低。由此可以推斷出,注意力機制能使MU在評價狀態時關注更利于自身卸載的UAV,加速了算法的收斂性。此外,MADDPG探索策略的不足導致其收斂較慢或局部最優收斂。從圖4可以觀察到,所提算法在初期探索階段前25×103步的獎勵上升速度略快,在5×104步出現收斂,最后得到的獎勵在-0.30左右。此外,可以看出在UAV資源分配智能體的訓練上,所提方法與MAPPO方法訓練速度仍然高于MADDPG。由此可見,基于MAPPO的方法探索環境的效率更高,且Beta分布能依據自身特性進一步提升探索—學習這一過程的速度與性能。

圖3 MU智能體獎勵值收斂性Fig.3 Convergence of MU agent reward

圖4 UAV資源分配智能體獎勵值收斂性Fig.4 Convergence of UAV resource allocation agent reward

圖5展示了UAV的飛行軌跡情況。可以觀察到,當UAV起點隨機分布在區域內時,UAV能夠保持在用戶密集區提供服務,通過快速移動以盡可能顧及到更多的用戶,當所服務用戶在某一區域內時,通過盤旋以保持速率。為此,采用加速度作為決策變量能使軌跡平滑,更能應用于實際場景,UAV軌跡優化智能體學習到了一定的相互協作能力,通過部署到各個區域在空間上分配計算資源,提高MU的服務質量。

圖5 UAV飛行軌跡情況Fig.5 Trajectories of UAVs

圖6對比了4種算法在不同任務量大小下的性能。任務量大小從1 Mb 增大至2 Mb 時,所提方法的MU平均加權能耗最低,在0.13～0.24 J,隨機算法最高,在0.27～0.53 J。相比于MAPPO和MADDPG,所提算法用戶平均加權能耗分別降低了 22.5%～31.6%和33.5%～45.8%,相對于隨機算法降低了43.7%以上。由此可見,MAPPO搜索到的策略優于MADDPG。這驗證了Beta分布與注意力機制的使用能夠提升MAPPO算法搜索到的策略質量,從而進一步提升MU的服務質量。

圖6 不同任務量下算法性能對比Fig.6 Performance comparison under different tasks

5 結束語

本文提出了一種CTDE的無人機輔助MEC任務卸載方法,以降低移動用戶與無人機的總能耗,提高邊緣計算網絡的可靠性。特別地,利用MARL方法解決了集中式執行的DRI算法不適于應對分布式、具有連續變量和離散變量的混合動作空間的難點,提出了針對不同智能體的特性進行獎勵值設計,并將Beta分布與注意力機制引入MAPPO方法以提升探索能力與收斂性能。進行了仿真實驗,將E-ABMAPPO與其他基準方法進行了對比,并分析了所提方法的性能。實驗結果表明,E-ABMAPPO方法能夠有效降低移動用戶與無人機的加權能耗,驗證了本文方法的有效性。未來工作將考慮多無人機協作與地面基站相結合的多層次邊緣計算網絡,設計無人機的飛行軌跡和協同計算卸載策略,以取得更好的系統性能。