基于邊緣云環境的工作流調度與卸載決策算法

金 儉，鄭 倩

(1.黃河科技學院 現代教育技術中心，河南 鄭州 450063；2.鄭州輕工業大學 軟件學院，河南 鄭州 450002)

0 引 言

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

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

1 相關研究

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

2 基本模型

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

表1 符號說明

2.1 系統模型

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

2.2 工作流模型

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

工作流結構中，令pred(ti)表示ti的前驅任務集合，succ(ti)表示ti的后繼任務集合。若pred(ti)=?，則稱ti為START任務；若succ(ti)=?，則稱ti為END任務。

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

圖1 工作流合并調度

2.3 代價模型

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

(1)

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

Tc(di,j,rk)=

(2)

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

(3)

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

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

Eexec(ti,mk)=τkwi

(4)

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

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 調度時長

本節描述如何確定每個任務ti在調度目標A(ti)上的開始執行時間Ts(ti,A(ti))，進而推導出任務調度時的整體調度時長。定義Tf(ti,A(ti))為ti的完成時間，則

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

(7)

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

(8)

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

Ts(tj,A(tj))=

(9)

工作流的調度時長即為END任務的完成時間，定義為

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

(10)

2.5 調度目標函數

綜合以上模型，邊緣云中工作流調度與卸載決策的優化目標函數可定義為

minTf(tend,A(tend))

(11)

約束條件為

(12)

(13)

3 PCTSO算法設計

3.1 算法總體流程

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

(14)

(15)

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

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

算法1：PCTSO算法執行過程

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

輸出：ti∈V至Cv cpu∪M間的映射調度方案

/*UEX為未調度任務集，fList為空閑任務集*/

(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映射調度解

圖2為PCTSO算法的執行流程。接下來需要進一步解決的問題是：

圖2 PCTSO算法執行流程

(1)如何從fList中選擇待調度目標任務，即如何決定任務優先級；

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

3.2 基于優先級的任務選擇機制

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

(16)

假設ti在mk上執行，則ti的開始時間可通過式(9)推導得到。則任務選擇的優先級level(ti)可定義為

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

(17)

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

(18)

3.3 基于連續任務選擇的卸載機制

由于無法確保可以通過將任務分配至邊緣云vCPU使其得到比在移動客戶端mk上更小的調度時長和能耗，因此，如果通過將任務插入至vCPU的空閑時槽中可以得到更小的調度時長和能耗，即可以接受任務卸載至該vCPU執行。以下對如何實現降低調度時長作出描述。首先，假設選擇的調度任務為ti∈fList，且假設ti從mk卸載至vCPUcp,q。那么，卸載任務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調度于mk上。因此，通過卸載ti降低調度時長的一個條件是

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

(21)

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

(22)

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

圖3 連續任務選擇卸載示例

能耗約束方面，對于屬于Vk的所有任務，必須滿足以下條件才能進行所選任務的調度

(23)

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

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

算法2：CTSO算法執行過程

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

輸出：Sfree：連續選擇任務集

(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

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

(17)ifSfree={ti}then

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

(19)Sfree←?

(20)returnSfree

//函數chkFreeCandidate()定義，用于判斷當前任務是否是侯選空閑任務，可放入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]與云計算環境仿真平臺CloudSim的有效融合進行邊緣云中工作流的卸載與調度仿真，軟件開發環境為JDK1.7.0.51，硬件開發環境為Inter(R)Core i-7-5600U 2.6 GHz型號CPU，內存為8 GB。為了實現對于PCTSO算法的實驗仿真，仿真平臺WorkflowSim在CloudSim的基礎上進行層次拓展，提供工作流層次的仿真。在平臺中，以有向無環圖定義工作流模型，以頂點定義任務。由于工作流任務數巨大，平臺還引入task clustering技術將任務進行集群。PCTSO算法具體通過擴展WorkflowPlanner類實現，在getPlanningAlgorithm()方法中進行添加。表2給出了相關仿真參數配置，其中，參數CCR表示工作流中計算密集型任務與通信密集型任務間的比例。實驗利用隨機生成的工作流結構和Montage科學工作流結構進行測試，具體應用可以模擬創建移動手機端的圖像處理任務量。

表2 仿真參數配置

除了能耗因素外，引入調度時長比率SLR進行性能比較分析，定義為

(24)

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

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

4.2 單工作流測試場景

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

圖4 單工作流執行情形

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

4.3 多工作流測試場景

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

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

圖5 多工作流執行情形

5 結束語

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