終端直通輔助的移動邊緣計(jì)算任務(wù)動態(tài)卸載方案

李 斌，徐天成

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

0 引言

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

為了解決用戶資源和計(jì)算能力有限的問題，提出了基于終端直通(Device-to-Device，D2D)技術(shù)的卸載模式作為MEC的一種有效增補(bǔ)[3]，旨在將大量的計(jì)算和存儲資源協(xié)同控制和管理起來，以完成密集型應(yīng)用任務(wù)[4-6]。同時，未來物聯(lián)網(wǎng)、邊緣計(jì)算網(wǎng)絡(luò)等新網(wǎng)絡(luò)場景高速發(fā)展，智能設(shè)備數(shù)量和用戶需求也隨之大幅增長，如何將有限的計(jì)算、帶寬和存儲等網(wǎng)絡(luò)資源最大程度利用起來，并在大量的終端數(shù)據(jù)上實(shí)現(xiàn)自動管理，以獲得更高效的網(wǎng)絡(luò)傳輸性能和通信質(zhì)量是實(shí)現(xiàn)5G應(yīng)用急需解決的熱點(diǎ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ù)框架解決問題。文獻(xiàn)[11]將用戶的卸載決策問題表述為序列博弈，為了實(shí)現(xiàn)納什均衡，提出了一種多用戶多目的地計(jì)算卸載方案。文獻(xiàn)[12]將任務(wù)調(diào)度和功率分配作為一個隨機(jī)優(yōu)化問題，其研究目標(biāo)是最小化協(xié)作設(shè)備在無線通信和計(jì)算方面的平均費(fèi)用。通過對優(yōu)化變量的解耦，提出了一種次優(yōu)化算法。為了最小化單用戶多任務(wù)協(xié)作MEC網(wǎng)絡(luò)的時延，文獻(xiàn)[13]將任務(wù)分配和無線資源分配共同定義為MINLP問題。在松弛凸問題最優(yōu)解的基礎(chǔ)上，提出了一種次優(yōu)解方案。

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

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

1 系統(tǒng)模型

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

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

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

1.1 用戶移動模型

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

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

1.2 任務(wù)卸載模型

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

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

(6)

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

(7)

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

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

(8)

(9)

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

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

(10)

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

(11)

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

(12)

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

(13)

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

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

(14)

(15)

2 問題描述

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

(16)

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

(17)

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

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

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

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

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

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

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

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

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

(3) 獎勵函數(shù)

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

(18)

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

(19)

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

算法1 基于DDQN的能耗最小化算法輸入 UD初始位置輸出 移動過程中使得系統(tǒng)能耗最小化的卸載決策1.初始化回放空間D,θt和θ-t;2.for episode=1:N3. 獲取初始狀態(tài)s;4. for episode=0:T-15. 將st輸入到預(yù)測網(wǎng)絡(luò)中,采用ε-greedy獲得動作at;6. 執(zhí)行動作at,利用式(18)計(jì)算即時獎勵rt;7. 然后獲得即時獎勵rt和新狀態(tài)st+1;8. 存儲記憶(st,at,rt,st+1)到D;9. 從D隨機(jī)抽取K個樣本;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ù)值分析

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

DDQN算法的收斂性如圖3所示。折扣因子是對未來獎勵的衰減值，代表了當(dāng)前獎勵與未來獎勵的重要性。DDQN算法曲線隨著迭代次數(shù)的增加遞減，逐漸收斂。算法訓(xùn)練200個周期，獲得了訓(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)生概率對平均能耗的影響如圖4所示，可見系統(tǒng)能耗隨著任務(wù)產(chǎn)生概率的增加而增加，這是由于任務(wù)數(shù)量的增大，導(dǎo)致系統(tǒng)需要更大的能耗開銷，從而使得系統(tǒng)能耗增加。本地計(jì)算、隨機(jī)卸載與D2D卸載算法系統(tǒng)能耗較高，DDQN算法的實(shí)驗(yàn)結(jié)果更優(yōu)。

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

不同時隙大小對本文方案系統(tǒng)能耗的影響情況如圖5所示?？梢钥闯?，隨著時隙的增大，任務(wù)量減少，從而系統(tǒng)能耗不斷降低。

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

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

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

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

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

5 結(jié)束語

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