李 斌,徐天成

(1.南京信息工程大學(xué) 計算機(jī)學(xué)院,南京210044;2.南京信息工程大學(xué) 江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心,南京 210044)

0 引 言

隨著5G、物聯(lián)網(wǎng)和人工智能的融合與快速發(fā)展,以及日益增長的用戶資源需求,利用移動邊緣計算(Mobile Edge Computing,MEC)在網(wǎng)絡(luò)邊緣卸載任務(wù),已成為解決此類問題的一個出色的方案[1-2]。其優(yōu)勢在于能夠為網(wǎng)絡(luò)邊緣用戶提供近距離通信,并且有效降低了計算密集型應(yīng)用的通信開銷和計算時延,同時有利于緩解網(wǎng)絡(luò)和數(shù)據(jù)中心的計算壓力[3]。物聯(lián)網(wǎng)應(yīng)用程序中的計算任務(wù)之間普遍存在一定的相關(guān)性[4],如果當(dāng)前任務(wù)的前驅(qū)任務(wù)沒有被優(yōu)先執(zhí)行,那么調(diào)度該任務(wù)會產(chǎn)生額外的等待時間甚至死鎖,這將對系統(tǒng)的實(shí)時性和穩(wěn)定性產(chǎn)生較大影響。通常,移動終端應(yīng)用軟件可以被建模為有向無環(huán)圖(Directed Acyclic Graph,DAG),以實(shí)現(xiàn)計算密集型應(yīng)用的調(diào)度問題。

為了解決用戶資源和計算能力有限的問題,研究者提出引入終端直通(Device-to-Device,D2D)技術(shù)的卸載模式作為MEC的有效補(bǔ)充[5],旨在將豐富的計算和存儲資源協(xié)同控制和管理起來,以完成密集的計算任務(wù)[6-8]。同時,未來物聯(lián)網(wǎng)、邊緣計算網(wǎng)絡(luò)等新網(wǎng)絡(luò)場景的快速發(fā)展,智能設(shè)備數(shù)量和用戶需求也隨之激增,如何將有限的計算、帶寬和存儲等網(wǎng)絡(luò)資源充分利用起來,并在大量的終端數(shù)據(jù)上實(shí)現(xiàn)智能管控,以獲得更高效的網(wǎng)絡(luò)性能和服務(wù)質(zhì)量,是實(shí)現(xiàn)這些5G應(yīng)用需要解決的熱點(diǎn)研究問題之一。

關(guān)于D2D和MEC一體化的工作已有相關(guān)研究[9-13],但主要考慮了任務(wù)的時延與能耗,鮮少考慮服務(wù)器有限資源下任務(wù)具有相關(guān)性的卸載情況。同時,因其沒有考慮用戶移動性與任務(wù)多樣性,難以適應(yīng)動態(tài)變化的物聯(lián)網(wǎng)場景。

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

與現(xiàn)有文獻(xiàn)不同,本文提出了一種結(jié)合移動邊緣計算與無線傳能的物聯(lián)網(wǎng)架構(gòu),建立D2D輔助移動用戶卸載數(shù)據(jù)模型。這種架構(gòu)聯(lián)合優(yōu)化任務(wù)調(diào)度和卸載策略問題,最大程度地降低了系統(tǒng)執(zhí)行時延。本文的貢獻(xiàn)主要體現(xiàn)在三個方面:一是對具有多用戶的MEC系統(tǒng)的任務(wù)調(diào)度和卸載問題進(jìn)行了建模,研究了任務(wù)調(diào)度和任務(wù)卸載策略的聯(lián)合問題,目標(biāo)為最小化系統(tǒng)執(zhí)行時延;二是提出了一種基于Dueling Double DQN(D3QN)的計算卸載算法,以實(shí)現(xiàn)動態(tài)任務(wù)卸載與資源智能管控;三是提出了基于改進(jìn)的深度優(yōu)先搜索(Depth First Search,DFS)算法解決了任務(wù)卸載調(diào)度問題。仿真結(jié)果證實(shí)了本文所提算法的可靠性和有效性。

1 基于相關(guān)性的任務(wù)調(diào)度算法

1.1 任務(wù)的相關(guān)性建模

任務(wù)的相關(guān)性通常用一個有向無環(huán)圖表示,如圖1所示。G=〈V,E〉為一個二元組,其中,V是任務(wù)節(jié)點(diǎn)的集合,vi表示第i個任務(wù),E?V×V表示有向邊集合。兩個任務(wù)節(jié)點(diǎn)之間存在有向邊表示這兩個任務(wù)具有相關(guān)性,且發(fā)出有向邊的任務(wù)為有向邊指向任務(wù)的前驅(qū)任務(wù),后繼任務(wù)只有在其前驅(qū)任務(wù)全部完成后才可執(zhí)行。在t時刻,移動終端將任務(wù)信息和用戶坐標(biāo)發(fā)送給基站,基站根據(jù)用戶的數(shù)據(jù)和位置信息使用基于任務(wù)相關(guān)性的D3QN算法訓(xùn)練移動終端的卸載策略,訓(xùn)練完成后智能體將卸載決策發(fā)送給移動終端,移動終端根據(jù)卸載策略來判斷任務(wù)的執(zhí)行模式。

圖1 任務(wù)執(zhí)行架構(gòu)

1.2 任務(wù)的優(yōu)先級

(1)

pi數(shù)值越大,任務(wù)的優(yōu)先級越高,具體過程如基于改進(jìn)的DFS任務(wù)調(diào)度算法(算法1)所示。首先訪問圖中某一未訪問的頂點(diǎn)v1,然后由v1出發(fā),訪問與v1鄰接且未被訪問的任一頂點(diǎn)v2,再訪問與v2鄰接且未被訪問的任一頂點(diǎn)v3,重復(fù)上述過程。當(dāng)不能再繼續(xù)向下訪問時,依次退回到最近被訪問的頂點(diǎn),若它還有鄰接頂點(diǎn)未被訪問過,則從該點(diǎn)開始繼續(xù)上述搜索過程,直到圖中所有頂點(diǎn)均被訪問過為止。

算法1具體描述如下:

輸入:DAG圖

輸出:拓?fù)渑判蛑蟮捻旤c(diǎn)

有向圖中具有多個入度為0的頂點(diǎn)時,選擇優(yōu)先級高的頂點(diǎn)v1進(jìn)棧;

依次從v1的各個未被訪問的鄰接點(diǎn)進(jìn)行深度優(yōu)先搜索遍歷圖;

如果s棧為空,則失敗退出,否則繼續(xù);

從棧頂取出頂點(diǎn)到數(shù)組中,然后將該節(jié)點(diǎn)所有連接的節(jié)點(diǎn)的入度都減1;

如果當(dāng)前頂點(diǎn)的出度為0或已訪問,則回退一步并轉(zhuǎn)向3;

繼續(xù)根據(jù)DFS算法遍歷后面的節(jié)點(diǎn);

2 系統(tǒng)模型

本文考慮一個支持無線能量獲取D2D通信的協(xié)同MEC網(wǎng)絡(luò),其中空閑和資源充裕的設(shè)備(如筆記本、平板電腦、手機(jī)等可以作為邊緣節(jié)點(diǎn))通過和資源有限的用戶設(shè)備(User Device,UD)建立直接的D2D鏈路,以促進(jìn)計算卸載。該系統(tǒng)模型由k個用戶、多天線的基站和M個D2D設(shè)備組成,移動用戶的任務(wù)沿著用戶的軌跡被卸載到D2D設(shè)備或基站上,如圖2所示。

圖2 系統(tǒng)模型

本文假設(shè)UDk以一定的速度和角度步行,同時,UDk有I個相互依賴的計算密集型任務(wù)要執(zhí)行,用集合I={1,2,…,i}表示。在UDk行走的道路上,分布著筆記本、平板電腦、手機(jī)等M個D2D設(shè)備,用集合M={1,2,…,m}表示。考慮一種網(wǎng)絡(luò)輔助架構(gòu),其中基站擁有全局網(wǎng)絡(luò)信息,包括關(guān)于用戶移動性和任務(wù)的細(xì)節(jié)。對于任務(wù)卸載,UDk可以在基站的幫助下通過建立直接的D2D鏈路連接到附近的D2D設(shè)備。基站可檢測出UDk的位置,以便將其任務(wù)調(diào)度到D2D設(shè)備,使計算卸載總時延最小化。為了簡化計算模型,UDk和D2D設(shè)備均只考慮裝配一根天線。為了避免用戶數(shù)據(jù)卸載之間的干擾,假設(shè)所考慮的網(wǎng)絡(luò)以時分多址方式工作。時間塊T被劃分為I個階段,其中,ατ為無線能量傳輸,(1-α)τ為分配給UDk計算卸載的時間。

2.1 能量捕獲模型

在能量捕獲階段,基站以功率Pk,n來廣播能量射頻信號,同時,k個移動終端從射頻信號中捕獲能量。在時間間隔為ατ的無線能量傳輸中,UDk收獲的能量為

Ek,i=ηPk,ihk,iατ,?i∈N。

(2)

式中:常數(shù)η∈(0,1)表示能量轉(zhuǎn)換效率因子;Pk,n表示基站在第i個任務(wù)給用戶k發(fā)射的信號功率;hk,n表示UDk和基站之間在第i個任務(wù)的無線信道增益。由于信道互易性,假設(shè)上行鏈路和下行鏈路的信道增益相同。依據(jù)文獻(xiàn)[16-17],本文采用了式(2)所示的線性能量捕獲模型。

2.2 用戶移動模型

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

2.3 任務(wù)卸載模型

在持續(xù)時間T內(nèi),每個用戶以一個確定概率隨機(jī)生成I個任務(wù),k個用戶同時進(jìn)行執(zhí)行任務(wù)。本文用Υk,n來表示是否有任務(wù)請求,Υk,n=1表示用戶k在第n時隙有一個任務(wù)請求,Υk,n=0表示用戶k在第n時隙沒有任務(wù)請求。UDk的計算任務(wù)可由TKk,i(ci,ai,di,pi)表示,其中,ci表示任務(wù)卸載時本地設(shè)備需向外傳輸?shù)臄?shù)據(jù)量,ai表示處理該任務(wù)所需的機(jī)器語言指令數(shù)。對于計算密集型任務(wù),每個任務(wù)必須在di內(nèi)完成,所以每個任務(wù)執(zhí)行時間應(yīng)該小于時隙長度τ。

(3)

(4)

UD在本地計算模式下的能耗定義為

(5)

(6)

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

(7)

因此,UDk在D2D卸載模式下的處理時延定義為

(8)

UDk在D2D卸載模式下的計算能耗定義為

(9)

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

(10)

(11)

(12)

UDk在D2D輔助邊緣計算模式下的上傳任務(wù)能耗定義為

(13)

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

(14)

(15)

3 問題描述

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

(16)

為了減少卸載時延,利用UDk移動過程中不同時隙的位置信息進(jìn)行任務(wù)卸載決策,故本文的研究問題形式化描述如下:

(17)

式(17)給出了以任務(wù)卸載決策為優(yōu)化變量的目標(biāo)函數(shù);約束C1表明用戶最多只能選擇一種模式來完成它的任務(wù);約束C2表明采集的能量需要大于任務(wù)計算所需的能量;約束C3表明任務(wù)只能全部卸載;約束C4表明分配給移動用戶的計算資源不能超過MEC服務(wù)器擁有的資源;約束C5表明如果用戶選擇3種模式中的一種來完成它的任務(wù),其時延不能超過最大時延;約束C6表明移動用戶最多同時連接一個D2D設(shè)備;約束C7中表示UDk和D2D的傳輸功率以及MEC服務(wù)器的計算資源分別是非負(fù)的?？梢?優(yōu)化問題(17)含有多個離散的決策變量,是一個混合整數(shù)非線性規(guī)劃問題,很難快速求得最優(yōu)解。本文提出基于深度強(qiáng)化學(xué)習(xí)的D3QN算法來解決此問題。

4 基于深度強(qiáng)化學(xué)習(xí)的算法設(shè)計

本文采用基于D3QN的計算卸載算法求解建立的D2D通信的協(xié)同MEC網(wǎng)絡(luò)中優(yōu)化任務(wù)卸載策略問題,求解目標(biāo)是通過優(yōu)化卸載決策變量,最小化系統(tǒng)執(zhí)行時延。為解決具有高維狀態(tài)空間的環(huán)境問題,深度強(qiáng)化學(xué)習(xí)將深度神經(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)境,由于它是通過計算每個動作的Q值進(jìn)行決策,所以會在某些條件下高估動作值。因此,本文提出使用D3QN方案是一種有效的改進(jìn),通過在DQN和DDQN的基礎(chǔ)上引入競爭網(wǎng)絡(luò)結(jié)構(gòu),神經(jīng)網(wǎng)絡(luò)不再直接輸出Q值而是輸出狀態(tài)價值函數(shù)和優(yōu)勢函數(shù)。解決Q值過估計問題的同時,擬合獲得更準(zhǔn)確的Q值。

4.1 基于D3QN的計算卸載

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

狀態(tài)空間:S={G,x,y},G代表已調(diào)度完成的任務(wù)序列,UDk在第t個時隙內(nèi)的狀態(tài)為其自身的位置(xk,t為UDk的橫坐標(biāo),yk,t為UDk的縱坐標(biāo))。

(18)

D3QN中使用狀態(tài)價值和動作優(yōu)勢來聚合Q值得網(wǎng)絡(luò)設(shè)計,可以降低不同狀態(tài)下動作的估計誤差,即

(19)

式中:A(s,a)為動作優(yōu)勢函數(shù);|A|為動作維度,V(s)為狀態(tài)價值函數(shù)。

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

(20)

然后利用選取出來的動作在目標(biāo)網(wǎng)絡(luò)里面去計算目標(biāo)Q值,即

(21)

式中:λ為折扣因子。綜合定義為

(22)

L(θ)=

(23)

4.2 基于D3QN的時間最小化算法

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

圖3 D3QN算法流程

基于D3QN的時延最小化算法(算法2)具體描述如下:

輸入:UD初始位置,已調(diào)度完成的任務(wù)序列

輸出:移動過程中使得系統(tǒng)時延最小化的卸載決策

2.for episode =1:N

3. 獲取初始狀態(tài)s;

4. for episode =0:T-1;

5. 將st輸入到預(yù)測網(wǎng)絡(luò)中,采用ε-greedy獲得動作at;

6. 執(zhí)行動作at,利用式(18)計算即時獎勵rt;

7. 然后獲得即時獎勵rt和新狀態(tài)st+1;

8. 存儲記憶(st,at,rt,st+1)到D;

9. 從D隨機(jī)抽取K個樣本;

10. 根據(jù)式(18)計算目標(biāo)Q值;

11. 根據(jù)式(23)計算損失函數(shù),反向傳播更新θ;

12. 更新目標(biāo)網(wǎng)絡(luò)參數(shù);

13. end for

14.end for

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

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

5.2 數(shù)值分析

為了充分驗證本文所提算法的有效性,與貪心算法、Q-learning和DQN 3種算法進(jìn)行了性能對比。

圖4給出了在取不同折扣因子時D3QN算法隨時間周期變化的收斂圖。折扣因子是對未來獎勵的衰減值,代表了當(dāng)前獎勵與未來獎勵的重要性。λ越大則智能體越重視歷史經(jīng)驗,歷史經(jīng)驗對未來獎勵的影響越大。當(dāng)λ=0.5和λ=0.99時,獎勵值差別較大,原因在于過大或過低的折扣因子不利于智能體的探索。D3QN算法曲線隨著迭代次數(shù)的增加逐漸遞減,在經(jīng)過大約50個時間周期后趨近于收斂。算法訓(xùn)練200個周期,獲得了訓(xùn)練回報。

圖4 所提算法收斂性

圖5給出了任務(wù)執(zhí)行時延和用戶數(shù)量之間的變化曲線。通過模擬2～10個用戶數(shù)量(以2遞增),比較4種算法的任務(wù)執(zhí)行時延。如圖5所示,系統(tǒng)時延隨著用戶個數(shù)的增加而增大。這是由于用戶數(shù)的增加,導(dǎo)致系統(tǒng)需要更大的時延開銷,從而使得任務(wù)執(zhí)行時延增加?？梢杂^察到,貪心算法、Q-learning和DQN三種算法系統(tǒng)時延較高,本文所提出的D3QN算法的實(shí)驗結(jié)果更優(yōu)。

圖5 任務(wù)執(zhí)行時延隨用戶數(shù)量的變化

圖6反映了不同移動速度對系統(tǒng)時延的影響情況。觀察圖6可知,隨著用戶移動速度的增大,傳輸時延增加,從而系統(tǒng)時延不斷增加。分別模擬了1～5 m的移動速度(以1遞增),比較4種算法的執(zhí)行時延。當(dāng)用戶移動速度大于3 m/s時,本文提出的D3QN算法達(dá)到的時延效果比貪心算法、Q-learning和DQN算法要好。

圖6 不同移動速度下的算法性能對比圖

為了進(jìn)一步驗證本文提出的D2D協(xié)同計算的性能,圖7給出了D2D數(shù)量對不同方案的任務(wù)執(zhí)行時延的影響情況。可以看出,隨著D2D數(shù)量的增加,任務(wù)執(zhí)行時延在不斷減少。這是因為D2D數(shù)量的增加豐富了用戶卸載的選擇,可以有效減少傳輸時延。

圖7 任務(wù)執(zhí)行時延與D2D數(shù)量的關(guān)系

6 結(jié)束語

本文提出了一種融合D2D的兩層邊緣計算架構(gòu),并引入D2D協(xié)作中繼技術(shù)用于輔助用戶接入遠(yuǎn)端邊緣服務(wù)器?？紤]到用戶移動性、任務(wù)相關(guān)性和任務(wù)卸載時延約束的特性,將任務(wù)卸載問題表述為時延最小化的混合整數(shù)非線性規(guī)劃問題,并進(jìn)一步提出了基于深度強(qiáng)化學(xué)習(xí)的D3QN算法來實(shí)時優(yōu)化任務(wù)卸載決策變量。仿真結(jié)果表明,所提出的D2D協(xié)同計算方案在計算資源緊張的情況下,能有效降低移動用戶的任務(wù)執(zhí)行時延且優(yōu)化決策的收斂性較好。在未來的工作中,將研究在對任務(wù)調(diào)度的同時考慮對任務(wù)節(jié)點(diǎn)的調(diào)度。