鄧文貴，文志誠，歐 靜

(湖南工業(yè)大學(xué) 計算機學(xué)院，湖南 株洲 412000)

0 引 言

移動云計算(mobile could computing，MCC)是一種集中式部署計算模式，可以利用云計算中心豐富的計算、儲存、網(wǎng)絡(luò)等資源提高移動終端的計算處理能力[1]。但是，移動終端設(shè)備和計算任務(wù)的增加，以及有限的網(wǎng)絡(luò)帶寬和較遠的傳輸距離，嚴重影響計算任務(wù)的數(shù)據(jù)傳輸，使得傳輸過程中的能耗和時延增大[2]，從而無法滿足延遲敏感型的計算任務(wù)，降低了用戶的體驗質(zhì)量。

為了彌補移動云計算的不足，移動邊緣計算(mobile edge computing，MEC)作為一種新的卸載方案被提出[3]。MEC采用分布式部署方式，將MEC服務(wù)器部署在移動設(shè)備網(wǎng)絡(luò)邊緣的基站，并在邊緣服務(wù)器上部署云計算中的計算、存儲等資源，相比于MCC，終端設(shè)備可以直接與MEC服務(wù)器進行數(shù)據(jù)傳輸，能夠更快速響應(yīng)用戶的計算任務(wù)卸載請求，減少訪問云計算中心的頻率，降低計算任務(wù)上傳時的能耗、傳輸延遲和網(wǎng)絡(luò)擁塞[4-6]。MEC系統(tǒng)的效率主要取決于任務(wù)卸載策略，而目前大多數(shù)研究將卸載問題描述為NP問題并通過啟發(fā)式算法進行求解。但這些算法不能保證其魯棒性，只能應(yīng)用于特定場景，難以適用于復(fù)雜的現(xiàn)實場景。

近些年，深度強化學(xué)習(xí)(deep reinforcement learning，DRL)[7]因其具有很好的環(huán)境適應(yīng)性而被廣泛應(yīng)用到各個領(lǐng)域以解決實際問題。DRL最顯著的算法之一是深度Q學(xué)習(xí)(DQN)，多用于處理連續(xù)狀態(tài)空間中的問題[8]，通過將深度學(xué)習(xí)模型與強化學(xué)習(xí)結(jié)合，實現(xiàn)直接從高位輸入學(xué)習(xí)的控制策略，進而提高算法收斂性能并解決當(dāng)前任務(wù)計算卸載所面臨的局限性。

1 相關(guān)工作

MEC系統(tǒng)的效率很大程度依賴于其任務(wù)卸載策略，因此MEC任務(wù)卸載策略成為了當(dāng)前研究的熱點。文獻[9]為降低細粒度任務(wù)遷移模型下的任務(wù)執(zhí)行時間，提出了基于遺傳算法的MEC任務(wù)緩存和遷移策略。文獻[10]提出了一種基于遺傳算法的聯(lián)合資源優(yōu)化方法，以優(yōu)化MEC服務(wù)器中的卸載比例、信道帶寬和計算資源分配，從而得到任務(wù)完成時間最小的卸載策略。文獻[11]將移動應(yīng)用程序建模為有向無環(huán)圖提出基于元強化學(xué)習(xí)的任務(wù)卸載策略，以降低任務(wù)執(zhí)行時延。文獻[12]提出了一種滿足不同任務(wù)延遲要求的啟發(fā)式任務(wù)卸載策略，通過合理分配MEC服務(wù)器無線電資源和計算資源來提高系統(tǒng)的執(zhí)行效率。文獻[13]針對邊云場景提出了一種智能蟻群任務(wù)卸載策略，以降低服務(wù)延遲，提高用戶服務(wù)質(zhì)量。文獻[14]為最小化所有系統(tǒng)實體的開銷，從任務(wù)計算和通信方面對卸載的消耗進行建模，提出了一種基于人工魚群算法的卸載方案，以優(yōu)化系統(tǒng)整體開銷。

此外，移動設(shè)備的任務(wù)計算卸載決策受限于網(wǎng)絡(luò)帶寬和存儲計算資源，因此研究人員開始嘗試通過深度學(xué)習(xí)和強化學(xué)習(xí)來解決計算卸載問題。文獻[15]將計算卸載視為一種游戲，由玩家(即移動設(shè)備)、策略(即本地或遠程執(zhí)行任務(wù))和獎勵值組成，然后采用Q-學(xué)習(xí)算法來解決此問題。文獻[16]提出了基于深度Q網(wǎng)絡(luò)的半在線計算卸載模型，通過強化學(xué)習(xí)來探索復(fù)雜動作空間中的用戶行為捕捉未知的環(huán)境信息。文獻[17]考慮了一個多用戶MEC系統(tǒng)，并提出基于RL的優(yōu)化框架來解決任務(wù)卸載的計算卸載和資源分配問題。文獻[18]采用深度強化學(xué)習(xí)來優(yōu)化虛擬邊緣計算系統(tǒng)從而提高計算卸載性能，但作者只是做了假設(shè)，而沒有在許多細節(jié)上探索事實。當(dāng)然，將強化學(xué)習(xí)應(yīng)用于邊緣計算的技術(shù)也在不斷趨于成熟。文獻[19]提出了一種新的基于狀態(tài)自適應(yīng)和深度強化學(xué)習(xí)的服務(wù)遷移方法來克服網(wǎng)絡(luò)故障，并利用滿足度理論來求解遷移策略的候選空間。文獻[20]提出了基于DRL的經(jīng)驗驅(qū)動網(wǎng)絡(luò)，它顯著減少了端到端延遲，并持續(xù)提高了網(wǎng)絡(luò)利用率。

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)架構(gòu)模型

我們考慮多用戶多MEC服務(wù)器邊云協(xié)同的場景，并考慮一個實時多用戶計算場景。利用云服務(wù)器和邊緣服務(wù)器的相互協(xié)同來完成移動設(shè)備的計算任務(wù)，具有云計算和存儲能力的移動基站密集分布在移動用戶附近，云服務(wù)器部署在遠離終端設(shè)備的網(wǎng)絡(luò)層。在本文中，我們考慮邊云協(xié)同，當(dāng)計算任務(wù)卸載時根據(jù)不同的卸載決將任務(wù)卸載到本地、該區(qū)域內(nèi)的MEC服務(wù)器和云服務(wù)器上進行計算。

移動邊緣計算系統(tǒng)架構(gòu)模型如圖1所示。卸載模型由多個終端設(shè)備、多個邊緣服務(wù)器和一個云服務(wù)器組成，構(gòu)成一個云-邊-終端的三層結(jié)構(gòu)。在該移動邊緣計算網(wǎng)絡(luò)架構(gòu)中，最上端的云服務(wù)器，利用交換機和基站聯(lián)系，整個互聯(lián)網(wǎng)由多個基站組成，多個小型MEC服務(wù)器部署在各個基站周圍，MEC服務(wù)器之間能夠?qū)崿F(xiàn)數(shù)據(jù)通信。在終端智能設(shè)備側(cè)，其產(chǎn)生的任務(wù)可直接在本機的CPU上進行，也可通過傳輸單元發(fā)送到其所在區(qū)域中的MEC服務(wù)器中實現(xiàn)遠程運算，甚至上傳到遠端的云服務(wù)器中實現(xiàn)運算。

圖1 移動邊緣計算系統(tǒng)架構(gòu)模型

整個移動邊緣計算系統(tǒng)網(wǎng)絡(luò)架構(gòu)，由若干個小區(qū)域組成，區(qū)域之間相互獨立。在一個區(qū)域中，假設(shè)用戶終端設(shè)備用集合 {1，2，…i，…，U} 表示，終端設(shè)備所在區(qū)域的MEC服務(wù)器用集合 {1，2，…j，…，M} 表示，用戶設(shè)備擁有有限的計算資源，智能設(shè)備Ui(i∈{1，2，…，U}) 通過5G無線通信技術(shù)將自己的計算任務(wù)卸載到MECj服務(wù)器 (j∈{1，2，…j，…，M}) 中，也可以選擇卸載到遠端的云服務(wù)器上進行計算，或者選擇在本地進行計算。

2.2 任務(wù)模型

每個終端設(shè)備都有一個計算密集型任務(wù)需要執(zhí)行，智能設(shè)備Ui產(chǎn)生的任務(wù)用Ai來表示，由3部分組成，Ai定義如式(1)所示

Ai={wk，dk，τk}

(1)

2.3 通信模型

用戶可以選擇將自己的任務(wù)在本地執(zhí)行，也可以卸載到邊緣服務(wù)器或遠端云服務(wù)器中執(zhí)行，在整個系統(tǒng)中，主要存在兩部分通信。包括用戶將任務(wù)傳輸?shù)組EC服務(wù)器的通信和MEC服務(wù)器與云服務(wù)器之間的通信。根據(jù)瑞利衰落信道模型，定義通信模型如下：

用戶Ui將任務(wù)Ti上傳到MECj的傳輸速率為

(2)

其中，B代表傳輸帶寬，pi，j為用戶Ui的傳輸功率，hi，j為信道增益，di，j代表用戶i與服務(wù)器j之間的距離，θ代表路徑損耗指數(shù)，N為高斯加白噪聲。

任務(wù)Ti從邊緣服務(wù)器MECj上傳到云服務(wù)器Cloud傳輸速率為

(3)

同理，其中B代表傳輸帶寬，pj，c為MECj到云服務(wù)器的傳輸功率，hj，c為信道增益，dj，c代表服務(wù)器j和云服務(wù)器之間的距離，θ代表路徑損耗指數(shù)，N為高斯加白噪聲。

2.4 計算模型

在這一小節(jié)，介紹了計算模型。本地服務(wù)器、邊緣服務(wù)器和云服務(wù)器都可以進行任務(wù)計算因此計算模型由本地計算、邊緣服務(wù)器計算和云服務(wù)器計算3種模型組成。本地計算模型即智能設(shè)備將任務(wù)卸載在本地進行計算，邊緣服務(wù)器和云服務(wù)器計算模型分別指的是將計算任務(wù)卸載到邊緣服務(wù)器和云服務(wù)器進行計算。

(1)本地計算模型

根據(jù)上面定義的任務(wù)模型，wk為該任務(wù)的負載，即執(zhí)行該任務(wù)需要花費的總CPU周期數(shù)，fi為用戶Ui的計算能力，則用戶i的任務(wù)k在本地的執(zhí)行時延為

(4)

(5)

用戶i的任務(wù)k在本地運行的總能耗為

(6)

其中，ki是設(shè)備芯片結(jié)構(gòu)的系數(shù)因子。

(2)邊緣服務(wù)器計算模型

當(dāng)用戶選擇卸載到邊緣服務(wù)器上進行計算時，用戶i向MEC服務(wù)器j傳輸任務(wù)的時延為

(7)

MECj的執(zhí)行時延為

(8)

其中，wk為任務(wù)的負載，即執(zhí)行該任務(wù)需要花費的總CPU周期數(shù)，服務(wù)器的計算能力為fj。

因此，用戶i的任務(wù)在MECj運行的總時延

(9)

用戶i的任務(wù)在MECj運行的能耗

(10)

(3)云服務(wù)器計算模型

當(dāng)用戶選擇卸載到云服務(wù)器上進行計算時，終端設(shè)備i需要先將任務(wù)上傳到臨近的MEC服務(wù)器，再上傳到云服務(wù)器。

用戶i向鄰近MEC服務(wù)器MECj傳輸任務(wù)的時延為

(11)

任務(wù)從MEC服務(wù)器j上傳到遠端云服務(wù)器的傳輸時延為

(12)

所以總傳輸時延為

(13)

執(zhí)行時延為

(14)

其中，wi為任務(wù)的負載，即執(zhí)行該任務(wù)需要花費的總CPU周期數(shù)，云服務(wù)器的計算能力為Fcloud。因為云端計算速度特別快，所以我們忽略等待時延。

因此，執(zhí)行總時延為

(15)

整個過程產(chǎn)生的總能耗為

(16)

2.5 系統(tǒng)目標建立

在本文，我們綜合考慮時延和能耗兩個開銷指標，以能耗和時延的加權(quán)定義任務(wù)Ai的總開銷為Ci=β*Ei+(1-β)*Ti， 其中β∈[0，1] 代表設(shè)備的能量消耗權(quán)衡參數(shù)。假設(shè)Ii，j為任務(wù)所選擇的卸載策略，則用戶執(zhí)行任務(wù)的時延開銷為

(17)

用戶執(zhí)行任務(wù)的能耗開銷為

(18)

因此，用戶產(chǎn)生的總代價為

Ctotal=β*Etotal+(1-β)*Ttotal

(19)

在本文中，綜合考慮應(yīng)用程序執(zhí)行所產(chǎn)生的時延與能耗兩方面，從而使應(yīng)用程序的總執(zhí)行開銷達到最小。因此問題描述可以表示為

(20)

其中，I為用戶的卸載決策集。C1是應(yīng)用程序的時延約束，要求時延不能超過所要求的最大延遲。C2表示任務(wù)只能執(zhí)行在一個地方。根據(jù)P1，我們可以知道，該問題是一個混合整數(shù)規(guī)劃和NP難問題。

3 算法設(shè)計

如上所述，為了減少任務(wù)計算完成所產(chǎn)生的能耗與時延，在本節(jié)中，提出了深度強化學(xué)習(xí)算法來解決資源分配和任務(wù)調(diào)度策略。

3.1 強化學(xué)習(xí)設(shè)計

在本小節(jié)中，我們將計算卸載優(yōu)化問題表述為深度強化學(xué)習(xí)(DRL)過程。在獲得當(dāng)前移動邊緣計算網(wǎng)絡(luò)狀態(tài)之后，我們的目標是通過最小化整個網(wǎng)絡(luò)架構(gòu)下的時延和能耗開銷來提高計算卸載效率。由于變量、環(huán)境狀態(tài)和系統(tǒng)動作的巨大空間隨時間動態(tài)變化，用傳統(tǒng)的優(yōu)化方法幾乎不可能解決這個復(fù)雜的問題，但是，深度強化學(xué)習(xí)方法卻能很好的解決這個問題。由于移動邊緣計算網(wǎng)絡(luò)架構(gòu)用戶動態(tài)請求和資源隨機分配，計算卸載策略算法應(yīng)該考慮MEC環(huán)境的狀態(tài)來做出有利的決策。因此，在本節(jié)中，我們提出了一種基于DQN的資源分配算法，以最小化時延和能耗的開銷并以自適應(yīng)的方式平衡資源分配。

RL系統(tǒng)可以通過探索環(huán)境和接收反饋來形成自適應(yīng)模型，而無需大量標記數(shù)據(jù)。它只是適應(yīng)我們考慮的多變的MEC環(huán)境。如第2節(jié)所述，傳統(tǒng)的Q-learning使用Q-table來存儲Q值，當(dāng)環(huán)境的狀態(tài)復(fù)雜多變時，將所有Q值存儲在一張表中是不切實際的，而且在一張大表中頻繁搜索狀態(tài)也很耗時。因此，我們采用上述DQN來實現(xiàn)我們的DRLRA，其直接通過神經(jīng)網(wǎng)絡(luò)生成對應(yīng)的Q值，即以MEC環(huán)境狀態(tài)作為輸入，每個可能動作的Q值作為輸出。我們提出的算法的訓(xùn)練階段如下所述。我們的DRLRA使用的DRL系統(tǒng)包含狀態(tài)、動作和獎勵等3個關(guān)鍵要素，應(yīng)首先定義：

狀態(tài)：強化學(xué)習(xí)目的是不斷從歷史信息中學(xué)習(xí)策略，考慮到用戶產(chǎn)生的任務(wù)、網(wǎng)絡(luò)情況、可用計算資源，狀態(tài)空間由應(yīng)用產(chǎn)生的任務(wù)列表及當(dāng)前產(chǎn)生的開銷組成，定義時刻t狀態(tài)向量可以表示為St=[c，n]t動作：在我們的DRL系統(tǒng)中，將終端用戶看作是一個決策者，決定在當(dāng)前的狀態(tài)下應(yīng)該選取怎樣的策略。動作由用戶任務(wù)可卸載的位置組成，動作向量可以給出為At=[Etar]t，Etar∈{-1，M}， 其中M為邊緣服務(wù)器的個數(shù)。Etar的值表示當(dāng)前用戶的任務(wù)請求所采取的動作，即決定卸載的位置。

3.2 基于深度強化學(xué)習(xí)的卸載策略算法設(shè)計

基于上一節(jié)的強化學(xué)習(xí)狀態(tài)空間、動作空間以及獎勵值的設(shè)計，設(shè)計基于深度強化學(xué)習(xí)的卸載策略算法。算法首先初始化深度強化學(xué)習(xí)的相關(guān)參數(shù)和移動邊緣計算網(wǎng)絡(luò)下的用戶、邊緣服務(wù)器以及云服務(wù)器，每個用戶通過訓(xùn)練獲得卸載策略。先生成初始狀態(tài)，并開始一個時間段的訓(xùn)練，通過運行當(dāng)前的決策網(wǎng)絡(luò)選擇當(dāng)前狀態(tài)的動作值at，執(zhí)行at并獲得獎勵rt和新的狀態(tài)st+1，并將狀態(tài)轉(zhuǎn)移過程存儲到經(jīng)驗池中，并從經(jīng)驗池中隨機采取一個小批量的樣本 (sj，aj，rj，sj+1) 進行訓(xùn)練，根據(jù)損失函數(shù)不斷優(yōu)化神經(jīng)網(wǎng)絡(luò)參數(shù)，最終得到卸載策略。具體的算法如算法1所示。

算法1：基于DQN的計算卸載策略

初始化經(jīng)驗池的大小為D，目標Q網(wǎng)絡(luò)的更新頻率為C

初始化邊緣服務(wù)器M，云服務(wù)器，用戶數(shù)量N

隨機初始化Q網(wǎng)絡(luò)的權(quán)值θ，目標Q網(wǎng)絡(luò)的權(quán)值θ-=θ

Forepisode= 1，Edo

初始化初始狀態(tài)s1

Fort=1，Tdo：

以概率ε隨機選擇動作at

若上一步中的概率ε沒有發(fā)生，則利用貪婪策略選擇當(dāng)前函數(shù)值最大的動作at=maxaQ*(st，a；θ)

執(zhí)行at并獲得獎勵rt和新的狀態(tài)st+1

將狀態(tài)轉(zhuǎn)移過程即經(jīng)驗 (st，at，rt，st+1) 存儲在D中

從D中隨機采取一個小批量的樣本 (sj，aj，rj，sj+1) 進行訓(xùn)練

根據(jù)損失函數(shù) (yj-Q(sj+1，at；θ)))2對參數(shù)θ進行梯度下降更新

每間隔C個步長更新一次目標網(wǎng)絡(luò)權(quán)值θ-=θ

End for

End for

4 實驗結(jié)果分析

4.1 實驗設(shè)置

在本節(jié)中，考慮多用戶多邊緣服務(wù)器基站的移動邊緣計算網(wǎng)絡(luò)環(huán)境，所以考慮了本地卸載策略、MEC隨機卸載策略、云端卸載策略、貪婪卸載策略4種算法與本文提出的算法進行對比，并對它們的實驗結(jié)果進行比較分析。

本地卸載策略指的是終端設(shè)備選擇將任務(wù)全部卸載在本地進行計算，MEC隨機卸載策略指的是隨機將任務(wù)卸載在所在區(qū)域的邊緣服務(wù)器上進行計算，云端卸載策略指的是將任務(wù)全部卸載在云服務(wù)器上，貪婪卸載策略指的是將任務(wù)卸載在當(dāng)前網(wǎng)絡(luò)中的最佳卸載位置。算法的參數(shù)設(shè)置見表1。

表1 仿真參數(shù)

4.2 結(jié)果分析

在本節(jié)中，先分析了算法的收斂性，接著通過將本文所提出的算法與其它的基準算法進行對比，驗證了算法的有效性。

系統(tǒng)獎勵值變化如圖2所示，隨著迭代次數(shù)變化獎勵值也不斷變化，它代表著算法的收斂性，從圖中可以看到隨著迭代次數(shù)的不斷增加，強化學(xué)習(xí)訓(xùn)練所獲得的獎勵回報值不斷增大且最終趨向于平穩(wěn)，大概200次迭代時候，獎勵值收斂到一個相比較穩(wěn)定的值，網(wǎng)絡(luò)參數(shù)達到相對穩(wěn)定狀態(tài)，表明網(wǎng)絡(luò)達到了穩(wěn)定最優(yōu)狀態(tài)，所有網(wǎng)絡(luò)輸出的卸載策略不再存在隨機性，而是根據(jù)當(dāng)前的狀態(tài)空間、網(wǎng)絡(luò)環(huán)境擇優(yōu)選擇。

圖2 系統(tǒng)獎勵值變化

不同的MEC服務(wù)器個數(shù)設(shè)置對設(shè)備開銷的影響如圖3所示。橫坐標是MEC服務(wù)器的個數(shù)，縱坐標是整個移動邊緣計算網(wǎng)絡(luò)環(huán)境中所有用戶的總開銷。設(shè)置MEC服務(wù)器的個數(shù)為5、6、7，然后采用本地卸載策略、MEC隨機卸載策略、云端卸載策略、貪婪卸載策略及DQN卸載策略算法進行卸載，并進行對比查看性能，首先可以看到在這5種卸載策略中，DQN卸載策略算法可以更好降低系統(tǒng)的開銷，以MEC數(shù)量為5進行實驗結(jié)果分析，本文所提出的DQN卸載策略算法與本地卸載策略、MEC隨機卸載策略、云端卸載策略以及貪婪卸載策略相比，優(yōu)化率分別達到了79.5%、55%、65.3%、31.2%。因為本地卸載策略是用戶全部選擇在本地計算，所以沒有利用邊緣計算服務(wù)器的計算能力強的優(yōu)勢，導(dǎo)致開銷很大。MEC隨機卸載策略，因為是隨機選取卸載位置，所以卸載位置隨機，且邊緣服務(wù)器如果位置不當(dāng)，也會產(chǎn)生較高的排隊時延和傳輸時延，所以整體開銷也較高。云端卸載策略選擇全部在云服務(wù)器計算，傳輸距離較遠，沒有綜合考慮任務(wù)特點和MEC服務(wù)器的優(yōu)勢，因此開銷也很大。貪婪算法是針對當(dāng)前用戶的任務(wù)去選擇局部的最優(yōu)卸載位置，但沒有全局考慮，雖然相比較前3種算法有所改進，但產(chǎn)生的時延也較高，而DQN采用強化學(xué)習(xí)的獎勵機制，以貪婪算法作為基線進行正向激勵的學(xué)習(xí)，所以產(chǎn)生的開銷較小，所以本文提出的卸載策略算法更優(yōu)。

圖3 不同的MEC服務(wù)器個數(shù)下的設(shè)備開銷

不同用戶數(shù)下的用戶開銷如圖4所示，分別測試了用戶數(shù)量為50、60、70的情況，且設(shè)置任務(wù)的數(shù)據(jù)大小隨即生成。因為當(dāng)設(shè)備數(shù)目越多時，其產(chǎn)生的任務(wù)越多，所需要的計算資源就越多，而MEC服務(wù)器、云服務(wù)器以及終端的智能設(shè)備的計算資源并非無限，所以如何分配資源，智能設(shè)備如何進行卸載，卸載策略顯得尤為重要。而在卸載策略選取上，可以看到DQN卸載策略有著更大的優(yōu)勢。以用戶數(shù)量50為例分析該算法的性能，與本地卸載策略、MEC隨機卸載策略、云端卸載策略、貪婪卸載策略相比，其優(yōu)化率分別為：79.7%、61.7%、70.2%、39.1%。

圖4 不同用戶數(shù)下的設(shè)備開銷

5 結(jié)束語

本文研究邊云協(xié)同架構(gòu)下基于多設(shè)備多MEC模型的任務(wù)卸載策略。首先，建立基于邊云協(xié)同架構(gòu)的系統(tǒng)模型，并基于該系統(tǒng)模型提出網(wǎng)絡(luò)模型、通信模型和計算模型。其次，為了滿足低能耗、低延遲的服務(wù)需求，我們以最小化系統(tǒng)開銷為目的，提出了聯(lián)合優(yōu)化時延和能耗的目標。然后基于深度強化學(xué)習(xí)算法，設(shè)計DQN卸載策略，為每個移動用戶制定獨立高效的計算卸載策略，最終可以自適應(yīng)決定將當(dāng)前產(chǎn)生的任務(wù)放置在本地、服務(wù)器或者云端進行計算。最后，通過仿真驗證了DQN卸載策略算法的收斂性和有效性。

在未來研究中，我們將考慮用戶的移動性以及MEC服務(wù)器的存儲資源，為用戶實時提供更高效的卸載服務(wù)。