基于移動邊緣云的計算密集型任務卸載決策算法

王志強 王金婉

(濟源職業(yè)技術學院信息工程系 河南 濟源 459000) 2(南京大學信息管理學院 江蘇 南京 210023)

0 引 言

隨著物聯(lián)網(wǎng)和可穿戴設備等移動技術的迅速興起,智能移動設備的使用正變得越來越廣泛,它為支持新型的移動應用提供了有力平臺,在交互型游戲、人臉識別、自然語言處理等領域得到了廣泛應用[1-2]。這種計算密集型應用比移動設備上執(zhí)行的傳統(tǒng)型應用需要更加強大的計算能力和消耗更多的能耗[3]。而通常移動設備擁有受限的計算資源(CPU頻率和內(nèi)存有限)和電池容量,這種移動應用的有效執(zhí)行給移動設備帶來了巨大挑戰(zhàn)[4]。

由于邊緣云服務器擁有比移動設備更加強大的計算能力,移動邊緣云可以利用移動設備至云端服務器間的任務遷移解決移動設備上執(zhí)行新型應用任務的效率問題,即計算卸載技術[5]。然而,云服務器通常距離移動設備較遠,這樣會導致較高的傳輸延時,不利于延時敏感型應用。移動邊緣云作為一種新的計算模式[6-7],通過5G網(wǎng)絡極大地拉近了云計算資源與移動設備間的距離,比較傳統(tǒng)云計算,移動邊緣云以計算卸載提供了更低的延時和計算靈活性。然而,考慮到經(jīng)濟性和擴展性問題,移動邊緣計算服務器的計算能力通常較為有限,此外,密集型網(wǎng)絡中的計算卸載可能導致更多的干擾和傳輸延時[8]。因此,將所有計算任務卸載到移動邊緣計算服務器上執(zhí)行顯得不切實際,部分應用仍需在移動設備本地上執(zhí)行。本地執(zhí)行雖然能耗更高,但此時不存在額外的通信或等待延時。綜合考慮,做出合理的任務卸載決策,是提高本地應用任務執(zhí)行效率的關鍵問題。

任務卸載決策問題是移動邊緣云中需要處理的關鍵問題,主要體現(xiàn)在:第一,卸載決策過程會隨著任務數(shù)量的增加而呈指數(shù)級增長,利用窮盡搜索機制顯然不切實際;第二,通用任務圖結構(順序任務結構和并行任務結構混合)的完成時間難以計算。此時的完成時間取決于多個客觀因素,包括:移動設備端和邊緣云端的并行性、邊緣云端的負載狀況、邊緣云端與移動設備端間的通信帶寬。

1 相關工作分析

移動邊緣云中的任務卸載決策已有許多相關研究工作,優(yōu)化目標各有不同,如移動設備端的能量優(yōu)化問題、移動數(shù)據(jù)流應用的吞吐量優(yōu)化問題、最為常見的計算密集型應用任務的完成時間優(yōu)化問題。文獻[9]設計了一種克隆云CloneCloud模型,該模型在給定的網(wǎng)絡傳輸速率和設備計算能力的基礎上可以利用離線算法計算應用的卸載決策。但由于作為離線算法使得尋優(yōu)復雜度過高。文獻[10]提出的MAUI模型可以實時地進行應用卸載決策,將卸載決策問題形式化為0-1線性規(guī)劃問題,但求解整數(shù)規(guī)劃的過高計算代價使得它并不適用于邊緣云端的任務卸載問題。文獻[11]設計的ODE算法本文研究有些類似,利用貪婪機制對通用的任務圖中的任務卸載決策進行了求解。然而,該算法求解速度雖然較快,但在網(wǎng)絡帶寬受限較多時,其卸載決策解距離理論最優(yōu)解相差較遠,其執(zhí)行效率較差。文獻[12]提出了具有線性時間復雜度的近似最優(yōu)卸載決策算法,然而,算法僅能夠對連續(xù)的任務結構應用進行卸載決策求解,并沒有考慮更為常規(guī)的并行任務結構的卸載決策問題,應用于計算密集型應用中的卸載決策表現(xiàn)較差。文獻[13]提出了可用于通用任務結構的卸載決策算法,可以實現(xiàn)最大化的系統(tǒng)吞吐量,但是,該算法中所考慮的云端服務時間模型不切實際,不適用于實際環(huán)境。

本文提出一種計算密集型應用任務的卸載決策算法,可以實現(xiàn)移動設備端應用的完成時間最小化。算法考慮了更為普遍的任務結構類型,包含了順序任務結構和并發(fā)任務結構。算法設計的出發(fā)點在于:(1) 若一個任務卸載執(zhí)行,則較大可能其鄰居任務也會卸載執(zhí)行;(2) 應用的執(zhí)行時間可以通過將任務卸載至邊緣云端最大化邊緣云端與移動設備端的并行性來降低任務完成時間。對于順序任務構成的線性拓撲任務圖,算法可以找到最優(yōu)的卸載任務;而對于并發(fā)任務的通用拓撲任務圖,算法可以最大化并行程度的同時實現(xiàn)任務卸載的更好負載均衡。

2 系統(tǒng)模型

將應用任務建模為有向任務圖G(V,E),其中:V代表圖的節(jié)點集,表示任務;E代表圖的有向邊集合,表示任務間的執(zhí)行順序約束。每個任務i∈V擁有一個權重si,表示任務i的執(zhí)行指令數(shù)。有向邊(i,j)∈E代表任務i與任務j間的數(shù)據(jù)傳輸。此時,任務i可視為父任務,任務j可視為子任務。如果一個任務擁有多個子任務,則稱該任務為分叉任務(fork task),如果一個任務擁有多個父任務,則稱該任務為合并任務(merging task)。每條邊(i,j)擁有一個權重di,j,代表任務i至任務j間的數(shù)據(jù)傳輸量。

假設移動設備擁有單個CPU,其處理能力為μm。移動設備的無線設備可與自身CPU內(nèi)核并行工作,CPU在進行任務計算過程中可與遠程邊緣云端間并行進行數(shù)據(jù)傳輸。若任務在移動設備上執(zhí)行,則任務i的執(zhí)行時間可表示為:

(1)

假設邊緣云處理能力為μc。邊緣云計算能力遠大于本地移動設備處理能力,并且可以在多個提交應用的用戶間共享,不同任務的卸載決策取決于當前邊緣云負載狀況。令Q表示當前邊緣云端服務器上排隊的任務集合,新到達任務的總排隊時間為:

(2)

若任務i卸載至邊緣云端執(zhí)行,則其執(zhí)行時間為:

(3)

需要注意的是,ci不包括任務的排隊時間。若將任務卸載至邊緣云端執(zhí)行,在移動設備上該任務的父任務的數(shù)據(jù)傳輸則需要通過網(wǎng)絡數(shù)據(jù)傳輸,同樣地,邊緣云端的執(zhí)行任務也需要將數(shù)據(jù)傳輸至移動設備端上執(zhí)行的子任務。令R表示移動設備與邊緣云端間的無線數(shù)據(jù)通信速率。給定任務i與任務j的連接鏈路,如果一個任務在移動設備端執(zhí)行,一個任務卸載至邊緣云端執(zhí)行,則鏈路的數(shù)據(jù)傳輸時間為:

(4)

本文的目標是將一個應用的部分任務卸載至邊緣云端執(zhí)行,從而降低應用的完成時間,提高應用執(zhí)行效率。即給定應用的任務圖結構G(V,E),算法需要尋找卸載至邊緣云的任務集合,并實現(xiàn)應用執(zhí)行時間的最小化。

3 任務卸載方法設計

目前的任務圖主要有兩種任務結構:順序任務結構和并發(fā)任務結構。對于順序任務,由于邊緣云端擁有比移動設備端更強大的處理能力,因此將任務卸載至邊緣云端執(zhí)行可以大大降低應用完成時間。對于并發(fā)任務,除了需要充分利用邊緣云端處理能力,還需要利用移動設備端與邊緣云端的并行處理能力。以下就兩種任務類型的卸載決策分別作出討論。

3.1 順序任務卸載

為了降低順序任務的完成時間,可以盡可能將任務卸載至邊緣云端執(zhí)行以利用更強大的云端服務器處理能力。然而,此時的任務卸載會導致網(wǎng)絡數(shù)據(jù)傳輸時間增加,該時間需要小于卸載任務節(jié)省的時間,這樣才可以最終降低應用任務的完成時間。在某些情形中,網(wǎng)絡傳輸數(shù)據(jù)的時間可能高于任務在本地移動設備端執(zhí)行的時間。研究表明,順序任務圖的最優(yōu)卸載任務集合應為任務圖中連續(xù)任務序列。以圖1的任務圖為例,若部分任務需要卸載至邊緣云端以降低任務完成時間,則任務必須是連續(xù)相鄰的,如圖1中的任務j至任務k。

圖1 順序任務

對于線性拓撲結構的n個任務序列,假設第一任務和最后一個任務在本地移動設備端執(zhí)行,從任務j(入口任務)至任務k(出口任務)被卸載至邊緣云端執(zhí)行。給定入口任務j和出口任務k,其完成時間可計算為:

(5)

算法1順序任務卸載決策

1.In:G(V,E)

2.EntryTask←1

3.ExitTask←1

4.Tmin=T(1,1)

5.Forj←1 ton-1

//尋找入口任務EntryTask

6.Fork←jton-1

//尋找出口任務ExitTask

7.IfT(j,k)

8.EntryTask←j

9.ExitTask←k

10.Tmin=T(j,k)

11.End

12.Out:{Taski|j≤i≤k}

算法過程的詳細說明:步驟1輸入任務圖結構,步驟2將任務1初始為入口任務,步驟3也將任務1初始為出口任務,步驟4入口至出口任務間的完成時間初始化為一個最小值,步驟5-步驟11遍歷所有任務,在確定入口任務的情況下(步驟5),檢測所有可能出口任務情形(步驟6),若得到的順序任務群集的完成時間小于初始的最小值(步驟7),則在步驟8和步驟9分別更新入口任務和出口任務,并在步驟10更新完成時間最小值,最后在步驟12輸出確定的入口任務與出口任務間的任務。入口任務至出口任務間的任務集群即為需要卸載至邊緣云端執(zhí)行的任務集合。

3.2 并發(fā)任務卸載

對于給定的任務圖G(V,E),假設其開始于分叉(fork)任務0,終止于合并任務n。第一個分叉任務和最后一個合并任務通常在本地移動設備端執(zhí)行,由于第一個任務(通常稱為根任務)需要來自于本地設備的輸入,而最后一個任務(通常稱為終止任務)需要將生成數(shù)據(jù)傳回本地移動設備。并發(fā)任務卸載的目標是通過最大化移動設備和邊緣云端的并行度的方式最小化任務完成時間。以圖2為例說明,在根任務0與終止任務n+1之間擁有n個并發(fā)任務,如果卸載過多任務至邊緣云端,則移動設備必須等待邊緣云端完成所有任務計算;如果卸載過少任務至邊緣云端,則應用需要等待本地移動設備完成任務計算,這會延長總完成時間。任務卸載決策的最佳結果是:在邊緣云端執(zhí)行的任務與移動設備端執(zhí)行的任務之間的終端任務等待時間應該盡可能減少。為了實現(xiàn)這一目標,計算任務卸載時,本地任務的完成時間需要盡可能接近于卸載任務的完成時間和數(shù)據(jù)傳輸時間之和。

圖2 并發(fā)任務結構

對于一般并發(fā)任務結構圖而言,決定哪些任務進行卸載是NP問題。研究表明,卸載任務通常是以集群形式進行,一旦一個任務被卸載,卸載其鄰居任務時,通信代價可以有效降低,帶來任務最終可以集群形式進行卸載(線性順序任務結構中,連續(xù)任務也是集群形式)。然而,對于并發(fā)任務結構而言,尋找結構中的任務集群相對困難。本文的方法是:將并發(fā)任務圖修剪為樹結構,然后標識集群為子樹,并尋找卸載子樹。

1) 樹的生成:算法通過剪枝每個任務輸入鏈路將任務圖轉換為一棵樹,直到每個任務僅有一個父任務為止。通過剪枝策略,可以降低卸載決策問題復雜度。然而,該過程需要均衡信息損失問題(任務依賴約束關系),這可能導致子最優(yōu)的卸載決策。因此,算法僅剪枝數(shù)據(jù)負載最低的鏈路,以降低傳輸至子樹以外的數(shù)據(jù)量。圖3(a)所示為一個并發(fā)任務圖,任務5和任務8是合并任務,其輸入鏈路以網(wǎng)絡傳輸時間標記。由于t3,5>t2,5、t5,8>t6,8>t7,8,對鏈路(2,5)、(6,8)和(7,8)進行剪枝后,得到的任務樹如圖3(b)所示。

(a) (b)圖3 剪枝成樹

2) 負載均衡的任務劃分:令VC表示卸載至邊緣云端的任務集合,VM表示本地移動設備端執(zhí)行任務的集合,因此,VC+VM=V-{0,n},即從V中排除根任務0和終止任務n考慮任務卸載問題。由于卸載至邊緣云端的任務為集群形式,則在樹形拓撲中,若一個非葉子任務被卸載,則以該任務為根節(jié)點的子樹中的所有任務均需要一起卸載。該卸載決策在分叉任務上作出,其子任務將作為入口任務的候選節(jié)點。令tree(i)表示以任務i為根節(jié)點的子樹中的任務集合(包括i),定義Mi表示在移動設備端tree(i)中所有任務的執(zhí)行時間:

(6)

Ci表示邊緣云端tree(i)中所有任務的執(zhí)行時間:

(7)

定義Ventry為卸載的入口任務集合,Ventry中每個任務為卸載子樹的根節(jié)點。由于數(shù)據(jù)傳輸僅發(fā)生在樹拓撲中的入口任務上,定義Tnet為邊緣云端與移動設備端之間的數(shù)據(jù)傳輸總時間:

(8)

令TC表示邊緣云端任務的執(zhí)行時間:

(9)

由于子樹任務卸載至邊緣云端,假設相同子樹中的任務在邊緣云端順序執(zhí)行,且不在等待隊列中重復輸入,這表明僅需要計算入口任務到達時的排隊時間。最后,定義TM表示移動設備端所有任務的完成時間:

(10)

為了最小化并發(fā)任務的完成時間,需要均衡邊緣云端與本地移動設備的負載,使得移動設備端任務的完成應盡可能接近于邊緣云端任務執(zhí)行與數(shù)據(jù)傳輸時間之和。假設根任務在移動設備端執(zhí)行,則任務卸載決策最優(yōu)化問題可形式化為:

min|TM-TC-Tnet|

(11)

初始時,將VC設置為空集,這表明所有任務在本地移動設備。從根節(jié)點開始,如圖4所示。根節(jié)點的子任務公式(6)定義的Mi的降序進行排列,i表示根的一個子任務。對子樹中依次執(zhí)行任務的卸載決策直到滿足TM

圖4 樹的卸載

算法2并發(fā)任務卸載決策

1.In:G(V,E)

2.r=0(根任務卸載至邊緣云)/r=1(根任務在移動設備)

3.Vnet=NULL

4.Ifr==1 thenVC=NULL

5.ElseVC=V-{0,n}

6.currentTask=root

7.while root has childen

8.i←0

9.while (2r-1)(TM-TC)>Tnet

10.Task child←currentTask.getChild[i]

11.Ifr==1 thenVC←VC+tree(child)

12.ElseVC←VC-tree(child);end

13.Ventry←Ventry+child

14.i=i+1

15.End

16.Ifr==1 thenVentry←Ventry+child

17.ElseVC←VC-tree(child);end

18.Ventry←Ventry-child

19.//rool back offload for break task

20.currentTask=child

21.end

22.out:VC

算法過程的詳細說明:步驟1輸入并發(fā)任務結構圖,步驟2定義卸載決策因子,步驟3初始化一個任務集合,步驟4判定,若卸載決策因子為1,表明任務在本地設備執(zhí)行,則卸載至邊緣云端的任務集合為空,否則,剔除入口任務和終止任務,更新卸載任務集合,即步驟5。步驟6將根節(jié)點定義為當前任務,若該任務擁有子節(jié)點任務,則在步驟9-步驟15剪枝成樹的形式更新入口任務,若為本地執(zhí)行的任務,則直接將其子節(jié)點添加至入口任務集合以下,即步驟16,否則,刪減以該節(jié)點為起始的子樹,即步驟17。該過程需要在所有擁有子節(jié)點的任務節(jié)點上進行迭代,最后輸出的集合即為整個任務圖中需要卸載至邊緣云端執(zhí)行的任務集合。

3.3 通用任務卸載

本節(jié)描述如何合并算法1和算法2實現(xiàn)通用任務圖的卸載決策。通用任務圖由順序的鏈式任務圖和并發(fā)任務合并而成。為了實現(xiàn)通用任務圖的卸載決策,將每個并發(fā)任務集合視為一個虛擬任務,使其得到一個線性拓撲圖。如圖5(a)的示例,每個并發(fā)任務子圖表示為虛擬節(jié)點后,得到圖5(b)。其中,圖5(a)左側任務結構圖為Fork-join結構,圖5(b)右側任務結構圖為并行結構。定義虛擬任務的計算權重為:

圖5 通用任務結構

(12)

計算線性拓撲圖的卸載決策后,某些虛擬節(jié)點將卸載至邊緣云端,而一些虛擬節(jié)點又將在移動設備端執(zhí)行。對于任意一種情形,利用算法2計算虛擬節(jié)點中并發(fā)任務的卸載決策,進而有效利用移動設備端和邊緣云端的并行性。

當根任務和終止任務在本地移動設備執(zhí)行時,利用式(11)實現(xiàn)負載均衡目標。對于并發(fā)任務子圖的卸載決策而言,子圖中的根節(jié)點和終止節(jié)點可能不在本地移動設備執(zhí)行。引入變量r,r=0表示根節(jié)點在邊緣云端執(zhí)行,r=1表示根節(jié)點在本地移動設備端執(zhí)行。將式(11)的任務卸載負載均衡目標修正為以下通用卸載負載均衡目標:

min|(2r-1)(TM-TC)-Tnet|

(13)

4 仿真實驗

4.1 實驗配置

以隨機生成的任務結構圖測試卸載決策算法性能,實驗環(huán)境為MATLAB。任務結構圖的生成重點考慮兩個屬性參數(shù):(1) 任務規(guī)模,即有向圖中任務的總數(shù)量;(2) 任務間的鏈接密度,以每個任務的平均出度數(shù)進行設置。任務出度表示在一個任務有向圖中,從一個任務節(jié)點出發(fā)的有向邊的條數(shù)。任務權重和連接權重通過均勻分布方式隨機生成。設置本地移動設備的CPU的μm=1,表1給出了仿真實驗中相關參數(shù)配置,其中,free代表參數(shù)為自由變量。四類參數(shù)配置中,取值為free時,其他三個參數(shù)則為固定值。為了對比算法性能,引入兩種同類型的任務卸載決策算法,一種是文獻[11]的ODE算法,一種是利用窮舉算法OPTIMAL得到的理論最優(yōu)解。由于在設定的任務規(guī)模下,可在有限時間內(nèi)通過窮舉法得到最優(yōu)的任務卸載決策解,但任務規(guī)模增大時,窮舉法的搜索時間復雜度將呈指數(shù)級增長,因此,引入該算法僅僅是用于衡量本文算法與理論最優(yōu)解間的差距,并以此間接度量算法性能。

表1 參數(shù)配置

4.2 實驗結果

圖6表示任務圖中任務數(shù)量對完成時間的影響?？梢钥吹?本文算法得到的完成時間約為最優(yōu)算法OPTIMAL結果的85%～90%,ODE算法的完成時間則與最優(yōu)算法相距45%(20個任務)～75%(5個任務),任務規(guī)模較小時該算法表現(xiàn)較好,是由于較小規(guī)模任務量更加有可能以集群形式進行任務卸載。隨著任務規(guī)模的增加,卸載任務更加分散,這會增加數(shù)據(jù)傳輸量,導致總體完成時間的遞增。

圖6 任務數(shù)量的影響

圖7表示任務圖中單個任務的平均出度對完成時間的影響,節(jié)點出度表示由任務節(jié)點出發(fā)的有向邊的條數(shù),通過任務圖中總的有向邊條數(shù)除以任務總數(shù)確定。可以看到,任務圖中的鏈接密度對任務總的完成時間影響較小,說明該參數(shù)不會過度影響算法性能。ODE算法的性能從57%(平均出度為1)降低至46%(平均出度為8)。由于任務圖中的鏈接密度的增加會導致任務卸載的數(shù)據(jù)傳輸代價的增加,因此,該算法較難作出最佳的任務卸載決策。

圖7 任務平均出度的影響

圖8表示網(wǎng)絡通信帶寬對于完成時間的影響?？梢钥吹?隨著網(wǎng)絡帶寬的增加,性能趨勢呈凹狀下降。本文算法在帶寬為0.1時接近于最優(yōu)算法的90%性能,至帶寬為1.5時增加至95%。當帶寬處于1.5至10區(qū)間時,算法性能出現(xiàn)輕微下降,原因在于算法可以以任務的序列形式將任務在本地移動設備上執(zhí)行,這會導致更少的任務卸載至邊緣云端。ODE算法在帶寬為0.1時接近于最優(yōu)算法的70%性能,至帶寬為1時增加至50%。帶寬從0.1變化至1時,ODE算法可以卸載更多任務進而降低完成時間,然后與本文算法相比,距離最優(yōu)算法仍然較遠,該算法對于任務卸載決策不是最優(yōu)的,也沒有考慮任務圖的內(nèi)在結構。隨著帶寬量的增加,ODE算法逐漸卸載其所有任務去邊緣云端,導致其性能上升至70%。

圖8 通信帶寬的影響

圖9表示邊緣云端排隊時間對于完成時間的影響。本文算法距離最優(yōu)算法性能約為85%～90%,而ODE算法則是45%～55%。由于ODE算法沒有考慮任務在邊緣云端的排隊時間,算法選擇卸載的任務數(shù)量是平均相同的,與邊緣云端排隊時間無關,最終導致其完成時間是接近于線性的。

圖9 邊緣云端排隊時間的影響

綜合考慮以上結果可以看到,本文算法得到的完成時間總體接近于理論最優(yōu)算法的85%,ODE則是接近于50%,其主要不足體現(xiàn)于兩點:(1) 本文算法一次僅卸載單個任務,無法實現(xiàn)集群式的任務卸載決策,這樣導致了過多頻繁的任務卸載決策,尤其在網(wǎng)絡帶寬限制較多時,會出現(xiàn)較大的完成延時;(2) 本文算法沒有考慮移動設備端與邊緣云端的并行性。若給定帶寬足夠大,ODE算法會卸載所有任務至邊緣云端,由于此時卸載任務的傳輸代價低于本地執(zhí)行與云端執(zhí)行時間之差。本文算法可以根據(jù)當前的負載狀況對特定任務圖結構作出最優(yōu)卸載決策,可以得到與理論最優(yōu)解更接近的解。

5 結 語

為了實現(xiàn)移動邊緣云環(huán)境中移動設備任務執(zhí)行時間的優(yōu)化,提出一種任務卸載決策算法。算法考慮了更為普遍的混合任務結構類型。對于順序任務構成的線性拓撲任務圖,算法可以找到最優(yōu)的卸載任務;而對于并發(fā)任務的通用拓撲任務圖,算法可以實現(xiàn)任務卸載的更好負載均衡。仿真實驗結果證明,與基準算法相比,本文算法得到的任務完成時間與理論最優(yōu)解更為接近,任務完成效率更高。