云邊協(xié)同下基于多智能體強化學(xué)習(xí)的任務(wù)卸載策略

劉雨暉, 陳寧江,2,3*, 何子琦

(1.廣西大學(xué) 計算機與電子信息學(xué)院, 廣西 南寧 530004；2.廣西智能數(shù)字服務(wù)工程技術(shù)研究中心, 廣西 南寧 530004；3.廣西高校并行分布與智能計算重點實驗室, 廣西 南寧 530004)

0 引言

基于Cybertwin的云邊協(xié)同網(wǎng)絡(luò)概念的提出，旨在將物理對象映射到虛擬網(wǎng)絡(luò)空間進(jìn)行實時配置從而優(yōu)化業(yè)務(wù)流程，為設(shè)計支持海量傳感器數(shù)據(jù)采集與處理的萬物互聯(lián)架構(gòu)以及構(gòu)建整個物聯(lián)網(wǎng)信息系統(tǒng)的“數(shù)字孿生”提供相應(yīng)的技術(shù)支撐[1]。由于智能移動設(shè)備自身算力資源有限，因此需要通過Cybertwin服務(wù)代理將復(fù)雜終端任務(wù)卸載到資源豐富的核心云、邊緣云或者空閑設(shè)備上執(zhí)行，在滿足用戶對網(wǎng)絡(luò)服務(wù)質(zhì)量(quality of service，QoS)的高要求的同時提高資源利用率。

現(xiàn)有基于近似優(yōu)化算法的任務(wù)卸載方法通常是根據(jù)優(yōu)化問題建立對應(yīng)的數(shù)學(xué)規(guī)劃模型，運用如貪心算法[2]、拉格朗日松弛[3]、李雅普諾夫(Lyapunov)優(yōu)化[4]和博弈論(game theory)[5]等算法在可接受的時間內(nèi)求得一個近似最優(yōu)解，但對于求解動態(tài)變化的大規(guī)模計算系統(tǒng)問題卻難以抉擇。由于其解空間的復(fù)雜性，因此通常采用單智能體深度強化學(xué)習(xí)算法求解最佳策略，同時也引出以下問題：第一，單智能體算法解決的是環(huán)境中存在單一智能體的情況(或者多個智能體可以轉(zhuǎn)化為一個智能體的決策)，缺少考慮多智能體的聯(lián)合行為對環(huán)境穩(wěn)定性影響而導(dǎo)致效果不佳[6]；第二，大規(guī)模智能移動設(shè)備的接入導(dǎo)致每個智能體的策略隨著訓(xùn)練的進(jìn)行都應(yīng)發(fā)生變化，只考慮單智能體自身狀態(tài)變化而沒有精確完整的環(huán)境信息會導(dǎo)致經(jīng)驗重放(experience replay)機制失效[7]。

因此，本文中將針對云邊協(xié)同環(huán)境下資源綜合利用困難以及單智能體強化學(xué)習(xí)算法不能滿足大規(guī)模終端協(xié)作任務(wù)卸載等問題，設(shè)計基于Cybertwin的云邊協(xié)同計算系統(tǒng)模型(Cybertwin-based cloud-edge collaborative computing system model，CCECM)，并構(gòu)建基于多智能體雙延遲深度確定性策略梯度算法(multi-agent twin delayed deep deterministic policy gradient algorithm，MATD3)的協(xié)作任務(wù)卸載與資源分配聯(lián)合優(yōu)化方法，從而緩解了海量終端協(xié)同卸載場景下單智能體強化學(xué)習(xí)算法效果不佳的問題，進(jìn)而提高任務(wù)處理效率與用戶體驗質(zhì)量。

1 系統(tǒng)模型

本節(jié)將進(jìn)一步從協(xié)同卸載模式、業(yè)務(wù)傳輸模型和綜合時延與能耗的卸載成本模型等角度構(gòu)建基于Cybertwin的云邊協(xié)同計算系統(tǒng)模型(CCECM)，從云邊端多角度刻畫任務(wù)卸載模型，更準(zhǔn)確地表征任務(wù)卸載所需總成本。基于Cybertwin的云邊協(xié)同計算系統(tǒng)架構(gòu)如圖1所示，分成以下3層：由工業(yè)物聯(lián)網(wǎng)制造設(shè)備、無人機和自動駕駛運輸車等智能設(shè)備接入的智能移動設(shè)備層(smart mobile device, SMD)，配置Cybertwin服務(wù)代理的邊緣云層(edge cloud, EC)以及具有高性能數(shù)據(jù)中心的核心云層(core cloud,CC)。

圖1 基于Cybertwin的云邊協(xié)同計算系統(tǒng)架構(gòu)Fig.1 Cybertwin-based cloud-edge collaborative computing system architecture

核心云層由多個大型云數(shù)據(jù)中心組成，依托大容量、高速、低時延的專用數(shù)據(jù)傳輸網(wǎng)絡(luò)為任務(wù)執(zhí)行提供充足的算力資源，因此，一般認(rèn)為核心云的服務(wù)能力能夠滿足所有用戶設(shè)備的服務(wù)需求，可以將部分任務(wù)卸載到核心云的數(shù)據(jù)中心上，以緩解邊緣云的流量壓力。

1.1 協(xié)同卸載模式

(1)

(2)

(3)

(4)

(5)

(6)

(7)

④ 智能移動設(shè)備卸載任務(wù)到核心云的云數(shù)據(jù)中心：由于核心云的云數(shù)據(jù)中心擁有海量算力與存儲資源，因此當(dāng)設(shè)備卸載任務(wù)到核心云時通常忽略在核心云上的執(zhí)行時間和計算能耗[12]，總時延可以表示為

(8)

(9)

(10)

(11)

(12)

1.2 業(yè)務(wù)傳輸模型

(13)

(14)

(15)

(16)

(17)

1.3 綜合時延與能耗的卸載成本模型

① 任務(wù)卸載的總時延取決于任務(wù)Γi(t)完成所選擇的協(xié)同卸載模式所需要的時間，表示為

(18)

② 任務(wù)卸載的總能耗定義為任務(wù)Γi(t)完成所選擇的協(xié)同卸載模式而產(chǎn)生的能量消耗，表示為

(19)

Fi(t)=αiTi(t)+βiEi(t)，

(20)

式中αi、βi分別為任務(wù)卸載總時延和總能耗的權(quán)重系數(shù)，通過求解上述權(quán)重系數(shù)來滿足延遲敏感型和延遲容忍型任務(wù)的服務(wù)質(zhì)量要求，其滿足的約束條件如下：

αi+βi=1, 0≤αi≤1,0≤βi≤1。

(21)

2 基于多智能體強化學(xué)習(xí)的任務(wù)卸載與資源分配聯(lián)合優(yōu)化方法

本節(jié)首先綜合多維資源約束條件制定任務(wù)卸載與資源分配的聯(lián)合優(yōu)化問題，然后將該問題轉(zhuǎn)化為成多智能體合作的馬爾可夫博弈過程(Markov game process，MGP)，最后提出基于多智能體雙延遲深度確定性策略梯度(MATD3)的深度強化學(xué)習(xí)算法求解。

2.1 優(yōu)化問題描述

(22)

通過聯(lián)合優(yōu)化智能設(shè)備協(xié)同任務(wù)卸載模式X(t)、頻譜資源φl(t)與算力資源Rcp(t)等異構(gòu)資源分配，實現(xiàn)最小化系統(tǒng)總成本，并盡量提高任務(wù)執(zhí)行的完成率，則該組合優(yōu)化問題的形式化定義如下：

(23)

C1表示在時隙t可供智能移動設(shè)備選擇的協(xié)同卸載模式?jīng)Q策變量；C2描述了云邊協(xié)同網(wǎng)絡(luò)中切片頻譜資源分配的指示變量；C3指出智能移動設(shè)備只能選擇一種卸載方式來完成計算任務(wù)；C4、C5表示邊緣云上頻譜資源與異構(gòu)算力資源的分配不能超過其資源總量；C6描述了終端設(shè)備分配自身算力資源的限制；C7表示計算任務(wù)執(zhí)行完成總時間必須滿足其對時延的最低QoS需求，確保不超過最大容忍時延；C8規(guī)定在終端設(shè)備本地執(zhí)行任務(wù)產(chǎn)生的總能耗不能超過該設(shè)備的可用剩余電量，為任務(wù)順利執(zhí)行提供保證。

2.2 算法描述及其實現(xiàn)

鑒于任務(wù)卸載與資源分配聯(lián)合優(yōu)化問題P1是復(fù)雜而連續(xù)的動作空間問題，本文設(shè)計了一個基于多智能體雙延遲深度確定性策略梯度算法來求解該問題。

2.2.1 多智能體合作的馬爾可夫博弈過程

本文將式(23)中表述的NP難問題建模為多智能體場景[14]中的馬爾可夫博弈過程，形式化描述為Ω={N,S,A,P,R,η}。N={1,2,…,|N|}表示智能移動設(shè)備集合，代表設(shè)備的Cybertwin是作為訓(xùn)練學(xué)習(xí)的智能體；狀態(tài)空間是全部Cybertwin智能體聯(lián)合環(huán)境的狀態(tài)集S={s1,s2,…,sK}；動作空間A=A1×A2×…×AN為多智能體聯(lián)合動作集合；狀態(tài)轉(zhuǎn)移概率函數(shù)P(s(t+1)|s(t),a1(t),a2(t),…,aN(t))→[0,1],?s(t)∈S,ai(t)∈Ai,i∈N；聯(lián)合獎勵函數(shù)值集合R={R1,R2,…,RN}反饋了任務(wù)卸載與資源分配聯(lián)合優(yōu)化決策的合理性與有效性，其中單個智能體的獎勵函數(shù)表示為ri=Ai×S→R；η是關(guān)于時間的折扣因子。

(24)

s(t)={O1(t),O2(t),…,ON(t)},?s(t)∈S,t∈[0,+∞)。

(25)

② 動作空間：在時隙t觀察當(dāng)前環(huán)境狀態(tài)s(t)∈S后，Cybertwin智能體i根據(jù)已有策略為當(dāng)前任務(wù)選擇一個合適的行為動作，完成協(xié)同卸載模式，則每個Cybertwin智能體i的獨立動作空間為

(26)

③ 獎勵函數(shù)：在多智能體合作與競爭環(huán)境中，每個Agent可以通過分布式執(zhí)行的方式做出相應(yīng)決策，以最大化聯(lián)合環(huán)境中的獎勵回報，設(shè)計準(zhǔn)確有效的獎勵函數(shù)有利于多智能體快速學(xué)習(xí)最優(yōu)策略[15]。根據(jù)時隙t觀察到環(huán)境狀態(tài)來為計算任務(wù)選擇卸載動作，則單個Cybertwin智能體i的獎勵函數(shù)定義為

ri(t)=-(αiTi(t)+βiEi(t))+ε(t),?ri(t)∈Ri,t∈[0,+∞)，

(27)

式中：ri(t)表示在智能體i在時隙t執(zhí)行卸載動作后立即獲得的獎勵；ε(t)表示時隙t邊緣云中每個Cybertwin智能體的任務(wù)執(zhí)行失效懲罰。系統(tǒng)獎勵是由所有智能體收到的獎勵總和，表述如下：

(28)

2.2.2 基于MATD3的深度強化學(xué)習(xí)算法的實現(xiàn)

(29)

式中：Z表示從經(jīng)驗重放緩沖區(qū)D中取出的樣本數(shù)據(jù)集合；|Z|是樣本數(shù)量；z是樣本數(shù)據(jù)的索引；yi是目標(biāo)函數(shù)值；λ為折扣因子；μ是添加的動作噪聲。Cybertwin智能體i的確定性策略πθi梯度的更新過程表示為

(30)

本文提出的MATD3算法主要分成2個重要步驟：收集環(huán)境狀態(tài)數(shù)據(jù)和目標(biāo)策略網(wǎng)絡(luò)訓(xùn)練，詳細(xì)的算法步驟如下：

Step1：初始化每個Cybertwin智能體中Actor網(wǎng)絡(luò)的策略參數(shù)θ、Critic網(wǎng)絡(luò)的評價參數(shù)φ1,φ2以及清空經(jīng)驗重放緩沖區(qū)D，定義最大訓(xùn)練回合數(shù)Kmax和每個訓(xùn)練回合內(nèi)的最大時間步長Tmax；

Step2：初始化剪切后的高斯噪聲μ用于隨機動作策略探索a(t)=πθ(O(t))+μ，系統(tǒng)內(nèi)全部Cybertwin智能體將自身的部分觀測值共同組合成云邊端協(xié)同環(huán)境的初始狀態(tài)s0；

Step3：每個Cybertwin智能體根據(jù)時隙t的確定性策略π選擇1.1節(jié)中的任務(wù)協(xié)同卸載模式并獲得相應(yīng)回報，并把當(dāng)前系統(tǒng)狀態(tài)轉(zhuǎn)移信息元組(s,a1,a2,…,aN,r1,r2,…,rN,s′)作為下一輪訓(xùn)練樣本數(shù)據(jù)存儲到經(jīng)驗重放緩沖區(qū)D中，此后系統(tǒng)環(huán)境轉(zhuǎn)移到新狀態(tài)s′；

Step4：接著每個Cybertwin智能體單獨對經(jīng)驗重放緩沖區(qū)D的數(shù)據(jù)進(jìn)行批量采樣，在樣本數(shù)據(jù)上利用損失函數(shù)(29)更新Critic網(wǎng)絡(luò)的參數(shù)φ1,φ2并延遲d個時間步后采用梯度下降法求解，即采用式(30)更新Actor網(wǎng)絡(luò)的策略參數(shù)θ，最后再對目標(biāo)網(wǎng)絡(luò)的相應(yīng)參數(shù)進(jìn)行軟更新；

Step5：判斷此時算法是否已經(jīng)達(dá)到當(dāng)前訓(xùn)練回合內(nèi)的最大時間步長Tmax，若已經(jīng)達(dá)到則跳轉(zhuǎn)到Step 6執(zhí)行，否則重新返回Step 3執(zhí)行；

Step6：判斷此時算法是否已經(jīng)達(dá)到最大訓(xùn)練回合數(shù)Kmax，若是則結(jié)束算法并輸出最優(yōu)卸載策略，否則重新返回Step 2繼續(xù)執(zhí)行。

算法中Actor和Critic網(wǎng)絡(luò)分別設(shè)計成擁有2層和3層隱藏層的全連接神經(jīng)網(wǎng)絡(luò)。根據(jù)文獻(xiàn)[16]可知，對于隱藏層是由固定數(shù)目神經(jīng)元構(gòu)成的全連接網(wǎng)絡(luò)，其反向傳播算法的計算復(fù)雜度與輸入維度和輸出維度的乘積成正比。假設(shè)本文設(shè)計的場景下邊緣云數(shù)量為M，每個邊緣云服務(wù)范圍內(nèi)智能移動設(shè)備總數(shù)為Nm。Cybertwin智能體的Critic網(wǎng)絡(luò)集中化訓(xùn)練的復(fù)雜度為O[M(Nm+M+Nm)]。而對于Actor網(wǎng)絡(luò)，其分散式執(zhí)行過程的計算復(fù)雜度為O[Nm(M+Nm)]。因此，本文所提出的MATD3算法的復(fù)雜度為O[Nm(M+Nm)]。

2.3 實驗性能評估

實驗的硬件環(huán)境：CPU為Intel Core i7-10700 KF、8核心、主頻為3.8 GHz，內(nèi)存為64 GB，顯卡為RTX2070。操作系統(tǒng)為Windows 11，運行環(huán)境為Python 3.9與Pytorch 1.10。模擬云邊協(xié)同系統(tǒng)環(huán)境所使用的主要參數(shù)見表1。

表1 系統(tǒng)仿真參數(shù)設(shè)置Tab 1 System simulation parameter setting

為了更直觀地評估所提出的MATD3優(yōu)化方案的性能，本文將其與以下5種基準(zhǔn)算法進(jìn)行比較：單智能體雙延遲深度確定性策略梯度算法(TD3)[17]、單智能體深度確定性策略梯度算法(DDPG)[18]、貪心算法(Greedy)、隨機卸載策略(randomly offloading algorithm，ROA)、本地計算(local processing，LP)。

MATD3、TD3、DDPG強化學(xué)習(xí)算法的平均獎勵曲線如圖2所示。從圖中可見，這3種算法的平均獎勵曲線隨著訓(xùn)練回合的增加而逐漸收斂。在0～500個訓(xùn)練回合中，Cybertwin智能體的平均獎勵較小并且隨著訓(xùn)練回合的遞增出現(xiàn)一定幅度的波動。這是因為在訓(xùn)練初期智能體只進(jìn)行隨機動作探索，經(jīng)驗重放緩沖區(qū)中樣本數(shù)據(jù)較少，導(dǎo)致剛開始訓(xùn)練好的模型偏向過擬合狀態(tài)，經(jīng)過2 000個訓(xùn)練回合充分訓(xùn)練后3種強化學(xué)習(xí)算法均達(dá)到收斂狀態(tài)。與其他2種單智能體基準(zhǔn)算法相比，本文提出的MATD3算法收斂速度最快，經(jīng)過1 500個訓(xùn)練回合后就已經(jīng)收斂了，而且獎勵波動范圍較小，平均獎勵值最高。

圖2 MATD3、TD3、DDPG的平均獎勵曲線Fig.2 Average reward curve for MATD3, TD3, and DDPG

圖3(a)的結(jié)果顯示系統(tǒng)平均成本隨著智能移動設(shè)備數(shù)量的增加而逐漸增大的變化趨勢，但當(dāng)設(shè)備數(shù)越多時增長速度減慢。這是因為接入設(shè)備數(shù)的增加意味著邊緣云內(nèi)有限多維異構(gòu)資源不能滿足所有用戶設(shè)備需求，部分設(shè)備只能選擇在本地執(zhí)行或者傳輸?shù)胶诵脑埔詧?zhí)行更多的延遲敏感任務(wù)導(dǎo)致平均成本的增加，甚至部分任務(wù)因算力資源不足在時間到期后被丟棄。從圖3(a)可以看出，隨著設(shè)備數(shù)增加，本文提出的MATD3算法在降低平均成本方面優(yōu)于其他5種算法。當(dāng)智能移動設(shè)備數(shù)目為40時，MATD3與TD3、DDPG、Greedy、ROA和LP等算法對比分別降低了24.69%、25.61%、35.79%、43.51%和51.58%的平均成本。

由圖3(b)可知隨著任務(wù)數(shù)據(jù)大小的增加，平均成本起始增速較快，隨后趨于平穩(wěn)。因為通信傳輸時延與任務(wù)數(shù)據(jù)大小成正相關(guān)關(guān)系，任務(wù)數(shù)據(jù)增大代表傳輸時延成本的增加，進(jìn)而增加了系統(tǒng)平均成本。當(dāng)任務(wù)數(shù)據(jù)大小為20 Mbits時，MATD3算法與TD3、DDPG、Greedy、ROA和LP等算法相比分別減少了29.31%、32.78%、43.84%、54.44%和60.34%的平均成本。總的來說，在上述6種算法中，MATD3算法能夠綜合考慮將任務(wù)卸載到不同計算節(jié)點上的可行性，對最小化系統(tǒng)總成本和提高QoS實施策略優(yōu)化，最終得到最低的平均成本。

(a) 智能移動設(shè)備數(shù)對平均成本的影響

(b) 任務(wù)數(shù)據(jù)大小對平均成本的影響

接著，本文對這幾種算法的任務(wù)卸載率進(jìn)行比較，而本地計算(LP)算法只在設(shè)備本地執(zhí)行任務(wù)，即該算法的任務(wù)卸載率為0，所以不在實驗部分進(jìn)行討論。在圖4(a)中，任務(wù)卸載率隨著智能移動設(shè)備數(shù)的增加而降低。這是因為接入設(shè)備數(shù)的增加將生成更多的異質(zhì)計算任務(wù)，越來越多沒有被分配到計算節(jié)點執(zhí)行的任務(wù)只能選擇在本地完成。當(dāng)接入設(shè)備數(shù)為40時，MATD3與TD3、DDPG、Greedy和ROA等算法相比分別提高了34.34%、39.13%、77.76%和95.12%的任務(wù)卸載率。

圖4(b)對任務(wù)丟棄率與任務(wù)數(shù)據(jù)大小的關(guān)系進(jìn)行分析。任務(wù)丟棄率反映了智能移動設(shè)備與計算節(jié)點之間通信服務(wù)質(zhì)量以及算力資源的可用性等問題。由圖4(b)可知，任務(wù)丟棄率是隨著任務(wù)數(shù)據(jù)大小的增加而增加。在對比的6種算法中，MATD3算法的任務(wù)丟棄率最低，原因是所提出的MATD3優(yōu)化方案能夠根據(jù)任務(wù)的服務(wù)質(zhì)量需求有效地綜合利用終端設(shè)備、邊緣云和核心云的空閑資源，從而保證整個網(wǎng)絡(luò)可以處理盡可能多的業(yè)務(wù)。

(a) 智能移動設(shè)備數(shù)對任務(wù)卸載率的影響

(b) 任務(wù)數(shù)據(jù)大小對任務(wù)丟棄率的影響

3 總結(jié)與展望

本文中設(shè)計了一個基于Cybertwin驅(qū)動的云邊協(xié)同計算框架，能夠高效完成任務(wù)卸載與多維異構(gòu)資源聯(lián)合分配優(yōu)化配置。通過實驗對比分析，在云邊協(xié)同網(wǎng)絡(luò)中使用本文提出的MATD3算法，能夠最小化任務(wù)卸載總成本，提高了任務(wù)執(zhí)行性能并減少任務(wù)丟棄率，有效保證了終端設(shè)備的用戶體驗質(zhì)量。未來，我們將把區(qū)塊鏈、聯(lián)邦計算與Cybertwin智能服務(wù)相結(jié)合，為分布式跨云環(huán)境中的資源管理和用戶設(shè)備隱私保護提供更加完善的解決方案。