改進深度強化學習算法的計算卸載策略

葛海波，弓海文，宋 興，李 順，孫 奧

(西安郵電大學 電子工程學院，陜西 西安 710121)

隨著智能手機、平板電腦等移動設備的數(shù)量急劇增加，諸如圖像識別、增強現(xiàn)實、虛擬現(xiàn)實等任務密集型、時延敏感型的應用程序大量增長[1]。這些移動應用常常需要大量的計算資源，而受限于計算能力與電池容量的移動設備越來越無法支持這些應用[2]。為了克服這一問題，移動云計算(Mobile Cloud Computing,MCC)作為一種新的分布式計算模型被提出[3]，MCC允許終端從云計算中心借用計算和存儲資源，滿足資源需求型應用程序的需要[4]。盡管MCC可以節(jié)約本地的計算資源，但是，從移動設備到基站或云服務器的長距離傳輸可能會導致嚴重的時間延遲和額外的傳輸能耗[5-6]。

針對MCC存在的問題，歐洲電信標準化協(xié)會(European Telecommunications Standards Institute,ETSI)提出了移動邊緣計算(Mobile Edge Computing,MEC)技術[7]。由于MEC卸載策略具有非確定性多項式難題(Nondeterministic Polynominal-Hard,NP-Hard)，大多數(shù)卸載策略都采用啟發(fā)式算法[8]。例如，文獻[9]提出了一種單用戶的MEC系統(tǒng)優(yōu)化框架，該框架采用一種基于線性規(guī)劃松弛和半確定松弛方法的卸載決策算法，降低了執(zhí)行延遲和能耗。文獻[10]設計了一種基于遺傳算法的任務卸載策略，減小了系統(tǒng)的總開銷。文獻[11]將MEC模型中的任務卸載問題描述為非線性問題，并提出了一種卸載算法來減少任務延遲并提高用戶設備(User Equipment,UE)的電池壽命。文獻[12]提出了一種基于能量消耗和等待時間的任務分擔算法，其能耗和等待時間加權總和較低。文獻[13]提出了一種基于改進遺傳算法的邊緣卸載策略，將每個卸載策略作為一條染色體，每條染色體上的基因對應一個計算任務，以降低系統(tǒng)總開銷。但是，隨著MEC應用程序和網(wǎng)絡架構的日益復雜，導致啟發(fā)式算法生成決策的時間過長，特別是在多用戶的MEC環(huán)境下如何減少計算卸載的系統(tǒng)總時延和系統(tǒng)總成本，還需進一步研究。

為了減少生成決策的時間、降低系統(tǒng)總成本，研究人員開始通過深度強化學習(Deep Reinforcement Learning,DRL)的方法來解決MEC卸載決策問題。DRL結合了強化學習與深度學習理論，更適用于處理復雜系統(tǒng)中的決策問題[14]。例如，文獻[15]提出了一種基于深度Q學習網(wǎng)絡(Deep Q-Learning Network,DQN)的自主算法，以最小化分布式邊緣網(wǎng)絡中的網(wǎng)絡延遲和功耗。文獻[16]使用DQN方法處理新穎的網(wǎng)絡知識，產(chǎn)生了近似的最優(yōu)調度容忍機制，減輕了對反饋的嚴格要求。文獻[17]提出了一種基于DQN的設備級和邊緣級任務卸載聯(lián)合優(yōu)化方法，獲得了接近最優(yōu)的任務延遲性能。文獻[18]提出了一種基于強化學習計算的車聯(lián)網(wǎng)邊緣計算架構的任務卸載策略，并采用雙深度Q學習網(wǎng)絡(Double Deep Q-Learning Network,DDQN)方法處理任務卸載問題，以克服用戶移動引起的網(wǎng)絡狀態(tài)實時變化，提高了該策略的收斂性。文獻[19]提出了一種利用DDQN方法在給定當前環(huán)境狀態(tài)的情況下輸出卸載決策。文獻[20]分別利用DQN算法和深度確定性策略梯度(Deep Deterministic Policy Gradient,DDPG)算法研究了任務的最佳卸載比例、局部計算功率和傳輸功率，以最小化執(zhí)行延遲和UE能耗。但是，目前利用DRL對MEC中卸載問題的研究仍存在兩個方面的不足：一方面，MEC服務器的計算資源有限，同時卸載太多任務會導致排隊延遲；另一方面，經(jīng)典DRL方法在訓練過程中存在訓練速度慢、收斂不穩(wěn)定等問題，影響了卸載計算的效率。

為了更好地利用MEC系統(tǒng)資源，降低系統(tǒng)成本，提高系統(tǒng)的效率，擬設計一種適用于MEC環(huán)境的二進制計算卸載策略。在有效減小UE和各計算節(jié)點的能耗與時延的基礎上，決定任務是否應該卸載至邊緣服務器執(zhí)行，以提高MEC系統(tǒng)的效率。在任務卸載執(zhí)行的時延中引入排隊時延的計算，以最小化能耗與時延加權和作為計算卸載的目標，利用優(yōu)先經(jīng)驗重放對DRL算法進行改進，對比改進前后不同用戶設備數(shù)量和任務數(shù)據(jù)大小的系統(tǒng)成本以及改進前后系統(tǒng)的平均時延，以提高其在解決實際問題時的效率及穩(wěn)定性。

1 系統(tǒng)模型

考慮到移動邊緣計算中具有多服務節(jié)點和多用戶的系統(tǒng)模型，建立一個多邊緣服務器和多用戶的MEC系統(tǒng)通信模型。該模型由一個包含多個邊緣服務器的基站(Base Station,BS)和m個UE組成[20]，UE與BS間通過無線網(wǎng)絡通信，MEC系統(tǒng)示意圖如圖1所示。

圖1 MEC系統(tǒng)示意圖

MEC系統(tǒng)中包含UE1,UE2,…,UEm等m個用戶。設時間為一組相等間隔的時隙t(t=1,2,…,z)，任務產(chǎn)生的時間間隔服從泊松分布[21]。UE生成的任務i(i=1,2,…,I)可以建模為一個具有4個元素的元組{Di,bi,Ci,Ti,max}，其中，Di表示任務i數(shù)據(jù)的大小，bi表示計算任務i每一位數(shù)據(jù)的CPU周期，Ci=Di·bi為任務i的總CPU周期，Ti,max表示用戶可接受的最大容忍時延。

定義任務i的二進制計算卸載決策變量為ψi∈{0,1}。當ψi=0時，表示任務i在本地執(zhí)行；ψi=1時，表示任務i卸載至邊緣服務器執(zhí)行。

1.1 本地計算

移動UE具有一定的計算能力。假設移動UE一次只能執(zhí)行一個任務。假設第k個(k=1,2,…,m)用戶設備UEk的容量為Uk,C，任務開始前每個時隙設備k的剩余能量為Ek,re，執(zhí)行任務i的能量消耗為Ei,k。若滿足Di≤Uk,C和Ei,k≤Ek,re，則任務在本地執(zhí)行。

本地計算模型的執(zhí)行時間僅包括計算時間，不包含傳輸時間。在本地執(zhí)行任務i的時間成本[19]為

(1)

式中，fk表示UEk的CPU頻率，即UEk的每秒CPU周期，反映了其計算能力。

在UEk上執(zhí)行任務i的能量消耗[19]為

Ei,k=κ·fk·Ci

(2)

式中，κ表示芯片中的有效開關電容，其大小取決于器件的芯片架構。

1.2 卸載計算模型

用戶移動設備的計算資源有限，執(zhí)行某些資源密集型應用時會產(chǎn)生較高的時延與能耗。當本地資源不足時，將任務卸載到MEC服務器上處理。

由于任務計算完成后傳回UE的數(shù)據(jù)量通常遠小于其原始數(shù)據(jù)，因此傳回的時間可忽略不計。傳輸時間僅為從UE向MEC服務器上傳任務數(shù)據(jù)的時間成本，根據(jù)香農(nóng)公式，UEk與BS的通信速率[22]為

(3)

式中：W表示UEk和BS之間的通信帶寬；pk是UEk的發(fā)射功率；N0是BS的噪聲功率譜密度；gk,B表示UEk和BS之間的信道增益[22]，其計算表達式為

(4)

式中：dk,B表示UEk與BS之間的距離；σ為路徑損耗指數(shù)。

發(fā)送任務i的數(shù)據(jù)產(chǎn)生的延遲[22]為

(5)

在MEC服務器上執(zhí)行任務i的延遲[22]為

(6)

式中，fs,k表示服務器s分配給UEk的計算資源。

任務i卸載至MEC服務器進行處理的能耗為上傳能耗和計算能耗的總和。其中任務i上傳能耗Ei,tr與MEC服務器執(zhí)行任務i的能耗[22]Ei,mec分別定義為

Ei,tr=pk·Ti,tr

(7)

Ei,mec=Di·es

(8)

式中，es表示服務器s在BS上計算的每個數(shù)據(jù)位的能耗。

2 PERDDQN的卸載策略

DRL對于復雜系統(tǒng)的感知決策問題有較強的解決能力[23]，但是，在MEC場景內(nèi)實際應用時往往由于很難學習到有用的經(jīng)驗，導致無法得到合理卸載策略。為此引入了一種基于優(yōu)先經(jīng)驗重放(Prioritized Experience Replay,PER)改進的DDQN算法(Prioritized Experience Replay Double Deep Q-Learning Network,PERDDQN)來求解最優(yōu)的卸載模式。

2.1 問題的建模

任務卸載執(zhí)行時，移動設備用戶會對有限計算資源的競爭而產(chǎn)生排隊延遲。設MEC服務器中可用的計算資源Vmec，則任務i等待執(zhí)行產(chǎn)生的排隊時延為

(9)

聯(lián)合式(5)、式(6)和式(9)，UEk將任務i卸載到BS上的服務器s處理所產(chǎn)生的時間成本為

Ti,off=Ti,tr+Ti,que+Ti,mec

(10)

根據(jù)式(7)和式(8)可得，任務i卸載執(zhí)行的能耗為

Ei,off=Ei,tr+Ei,mec

(11)

MEC系統(tǒng)中存在多個用戶，每個用戶都遵循二進制卸載決策完成計算任務。根據(jù)式(1)與式(10)，MEC系統(tǒng)執(zhí)行全部任務的總時延為

(12)

當ψi=0時，Ti=Ti,k；當ψi=1時，Ti=Ti,off。

同理，執(zhí)行所有任務的總能耗為

(13)

當ψi=0時，Ei=Ei,k；當ψi=1時，Ei=Ei,off。

為了同時考慮能量消耗和延遲，總計算成本根據(jù)能量消耗和任務延遲線性加權進行量化。聯(lián)合式(12)和式(13)，系統(tǒng)總成本可以表示為

(14)

式中，ω∈(0,1)表示為UE的執(zhí)行延遲加權參數(shù)，可以根據(jù)用戶的需求進行調整，例如，執(zhí)行時延敏感型應用程序時可適當增大ω的值。考慮到時延敏感型應用程序，ω取0.8[24-25]。

多計算節(jié)點多用戶卸載問題的目標是在滿足用戶最大容忍時延的條件下，最小化系統(tǒng)總成本，該問題是具有耦合約束的多目標優(yōu)化編程。目標函數(shù)建模為

(15)

式中：fk,max表示UEk的最大計算功率；pk,max表示UEk的最大發(fā)射功率；Fs,max表示服務器s的最大計算頻率；C1表示選擇任務在本地執(zhí)行或卸載至邊緣服務器執(zhí)行；C2表示執(zhí)行任務的能耗不能超過UE當前剩余能量，若能量不足則任務需卸載執(zhí)行；C3表示設備計算頻率最大限制；C4表示傳輸功率最大限制；C5表示服務器分配的計算資源不能超過其最大計算資源；C6表示任務需要在可容忍時延內(nèi)完成。

2.2 MDP模型的構建

強化學習的過程中，將計算卸載問題重新表述為馬爾科夫決策過程(Markov Decision Process,MDP)模型。典型的MDP模型由具有5個元素的元組{S,A,P,R,γ}組成。其中，S代表狀態(tài)空間，A為有限動作空間，P為狀態(tài)轉移概率，R代表獎勵函數(shù)，γ∈[0,1]是未來獎勵的折扣因子。MDP模型元組中每個元素對應的含義如下。

1)狀態(tài)空間。狀態(tài)空間中的每個狀態(tài)都包含一些從環(huán)境中觀察到的信息。將模型中時隙t的狀態(tài)s(t)表示為s(t)={fk,Ek,re,Uk,C,W,Di}。

2)動作空間。為了確定任務是否應卸載到計算節(jié)點上執(zhí)行，動作空間與卸載決策應呈對應關系。動作空間的定義為

A={a(1),a(2),…,a(z)}

(16)

在時隙t(t=1,2,…,z)，a(t)=0表示任務在本地執(zhí)行，a(t)=1表示任務卸載至邊緣服務器執(zhí)行。

3)獎勵函數(shù)。在執(zhí)行動作a(t)后，將獲得獎勵r(s(t),a(t))，UE選擇要執(zhí)行的動作a(t+1)。獎勵函數(shù)通常與目標函數(shù)相關，為了高效判斷任務是否需要卸載執(zhí)行，將目標函數(shù)定義為實現(xiàn)最小化任務執(zhí)行時間與能耗的加權和。強化的目標是獲得最大獎勵，為此定義獎勵值R與系統(tǒng)總成本C的大小負相關，即

R=-C(t)

(17)

4)轉移概率。給定用戶采取的操作a(t)，轉移概率P{s(t+1)|s(t),a(t)}表示環(huán)境狀態(tài)在下一個時隙中從s(t)轉換為s(t+1)的概率。

5)折扣因子。折扣因子γ為未來獎勵權重。當γ趨于0時，表示主要考慮當前獲得的獎勵；γ趨于1則表示將更關注后續(xù)步驟中的累積獎勵。γ的值決定了更傾向于短期回報或長期回報。

2.3 優(yōu)先級的計算

PERDDQN算法利用PER在訓練過程中對樣本進行優(yōu)先級采樣，用于加快神經(jīng)網(wǎng)絡的訓練速度。PER打破均勻采樣，賦予學習效率高的狀態(tài)更大的采樣權重[26]。PER采用時間差分(Temporal-Difference,TD)誤差來表示每個轉移過渡的重要性。

TD誤差為目標Q網(wǎng)絡計算的目標Q值和當前Q網(wǎng)絡計算的Q值之差。TD誤差越大代表預測精度還有很大的上升空間，那么該樣本就越需要被學習，優(yōu)先級就越高，樣本j優(yōu)先級可以表示為

δj=yj,PER-Q(SJ(T),AJ,θ)

(18)

其中：yj,PER為目標的Q值；Q(sj(t),aj,θ)為當前網(wǎng)絡的Q值。

為了避免初始的高TD誤差轉移被經(jīng)常重放，帶有低TD誤差的轉移在第一次訪問時不會被重放，引入了隨機采樣方法。該方法結合純貪婪優(yōu)先化和均勻隨機采樣，既保證被采樣的概率是單一的，也能使低優(yōu)先級樣本采樣概率非零。定義樣本j的采樣概率為

(19)

式中：n表示樣本數(shù)量；α確定使用多少優(yōu)先級，當α=0時為均勻采樣。

2.4 樣本的存儲

由于優(yōu)先級大小會影響被采樣的概率，導致PERDDQN算法的經(jīng)驗重放池與其他采用Q學習的DRL算法不同。使用SumTree結構[26]作為帶有優(yōu)先級的經(jīng)驗重放池，用于樣本的儲存。SumTree結構示意圖如圖2所示。圖中，圈外數(shù)字為節(jié)點序號，圈內(nèi)數(shù)字為節(jié)點值，例如0號節(jié)點的節(jié)點值為29。圖中陰影部分為葉子節(jié)點，所有的經(jīng)驗重放樣本只保存在葉子節(jié)點上，一個節(jié)點對應一個樣本。0號到2號節(jié)點不保存樣本數(shù)據(jù)，只保存自己子節(jié)點的優(yōu)先級值之和。葉子結點下面是樣本對應的數(shù)值區(qū)間，葉子結點數(shù)值越大(優(yōu)先級越高)其區(qū)間長度就越大。例如，從區(qū)間0～29中均勻抽樣一個數(shù)據(jù)，5號節(jié)點的區(qū)間為14～26，優(yōu)先級為12，比其他節(jié)點更容易被采樣。

圖2 SumTree結構示意圖

2.5 網(wǎng)絡參數(shù)的更新

從SumTree中采得樣本后，使用均方差損失函數(shù)通過神經(jīng)網(wǎng)絡的梯度反向傳播來更新Q網(wǎng)絡的參數(shù)，并計算當前目標Q值。PERDDQN算法的損失函數(shù)L(θ)與當前目標Q值yj,PER的計算表達式分別為

PER以一種不受控的形式改變了分布，因此引入了誤差，改變了預測會收斂到的解決方案。可以使用重要性采樣權重來修正該誤差[26]。

網(wǎng)絡參數(shù)更新完畢后根據(jù)狀態(tài)s′判斷整個算法是否結束，若結束則輸出最優(yōu)的卸載決策。根據(jù)以上改進的DRL算法，結合MDP模型的MEC計算卸載策略的偽代碼如下所示。

3 仿真與結果分析

3.1 實驗環(huán)境選擇及參數(shù)設置

為驗證提出的DRL算法在MEC環(huán)境中的有效性，使用TensorFlow-GPU 1.13.1在Python3.7.4中實現(xiàn)了PERDDQN算法。驗證算法的收斂性，并與本地執(zhí)行(All Local Executing,ALE)、完全卸載(All Offload Executing,AOE)、隨機卸載(Random Offloading Executing，ROE)、DDQN[19]和DDPG[20]等算法進行比較，驗證在多用戶MEC系統(tǒng)中的算法的總成本，反映算法的優(yōu)劣。

仿真實驗模擬的集群包括2個邊緣服務器，5～30個移動用戶設備。其中，移動用戶設備隨機分布在距基站150 m范圍內(nèi)，每個邊緣服務器的計算能力設置為1 GHz～5 GHz。任務數(shù)據(jù)的隨機大小為100 kb～500 kb。任務的最大可容忍時延在5 ms～30 ms隨機選擇。

對于深度強化學習算法，深度神經(jīng)網(wǎng)絡的輸入包括狀態(tài)值s(t)和動作值a(t)。在實驗神經(jīng)網(wǎng)絡的構建中，將s(t)作為輸入，輸出層是每個a(t)對應的Q值。經(jīng)驗重放池容量為1 000，訓練時采用貪婪法選擇動作，貪婪策略概率為0.1，批學習大小為32，學習率為0.01，折扣因子γ=0.9。

3.2 算法的收斂性

PERDDQN算法、DDPG算法以及DDQN算法的收斂性能如圖3所示。可以看出，3種算法的總獎勵都隨著迭代次數(shù)的增加而增加，直至達到一個相對穩(wěn)定的值。當?shù)螖?shù)為分別為50、75和100時，PERDDQN算法、DDPG算法和DDQN算法的獎勵值不再增加并趨于穩(wěn)定值，分別在-20、-25、-30左右。可見，PERDDQN算法是收斂的，且收斂速度比DDPG和DDQN快、獎勵值也大于其他兩種比較算法，這使得該算法能夠更好地應對動態(tài)的MEC環(huán)境。

圖3 3種算法的收斂性

3.3 系統(tǒng)成本

不同數(shù)量UE以及不同任務數(shù)據(jù)量大小的成本不同。6種算法的總成本如圖4所示。可以看出，6種算法的總成本隨著UE數(shù)量和任務數(shù)據(jù)大小的增加。這是因為，UE數(shù)量和任務數(shù)據(jù)越大，執(zhí)行時間和傳輸時間就越長，處理具有較大數(shù)據(jù)量的任務所消耗的能量也更多。當UE數(shù)量為20時，應用PERDDQN算法的系統(tǒng)總成本為2.49，其余算法的系統(tǒng)總成本均超過3.00；當任務數(shù)據(jù)大小為500 kb時，應用PERDDQN算法的系統(tǒng)總成本為2.42，其余算法的系統(tǒng)總成本均超過2.80。由此可見，在UE數(shù)量和任務大小相同的情況下，PERDDQN算法的系統(tǒng)總成本始終是最小的，分別比未改進的DDQN算法減少了17.6%和23.0%。這是因為，與DDQN和DDPG算法相比，PERDDQN算法收斂速度更快，可以更快地獲得最優(yōu)策略，從而系統(tǒng)總成本較低，而ALE和AOE算法不能充分利用整個系統(tǒng)的計算資源，因此，具有較高的成本。

圖4 6種算法的總成本

3.4 服務器計算能力對系統(tǒng)時延的影響

圖5顯示了使用不同的優(yōu)化算法時，平均時延隨MEC服務器計算能力的增加而變化的情況。由于ALE算法不涉及MEC服務器，因此不做討論。除了ALE之外，其他方法的平均時延均隨著MEC服務器計算能力的提升而逐漸降低，這是由于MEC服務器的計算能力逐漸滿足所有UE卸載任務的計算需求。當MEC服務器計算能力為1 GHz時，PERDDQN算法、DDPG算法、DDQN算法的平均時延分別為14.01 ms、15.10 ms、16.90 ms；當MEC服務器計算能力增加為5 GHz時，PERDDQN算法、DDPG算法、DDQN算法的平均時延分別為8.21 ms、9.28 ms、9.71 ms。由此可見，與其他兩種DRL算法相比，PERDDQN算法的任務卸載解決方案的平均時延較低。因為該算法頻繁重放具有價值的樣本數(shù)據(jù)，對于復雜的環(huán)境具有更好的適應性，在解決復雜的組合優(yōu)化問題時的效果較好。

圖5 不同MEC計算能力的平均時延

4 結語

針對多移動用戶設備和多服務器的MEC環(huán)境，在滿足用戶最大容忍時延的前提下考慮了時延與能耗，提出了一種以最小化系統(tǒng)總成本為目標的任務卸載優(yōu)化策略。將目標函數(shù)建模為MDP模型，提出基于PER改進的PERDDQN卸載決策算法。該算法利用PER對DRL算法進行改進，并對歷史經(jīng)驗賦予優(yōu)先級，優(yōu)先采樣高優(yōu)先級的經(jīng)驗，以提高學習效率，快速、準確地做出合理的卸載決策。仿真結果表明，PERDDQN卸載決策算法的系統(tǒng)總成本較低、系統(tǒng)的平均時延較小。

研究基于單基站多用戶的MEC模型，僅將任務作為一個整體卸載，實際中的MEC系統(tǒng)通常包含多個基站，高復雜度的計算任務也可進一步劃分為更小的子任務進行卸載。因此，下一步工作將基于DRL對包含多個基站、多個移動設備MEC系統(tǒng)的細粒度任務卸載問題進行研究。