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

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

(湖南師范大學(xué)信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410012)

1 引言

隨著5G網(wǎng)絡(luò)時(shí)代的到來，5G通信技術(shù)正在逐步走向標(biāo)準(zhǔn)化，物聯(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)爆炸式的增長(zhǎng)。傳統(tǒng)的云計(jì)算存儲(chǔ)和計(jì)算平臺(tái)雖然能較好地對(duì)大數(shù)據(jù)進(jìn)行存儲(chǔ)、分析與處理，但是隨著各種數(shù)據(jù)的增多，尤其是云中心遠(yuǎn)端，靠近數(shù)據(jù)源端的數(shù)據(jù)激增，再加上用戶對(duì)數(shù)據(jù)安全性的要求和對(duì)用戶服務(wù)質(zhì)量QoS(Quality of Service)要求的提高，傳統(tǒng)的以云計(jì)算為基礎(chǔ)的分析、處理平臺(tái)面臨著巨大的挑戰(zhàn)。

云中心通常離用戶、終端設(shè)備比較遠(yuǎn)，終端設(shè)備產(chǎn)生的實(shí)時(shí)數(shù)據(jù)上傳到遠(yuǎn)端云平臺(tái)上分析、處理，完成之后再將結(jié)果沿相同的傳輸路線返回到終端設(shè)備，這一過程會(huì)產(chǎn)生一定的傳輸時(shí)延。同時(shí)，大量的數(shù)據(jù)傳輸也會(huì)增加網(wǎng)絡(luò)帶寬的傳輸負(fù)擔(dān)，使得數(shù)據(jù)傳輸效率和處理速率降低。加上傳輸?shù)皆破脚_(tái)的大量任務(wù)會(huì)使得任務(wù)等待隊(duì)列過長(zhǎng)，導(dǎo)致任務(wù)的響應(yīng)時(shí)間增長(zhǎng)，從而影響了用戶的體驗(yàn)質(zhì)量。并且任務(wù)響應(yīng)時(shí)間過長(zhǎng)，可能會(huì)使得數(shù)據(jù)受到攻擊的概率增大。綜上所述，基于傳統(tǒng)的云計(jì)算的數(shù)據(jù)處理架構(gòu)無法很好地滿足低延遲、高實(shí)時(shí)、高可靠的業(yè)務(wù)需求。為了緩解海量數(shù)據(jù)傳輸帶來的網(wǎng)絡(luò)負(fù)荷問題和滿足用戶低延遲、高實(shí)時(shí)、高可靠的業(yè)務(wù)請(qǐng)求，2014年國(guó)際標(biāo)準(zhǔn)組織[5]提出了一種新興的計(jì)算方式──移動(dòng)邊緣計(jì)算MEC(Mobile Edge Computing)[3,4]。Gartner將移動(dòng)邊緣計(jì)算定義為“分布式計(jì)算拓?fù)涞囊徊糠郑渲行畔⑻幚砦挥谶吘壐浇挛锖腿嗽诖颂幧苫蛳M(fèi)該信息”[6]。也就是說，將云中心的部分存儲(chǔ)、計(jì)算資源轉(zhuǎn)移到網(wǎng)絡(luò)邊緣，更靠近數(shù)據(jù)源的地方，能夠更好地滿足低延遲、高實(shí)時(shí)、高可靠的業(yè)務(wù)請(qǐng)求。

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

2 相關(guān)工作

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

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

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

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

3 系統(tǒng)模型

本文考慮了一個(gè)多用戶、多UE、單基站BS(Base Station)、多異構(gòu)邊緣服務(wù)器的移動(dòng)邊緣計(jì)算場(chǎng)景，如圖1所示。當(dāng)有任務(wù)生成時(shí)，用戶的任務(wù)請(qǐng)求首先提交到某一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 移動(dòng)邊緣計(jì)算系統(tǒng)的模型

3.1 場(chǎng)景描述

本文考慮的MEC模型中，假設(shè)用戶的數(shù)量為n,用戶提交任務(wù)請(qǐng)求的時(shí)間間隔服從泊松分布[21]。UE的數(shù)量為M，用戶提交到UE上的任務(wù)是相互獨(dú)立的。邊緣服務(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的提交時(shí)間；di表示任務(wù)i的數(shù)據(jù)量；memi表示任務(wù)i請(qǐng)求的內(nèi)存資源；cpui表示任務(wù)i請(qǐng)求的CPU資源；deadlinei表示任務(wù)i能夠容忍的最大響應(yīng)時(shí)間，任務(wù)的響應(yīng)時(shí)間是指任務(wù)從提交到完成執(zhí)行的時(shí)間間隔；seci表示任務(wù)i的安全性等級(jí)。

3.2 通信模型

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

gm,k=127+25·lgD

(1)

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

(2)

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

3.3 計(jì)算模型

(1)本地計(jì)算模型。

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

(3)

(4)

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

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

(5)

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

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

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

(6)

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

(7)

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

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

(8)

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

(9)

3.4 問題描述

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

假設(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)

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

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

maxosr、serand minEl

s.t.memi≤MEMcn

cpui≤CPUcn

seci≤seccn

(13)

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

4 算法設(shè)計(jì)

4.1 深度強(qiáng)化學(xué)習(xí)

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

Figure 2 Principle of DRL圖2 DRL原理圖

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

4.2 Double DQN算法

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

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

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

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

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

(14)

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

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

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

(15)

其中，Q(st,ɑ;θ)為當(dāng)前Q值。誤差函數(shù)基于殘差模型，為目標(biāo)Q值與當(dāng)前Q值之差的平方。訓(xùn)練時(shí)，依據(jù)Loss的值，通過誤差方向傳播的方式來不斷更新當(dāng)前Q網(wǎng)絡(luò)的參數(shù)。經(jīng)過反復(fù)學(xué)習(xí)和訓(xùn)練，最終使得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)值。

輸出：動(dòng)作值。

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è)計(jì)

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

算法2DDQNOA算法

輸入：所有計(jì)算節(jié)點(diǎn)。

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

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

(16)

綜上，獎(jiǎng)勵(lì)值這樣設(shè)計(jì)較為合理。

5 仿真實(shí)驗(yàn)及性能分析

5.1 仿真環(huán)境

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

5.2 實(shí)驗(yàn)參數(shù)

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

Table 1 Experimental parameters表1 實(shí)驗(yàn)參數(shù)

5.3 對(duì)比算法

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

5.4 實(shí)驗(yàn)結(jié)果及分析

(1) 收斂性。

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

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

(2) 任務(wù)卸載對(duì)比實(shí)驗(yàn)。

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

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

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

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

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

(3) 任務(wù)執(zhí)行情況對(duì)比實(shí)驗(yàn)。

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

部分，一部分是卸載到邊緣服務(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端能耗實(shí)驗(yàn)。

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

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

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

6 結(jié)束語

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

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