基于圖神經網絡的具有依賴關系任務的計算卸載方法

崔 碩，覃少華，謝志斌，張家豪，卞圣強

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

0 引言

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

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

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

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

1 系統結構及原理

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

圖1 系統實現結構流程圖

2 系統模型

圖2 系統模型

2.1 通信模型

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

(1)

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

2.2 計算模型

用戶設備UE在同一時隙內只產生一個計算密集型的應用，它被進一步分割為多個相互之間具有依賴關系的任務，每個處理單元在同一時隙內只能處理一個任務，每個任務只能被一個處理單元所處理。下面分別討論任務在本地計算和MEC服務器上計算的時延。

①本地計算：

用f0表示用戶設備UE自身的計算能力，則任務i在UE本地計算的計算時延可以表示為：

(2)

由于本地計算無需進行數據的傳輸所以不存在通信時延，所以任務i在本地計算的全部時延為：

(3)

②MEC服務器計算：

當任務i被調度為MEC服務器n計算時，數據需要在用戶設備UE和MEC服務器之間傳輸，因而MEC服務器計算情景下的時延由兩部分構成：傳輸和MEC服務器執行。特別地，由于任務被執行所產生的計算結果的數據量往往很小，類似于現有大多數文獻的假設[8,12,18]，本文不考慮計算結果的傳輸時延。由此可得任務i在MEC服務器n上計算的時延為：

(4)

2.3 依賴關系模型

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

在應用開始卸載調度后，用AFTn,i表示任務i在處理單元n上執行時的實際完成時間。由于一個任務只有在其所有直接前驅任務都被執行完成后才能進入準備就緒狀態，所以任務i的就緒時間可以表示為：

(5)

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

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

(6)

用ETn,i表示任務i在處理單元n上執行所花費的時間，它可以表示為：

(7)

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

(8)

在定義了任務的最晚完成時間后我們可以相應地得到任務的最晚開始執行時間，它可以表示為：

(9)

2.4 優化目標制定

本文以使任務的時延最小為優化目標，首先定義兩個0-1變量xn,i和yh,i，它們的取值分別為：

(10)

(11)

基于上文的定義，本文的優化問題可表示為：

(12)

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

(12a)

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

(12b)

(12c)

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

3 基于DRL和GNN的DAG任務卸載調度算法

由于DAG任務調度問題的復雜性，文獻[11]等提出使用深度強化學習的方法進行卸載決策。但由于DRL算法無法處理諸如DAG圖一類的圖結構的信息，文獻[22]采用節點嵌入的方式將DAG圖的拓撲結構和節點信息轉化為任務序列輸入到DRL算法的神經網絡中。但這種方式會損失很多DAG圖的結構信息。鑒于圖神經網絡在處理圖結構數據時的優異表現，本文提出將圖神經網絡(GNN，graph neural network)與DRL算法相結合用于解決DAG任務的卸載調度問題。與此同時由于DAG圖是有向圖，本文針對DAG圖的結構特點設計了一種有向圖神經網絡(DAGNN)用于提取DAG圖的信息，取得了較好的效果。

3.1 任務優先級

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

3.2 MDP的構造

3.2.1 狀態空間

MDP的狀態空間應該能夠反映當前應用的DAG結構、已經完成調度決策的任務情況等，基于此狀態空間應包括以下部分：①當前已完成調度的任務序列；②已完成調度任務的卸載動作的集合；③DAG圖。每當完成一個任務節點的調度，系統更新已完成調度任務序列及其動作集，并進入下一狀態。

3.2.2 動作空間

動作空間中的動作表示的是G中每個任務的卸載調度決策，由于本文中每個任務都可以被分配給N個處理單元中的任意一個進行執行且分配給每個處理單元的概率是相同的，所以動作空間具體可以表示為：

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

其中:動作a={0}表示任務被分配在本地執行，a={n}表示任務被分配給了第n臺MEC服務器執行。

智能體在執行選定的動作a后，環境將會反饋給智能體一個即時獎勵r，在本章中即時獎勵被設定為任務節點調度前后應用執行時延的差值，特別地，如果任務的執行時間超過了其最大容忍時延，即時獎勵被設定為0。

3.3 有向無環圖神經網絡

由于DAG圖是有向的、無環的，所以我們針對DAG的結構特性對標準的GNN做了改動使其能夠處理DAG圖。由于文獻[16]歸納并抽象出各種GNN模型的共性，提出了一種通用的GNN處理框架信息傳遞網絡(MPNN，message passing neural network)，鑒于其在各領域的應用中展現出的良好的GNN信息提取能力[17]，本文的DAGNN借鑒了MPNN的基本結構，具體的結構如圖3所示。

圖3 DAGNN結構圖

DAGNN中每個節點代表應用的一個任務，共包含L層網絡。DAGNN通過聚合函數對每個節點的直接前驅節點的節點表示進行聚合，并把得到的聚合信息用連結函數與該節點在當前網絡層的節點表示進行連結，用以更新節點表示。在所有節點間迭代進行這一過程，最后使用最大池化的方法將所有網絡層的出口節點的節點表示進行聚合，通過讀出函數將聚合后的信息讀出，生成最終的圖表示。DAGNN總的計算過程如式(13)和式(14)所示：

(13)

(14)

由于每個任務的執行時延只受其前驅任務的影響，因此我們在進行信息聚合時只考慮節點的前驅任務。除此之外，本文在聚合函數計算過程中引入注意力機制以便更好地聚合相關節點的信息,具體的計算方式如式(15)所示：

(15)

(16)

(17)

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

在進行圖表示的讀出時，類似于以往圖表示學習文獻，我們用最大池化的方法把同一節點在每個網絡層的表示進行連結，之后用一個全連接層產生圖表示的讀出。但與以往文獻不同的是，根據DAGNN特殊的結構我們只把出口節點在每個網絡層中的節點表示進行連結，之后用一個全連接層得出最終的圖表示。具體計算過程如式(18)所示：

(18)

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

2.輸出：動作的q值

3.forl=1 toLdo

4.forv=1 toVdo

8.end for

9.end for

10.forvinTdo

11.通過式(3.25)將出口節點在所有網絡層中的節點表示進行連結

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

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

14.end for

3.4 卸載調度流程

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

算法2：基于DAGNN的卸載調度算法

2.輸出：卸載動作序列β

3.初始化agent，狀態空間S←{?}，卸載動作序列β←{?}，即時獎勵r←0，初始化經驗回放緩存區buffer

4.隨機初始化DAGNN中的參數，初始化DAGNN每個節點的表示

5.根據2.3節中所述方式計算每個任務i的最晚開始執行時間LSTn,i

6.將所有任務按照其LSTn,i升序排列，得到優先級序列φ={x1,…,xv}

7.forx1toxvinφdo

8.fora=0 toNdo

9.調用算法1計算每個動作a的q值

10.根據ε貪心算法選擇要采取的動作a

11.s←s’，更新動作序列β，獲取即時獎勵r

12.將四元組(s，a，r，s’)存入經驗回放緩存區buffer

13.隨機從buffer中取出若干個元組

15.使用隨機梯度下降算法SGD更新DAGNN的參數

16.end for

17.end for

4 仿真實驗

本節將對本文提出的算法進行實驗驗證，主要以應用的完成時延作為標準來衡量各算法的性能，除此之外還考慮了在改變某些環境因素的情況下驗證本文算法的通用性和穩定性。

4.1 實驗設計

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

表1 仿真實驗參數

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

圖的密度是描述DAG中兩個相鄰的任務層之間依賴關系數量的參數，若該參數較大則表明DAG圖中任務的前驅和后繼節點較多。由于本文處理的主要是DAG結構復雜、模塊的前驅和后繼較多的應用，因而本節實驗還將在改變DAG圖的密度的條件下驗證本文算法的性能。

4.2 實驗結果分析

首先，對本章算法的收斂性進行評估。在上文所述的仿真參數下，隨機生成3 000個DAG樣本用于訓練以得到對該批樣本的卸載調度方案，然后將該調度方案在同樣的仿真環境中對該批樣本進行模擬調度，并記錄該批樣本所獲得的平均累積獎勵。如圖4所示，該批樣本的平均累積獎勵在經歷700此迭代后逐漸趨于穩定，證明了該算法具有良好的收斂性。

圖4 收斂性曲線

然后，基于使應用的總處理時延最小的優化目標，在默認環境下對任務節點數量不同的DAG應用的處理時延進行了比較，圖5展示了實驗結果。可以看出在不同節點數的條件下，完全本地執行(LE)的方式的時延都是最高的，本文提出的算法(TOSA-DAGNN)都要優于其它對比算法。值得注意的是，雖然文獻[22]提出的DRLOSM算法在節點數較少時也體現出了較好的性能，但是在節點數增加至50個后本文的算法開始明顯優于DRLOSM算法，這是由于DRLOSM算法將所有節點的信息轉化為統一長度的向量來輸入DRL算法的神經網絡中，這種方式在處理節點數較多且DAG結構復雜的應用時會丟失很多DAG圖的結構信息，導致做出的卸載決策不夠準確。

圖5 應用的完成時延隨任務節點數的變化

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

圖6 應用完成時延隨圖密度的變化

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

圖7 應用完成時延隨網絡傳輸速率的變化

5 結束語

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