移動邊緣計算環(huán)境下基于移動感知的工作流調(diào)度算法

魏澤豐，周元元

(1.杭州電子科技大學(xué) 計算機學(xué)院，浙江 杭州 310018； 2. 合肥師范學(xué)院 電子信息系統(tǒng)仿真設(shè)計安徽省重點實驗室，安徽 合肥 23009)

隨著智能移動設(shè)備和人工智能技術(shù)[1]的高速發(fā)展，人臉識別、自然語言處理、虛擬現(xiàn)實、深度學(xué)習(xí)模型壓縮[2]等新興技術(shù)逐漸被布局在移動設(shè)備上，這對移動設(shè)備的計算能力、內(nèi)存、電池容量提出了挑戰(zhàn)[3-4]。傳統(tǒng)方法中，移動用戶可以將工作流任務(wù)卸載到云端服務(wù)器，從而提高服務(wù)質(zhì)量，但是這種方式存在延遲過高、帶寬有限、極度中心化等缺點，大幅度降低了用戶服務(wù)質(zhì)量(Quality of Service，QoS)。近年來，研究人員對云計算技術(shù)進(jìn)行了優(yōu)化，提出了移動邊緣計算[5](Mobile Edge Computing，MEC)的概念。在MEC環(huán)境下，用戶將計算密集型應(yīng)用卸載到基站(evolved Node B，eNB)配置的邊緣服務(wù)器中，從而降低任務(wù)的響應(yīng)時間，減少本地能源消耗并增強隱私保護(hù)。

移動邊緣計算也受到學(xué)術(shù)界的廣泛關(guān)注。任務(wù)調(diào)度是移動邊緣計算研究中最核心的部分，是向用戶提供優(yōu)質(zhì)服務(wù)的關(guān)鍵。因此，研究人員對移動邊緣計算環(huán)境下的任務(wù)調(diào)度問題進(jìn)行了一系列研究。文獻(xiàn)[6]考慮了任務(wù)執(zhí)行者之間的默契程度，并將其定義為協(xié)作相容性，提出了一種兼顧協(xié)作相容性和任務(wù)負(fù)載的任務(wù)分配算法，提高了整個工作流的執(zhí)行效率。為了實現(xiàn)最大收益和服務(wù)利用率，文獻(xiàn)[7]在考慮延遲容忍和延遲約束的前提下，對任務(wù)進(jìn)行優(yōu)先級排序以優(yōu)化任務(wù)分流，有效降低了服務(wù)延遲。文獻(xiàn)[8]提出了一種基于凸函數(shù)優(yōu)化的迭代搜索算法，將移動設(shè)備電池的剩余容量引入到能耗和等待時間的加權(quán)因子中，優(yōu)化了網(wǎng)絡(luò)和計算資源的分配，達(dá)到減少能耗的目的。文獻(xiàn)[9]提出了一種多維博弈算法，避免用戶同時集中卸載任務(wù)到同一個基站，優(yōu)化了移動端能耗和任務(wù)的排隊延時。文獻(xiàn)[10]設(shè)計了一種針對保密設(shè)置、計算分流、網(wǎng)絡(luò)資源的聯(lián)合優(yōu)化卸載方案，避免在任務(wù)卸載過程中遭遇惡意竊聽，提高了任務(wù)的卸載成功率。文獻(xiàn)[11]研究了混合邊緣云環(huán)境下工作流任務(wù)的運算符放置問題，提出了一種啟發(fā)式方法來制定任務(wù)執(zhí)行方案，縮短了應(yīng)用程序的響應(yīng)時間。文獻(xiàn)[12] 提出了一種基于平均場博弈(Mean Field Game，MFG) 和深度強化學(xué)習(xí)的負(fù)載均衡調(diào)度算法，將任務(wù)合理分配給每個邊緣服務(wù)器，降低了平均服務(wù)延遲。

然而，移動用戶通常具有較高的移動性，如果在任務(wù)卸載時忽略用戶的移動性，將降低任務(wù)的卸載成功率，例如用戶卸載任務(wù)到邊緣服務(wù)器之后，離開了eNB的通信范圍，這將導(dǎo)致任務(wù)卸載失敗。因此，捕獲用戶的移動性并執(zhí)行有效的任務(wù)卸載策略來避免任務(wù)失敗，并減少任務(wù)執(zhí)行時間，降低移動端能耗已成為主要問題。本文提出了基于移動感知的工作流調(diào)度MaWS(Mobility-aware Workflow Scheduling)算法。首先，該算法通過STGAT[13]預(yù)測用戶的行為軌跡，得到每個時間段內(nèi)的可卸載eNB；然后，通過遺傳算法制定全局卸載策略，避免卸載工作流失敗。相比于幾種經(jīng)典調(diào)度算法，MaWS能夠顯著減少工作流的完工時間并降低移動端能耗。

1 模型以及問題描述

1.1 工作流模型

用戶執(zhí)行的工作流W表示為一個有向無環(huán)圖(Directed Acyclic Graph)，記為W={wi|wi=(T，V)}。其中，T為工作流任務(wù)的集合T={ti|ti=(IDti，ODti，W(ti))}， IDti、ODti和W(ti)分別表示ti的輸入數(shù)據(jù)大小、輸出數(shù)據(jù)大小和計算量。V表示工作流任務(wù)之間的依賴關(guān)系，V= {(ti，tj)| (ti，tj)∈T}，其中ti是tj的前驅(qū)任務(wù)，tj是ti的后繼任務(wù)，ti的前驅(qū)任務(wù)表示為pre(ti)，tj的后繼任務(wù)表示為succ(tj)。

1.2 網(wǎng)絡(luò)信號模型

用戶在移動過程中移動設(shè)備(Mobile Device，MD)與每個eNB之間的蜂窩信號也在不斷改變。在本文環(huán)境中，假設(shè)時間系統(tǒng)是離散的并按等長間隔變化，如圖1所示，即τ=0，1，…，每個時間間隔的時長為Tslot。在每個時間段τ內(nèi)，MD與eNB的蜂窩信號的強度為恒定值R(τ)。

圖1 每個時間段的信號狀態(tài)Figure 1. Signal status for each time period

R(τ)的大小取決于MD與eNB之間的距離以及信噪比，MDi與eNBj的傳輸信噪比為

(1)

Rn=Blog2(1+fSNR(di，n(τ)))

(2)

1.3 軌跡預(yù)測模型

本文采用STGAT[13](Spatial-Temporal Graph Attention network)算法預(yù)測用戶的未來軌跡。STGAT基于序列到序列(Sequence to Sequence)架構(gòu)，通過圖注意力網(wǎng)絡(luò)[14](Graph Attention Network，GAT)獲取每個時間段τ內(nèi)行人之間的空間交互信息，并利用額外的長短時記憶網(wǎng)絡(luò)[15](Long Short Term Memory Network，LSTM)解析軌跡之間的時間相關(guān)性，進(jìn)一步提高軌跡預(yù)測的準(zhǔn)確率。

(3)

式中，ex和ey表示eNB的位置坐標(biāo)；maxDis為MD與eNB的最大通信距離。

1.4 任務(wù)執(zhí)行模型

MEC環(huán)境下，用戶產(chǎn)生的工作流任務(wù)可以卸載到eNB或在MD本地執(zhí)行。如果任務(wù)ti在MD執(zhí)行，則需要從eNB或MD獲取任務(wù)ti的輸入數(shù)據(jù)。若任務(wù)ti的前驅(qū)任務(wù)pre(ti)在eNB中執(zhí)行，則先要從eNB中接收輸出數(shù)據(jù)。假設(shè)當(dāng)前時間段為τ=h，此時MD從eNB接收數(shù)據(jù)的傳輸時間為

(4)

(5)

式中，D(ti，tj)表示前驅(qū)任務(wù)tj需要傳輸給任務(wù)ti的數(shù)據(jù)大小。

MD通過蜂窩網(wǎng)絡(luò)接收輸入數(shù)據(jù)的同時，產(chǎn)生了接收能耗，表示為式(6)。

(6)

當(dāng)所有前驅(qū)任務(wù)的輸出數(shù)據(jù)都傳輸?shù)組D時，任務(wù)ti即可開始在MD執(zhí)行，所需執(zhí)行時間如式(7)所示。

(7)

MD在執(zhí)行任務(wù)ti時所消耗的能源如式(8)所示。

(8)

若要將任務(wù)卸載到eNB執(zhí)行，則需要將MD中的數(shù)據(jù)發(fā)送到目標(biāo)eNB。MD發(fā)送數(shù)據(jù)的傳輸時間為

(9)

(10)

eNB在接收完數(shù)據(jù)之后，即可開始執(zhí)行任務(wù)，執(zhí)行時間為式(11)。

(11)

MD在將任務(wù)卸載到eNB執(zhí)行時將產(chǎn)生傳輸能耗，表示為式(12)。

(12)

由上述任務(wù)執(zhí)行過程的分析可知，MD的能源消耗主要由發(fā)送、接收數(shù)據(jù)的傳輸能耗以及MD執(zhí)行任務(wù)的能耗3部分組成。工作流的執(zhí)行時耗主要由MD接收和發(fā)送數(shù)據(jù)的傳輸時間、MD本地執(zhí)行任務(wù)的耗時以及任務(wù)在eNB的執(zhí)行耗時4部分組成。

1.5 問題描述

縮短工作流的完工時間和降低移動端能耗，是本文工作流調(diào)度的優(yōu)化目標(biāo)。為了計算工作流的完工時間，需要計算每個任務(wù)的開始時間和結(jié)束時間。通常情況下，任務(wù)ti的前驅(qū)任務(wù)可能在eNB或MD執(zhí)行，那么任務(wù)ti的開始時間即為所有前驅(qū)任務(wù)中的最晚完成時間，即式(13)。

Tstart(ti)=maxtj∈pre(ti){Tend(ti)}

(13)

在計算任務(wù)的結(jié)束時間時，分兩種情況，若任務(wù)ti在MD本地執(zhí)行，則結(jié)束時間為任務(wù)開始時間、MD接收數(shù)據(jù)的傳輸時間和任務(wù)在MD的執(zhí)行時間的總和，即

(14)

同理，若任務(wù)ti在eNB執(zhí)行，則任務(wù)ti的結(jié)束時間為式(15)。

(15)

(16)

綜合式(14)～式(16)，工作流的完工時間和移動端能耗分別如下所示。

(17)

(18)

基于以上分析，本文MEC環(huán)境下的工作流調(diào)度問題可總結(jié)為：在執(zhí)行工作流任務(wù)前，根據(jù)預(yù)測軌跡計算MD與每個eNB之間的通信狀態(tài)，根據(jù)這些先驗信息利用算法得到調(diào)度策略Γ，通過該調(diào)度策略最小化MD的能耗和工作流的完工時間，如下式所示。

F(Γ)=(energy，makespan)

(19)

s.t. makespan

(20)

dist(u，e)

(21)

2 算法設(shè)計

本文提出的MaWS算法基于遺傳算法[16]，其執(zhí)行流程如圖2所示。

圖2 MaWS算法執(zhí)行流程圖Figure 2. Flow chart of MaWS execution

2.1 編碼方案

在進(jìn)行遺傳算法編碼時，需要分別考慮工作流任務(wù)的執(zhí)行順序以及卸載位置。圖3表示本文遺傳算法的編碼示例。集合E={e0，e1，…，en-1}表示任務(wù)的執(zhí)行順序集合，其中，ei表示工作流中的某個任務(wù)，在理論上，ei∈{t0，t1，…，ti，tn-1}。但是任務(wù)的排序需要滿足先序限制關(guān)系，即只有當(dāng)任務(wù)t0的前驅(qū)任務(wù)全部完成時，t0才能開始執(zhí)行，因此開始任務(wù)tstart和結(jié)束任務(wù)tend必須分別排在第1位和最后。集合L={L1，L2，…，Ln}用來表示工作流任務(wù)卸載位置的集合，li=0表示任務(wù)ti在本地執(zhí)行，li=n(n>0)表示任務(wù)卸載到相應(yīng)eNB執(zhí)行。

圖3 編碼方案Figure 3. Coding scheme

2.2 適應(yīng)度

在評價基因的適應(yīng)度時，需要同時考慮用戶設(shè)備的能耗以及工作流的完成時間。如式(22)所示，WE和WT分別表示能耗和完工時間的優(yōu)化權(quán)重。在制定調(diào)度策略時，可根據(jù)工作流任務(wù)對能耗和完工時間的需求，調(diào)整這兩個優(yōu)化權(quán)重。

fitness(x)=WEenergy+WTmakespan

(22)

2.3 初始化

MaWS算法中，任務(wù)執(zhí)行的排序和位置均采用隨機的方式生成。如算法1所示，集合T表示所有工作流任務(wù)，集合R用來記錄已排序任務(wù)，集合S表示當(dāng)前沒有前驅(qū)或者其前驅(qū)排序完畢的任務(wù)。執(zhí)行算法時，每次都從T中選取符合條件的任務(wù)加入到S中(第7～11行)；然后根據(jù)STGAT預(yù)測的用戶軌跡得到每個時間段τ內(nèi)可以卸載的eNB集合(第12～13行)；之后為S中的任務(wù)隨機分配卸載的eNB或本地執(zhí)行(第14～16行)；當(dāng)T中的任務(wù)為空時，基因生成完畢。

算法1 生成初始基因輸入:工作流W, 軌跡數(shù)據(jù)TrajData。輸出: 基因G。1. S =?; /?可排序任務(wù)集合?/2. R = {t0}; /?已排序任務(wù)?/3. T= T -{t0};4. E = {}; /?基因中任務(wù)的執(zhí)行位置部分?/5. while T ≠ ? do6. S= {};7. for each ti in T do8. if pre(ti)∈R or pre(ti).size == 09. S.add(ti);10. end if;11. end for12. Trajτ= TrajData.get(τ); /?得到時刻τ的軌跡數(shù)據(jù)?/13. eNBSet = geteNBSet(Trajτ); /?得到可卸載基站?/14. for each task ti in S do15. E(ti) = random{eNBSet, MD};16. End for17. T = T-S;18. R = R + S;19. S = {};20. end while

2.4 選擇

MaWS算法中采用輪盤賭算法選擇需要進(jìn)行交叉和變異的兩個基因。

2.5 交叉

交叉算子能夠通過將兩個染色體交換組合，將父染色體的優(yōu)秀特征遺傳給子染色體，并避免局部最優(yōu)解。MaWS算法中的交叉算子，如算法2所示。兩個基因的任務(wù)排序集合分別為E1和E2，通過隨機數(shù)的方式確定基因的交叉區(qū)域E12和E21，然后在E12和E21的交叉區(qū)域后分別加上集合E1和E2，得到兩個新的臨時個體(第7～8行)，并刪除兩個臨時個體中的重復(fù)任務(wù)。此時，E12和E21即為交叉完成后的新個體。新個體的任務(wù)排序仍舊滿足先序限制關(guān)系，不會因為任務(wù)的錯誤排序?qū)е氯蝿?wù)死鎖。

算法2 基因交叉算法輸入:舊基因G1、G2。輸出:新基因G′1、G′2。1.Generate a random number r in [0,n-1]2.E12=E21=?; 3.for k = 0 to r do4. E12=E12 +e1k; 5. E21=E21 +e2k;6.end for7.E12=E12 + E2;8.E21=E21 + E1;9.remove duplicate tasks in E12, E21;10.L12=L21= ?;11.for k = 0 to r do 12. L12=L12 + lk1;13. L21=L21 + lk2;14.end for15.for i = 0 to n do 16. if L12(i) not in availableeNB17. L12(i) = random(availableeNB, local);18. end if19. if L21(i) not in availableeNB20. L21(i) = random(availableeNB, local);21. end if22.end for

完成任務(wù)執(zhí)行順序部分的交叉之后，需要對任務(wù)的執(zhí)行位置部分進(jìn)行交叉，假設(shè)兩個基因的執(zhí)行位置部分分別為L1、L2。首先，根據(jù)隨機數(shù)確定L1和L2的交叉區(qū)域，并對基因進(jìn)行交叉(第11～14行)；然后，需要對任務(wù)執(zhí)行位置進(jìn)行遍歷，判斷任務(wù)ti能否卸載到對應(yīng)執(zhí)行位置上的eNB，如果無法卸載，需要從MD和可卸載eNB集合中隨機選出一個位置，這樣能夠保證卸載的可靠性(第15～22行)。

2.6 變異

MaWS算法中的變異算子，如算法3所示。首先，通過隨機數(shù)的方式確定變異任務(wù)ei，并從任務(wù)排序集合E向前遍歷，當(dāng)某個任務(wù)eb使得任務(wù)ei的全部前驅(qū)都在集合{e0，…，eb}內(nèi)，則停止搜索(第2～4行)。同理，從集合E逆向進(jìn)行遍歷，當(dāng)某個任務(wù)ea使得任務(wù)ei的全部后繼都在{ea，…，en-1}內(nèi)，則停止搜索(第5～7行)；然后，可以任意改變集合E′={eb+1，…，ea-1}中任務(wù)執(zhí)行位置，并且保證集合E中任務(wù)之間的先序限制關(guān)系；最后，將任務(wù)ei隨機插入一個新的位置(第9行)。

完成基因的任務(wù)執(zhí)行順序部分變異后，通過隨機數(shù)的方式確定執(zhí)行位置部分的變異點，并更改該點對應(yīng)任務(wù)的執(zhí)行位置。由于基因執(zhí)行順序和執(zhí)行位置的對應(yīng)關(guān)系會隨著變異而改變，所以需要對任務(wù)執(zhí)行順序進(jìn)行遍歷，判斷任務(wù)ti能否有效卸載(第12～16行)。

算法3 排序變異算法輸入:變異前基因G。輸出:變異后基因G′。1.Generate a random number r in [0,n-1];2.for i = 0 to n-1 do3. find ebst pre(ti)∈{e0,…,eb};4.end for5.for i = n-1 to 0 do6. find ea st succ(ti)∈{e0,…,eb};7.end for8.Get set E′ ={eb+1,…,ea-1};9.Select the insertion position in set E′;10.Get new set E = {e0,…,eb} + E′+ {eb+1,…,ea-1};11.L(r) = random(availableeNB, local);12.for i = 0 to n do 13. if L(i) not in availableeNB14. L(i) = random(availableeNB, local);15. end if16.end for

3 模擬實驗

本節(jié)進(jìn)行了實驗評估，并分析了MaWS算法的性能，通過改變調(diào)度策略與卸載策略，對MaWS算法與傳統(tǒng)算法的完工時間以及移動端能耗進(jìn)行了比較分析。

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

本文用戶生成的工作流的任務(wù)個數(shù)范圍為4～20，每個任務(wù)的工作量服從[1，10]均勻分布(單位為GHz)，每個任務(wù)的輸入輸出數(shù)據(jù)大小服從[1，10]均勻分布(單位為MB)，每個任務(wù)的最大完成時長都為1 s。移動設(shè)備的計算能力為2.4 GHz，計算功耗為0.5 W。數(shù)據(jù)的發(fā)送、接收功率分別為0.1 W和0.05 W，邊緣服務(wù)器的計算能力為5 GHz。移動設(shè)備與eNB的通信范圍為50 m。路徑損耗因子δ=-174 dBm·Hz-1，傳輸帶寬B=10 MHz，路徑損耗指數(shù)g0=-40 dB。

3.2 數(shù)據(jù)集

本文使用預(yù)處理后的斯坦福大學(xué)行人數(shù)據(jù)集[17]來模擬移動邊緣計算環(huán)境。該數(shù)據(jù)集中記錄了斯坦福大學(xué)校區(qū)內(nèi)行人的運動軌跡，本文選擇Bookstore的行人軌跡數(shù)據(jù)作為STGAT的訓(xùn)練集，鳥瞰圖和軌跡預(yù)測結(jié)果如圖4所示。

(a)

(b)圖4 鳥瞰圖及軌跡預(yù)測結(jié)果圖 (a)Bookstore鳥瞰圖 (b)軌跡預(yù)測結(jié)果圖Figure 4. Bird′s-eye view and trajectory prediction results (a)Bird′s-eye view of bookstore (b)Trajectory prediction results

3.3 對比實驗

本節(jié)通過改變調(diào)度策略與卸載策略，比較了MaWS與傳統(tǒng)算法的完工時間和能耗，驗證了MaWS算法的優(yōu)化效果。

不同調(diào)度策略下，工作流完工時間、移動端能耗與工作流任務(wù)數(shù)的關(guān)系如圖5和圖6所示。通過對比可以觀察到，相比GA算法和HEFT算法，MaWS算法能夠減少10%～15%的工作流完工時間以及8%～13%的移動端能耗。當(dāng)工作流任務(wù)數(shù)量小于8時，MaWS算法與GA算法的優(yōu)化效果相近。這是因為當(dāng)任務(wù)數(shù)量較小時，工作流的整體執(zhí)行時間較短，即使不考慮用戶未來與基站的通信情況，對最終結(jié)果的影響也不大。當(dāng)工作流任務(wù)數(shù)量大于8時，MaWS算法優(yōu)勢開始體現(xiàn)。這是因為隨著任務(wù)數(shù)量的增加，會導(dǎo)致任務(wù)所需執(zhí)行時間增加。用戶由于移動與基站斷開連接，使得任務(wù)卸載失敗，因此需要重新傳輸數(shù)據(jù)，導(dǎo)致GA算法制定的調(diào)度方案從近似最優(yōu)解退化到不可行解。當(dāng)工作流變得更加復(fù)雜時，這一劣勢將更加明顯。而MaWS算法在制定卸載策略時考慮了用戶的移動軌跡，得出用戶未來與基站的通信情況，最大程度避免了通信中斷導(dǎo)致的任務(wù)卸載失敗。

圖7和圖8給出了不同卸載位置情況下，工作流完工時間、移動端能耗與工作流任務(wù)數(shù)的關(guān)系。由結(jié)果可知，MaWS算法的優(yōu)化效果明顯優(yōu)于其他算法。Greedy算法只考慮將任務(wù)卸載到與用戶設(shè)備傳輸收益最大的eNB，但由于用戶具有移動性，可能會導(dǎo)致設(shè)備在卸載任務(wù)的過程中與eNB失聯(lián)，從而導(dǎo)致任務(wù)重傳，增加了設(shè)備能耗并延長了完工時間。Random算法由于具有隨機性，最終的效果也不穩(wěn)定。MaWS算法通過STGAT預(yù)測的用戶軌跡制定最優(yōu)卸載策略，相比于其他算法可以有效地減少工作流執(zhí)行時間并降低移動端能耗。

圖5 不同調(diào)度策略下的工作流耗時Figure 5. Workflow time-consuming under different scheduling strategies

圖6 不同調(diào)度策略下的設(shè)備能耗Figure 6. Equipment energy consumption under different scheduling strategies

圖7 不同卸載位置下的工作流耗時Figure 7. Workflow time-consuming in different offloading positions

圖8 不同卸載位置下的設(shè)備能耗Figure 8. Equipment energy consumption under different offloading positions

4 結(jié)束語

本文對移動邊緣環(huán)境下的工作流調(diào)度問題進(jìn)行研究，針對其中存在的工作流時間較長和能耗較高的問題，提出了基于移動感知的工作流調(diào)度算法，即MaWS。該算法根據(jù)預(yù)測用戶未來軌跡得出用戶未來與eNB的通信狀態(tài)，并將這些信息融入遺傳算法，制定合理的任務(wù)執(zhí)行順序以及位置。本文通過仿真實驗將MaWS算法與傳統(tǒng)調(diào)度算法進(jìn)行對比，實驗表明本文提出的MaWS算法能夠有效地降低移動端能耗并減少工作流完工時間。未來將在算法中引入 D2D 卸載的調(diào)度方案，并對容錯、調(diào)度優(yōu)化等問題進(jìn)行探索。