李 斌，徐天成

(南京信息工程大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210044)

0 引言

隨著5G、物聯(lián)網(wǎng)和人工智能的融合與快速發(fā)展，以及日益增長(zhǎng)的用戶(hù)計(jì)算資源需求，利用移動(dòng)邊緣計(jì)算(Mobile Edge Computing，MEC)在網(wǎng)絡(luò)邊緣卸載任務(wù)，已成為未來(lái)互聯(lián)網(wǎng)發(fā)展的重要方向[1-2]。其優(yōu)勢(shì)在于能夠?yàn)榫W(wǎng)絡(luò)邊緣用戶(hù)提供近距離通信，并且有效減輕用戶(hù)設(shè)備的壓力，同時(shí)有利于與物聯(lián)網(wǎng)和云計(jì)算等新技術(shù)的融合應(yīng)用。

為了解決用戶(hù)資源和計(jì)算能力有限的問(wèn)題，提出了基于終端直通(Device-to-Device，D2D)技術(shù)的卸載模式作為MEC的一種有效增補(bǔ)[3]，旨在將大量的計(jì)算和存儲(chǔ)資源協(xié)同控制和管理起來(lái)，以完成密集型應(yīng)用任務(wù)[4-6]。同時(shí)，未來(lái)物聯(lián)網(wǎng)、邊緣計(jì)算網(wǎng)絡(luò)等新網(wǎng)絡(luò)場(chǎng)景高速發(fā)展，智能設(shè)備數(shù)量和用戶(hù)需求也隨之大幅增長(zhǎng)，如何將有限的計(jì)算、帶寬和存儲(chǔ)等網(wǎng)絡(luò)資源最大程度利用起來(lái)，并在大量的終端數(shù)據(jù)上實(shí)現(xiàn)自動(dòng)管理，以獲得更高效的網(wǎng)絡(luò)傳輸性能和通信質(zhì)量是實(shí)現(xiàn)5G應(yīng)用急需解決的熱點(diǎn)研究問(wèn)題之一。

關(guān)于D2D和MEC集成化的任務(wù)卸載方案已有相關(guān)研究[7-9]。文獻(xiàn)[10]提出了具有邊緣計(jì)算和D2D通信的5G蜂窩網(wǎng)絡(luò)節(jié)能計(jì)算卸載方案，采用Lyapunov優(yōu)化技術(shù)框架解決問(wèn)題。文獻(xiàn)[11]將用戶(hù)的卸載決策問(wèn)題表述為序列博弈，為了實(shí)現(xiàn)納什均衡，提出了一種多用戶(hù)多目的地計(jì)算卸載方案。文獻(xiàn)[12]將任務(wù)調(diào)度和功率分配作為一個(gè)隨機(jī)優(yōu)化問(wèn)題，其研究目標(biāo)是最小化協(xié)作設(shè)備在無(wú)線(xiàn)通信和計(jì)算方面的平均費(fèi)用。通過(guò)對(duì)優(yōu)化變量的解耦，提出了一種次優(yōu)化算法。為了最小化單用戶(hù)多任務(wù)協(xié)作MEC網(wǎng)絡(luò)的時(shí)延，文獻(xiàn)[13]將任務(wù)分配和無(wú)線(xiàn)資源分配共同定義為MINLP問(wèn)題。在松弛凸問(wèn)題最優(yōu)解的基礎(chǔ)上，提出了一種次優(yōu)解方案。

用戶(hù)的移動(dòng)性使得卸載決策高度動(dòng)態(tài)。因此，如何通過(guò)考慮用戶(hù)移動(dòng)性驅(qū)動(dòng)的網(wǎng)絡(luò)狀態(tài)不確定性來(lái)設(shè)計(jì)高效的任務(wù)調(diào)度和資源分配策略，以增強(qiáng)分布式系統(tǒng)中移動(dòng)用戶(hù)的任務(wù)卸載體驗(yàn)，成為了一個(gè)重要的研究方向?；诖耍墨I(xiàn)[14]提出了一個(gè)基于連續(xù)時(shí)間馬爾可夫鏈的連接概率模型，以最小化在D2D網(wǎng)絡(luò)中協(xié)作任務(wù)的執(zhí)行時(shí)間。目前，越來(lái)越多的學(xué)者試圖用深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning，DRL)的方法來(lái)解決這一問(wèn)題，通過(guò)構(gòu)建自學(xué)習(xí)能力更強(qiáng)的神經(jīng)網(wǎng)絡(luò)來(lái)近似表示Q值。作為智能體的每個(gè)卸載節(jié)點(diǎn)學(xué)會(huì)基于與環(huán)境的交互做出計(jì)算卸載的決定。從長(zhǎng)遠(yuǎn)來(lái)看，通過(guò)從經(jīng)驗(yàn)中優(yōu)化計(jì)算卸載策略，系統(tǒng)能耗被最小化。

本文提出了一種基于D2D通信和MEC的2層任務(wù)卸載框架。在所提框架下，用戶(hù)自低到高依次具有設(shè)備層(本地設(shè)備和D2D協(xié)作設(shè)備)和邊緣層(邊緣服務(wù)器)2個(gè)卸載層級(jí)可選。層級(jí)越高的卸載模式具有越充裕的計(jì)算資源，而將任務(wù)卸載到更高層級(jí)處理所付出的傳輸代價(jià)也更高。同時(shí)，所提框架還利用D2D協(xié)作中繼技術(shù)協(xié)助移動(dòng)用戶(hù)連接更高卸載層級(jí)。為了實(shí)現(xiàn)動(dòng)態(tài)、智能的任務(wù)卸載模式，提出了一種基于DRL的任務(wù)卸載策略。首先，對(duì)D2D輔助多任務(wù)用戶(hù)卸載數(shù)據(jù)的場(chǎng)景進(jìn)行建模，并考慮用戶(hù)的移動(dòng)性構(gòu)建能耗最小化優(yōu)化問(wèn)題；然后，基于強(qiáng)化學(xué)習(xí)思想，設(shè)計(jì)了雙深度Q網(wǎng)絡(luò)(Double DQN,DDQN)算法對(duì)多任務(wù)卸載做出實(shí)時(shí)決策；最后，利用所提DDQN算法對(duì)本文所考慮的場(chǎng)景進(jìn)行仿真，其優(yōu)化決策的收斂性較好，并與其他基線(xiàn)方案進(jìn)行對(duì)比，證實(shí)了本文所提方案的優(yōu)越性。

1 系統(tǒng)模型

本文考慮一個(gè)支持D2D通信的協(xié)同MEC網(wǎng)絡(luò)，該系統(tǒng)模型由單個(gè)用戶(hù)、單個(gè)基站和M個(gè)D2D設(shè)備組成，如圖1所示。其中空閑且資源充裕的設(shè)備(如筆記本、平板電腦和手機(jī)等可以作為邊緣節(jié)點(diǎn))通過(guò)與資源有限的用戶(hù)設(shè)備(User Device，UD)建立直接的D2D鏈路[15]，以促進(jìn)計(jì)算卸載。假設(shè)UD有J個(gè)獨(dú)立的計(jì)算密集型任務(wù)要執(zhí)行，用集合J={1,2,…,i}表示。移動(dòng)用戶(hù)的任務(wù)沿著用戶(hù)的軌跡被卸載到D2D設(shè)備或基站上。在UD行走的道路上，分布著M個(gè)D2D設(shè)備，用集合M={1,2,…,m}表示?？紤]一種網(wǎng)絡(luò)輔助架構(gòu)，其中基站擁有全局網(wǎng)絡(luò)信息，包括關(guān)于用戶(hù)移動(dòng)性和任務(wù)的細(xì)節(jié)。

圖1 系統(tǒng)模型Fig.1 System model

對(duì)于任務(wù)卸載，UD可以在基站的幫助下通過(guò)建立直接的D2D鏈路(使用WiFi或藍(lán)牙等技術(shù))連接到附近的D2D設(shè)備?；究蓹z測(cè)出UD的位置，以便將其任務(wù)調(diào)度到D2D設(shè)備，使計(jì)算卸載總能耗最小化。為了簡(jiǎn)化計(jì)算模型，UD、基站和D2D設(shè)備均只考慮裝配一根天線(xiàn)。

1.1 用戶(hù)移動(dòng)模型

假設(shè)UD的軌跡在[0,T]可獲得，小區(qū)空間劃分為二維空間，λ(t)={x(t),y(t)}，T={1,2,…,t}表示用戶(hù)在t時(shí)隙所在的位置。由于其有限的處理能力，UD可以選擇將任務(wù)卸載到附近的D2D進(jìn)行計(jì)算。λm={xm,ym}，M={1,2,…,m}表示第m個(gè)D2D的位置。

與文獻(xiàn)[16-17]中的類(lèi)似，假設(shè)系統(tǒng)在一個(gè)持續(xù)時(shí)間T內(nèi)工作，以精確捕獲用戶(hù)的移動(dòng)性。因此，將移動(dòng)軌跡劃分為時(shí)間τ相等的時(shí)間段，滿(mǎn)足T=nτ。記時(shí)間段的集合為N={1,2,…,n}。對(duì)于每一個(gè)選擇的n，UD在每個(gè)時(shí)隙內(nèi)的位置近似不變。假設(shè)UD的移動(dòng)速度相對(duì)較慢，短時(shí)間內(nèi)所走的距離不會(huì)有很大的變化。記UD在時(shí)隙n∈N中的水平位置為λo(n)=λ(nτ)。根據(jù)UD在時(shí)隙n∈N中的位置，可以得到UD與第m個(gè)D2D設(shè)備之間的距離為dm(n)=‖λo(n)-λm‖。

1.2 任務(wù)卸載模型

在每個(gè)時(shí)隙，UD以一個(gè)確定概率隨機(jī)生成i個(gè)任務(wù)(i∈J)。本文用Υt來(lái)表示是否有任務(wù)請(qǐng)求，Υt=1表示在t時(shí)隙有一個(gè)任務(wù)請(qǐng)求，Υt=0表示在t時(shí)隙沒(méi)有任務(wù)請(qǐng)求。UD的計(jì)算任務(wù)可由TKi(ci,ai,dli)表示，其中ci表示任務(wù)卸載時(shí)本地設(shè)備需向外傳輸?shù)臄?shù)據(jù)量，ai表示處理該任務(wù)所需的機(jī)器語(yǔ)言指令數(shù)，dli表示執(zhí)行任務(wù)的最大時(shí)延。對(duì)于時(shí)間密集型任務(wù)，每個(gè)任務(wù)必須在dli內(nèi)完成，所以每個(gè)任務(wù)執(zhí)行時(shí)間應(yīng)該小于時(shí)隙長(zhǎng)度τ。

(1)

(1) 本地計(jì)算模式

(2)

UD在本地計(jì)算模式下的能耗定義為：

(3)

式中，ko表示有效電容系數(shù)，它取決于UD使用的芯片結(jié)構(gòu)[18]。為了現(xiàn)實(shí)，假設(shè)CPU頻率小于最大CPU頻率。

(2) D2D卸載模式

(4)

UD在D2D卸載模式下的上傳任務(wù)所需能耗定義為：

(5)

此時(shí)，UD在D2D卸載模式下的處理時(shí)延定義為：

(6)

UD在D2D卸載模式下的計(jì)算能耗定義為：

(7)

式中，kD表示有效電容系數(shù)，它取決于D2D使用的芯片結(jié)構(gòu)。

根據(jù)式(4)～式(7)，UD在D2D卸載模式下的執(zhí)行時(shí)延和能耗分別為：

(8)

(9)

(3) D2D輔助中繼卸載模式

由此，任務(wù)上傳到邊緣服務(wù)器執(zhí)行所需時(shí)間定義為：

(10)

UD在D2D輔助邊緣計(jì)算模式下的上傳任務(wù)所需能耗定義為：

(11)

UD在D2D輔助邊緣計(jì)算模式下的處理時(shí)延定義為：

(12)

UD在D2D輔助邊緣計(jì)算模式下的計(jì)算能耗定義為：

(13)

式中，kBS表示有效電容系數(shù)，它取決于邊緣服務(wù)器使用的芯片結(jié)構(gòu)。

根據(jù)式(10)～式(13)，UD在D2D輔助邊緣計(jì)算模式下的執(zhí)行時(shí)延和能耗分別為：

(14)

(15)

2 問(wèn)題描述

在這項(xiàng)工作中，本文的研究目標(biāo)是最小化時(shí)延約束下任務(wù)執(zhí)行的總能耗，包括本地執(zhí)行能耗、D2D卸載能耗和卸載到基站能耗，可表示為：

(16)

為了減少卸載能耗，利用UD移動(dòng)過(guò)程中不同時(shí)隙的位置信息進(jìn)行任務(wù)卸載決策。故本文的研究問(wèn)題形式化描述為：

(17)

式(17)給出了以任務(wù)卸載決策為優(yōu)化變量的目標(biāo)函數(shù)。約束C1表明用戶(hù)最多只能選擇一種模式來(lái)完成它的任務(wù)。約束C2表明任務(wù)只能全部卸載。約束C3表明分配給移動(dòng)用戶(hù)的計(jì)算資源不能超過(guò)MEC服務(wù)器擁有的資源。約束C4表明如果用戶(hù)選擇3種模式中的一種來(lái)完成它的任務(wù)，其時(shí)延不能超過(guò)最大時(shí)延。約束C5表明移動(dòng)用戶(hù)最多同時(shí)連接一個(gè)D2D設(shè)備。約束C6表示UD，D2D的傳輸功率和MEC服務(wù)器的計(jì)算資源分配分別是非負(fù)的?？梢?jiàn)，優(yōu)化式(17)含有多個(gè)離散的決策變量，是一個(gè)混合整數(shù)非線(xiàn)性規(guī)劃問(wèn)題，很難快速求得最優(yōu)解。本文提出了基于DRL的DDQN算法來(lái)解決此問(wèn)題。

3 基于DRL的算法設(shè)計(jì)

由于在高維場(chǎng)景下，創(chuàng)建出來(lái)的Q-table會(huì)過(guò)于龐大，導(dǎo)致無(wú)法建立。為解決具有高維狀態(tài)空間的環(huán)境問(wèn)題，DRL將深度神經(jīng)網(wǎng)絡(luò)與強(qiáng)化學(xué)習(xí)的決策能力相結(jié)合，通過(guò)使用卷積神經(jīng)網(wǎng)絡(luò)對(duì)Q-table做函數(shù)擬合。

由于本文研究的問(wèn)題是移動(dòng)場(chǎng)景下任務(wù)卸載的決策，隨著用戶(hù)的不斷移動(dòng)，環(huán)境也開(kāi)始發(fā)生動(dòng)態(tài)變化。傳統(tǒng)的方案使用Q-learning算法來(lái)探索未知環(huán)境，移動(dòng)用戶(hù)通過(guò)嘗試不同的行動(dòng)，從反饋中學(xué)習(xí)，然后強(qiáng)化動(dòng)作，直到動(dòng)作提供最佳結(jié)果。由于Q-learning算法通過(guò)計(jì)算每個(gè)動(dòng)作的Q值進(jìn)行決策，所以會(huì)在某些條件下高估動(dòng)作值。因此，本文提出使用DDQN方案是一種有效的改進(jìn)，通過(guò)選擇預(yù)測(cè)網(wǎng)絡(luò)中最大Q值對(duì)應(yīng)的動(dòng)作來(lái)計(jì)算目標(biāo)Q值，從而解決過(guò)估計(jì)的問(wèn)題。

3.1 基于DDQN的計(jì)算卸載

為了使用DDQN算法，先將計(jì)算卸載問(wèn)題轉(zhuǎn)化為一個(gè)優(yōu)化問(wèn)題。通過(guò)優(yōu)化任務(wù)卸載，實(shí)現(xiàn)了系統(tǒng)能耗的最小化。由于優(yōu)化問(wèn)題是馬爾可夫問(wèn)題，先將其建模為MDP問(wèn)題。

(1) 狀態(tài)空間:S={x,y}

UD在第t個(gè)時(shí)隙內(nèi)的狀態(tài)為其自身的位置。其中，xt為UD的橫坐標(biāo)，yt為UD的縱坐標(biāo)。

(2) 動(dòng)作空間:A={a}

(3) 獎(jiǎng)勵(lì)函數(shù)

獎(jiǎng)勵(lì)是對(duì)從先前動(dòng)作中獲得的利益的評(píng)估。在這個(gè)問(wèn)題中，優(yōu)化目標(biāo)是使系統(tǒng)的能耗最小，而強(qiáng)化學(xué)習(xí)的目標(biāo)是獲得最大回報(bào)。如果借助強(qiáng)化學(xué)習(xí)來(lái)解決問(wèn)題，就必須將獎(jiǎng)勵(lì)函數(shù)與優(yōu)化目標(biāo)函數(shù)關(guān)聯(lián)起來(lái)。因此，將獎(jiǎng)勵(lì)函數(shù)定義為優(yōu)化目標(biāo)函數(shù)的負(fù)函數(shù)。

(18)

對(duì)于DDQN，不是在目標(biāo)網(wǎng)絡(luò)里面直接搜索最大Q值的動(dòng)作，而是先在預(yù)測(cè)網(wǎng)絡(luò)中找出最大Q值對(duì)應(yīng)的動(dòng)作，即：

(19)

然后利用選取出來(lái)的動(dòng)作在目標(biāo)網(wǎng)絡(luò)里面計(jì)算目標(biāo)Q值：

(20)

式中，γ為折扣因子。

綜合定義為：

(21)

損失函數(shù)為：

(22)

式中，E[·]為隨機(jī)變量期望。

3.2 基于DDQN的能耗最小化算法

本文所提DDQN算法的執(zhí)行架構(gòu)如圖2所示。

圖2 DDQN算法執(zhí)行架構(gòu)Fig.2 DDQN algorithm execution architecture

具體實(shí)現(xiàn)過(guò)程如下：首先，初始化預(yù)測(cè)網(wǎng)絡(luò)、目標(biāo)網(wǎng)絡(luò)和回放空間(算法1中的第1行)。其次，輸入U(xiǎn)D初始位置。接下來(lái)，利用ε-greedy選擇并執(zhí)行動(dòng)作at(算法1中的第5行)。在執(zhí)行動(dòng)作at后，獲得即時(shí)獎(jiǎng)勵(lì)rt和新?tīng)顟B(tài)st+1(算法1中的第6～7行)，并將記憶(st,at,rt,st+1)存儲(chǔ)到D(算法1中的第8行)。然后，從回放空間中隨機(jī)抽取K個(gè)樣本，通過(guò)計(jì)算損失函數(shù)更新目標(biāo)網(wǎng)絡(luò)的參數(shù)(算法1中的第10～13行)。

算法1 基于DDQN的能耗最小化算法輸入 UD初始位置輸出 移動(dòng)過(guò)程中使得系統(tǒng)能耗最小化的卸載決策1.初始化回放空間D,θt和θ-t;2.for episode=1:N3. 獲取初始狀態(tài)s;4. for episode=0:T-15. 將st輸入到預(yù)測(cè)網(wǎng)絡(luò)中,采用ε-greedy獲得動(dòng)作at;6. 執(zhí)行動(dòng)作at,利用式(18)計(jì)算即時(shí)獎(jiǎng)勵(lì)rt;7. 然后獲得即時(shí)獎(jiǎng)勵(lì)rt和新?tīng)顟B(tài)st+1;8. 存儲(chǔ)記憶(st,at,rt,st+1)到D;9. 從D隨機(jī)抽取K個(gè)樣本;10. 根據(jù)式(20)計(jì)算目標(biāo)Q值;11. 根據(jù)式(22)計(jì)算損失函數(shù)以更新θ;12. 更新目標(biāo)網(wǎng)絡(luò)參數(shù);end for

4 仿真結(jié)果與分析

4.1 參數(shù)設(shè)置

4.2 數(shù)值分析

為了評(píng)估本文方案，比較4種方案：① 本地計(jì)算方案，任務(wù)都在本地執(zhí)行；② 隨機(jī)卸載方案，任務(wù)隨機(jī)選擇卸載；③ 無(wú)D2D卸載方案，任務(wù)通過(guò)中繼卸載到MEC服務(wù)器；④ 本文所提方案，任務(wù)可以在本地計(jì)算，也可以卸載到D2D設(shè)備或者卸載到MEC服務(wù)器。

DDQN算法的收斂性如圖3所示。折扣因子是對(duì)未來(lái)獎(jiǎng)勵(lì)的衰減值，代表了當(dāng)前獎(jiǎng)勵(lì)與未來(lái)獎(jiǎng)勵(lì)的重要性。DDQN算法曲線(xiàn)隨著迭代次數(shù)的增加遞減，逐漸收斂。算法訓(xùn)練200個(gè)周期，獲得了訓(xùn)練回報(bào)。

圖3 所提算法收斂性Fig.3 Convergence of the proposed algorithm

分別模擬0.1～0.9的任務(wù)產(chǎn)生概率(以0.2遞增)，比較4種算法的系統(tǒng)能耗。任務(wù)產(chǎn)生概率對(duì)平均能耗的影響如圖4所示，可見(jiàn)系統(tǒng)能耗隨著任務(wù)產(chǎn)生概率的增加而增加，這是由于任務(wù)數(shù)量的增大，導(dǎo)致系統(tǒng)需要更大的能耗開(kāi)銷(xiāo)，從而使得系統(tǒng)能耗增加。本地計(jì)算、隨機(jī)卸載與D2D卸載算法系統(tǒng)能耗較高，DDQN算法的實(shí)驗(yàn)結(jié)果更優(yōu)。

圖4 任務(wù)產(chǎn)生概率對(duì)平均能耗的影響Fig.4 Influence of task generation probability on average energy consumption

不同時(shí)隙大小對(duì)本文方案系統(tǒng)能耗的影響情況如圖5所示。可以看出，隨著時(shí)隙的增大，任務(wù)量減少，從而系統(tǒng)能耗不斷降低。

圖5 平均能耗與時(shí)隙大小的關(guān)系Fig.5 Relationship between average energy consumption and time slot length

分別模擬0.2～1.0的最大時(shí)延(以0.2遞增)，比較4種算法的系統(tǒng)能耗。最大時(shí)延對(duì)平均能耗的影響如圖6所示?？梢钥闯?，系統(tǒng)能耗隨著最大時(shí)延的增加而減少，這是由于最大時(shí)延的增加，導(dǎo)致設(shè)備有充足的計(jì)算任務(wù)時(shí)間。本文方案比其他3種方案能耗更低，進(jìn)一步說(shuō)明了本文方案的有效性。

圖6 最大時(shí)延對(duì)平均能耗的影響Fig.6 Influence of maximum latency on average energy consumption

D2D數(shù)量對(duì)不同方案的系統(tǒng)能耗的影響情況如圖7所示?？梢钥闯觯S著D2D數(shù)量的增加，本文所提方案的能耗在不斷減少。這是因?yàn)?，D2D數(shù)量的增加豐富了用戶(hù)卸載的選擇，可以有效減少傳輸能耗。

圖7 平均能耗與D2D數(shù)量的關(guān)系Fig.7 Relationship between average energy consumption and the number of D2D

5 結(jié)束語(yǔ)

本文提出了一種融合D2D和MEC的2層邊緣云計(jì)算架構(gòu)，并引入D2D協(xié)作中繼技術(shù)用于輔助用戶(hù)接入遠(yuǎn)端邊緣服務(wù)器?？紤]到用戶(hù)移動(dòng)性、分布式計(jì)算能力和任務(wù)卸載時(shí)延約束的特性，將任務(wù)卸載問(wèn)題表述為能耗最小化的混合整數(shù)非線(xiàn)性規(guī)劃問(wèn)題，并進(jìn)一步提出了基于DRL的DDQN算法來(lái)實(shí)時(shí)優(yōu)化任務(wù)卸載決策變量。仿真數(shù)據(jù)表明，提出的協(xié)同計(jì)算方案在計(jì)算資源緊張的情況下，能有效降低移動(dòng)用戶(hù)的任務(wù)執(zhí)行能耗且優(yōu)化決策的收斂性較好。在未來(lái)的工作中，將研究D2D輔助的計(jì)算任務(wù)動(dòng)態(tài)卸載方案中的激勵(lì)機(jī)制。