基于邊緣云環(huán)境的工作流調(diào)度與卸載決策算法

金 儉，鄭 倩

(1.黃河科技學(xué)院 現(xiàn)代教育技術(shù)中心，河南 鄭州 450063；2.鄭州輕工業(yè)大學(xué) 軟件學(xué)院，河南 鄭州 450002)

0 引 言

隨著智能終端設(shè)備的廣泛流行，移動終端所能執(zhí)行的應(yīng)用類型越來越多樣化，如圖像處理、面部識別及增強現(xiàn)實等應(yīng)用，越來越多地運行在移動終端[1]。以上應(yīng)用類型的任務(wù)構(gòu)成并非單純的完全串行或并行結(jié)構(gòu)，而是更為復(fù)雜的工作流結(jié)構(gòu)。處理工作流應(yīng)用需要高性能處理資源，以獲取更好的用戶體檢[2,3]，邊緣云任務(wù)卸載即是在這種背景下產(chǎn)生的[4,5]。利用卸載，用戶可將任務(wù)需求從本地卸載到能力更強的邊緣云上執(zhí)行，憑借邊緣云的性能優(yōu)勢，加快任務(wù)執(zhí)行效率，節(jié)省本地能源消耗。然而，工作流任務(wù)的特殊結(jié)構(gòu)及移動客戶端與邊緣云服務(wù)器間的無線通信條件為工作流任務(wù)調(diào)度與卸載決策帶來了挑戰(zhàn)，體現(xiàn)在：①延時敏感型應(yīng)用在本地執(zhí)行勢必導(dǎo)致較長響應(yīng)時間，部分卸載方法需要在考慮執(zhí)行時長和本地能耗基礎(chǔ)上進(jìn)行任務(wù)卸載，這是帶約束條件的優(yōu)化問題；②任務(wù)卸載執(zhí)行雖然可以性能更強的云端資源處理本地任務(wù)，但傳輸時延、傳輸能耗及通信環(huán)境均會對卸載決策產(chǎn)生影響，卸載決策需考慮多方面因素；③調(diào)度時長和能耗優(yōu)化作為兩個沖突目標(biāo)，在實際卸載決策過程中需均衡考慮。若要降低調(diào)度時長，勢必要卸載更多任務(wù)至邊緣云，但過多傳輸時間反過來會增加響應(yīng)時間，同時會額外增加傳輸能耗；為了降低本地能耗，同時會導(dǎo)致更多任務(wù)卸載執(zhí)行，而這同樣會帶來調(diào)度時長增加。

為了實現(xiàn)移動客戶端能量約束條件下的工作流調(diào)度效率的優(yōu)化，在邊緣云中設(shè)計一種卸載決策算法PCTSO。算法重點解決了待調(diào)度任務(wù)的優(yōu)先級確定問題和連續(xù)依賴工作流任務(wù)的卸載決策問題，在提升任務(wù)執(zhí)行并行度的同時，還可以優(yōu)化工作流的執(zhí)行效率和移動客戶端的能量消耗。

1 相關(guān)研究

有關(guān)邊緣云環(huán)境中的任務(wù)調(diào)度與卸載決策問題，文獻(xiàn)[6]提出一種以最小化移動客戶端的能耗，滿足任務(wù)執(zhí)行截止時間約束的任務(wù)卸載算法。文獻(xiàn)[7]通過檢測每個邊緣云的每個時槽決定任務(wù)是在本地執(zhí)行還是卸載執(zhí)行，所設(shè)計的卸載決策算法可以通過線性規(guī)劃方法在滿足能量約束的情況下最小化任務(wù)執(zhí)行的總延時。為了降低本地能耗，滿足延時約束，文獻(xiàn)[8]提出基于Lyapunov優(yōu)化的動態(tài)卸載算法。文獻(xiàn)[9]在多用戶應(yīng)用分割與卸載環(huán)境下設(shè)計了離線卸載算法，實現(xiàn)了執(zhí)行延時的優(yōu)化。文獻(xiàn)[10]提出基于馬爾可夫決策的朵云任務(wù)卸載算法。但是，朵云受限于無線網(wǎng)絡(luò)覆蓋，服務(wù)連續(xù)性較差，無法應(yīng)用在邊緣云卸載決策問題。文獻(xiàn)[11]同樣利用馬爾可夫決策對卸載決策進(jìn)行了建模。文獻(xiàn)[12]設(shè)計了博弈分布式卸載決策算法，文獻(xiàn)[13]聯(lián)合考慮通信資源和計算資源分配，設(shè)計了迭代任務(wù)卸載算法。對于工作流結(jié)構(gòu)的邊緣云中的任務(wù)卸載決策問題，文獻(xiàn)[14]將容錯機(jī)制考慮在任務(wù)卸載中，有利于恢復(fù)邊緣云的任務(wù)執(zhí)行。文獻(xiàn)[15]提出將每個任務(wù)卸載至朵云中，實現(xiàn)移動客戶端的執(zhí)行延時和執(zhí)行能耗的最小化。模型中，若一個任務(wù)卸載至朵云，則其后繼任務(wù)也會被檢測是否卸載至相同朵云中執(zhí)行。在執(zhí)行延時和能耗同步降低時可將其進(jìn)行卸載至朵云。文獻(xiàn)[16]設(shè)計了負(fù)載均衡的工作流卸載算法LBOA，該算法更多考慮的是將移動終端的負(fù)載均勻地分布于邊緣云端和移動客戶端，沒有過多考慮調(diào)度效率和執(zhí)行能耗問題。文獻(xiàn)[17]設(shè)計了面向邊緣側(cè)卸載的兩階段工作流調(diào)度算法，通過隱性馬爾可夫鏈預(yù)測負(fù)載量，從而保證任務(wù)調(diào)度的成功率。文獻(xiàn)[18]提出了基于遺傳算法的任務(wù)卸載方法，有效實現(xiàn)了移動服務(wù)的執(zhí)行效率與執(zhí)行能耗的平衡。文獻(xiàn)[19]設(shè)計了一種多重資源卸載能耗模型，利用粒子群算法對該模型下的任務(wù)調(diào)度進(jìn)行了求解，在滿足響應(yīng)時間約束的同時降低了設(shè)備能耗。算法同樣解決的是工作流式任務(wù)的調(diào)度與卸載決策問題，但側(cè)重于以單個任務(wù)作為決策基準(zhǔn)，不考慮任務(wù)關(guān)聯(lián)性。文獻(xiàn)[20]將卸載決策問題建立為能耗和時延加權(quán)的凸優(yōu)化問題，并設(shè)計了基于乘子法的卸載決策策略，證實了終端能耗和執(zhí)行時延遠(yuǎn)低于本地執(zhí)行。文獻(xiàn)[21]同樣是以卸載決策問題的聯(lián)合凸優(yōu)化為基礎(chǔ)進(jìn)行任務(wù)卸載的求解，降低了任務(wù)執(zhí)行開銷。以上兩篇文獻(xiàn)則主要側(cè)重于單純的串行或并行任務(wù)，不是更為復(fù)雜的工作流結(jié)構(gòu)任務(wù)的調(diào)度與卸載決策問題。綜合考慮已有工作，對于任務(wù)的卸載決策通常是一種one-by-one模式的。現(xiàn)實情況是，卸載任務(wù)和本地執(zhí)行任務(wù)可能是工作流結(jié)構(gòu)中的一條路徑，是否可以將處于一條路徑上的若干任務(wù)集進(jìn)行整體卸載是值得研究的問題，此時不僅可以節(jié)省大量的任務(wù)間數(shù)據(jù)的傳輸時間，還可以降低本地設(shè)備的執(zhí)行能耗。

2 基本模型

表1首先給出主要的符號定義說明。

表1 符號說明

2.1 系統(tǒng)模型

邊緣云系統(tǒng)中，假設(shè)擁有一個可提供多虛擬機(jī)VM實例的邊緣云服務(wù)器，其可用的虛擬CPU(vCPUs)集合定義為Cv cpu，Cv m為虛擬機(jī)實例集合，則|Cv m|≤|Cv cpu|。令vi表示虛擬機(jī)實例i，ci,j表示虛擬機(jī)實例i上的vCPUj，且ci,j∈Cv cpu。假設(shè)邊緣云服務(wù)器擁有固定數(shù)量的虛擬機(jī)實例數(shù)量，即|Cv m|為固定值，無法重新開啟新的虛擬機(jī)實例。

2.2 工作流模型

對于一個工作流，其任務(wù)之間擁有數(shù)據(jù)依賴性。每個任務(wù)可視為一個指令集，即一個可執(zhí)行單元。每個移動客戶端擁有一個工作流的執(zhí)行需求。現(xiàn)令總工作流數(shù)量為M，即表示移動客戶端的數(shù)量也為M。將每個工作流表示為Wk=Gk(Vk,Ek)，工作流集合定義為W。為了簡化表達(dá)，可將移動客戶端的所有工作流聯(lián)合為一個更大規(guī)模的工作流W進(jìn)行調(diào)度，定義為W=G(V,E)，任務(wù)和邊分別定義為ti∈V和ei,j∈E。偽任務(wù)STARTtpstart可作為合并工作流的入口任務(wù)(也稱開始任務(wù))，偽任務(wù)ENDtpend可作為合并工作流的出口任務(wù)(也稱出口任務(wù))。同時，wpstart=wpend=0，即兩個偽任務(wù)的負(fù)載量均為0。通過生成合成工作流結(jié)構(gòu)，每個任務(wù)可根據(jù)其優(yōu)先級同步進(jìn)行調(diào)度。

工作流結(jié)構(gòu)中，令pred(ti)表示ti的前驅(qū)任務(wù)集合，succ(ti)表示ti的后繼任務(wù)集合。若pred(ti)=?，則稱ti為START任務(wù)；若succ(ti)=?，則稱ti為END任務(wù)。

如圖1描述了多個工作流如何合并為一個工作流W及每個工作流任務(wù)如何分配與調(diào)度的過程。圖中，3個工作流W1、W2和W3合并為W。W中，偽START任務(wù)和偽END任務(wù)被添加為新的START任務(wù)和END任務(wù)。不失一般性，偽START任務(wù)和偽END任務(wù)與其它任務(wù)的通信時間均為0。

圖1 工作流合并調(diào)度

2.3 代價模型

令任務(wù)ti的負(fù)載為wi。ti生成的數(shù)據(jù)量，即從ti發(fā)送至tj的數(shù)據(jù)量為di,j。對于偽START任務(wù)和偽END任務(wù)，wpstart=wpend=0，dpstart,i=dj,pend=0，且ti,tj∈V。任務(wù)ti在mk上的處理時間定義為

(1)

數(shù)據(jù)量di,j在mk與邊緣云服務(wù)器之間無線鏈路上的傳輸時間定義為

Tc(di,j,rk)=

(2)

式中：A(ti)表示ti的分配目標(biāo)，A(ti)∈Cv cpu表明ti在邊緣云的vCPU上執(zhí)行，rk表示邊緣云服務(wù)器與mk間的無線數(shù)據(jù)通信速率，根據(jù)香農(nóng)理論可定義為

(3)

式中：βk表示mk的通信帶寬，pk表示mk的發(fā)送功率和接收功率，gk表示mk與基站間的信道增益，ω表示背景噪聲功率，CNk表示mk利用的通信信道。顯然，若移動客戶端利用相同的信道，則rk會變小。

定義Eexec(ti,mk)為在mk上執(zhí)行ti的能耗，Ein(ei,j,mk)為邊緣云至mk間ei,j的傳輸能耗，Eout(ei,j,mk)為mk至邊緣云間ei,j的傳輸能耗，分別定義為

Eexec(ti,mk)=τkwi

(4)

式中：τk表示每個mk∈M在單位周期內(nèi)的能耗因子，假設(shè)對于mk∈M和ti∈V，wi∝Eexec(ti,mk)。發(fā)送和接收能耗分別表示為

Ein(ei,j,mk)=pkTc(di,j,rk),A(ti)∈Cv cpu

(5)

Eout(ei,j,mk)=pkTc(di,j,rk),A(tj)∈Cv cpu

(6)

2.4 調(diào)度時長

本節(jié)描述如何確定每個任務(wù)ti在調(diào)度目標(biāo)A(ti)上的開始執(zhí)行時間Ts(ti,A(ti))，進(jìn)而推導(dǎo)出任務(wù)調(diào)度時的整體調(diào)度時長。定義Tf(ti,A(ti))為ti的完成時間，則

Tf(ti,A(ti))=Ts(ti,A(ti))+Tp(ti,A(ti))

(7)

式中：A(ti)∈M∪Cv cpu。令fList表示空閑任務(wù)集，即其前驅(qū)任務(wù)已被調(diào)度的任務(wù)集。對于fList中的每個任務(wù)，可以推導(dǎo)出任務(wù)的數(shù)據(jù)就緒時間。數(shù)據(jù)就緒時間DRT為所有前驅(qū)任務(wù)中的最大數(shù)據(jù)到達(dá)時間，且DRT應(yīng)為每個任務(wù)的最早開始時間，實際開始時間要晚于DRT，原因在于：當(dāng)一個任務(wù)th?pred(tj)在tj之前調(diào)度，且A(th)=A(tj)時，任務(wù)tj無法開始執(zhí)行。任務(wù)tj在mk上的DRT推導(dǎo)為

(8)

式中：若A(tj)∈Cv cpu且A(ti)∈Cv cpu，或ti和tj均被分配至mk時，有Tc(di,j,rk)=0。然后，可以利用DRT推導(dǎo)任務(wù)在調(diào)度目標(biāo)上的開始執(zhí)行時間Ts(tj,A(tj))為

Ts(tj,A(tj))=

(9)

工作流的調(diào)度時長即為END任務(wù)的完成時間，定義為

Tf(tend,A(tend))=Ts(tend,A(tend))+Tp(tend,A(tend))

(10)

2.5 調(diào)度目標(biāo)函數(shù)

綜合以上模型，邊緣云中工作流調(diào)度與卸載決策的優(yōu)化目標(biāo)函數(shù)可定義為

minTf(tend,A(tend))

(11)

約束條件為

(12)

(13)

3 PCTSO算法設(shè)計

3.1 算法總體流程

如2.2節(jié)所述，來自所有移動客戶端的工作流可以合并為一個整體工作流結(jié)構(gòu)W=G(V,E)。式(12)表明，每個移動客戶端的任務(wù)調(diào)度能耗必須小于或等于初始執(zhí)行能耗。初始狀態(tài)下，每個移動客戶端mk擁有其自身的工作流任務(wù)Wk=Gk(Vk,Ek)。初始調(diào)度時長SLinit(Wk)和初始調(diào)度能耗Einit(mk)可以分別定義為

(14)

(15)

由目標(biāo)函數(shù)可知，PCTSO算法需要實現(xiàn)Tf(tend,A(tend))≤SLinit(Wk)，且對于每個mk∈M，Einit(mk)需要盡可能降低。

算法1給出了PCTSO算法的完整執(zhí)行流程。算法輸入為邊緣云服務(wù)器的vCPU集合、移動客戶端集合M以及合并工作流W。算法輸出為工作流中每個任務(wù)與vCPU集合和移動客戶端間的調(diào)度關(guān)系，其中包含著任務(wù)卸載決策和任務(wù)調(diào)度解。UEX表示未調(diào)度任務(wù)集合，fList表示空閑任務(wù)集合。步驟(1)對UEX和fList進(jìn)行初始化。步驟(2)～步驟(14)，算法執(zhí)行迭代步驟，輸出UEX≠?時的調(diào)度方案。步驟(3)選擇在fList中擁有最大優(yōu)先級level的目標(biāo)調(diào)度任務(wù)tpivot。然后，步驟(4)調(diào)用算法2的CTSO算法生成從任務(wù)tpivot開始的連續(xù)任務(wù)集合Sfree。對于Sfree中的每個任務(wù)，按序?qū)⑵浞峙渲羦CPU的空閑時槽中，以便盡可能早的執(zhí)行，即步驟(7)、步驟(8)。最后，算法通過追溯succ(t)對UEX和fList進(jìn)行更新，且t∈Sfree，即步驟(9)、步驟(10)，或Sfree=?時如步驟(12)～步驟(14)執(zhí)行。當(dāng)追溯完所有任務(wù)后，即UEX=?時，算法完成調(diào)度過程，返回調(diào)度解。

算法1：PCTSO算法執(zhí)行過程

輸入：vCPU集合Cv cpu，移動客戶端集合M，合并工作流W

輸出：ti∈V至Cv cpu∪M間的映射調(diào)度方案

/*UEX為未調(diào)度任務(wù)集，fList為空閑任務(wù)集*/

(1)UEX←V,fList←START tasks

(2)whileUEX≠?do

(3)tpivot←the task satisfying Equ.(18)fromfList

(4)Sfree←CTSO(tpivot)

(5)ifSfree≠?then

(6)whileSfree≠?do

(7)t←head ofSfreeand removetfromSfree

(8) assigntto the idle time slot of a vCPU via the insertion-based technique

(9) removetfromUEXandfList

(10) updatefListby tracingsucc(t)

(11)else

(12) assigntpivotto the idel time slot ofmk

(13) removetpivotfromUEX

(14) updatefListby tracingsucc(tpivot)

(15)return映射調(diào)度解

圖2為PCTSO算法的執(zhí)行流程。接下來需要進(jìn)一步解決的問題是：

圖2 PCTSO算法執(zhí)行流程

(1)如何從fList中選擇待調(diào)度目標(biāo)任務(wù)，即如何決定任務(wù)優(yōu)先級；

(2)如何決定需要卸載至邊緣云上或移動客戶端執(zhí)行的任務(wù)集合。

3.2 基于優(yōu)先級的任務(wù)選擇機(jī)制

任務(wù)選擇即從空閑任務(wù)列表fList中選擇調(diào)度任務(wù)。定義在mk上任務(wù)ti至END任務(wù)的剩余時長為

(16)

假設(shè)ti在mk上執(zhí)行，則ti的開始時間可通過式(9)推導(dǎo)得到。則任務(wù)選擇的優(yōu)先級level(ti)可定義為

level(ti)=Ts(ti,A(ti))+Tp(ti,mk)+rlevel(ti)

(17)

式中：Ts(ti,A(ti))表示ti在mk上執(zhí)行時的開始時間，level(ti)表示如果ti之后的每個任務(wù)分配至邊緣云，調(diào)度時長的占優(yōu)路徑。算法試圖通過最小化處于占優(yōu)路徑上的任務(wù)的開始時間實現(xiàn)調(diào)度時長的最小化。對于屬于fList內(nèi)的每個任務(wù)，滿足以下條件的任務(wù)將被選擇為目標(biāo)調(diào)度任務(wù)

(18)

3.3 基于連續(xù)任務(wù)選擇的卸載機(jī)制

由于無法確?？梢酝ㄟ^將任務(wù)分配至邊緣云vCPU使其得到比在移動客戶端mk上更小的調(diào)度時長和能耗，因此，如果通過將任務(wù)插入至vCPU的空閑時槽中可以得到更小的調(diào)度時長和能耗，即可以接受任務(wù)卸載至該vCPU執(zhí)行。以下對如何實現(xiàn)降低調(diào)度時長作出描述。首先，假設(shè)選擇的調(diào)度任務(wù)為ti∈fList，且假設(shè)ti從mk卸載至vCPUcp,q。那么，卸載任務(wù)ti的時間差值計算為

ΔTp(ti)=Tp(ti,cp,q)-Tp(ti,mk)

(19)

ΔTs(ti)=Ts(ti,cp,q)-Ts(ti,mk)

(20)

同時，Tc(di,j,rk)為最新生成，tj∈succ(ti)，tj調(diào)度于mk上。因此，通過卸載ti降低調(diào)度時長的一個條件是

ΔSL(ti)=Tc(di,j,rk)+ΔTp(ti)+ΔTs(ti,A(ti))≤0

(21)

式中：ΔSL(ti)表示ti之后調(diào)度的所有任務(wù)，在沒有數(shù)據(jù)等待時間的情況下，調(diào)度時長的增加值。盡管如果卸載ti，可得ΔSL(ti)>0，但仍然存在一種可能：即卸載ti和tj，ΔSL(ti∪tj)≤0，tj∈succ(ti)，Tc(di,j,rk)遠(yuǎn)大于Tp(tj,A(tj))，由于Tc(di,j,rk)是邊緣云虛擬機(jī)本地計算值。由此可見，卸載相互關(guān)聯(lián)的多個任務(wù)可能導(dǎo)致在移動客戶端的調(diào)度時長和能耗的同步降低。假設(shè)ti為從fList中選擇的卸載侯選任務(wù)，且假設(shè)ti+1∈succ(ti)，ti+2∈succ(ti+1),…,ti+r∈succ(ti+r-1)。對于ti+j∈succ(ti+j-1)，假設(shè)除了任務(wù)ti+j-1，在pred(ti+j)內(nèi)的任務(wù)已經(jīng)被調(diào)度。定義該類任務(wù)為Sfree的輸入，即滿足以下條件的任務(wù)均被放入Sfree內(nèi)

(22)

式中：假設(shè)ts調(diào)度于mk上。圖3展示了Sfree的生成示例，假設(shè)ti為從fList內(nèi)選擇的任務(wù)。示例假設(shè)對于Sfree={ti}，ΔSL(Sfree)>0，即如圖3(b)所示。而如果更多任務(wù)添加至Sfree，則ΔSL(Sfree)<0，如圖3(c)和圖3(d)所示。從圖3(b)～圖3(d)可以觀察到，對于ΔSL(Sfree)>0的主要影響因素是Cv cpu中vCPU與移動客戶端mk間的通信時間，該通信時間僅發(fā)生在Sfree內(nèi)的最后一個任務(wù)的數(shù)據(jù)通信輸出上。如果該通信時間小于Sfree內(nèi)的任務(wù)執(zhí)行時間之和ΔTp(Sfree)，則有ΔSL(Sfree)<0。因此，盡管有ΔSL(ti)>0，ΔSL(Sfree)<0依然有可能成立，這取決于新生成的通信時間與Sfree內(nèi)處理時間之和之間的關(guān)系。

圖3 連續(xù)任務(wù)選擇卸載示例

能耗約束方面，對于屬于Vk的所有任務(wù)，必須滿足以下條件才能進(jìn)行所選任務(wù)的調(diào)度

(23)

如果滿足式(22)和式(23)，在Sfree內(nèi)的每個任務(wù)可被選擇為卸載調(diào)度任務(wù)，并被插入至vCPU的空閑時槽中，實現(xiàn)最小化的Tf(tk,cp)，tk∈Sfree。

推導(dǎo)Sfree的詳細(xì)過程如算法2所示，將其命名為連續(xù)任務(wù)選擇卸載決策算法CTSO。算法輸入空閑任務(wù)集合fList中擁有最大優(yōu)先級的任務(wù)，輸出連續(xù)選擇卸載任務(wù)集合。步驟(1)～步驟(3)對相關(guān)參數(shù)進(jìn)行初始化操作，其中，tmin表示對于ΔSL(Sfree)的最佳任務(wù)。步驟(4)～步驟(16)，算法通過追溯Sfree內(nèi)tpred的后繼任務(wù)以構(gòu)造Sfree。步驟(8)中，如果ΔSL(Sfree)得到最小值，且ΔSL(Sfree)≤0，則可以將任務(wù)t添加為tmin以更新Sfree。否則，Sfree不發(fā)生變化，即步驟(13)～步驟(15)。步驟(4)～步驟(16)中，假設(shè)Sfree擁有兩條以上記錄，步驟(17)中，算法檢測Sfree={ti} 的情形。然后，算法返回Sfree。接受卸載ti的條件是ΔSL≤0，即：每個任務(wù)添加至Sfree時，算法尋找Sfree，使得ΔSL(Sfree)最小化，且ΔSL(Sfree)≤0。由于在每個任務(wù)添加至Sfree時，ΔTs(ti,A(ti))不發(fā)生變化，僅能觀察到Tc(di+r,s,rk)和∑ti∈SfreeΔTp(ti)的變化行為。

算法2：CTSO算法執(zhí)行過程

輸入：集合fList中擁有最大level的任務(wù)ti

輸出：Sfree：連續(xù)選擇任務(wù)集

(1)Sfree←{ti}

(2)tpred←ti,tmin←?

(3)ΔSLpre←ΔSL(Sfree)

(4)whileS←chkFreeCandidate(tpred)≠?do

(5)tmin←null

(6)whilet∈Sdo

(7)Sfree←Sfree∪{t}

(8)ifΔSL(Sfree)≤ΔSLpre∧ΔSL(Sfree)≤0then

(9)if(23)is satisfied withA(t)∈Cv cpu,t∈Sfreethen

(10) ΔSLpre←ΔSL(Sfree)

(11)tmin←t

(12)else

(13)Sfree←Sfree-{t}

(14)else

(15)Sfree←Sfree-{t}

(16)tpred←tmin

//若沒有任務(wù)添加至Sfree，則需要檢測Sfree={ti}的情形

(17)ifSfree={ti}then

(18)ifΔSL(Sfree)>0∨(23)條件不滿足then

(19)Sfree←?

(20)returnSfree

//函數(shù)chkFreeCandidate()定義，用于判斷當(dāng)前任務(wù)是否是侯選空閑任務(wù)，可放入Sfree中。

(21)FunctionchkFreeCandidate(tcan)

(22)Sout←?,FindFly←true

(23)whiletsuc∈succ(tcan)do

(24)whilet∈pred(tsuc)do

(25)ift=tcanthen

(26)continue

(27)else

(28)ift∈UEXthen

(29)FindFlg←false

(30)break

(31)ifFindFlg=truethen

(32)Sout←Sout∪{tsuc}

(33)FindFlg←true

(34)returnSout

4 仿真分析

4.1 實驗配置

通過工作流仿真平臺WorkflowSim[22]與云計算環(huán)境仿真平臺CloudSim的有效融合進(jìn)行邊緣云中工作流的卸載與調(diào)度仿真，軟件開發(fā)環(huán)境為JDK1.7.0.51，硬件開發(fā)環(huán)境為Inter(R)Core i-7-5600U 2.6 GHz型號CPU，內(nèi)存為8 GB。為了實現(xiàn)對于PCTSO算法的實驗仿真，仿真平臺WorkflowSim在CloudSim的基礎(chǔ)上進(jìn)行層次拓展，提供工作流層次的仿真。在平臺中，以有向無環(huán)圖定義工作流模型，以頂點定義任務(wù)。由于工作流任務(wù)數(shù)巨大，平臺還引入task clustering技術(shù)將任務(wù)進(jìn)行集群。PCTSO算法具體通過擴(kuò)展WorkflowPlanner類實現(xiàn)，在getPlanningAlgorithm()方法中進(jìn)行添加。表2給出了相關(guān)仿真參數(shù)配置，其中，參數(shù)CCR表示工作流中計算密集型任務(wù)與通信密集型任務(wù)間的比例。實驗利用隨機(jī)生成的工作流結(jié)構(gòu)和Montage科學(xué)工作流結(jié)構(gòu)進(jìn)行測試，具體應(yīng)用可以模擬創(chuàng)建移動手機(jī)端的圖像處理任務(wù)量。

表2 仿真參數(shù)配置

除了能耗因素外，引入調(diào)度時長比率SLR進(jìn)行性能比較分析，定義為

(24)

式中：CPw表示根據(jù)總執(zhí)行時間得到的工作流W的關(guān)鍵路徑，SL表示工作流W的調(diào)度時長。假設(shè)每個vCPU擁有相同處理頻率，則ci,j在不同vCPU之間取值也相同。

選擇以下幾個算法進(jìn)行性能對比：第一種算法為本文算法的低級版本non-PCTSO。該算法與PCTSO的區(qū)別在于：以單個任務(wù)為單位判斷卸載時是否能在調(diào)度時長和調(diào)度能耗上得到優(yōu)化，而沒有考慮其后繼任務(wù)的卸載決策問題，與本文的連續(xù)任務(wù)選擇卸載機(jī)制完全不同。第二種算法為能效感知卸載算法EAOA[15]，算法同步考慮了時間和能耗的約束，并建立了工作流調(diào)度跨度和執(zhí)行能耗的多目標(biāo)優(yōu)化模型，與本文不同的是沒有考慮多工作流的卸載決策以及沒有考慮連續(xù)多任務(wù)的卸載問題。第三種算法為負(fù)載均衡的工作流卸載算法LBOA[16]，該算法更多考慮的是將移動終端的負(fù)載均勻地分布于邊緣云端和移動客戶端，沒有過多考慮調(diào)度效率和執(zhí)行能耗問題。

4.2 單工作流測試場景

實驗首先進(jìn)行單工作流調(diào)度場景的性能測試，實驗中獲取了在變化的CCR和任務(wù)量的情況下20次實驗得到的調(diào)度時長和調(diào)度能耗的均值情況。圖4是兩種工作流結(jié)構(gòu)得到SLR指標(biāo)情況。從圖4(a)、圖4(b)的結(jié)果看出，對于單工作流的調(diào)度場景而言，當(dāng)增大CCR的取值時，算法的調(diào)度時長是遞增的，這是由于CCR增大即表明工作流結(jié)構(gòu)中的計算密集型任務(wù)的數(shù)量比例的增加，這勢必會相應(yīng)增加任務(wù)的執(zhí)行時間，SLR指標(biāo)也相應(yīng)增加。本文提出的PCTSO算法在所有CCR取值下均得到了最小的調(diào)度時長。當(dāng)CCR=7.0和10時，PCTSO與non-PCTSO間的SLR差距變得更大，這是由于在non-PCTSO算法中僅有擁有更小數(shù)據(jù)輸出的任務(wù)可被卸載，導(dǎo)致任務(wù)卸載量較小，大部分任務(wù)集中于移動客戶端上執(zhí)行，任務(wù)執(zhí)行效率會遠(yuǎn)低于邊緣云端的任務(wù)執(zhí)行效率。而在PCTSO算法中，更多任務(wù)卸載至邊緣云執(zhí)行，能耗也得到了有效降低。LBOA算法在相對較低的CCR取值時調(diào)度時長接近甚至低于EAOA算法，此時工作流結(jié)構(gòu)中的任務(wù)類型并沒有太大差別，計算密集型和通信密集型任務(wù)數(shù)量差距不大。但隨著CCR的增加，LBOA也顯示出一定優(yōu)勢，說明在單工作流場景下負(fù)載均衡的任務(wù)調(diào)度方式可以更好有效利用本地資源和邊緣云端資源。單隨機(jī)工作流和單Montage科學(xué)工作流的測試中算法的演變趨勢不變，但由于Montage工作流多以I/O密集型任務(wù)為主，性能表現(xiàn)還是略有差異。表3給出了單工作流場景下的不同算法的能耗節(jié)省比例，表中的取值是對比所有任務(wù)在移動客戶端執(zhí)行時得到的執(zhí)行能耗的節(jié)省比例。PCTSO的原始意圖是可以確保其能耗大幅小于移動客戶端的執(zhí)行能耗，并不能達(dá)到最小化能耗。然而，由于算法中的卸載任務(wù)數(shù)量大于non-PCTSO，故在所有的CCR取值下，其能耗性能明顯優(yōu)于non-PCTSO算法以及另外兩種對比算法。EAOA和LBOA兩種算法的能耗節(jié)省比例始終比較相近，LBOA在多數(shù)的CCR取值下比EAOA節(jié)省更多的能耗，反應(yīng)出負(fù)載均衡的思路可以有效降低總體能耗，利益于較少的任務(wù)卸載的同時，傳輸能耗也更少。EAOA雖然是多目標(biāo)的優(yōu)化模型，但是沒有考慮工作流的任務(wù)結(jié)構(gòu)，始終以單個任務(wù)為目標(biāo)進(jìn)行卸載決策，決策結(jié)果相比本文算法不是最優(yōu)的。綜合整體結(jié)果來看，連續(xù)分配信賴型任務(wù)可以導(dǎo)致更好的能效。

圖4 單工作流執(zhí)行情形

表3 單工作流場景下的能耗節(jié)省比例/%

4.3 多工作流測試場景

多工作流情形中的調(diào)度時長為所有工作流中的最大時長，本實驗測試了不同規(guī)模的多工作流執(zhí)行場景，并取結(jié)果的均值。從圖5(a)、圖5(b)可以看到，在所有工作流規(guī)模下，PCTSO算法均擁有最佳的SLR表現(xiàn)，其調(diào)度時長平均低于3種對比算法約30%左右，這與單工作流執(zhí)行場景類似，說明了PCTSO算法的連續(xù)任務(wù)選擇的卸載機(jī)制在降低整體工作流調(diào)度時長方面是有效可行的。總體來說，調(diào)度工作流數(shù)量的增加會使得調(diào)度時長(所有工作流中的最大時長)有所增加。在多隨機(jī)工作流結(jié)構(gòu)中，3種對比算法的SLR表現(xiàn)起伏較大，說明對于任務(wù)的卸載決策并不能生成在調(diào)度效率上比較穩(wěn)定的結(jié)果。本文的PCTSO算法始終以工作流任務(wù)的層次結(jié)構(gòu)為基礎(chǔ)，首先基于任先級選擇待調(diào)度任務(wù)，然后以該任務(wù)為基礎(chǔ)，考慮與之關(guān)聯(lián)的連續(xù)任務(wù)集的卸載決策，而不是以單個任務(wù)為基礎(chǔ)做卸載決策，有效提升任務(wù)執(zhí)行的并行度及調(diào)度效率。表4給出多工作流場景下的能耗節(jié)省比例情況。顯然，PCTSO算法的能效也是最高的，non-PCTSO的能耗節(jié)省值低于另外兩種對比算法，這也印證了連續(xù)任務(wù)選擇的卸載機(jī)制是可以有效降低調(diào)度時長和調(diào)度能耗的。EAOA與LBOA兩種的能耗節(jié)省比例與單工作流調(diào)度場景結(jié)果相似，LBOA算法略優(yōu)。在考慮傳輸能耗和傳輸延時的情況下，結(jié)合工作流任務(wù)結(jié)構(gòu)特征做出卸載決策顯然比單個任務(wù)的卸載決策具有更高的效率。

表4 多工作流場景下的能耗節(jié)省比例/%

圖5 多工作流執(zhí)行情形

5 結(jié)束語

本文以優(yōu)化執(zhí)行時長和降低移動端能耗為目標(biāo)，提出一種基于邊緣云環(huán)境的工作流調(diào)度與卸載決策算法。算法首先依據(jù)工作流內(nèi)任務(wù)間的結(jié)構(gòu)層次特點，設(shè)計了基于優(yōu)先級的待調(diào)度選擇機(jī)制；然后設(shè)計了基于連續(xù)任務(wù)選擇的卸載機(jī)制，驗證了連續(xù)依賴型任務(wù)的整體卸載可以更有效利用邊緣云端服務(wù)器資源，提升任務(wù)執(zhí)行并行度。利用不同規(guī)模的隨機(jī)工作流結(jié)構(gòu)和Montage科學(xué)工作流進(jìn)行了仿真測試。結(jié)果表明：①該算法在滿足能量約束的同時，基于連續(xù)任務(wù)選擇的卸載機(jī)制的調(diào)度效率可以平均提高約25%；②在相同工作流調(diào)度規(guī)模下，算法的執(zhí)行能耗可以降低約15%。實驗結(jié)果表明該算法是有效可行的。進(jìn)一步的工作可以在考慮通信鏈路可靠性的基礎(chǔ)上，設(shè)計相應(yīng)的任務(wù)卸載決策算法，從而實現(xiàn)更加安全可靠的工作流任務(wù)卸載與調(diào)度策略。