鮮永菊,韓瑞寅,左維昊,汪帥鴿

(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)

0 引 言

隨著移動通信技術(shù)和物聯(lián)網(wǎng)產(chǎn)業(yè)的不斷發(fā)展,以虛擬現(xiàn)實(Virtual Reality,VR)、增強現(xiàn)實(Augmented Reality,AR)、自動駕駛、遠(yuǎn)程醫(yī)療為代表的一系列新型業(yè)務(wù)產(chǎn)生,給人們的生活帶來了全新的體驗。這類業(yè)務(wù)往往具有較大的計算需求和較高的時延敏感度,給能量、計算資源有限的移動終端設(shè)備帶來了極大挑戰(zhàn)。移動邊緣計算(Mobile Edge Computing,MEC)將原本云計算的計算資源和存儲資源下沉到更靠近用戶一側(cè)的邊緣設(shè)備上,能夠為用戶提供低時延高可靠性的服務(wù),提升用戶服務(wù)質(zhì)量(Quality of Service,QoS)。

用戶的移動性作為MEC環(huán)境中一項不可忽略的因素,極大限制了用戶服務(wù)質(zhì)量的提升。用戶移動過程中,信道狀態(tài)會不斷變化,可能會影響原有卸載方案性能。通過跟隨用戶移動進行任務(wù)遷移的方式,可以在一定程度上保證用戶QoS和服務(wù)連續(xù)性[1]。但在這一過程中,大量用戶的涌入或者離開引發(fā)的任務(wù)遷移,會使得服務(wù)器負(fù)載突然增加或者減少,導(dǎo)致整個系統(tǒng)中負(fù)載分布不均,增加用戶任務(wù)在部分服務(wù)器上的排隊時延,導(dǎo)致系統(tǒng)資源利用不均,降低系統(tǒng)吞吐量[2]。因此,如何在保證用戶服務(wù)連續(xù)不中斷的前提下,進行卸載和遷移決策,保證系統(tǒng)負(fù)載均衡,是MEC任務(wù)遷移中一項亟待解決的問題。

針對邊緣計算中用戶移動性導(dǎo)致的QoS下降的問題,部分文獻采用凸優(yōu)化或者啟發(fā)式算法進行求解。文獻[3-4]提出的方案均未考慮移動性可能帶來的負(fù)載分布不均的問題,文獻[5-6]提出的方案只進行了單時隙優(yōu)化,沒有考慮到系統(tǒng)長期性能優(yōu)化。

近年來,隨著強化學(xué)習(xí)的興起,也有大量文獻采用強化學(xué)習(xí)方法進行研究[7-9],但這些研究都是基于單智能體強化學(xué)習(xí)算法進行求解,只適用于控制器集中控制或者單個用戶決策的場景。還有文獻是基于多智能體強化學(xué)習(xí)(Multi-agent Reinforcement Learning,MARL)進行研究的。文獻[10]建立了多用戶場景下的任務(wù)遷移模型,采用基于反事實多智能體(Counterfactual Multi-agent,COMA)的分布式任務(wù)遷移算法求解原問題,但是作者假設(shè)所有任務(wù)均已卸載,忽略了卸載決策和資源分配的影響。文獻[11]采用多智能體深度Q網(wǎng)絡(luò)(Deep Q Network,DQN),使用雙分支卷積神經(jīng)網(wǎng)絡(luò)生成任務(wù)遷移和移動決策。

綜上所述,目前已有大量研究工作圍繞移動性場景下用戶任務(wù)遷移展開,但是少有研究關(guān)注用戶移動性帶來負(fù)載分布不均的問題。此外,在多用戶多基站的分布式場景下,采用集中式控制需要不斷收集用戶位置變化信息,這會產(chǎn)生較大的信令收集成本。因此,本文提出了一種基于多智能體柔性演員-評論家(Soft Actor-Critic,SAC)的分布式任務(wù)遷移方案(Distributed Soft Actor-Critic Migration,DSACM)來解決上述問題,具體的研究工作可以概括如下:

一是建立了多用戶多節(jié)點MEC場景下用戶隨機移動的任務(wù)遷移模型,將其建模為一個長期極大極小化公平性問題,旨在考慮系統(tǒng)遷移成本約束、用戶設(shè)備能耗約束和系統(tǒng)負(fù)載均衡的同時,優(yōu)化性能最差的用戶的服務(wù)質(zhì)量。

二是通過引入輔助變量結(jié)合李雅普諾夫(Lyapunov)優(yōu)化的方式將原問題轉(zhuǎn)化并解耦,將其建模為去中心化部分可觀測馬爾可夫決策過程(Decentralized Partially Observable Markov Decision Process,Dec-POMDP),將獎勵函數(shù)分解為節(jié)點全局獎勵和用戶個體獎勵,分別基于網(wǎng)絡(luò)負(fù)載和用戶QoS對用戶動作施加獎勵。

三審針對集中式控制需要大量收集用戶信息的問題,提出一種基于擴展多智能體SAC的分布式任務(wù)遷移方案。利用集中式訓(xùn)練分布式執(zhí)行(Central Training Distributed Execute,CTDE)框架,將單智能體強化學(xué)習(xí)算法SAC擴展到多智能體領(lǐng)域。相比于一般的強化學(xué)習(xí)算法,SAC算法通過最大化熵正則項可以獲得更高的探索能力和更強的魯棒性。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

在圖1所示的系統(tǒng)模型中,每個小基站上部署一個服務(wù)器,不同小基站上的服務(wù)器計算能力異構(gòu),一共有M個服務(wù)器,M={1,2,…,m,…,M}表示服務(wù)器的集合。系統(tǒng)中共有U個用戶,用戶集合用U={1,2,…,u,…,U}表示,用戶設(shè)備可以是車輛、普通移動用戶等。假設(shè)每個用戶在關(guān)聯(lián)節(jié)點上都有一個虛擬機提供服務(wù),它可以跟隨用戶移動被遷移到新的服務(wù)器上繼續(xù)執(zhí)行。

圖1 系統(tǒng)模型Fig.1 System model

1.2 通信模型

(1)

(2)

(3)

(4)

1.3 計算模型

1.3.1 本地計算

當(dāng)任務(wù)本地執(zhí)行時,即使用戶位置發(fā)生改變,任務(wù)仍然在本地設(shè)備上繼續(xù)執(zhí)行,用戶設(shè)備能耗只包括本地計算能耗,本地計算時延可以表示為

(5)

(6)

式中:κ是與芯片架構(gòu)相關(guān)的有效能量成本系數(shù)。

1.3.2 邊緣計算

(7)

整個邊緣執(zhí)行階段包括用戶將任務(wù)發(fā)送到服務(wù)器,服務(wù)器完成任務(wù)計算,計算結(jié)果發(fā)送給用戶三部分。其中,由于任務(wù)輸出結(jié)果往往較小,且下行鏈路傳輸速率較快,因此這一部分時延可以忽略。任務(wù)在邊緣執(zhí)行的總時延可以表示為

(8)

1.4 任務(wù)遷移及用戶QoS模型

(9)

任務(wù)遷移通過服務(wù)器間的有線連接完成,為了簡化計算,基于靜態(tài)路由跳數(shù)計算有線傳輸時延。使用Q表示單跳時延,σi,j表示服務(wù)器i與服務(wù)器j之間的路由跳數(shù),任務(wù)的遷移時延可以具體表示為

(10)

(11)

式中:C是固定的遷移成本;b是控制因子,用于控制遷移成本隨待遷移用戶數(shù)變化的快慢。

(12)

t時隙內(nèi),所有用戶產(chǎn)生的總遷移成本可以表示為

(13)

(14)

用戶QoS與任務(wù)完成時延相關(guān),用戶QoS模型可以利用對數(shù)函數(shù)規(guī)律進行刻畫[8]。用戶QoS增益可以表示為

(15)

1.5 負(fù)載均衡模型

為了衡量用戶移動過程中網(wǎng)絡(luò)負(fù)載變化情況,受文獻[12]的啟發(fā),服務(wù)器的負(fù)載狀態(tài)可以用服務(wù)器的剩余CPU和存儲資源來刻畫。定義t時隙服務(wù)器m的負(fù)載為

(16)

2 問題建模

通過聯(lián)合優(yōu)化用戶卸載策略、遷移決策和計算資源分配,優(yōu)化性能最差的用戶平均QoS,長期優(yōu)化問題建模為

(17)

2.1 引入輔助變量

由于建模的是一個長期極大極小化公平性問題,難以直接求解。根據(jù)文獻[13]和文獻[14]中的方法,可以每個時隙引入輔助變量φt,將其轉(zhuǎn)化為一個最大化問題。P1可以被等價轉(zhuǎn)化為P2,具體表示如下:

(18)

2.2 李雅普諾夫優(yōu)化

(19)

針對約束條件C5,定義虛擬遷移成本隊列G(t),表示t時隙內(nèi)系統(tǒng)中所有用戶產(chǎn)生的遷移成本:

(20)

針對引入的輔助變量約束條件C7,定義虛擬隊列Y(t)={Yu(t)}u∈U,虛擬隊列的動態(tài)變化表示如下:

Yu(t+1)=max{Yu(t)+φ(t)-Qu(t),0}

(21)

為了聯(lián)合控制能耗隊列和遷移成本隊列,定義Θ(t){Z(t),Y(t),G(t)}作為總隊列積壓。定義李雅普諾夫函數(shù)L(Θ(t))如下:

(22)

定義兩個時隙間李雅普諾夫函數(shù)的變化為李雅普諾夫漂移函數(shù)ΔL(Θ(t)),為了保證隊列的穩(wěn)定,需要最小化漂移函數(shù)的值,ΔL(Θ(t))表示如下:

ΔL(Θ(t))=E{L(Θ(T+1))-L(Θ(t))|Θ(t)}

(23)

定義李雅普諾夫漂移加懲罰項為

Λ(Θ(t))ΔL(Θ(t))-VE{φt|Θ(t)|}

(24)

式中:V(V>0)是控制因子,用于控制隊列穩(wěn)定性與目標(biāo)函數(shù)優(yōu)化之間的權(quán)重。懲罰項可以表示為目標(biāo)函數(shù)的映射,加上這一項是為了在最小化李雅普諾夫漂移保證隊列穩(wěn)定性的同時最小化目標(biāo)函數(shù)的值。

可以得到李雅普諾夫漂移函數(shù)ΔL(Θ(t))表示為

(25)

為了在最大化用戶QoS的同時保證隊列積壓Θ(t)的穩(wěn)定,采用最小化李雅普諾夫漂移加懲罰項的方式,可以得到

(26)

優(yōu)化問題P2可被進一步轉(zhuǎn)化為

s.t.C1,C2,C4,C8

(27)

3 基于SAC的分布式任務(wù)遷移方案

3.1 去中心化部分可觀測馬爾可夫決策過程

強化學(xué)習(xí)可以適應(yīng)復(fù)雜的環(huán)境狀態(tài)變化,但對于大規(guī)模分布式系統(tǒng),單一智能體要學(xué)習(xí)大量分布式策略,隨著策略網(wǎng)絡(luò)數(shù)量的增加,會使得狀態(tài)空間呈指數(shù)級增長。將單個龐大的智能體分解為多個結(jié)構(gòu)簡單的智能體,可以降低狀態(tài)空間和動作空間的維度[15]。

在本文中,大量移動用戶的存在使得集中式控制器難以及時收集到所有用戶的信息,容易出現(xiàn)狀態(tài)空間“維度爆炸”的現(xiàn)象。因此,本文采用MARL方式,由每個用戶設(shè)備作為智能體進行決策。對于每一個用戶智能體U-Agent而言,難以獲得完整的網(wǎng)絡(luò)狀態(tài)和其他所有智能體的動作,用戶進行決策時只能夠觀測到部分環(huán)境狀態(tài)。借助Dec-POMDP理論,可以將這一過程建模如下:

觀測空間:對于智能體U-Agentu,狀態(tài)包括剩余可用遷移成本預(yù)算、剩余設(shè)備能量、節(jié)點剩余計算資源、當(dāng)前負(fù)載偏差值等。觀測空間定義為

(28)

動作空間:動作空間包括卸載決策、服務(wù)器關(guān)聯(lián)策略、功率分配策略,定義為

Au(t)={ρu(t),ou(t),pu(t)}

(29)

獎勵函數(shù):以往相關(guān)文獻研究中獎勵函數(shù)往往設(shè)置為共享的全局獎勵,但在多智能體場景下,難以衡量某一個智能體對全局獎勵的貢獻值,容易產(chǎn)生信用分配問題。在這種情況下,部分智能體無法得到有效訓(xùn)練。受文獻[16]的啟發(fā),本文將獎勵函數(shù)分別設(shè)置為節(jié)點全局獎勵函數(shù)和個體獎勵函數(shù)。對于邊緣節(jié)點而言,希望能夠在保證用戶QoS的同時,維持整個網(wǎng)絡(luò)的負(fù)載均衡。節(jié)點基于當(dāng)前自身負(fù)載均衡度和剩余遷移成本預(yù)算隊列建立全局獎勵函數(shù),避免只考慮用戶移動性進行任務(wù)遷移容易導(dǎo)致的負(fù)載不均衡問題。節(jié)點m處的全局獎勵函數(shù)可以表示為

(30)

式中:ω作為歸一化因子。

用戶智能體需要關(guān)注自身QoS與能耗,結(jié)合優(yōu)化問題P3的優(yōu)化目標(biāo),因此可以將個體獎勵函數(shù)表示為

(31)

3.2 DSACM算法

本文采用CTDE框架,借助以往收集數(shù)據(jù)對網(wǎng)絡(luò)進行預(yù)訓(xùn)練,之后直接將訓(xùn)練好的模型分發(fā)給參與卸載的用戶,用戶直接離線執(zhí)行任務(wù)。在線執(zhí)行階段,用戶智能體只需要依靠自身局部環(huán)境觀測就可以做出實時性決策[17]。DSACM網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。

圖2 DSACM網(wǎng)絡(luò)結(jié)構(gòu)Fig.2 DSACM network structure

由于用戶在系統(tǒng)中隨機移動以及信道時變特性,導(dǎo)致網(wǎng)絡(luò)狀態(tài)不斷發(fā)生變化。為了穩(wěn)定算法收斂過程,本文將單智能體SAC擴展到多智能體領(lǐng)域。SAC是一種離線強化學(xué)習(xí)算法,通過最大化熵正則項來做出更加隨機的決策,增加算法的探索性能,避免陷入局部最優(yōu)解。相比于一般的最大化獎勵的強化學(xué)習(xí)算法,SAC有著更高的探索能力和更強的魯棒性,能夠更好地適應(yīng)復(fù)雜的網(wǎng)絡(luò)環(huán)境[18]。

針對本文中多用戶多節(jié)點的分布式場景,所提分布式SAC算法訓(xùn)練的目標(biāo)是最大化如下所示的熵正則項:

(32)

在Actor-Critic網(wǎng)絡(luò)架構(gòu)中,長期訓(xùn)練過程時,為了最大化長期回報獎勵,需要借助Critic網(wǎng)絡(luò)和Actor網(wǎng)絡(luò)對策略進行評估和改進。用戶價值網(wǎng)絡(luò)軟Q值函數(shù)為

(33)

(34)

為了避免價值網(wǎng)絡(luò)輸出的Q值出現(xiàn)高估問題,引入雙Q網(wǎng)絡(luò),使用兩個網(wǎng)絡(luò)中Q值最小的一個作為近似估計值,即有

(35)

同理可以得到節(jié)點價值網(wǎng)絡(luò)損失函數(shù)。采用梯度下降法更新用戶智能體和節(jié)點處的價值網(wǎng)絡(luò),用戶價值網(wǎng)絡(luò)更新公式可以表示為

(36)

節(jié)點價值網(wǎng)絡(luò)更新公式為

(37)

(38)

所提出的DSACM算法具體描述如下:

1 for episodet=1 to MAX_EPISODE do

2 生成隨機數(shù)p∈[0,1]

3 for智能體u∈U do

4 ifp<εor ‖Bu‖

5 隨機產(chǎn)生動作au(t)

6 else

7 局部觀測,獲取狀態(tài)su(t),將su(t)輸入Actor網(wǎng)絡(luò)θu,產(chǎn)生動作au(t)

8 end if

9 end for

11 將(s(t),a(t),R(t),Rm(t),s′(t+1))存放到經(jīng)驗池B中

12 iftmoddloc==0

13 for 智能體u∈U do

14 從經(jīng)驗重放池B提取大小為d的樣本(s(t),a(t),R(t),Rm(t),s′(t+1))

15 根據(jù)式(36)更新本地價值網(wǎng)絡(luò)參數(shù)φ1,u和φ2,u

16 根據(jù)式(38)更新本地策略網(wǎng)絡(luò)參數(shù)θu

17 采用軟更新方式更新目標(biāo)網(wǎng)絡(luò)值

19 end for

20 end if

21 iftmoddglobal==0

22 根據(jù)式(37)更新節(jié)點全局價值網(wǎng)絡(luò)參數(shù)

23 end if

24 end for

完成訓(xùn)練之后,訓(xùn)練好的模型被直接部署到系統(tǒng)中的用戶終端,分布式進行決策。

3.3 算法復(fù)雜度分析

(39)

4 仿真結(jié)果及分析

4.1 仿真設(shè)置

仿真在PyCharm平臺上完成,仿真參數(shù)設(shè)置參考文獻[10],具體的仿真參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameter setting

本文選擇與其他兩種算法進行比較:一種是從不遷移方案(No Migration,NM),任務(wù)始終在用戶初次卸載的節(jié)點上執(zhí)行,不會隨著用戶移動進行遷移;另一種是文獻[10]所提的基于COMA的任務(wù)遷移方案。COMA是一種多智能體強化學(xué)習(xí)算法,其核心思想是使用集中式評價網(wǎng)絡(luò)進行集中訓(xùn)練,動作網(wǎng)絡(luò)分布式學(xué)習(xí)用戶動作決定任務(wù)是否遷移。

4.2 仿真結(jié)果

圖3比較了所提算法與文獻[10]所提COMA算法的平均獎勵值,實線部分為獎勵值每50個回合的滑動平均值,陰影填充部分是獎勵值變化范圍?？梢园l(fā)現(xiàn),COMA算法在1 000代左右收斂,本文所提DSACM算法在1 500代左右收斂。DSACM算法的收斂沒有COMA算法快,但是所獲得的累積獎勵值高于COMA算法。這是由于DSACM繼承了SAC算法最大化熵正則項的思想,鼓勵探索,避免陷入局部最優(yōu)。

圖3 算法收斂性分析Fig.3 Algorithm convergence analysis

圖4比較了算法在不同學(xué)習(xí)率下獎勵值的變化情況,可以看出增大Actor網(wǎng)絡(luò)的學(xué)習(xí)率可以收斂更快,但所獲得獎勵減小,收斂不穩(wěn)定。本文將策略網(wǎng)絡(luò)和價值網(wǎng)絡(luò)學(xué)習(xí)率分別設(shè)置為0.000 1和0.001。

圖4 不同學(xué)習(xí)率下算法收斂分析Fig.4 Comparison of algorithm convergence analysis with different learning rates

圖5(a)對比了在不同用戶數(shù)量情況任務(wù)平均執(zhí)行時延的變化情況。其中,NM方案的執(zhí)行時延增長速度最快,這是由于用戶任務(wù)從不遷移,大量用戶聚集在某些服務(wù)器上,增加了執(zhí)行時延。DSACM的平均執(zhí)行時延小于COMA方案和NM方案,在用戶數(shù)量增加到一定程度之后,優(yōu)勢更加明顯。這是由于所提DSACM方案增加了負(fù)載均衡約束,避免了大量任務(wù)聚集在某些節(jié)點,增加這部分任務(wù)執(zhí)行時延。

(a)平均完成時延

圖5(b)對比了不同用戶數(shù)量情況下的任務(wù)失敗率。所提DSACM算法的任務(wù)失敗率始終低于COMA方案和NM方案。用戶數(shù)量較少時,系統(tǒng)計算資源充足,此時3種方案的任務(wù)失敗率接近,但隨著用戶數(shù)量的增加,3種方案的任務(wù)失敗率之間的差距逐漸增大。

圖6(a)對比不同移動速度下的用戶平均任務(wù)失敗率,可以看出由于NM算法從不遷移,在用戶移動速度較快時,可能產(chǎn)生較大的傳輸時延從而導(dǎo)致任務(wù)失敗。DSACM的失敗率始終低于其他兩種算法,能夠在移動過程中保證用戶QoS。

(a)失敗率

圖6(b)比較了不同移動速度下3種算法的遷移率。由于NM選擇從不遷移,因此遷移率始終為0。隨著用戶移動速度加快,為了保障用戶QoS,大量任務(wù)開始頻繁遷移,由于本文所提方案增加了遷移成本控制和負(fù)載均衡約束,避免了頻繁的遷移,因此遷移率始終低于COMA方案。

圖7比較了不同移動速度下系統(tǒng)的平均負(fù)載偏差系數(shù)。根據(jù)前文的定義,偏差系數(shù)越小,系統(tǒng)負(fù)載分布越均衡?？梢钥闯?不同移動速度對所提方案與COMA方案的負(fù)載分布影響較小,且DSACM算法的平均偏差系數(shù)最小,節(jié)點間的負(fù)載分布更為均衡。

圖7 不同移動速度下平均負(fù)載偏差系數(shù)對比Fig.7 Comparison of average load deviation factors for different movement speeds

5 結(jié) 論

本文針對MEC中用戶移動性導(dǎo)致負(fù)載分布不均以及用戶QoS下降的問題,提出了一種分布式任務(wù)遷移方案,建模了旨在保證用戶整體服務(wù)質(zhì)量的優(yōu)化問題。利用李雅普諾夫優(yōu)化將問題解耦,并提出一種基于多智能體SAC的分布式遷移算法,采用CTDE框架保證用戶可以做出實時性決策。仿真結(jié)果表明,相較于現(xiàn)有算法,所提算法能有效降低任務(wù)執(zhí)行時延、任務(wù)失敗率和遷移率,并能夠保證節(jié)點間負(fù)載分布均衡。