子任務調度和時延聯合優化的MEC卸載方案

陳 韓, 張 晶,3,*, 董 俊, 董 潔

(1. 南京郵電大學通信與信息工程學院, 江蘇 南京 210003; 2. 南京郵電大學江蘇省無線通信重點實驗室, 江蘇 南京 210003; 3. 南京郵電大學物聯網研究院, 江蘇 南京 210003;4. 中國科學院合肥物質科學研究院智能機械研究所, 安徽 合肥 230031;5. 安徽中科德技智能科技有限公司, 安徽 合肥 230031; 6. 國家無線電監測中心, 北京 100037)

0 引 言

隨著5G時代的來臨,移動通信與物聯網加速融合,集中式處理的云計算已經滿足不了多行業的分布式應用需求[1-2],移動邊緣計算(mobile edge computing,MEC)應運而生。MEC技術將分布式計算能力置于移動網絡邊緣,利用無線接入網絡為用戶提供互聯網技術服務和計算功能,加速網絡中各項內容、服務及應用的快速提供,讓消費者享有不間斷的高質量網絡體驗[3-4]。基于MEC技術,物聯網設備可以將應用任務卸載到邊緣服務器計算處理,不再需要“長途跋涉”地傳輸到云端處理,因此大大減少了任務的平均處理延遲和能量消耗[5-6]。

如何設計計算任務卸載模型并做出最優的卸載決策,是MEC面臨的一個挑戰性難題。不合理的卸載決策可能會導致任務處理時延和能耗上升,從而影響MEC的性能。目前大部分卸載模型將每個計算任務視為不可分割的獨立單元,任一獨立的計算任務只能選擇全部本地處理或者全部卸載到MEC服務器處理,即二進制卸載[7]。文獻[8]研究了超密集邊緣網絡中的二進制卸載和任務調度問題,提出了基于次梯度的非聯盟博弈求解算法,有效地節省了能耗。文獻[9]研究了在線和離線卸載平衡問題,探討了成本模型、用戶配置和環境因素等約束條件下的二進制任務卸載算法,以實現低延遲和更好的能效。文獻[10]提出了分層MEC系統架構,探討了基于該架構的二進制任務卸載方案。文獻[11]研究了異構移動邊緣云環境中的非合作用戶博弈方法,以實現二進制卸載計算策略的優化。文獻[12]確立了MEC質量和服務響應時間的平衡點,以解決服務質量有損情況下的MEC卸載計算問題。文獻[13]研究了功率約束下的二進制卸載計算時延最小化問題。文獻[14]提出了一個基于博弈論的分布式卸載算法(potential game-based offloading algorithm, PGOA),該算法基于二進制卸載,以解決多用戶多服務器的分布式卸載計算。該文獻基于博弈論制定卸載策略,決定是否應該卸載整個應用程序以減少執行時間。然而該工作忽略了子任務之間的依賴關系,增加了任務執行的額外時延。

對于大型計算任務,這種“二進制任務卸載”模型存在較大的處理時延。為此,近來有學者提出了非二進制的任務部分卸載策略,即將計算任務細分為多個子任務,部分子任務本地執行,部分子任務卸載到MEC服務器執行,從而大大提高計算效率,降低處理時延。文獻[15]針對本地/邊緣服務器聯合計算場景,探索了基于任務關系圖的卸載策略,提出了時延最小的任務部分卸載算法。文獻[16]考慮云-邊協調計算場景,研究了模塊化任務的卸載計算優化決策方案,提出了一種迭代啟發式MEC資源分配算法。上述兩篇文獻只是簡單地將子任務看成一種順序執行問題,沒有考慮任務之間的數據依賴性。為此,文獻[17]考慮任務間的依賴性提出了一種分布式最早完成時間卸載(distributed earliest finish-time offloading, DEFO)算法來動態地執行MEC卸載決策,然而該算法犧牲了子任務的并行性來減少系統時延,因為卸載到不同邊緣服務器的子任務需要額外的等待時延,這意味著卸載計算的并行性和的服務器資源利用率較低。

針對當前MEC卸載研究中存在的問題,本文提出了一種基于子任務調度和時延聯合優化的MEC部分卸載計算方案。在該方案中,用戶任務劃分為多個有順序依賴關系的子任務,以子任務間交換數據量為權重,構建一個任務關系的有向無環圖(directed acyclic graph,DAG);基于此圖建立子任務調度-計算時延聯合優化問題,提出一種基于節點復制的最早卸載算法(earliest offloading algorithm of node replication,EOAONR),完成子任務面向MEC服務器的最小時延卸載決策。相比于PGOA,本文考慮子任務之間的依賴關系,減少了任務執行的額外時延。而相比于DEFO算法,本文通過節點復制消除了部分節點對其前驅子任務計算結果的等待時間,提高了卸載計算的并行性和服務器資源利用率。

1 系統模型

考慮圖1所示的微蜂窩系統,其中存在一個活躍用戶和N個配置有MEC服務器的微基站,用戶可以同時與多個微基站關聯。活躍用戶申請一個大容量應用服務,該應用服務可分解為M個有順序依賴關系的計算型子任務,除首個子任務之外,其他每個子任務的執行需要依賴其相鄰前驅子任務的計算結果。每個子任務可以由終端(本地處理器)執行計算,亦可以卸載至MEC服務器執行計算。每個微基站關聯一個邊緣服務器,N個邊緣服務器通過高速光纖網絡彼此連接,即邊緣服務器之間可以互相通信,協作完成一個用戶的DAG任務。

圖1 系統模型Fig.1 System model

定義本地處理器/邊緣服務器集合為S={s1,s2,…,sj,…,sN}∪{s0},其中N表示邊緣服務器的數量,sj(j>0)表示第j個邊緣服務器,s0表示本地處理器。本地處理器/邊緣服務器sj的計算能力用fj表示,j∈N={0,1,…,j,…,N},其中f0表示本地處理器的計算能力。用戶子任務集合為V={v1,v2,…,vi,…,vM},其中vi表示第i個子任務,i∈M={1,2,…,M};子任務vi的屬性表示為Ti={mi,ci,ai},其中mi表示子任務vi的數據量,ci表示完成子任務vi所需要的中央處理器周期數,ai表示子任務vi的卸載決策,表示子任務vi在本地處理器s0上計算,ai=j表示子任務vi在邊緣服務器sj,j∈N上計算;a=(a1,a2,…,ai,…,aM)表示M個子任務的聯合卸載決策向量。

(1)

(2)

式中:δl為本地處理器在每個中央處理器周期的能耗。

若用戶子任務vi卸載到MEC服務器sj計算,用戶子任務vi至邊緣服務器sj的上行傳輸速率可計算為

(3)

子任務vi至服務器sj的傳輸時間ωi, j、邊緣計算執行時間ti, j和傳輸能耗ei, j、分別表示為

(4)

(5)

(6)

2 子任務卸載調度優化問題

2.1 構建子任務關系圖

根據系統模型,活躍用戶的任務劃分為M個有順序依賴關系的子任務分別卸載計算。為了找到滿足順序關系約束且時延最小的子任務卸載調度排序方案,本文首先以子任務間的交換數據量為權重構建一個有向無環的任務關系圖來描述子任務間的依賴關系,具體構建方法如下:以應用程序的起始子任務為圖的首層任務節點(入口子任務節點),將與其相鄰的后繼子任務依次放至圖的第二層并分別與首層任務節點關聯,形成第二層任務節點;再從第二層的每個子任務出發,將與其相鄰的后繼子任務依次放至圖的第三層并與上層節點關聯,以此類推形成圖的其他層節點,直至遍歷到應用程序的最終子任務(出口子任務節點),它為圖的最下層節點,這樣就形成了用戶任務的DAG。用G={V,E}表示建立好的用戶子任務DAG,其中V={v1,v2,…,vi,…,vM}表示子任務節點集,E={e(vi,vi′)}表示子任務間的有向邊集合,有向邊e(vi,vi′)由上層指向下層,代表上層子任務vi的計算結果將傳遞給其相鄰的下層子任務vi′;有向邊e(vi,vi′)的權值為βii′,表示兩個子任務間的數據交換量。

一個包含7個子任務的用戶計算任務的DAG如圖2所示,它可以記為G={{v1,v2,…,v7},{e(v1,v2),e(v1,v3),e(v1,v4),e(v2,v5),…,e(v6,v7)}},其中,v1為入口子任務節點,v7為出口子任務節點,e(v1,v2)的權值為β12=10,表示節點v1與v2間交互數據量為10 bits。

圖2 基于DAG的任務模型的圖示Fig.2 Illustration of the DAG-based task model

2.2 優化問題闡述

本文的目標是將應用程序的總計算執行時間降至最低,即DAG中全部子任務的總執行時間最小化。應用程序的卸載計算需要考慮以下兩個問題:

(1) 子任務卸載策略:在本地處理子任務還是將子任務卸載到邊緣服務器上;

(2) 子任務調度順序:對不同子任務進行卸載排序,以降低系統的整體延遲。

在構建子任務卸載調度優化問題之前,首先定義兩個變量:①子任務vi卸載至服務器sj的執行開始時間(the execution start time, TEST),表示為TEST(i,j);②子任務vi卸載至服務器sj計算時的執行完成時間(the execution finish time, TEFT),表示為TEFT(i),i∈M={1,2,…,M},j∈N={0,1,…,j,…,N}。

事實上,子任務vi開始執行前需求具備兩個條件:①其所需的來自相鄰前驅子任務的數據已經傳輸到達;②其目標卸載服務器sj已經空出并準備提供服務。于是,子任務執行開始時間TEST(i,j)和完成時間TEFT(i)分別表示為

(7)

(8)

(9)

不失一般性,本文規定DAG入口任務節點(例如,圖2中v1)的開始執行時間為0,即有

TEST(1,j)=0,j∈N

(10)

(11)

式中:TEFTM表示最后一個子任務的完成時間;TEST(M,0)表示最后一個子任務的開始執行時間,由式(7)、式(8)、式(10)迭代得到,表示為

(12)

式中:TEFT(i′)可由式(8)計算得到。

以最小化所有子任務的執行完成時間為目標,同時考慮用戶設備的能耗約束,建立如下的優化問題:

(13)

式中：式(13a)表示與子任務有關的能耗約束,即本地計算能耗和傳輸能耗,Costi表示子任務vi的能耗,包含本地計算能耗和傳輸能耗;C表示每個子任務的能耗閾值,即最大能耗限值;1[x]表示指標函數,x成立時1[x]=1,否則為0。式(13b)表示子任務的傳輸能耗。式(13c)表示子任務的本地計算能耗。式(13d)表示子任務的計算卸載決策,a表示卸載決策向量,ai=j,j∈N表示子任務vi在本地處理器或MEC服務器sj上計算;a1=0,aM=0約束初始子任務和最終子任務均在本地執行。

式(13)所述優化問題屬于多變量整數優化問題,很難給出閉式解。下面研究該問題的求解算法。

3 EOAONR

本節提出一種EOAONR求解式(13)所述優化問題,以實現所有子任務的最小時延卸載決策。鑒于子任務的調度順序影響總卸載時延,而待卸載的子任務具有順序依賴關系,本節基于DAG賦予不同子任務卸載優先級,據此找到執行完全部子任務的最大時延路徑——關鍵卸載路徑,實現任務調度順序的優化,在此基礎上設計最小時延任務卸載決策算法。

3.1 劃分子任務優先級

對于用戶子任務DAG,賦予圖中子任務節點vi卸載等級：

(14)

式中:δi表示子任務vi的平均執行時間方差;succ(i)表示子任務vi的相鄰后繼任務組成的集合;Cii′表示子任務vi與其相鄰后繼子任務vi′的平均通信時間。

式(14)是求DAG中子任務vi到出口子任務的路徑長度,路徑長度用時延衡量,用來解決任務依賴問題。例如,入口子任務的路徑長度是最大的,表示依賴關系最多;出口子任務的路徑長度是最小的,表示依賴關系最少。

δi和Cii′分別由下式得到：

(15)

(16)

(17)

Bjj′表示服務器sj和sj′之間的信道帶寬;βii′表示子任務vi和vi′間的通信數據量。

由式(14)可知,rank(i)大的子任務依賴關系多,需要優先卸載,因此,將所有子任務按照rank(i)值降序排列,rank(i)值大的子任務具有更高的卸載優先級,優先執行卸載計算。

3.2 求關鍵卸載路徑

定義 1關鍵卸載路徑為DAG中入口子任務節點到出口子任務節點的時延最長路徑。

為尋址DAG的關鍵卸載路徑,引入子任務vi的最大升秩值ranku(i)和最大降秩值rankd(i)兩個參數,分別計算如下：

(18)

(19)

式中:ranku(i)表示子任務vi至其相鄰后繼任務節點的最大升秩值,rankd(i)表示子任務至其相鄰前驅任務節點的最大降秩值;succ(i)表示子任務vi的相鄰后繼任務組成的集合,pred(i)表示子任務vi的相鄰前驅任務組成的集合;Cii′表示子任務vi到其相鄰后繼任務節點vi′的平均通信時間。

特別地,入口子任務沒有前驅節點,出口子任務沒有后繼節點,相應地補充規定入口子任務v1的rankd(1)=0,出口子任務vM的ranku(M)=0。

定義 2對于某一子任務vi∈V,若其ranku(i)+rankd(i)值大于其當前所在DAG圖層G(vi)中的其他子任務節點,則vi是關鍵卸載路徑上的子任務節點。

很顯然,DAG的入口節點和出口節點必然在關鍵卸載路徑上。

3.3 子任務卸載計算決策算法

以圖2所示的DAG為例,EOAONR詳細描述如下。

步驟 1確定待卸載子任務集合并初始化卸載決策向量,根據式(14)計算集合中各子任務的卸載等級;

如圖4(a)所示,當前待卸載子任務集合為G={v1,v2,…,v7},其中子任務vi的卸載等級為rank(i)。

圖3 EOAONR流程圖Fig.3 Flowchart of EOAONA

步驟 2選擇待卸載子任務集合中優先級最高的子任務vi*,判斷其是否為出口子任務節點或者出口子任務節點,若是,直接本地執行計算并跳轉至步驟6;否則,在式(13)能耗約束下為子任務vi*確定最優卸載MEC服務器,轉步驟3。

例如,圖4(a)中,具有最大rank(i)值(最高卸載優先級)的子任務為v1,其卸載優先級最高;由于v1是入口節點,由式(13)可知,v1在本地執行,待v1計算完成之后,轉步驟6。若當前具有最高卸載優先級的子任務vi*不是入口節點/出口節點,如v2、v3、v6,對vi*分別遍歷j∈N,在滿足能耗約束的情況下確定使TEFT(i*)最小的MEC服務器sj*,即為vi*匹配的最優卸載MEC服務器,然后轉步驟3。

步驟 3根據確定好的關鍵卸載路徑,判斷當前要執行子任務vi*的相鄰前驅子任務是否為關鍵卸載路徑上的節點。

例如,圖4(a)中,根據式(18)、式(19)求得的關鍵卸載路徑為v1→v4→v5→v7。若當前待執行子任務vi*為v2,其相鄰前驅子任務v1是關鍵卸載路徑上的節點,轉步驟4;若當前待執行子任務vi*為v6,其相鄰前驅子任務v3不是關鍵卸載路徑上的節點,轉步驟5。

圖4 DAG更新過程Fig.4 Update process of DAG

步驟 4判斷當前要執行的子任務vi*是否滿足前驅子任務復制卸載條件,即是否滿足不等式：

(20)

若是,將vi*的相鄰前驅子任務的數據復制到vi*匹配的MEC服務器中,轉步驟5;否則,直接轉步驟5。

(21)

(22)

例如,圖4(a)中,v2和v4滿足前驅子任務復制卸載條件,v3不滿足前驅子任務復制卸載條件,因此v3直接轉步驟5;對于v2和v4,其前驅子任務v1分別復制到v2和v4匹配的MEC服務器中(步驟2已選定),形成合并子任務,然后轉步驟5。

步驟 5MEC服務器sj*對當前卸載的子任務vi*(包括其復制任務)一并計算處理。

例如,如圖4(a)中,子任務v2的匹配服務器同時處理子任務v1+v2,子任務v4的匹配服務器同時處理子任務v1+v4;而子任務v3的匹配服務器等待終端(本地)執行完v1后將數據返回方可處理子任務v3。

步驟 6將子任務sj*從待卸載子任務集合G中刪除,更新待卸載子任務集合和卸載決策向量a;若更新后的待卸載子任務集合非空,轉步驟1,否則,轉步驟7。

如圖4(a)所示,v1的相鄰后繼任務節點v2、v3、v4全部卸載執行完成后,刪除v1,更新任務關系圖,其中v3(v1)表示包含v1計算結果的v3。同時更新卸載決策向量a和v2、v3、v4的TEST(i,j),TEFT(i)。

步驟 7求得最后子任務的完成時間TEFTM和所有子任務的最優卸載決策向量a*,算法結束。

根據上述步驟,后續DAG更新過程如圖4(b)所示。

由更新過程可知,將關鍵卸載路徑上的部分任務通過復制將“串行”卸載計算轉變為“并行”卸載計算,消除部分節點對其前驅子任務計算結果的等待時間。

4 仿真分析

基于Matlab軟件,本節對提出的EOAONR的性能進行仿真研究。仿真參數設置如表1所示。

表1 仿真參數

圖5給出EOAONR不同邊緣服務器計算能力下子任務數量與任務卸載計算時延的關系,并與文獻[17]的DEFO算法進行比較。可以得出,隨著子任務數量增加,EOAONR和DEFO算法的任務卸載處理時延均呈現上升趨勢。這是因為隨著子任務數量增加,完成該應用程序所需要的傳輸時延和計算時延會增大,導致任務卸載計算的總時延增大。與DEFO算法相比,本文提出的EOAONR的任務卸載計算時延更小;隨著子任務數量的增加,本文算法的低時延優勢更為顯著。這是因為,本文算法通過任務復制將“串行”卸載計算轉變為“并行”卸載計算,消除了部分節點對其前驅子任務計算結果的等待時間,因此大大降低了任務的卸載時延。還可以得出,有較大計算能力的邊緣服務器會帶來更低的任務卸載處理時延,例如f=2.5 GHz與f=10 GHz的邊緣服務器相比,雖然計算能力是4倍關系,但卸載計算時延卻降低了不到兩倍,這是因為卸載計算時延包含了計算時延和傳輸時延,隨著子任務數量的增加,傳輸時延會增大,導致任務卸載計算的總時延不能成倍降低。值得一提的是,與DEFO算法相比,在不同邊緣服務器計算能力下,本文提出的EOAONR在子任務數量較少時,例如N<33時,能依靠算法的優勢彌補服務器計算能力的差距,但當子任務數量進一步增加時,邊緣服務器計算能力的差距就不能靠EOAONR的優勢來彌補。

圖5 不同邊緣服務器計算能力下子任務的數量與 卸載計算時延的關系(N=5)Fig.5 Relationship between the number of subtasks and the offloading calculation delay under different edge server computing capabilities (N=5)

圖6給出EOAONR的服務器數量與卸載計算時延的關系,并與文獻[17]的DEFO算法和文獻[14]的PGOA進行比較。可以看出,相比基于二進制卸載模型的PGOA,基于部分卸載模型的EOAONR和DEFO算法具有明顯的時延優勢。隨著MEC服務器數量的增加,DEFO算法和EOAONR的任務卸載計算時延逐漸下降并趨于恒定,而PGOA的任務卸載計算時延始終保持恒定。而且,EOAONR的任務卸載計算時延總是小于DEFO算法,當服務器數量較少時,例如N<8時,兩者的時延差距尤為明顯;當N>8時,兩者時延差距逐漸減小,但EOAONR仍具優勢。

圖7給出子任務的數量與服務器資源利用率的關系,并與DEFO算法進行比較。待卸載計算的應用程序大小固定,被分為1～40個子任務,服務器數量設置為5。可以看出,隨著子任務數量增加,EOAONR和DEFO算法的服務器資源利用率均呈現上升趨勢。但本文算法的服務器資源利用率要高于DEFO算法,提升幅度大概20%。當子任務的數量達到32時,本文算法的服務器資源利用率不再增加,這一結果可用于指導邊緣服務器的部署。雖然子任務數增加,但用戶所需的計算資源保持不變,這可以推斷,通過將應用程序劃分為更多的子任務,可以進一步提高服務器的利用率。

圖6 服務器的數量與卸載計算時延的關系(M=25)Fig.6 Relationship between the number of servers and the offloading calculation delay (M=25)

圖7 子任務的數量與服務器資源利用率的關系Fig.7 Relationship between the number of subtasks and the server resource utilization

5 結束語

本文研究了大容量計算型任務的低時延邊緣卸載計算問題。針對端-邊協同MEC場景,考慮將用戶任務劃分為多個有順序依賴關系的子任務并構建任務的DAG,設計了子任務調度優化方案,進而提出了一種EOAONR完成子任務面向MEC服務器的最小時延卸載決策。仿真結果驗證了本文算法的優越性,亦表明所提出的算法在能耗的約束下,能夠有效降低任務處理時延,并且該算法的服務器資源利用率更高。本文只考慮多子任務的單用戶 MEC 系統,所設計的卸載優化算法是針對單用戶的,后續的工作可以將通信場景擴展為多用戶,并探尋一種多用戶卸載優化算法。同時,在這項工作中,我們的性能提升主要來自于最大限度地提升邊緣服務器之間的并行性。在未來的工作中,我們將重點評估子任務之間的并行度,驗證算法在不同并行度下的性能。