移動邊緣計算中多約束下的任務(wù)卸載和資源分配算法

童 釗，葉 鋒，劉碧籃，鄧小妹，梅 晶，劉 宏

(湖南師范大學信息科學與工程學院，湖南 長沙 410012)

1 引言

隨著5G網(wǎng)絡(luò)時代的到來，5G通信技術(shù)正在逐步走向標準化，物聯(lián)網(wǎng)IoT(Internet of Things)[1]、車載網(wǎng)[2]日益廣泛地應(yīng)用于人們的日常生活中。相應(yīng)地，物聯(lián)網(wǎng)終端設(shè)備、車載網(wǎng)終端設(shè)備的數(shù)量顯著增加。各種終端設(shè)備的增多，使得各種數(shù)據(jù)呈現(xiàn)爆炸式的增長。傳統(tǒng)的云計算存儲和計算平臺雖然能較好地對大數(shù)據(jù)進行存儲、分析與處理，但是隨著各種數(shù)據(jù)的增多，尤其是云中心遠端，靠近數(shù)據(jù)源端的數(shù)據(jù)激增，再加上用戶對數(shù)據(jù)安全性的要求和對用戶服務(wù)質(zhì)量QoS(Quality of Service)要求的提高，傳統(tǒng)的以云計算為基礎(chǔ)的分析、處理平臺面臨著巨大的挑戰(zhàn)。

云中心通常離用戶、終端設(shè)備比較遠，終端設(shè)備產(chǎn)生的實時數(shù)據(jù)上傳到遠端云平臺上分析、處理，完成之后再將結(jié)果沿相同的傳輸路線返回到終端設(shè)備，這一過程會產(chǎn)生一定的傳輸時延。同時，大量的數(shù)據(jù)傳輸也會增加網(wǎng)絡(luò)帶寬的傳輸負擔，使得數(shù)據(jù)傳輸效率和處理速率降低。加上傳輸?shù)皆破脚_的大量任務(wù)會使得任務(wù)等待隊列過長，導致任務(wù)的響應(yīng)時間增長，從而影響了用戶的體驗質(zhì)量。并且任務(wù)響應(yīng)時間過長，可能會使得數(shù)據(jù)受到攻擊的概率增大。綜上所述，基于傳統(tǒng)的云計算的數(shù)據(jù)處理架構(gòu)無法很好地滿足低延遲、高實時、高可靠的業(yè)務(wù)需求。為了緩解海量數(shù)據(jù)傳輸帶來的網(wǎng)絡(luò)負荷問題和滿足用戶低延遲、高實時、高可靠的業(yè)務(wù)請求，2014年國際標準組織[5]提出了一種新興的計算方式──移動邊緣計算MEC(Mobile Edge Computing)[3,4]。Gartner將移動邊緣計算定義為“分布式計算拓撲的一部分，其中信息處理位于邊緣附近——事物和人在此處生成或消費該信息”[6]。也就是說，將云中心的部分存儲、計算資源轉(zhuǎn)移到網(wǎng)絡(luò)邊緣，更靠近數(shù)據(jù)源的地方，能夠更好地滿足低延遲、高實時、高可靠的業(yè)務(wù)請求。

邊緣計算提出至今，受到了業(yè)界研究學者的廣泛關(guān)注，不少研究學者對邊緣計算展開了深入研究。研究成果表明，邊緣計算能夠較好地解決云計算不能有效處理資源分配的問題。例如，網(wǎng)絡(luò)帶寬負擔過重、延時較長、能耗較高等。但是，由于研究時間不長，很多技術(shù)不成熟，考慮問題涉及面也不是很全面。因此，邊緣計算的研究仍然存在不少問題等待進一步探索。如目前不少研究并沒有考慮數(shù)據(jù)安全性、計算節(jié)點安全性；邊緣服務(wù)器該如何部署；什么類型的任務(wù)該卸載到邊緣服務(wù)器上執(zhí)行；以及本地端、邊緣服務(wù)器端的資源該如何分配；本地端能源有限性等問題。本文著重考慮了能耗和安全性這2個問題，并在此基礎(chǔ)上，為了降低系統(tǒng)能耗、更好地滿足用戶的QoS請求，結(jié)合深度強化學習中的Double DQN(Double Deep-Q-Network)算法，在多約束條件下提出了一種有效的資源分配[7]和任務(wù)卸載算法DDQNOA(Double DQN Offloading Algorithm)。實驗結(jié)果表明，與幾種經(jīng)典算法相比，該算法能夠提高任務(wù)卸載成功率、任務(wù)執(zhí)行成功率，有效降低本地端能耗。為解決MEC環(huán)境下的任務(wù)卸載和資源分配提供了一種新的思路。

2 相關(guān)工作

云計算距今已有十多年的發(fā)展歷史，其研究、發(fā)展歷程中最至關(guān)重要的一個問題就是任務(wù)調(diào)度[8 - 10]。在MEC環(huán)境中，為了更好地滿足用戶的QoS請求和提升用戶體驗的質(zhì)量，如何高效地進行任務(wù)卸載(計算卸載)是目前被廣泛研究的熱點問題之一。任務(wù)卸載是指將在資源有限的終端設(shè)備上不能夠有效處理的任務(wù)上傳到指定無線區(qū)域內(nèi)的邊緣服務(wù)器上執(zhí)行，任務(wù)在邊緣服務(wù)器上執(zhí)行完成之后，再將計算結(jié)果返回到原來的終端設(shè)備的過程。有效的任務(wù)卸載與資源分配，既要保證用戶的QoS請求，又要最小化系統(tǒng)的能耗，保證服務(wù)提供商的利益。因此，該問題是一個典型的NP-hard問題[11]。

目前，MEC研究的任務(wù)卸載策略主要考慮了能耗效率、低延遲、高實時、邊緣存儲等方面的問題。例如，Tao等人[12]為了研究MEC中具有性能保障的能耗問題，針對移動用戶對低能耗和低延時的需求，提出了一種MEC中能耗最小化問題，并利用KKT(Karush-Kuhn-Tucker)條件求解優(yōu)化該問題。數(shù)值仿真結(jié)果表明，該方法在能源消耗和延遲性能方面優(yōu)于本地計算和完全卸載方法。為了使系統(tǒng)能源最小化，從而最大化移動服務(wù)提供商MSP(Mobile Service Provider)的利潤。Wang等人[13]提出了一個統(tǒng)一的MSP性能權(quán)衡框架，并利用Lyapunov技術(shù)對框架進行了優(yōu)化，設(shè)計了VariedLen算法求解優(yōu)化該問題。仿真結(jié)果表明，該算法可以在保證系統(tǒng)穩(wěn)定性和低擁塞的前提下，使MSP平均利潤達到最優(yōu)水平。為了節(jié)省系統(tǒng)能耗，Guo等人[14]在同時考慮系統(tǒng)通信和計算資源的情況下，提出了一種多用戶MEC系統(tǒng)的節(jié)能資源配置算法。在該研究中建立了2個高效的計算模型，并在此基礎(chǔ)上優(yōu)化通信和計算資源的分配，利用Johnson’s算法求解資源優(yōu)化問題，使得2個模型的總體加權(quán)和能耗最小化。數(shù)值仿真結(jié)果表明，該算法明顯優(yōu)于經(jīng)典的基準算法。同樣，為了提高系統(tǒng)的能源效率，在給定任務(wù)完成時間約束下，Wang等人[15]提出了CRAN和MEC聯(lián)合能源最小化和資源分配問題，并將該問題轉(zhuǎn)化為非凸優(yōu)化問題，利用迭代算法求解該優(yōu)化問題，使得2種能源加權(quán)和最小化。仿真結(jié)果表明，該方法能夠提高系統(tǒng)性能，節(jié)約能源。Zhu等人[16]考慮了一個多移動用戶、多異構(gòu)邊緣服務(wù)器的MEC場景，在移動設(shè)備電池有限和嚴格的任務(wù)完成時間約束下，提出了一個MEC系統(tǒng)具有完成時間感知的能耗最小化問題，并利用2種近似算法求解該優(yōu)化問題。最終的理論分析和仿真結(jié)果表明了該方法的有效性。上述這些方法在一定程度上能夠很好地降低MEC系統(tǒng)的能耗，但是這些方法優(yōu)化目標都比較單一，只考慮了能耗問題，沒有考慮任務(wù)卸載的效率。為了更好地體現(xiàn)MEC任務(wù)卸載框架的性能，任務(wù)卸載成功率也是另一個值得考慮的優(yōu)化目標。

Le等人[17]考慮了一個多用戶的MEC卸載系統(tǒng)，目標是最小化用戶提交的任務(wù)的完成時間。該系統(tǒng)考慮了時分多址和頻分多址2種不同的無線信道接入方案，針對每一種接入方案都提出了相應(yīng)的聯(lián)合優(yōu)化問題，并利用二分搜索方法求解相應(yīng)的優(yōu)化問題。仿真結(jié)果表明，該方法具有較好的卸載性能，能夠最小化任務(wù)的完成時間。為了更好地滿足用戶的QoS需求和提高MEC系統(tǒng)的效率，Kan等人[18]同時兼顧了無線資源和MEC服務(wù)器的計算資源，在各種不同的任務(wù)延遲的約束條件下，提出了一種成本最小化方案，并利用啟發(fā)式算法進行優(yōu)化。數(shù)值仿真結(jié)果表明，該算法能夠提高用戶的QoS需求。為了最大限度地降低MEC系統(tǒng)任務(wù)卸載請求的拒絕率，Li等人[19]在網(wǎng)絡(luò)資源和計算資源的約束下，設(shè)計了一個有效的卸載控制框架，并提出了一種三層啟發(fā)式算法優(yōu)化該問題。仿真實驗驗證了該方法的有效性，能夠有效降低任務(wù)卸載請求的拒絕率。Liu等人[20]研究了任務(wù)卸載到邊緣服務(wù)器時的延遲和可靠性之間的權(quán)衡問題。該問題主要是為了優(yōu)化任務(wù)卸載延遲和任務(wù)卸載成功率，作者將該問題構(gòu)造為一個非凸優(yōu)化問題，并通過啟發(fā)式算法求解該問題。數(shù)值仿真結(jié)果表明，該方法在延遲和可靠性之間取得了很好的均衡?？梢缘弥?，這些方法在一定程度上都能夠有效地提高MEC系統(tǒng)的性能，但是上述所有的方法都忽視了任務(wù)的安全屬性和計算節(jié)點的安全性，這是有待進一步改進的，因為保證數(shù)據(jù)的安全至關(guān)重要，數(shù)據(jù)的安全性是一個信息時代不可忽視的問題。

基于對上述工作的考量，本文考慮了一個多用戶、多移動用戶設(shè)備UE(User Equipment)、多異構(gòu)邊緣服務(wù)器的MEC場景。為了更好地滿足用戶的QoS要求，不僅考慮了硬件資源的約束、各UE能源的有限性，還引入了任務(wù)的完成時間和安全性約束，并結(jié)合具有自適應(yīng)性的深度強化學習算法，提出了一種多約束條件下的任務(wù)卸載和資源分配算法。實驗結(jié)果表明了該算法的有效性，能夠保證用戶的QoS請求。

3 系統(tǒng)模型

本文考慮了一個多用戶、多UE、單基站BS(Base Station)、多異構(gòu)邊緣服務(wù)器的移動邊緣計算場景，如圖1所示。當有任務(wù)生成時，用戶的任務(wù)請求首先提交到某一UE設(shè)備上。然后，根據(jù)一定的任務(wù)卸載策略判定該任務(wù)是否在此UE上執(zhí)行，也就是判定該任務(wù)是否在本地端執(zhí)行。若根據(jù)策略判定該任務(wù)能夠在此UE上有效執(zhí)行，那么該任務(wù)就不必經(jīng)無線信道卸載到邊緣服務(wù)器上執(zhí)行。反之，任務(wù)將從此UE卸載到某一邊緣服務(wù)器上執(zhí)行，執(zhí)行完成之后，結(jié)果將被返回到原UE上。

Figure 1 Model of mobile edge computing system圖1 移動邊緣計算系統(tǒng)的模型

3.1 場景描述

本文考慮的MEC模型中，假設(shè)用戶的數(shù)量為n,用戶提交任務(wù)請求的時間間隔服從泊松分布[21]。UE的數(shù)量為M，用戶提交到UE上的任務(wù)是相互獨立的。邊緣服務(wù)器的數(shù)量為K，UE通過無線信道與邊緣服務(wù)器相連接。用戶提交的任務(wù)的屬性被定義為taski={idu,idi,subi,di,memi,cpui,deadlinei,seci}，其中idu為提交任務(wù)i的用戶的id；idi表示任務(wù)i的id；subi表示任務(wù)i的提交時間；di表示任務(wù)i的數(shù)據(jù)量；memi表示任務(wù)i請求的內(nèi)存資源；cpui表示任務(wù)i請求的CPU資源；deadlinei表示任務(wù)i能夠容忍的最大響應(yīng)時間，任務(wù)的響應(yīng)時間是指任務(wù)從提交到完成執(zhí)行的時間間隔；seci表示任務(wù)i的安全性等級。

3.2 通信模型

UE與邊緣服務(wù)器之間是通過無線信道相連接的，假設(shè)gm,k表示某一UE設(shè)備m與某一邊緣服務(wù)器k之間的信道增益，單位為dB，gm,k一般的計算公式為：

gm,k=127+25·lgD

(1)

其中，D表示通信距離，若通信距離不發(fā)生變化，則信道增益為常量。假設(shè)任務(wù)從UE設(shè)備m上卸載到邊緣服務(wù)器k的發(fā)射功率為pm,k，當任務(wù)卸載時，任務(wù)的通信速率定義為：

(2)

其中，B表示UE與邊緣服務(wù)器之間的無線信道帶寬，N表示信道噪聲功率密度。

3.3 計算模型

(1)本地計算模型。

本地端的移動UE設(shè)備自身具有一定的計算能力，能夠處理適量的任務(wù)請求，其計算能力用CPU頻率來表示，表示為fm,l,l表示本地端。假設(shè)用戶提交的任務(wù)被分配到UE上執(zhí)行，不卸載到邊緣服務(wù)器上處理，那么任務(wù)i在UE設(shè)備m上的處理時間和響應(yīng)時間分別定義為式(3)和式(4)：

(3)

(4)

任務(wù)i在UE設(shè)備m上的執(zhí)行能耗表示為：

Ei,m=η·(fm,l)2·di·C

(5)

其中，η表示能量因子，大小取決于CPU芯片工藝，一般設(shè)置為10-28。

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

當本地設(shè)備無法對某些任務(wù)進行有效處理時，為了更好地滿足用戶的QoS需求，此類任務(wù)就有必要從UE設(shè)備卸載到邊緣服務(wù)器上執(zhí)行。邊緣服務(wù)器k的計算能力定義為fk,e，e表示邊緣服務(wù)器端，任務(wù)i卸載到邊緣服務(wù)器k上的處理時間表示為：

(6)

任務(wù)i卸載到邊緣服務(wù)器上處理時，存在一個任務(wù)上傳時間，任務(wù)的上傳時間定義為：

(7)

由于經(jīng)邊緣服務(wù)器處理后，任務(wù)的數(shù)據(jù)量遠小于任務(wù)處理之前的數(shù)據(jù)量，且下載速率遠高于上傳速率，所以，本文不考慮結(jié)果從邊緣服務(wù)器返回到UE的下載時延。

與式(4)同理，任務(wù)i在邊緣服務(wù)器k上的響應(yīng)時間定義為：

(8)

若任務(wù)i卸載到邊緣服務(wù)器k上處理，此時，UE設(shè)備m的能耗僅為任務(wù)i卸載時的發(fā)射能耗，任務(wù)i卸載時的發(fā)射能耗定義為：

(9)

3.4 問題描述

本文的優(yōu)化目標是在提高任務(wù)卸載成功率和任務(wù)成功執(zhí)行率的同時降低本地端的能耗開銷，且盡量滿足用戶的QoS請求。QoS指標包括：任務(wù)的響應(yīng)容忍度(也稱為deadline)、任務(wù)在計算節(jié)點上處理的安全性。任務(wù)要想成功地在計算節(jié)點上執(zhí)行：首先，要保證任務(wù)請求的硬件資源小于計算節(jié)點的硬件資源；其次，要考慮各UE設(shè)備能源的有限性；最后，要保證任務(wù)在計算節(jié)點上執(zhí)行不違背deadline，且計算節(jié)點的安全性等級不小于任務(wù)所要求的安全性等級。本文中，任務(wù)的安全性等級設(shè)置分別為低、中、高，且任務(wù)屬性的安全性等級是隨機生成的；由于UE設(shè)備為私人設(shè)備，因此，將UE設(shè)備的安全性等級全設(shè)置為高；本文考慮的MEC模型中，邊緣端共有3種類型的邊緣服務(wù)器，其安全性等級分別為高、中、低。

假設(shè)總?cè)蝿?wù)量為x，任務(wù)的卸載比例為β，那么卸載的任務(wù)數(shù)量為βx。假設(shè)成功卸載的任務(wù)數(shù)量為y，在本地端成功執(zhí)行的任務(wù)數(shù)量為z，那么任務(wù)的卸載成功率和任務(wù)的成功執(zhí)行率分別定義為式(10)和式(11)：

(10)

(11)

本地端的總能耗定義為式(12)：

(12)

當任務(wù)在本地端執(zhí)行時，沒有通信能耗，通信能耗即為0；當任務(wù)卸載到邊緣服務(wù)器端執(zhí)行時，就只有通信能耗，在UE上的執(zhí)行能耗即為0。

綜上，本文的優(yōu)化目標定義為：

maxosr、serand minEl

s.t.memi≤MEMcn

cpui≤CPUcn

seci≤seccn

(13)

其中，MEMcn、CPUcn分別為計算節(jié)點的內(nèi)存資源、CPU資源，seccn表示計算節(jié)點的安全性等級。由于在MEC模型中考慮的任務(wù)等待執(zhí)行是非搶占的，先到達任務(wù)等待隊列的任務(wù)先執(zhí)行，且每個計算節(jié)點執(zhí)行的是單任務(wù)。因此，本文默認單任務(wù)請求的硬件資源總是不大于計算節(jié)點的硬件資源的。

4 算法設(shè)計

4.1 深度強化學習

深度強化學習DRL(Deep Reinforcement Learning)[22,23]近些年在人工智能領(lǐng)域受到了廣泛關(guān)注，是人工智能領(lǐng)域最受歡迎的學習方法之一。深度強化學習做為一種自適應(yīng)學習方法，是深度學習DL(Deep Learning)[24]與強化學習RL(Reinforcement Learning)[25]相結(jié)合的一種新型的學習方式。DL是一種機器學習方法，源于對人工神經(jīng)網(wǎng)絡(luò)的研究，是一種含有多個隱藏層的多層感知器的DL結(jié)構(gòu)。DL通過組合低層特征形成更加抽象的高層特征表示屬性類別或特征，以發(fā)現(xiàn)數(shù)據(jù)的分布式特征表示。因此，DL能夠很好地擬合高維數(shù)據(jù)。RL也是機器學習的一種，用于描述智能體在與外部環(huán)境的交互過程中通過學習策略以達到回報最大化。DRL方法充分發(fā)揮了DL、RL各自的優(yōu)勢，能夠有效地處理生活中高維且連續(xù)的問題，DRL的原理如圖2所示。

Figure 2 Principle of DRL圖2 DRL原理圖

從圖2中也可以了解到，DRL方法主要是通過DL來擬合場景的狀態(tài)，并用RL來進行決策，且智能體不斷地與外部環(huán)境進行交互，最終實現(xiàn)回報最大化。

4.2 Double DQN算法

Double DQN算法[26]是DRL方法中的一種具體算法，該算法是用卷積神經(jīng)網(wǎng)絡(luò)CNN(Convolutional Neural Network)來充當DRL模型中的深度學習結(jié)構(gòu)，也就是用CNN擬合場景的高維狀態(tài)。一般稱Double DQN算法中的網(wǎng)絡(luò)結(jié)構(gòu)為Q網(wǎng)絡(luò)，然而在Double DQN算法中包含2個結(jié)構(gòu)完全相同的Q網(wǎng)絡(luò)，一個稱為當前Q網(wǎng)絡(luò)，另一個稱為目標Q網(wǎng)絡(luò)。Double DQN算法的另一個結(jié)合體是RL方法中最為經(jīng)典的Q-learning算法[27,28]，Q-learning算法能夠很好地求解連續(xù)決策問題，其通過外部環(huán)境的反饋值不斷地調(diào)整策略，最終使回報達到最大化。Double DQN算法的關(guān)鍵技術(shù)有：值函數(shù)逼近(高維狀態(tài)擬合)、經(jīng)驗回放、雙Q網(wǎng)絡(luò)等。這些關(guān)鍵技術(shù)能夠提高算法的性能。

(1)值函數(shù)逼近。Q-learning算法的決策是基于Markov決策[29]過程的，Markov決策過程是離散化的，然而現(xiàn)實生活中大多數(shù)問題是連續(xù)的。具體方法為，假設(shè)當前環(huán)境的一組狀態(tài)集S為Q網(wǎng)絡(luò)的輸入，經(jīng)過網(wǎng)絡(luò)訓練之后，最后相應(yīng)的輸出為一組動作Q值。

(2)經(jīng)驗回放。經(jīng)驗回放是Double DQN算法的一項關(guān)鍵技術(shù)，能夠改善經(jīng)驗樣本相關(guān)性引起的振蕩和發(fā)散問題。經(jīng)驗回放是指在經(jīng)驗回放池中隨機抽取小批量的經(jīng)驗樣本以獲取目標動作Q值。經(jīng)驗回放池由一個個經(jīng)驗元組{st,ɑt,rt,st+1}構(gòu)成，st表示當前環(huán)境在t時刻的狀態(tài)；ɑt表示在t時刻做出的動作決策；rt表示在做出決策之后，外部環(huán)境所給出的反饋值，反饋值有積極的、有消極的，這將會影響下一決策；st+1是指t時刻的下一時刻的環(huán)境狀態(tài)。當然，經(jīng)驗回放池的容量是有限的，當經(jīng)驗回放池將要溢出時，則會刪除最老的經(jīng)驗樣本。

(3)雙Q網(wǎng)絡(luò)。雙Q網(wǎng)絡(luò)作為Double DQN算法最核心的技術(shù)，不僅能減少當前Q值與目標Q值的相關(guān)性，還能通過解耦更新目標Q值的動作選擇和目標Q值計算這2步，避免對動作值過估計，加快算法收斂。經(jīng)研究發(fā)現(xiàn)，無論是Q-learning算法還是DQN算法[30]，有時都會獲得不切實際的高動作值。而Double DQN算法能夠消除過估計的具體原理是：目標Q值的計算不同于DQN算法在目標Q網(wǎng)絡(luò)中找每一動作對應(yīng)的最大Q值，而是先在當前Q網(wǎng)絡(luò)中找出最大Q值對應(yīng)的動作，然后再利用這個選出的動作在目標Q網(wǎng)絡(luò)中計算目標Q值。Double DQN算法中的2個Q網(wǎng)絡(luò)具有完全相同的結(jié)構(gòu)，但是目標Q網(wǎng)絡(luò)不必更新網(wǎng)絡(luò)參數(shù)，只需每隔特定時間步從當前Q網(wǎng)絡(luò)復制其網(wǎng)絡(luò)參數(shù)。目標Q值的更新公式為：

yt=rt+γ*Q′(st+1,argmaxaQ(st+1,a;θ);θ′)

(14)

其中，γ表示折扣因子；argmaxaQ(st+1,ɑ;θ)表示當前Q網(wǎng)絡(luò)最大Q值所對應(yīng)的動作；θ是當前Q網(wǎng)絡(luò)的網(wǎng)絡(luò)參數(shù)；θ′是目標Q的網(wǎng)絡(luò)參數(shù)。

Double DQN算法訓練的實質(zhì)是在經(jīng)過大量訓練之后使得當前Q值無限接近于目標Q值，使這兩者之間的誤差趨于穩(wěn)定且接近于0。此時，訓練就基本結(jié)束，算法也就達到了最終收斂的狀態(tài)。誤差函數(shù)(損失函數(shù))可以定義為：

Loss(θ)=E[(yt-Q(st,a;θ))]2

(15)

其中，Q(st,ɑ;θ)為當前Q值。誤差函數(shù)基于殘差模型，為目標Q值與當前Q值之差的平方。訓練時，依據(jù)Loss的值，通過誤差方向傳播的方式來不斷更新當前Q網(wǎng)絡(luò)的參數(shù)。經(jīng)過反復學習和訓練，最終使得Loss趨于穩(wěn)定且最小化。

Double DQN算法的結(jié)構(gòu)如圖3所示。

Figure 3 Structure of Double DQN圖3 Double DQN結(jié)構(gòu)圖

Double DQN算法的偽代碼如算法1所示。

算法1Double DQN算法

輸入：狀態(tài)值。

輸出：動作值。

step1Initialize replay memoryRto capacityRC；

step2Initialize action-value functionQwith random weightsθ;

step3Initialize target action-value functionQ′ with weightsθ′；

step4Forepisode=1,Mdo

step5Initialize sequences1={x1} and preprocessed sequence Ф1=Ф(s1)；

step6Fort=1,Tdo

step7With probabilityεselect a random actionat；

step8otherwise selectat=argmaxaQ(Ф(st),a;θ);

step9Execute actionatin emulator and observe rewardrtand imagext+1；

step10Setst+1 =st,ɑt,xt+1and preprocess Фt+1=Ф(st+1)；

step11Store transition (Фt,ɑt,rt,Фt+1) inR；

step12Sample random minibatch of transitions (Фj,αj,rj,Фj+1) fromR；

step13Executey=Q′(sj+1,argmaxaQ(sj+1,a,θ);θ′);

step15Perform a gradient descent step on (yj-Q(Фj,αj;θ))2with respect to the network parametersθ；

step16Everyζsteps resetQ′ =Q；

step17EndFor

step18EndFor

4.3 Double DQN任務(wù)卸載算法設(shè)計

本文的核心是運用深度強化學習方式中的一種具體算法Double DQN解決MEC環(huán)境中的任務(wù)卸載和資源分配問題，本文將這種算法命名為DDQNOA。該算法主要是通過深度學習架構(gòu)去擬合環(huán)境的狀態(tài)，然后基于強化學習在每一種狀態(tài)下做出合理決策，選出合理動作，也就是為到達任務(wù)等待隊列的每一個任務(wù)做出合理決策。確定每一個任務(wù)是否需要卸載，若需要，確定任務(wù)卸載到哪一個邊緣服務(wù)器；若不需要，確定任務(wù)分配到哪一臺UE設(shè)備上處理。每做出一次決策，就會獲得一個來自環(huán)境的反饋獎勵值，該值用來指導Agent的學習，使Agent朝著回報最大化的方向探索，最終提升優(yōu)化目標的優(yōu)化效果。DDQNOA算法的偽代碼如算法2所示：

算法2DDQNOA算法

輸入：所有計算節(jié)點。

輸出：任務(wù)卸載成功率,任務(wù)成功執(zhí)行率,UE端總能耗。

step1Initialize the MEC environment；

step2Initialize computing node resources；

step3Initialize parameters settings；

step4Wait for users to submit tasks；

step5Forone task arrives in task waiting queuedo

step6Use Double DQN algorithm to select a computing node for the task；

step7Ifthe selected computing node is UEmthen

step8Task is processed on the local device UEm；

step9Calculate task response time and UEmenergy consumption；

step10End

step11Elseoffload the task to the edge serverkto process；

step12Calculate task response time, communication time and transmission energy consumption；

step13End

step14Calculate the reward value to the agent according to formula (16)；

step15Update the optimal strategy of the DDQNOA algorithm；

step16EndFor

step17Returnstep 5

(2)動作空間。動作空間是指在狀態(tài)S下，Agent在做出決策時所能夠選取的所有動作的集合。具體到本文考慮的MEC模型中，是指在決策時能夠選取的所有計算節(jié)點組成的集合。那么動作集可以表示為：A={UE1,UE2,…,UEm,ES1,…,ESk},其中，UEm表示UE設(shè)備m,ESk表示邊緣服務(wù)器k。假設(shè)某一計算節(jié)點被選中，那么其相對應(yīng)的動作值為1，未被選中的計算節(jié)點對應(yīng)的動作值就為0。假設(shè)任務(wù)在UE1上執(zhí)行，此時動作空間就可表示為：A=(1,0,…,0)。

(3)獎勵值函數(shù)。獎勵值的合理設(shè)計對算法的性能起著至關(guān)重要的作用，獎勵值用于評估當前狀態(tài)下Agent所選取動作的優(yōu)劣。顯然，一個訓練有素的神經(jīng)網(wǎng)絡(luò)應(yīng)該具有評估積極情況的能力，能對合理的決策給予肯定，最終使Agent能夠根據(jù)用戶的QoS請求合理地卸載任務(wù)、分配資源。本文中，獎勵值函數(shù)可以表示為：

(16)

綜上，獎勵值這樣設(shè)計較為合理。

5 仿真實驗及性能分析

5.1 仿真環(huán)境

本文的仿真實驗是在內(nèi)存為8 GB、CPU型號為Intel Core i5、頻率為2.4 GHz，操作系統(tǒng)為Windows 10的環(huán)境下進行。集成開發(fā)環(huán)境為Python 3.6，且在該環(huán)境下調(diào)用了Google的tensorflow 1.13類庫作為DDQNOA算法的深度學習框架。

5.2 實驗參數(shù)

本文仿真實驗，訓練和測試所使用的任務(wù)集是隨機生成的、大小為2 MB的隨機均勻分布的任務(wù)集合，且MEC模型中的相關(guān)參數(shù)的設(shè)計都與文獻[12,14,17]中參數(shù)的設(shè)計大致相似。實驗參數(shù)和超參數(shù)的設(shè)置如表1所示。

Table 1 Experimental parameters表1 實驗參數(shù)

5.3 對比算法

為了評估和驗證本文所提出的任務(wù)卸載算法的性能，引入了幾種經(jīng)典算法進行對比。第1種是隨機卸載算法Random。Random算法是指將任務(wù)隨機卸載到邊緣服務(wù)器上處理，該算法容易理解，且易于實現(xiàn)，對解決任務(wù)調(diào)度等問題有一定的效果。第2種是輪詢卸載算法RR(Round-Robin)，RR算法是指將要卸載的任務(wù)依次按順序卸載到邊緣服務(wù)器上處理。第3種是基于DQN的任務(wù)卸載算法，該算法也是本文任務(wù)卸載算法重點要對比的算法。與Double DQN算法一樣，DQN算法同樣是深度強化學習的一種具體算法，其在解決實際問題時能夠取得不錯的效果，已在求解云環(huán)境中的任務(wù)調(diào)度問題上有了廣泛的應(yīng)用[9,31]。

5.4 實驗結(jié)果及分析

(1) 收斂性。

為了驗證本文算法在解決MEC環(huán)境中任務(wù)卸載與資源分配問題上的可行性與算法的性能，首先進行了收斂性對比實驗。通過隨機生成的50 000個任務(wù)對基于DQN的任務(wù)卸載算法和DDQNOA算法進行了充分的訓練，訓練結(jié)果如圖4所示。由圖4可知，這2種算法均可以收斂，證明了它們用于解決該問題是可行的。通過對比發(fā)現(xiàn)，DDQNOA算法較DQN算法能夠更早地收斂，這主要是由DDQNOA算法策略所決定的，DDQNOA算法通過解耦目標Q值的計算與解耦目標Q值動作的選擇，解決了在決策時存在的對動作值的過高估計的問題，加快了算法收斂。

Figure 4 Convergence comparison of algorithms 圖4 算法收斂性比較

(2) 任務(wù)卸載對比實驗。

為了驗證本文算法的性能，基于不同數(shù)量的任務(wù)集，對各種算法的任務(wù)卸載情況、任務(wù)卸載成功率進行了分析，任務(wù)的卸載比例和任務(wù)卸載成功率如圖5和圖6所示。

Figure 5 Ratio of task offloading圖5 任務(wù)卸載比例

由圖5可知，DDQNOA算法將任務(wù)卸載到邊緣服務(wù)器上執(zhí)行的比例明顯高于其它幾種算法的，這是由于邊緣服務(wù)器端的計算節(jié)點的計算能力較UE設(shè)備的更為強大。為了保證用戶的QoS請求，DDQNOA算法能夠根據(jù)QoS請求和UE端、邊緣服務(wù)器端的資源情況，合理地分配任務(wù)在UE端和在邊緣服務(wù)器端的執(zhí)行比例。根據(jù)任務(wù)卸載比例圖，也能很好地與rewards的設(shè)計相對應(yīng)起來。

Figure 6 Successed rate of task offloading圖6 任務(wù)卸載成功率

由圖6可知，DDQNOA算法的卸載成功率也明顯高于其它算法的，表明了DDQNOA算法能同時兼顧任務(wù)卸載比例與卸載成功率，這很好地體現(xiàn)了DDQNOA算法的性能。

(3) 任務(wù)執(zhí)行情況對比實驗。

整個MEC模型中，成功執(zhí)行的任務(wù)包含2個

部分，一部分是卸載到邊緣服務(wù)器上能夠成功執(zhí)行的任務(wù)，另一部分是分配到UE設(shè)備上能夠成功執(zhí)行的任務(wù)。任務(wù)總的執(zhí)行情況如圖7所示，可以得知，DDQNOA算法的任務(wù)成功執(zhí)行率高于其它幾種算法的。由任務(wù)的成功執(zhí)行率也能夠看出本文算法的性能優(yōu)于其它幾種算法的。

Figure 7 Rate of task successful executed圖7 任務(wù)成功執(zhí)行率

(4) UE端能耗實驗。

為了對比不同算法UE端的總能耗情況，分別測試了各算法在不同任務(wù)數(shù)量下UE端的總能耗。由圖8可知，使用DDQNOA算法進行任務(wù)卸載與資源分配時，UE端的總能耗總是最低的。然而，本文的主要目的是在保證任務(wù)卸載成功率和任務(wù)成功執(zhí)行率的同時，降低UE端的總能耗。結(jié)合圖6和圖7可知，在不同任務(wù)數(shù)量的測試集上，DDQNOA算法總是具有更高的任務(wù)卸載成功率和任務(wù)執(zhí)行成功率，且UE端具有更低的總能耗。這不僅表明了DDQNOA算法有著良好的穩(wěn)定性，還充分體現(xiàn)了DDQNOA算法較其它對比算法具有更好的性能。

Figure 8 Total energy consumption of UE圖8 UE端總能耗

根據(jù)所有仿真實驗結(jié)果，經(jīng)過分析得知，本文提出的DDQNOA算法在具有多約束條件的MEC環(huán)境中，能夠有效地求解任務(wù)卸載與資源分配問題，在提升任務(wù)卸載成功率、任務(wù)成功執(zhí)行率的同時降低了本地端的能耗，更好地滿足了用戶的QoS需求。

6 結(jié)束語

針對目前大多數(shù)MEC研究中對數(shù)據(jù)安全性問題的忽視，本文考慮了任務(wù)處理時數(shù)據(jù)的安全性，結(jié)合Double DQN算法，在多約束條件下提出了一種高效的任務(wù)卸載與資源分配算法——DDQNOA。實驗結(jié)果表明，與幾種經(jīng)典算法相比較，該算法能夠滿足用戶的QoS需求，在提高任務(wù)卸載成功率和任務(wù)成功執(zhí)行率的同時，確保本地端具有更低的能耗。

在今后的研究中，將會考慮更為復雜的MEC場景。例如，擴大邊緣服務(wù)器端的規(guī)模、多信道通信；將云計算與MEC相結(jié)合，綜合考慮云邊協(xié)同下的任務(wù)卸載與資源分配等。