崔 碩，覃少華，謝志斌，張家豪，卞圣強(qiáng)

(廣西師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，廣西 桂林 541004)

0 引言

移動(dòng)邊緣計(jì)算(MEC，mobile edge computing)技術(shù)通過在網(wǎng)絡(luò)邊緣部署計(jì)算和存儲(chǔ)資源，將云計(jì)算的部分能力下沉到無線接入網(wǎng)等靠近用戶的網(wǎng)絡(luò)邊緣，就近為用戶提供計(jì)算和存儲(chǔ)服務(wù)，降低用戶的等待時(shí)延，同時(shí)減輕了骨干網(wǎng)的負(fù)擔(dān)，防止網(wǎng)絡(luò)擁塞的發(fā)生[1-3]。計(jì)算卸載是MEC的關(guān)鍵技術(shù)[4]，用戶設(shè)備可以通過計(jì)算卸載技術(shù)將計(jì)算密集型的應(yīng)用整體或部分地卸載到MEC服務(wù)器上運(yùn)行，顯著降低了處理時(shí)延和能耗。

細(xì)粒度的計(jì)算卸載將應(yīng)用進(jìn)一步分割為多個(gè)任務(wù)，使得任務(wù)間的并行卸載處理成為可能[5]。由于在應(yīng)用程序中一個(gè)任務(wù)經(jīng)常需要其它任務(wù)的輸出數(shù)據(jù)作為自己的輸入，因而不同任務(wù)間是具有依賴關(guān)系的。現(xiàn)有文獻(xiàn)大多使用有向無環(huán)圖(DAG，directed acyclic graph)對(duì)具有依賴關(guān)系的計(jì)算卸載問題進(jìn)行建模，但是由于DAG結(jié)構(gòu)的復(fù)雜性和多樣性，基于DAG的計(jì)算卸載問題是困難的[5-7]。受制于問題的復(fù)雜性，文獻(xiàn)[8-9]大多使用啟發(fā)式算法對(duì)這一問題進(jìn)行求解。然而，啟發(fā)式算法難以滿足MEC環(huán)境下的實(shí)時(shí)動(dòng)態(tài)決策的要求[10]，同時(shí)也缺乏通用性。針對(duì)這一問題，文獻(xiàn)[10-12]提出通過深度強(qiáng)化學(xué)習(xí)(DRL，deep reinforcement learning)算法求解DAG任務(wù)卸載調(diào)度決策的方法，利用DRL算法較強(qiáng)的表示能力[13]對(duì)DAG卸載決策問題巨大的狀態(tài)空間進(jìn)行學(xué)習(xí)，與此同時(shí)DRL算法把最大化長(zhǎng)期獎(jiǎng)勵(lì)作為目標(biāo)，可以避免卸載決策算法陷入局部最優(yōu)，更能求得全局最優(yōu)解。

然而，使用DRL算法解決基于DAG的卸載調(diào)度問題時(shí)會(huì)遇到一個(gè)棘手的問題，那就是DRL算法所使用的神經(jīng)網(wǎng)絡(luò)只適用于處理歐氏空間數(shù)據(jù)[14]，無法處理非歐式空間的數(shù)據(jù)，因而對(duì)這一卸載調(diào)度問題中的DAG圖無能為力。為了能將DAG圖輸入DRL算法的神經(jīng)網(wǎng)絡(luò)中，文獻(xiàn)[15]采取嵌入的方法，把DAG圖中的每個(gè)任務(wù)節(jié)點(diǎn)的本地執(zhí)行時(shí)延、MEC服務(wù)器執(zhí)行時(shí)延和前驅(qū)后繼任務(wù)的索引等信息構(gòu)成一個(gè)定長(zhǎng)的任務(wù)嵌入向量，然后輸入到DRL算法的神經(jīng)網(wǎng)絡(luò)中。這種方法中每個(gè)任務(wù)的嵌入向量是定長(zhǎng)的，同時(shí)由于嵌入向量的長(zhǎng)度直接決定了DRL算法中神經(jīng)網(wǎng)絡(luò)的規(guī)模，因而嵌入向量的長(zhǎng)度不能過長(zhǎng)。但是對(duì)于很多DAG結(jié)構(gòu)復(fù)雜的應(yīng)用來說其中核心任務(wù)的前驅(qū)后繼任務(wù)的數(shù)量可能是非常大的，這將導(dǎo)致DAG圖轉(zhuǎn)換為嵌入向量的過程會(huì)丟失很多DAG自身的結(jié)構(gòu)信息，從而使制定的卸載策略不夠準(zhǔn)確。鑒于圖神經(jīng)網(wǎng)絡(luò)(graph neural network，GNN)所表現(xiàn)出的對(duì)圖結(jié)構(gòu)數(shù)據(jù)出色的處理能力[16]，本文針對(duì)DAG任務(wù)卸載調(diào)度問題提出一種新穎的將GNN和DRL算法相結(jié)合的方案，收到了很好的效果。

本文提出的方案基于DRL中的DQN算法進(jìn)行了修改以使其適用于處理DAG任務(wù)的卸載調(diào)度問題，具體的，本文使用GNN替代DQN算法中的標(biāo)準(zhǔn)神經(jīng)網(wǎng)絡(luò)來評(píng)估每個(gè)卸載動(dòng)作的Q值。在GNN的結(jié)構(gòu)方面，本文借鑒了消息傳遞網(wǎng)絡(luò)(MPNN，message passing neural network)的結(jié)構(gòu)[17]，由于DAG圖是有向的和無環(huán)的，本文針對(duì)DAG圖的結(jié)構(gòu)特點(diǎn)設(shè)計(jì)了一種有向無環(huán)圖神經(jīng)網(wǎng)絡(luò)(DAGNN，directed acyclic graph neural network)用來更有效地提取DAG圖的信息。仿真實(shí)驗(yàn)表明，本文提出的方案具有良好的收斂性，并在不同的節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)環(huán)境下收到了優(yōu)于其它對(duì)比算法的調(diào)度效果。

1 系統(tǒng)結(jié)構(gòu)及原理

下面首先給出整個(gè)系統(tǒng)的實(shí)現(xiàn)結(jié)構(gòu)流程圖，如圖1所示，系統(tǒng)首先讀取待調(diào)度應(yīng)用的DAG結(jié)構(gòu)圖，以及應(yīng)用中每個(gè)任務(wù)的本地執(zhí)行時(shí)延和在MEC服務(wù)器上執(zhí)行的傳輸時(shí)延和計(jì)算時(shí)延。隨后系統(tǒng)初始化DAGNN的參數(shù)和每個(gè)節(jié)點(diǎn)的輸入狀態(tài)。在對(duì)應(yīng)用進(jìn)行卸載調(diào)度時(shí)，系統(tǒng)首先計(jì)算每個(gè)任務(wù)的最晚開始執(zhí)行時(shí)間，并按照升序進(jìn)行排列，從而得到任務(wù)的優(yōu)先級(jí)序列,之后系統(tǒng)對(duì)所有任務(wù)按照優(yōu)先級(jí)的順序依次進(jìn)行調(diào)度。在對(duì)每個(gè)任務(wù)進(jìn)行調(diào)度時(shí)系統(tǒng)首先調(diào)用下文的算法1衡量每個(gè)動(dòng)作的q值，之后根據(jù)貪心策略選擇要采取的動(dòng)作，并更新卸載動(dòng)作序列。隨后系統(tǒng)收到環(huán)境反饋的即時(shí)獎(jiǎng)勵(lì)r，并進(jìn)入下一狀態(tài)s′,與此同時(shí)系統(tǒng)將四元組(s,a,r,s′)存入經(jīng)驗(yàn)回放緩存區(qū)，并定時(shí)從經(jīng)驗(yàn)回放緩存區(qū)中取出一些元組數(shù)據(jù)通過隨機(jī)梯度下降法更新DAGNN的參數(shù)。

圖1 系統(tǒng)實(shí)現(xiàn)結(jié)構(gòu)流程圖

2 系統(tǒng)模型

圖2 系統(tǒng)模型

2.1 通信模型

用戶設(shè)備UE和每個(gè)微基站之間通過無線鏈路相連，我們假設(shè)在任務(wù)的執(zhí)行過程中UE與MEC服務(wù)器之間的信道保持穩(wěn)定，根據(jù)香農(nóng)公式可得到用戶設(shè)備UE到MEC服務(wù)器間鏈路的傳輸速率為：

(1)

其中:參數(shù)B代表用戶設(shè)備UE可用的信道帶寬，p0代表用戶設(shè)備UE的發(fā)送功率，gn表示UE與MEC服務(wù)器n之間的信道增益，N0表示高斯噪聲功率。

2.2 計(jì)算模型

用戶設(shè)備UE在同一時(shí)隙內(nèi)只產(chǎn)生一個(gè)計(jì)算密集型的應(yīng)用，它被進(jìn)一步分割為多個(gè)相互之間具有依賴關(guān)系的任務(wù)，每個(gè)處理單元在同一時(shí)隙內(nèi)只能處理一個(gè)任務(wù)，每個(gè)任務(wù)只能被一個(gè)處理單元所處理。下面分別討論任務(wù)在本地計(jì)算和MEC服務(wù)器上計(jì)算的時(shí)延。

①本地計(jì)算：

用f0表示用戶設(shè)備UE自身的計(jì)算能力，則任務(wù)i在UE本地計(jì)算的計(jì)算時(shí)延可以表示為：

(2)

由于本地計(jì)算無需進(jìn)行數(shù)據(jù)的傳輸所以不存在通信時(shí)延，所以任務(wù)i在本地計(jì)算的全部時(shí)延為：

(3)

②MEC服務(wù)器計(jì)算：

當(dāng)任務(wù)i被調(diào)度為MEC服務(wù)器n計(jì)算時(shí)，數(shù)據(jù)需要在用戶設(shè)備UE和MEC服務(wù)器之間傳輸，因而MEC服務(wù)器計(jì)算情景下的時(shí)延由兩部分構(gòu)成：傳輸和MEC服務(wù)器執(zhí)行。特別地，由于任務(wù)被執(zhí)行所產(chǎn)生的計(jì)算結(jié)果的數(shù)據(jù)量往往很小，類似于現(xiàn)有大多數(shù)文獻(xiàn)的假設(shè)[8,12,18]，本文不考慮計(jì)算結(jié)果的傳輸時(shí)延。由此可得任務(wù)i在MEC服務(wù)器n上計(jì)算的時(shí)延為：

(4)

2.3 依賴關(guān)系模型

本文將應(yīng)用中不同任務(wù)間的依賴關(guān)系建模為一個(gè)DAG，表示為G=(V,E)，其中V表示DAG中節(jié)點(diǎn)的集合，每個(gè)節(jié)點(diǎn)i∈V表示UE運(yùn)行的應(yīng)用中的一個(gè)任務(wù)；E表示DAG中邊的集合，每條邊e(i,j)∈E表示任務(wù)i和j之間的依賴關(guān)系，即任務(wù)j需要任務(wù)i的輸出數(shù)據(jù)作為自己的輸入，并稱任務(wù)i為j的前驅(qū)，任務(wù)j為i的后繼，一個(gè)任務(wù)只有在其所有前驅(qū)任務(wù)完成后才能開始執(zhí)行。在一個(gè)DAG中，沒有前驅(qū)任務(wù)的任務(wù)被稱為入口任務(wù)，沒有后繼任務(wù)的任務(wù)被稱為出口任務(wù)，一個(gè)應(yīng)用允許同時(shí)有多個(gè)入口任務(wù)和出口任務(wù)。

在應(yīng)用開始卸載調(diào)度后，用AFTn,i表示任務(wù)i在處理單元n上執(zhí)行時(shí)的實(shí)際完成時(shí)間。由于一個(gè)任務(wù)只有在其所有直接前驅(qū)任務(wù)都被執(zhí)行完成后才能進(jìn)入準(zhǔn)備就緒狀態(tài)，所以任務(wù)i的就緒時(shí)間可以表示為：

(5)

其中:pre(i)表示任務(wù)i所有直接前驅(qū)任務(wù)的集合。然而，當(dāng)一個(gè)任務(wù)被分配至處理單元n上執(zhí)行時(shí)該處理單元可能并未處于空閑狀態(tài)，所以任務(wù)的就緒時(shí)間并不一定是它真正開始被執(zhí)行的時(shí)間。我們用ATn,i表示處理單元n最早可以為任務(wù)i服務(wù)的時(shí)間，容易得到：

ESTn,i=max{RTi,ATn,i}

(6)

用ETn,i表示任務(wù)i在處理單元n上執(zhí)行所花費(fèi)的時(shí)間，它可以表示為：

(7)

由于用戶設(shè)備UE的應(yīng)用都是時(shí)延敏感型的，所以應(yīng)用存在一個(gè)最大容忍時(shí)延。我們定義tmax為應(yīng)用的最大容忍時(shí)延，它可以看作是應(yīng)用的DAG圖中出口任務(wù)的最晚執(zhí)行完成時(shí)間。用LFTn,i表示 DAG圖中任務(wù)i的最晚執(zhí)行完成時(shí)間，它可以從應(yīng)用的出口任務(wù)逐級(jí)往上遞歸地求出,則LFTn,i可以表示為：

(8)

在定義了任務(wù)的最晚完成時(shí)間后我們可以相應(yīng)地得到任務(wù)的最晚開始執(zhí)行時(shí)間，它可以表示為：

(9)

2.4 優(yōu)化目標(biāo)制定

本文以使任務(wù)的時(shí)延最小為優(yōu)化目標(biāo)，首先定義兩個(gè)0-1變量xn,i和yh,i，它們的取值分別為：

(10)

(11)

基于上文的定義，本文的優(yōu)化問題可表示為：

(12)

s.t.ESTn,i≥xn,i·yn,i·AFTh

(12a)

xn,i∈{0,1},?n∈N,i∈V

(12b)

(12c)

其中:約束式(12a)表示任務(wù)i的最早開始執(zhí)行時(shí)間不能早于其直接前驅(qū)任務(wù)h的實(shí)際完成時(shí)間，約束式(12b)和(12c)表示同一任務(wù)只能在同一個(gè)處理單元上計(jì)算。

3 基于DRL和GNN的DAG任務(wù)卸載調(diào)度算法

由于DAG任務(wù)調(diào)度問題的復(fù)雜性，文獻(xiàn)[11]等提出使用深度強(qiáng)化學(xué)習(xí)的方法進(jìn)行卸載決策。但由于DRL算法無法處理諸如DAG圖一類的圖結(jié)構(gòu)的信息，文獻(xiàn)[22]采用節(jié)點(diǎn)嵌入的方式將DAG圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)信息轉(zhuǎn)化為任務(wù)序列輸入到DRL算法的神經(jīng)網(wǎng)絡(luò)中。但這種方式會(huì)損失很多DAG圖的結(jié)構(gòu)信息。鑒于圖神經(jīng)網(wǎng)絡(luò)在處理圖結(jié)構(gòu)數(shù)據(jù)時(shí)的優(yōu)異表現(xiàn)，本文提出將圖神經(jīng)網(wǎng)絡(luò)(GNN，graph neural network)與DRL算法相結(jié)合用于解決DAG任務(wù)的卸載調(diào)度問題。與此同時(shí)由于DAG圖是有向圖，本文針對(duì)DAG圖的結(jié)構(gòu)特點(diǎn)設(shè)計(jì)了一種有向圖神經(jīng)網(wǎng)絡(luò)(DAGNN)用于提取DAG圖的信息，取得了較好的效果。

3.1 任務(wù)優(yōu)先級(jí)

為了簡(jiǎn)化卸載調(diào)度決策過程同時(shí)也滿足任務(wù)之間的依賴性，與其它基于DAG圖的任務(wù)卸載調(diào)度問題文獻(xiàn)一樣[7,19]，本文首先確定任務(wù)的調(diào)度順序。由于計(jì)算卸載的任務(wù)大多是時(shí)延敏感型的，所以在確定任務(wù)調(diào)度的優(yōu)先級(jí)時(shí)應(yīng)主要考慮任務(wù)的時(shí)延約束。如上文所述，任務(wù)的最晚完成時(shí)間可以看作是每個(gè)任務(wù)的時(shí)延約束，每個(gè)任務(wù)的最晚完成時(shí)間可以從出口任務(wù)開始逐層向上遞歸地求出，基于此我們可求得所有任務(wù)的優(yōu)先級(jí)。

3.2 MDP的構(gòu)造

3.2.1 狀態(tài)空間

MDP的狀態(tài)空間應(yīng)該能夠反映當(dāng)前應(yīng)用的DAG結(jié)構(gòu)、已經(jīng)完成調(diào)度決策的任務(wù)情況等，基于此狀態(tài)空間應(yīng)包括以下部分：①當(dāng)前已完成調(diào)度的任務(wù)序列；②已完成調(diào)度任務(wù)的卸載動(dòng)作的集合；③DAG圖。每當(dāng)完成一個(gè)任務(wù)節(jié)點(diǎn)的調(diào)度，系統(tǒng)更新已完成調(diào)度任務(wù)序列及其動(dòng)作集，并進(jìn)入下一狀態(tài)。

3.2.2 動(dòng)作空間

動(dòng)作空間中的動(dòng)作表示的是G中每個(gè)任務(wù)的卸載調(diào)度決策，由于本文中每個(gè)任務(wù)都可以被分配給N個(gè)處理單元中的任意一個(gè)進(jìn)行執(zhí)行且分配給每個(gè)處理單元的概率是相同的，所以動(dòng)作空間具體可以表示為：

A={0,1,2,…,n,…N}

其中:動(dòng)作a={0}表示任務(wù)被分配在本地執(zhí)行，a={n}表示任務(wù)被分配給了第n臺(tái)MEC服務(wù)器執(zhí)行。

智能體在執(zhí)行選定的動(dòng)作a后，環(huán)境將會(huì)反饋給智能體一個(gè)即時(shí)獎(jiǎng)勵(lì)r，在本章中即時(shí)獎(jiǎng)勵(lì)被設(shè)定為任務(wù)節(jié)點(diǎn)調(diào)度前后應(yīng)用執(zhí)行時(shí)延的差值，特別地，如果任務(wù)的執(zhí)行時(shí)間超過了其最大容忍時(shí)延，即時(shí)獎(jiǎng)勵(lì)被設(shè)定為0。

3.3 有向無環(huán)圖神經(jīng)網(wǎng)絡(luò)

由于DAG圖是有向的、無環(huán)的，所以我們針對(duì)DAG的結(jié)構(gòu)特性對(duì)標(biāo)準(zhǔn)的GNN做了改動(dòng)使其能夠處理DAG圖。由于文獻(xiàn)[16]歸納并抽象出各種GNN模型的共性，提出了一種通用的GNN處理框架信息傳遞網(wǎng)絡(luò)(MPNN，message passing neural network)，鑒于其在各領(lǐng)域的應(yīng)用中展現(xiàn)出的良好的GNN信息提取能力[17]，本文的DAGNN借鑒了MPNN的基本結(jié)構(gòu)，具體的結(jié)構(gòu)如圖3所示。

圖3 DAGNN結(jié)構(gòu)圖

DAGNN中每個(gè)節(jié)點(diǎn)代表應(yīng)用的一個(gè)任務(wù)，共包含L層網(wǎng)絡(luò)。DAGNN通過聚合函數(shù)對(duì)每個(gè)節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)表示進(jìn)行聚合，并把得到的聚合信息用連結(jié)函數(shù)與該節(jié)點(diǎn)在當(dāng)前網(wǎng)絡(luò)層的節(jié)點(diǎn)表示進(jìn)行連結(jié)，用以更新節(jié)點(diǎn)表示。在所有節(jié)點(diǎn)間迭代進(jìn)行這一過程，最后使用最大池化的方法將所有網(wǎng)絡(luò)層的出口節(jié)點(diǎn)的節(jié)點(diǎn)表示進(jìn)行聚合，通過讀出函數(shù)將聚合后的信息讀出，生成最終的圖表示。DAGNN總的計(jì)算過程如式(13)和式(14)所示：

(13)

(14)

由于每個(gè)任務(wù)的執(zhí)行時(shí)延只受其前驅(qū)任務(wù)的影響，因此我們?cè)谶M(jìn)行信息聚合時(shí)只考慮節(jié)點(diǎn)的前驅(qū)任務(wù)。除此之外，本文在聚合函數(shù)計(jì)算過程中引入注意力機(jī)制以便更好地聚合相關(guān)節(jié)點(diǎn)的信息,具體的計(jì)算方式如式(15)所示：

(15)

(16)

(17)

是儀也，不可謂禮。禮，所以守其國(guó)家，行其政令，無失其民者也。今政令在家，不能取也。有子家羈，弗能用也。奸大國(guó)之盟，陵虐小國(guó)。利人之難，不知其私。公室四分，民食于他，思莫在公，不圖其終。為國(guó)君，難將及身，不恤其所。禮之本末，將于此乎在，而屑屑焉習(xí)儀以亟。言善于禮，不亦遠(yuǎn)乎？

在進(jìn)行圖表示的讀出時(shí)，類似于以往圖表示學(xué)習(xí)文獻(xiàn)，我們用最大池化的方法把同一節(jié)點(diǎn)在每個(gè)網(wǎng)絡(luò)層的表示進(jìn)行連結(jié)，之后用一個(gè)全連接層產(chǎn)生圖表示的讀出。但與以往文獻(xiàn)不同的是，根據(jù)DAGNN特殊的結(jié)構(gòu)我們只把出口節(jié)點(diǎn)在每個(gè)網(wǎng)絡(luò)層中的節(jié)點(diǎn)表示進(jìn)行連結(jié)，之后用一個(gè)全連接層得出最終的圖表示。具體計(jì)算過程如式(18)所示：

(18)

算法1:基于DAGNN的信息傳遞算法

2.輸出：動(dòng)作的q值

3.forl=1 toLdo

4.forv=1 toVdo

8.end for

9.end for

10.forvinTdo

11.通過式(3.25)將出口節(jié)點(diǎn)在所有網(wǎng)絡(luò)層中的節(jié)點(diǎn)表示進(jìn)行連結(jié)

12.用最大池化方法處理連結(jié)后的信息

13.將上一步處理過的信息輸入全連接層，生成最終的圖表示

14.end for

3.4 卸載調(diào)度流程

卸載調(diào)度的具體過程如算法2所示。在算法開始時(shí)，DRL算法的智能體收到要進(jìn)行卸載調(diào)度決策的應(yīng)用及其自身的DAG圖，并獲取每個(gè)任務(wù)節(jié)點(diǎn)的本地執(zhí)行時(shí)延、MEC服務(wù)器上傳輸和執(zhí)行時(shí)延等信息，生成每個(gè)任務(wù)節(jié)點(diǎn)的節(jié)點(diǎn)表示，將累積獎(jiǎng)勵(lì)和動(dòng)作空間分別初始化為0和?，并創(chuàng)建一個(gè)經(jīng)驗(yàn)回放緩存區(qū)。與此同時(shí)，用戶設(shè)備產(chǎn)生一個(gè)待調(diào)度的應(yīng)用，之后算法首先根據(jù)3.1節(jié)中所說的方式確定該應(yīng)用中所有任務(wù)的調(diào)度優(yōu)先級(jí)，然后按照任務(wù)優(yōu)先級(jí)降序的順序依次對(duì)任務(wù)進(jìn)行調(diào)度決策。在對(duì)每個(gè)任務(wù)做決策時(shí)，智能體使用算法1評(píng)估每個(gè)動(dòng)作的q值，得到每個(gè)動(dòng)作的q值后根據(jù)ε貪心策略選擇動(dòng)作，在實(shí)施所選擇的動(dòng)作后系統(tǒng)進(jìn)入下一狀態(tài)s′，并獲得環(huán)境反饋的即時(shí)獎(jiǎng)勵(lì)r，同時(shí)系統(tǒng)將當(dāng)前狀態(tài)s,采取的動(dòng)作a，下一狀態(tài)s′，即時(shí)獎(jiǎng)勵(lì)r等信息存入經(jīng)驗(yàn)回放緩存區(qū)，用于對(duì)圖神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練和更新參數(shù)。卸載動(dòng)作序列即為卸載調(diào)度決策。

算法2：基于DAGNN的卸載調(diào)度算法

2.輸出：卸載動(dòng)作序列β

3.初始化agent，狀態(tài)空間S←{?}，卸載動(dòng)作序列β←{?}，即時(shí)獎(jiǎng)勵(lì)r←0，初始化經(jīng)驗(yàn)回放緩存區(qū)buffer

4.隨機(jī)初始化DAGNN中的參數(shù)，初始化DAGNN每個(gè)節(jié)點(diǎn)的表示

5.根據(jù)2.3節(jié)中所述方式計(jì)算每個(gè)任務(wù)i的最晚開始執(zhí)行時(shí)間LSTn,i

6.將所有任務(wù)按照其LSTn,i升序排列，得到優(yōu)先級(jí)序列φ={x1,…,xv}

7.forx1toxvinφdo

8.fora=0 toNdo

9.調(diào)用算法1計(jì)算每個(gè)動(dòng)作a的q值

10.根據(jù)ε貪心算法選擇要采取的動(dòng)作a

11.s←s’，更新動(dòng)作序列β，獲取即時(shí)獎(jiǎng)勵(lì)r

12.將四元組(s，a，r，s’)存入經(jīng)驗(yàn)回放緩存區(qū)buffer

13.隨機(jī)從buffer中取出若干個(gè)元組

15.使用隨機(jī)梯度下降算法SGD更新DAGNN的參數(shù)

16.end for

17.end for

4 仿真實(shí)驗(yàn)

本節(jié)將對(duì)本文提出的算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，主要以應(yīng)用的完成時(shí)延作為標(biāo)準(zhǔn)來衡量各算法的性能，除此之外還考慮了在改變某些環(huán)境因素的情況下驗(yàn)證本文算法的通用性和穩(wěn)定性。

4.1 實(shí)驗(yàn)設(shè)計(jì)

本節(jié)的實(shí)驗(yàn)情景包括多個(gè)微微基站(均配備有MEC服務(wù)器)和一個(gè)用戶設(shè)備UE，具體的實(shí)驗(yàn)參數(shù)仿照文獻(xiàn)[20]設(shè)置，如表1所示。

表1 仿真實(shí)驗(yàn)參數(shù)

為了模擬DAG應(yīng)用的多樣性，本節(jié)的實(shí)驗(yàn)使用文獻(xiàn)[19-21]所采用的DAG生成器，本節(jié)實(shí)驗(yàn)中所用到的訓(xùn)練和測(cè)試DAG均通過該生成器生成。與此同時(shí)，本節(jié)設(shè)置了4個(gè)基線算法用以與本文提出的算法作對(duì)比，具體為：①本地執(zhí)行(LE，local execution):應(yīng)用的所有任務(wù)均在UE本地執(zhí)行；②卸載執(zhí)行(OE，offloading execution):DAG圖中的所有任務(wù)均被調(diào)度為卸載執(zhí)行；③隨機(jī)調(diào)度(RS，random scheduling)：對(duì)DAG圖中所有任務(wù)均隨機(jī)確定調(diào)度決策；④DRLOSM算法(DRLOSM)：文獻(xiàn)[22]提出的用來解決DAG應(yīng)用卸載調(diào)度問題的算法，它采用圖嵌入的方式將DAG圖轉(zhuǎn)化為節(jié)點(diǎn)信息向量的集合輸入DRL算法的DNN網(wǎng)絡(luò)中，并取得了同類文獻(xiàn)中較好的調(diào)度效果。

圖的密度是描述DAG中兩個(gè)相鄰的任務(wù)層之間依賴關(guān)系數(shù)量的參數(shù)，若該參數(shù)較大則表明DAG圖中任務(wù)的前驅(qū)和后繼節(jié)點(diǎn)較多。由于本文處理的主要是DAG結(jié)構(gòu)復(fù)雜、模塊的前驅(qū)和后繼較多的應(yīng)用，因而本節(jié)實(shí)驗(yàn)還將在改變DAG圖的密度的條件下驗(yàn)證本文算法的性能。

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

首先，對(duì)本章算法的收斂性進(jìn)行評(píng)估。在上文所述的仿真參數(shù)下，隨機(jī)生成3 000個(gè)DAG樣本用于訓(xùn)練以得到對(duì)該批樣本的卸載調(diào)度方案，然后將該調(diào)度方案在同樣的仿真環(huán)境中對(duì)該批樣本進(jìn)行模擬調(diào)度，并記錄該批樣本所獲得的平均累積獎(jiǎng)勵(lì)。如圖4所示，該批樣本的平均累積獎(jiǎng)勵(lì)在經(jīng)歷700此迭代后逐漸趨于穩(wěn)定，證明了該算法具有良好的收斂性。

圖4 收斂性曲線

然后，基于使應(yīng)用的總處理時(shí)延最小的優(yōu)化目標(biāo)，在默認(rèn)環(huán)境下對(duì)任務(wù)節(jié)點(diǎn)數(shù)量不同的DAG應(yīng)用的處理時(shí)延進(jìn)行了比較，圖5展示了實(shí)驗(yàn)結(jié)果?？梢钥闯鲈诓煌?jié)點(diǎn)數(shù)的條件下，完全本地執(zhí)行(LE)的方式的時(shí)延都是最高的，本文提出的算法(TOSA-DAGNN)都要優(yōu)于其它對(duì)比算法。值得注意的是，雖然文獻(xiàn)[22]提出的DRLOSM算法在節(jié)點(diǎn)數(shù)較少時(shí)也體現(xiàn)出了較好的性能，但是在節(jié)點(diǎn)數(shù)增加至50個(gè)后本文的算法開始明顯優(yōu)于DRLOSM算法，這是由于DRLOSM算法將所有節(jié)點(diǎn)的信息轉(zhuǎn)化為統(tǒng)一長(zhǎng)度的向量來輸入DRL算法的神經(jīng)網(wǎng)絡(luò)中，這種方式在處理節(jié)點(diǎn)數(shù)較多且DAG結(jié)構(gòu)復(fù)雜的應(yīng)用時(shí)會(huì)丟失很多DAG圖的結(jié)構(gòu)信息，導(dǎo)致做出的卸載決策不夠準(zhǔn)確。

圖5 應(yīng)用的完成時(shí)延隨任務(wù)節(jié)點(diǎn)數(shù)的變化

下面將在改變DAG圖的密度的條件下驗(yàn)證本文算法的性能，如圖6所示，在節(jié)點(diǎn)數(shù)量均為40的條件下,本節(jié)實(shí)驗(yàn)分別在DAG圖密度為0.3、0.6、0.8和0.9時(shí)進(jìn)行驗(yàn)證。從圖中可以看出，隨著圖密度的增加本地執(zhí)行(LE)、卸載執(zhí)行(OE)和隨機(jī)調(diào)度(RS)3種方式變化不大，這是由于在這3種方式中每個(gè)任務(wù)的執(zhí)行方式是固定不變的，因而并不受到圖密度變化的影響。但DRLOSM算法受圖密度變化的影響較為明顯，這是因?yàn)镈RLOSM算法在處理過程中將任務(wù)的前驅(qū)和后繼節(jié)點(diǎn)的信息轉(zhuǎn)化為固定長(zhǎng)度的向量，如果某個(gè)任務(wù)的前驅(qū)和后繼節(jié)點(diǎn)過多就將超出的部分舍棄，而圖的密度較大時(shí)DAG圖中任務(wù)的前驅(qū)和后繼節(jié)點(diǎn)往往是比較多的，因而此時(shí)DRLOSM算法的處理方式會(huì)舍棄大量的DAG圖的結(jié)構(gòu)信息，導(dǎo)致做出的卸載決策不準(zhǔn)確。相較之下，本文的算法在各種圖密度的條件下都能保持較好的卸載調(diào)度效果。

圖6 應(yīng)用完成時(shí)延隨圖密度的變化

為了驗(yàn)證本文算法的通用性和穩(wěn)定性，下面在節(jié)點(diǎn)數(shù)均為40的情況下改變網(wǎng)絡(luò)的傳輸速率來驗(yàn)證各算法的性能，如圖7所示?？梢钥闯鲭S著網(wǎng)絡(luò)傳輸速率的增大，除本地執(zhí)行(LE)以外的各算法的完成時(shí)延都處于下降趨勢(shì)，這是因?yàn)榫W(wǎng)絡(luò)傳輸速率的加大降低了任務(wù)從用戶設(shè)備UE到MEC服務(wù)器之間的傳輸時(shí)延，而本地執(zhí)行(LE)的方式由于其所有任務(wù)都在本地執(zhí)行，所以其完成時(shí)延不受網(wǎng)絡(luò)傳輸速率的影響。卸載執(zhí)行(OE)的方式由于其所有任務(wù)都被卸載至MEC服務(wù)器執(zhí)行，所以隨著網(wǎng)絡(luò)傳輸速率的增加它的完成時(shí)延大幅降低，并在網(wǎng)絡(luò)傳輸速率超過8 Mbps后其完成時(shí)延逐漸超過DRLOSM算法。同時(shí)可以看出，本文提出的算法(TOSA-DAGNN)始終在完成時(shí)延方面優(yōu)于其它算法。

圖7 應(yīng)用完成時(shí)延隨網(wǎng)絡(luò)傳輸速率的變化

5 結(jié)束語

本文研究了MEC中具有依賴關(guān)系任務(wù)的計(jì)算卸載問題，通過DAG對(duì)任務(wù)間的依賴關(guān)系進(jìn)行建模，將卸載調(diào)度建模為MDP過程進(jìn)而使用DRL算法進(jìn)行求解。為了解決其它文獻(xiàn)在將DAG圖輸入DRL算法的神經(jīng)網(wǎng)絡(luò)時(shí)存在的丟失DAG圖的結(jié)構(gòu)信息的問題，創(chuàng)新地將GNN與DRL算法相結(jié)合用于解決卸載調(diào)度的問題。同時(shí)為了適應(yīng)DAG圖的結(jié)構(gòu)特點(diǎn)將MPNN進(jìn)行了改進(jìn)，提出有向無環(huán)圖神經(jīng)網(wǎng)絡(luò)(DAGNN)，最后的實(shí)驗(yàn)結(jié)果表明，與其它基線算法相比本文提出的方案收到了最好的調(diào)度效果，尤其是在處理DAG結(jié)構(gòu)復(fù)雜、任務(wù)的前驅(qū)和后繼節(jié)點(diǎn)較多的應(yīng)用時(shí)本文的方案明顯優(yōu)于其它算法，并在網(wǎng)絡(luò)環(huán)境改變時(shí)始終優(yōu)于其它算法，體現(xiàn)了本文方案的通用性和穩(wěn)定性。