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

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

0 引言

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

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

因此，本文中將針對(duì)云邊協(xié)同環(huán)境下資源綜合利用困難以及單智能體強(qiáng)化學(xué)習(xí)算法不能滿足大規(guī)模終端協(xié)作任務(wù)卸載等問題，設(shè)計(jì)基于Cybertwin的云邊協(xié)同計(jì)算系統(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é)同卸載場(chǎng)景下單智能體強(qiáng)化學(xué)習(xí)算法效果不佳的問題，進(jìn)而提高任務(wù)處理效率與用戶體驗(yàn)質(zhì)量。

1 系統(tǒng)模型

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

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

核心云層由多個(gè)大型云數(shù)據(jù)中心組成，依托大容量、高速、低時(shí)延的專用數(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)

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

(8)

(9)

(10)

(11)

(12)

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

(13)

(14)

(15)

(16)

(17)

1.3 綜合時(shí)延與能耗的卸載成本模型

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

(18)

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

(19)

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

(20)

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

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

(21)

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

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

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

(22)

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

(23)

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

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

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

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

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

(24)

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

(25)

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

(26)

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

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

(27)

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

(28)

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

(29)

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

(30)

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

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

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

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

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

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

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

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

2.3 實(shí)驗(yàn)性能評(píng)估

實(shí)驗(yàn)的硬件環(huán)境：CPU為Intel Core i7-10700 KF、8核心、主頻為3.8 GHz，內(nèi)存為64 GB，顯卡為RTX2070。操作系統(tǒng)為Windows 11，運(yùn)行環(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

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

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

圖2 MATD3、TD3、DDPG的平均獎(jiǎng)勵(lì)曲線Fig.2 Average reward curve for MATD3, TD3, and DDPG

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

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

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

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

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

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

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

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

3 總結(jié)與展望

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