基于深度強化學(xué)習(xí)的移動邊緣計算任務(wù)卸載研究

盧海峰 顧春華 羅 飛 丁煒超 楊 婷 鄭 帥

(華東理工大學(xué)信息科學(xué)與工程學(xué)院 上海 200237)

隨著近幾年各類智能設(shè)備的快速發(fā)展和廣泛普及，傳統(tǒng)以云數(shù)據(jù)中心為核心的運行模式在單位時間內(nèi)需要承載的數(shù)據(jù)量越來越大，其造成的數(shù)據(jù)阻塞和網(wǎng)絡(luò)延遲極大影響了用戶服務(wù)質(zhì)量.一方面是由于所用的業(yè)務(wù)數(shù)據(jù)交互都需要通過核心網(wǎng)進行傳輸，因此在網(wǎng)絡(luò)高峰期會對核心網(wǎng)產(chǎn)生很大負載壓力；另一方面是根據(jù)智能設(shè)備與云數(shù)據(jù)中心兩者之間的相對距離產(chǎn)生較大網(wǎng)絡(luò)延遲，這嚴重影響了延遲敏感性應(yīng)用的服務(wù)體驗[1].針對以上云計算服務(wù)模式產(chǎn)生的問題，移動邊緣計算(mobile edge computing, MEC)通過在靠近物理實體或數(shù)據(jù)源頭的一側(cè)采用網(wǎng)絡(luò)、計算、存儲和應(yīng)用核心能力為一體的開放平臺就近提供服務(wù)，使其應(yīng)用程序在邊緣側(cè)執(zhí)行，產(chǎn)生更快的網(wǎng)絡(luò)服務(wù)響應(yīng)，滿足行業(yè)在實時處理、智能應(yīng)用、安全和隱私保護等方面的基本需求[2].換言之，MEC的核心思想是將計算資源和緩存資源邊緣化和本地化，從而降低網(wǎng)絡(luò)延遲和緩解帶寬壓力，這樣既滿足了智能設(shè)備擴展計算能力的需求，同時也彌補了云計算平臺傳輸時延較長的缺點[3].

雖然MEC增強了智能設(shè)備的計算能力并且緩解了核心網(wǎng)的網(wǎng)絡(luò)壓力，但是其邊緣服務(wù)器在單位時間內(nèi)能夠處理的數(shù)據(jù)是有限的，因此需要設(shè)計一種卸載方案決定移動任務(wù)是在本地智能設(shè)備上執(zhí)行，還是卸載到遠程服務(wù)器上執(zhí)行.目前常見的任務(wù)卸載方式主要包括2種：粗粒度任務(wù)卸載和細粒度任務(wù)卸載.粗粒度任務(wù)卸載是指將整個移動終端應(yīng)用作為卸載對象，并未根據(jù)功能再將其劃分為多個子任務(wù)，這種卸載方法往往未充分考慮MEC邊緣服務(wù)器的低時延和性能相對有限的特性，同時對MEC邊緣服務(wù)器的資源利用率較低；細粒度任務(wù)卸載是指先將一個移動應(yīng)用劃分為多個具有數(shù)據(jù)依賴關(guān)系的子任務(wù)，因為劃分后的子任務(wù)所需的計算復(fù)雜度和數(shù)據(jù)傳輸量更少，因此可以將部分或者所有任務(wù)卸載到多個遠程服務(wù)器上進行處理，以此節(jié)省計算時間和傳輸時間，并且對邊緣服務(wù)器集群的資源利用率更高[4].因此本文將設(shè)計一種基于細粒度任務(wù)卸載的算法策略，結(jié)合深度強化學(xué)習(xí)構(gòu)建Markov決策過程(Markov decision processes, MDP)模型，以此解決卸載什么、卸載多少以及卸載到哪里的問題，最終有效減少智能設(shè)備和各服務(wù)節(jié)點的能耗、時延和網(wǎng)絡(luò)使用量，提高整個MEC平臺的資源利用率.

本文通過改進深度強化學(xué)習(xí)算法來解決MEC中具有大規(guī)模服務(wù)節(jié)點的任務(wù)卸載問題，其主要貢獻包含3個方面：

1) 構(gòu)建了大規(guī)模異構(gòu)MEC中具有多服務(wù)節(jié)點和移動任務(wù)內(nèi)部具有多依賴關(guān)系的卸載模型.

2) 結(jié)合MEC實際應(yīng)用場景，利用長短期記憶(long short-term memory, LSTM)和事后經(jīng)驗回放(hindsight experience replay, HER)改進深度強化學(xué)習(xí)算法，以此優(yōu)化任務(wù)卸載策略.

3) 綜合比較任務(wù)卸載策略的能耗、費用、負載均衡、延遲、網(wǎng)絡(luò)使用量和平均執(zhí)行時間等指標，以此分析各卸載策略的優(yōu)缺點.

1 相關(guān)工作

隨著5G技術(shù)的日益成熟，MEC的任務(wù)卸載問題在近幾年得到了廣泛關(guān)注和研究.其中，文獻[5]研究了基于任務(wù)卸載決策和通信資源分配的聯(lián)合優(yōu)化方案，用于最大程度上降低能耗、通信成本和延遲；文獻[6]研究了一種針對計算資源和無線網(wǎng)絡(luò)資源的多目標卸載決策，以便滿足延遲敏感性應(yīng)用的網(wǎng)絡(luò)需求，同時在此基礎(chǔ)上降低能耗；文獻[7]研究了基于計算資源和網(wǎng)絡(luò)資源的聯(lián)合優(yōu)化策略，通過部分計算卸載解決MEC中多用戶的延遲最小化問題；文獻[8]提出了基于時分多址和正交頻分多址的資源調(diào)度策略，解決了以最小化能耗為目標的部分計算卸載問題；文獻[9]提出移動任務(wù)可以根據(jù)需求選擇MEC中的多個基站進行計算卸載，并在此基礎(chǔ)上研究了基于深度強化學(xué)習(xí)算法的任務(wù)卸載策略以最大程度優(yōu)化長期性能.文獻[10]對MEC架構(gòu)進行了數(shù)學(xué)建模，通過在網(wǎng)絡(luò)邊緣測量用戶設(shè)備與MEC服務(wù)器的數(shù)據(jù)包往返時間，對MEC的計算卸載策略進行了優(yōu)化，決定了何時將用戶的計算任務(wù)卸載至MEC服務(wù)器上進行處理，并通過人臉識別應(yīng)用驗證了該策略的有效性，與移動設(shè)備的本地執(zhí)行相比大幅降低了服務(wù)時延、節(jié)省了設(shè)備的能源消耗.文獻[11]研究了MEC卸載場景下的多用戶業(yè)務(wù)時延問題，提出了一種新型的部分計算卸載模型，通過最優(yōu)數(shù)據(jù)分割等策略對通信及計算資源的分配進行了優(yōu)化，并在通信資源遠大于計算資源的特定場景下進行了實驗驗證，與設(shè)備的本地執(zhí)行及邊緣云執(zhí)行相比，所提出的部分卸載策略可以使所有用戶設(shè)備的加權(quán)時延最小，從而提高用戶的服務(wù)體驗質(zhì)量.目前大多數(shù)MEC卸載策略算法研究主要是假設(shè)資源需求的先驗分布或者基于歷史數(shù)據(jù)來預(yù)測資源需求;由于MEC的可用資源都是隨著信道質(zhì)量、任務(wù)到達率和能源狀態(tài)而動態(tài)變化的，因此先驗概率很難在實際環(huán)境中做出準確假設(shè)[12];文獻[13]在MDP框架中構(gòu)建了用于降低延遲的任務(wù)卸載模型，并提出了一種一維搜索算法來尋找最優(yōu)解，但該方法的前提是需要預(yù)先獲得集群環(huán)境中信道質(zhì)量變化以及任務(wù)到達的準確統(tǒng)計信息，所以該方法在真實場景中很難具有應(yīng)用價值；另外目前文獻提出利用啟發(fā)式算法來解決基于歷史數(shù)據(jù)的資源需求問題，文獻[14]利用Lyapunov優(yōu)化方法解決了具有無線能源傳輸功能的移動設(shè)備在動態(tài)任務(wù)卸載策略方面的研究；文獻[15-16]也同樣利用了Lyapunov方法對任務(wù)卸載的能耗和延遲進行了研究；文獻[17]使用線性整數(shù)規(guī)劃以及首次適應(yīng)和在線優(yōu)先等啟發(fā)式算法來優(yōu)化任務(wù)卸載中的延遲和能耗問題.以上研究在利用啟發(fā)式算法處理大規(guī)模任務(wù)卸載問題時都會由于問題維度過高導(dǎo)致算法生成決策的時間很長，同時該類算法也只能求出近似最優(yōu)解，因此其在實際使用中并不能符合預(yù)期要求.

基于上述研究，相比于假設(shè)先驗分布或者啟發(fā)式算法，深度強化學(xué)習(xí)通過結(jié)合深度學(xué)習(xí)和強化學(xué)習(xí)的優(yōu)勢，具有自學(xué)習(xí)和自適應(yīng)等特征，需要提供的參數(shù)較少，有較好的全局搜索能力，能夠解決較復(fù)雜、高維度且更加接近實際情況的任務(wù)場景.另外為保證算法策略在MEC的任務(wù)卸載問題中能夠具有更好的泛化性能及更快的收斂速度，本文利用LSTM和HER對深度強化學(xué)習(xí)算法DQN進行改進：

1) 在MEC真實環(huán)境中由于問題復(fù)雜性和感知局限性容易導(dǎo)致環(huán)境信息產(chǎn)生誤差及缺失，造成算法生成的策略缺乏有效性和穩(wěn)定性，因此結(jié)合LSTM是為了解決依賴于時序的任務(wù)卸載問題，利用部分觀測Markov過程(partially observed Markov decision processes, POMDP)對只有不完全狀態(tài)信息的系統(tǒng)建模,依據(jù)當(dāng)前的缺失信息做出決策，提高算法的泛化性能；

2) 深度強化學(xué)習(xí)算法在解決MEC實際問題時由于大部分情況下無法得到有效反饋，其模型很難學(xué)習(xí)到可用策略，造成求解復(fù)雜問題的決策無法收斂，因此結(jié)合HER是為了解決因為稀疏獎勵導(dǎo)致的收斂速度變慢問題.

相比于傳統(tǒng)深度強化學(xué)習(xí)算法，基于LSTM和HER改進的深度強化學(xué)習(xí)算法在實用性和收斂性上都有了很大提高，對解決MEC中任務(wù)卸載問題提供了更高效魯棒的算法策略.結(jié)合以上分析，本文重點研究了大規(guī)模異構(gòu)MEC中具有多服務(wù)節(jié)點和移動終端任務(wù)內(nèi)部具有多依賴關(guān)系的卸載問題，通過比較能耗、費用、負載、延遲、網(wǎng)絡(luò)使用量以及平均執(zhí)行時間等多方面因素來驗證基于深度強化學(xué)習(xí)算法策略的優(yōu)劣.

2 問題建模

2.1 任務(wù)依賴模型

MEC的組成結(jié)構(gòu)通常包含云數(shù)據(jù)中心層、邊緣服務(wù)器層以及用戶設(shè)備層3部分.如圖1所示，終端設(shè)備層包含各類傳感器、電腦和手機等具有一定處理性能的設(shè)備；邊緣服務(wù)器層是按照相對距離對所有邊緣服務(wù)器進行區(qū)域劃分，每個區(qū)域包含性能適中且異構(gòu)的邊緣服務(wù)器；云數(shù)據(jù)中心層包含大量性能優(yōu)異的物理服務(wù)器，這些服務(wù)器組成集群為用戶提供服務(wù).當(dāng)來自移動終端的任務(wù)需要卸載時，首先會通過某種切分算法將一個整體的移動應(yīng)用劃分為多個子任務(wù)，這些子任務(wù)有的是必須在本地執(zhí)行，比如用戶交互任務(wù)、設(shè)備IO任務(wù)和外圍設(shè)備接口任務(wù)等，還有一些是可在本地執(zhí)行，也可進行卸載的任務(wù)，它們通常都是數(shù)據(jù)處理型任務(wù)，計算量較大.劃分后的子任務(wù)彼此之間有數(shù)據(jù)交互，但是又能夠獨立執(zhí)行，這是進行細粒度卸載決策的前提條件[18].

Fig. 1 Composition structure diagram of MEC圖1 MEC組成結(jié)構(gòu)圖

假如移動應(yīng)用拆分后的子任務(wù)之間具有依賴關(guān)系，該關(guān)系可以用一個有向圖Loop=(V,E)表示，其中圖的每個節(jié)點vi∈V表示拆分后的子任務(wù)，圖的每條邊表示任務(wù)間的數(shù)據(jù)依賴，例如eij∈E表示任務(wù)vi執(zhí)行完成后會將數(shù)據(jù)傳輸給vj，而vj必須接收該數(shù)據(jù)后才能繼續(xù)往后執(zhí)行[14].如圖2所示，一個移動應(yīng)用拆分后的子任務(wù)集合為V={v1,v2,v3,v4,v5}，其中v1和v5必須在本地設(shè)備執(zhí)行，其余子任務(wù)可以根據(jù)需要進行卸載.同時各子任務(wù)之間用有向線條表示其數(shù)據(jù)依賴，例如v5必須在接受到v2和v4的處理結(jié)果后才能繼續(xù)執(zhí)行.

Fig. 2 Multi-tasking data dependency diagram圖2 多任務(wù)數(shù)據(jù)依賴圖

2.2 問題建模

1) 能耗模型

針對包含智能手機和遠程服務(wù)器等所有計算設(shè)備在一定時間內(nèi)產(chǎn)生的總能耗，本文首先定義第i臺計算設(shè)備的功率模型為

(1)

(2)

總數(shù)量為1+m+n的所有計算設(shè)備在單位時間t內(nèi)產(chǎn)生的總能耗為

(3)

2) 費用模型

用戶獲取遠程服務(wù)器提供的計算資源需要支付相應(yīng)的費用，本文使用基于資源剩余量的動態(tài)價格模型，當(dāng)資源剩余量越少時資源價格越高，此時用戶較傾向于選取單價較低的服務(wù)節(jié)點作為卸載目標，從而在降低用戶花銷的同時提高資源利用率.基于計算資源剩余量的動態(tài)價格模型：

Cost=Costexist+Timeunit×Priceunit×
Ratioused×Rtotal,

(4)

其中,Costexist表示當(dāng)前設(shè)備已經(jīng)產(chǎn)生的費用，Timeunit表示費用計算的單位間隔時間，Priceunit表示單位計算資源所設(shè)定的價格，Ratioused表示當(dāng)前設(shè)備使用的計算資源比率，Rtotal表示當(dāng)前設(shè)備的總計算資源.同時由于本地設(shè)備的計算資源屬于用戶個人所有，不需要作為運營商提供的服務(wù)進行費用計算，因此所有收費設(shè)備(數(shù)量為1+m)的總開銷:

(5)

3) 負載均衡

負載均衡是實現(xiàn)集群中各類資源有效利用和共享的一個重要手段，其主要是為了實現(xiàn)最佳化資源使用、最大化吞吐率、最小化響應(yīng)時間以及避免過載的目的.集群中所有設(shè)備的負載均衡：

(6)

4) 服務(wù)時延

根據(jù)子任務(wù)之間的依賴關(guān)系，一個移動應(yīng)用的服務(wù)時延是指第1個子任務(wù)接收用戶請求的時間Timefirst到最后1個子任務(wù)獲取結(jié)果并執(zhí)行相應(yīng)操作的時間Timeend之間的差值，其服務(wù)時延:

SL=Timeend-Timefirst.

(7)

5) 平均執(zhí)行時間

執(zhí)行時間是指一個子任務(wù)進行數(shù)據(jù)處理所需要花費的時間，當(dāng)子任務(wù)卸載的計算設(shè)備性能越好，則其處理時間越短，在規(guī)定時間內(nèi)能處理的請求就越多.因此卸載決策需要盡可能降低移動應(yīng)用的平均執(zhí)行時間，其中平均執(zhí)行時間:

(8)

其中,subnum表示一個移動應(yīng)用拆分后的子任務(wù)數(shù)量，F(xiàn)TTaski表示第i個子任務(wù)結(jié)束處理的時間，STTaski表示第i個子任務(wù)開始處理的時間，Loop(Taskfirst,Taskend)表示子任務(wù)集合形成的有向圖.

6) 網(wǎng)絡(luò)使用量

網(wǎng)絡(luò)使用量是指所有移動應(yīng)用在規(guī)定時間內(nèi)產(chǎn)生的數(shù)據(jù)傳輸量，該值過高可能導(dǎo)致整個網(wǎng)絡(luò)產(chǎn)生擁塞，進一步降低應(yīng)用程序的處理性能.網(wǎng)絡(luò)使用量：

(9)

其中,appnum表示單位時間內(nèi)所有請求的移動應(yīng)用數(shù)量，TLi表示第i個移動應(yīng)用處理請求所產(chǎn)生的延遲，TSi表示第i個移動應(yīng)用處理請求所產(chǎn)生的總數(shù)據(jù)傳輸量，Timeunit表示設(shè)定的單位時間.

3 深度強化學(xué)習(xí)算法設(shè)計

強化學(xué)習(xí)是一種能在特定場景下通過自學(xué)做出最優(yōu)決策的算法模型，其通過把所有現(xiàn)實問題都抽象為智能體與環(huán)境的互動過程來進行建模.在互動過程中的每個時間步，智能體都收到環(huán)境的狀態(tài)并選擇相應(yīng)的響應(yīng)動作，然后在下一個時間步，智能體根據(jù)環(huán)境的反饋獲得一個獎勵值和新的狀態(tài).強化學(xué)習(xí)根據(jù)獲得的獎勵不斷學(xué)習(xí)知識以適應(yīng)環(huán)境，其所有智能體的目標都是最大化預(yù)期累積獎勵或在所有時間步獲得的預(yù)期獎勵之和.雖然強化學(xué)習(xí)具有很多優(yōu)勢，但同時該方法缺乏可擴展性，并且本質(zhì)上局限于相當(dāng)?shù)途S的問題.這些限制的存在是因為強化學(xué)習(xí)算法與其他算法具有相同的內(nèi)存復(fù)雜度、計算復(fù)雜度以及機器學(xué)習(xí)算法中的樣本復(fù)雜度.

為解決強化學(xué)習(xí)難以處理的決策問題，深度強化學(xué)習(xí)將深度學(xué)習(xí)的感知能力和強化學(xué)習(xí)的決策能力相結(jié)合，依靠強大的函數(shù)逼近和深度神經(jīng)網(wǎng)絡(luò)的表示學(xué)習(xí)性質(zhì)來解決具有高維度狀態(tài)空間和動作空間的環(huán)境問題[21].下面通過結(jié)合實際移動計算環(huán)境構(gòu)建MDP模型，并針對深度Q學(xué)習(xí)網(wǎng)絡(luò)(deep Q-Learing network, DQN)算法進行改進，以此解決MEC中的任務(wù)卸載問題.

3.1 MDP模型

1) 狀態(tài)空間

為了綜合考慮MEC中子任務(wù)與服務(wù)器資源之間的特性，本文定義在時間步t的狀態(tài)空間為St=(Cin,Nup,M,Cout,Ndo,U1,U2,…,U2+m).其中，Cin表示當(dāng)前子任務(wù)所需的輸入數(shù)據(jù)量；Nup表示該子任務(wù)用于接收數(shù)據(jù)所能使用的上傳帶寬；M表示該子任務(wù)部署所需的CPU資源；Cout表示當(dāng)前子任務(wù)計算產(chǎn)生的結(jié)果數(shù)據(jù)量；Ndo表示同一子任務(wù)用于提供結(jié)果下載所能使用的下行帶寬；Ui表示在時間步t第i個計算設(shè)備的CPU利用率,同時為了保證子任務(wù)只能選擇在本地移動終端設(shè)備或者遠程服務(wù)器上執(zhí)行，因此對于該子任務(wù)只需考慮2+m個計算設(shè)備，其中包含1個云數(shù)據(jù)中心、1個本地設(shè)備和m個邊緣服務(wù)器.

2) 動作空間

3) 獎勵函數(shù)

本文將綜合考慮MEC中所有設(shè)備的能耗、費用以及負載均衡3方面因素來評估卸載決策的優(yōu)劣，同時為了解決異構(gòu)計算設(shè)備因性能差異在每一個時間步所造成的獎勵值偏差，本文利用z-score標準化方法分別對能耗、費用以及負載均衡進行正規(guī)化，當(dāng)數(shù)據(jù)序列為{x1,x2,…,xnum}時，其計算為

(10)

分別將式(2)(4)(6)與式(10)進行結(jié)合可以求出各個計算設(shè)備的能耗、費用以及負載均衡正規(guī)化值，則獎勵函數(shù)為

(11)

根據(jù)以上構(gòu)建的MDP模型，結(jié)合深度強化學(xué)習(xí)的MEC任務(wù)卸載策略的偽代碼如算法1所示：

算法1.結(jié)合深度強化學(xué)習(xí)的任務(wù)卸載算法.

輸入：包含一個移動設(shè)備、多個邊緣服務(wù)器和一個云數(shù)據(jù)中心的集合hostList、所有需要卸載的任務(wù)集合taskList;

輸出：對任務(wù)集合taskList的卸載決策.

① 基于taskList初始化卸載集合offloadList;

② 基于hostList初始化動作空間A;

③ For任務(wù)T∈taskList

④ 獲取任務(wù)T的輸入數(shù)據(jù)量Cin、上傳帶寬Nup、所需CPU資源M、輸出數(shù)據(jù)量Cout、下行帶寬Ndo;

⑤ 獲取hostList在時間步t的CPU利用率集合CPUList;

⑥ 構(gòu)建時間步t的狀態(tài)空間St;

⑦ 根據(jù)狀態(tài)St選擇動作at∈A，其中at表示選擇設(shè)備h∈hostList;

⑧ If任務(wù)T能夠放置在設(shè)備h上

⑩ 在offloadList中添加鍵值對T,h;

3.2 算法優(yōu)化

1) LSTM網(wǎng)絡(luò)

(12)

其中,st+1表示狀態(tài)st在時間步t采取動作at后的下一狀態(tài)，rt+1是采取動作at后的即時獎勵，而a′為狀態(tài)st+1能夠采取的所有動作；γ為價值累積過程中的折扣系數(shù)，決定了未來回報相對于當(dāng)前回報的重要程度；α為學(xué)習(xí)速率，該值越大，則保留之前訓(xùn)練的效果就越少.

DQN不僅利用函數(shù)擬合改進了Q-Learning算法的搜索速度，同時還通過增加經(jīng)驗池和目標網(wǎng)絡(luò)提升了其多樣性和穩(wěn)定性.其中經(jīng)驗池是將每個時間步智能體與環(huán)境交互得到的轉(zhuǎn)移樣本(st,at,rt,st+1)儲存到回放記憶單元，當(dāng)進行訓(xùn)練時隨機抽取一定數(shù)量的樣本來解決數(shù)據(jù)之間的相關(guān)性及非靜態(tài)分布問題；目標網(wǎng)絡(luò)是指使用另一個網(wǎng)絡(luò)TargetNet生成訓(xùn)練過程的目標Q值，該網(wǎng)絡(luò)的結(jié)構(gòu)與DQN的神經(jīng)網(wǎng)絡(luò)MainNet保持一致，每經(jīng)過C輪迭代，將MainNet的參數(shù)復(fù)制給TargetNet.因此通過在一段時間內(nèi)保持2個網(wǎng)絡(luò)參數(shù)的差異性，以此利用當(dāng)前Q值和目標Q值的差值來計算損失函數(shù)，隨后使用隨機梯度下降等方法反向更新MainNet網(wǎng)絡(luò)的參數(shù).DQN算法的損失函數(shù)計算為

(13)

在MEC的真實環(huán)境中，由于問題的復(fù)雜性和感知的局限性,系統(tǒng)很難直接獲取到當(dāng)前時間步所處的精確狀態(tài).假設(shè)系統(tǒng)的狀態(tài)信息不能直接觀測得到,是部分可知的，因而通常需要使用POMDP對只有不完全狀態(tài)信息的系統(tǒng)建模,依據(jù)當(dāng)前的不完全狀態(tài)信息做出決策[22].POMDP可以用一個六元組(S,A,T,R,Z,O)描述.其中，S表示系統(tǒng)所處環(huán)境的狀態(tài)集合，其都是部分可觀測的；A表示動作的有限集合；Z表示觀測值的有限集合；T:S×A→π(S)是狀態(tài)轉(zhuǎn)移函數(shù)；R:S×A→R是獎勵函數(shù)；O:S×A→π(Z)是狀態(tài)和系統(tǒng)所做動作給出的觀測函數(shù).通常情況下，DQN只能在觀測值z∈Z能夠很好地反映真實環(huán)境狀態(tài)s∈S的情況下才能取得較好結(jié)果，因此其很難直接用于解決實際的MEC問題.

ht+1=LSTM(ht,zt,at).

(14)

Fig. 3 DRQN algorithm training flow chart of MainNet圖3 DRQN算法MainNet訓(xùn)練流程圖

2) 事后經(jīng)驗回放

為提高深度強化學(xué)習(xí)算法的泛化性能，DQN算法通過經(jīng)驗回放對樣本數(shù)據(jù)進行存儲，隨后利用隨機采樣更新深度神經(jīng)網(wǎng)絡(luò)參數(shù)，以此實現(xiàn)數(shù)據(jù)之間的獨立同分布以及降低其關(guān)聯(lián)性，解決了經(jīng)驗數(shù)據(jù)的相關(guān)性和非平穩(wěn)分布問題，提高了數(shù)據(jù)利用率并且降低了更新網(wǎng)絡(luò)參數(shù)產(chǎn)生的方差.深度強化學(xué)習(xí)在解決實際問題時由于大部分情況下無法得到有效反饋，其模型很難學(xué)習(xí)到可用策略，造成求解復(fù)雜問題的決策無法收斂.因此本文希望在經(jīng)驗回放的基礎(chǔ)上結(jié)合后見之明的思想，提出利用事后經(jīng)驗回放解決MEC中無法獲取有效反饋的問題.

HER是用來解決反饋獎勵稀疏的一種樣本數(shù)據(jù)存儲結(jié)構(gòu)，其通過漸進式學(xué)習(xí)方法調(diào)整任務(wù)目標以此提高模型的策略探索能力[23].現(xiàn)假設(shè)智能體將經(jīng)歷從初始狀態(tài)s0到達目標狀態(tài)g的學(xué)習(xí)過程，但最終在學(xué)習(xí)結(jié)束時其終止狀態(tài)為g′，則生成的真實學(xué)習(xí)軌跡可以表示為

{(s0,g,a0,r0,s1),(s1,g,a1,r1,s2),…,
(sn,g,an,rn,g′)},

其中,an表示智能體在時間步n時采取的動作，rn表示智能體在時間步n時獲取的獎勵.基于以上假設(shè)，HER將目標狀態(tài)g替換成終止狀態(tài)g′，以此表示智能體在該學(xué)習(xí)過程中達成目標并獲取到有效反饋，其生成的想象學(xué)習(xí)軌跡可以表示為

{(s0,g′,a0,r0,s1),(s1,g′,a1,r1,s2),…,
(sn,g′,an,rn,g′)}.

因為每次迭代過程中模型的學(xué)習(xí)目標都是不同的，因此所選取的動作也將發(fā)生變化，則在時間步t時根據(jù)當(dāng)前狀態(tài)st和目標狀態(tài)g得到的動作計算為

at=π(st,g).

(15)

相應(yīng)的即時獎勵計算為

rt=Reward(st,at,g).

(16)

最后將根據(jù)目標狀態(tài)g計算得到的經(jīng)驗存入經(jīng)驗池中，其中基于HER的每一條經(jīng)驗將由5部分元素組成：當(dāng)前狀態(tài)s、動作a、及時獎勵r、下一狀態(tài)s′、當(dāng)前目標g.同時在訓(xùn)練過程中，基于HER的經(jīng)驗回放可以通過目標采樣策略生成想象目標g′，并結(jié)合狀態(tài)st和動作at來計算新的獎勵并將其存入到經(jīng)驗池中，以此生成一些額外的訓(xùn)練經(jīng)驗，其計算為

r′=Reward(st,at,g′),

(17)

其中本文采用的目標采樣策略為future，即對時間步t以后的狀態(tài)進行隨機采樣，選取k個狀態(tài)作為新的想象目標集合.HER充分利用了人類從失敗經(jīng)歷中獲取有用經(jīng)驗的思想，通過想象軌跡在學(xué)習(xí)過程中達成想象目標而獲取有效獎勵，以此保證生成的任何策略都能利用反饋獎勵進行學(xué)習(xí).其中智能體首先在靠近初始狀態(tài)的較小區(qū)域到達想象目標狀態(tài)，隨后逐漸向周圍區(qū)域進行探索，利用漸進式學(xué)習(xí)滿足難度逐漸增加的任務(wù)目標，最終使模型學(xué)習(xí)到實際目標狀態(tài).基于HER的訓(xùn)練過程代碼如算法2所示：

算法2.基于HER的深度強化學(xué)習(xí).

輸入：用于目標重采樣的策略RSample、獎勵函數(shù)Reward().

① 初始化回放空間D;

② For迭代次數(shù)episode=1,2,…,M

③ 對目標g和初始狀態(tài)s0進行抽樣;

④ For迭代次數(shù)t=0,1,…,T-1

⑤ 利用式(15)選擇動作at；

⑥ 執(zhí)行動作at然后獲得新狀態(tài)st+1；

⑦ End For

⑧ For迭代次數(shù)t=0,1,…,T-1

⑨ 利用式(16)計算即時獎勵rt;

⑩ 將轉(zhuǎn)移樣本(st,at,rt,st+1,g)存入D;

3.3 算法流程

Fig. 4 HERDRQN algorithm flow chart圖4 HERDRQN算法流程圖

圖4是基于LSTM和HER改進的深度強化學(xué)習(xí)算法HERDRQN流程圖.該算法首先將每個時間步智能體與環(huán)境交互得到的轉(zhuǎn)移樣本(zt,at,rt,zt+1)儲存到HER記憶單元，隨后在訓(xùn)練過程中利用future策略對樣本進行隨機采樣，將其進行拆分后分別用于訓(xùn)練當(dāng)前值網(wǎng)絡(luò)和目標值網(wǎng)絡(luò)的權(quán)重，其中這2個網(wǎng)絡(luò)的結(jié)構(gòu)一致，都是由一個單隱層的LSTM網(wǎng)絡(luò)和2個全連接層組成，其中最后一個全連接層的節(jié)點數(shù)為動作空間大小.為保證在MEC真實環(huán)境中獲取到更精確的狀態(tài)，當(dāng)前值網(wǎng)絡(luò)和目標值網(wǎng)絡(luò)通過LSTM網(wǎng)絡(luò)的長時間序列觀測值對當(dāng)前時間步的狀態(tài)st和下一時間步的狀態(tài)st+1進行推導(dǎo)，然后利用全連接層分別求出2個網(wǎng)絡(luò)對應(yīng)狀態(tài)的Q值，根據(jù)式(13)求出誤差并計算梯度反向更新當(dāng)前值網(wǎng)絡(luò)的權(quán)重.另外基于LSTM改進的DRQN算法流程與HERDRQN算法流程在網(wǎng)絡(luò)結(jié)構(gòu)上是一致的，區(qū)別在于兩者采用的記憶單元方法存在不同，其中DRQN算法使用的是回放記憶單元，而HERDRQN算法使用的是事后經(jīng)驗回放單元.

圖5是基于HER改進的深度強化學(xué)習(xí)算法HERDQN流程圖.與HERDRQN算法的流程相比，HERDQN算法的差異在于當(dāng)前值網(wǎng)絡(luò)和目標值網(wǎng)絡(luò)使用的是3個全連接層，其將LSTM層替換為一個具有256個節(jié)點的全連接層，同時當(dāng)前環(huán)境的觀測值被直接作為狀態(tài)進行訓(xùn)練，因此該算法在狀態(tài)信息只能部分可知的情況下表現(xiàn)相對較差.另外與DRQN算法和HERDRQN算法的差異類似，DQN算法與HERDQN算法的網(wǎng)絡(luò)結(jié)構(gòu)都是3個全連接層，但DQN算法使用的是回放記憶單元，HERDQN算法使用的是事后經(jīng)驗回放單元.

Fig. 5 HERDQN algorithm flow chart圖5 HERDQN算法流程圖

4 MEC任務(wù)卸載仿真實驗

4.1 仿真環(huán)境

本文采用iFogSim對基于MEC的任務(wù)卸載問題進行仿真實驗[24]，通過比較各算法在大規(guī)模異構(gòu)集群中的能耗、費用、負載均衡、服務(wù)時延、平均執(zhí)行時間以及網(wǎng)絡(luò)使用量等來反映卸載決策的優(yōu)劣，其中實現(xiàn)的算法包括基于本地設(shè)備優(yōu)先放置的策略Mobile、基于邊緣服務(wù)器優(yōu)先放置的策略Edge、基于深度強化學(xué)習(xí)的策略DQN、基于LSTM改進的深度強化學(xué)習(xí)策略DRQN、基于HER改進的深度強化學(xué)習(xí)策略HERDQN以及基于LSTM和HER改進的深度強化學(xué)習(xí)策略HERDRQN.仿真實驗?zāi)M的設(shè)備集群主要包含1個云數(shù)據(jù)中心、60個邊緣服務(wù)器和數(shù)量不等的移動終端設(shè)備，其中所有邊緣服務(wù)器將平均劃分到10個不同的區(qū)域，并且每個移動終端設(shè)備在同一時間內(nèi)只能發(fā)送一個應(yīng)用卸載請求.本文參考SPEC(standard performance evaluation corporation)設(shè)置了相應(yīng)的仿真設(shè)備配置及平均性能功耗比，該值越大表明設(shè)備在相同性能下能耗越少，其詳細信息如表1所示.

為了模擬移動應(yīng)用拆分成不同子任務(wù)后的卸載流程，本文根據(jù)參考文獻[25]構(gòu)建了一個網(wǎng)絡(luò)購物的子任務(wù)依賴關(guān)系，如圖6所示，該應(yīng)用主要是由edge,front end,login,accounts,orders,shipping,catalogue,cart和payment等子任務(wù)組成，其中edge必須在移動設(shè)備上執(zhí)行，而其余子任務(wù)則可以根據(jù)決策選擇是否卸載.網(wǎng)絡(luò)購物應(yīng)用通常對卸載決策的要求非常高，其一方面需要將高計算量的數(shù)據(jù)處理模塊卸載到遠程服務(wù)器上執(zhí)行，盡可能降低移動設(shè)備能耗；另一方面計算模塊需要盡可能靠近數(shù)據(jù)源，以此降低模塊之間數(shù)據(jù)傳輸所造成的延遲.如表2所示，本文通過CPULength和NWLength這2個變量來表示任務(wù)依賴對計算復(fù)雜度和數(shù)據(jù)傳輸量的要求，當(dāng)CPULength越大并且NWLength越小時，則表示該任務(wù)更偏向于高計算量需求，反之則偏向于數(shù)據(jù)傳輸需求.同時本文對于所有深度強化學(xué)習(xí)算法模型的參數(shù)進行統(tǒng)一設(shè)置以確保訓(xùn)練結(jié)果的公平性，其中定義深度強化學(xué)習(xí)的記憶空間大小M=100 000，優(yōu)化算法SGD的學(xué)習(xí)速率α=0.005，批學(xué)習(xí)大小BatchSize=32，目標網(wǎng)絡(luò)參數(shù)的更新周期C=50，折扣系數(shù)γ=0.9；對于基于LSTM改進的深度強化學(xué)習(xí)算法，設(shè)置其LSTM網(wǎng)絡(luò)層的時間窗口為10；對于基于HER改進的深度強化學(xué)習(xí)算法，其將型號為DL360 Gen10的邊緣服務(wù)器目標利用率設(shè)置為100%，因為該設(shè)備在所有邊緣服務(wù)器中的平均性能功耗比最大，而其余設(shè)備的目標利用率設(shè)置為0%，以此組成的所有設(shè)備利用率數(shù)組作為初始狀態(tài).

Table 1 Detailed Configuration Table of Computing Devices表1 計算設(shè)備詳細配置表

Fig. 6 Subtask dependence graph for online shopping圖6 網(wǎng)絡(luò)購物子任務(wù)依賴圖

Tuple TypeCPU LengthN∕W LengthREQUEST30001000BROWSE10001000LOG_B300100IDENTIFY500500LOG_U300100SELECT1000500BUY50001000SEE500500ADD500200PAY500500SEND5001000LOG_O300100

4.2 實驗結(jié)果分析

為了反映移動應(yīng)用在不同時間段的資源利用率變化情況，本文使用Google Cluster Trace數(shù)據(jù)集來模擬各模塊利用率隨時間所發(fā)生的變化[26].另外為了保證各深度強化學(xué)習(xí)算法生成的策略高效可用，本文首先從Google數(shù)據(jù)集中選擇1 000個應(yīng)用來對各神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練，隨后選取其他數(shù)據(jù)對訓(xùn)練后的網(wǎng)絡(luò)模型進行檢驗，以此比較各策略的泛用性和高效性.

Fig. 7 Resource loss graph generated by each algorithm in task offloading圖7 各算法在任務(wù)卸載中所產(chǎn)生的資源損耗圖

圖7是各算法在任務(wù)卸載中所產(chǎn)生的資源損耗圖.由圖可知隨著應(yīng)用數(shù)量的增長，各算法所生成的卸載策略在能耗、費用、負載均衡、延遲、網(wǎng)絡(luò)使用量以及執(zhí)行時間等方面大致呈遞增關(guān)系，其中基于Mobile算法的卸載策略在費用和延遲上都能取得很好的效果，而在其余方面則表現(xiàn)較差，這主要是因為Mobile算法是將子任務(wù)優(yōu)先卸載到本地設(shè)備上執(zhí)行，當(dāng)資源不足后再逐步向上層設(shè)備卸載，因此該算法在網(wǎng)絡(luò)層面具有更低的延遲；另外由于本地設(shè)備屬于用戶個人所有，處理任務(wù)時不需要支付相應(yīng)的計算費用，因此該算法產(chǎn)生的費用很低.同時根據(jù)表1中的數(shù)據(jù)可知移動設(shè)備的處理能力和平均性能功耗都要遠小于遠程服務(wù)器，所以移動設(shè)備處理子任務(wù)會產(chǎn)生更高的執(zhí)行時間和能耗；另外基于Edge算法的卸載策略在負載均衡方面表現(xiàn)較好，在其余方面則表現(xiàn)一般，主要原因是Edge算法將子任務(wù)優(yōu)先卸載到邊緣服務(wù)器集群中，這造成所有邊緣服務(wù)器的資源利用率都能維持在一個很高的水平，使其負載均衡的計算結(jié)果最低.

DQN算法、DRQN算法、HERDQN算法和HERDRQN算法都是利用深度強化學(xué)習(xí)自動從數(shù)據(jù)中生成相應(yīng)的卸載策略，由圖7中的結(jié)果可知隨著應(yīng)用數(shù)量的增長，DQN算法和DRQN算法生成的卸載策略在網(wǎng)絡(luò)使用量方面表現(xiàn)較優(yōu)，在其余方面則表現(xiàn)一般，但是DRQN算法在綜合性能上要優(yōu)于DQN算法.當(dāng)應(yīng)用數(shù)量較多時，HERDQN算法和HERDRQN算法生成的策略在能耗、費用、負載和延遲上都要優(yōu)于DQN算法和DRQN算法，其中HERDRQN算法的結(jié)果是所有深度強化學(xué)習(xí)算法中表現(xiàn)最好的.

為驗證異構(gòu)設(shè)備中CPU利用率與不同資源損耗之間的關(guān)系，本文利用各算法生成的決策對120個應(yīng)用進行卸載處理，根據(jù)表1中各設(shè)備類型的平均性能功耗比分析異構(gòu)設(shè)備在不同CPU利用率下的數(shù)量分布對資源損耗的影響.表3是各算法根據(jù)CPU利用率對異構(gòu)設(shè)備進行分類的詳細數(shù)據(jù)，由表3可知當(dāng)CPU利用率在[80%,100%]的范圍時，HERDRQN算法所生成的策略傾向于將子任務(wù)卸載到型號為DL360 Gen10的邊緣服務(wù)器設(shè)備，同時對于型號為RX350 S7和DL325 Gen10的邊緣服務(wù)器設(shè)備則是所有深度強化學(xué)習(xí)算法中使用最少的.

Table 3 Number Distribution Table of Heterogeneous Devices with Different CPU Utilization Rates表3 各算法在不同CPU利用率下的異構(gòu)設(shè)備數(shù)量分布表

由表1可知在相同功耗下，DL360 Gen10和RX350 S7分別是性能最好和最差的邊緣服務(wù)器型號，同時該算法也將部分子任務(wù)卸載到平均性能功耗比很低但資費為0的本地設(shè)備，因此HERDRQN算法在能耗、費用、負載和延遲等方面都具有很好的性能.除此之外，結(jié)合表3和表4可知：由于Mobile算法對移動設(shè)備的CPU利用率很高，因此其卸載決策產(chǎn)生的費用最低但能耗最高；Edge算法將所有子任務(wù)均勻卸載到所有邊緣服務(wù)器上，因此其卸載決策對邊緣服務(wù)器的CPU利用率都保持在20%～80%之間，保證了負載均衡的性能；相比于DQN算法，DRQN算法和HERDQN算法在CPU利用率為[80%,100%]時對平均性能功耗比最低的邊緣服務(wù)器使用較少，因此這2種算法在能耗方面都要優(yōu)于DQN算法.

Table 4 Total Number Table of Heterogeneous Devices

4.3 實機驗證實驗

該部分實驗主要用于驗證各算法在實際MEC卸載任務(wù)中的性能表現(xiàn).整個測試平臺共使用3臺服務(wù)器和2臺筆記本電腦用于實驗?zāi)M，其中2臺服務(wù)器用于模擬不同地理位置的邊緣服務(wù)節(jié)點，1臺服務(wù)器用于模擬云數(shù)據(jù)中心，而2臺筆記本電腦則用于模擬用戶的移動設(shè)備.所有服務(wù)器均采用Ubuntu 16.04.6 LTS操作系統(tǒng)、型號為Intel Xeon E5-2660的16核處理器、2張千兆網(wǎng)卡和32 GB內(nèi)存、并且都安裝了Docker 18.09.2，CRIU(CheckpointRestore In Userspace) 3.10，sysstat 12.1.1.

Fig. 8 Energy consumption comparison chart of each algorithm in test environment圖8 各算法在測試環(huán)境中的能耗比較圖

Fig. 9 Cost comparison chart of each algorithm in test environment圖9 各算法在測試環(huán)境中的費用比較圖

Fig. 10 Delay comparison chart of each algorithm in test environment圖10 各算法在測試環(huán)境中的延遲比較圖

5 結(jié) 論

本文首先提出利用深度強化學(xué)習(xí)解決大規(guī)模異構(gòu)MEC中具有多服務(wù)節(jié)點和移動終端任務(wù)內(nèi)部具有多依賴關(guān)系的卸載問題，然后將各算法生成的卸載策略在邊緣計算仿真平臺iFogSim上進行實驗，最后通過比較能耗、費用、負載、延遲、網(wǎng)絡(luò)使用量以及平均執(zhí)行時間等多方面因素來驗證各算法策略的優(yōu)劣.根據(jù)比較各算法的多方面結(jié)果可知，基于LSTM網(wǎng)絡(luò)和HER改進的HERDRQN算法在能耗、費用、負載均衡和延遲等方面都具有很好的結(jié)果.另外本文利用各算法策略對一定數(shù)量的應(yīng)用進行卸載，通過比較不同CPU利用率下的異構(gòu)設(shè)備數(shù)量分布來驗證其與各資源損耗之間的關(guān)系，以此證明HERDRQN算法生成的策略在解決MEC任務(wù)卸載問題中的科學(xué)性和有效性.