金 儉，鄭 倩

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

0 引 言

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

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

1 相關(guān)研究

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

2 基本模型

表1首先給出主要的符號(hào)定義說(shuō)明。

表1 符號(hào)說(shuō)明

2.1 系統(tǒng)模型

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

2.2 工作流模型

對(duì)于一個(gè)工作流，其任務(wù)之間擁有數(shù)據(jù)依賴性。每個(gè)任務(wù)可視為一個(gè)指令集，即一個(gè)可執(zhí)行單元。每個(gè)移動(dòng)客戶端擁有一個(gè)工作流的執(zhí)行需求。現(xiàn)令總工作流數(shù)量為M，即表示移動(dòng)客戶端的數(shù)量也為M。將每個(gè)工作流表示為Wk=Gk(Vk,Ek)，工作流集合定義為W。為了簡(jiǎn)化表達(dá)，可將移動(dòng)客戶端的所有工作流聯(lián)合為一個(gè)更大規(guī)模的工作流W進(jìn)行調(diào)度，定義為W=G(V,E)，任務(wù)和邊分別定義為ti∈V和ei,j∈E。偽任務(wù)STARTtpstart可作為合并工作流的入口任務(wù)(也稱開(kāi)始任務(wù))，偽任務(wù)ENDtpend可作為合并工作流的出口任務(wù)(也稱出口任務(wù))。同時(shí)，wpstart=wpend=0，即兩個(gè)偽任務(wù)的負(fù)載量均為0。通過(guò)生成合成工作流結(jié)構(gòu)，每個(gè)任務(wù)可根據(jù)其優(yōu)先級(jí)同步進(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描述了多個(gè)工作流如何合并為一個(gè)工作流W及每個(gè)工作流任務(wù)如何分配與調(diào)度的過(guò)程。圖中，3個(gè)工作流W1、W2和W3合并為W。W中，偽START任務(wù)和偽END任務(wù)被添加為新的START任務(wù)和END任務(wù)。不失一般性，偽START任務(wù)和偽END任務(wù)與其它任務(wù)的通信時(shí)間均為0。

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

2.3 代價(jià)模型

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

(1)

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

Tc(di,j,rk)=

(2)

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

(3)

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

定義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表示每個(gè)mk∈M在單位周期內(nèi)的能耗因子，假設(shè)對(duì)于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)度時(shí)長(zhǎng)

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

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ù)集。對(duì)于fList中的每個(gè)任務(wù)，可以推導(dǎo)出任務(wù)的數(shù)據(jù)就緒時(shí)間。數(shù)據(jù)就緒時(shí)間DRT為所有前驅(qū)任務(wù)中的最大數(shù)據(jù)到達(dá)時(shí)間，且DRT應(yīng)為每個(gè)任務(wù)的最早開(kāi)始時(shí)間，實(shí)際開(kāi)始時(shí)間要晚于DRT，原因在于：當(dāng)一個(gè)任務(wù)th?pred(tj)在tj之前調(diào)度，且A(th)=A(tj)時(shí)，任務(wù)tj無(wú)法開(kāi)始執(zhí)行。任務(wù)tj在mk上的DRT推導(dǎo)為

(8)

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

Ts(tj,A(tj))=

(9)

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

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è)計(jì)

3.1 算法總體流程

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

(14)

(15)

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

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

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

輸入：vCPU集合Cv cpu，移動(dòng)客戶端集合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í)行流程。接下來(lái)需要進(jìn)一步解決的問(wèn)題是：

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

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

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

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

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

(16)

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

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

(17)

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

(18)

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

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

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

(19)

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

(20)

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

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

(21)

式中：ΔSL(ti)表示ti之后調(diào)度的所有任務(wù)，在沒(méi)有數(shù)據(jù)等待時(shí)間的情況下，調(diào)度時(shí)長(zhǎng)的增加值。盡管如果卸載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ī)本地計(jì)算值。由此可見(jiàn)，卸載相互關(guān)聯(lián)的多個(gè)任務(wù)可能導(dǎo)致在移動(dòng)客戶端的調(diào)度時(shí)長(zhǎng)和能耗的同步降低。假設(shè)ti為從fList中選擇的卸載侯選任務(wù)，且假設(shè)ti+1∈succ(ti)，ti+2∈succ(ti+1),…,ti+r∈succ(ti+r-1)。對(duì)于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è)對(duì)于Sfree={ti}，ΔSL(Sfree)>0，即如圖3(b)所示。而如果更多任務(wù)添加至Sfree，則ΔSL(Sfree)<0，如圖3(c)和圖3(d)所示。從圖3(b)～圖3(d)可以觀察到，對(duì)于ΔSL(Sfree)>0的主要影響因素是Cv cpu中vCPU與移動(dòng)客戶端mk間的通信時(shí)間，該通信時(shí)間僅發(fā)生在Sfree內(nèi)的最后一個(gè)任務(wù)的數(shù)據(jù)通信輸出上。如果該通信時(shí)間小于Sfree內(nèi)的任務(wù)執(zhí)行時(shí)間之和ΔTp(Sfree)，則有ΔSL(Sfree)<0。因此，盡管有ΔSL(ti)>0，ΔSL(Sfree)<0依然有可能成立，這取決于新生成的通信時(shí)間與Sfree內(nèi)處理時(shí)間之和之間的關(guān)系。

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

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

(23)

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

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

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

輸入：集合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

//若沒(méi)有任務(wù)添加至Sfree，則需要檢測(cè)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 實(shí)驗(yàn)配置

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

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

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

(24)

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

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

4.2 單工作流測(cè)試場(chǎng)景

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

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

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

4.3 多工作流測(cè)試場(chǎng)景

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

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

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

5 結(jié)束語(yǔ)

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