云邊協同環境下基于局部關鍵路徑的工作流應用調度策略

林潮偉,林 兵,陳 星

1(福州大學 計算機與大數據學院,福州 350108)

2(福建省網絡計算與智能信息處理重點實驗室,福州 350108)

3(福建師范大學 物理與能源學院,福州 350117)

0 引 言

工作流應用結構復雜,通常包含數十個計算任務,這些任務之間具有數據或控制流依賴關系.典型的工作流應用[1]包括基于深度神經網絡(Deep Neural Network,DNN)的應用、物聯網(Internet of Things,IoT)應用等.這些應用計算復雜度高,對數據傳輸時延敏感,一般需要高性能的計算平臺來執行完成.云計算提供強大的計算性能,但由于IoT設備和云端間的數據傳輸時延嚴重,導致IoT設備的時延敏感工作流應用無法直接調度至云端執行.移動邊緣計算[2,3](Mobile Edge Computing,MEC)作為一種不斷發展的計算范式,能夠提供一種更有效的方法,即在更接近數據創建點的位置處理數據,使得延遲敏感的工作流應用可以得到及時處理.考慮到云端虛擬機的強大存儲、計算能力和邊緣服務器的更靠近用戶端的優勢,云邊協同計算模式作為一種融合云計算與邊緣計算差異化優勢的新型計算范式[4,5],將數據密集型任務調度至邊緣,計算密集型任務調度至云端,云計算與邊緣計算有機結合,為移動用戶設備的各種請求提供不同的按需服務.然而,由于云邊協同環境的資源異構性高,各個計算節點的計算能力、帶寬、存儲等均存在差異,同時每個工作流應用中任務之間存在復雜的數據依賴關系,如何在云邊協同環境下合理高效地調度多工作流應用仍然存在重大挑戰.

近年來,許多研究工作針對云計算或邊緣計算環境下的工作流應用調度展開[6-8].工作流應用調度是一個NP難問題[9],通常考慮在單一平臺(云計算或邊緣計算)環境下,將工作流應用的依賴任務分別調度到不同的計算節點,滿足工作流應用的服務質量(Quality of Service,QoS)要求.云邊協同環境下的工作流應用調度,不僅需要滿足工作流應用的高計算復雜度需求,而且能夠有效降低數據傳輸時延[5].現有研究工作大多僅考慮單一工作流應用的調度問題,而忽略了多個工作流應用的調度,且在滿足工作流應用截止時間約束前提下的調度代價優化方面仍有較大的可挖掘空間.如何在滿足多個不同工作流應用時延約束前提下,考慮不同工作流應用的差異化生成時間,有效調度工作流應用的依賴任務至合適的云邊計算節點上,降低多工作流應用的總體執行代價,仍是一項極具挑戰的研究.

目前關于工作流應用調度的研究主要集中在確定性環境下,即計算節點的計算性能、傳輸帶寬等計算環境因素相對穩定,不存在波動.然而,在云邊協同環境中,由于不同服務器之間的負載不同、帶寬波動、網絡擁塞等原因和計算機自身特性,工作流任務的執行時間往往不能準確地預測[10],并且即使是相同的數據在固定的服務器之間傳輸時,其傳輸時間也會時常變化.因此,在實際的調度過程中,服務器的性能和服務器之間的帶寬通常是波動的.調度環境的波動會對工作流應用調度產生不確定的影響,這是不可忽視的,在建立工作流調度模型時,需要考慮到這種不確定性.目前的不確定性環境下的調度研究主要針對模糊作業車間調度[11]和實時嵌入式系統的任務調度[12]等,較少關注模糊云邊協同環境下工作流應用調度的研究.

在前期工作中,云邊協同環境中基于DNN的應用程序的代價驅動卸載[13],以及基于DNN的智能物聯網系統的節能卸載[14]得到解決,在工作流應用調度方面已積累相關經驗,并在云邊協同卸載方面也有一定工作基礎.與本文工作相比,它們都處理某些云邊協同環境中的工作流調度,而不是模糊云邊協同環境.在本文研究中,進一步解決了降低任務計算和數據傳輸導致的多個工作流應用的執行代價,且滿足相應的截止時間約束,同時考慮調度策略對于實際調度中不同規模工作流應用的決策實時性.三角模糊數[15]被用于來表示模糊環境下服務器的計算性能和傳輸帶寬.特別地,提出一種基于局部關鍵路徑的多工作流應用調度策略(Workflow applications Scheduling strategy based on Partial Critical Path,WSPCP),該策略基于工作流應用的數據依賴結構,采用預處理方法合并有向割邊;同時在調度過程中,將局部關鍵路徑的所有任務作為調度單元進行統一調度,很大程度上避免了任務之間的數據傳輸,從而減少數據傳輸代價,從而實現在滿足每個工作流應用截止時間約束的前提下,盡可能地降低模糊執行代價.本文的主要貢獻包括以下3個部分:

1)考慮到實際調度過程中服務器的負載壓力、網絡擁塞等計算環境因素造成計算性能和傳輸帶寬的不穩定性,采用三角模糊數來表示模糊云邊協同環境中服務器的計算性能和傳輸帶寬.

2)針對泊松到達的多工作流應用,提出一種基于局部關鍵路徑的多工作流應用調度策略(WSPCP),基于工作流應用自身結構,提出合并有向割邊的預處理方法;同時,將局部關鍵路徑作為調度單元進行統一調度,充分避免任務之間的數據傳輸,從而滿足多工作流應用的時延約束,并降低其模糊執行代價.

3)通過仿真實驗驗證,與其他基準調度策略相比,在常用的工作流基準數據集上,WSPCP可以在滿足多個工作流應用的截止時間的前提下獲得更優的可行調度方案,有效降低了模糊執行代價.同時,對于不同規模的多工作流應用,WSPCP能夠在平均秒級時間內得到可行的調度方案,具有較好的決策實時性,能夠一定程度上應對實際調度中多個應用同時到達的極端情況.針對交通系統中的車輛識別應用,考慮工作流應用的任務規模、任務的計算復雜度、任務之間的數據傳輸量,進一步分析WSPCP對于實際應用的可行性.

本文的其余章節安排如下:第1節回顧相關工作,第2節給出多工作流應用調度模型的定義,并對模糊云邊協同環境下的多工作流應用調度進行形式化表示;第3節詳細描述本文所提出的WSPCP策略;第4節設計仿真實驗環境,通過對比實驗,分析WSPCP的性能效果,以及對于實際應用的可行性;最后,第5節概述本文的工作,并展望未來的研究方向.

1 相關工作

隨著移動邊緣計算的快速發展和云邊協同模式的廣泛應用,IoT設備對于在邊緣節點運行復雜應用程序的需求越來越大[16].這些復雜的應用程序可以表示為任務之間存在數據依賴關系的工作流應用.在本節中,將簡要回顧并分析云計算和邊緣計算中的工作流應用調度以及模糊不確定性環境中任務調度的研究.

近年來,云計算環境中的工作流應用調度已經展開了許多研究工作[17-19].Meng等人[8]提出一種基于粒子群優化算法的安全感知調度方法,用于跨異構云的實時資源分配.實驗結果表明,該策略能夠在調度和安全性能之間取得良好的平衡.Paknejad等人[19]提出一種增強的多目標協同進化算法,用于云環境中的工作流調度.實驗結果表明,該算法在代價、完工時間和能耗等性能指標上均優于同類算法.Qin等人[20]研究云工作流調度問題,在其執行時間保持在截止時間內的同時降低執行代價.基于云工作流調度問題的特定知識,提出一種新型的基于知識的自適應離散水波優化算法(Knowledge-based Adaptive Discrete Water Wave Optimization,KADWWO).實驗結果表明,KADWWO算法的性能優于最先進的算法.然而,上述研究工作往往忽略了IoT設備向云端提交工作流應用的數據傳輸,雖然云計算為調度工作流應用提供了強大的計算性能,但由于IoT設備與云端之間的大量數據傳輸,可能會增加核心網絡的流量負載并導致高延遲.

邊緣計算技術能夠有效降低工作流調度和計算卸載的系統時延,帶來更好的用戶體驗[5,21,22].近年來,云邊協同環境中任務調度和卸載問題已引起廣泛研究.Xie等人[22]提出一種新的定向非局部收斂粒子群優化算法(Directional and Non-local-Convergent PSO,DNCPSO),利用非線性慣性權重,通過定向搜索過程進行變異和選擇操作,同時降低云邊環境下工作流的執行成本和完成時間.仿真實驗表明,DNCPSO算法的性能優于其他經典算法和改進算法.Hazra等人[23]提出一種節能任務卸載策略(Energy-Efficient Task Offloading,EETO),通過聯合卸載和調度光纖陀螺網絡中的實時IoT應用,解決能源性能權衡問題.在不同QoS參數下的實驗結果表明,EETO策略比現有策略具有更好的性能.Zhao等人[24]提出一種邊緣環境下基于Q-learning算法的低負載分布式入侵檢測系統任務調度策略,該策略根據網絡變化動態調整調度策略,使得總體負載保持在較低水平,同時保持低負載和丟包率之間的平衡.實驗結果表明,與其他經典方法相比,該策略具有更好的低負載性能,惡意特征檢測率等指標沒有顯著降低.然而,現有的云邊協同環境下工作流應用調度的研究很少考慮在滿足截止時間約束的同時優化工作流應用任務計算和數據傳輸造成的執行代價.

在工作流應用的實際調度過程中,服務器的性能和它們之間的帶寬通常會發生波動,這可能會對調度結果產生相當大的影響.現有工作解決了模糊環境中的調度問題,但此類工作主要面向其他領域.Sun等人[11]考慮模糊柔性作業車間調度問題,將不確定的加工時間表示為三角模糊數,提出一種有效的混合協同進化算法來最小化模糊最大完工時間.通過五個基準測試和三個處理時間模糊的大規模問題的測試,結果表明該算法的性能優于現有方法,表現出較好的收斂能力.Muhuri等人[12]提出一種新的解決模糊不確定環境下實時嵌入式系統節能任務調度問題的方法,稱為“約束耦合節能遺傳算法”.實驗結果表明,該算法的性能優于現有的同類算法.Wu等人[25]針對具有不確定參數的物聯網應用提出一種模糊邏輯卸載策略,以優化魯棒性和一致性指數,其中三角模糊數與半梯形模糊數分別用于建模任務處理時間和數據傳輸時間.同時,設計一種多目標分布估計算法,用于各種應用中優化模糊卸載策略.實驗結果表明,該算法在魯棒性和一致性指標上均優于經典啟發式算法.盡管相關研究領域已經取得了顯著進展,但是在不確定性云邊協同環境中多工作流應用的模糊調度仍然是一個極具價值的研究方向.

受到上述工作的啟發,本文將提出一種啟發式調度策略,用于解決在模糊云邊協同環境中截止時間約束的多工作流應用的代價驅動調度.

2 系統模型

云邊協同環境下的多工作流應用調度框架如圖1所示,主要包括3個組成部分:帶截止時間約束的多工作流應用、云邊協同環境以及啟發式調度器.

圖1 云邊協同環境下的多工作流應用調度框架Fig.1 Framework model of workflow scheduling in edge-cloud environment

2.1 多工作流應用模型

用戶在不同時間通過IoT設備向云邊協同環境提交工作流應用,本文假設工作流應用的到達滿足一個強度為λ的泊松過程[26],因此工作流應用到達的時間間隔服從參數為λ的指數分布,其中,λ表示工作流的到達率.多工作流應用W由多個工作流應用{w1,w2,…,wn}組成,每個工作流應用wi可以表示為一個三元組wi=(αi,di,Gi),αi表示第i個工作流應用Wi到達的時間;di表示第i個工作流應用的截止時間,在某個調度方案中,若所有工作流應用都能在相應的截止時間前被執行完成,則稱該調度方案是可行的;Gi表示第i個工作流應用的數據依賴結構.

此外,工作流應用可能包含兩個及以上入任務或出任務,可以通過為其添加虛擬入任務vin或虛擬出任務vout,將其轉化為僅含有一個入任務和出任務的工作流,具體操作為:設置虛擬入任務vin或虛擬出任務vout的計算量為0,并將原有的入任務和出任務分別與vin和vout通過虛擬數據邊連接,同時將上述虛擬數據邊的權值設置為0,即其傳輸數據量為0.值得注意的是,增加虛擬任務和虛擬數據邊不會對多工作流應用調度的結果產生任何影響.

2.2 云邊協同環境

在多工作流應用調度過程中,云邊協同環境主要向用戶提供計算服務和帶寬服務,同時允許動態租賃.云邊協同環境S={Scloud,Sedge}由云和邊緣組成,具有不同的計算節點,即云的虛擬機和邊緣的服務器.為了簡化表述,統一使用“服務器”表示云和邊緣中的計算節點.云Scloud={s1,s2,…,su}包含的u個服務器,邊緣Sedge={su+1,su+2,…,su+v}包含v個服務器.服務器sk可以表示為:

(1)

根據服務器所屬平臺的類型,云邊協同環境中的服務器sr和st之間的帶寬βr,t可表示為:

(2)

2.3 多工作流應用調度方案

在云邊協同環境中,啟發式調度器的目標是給定一個調度方案,在每個工作流應用都滿足截止時間約束的條件下,使得多工作流應用的執行代價最低.其根據調度方案中工作流應用任務和服務器之間的映射關系,為工作流應用任務分配相應的服務器.

因此,多工作流應用的調度方案可以被定義如下:

Γ=(W,S,M,ce,Tf)

(3)

(4)

(5)

2.3.1 確定性云邊協同環境下的調度

在本次研究中,主要關注服務器的任務計算能力和服務器之間的數據傳輸能力,并假定在執行過程中有足夠的容量存儲傳輸數據.因此,本文側重于考慮任務計算時間ttc和數據傳輸時間tdt,其計算方式具體如式(6)和式(7)所示:

(6)

(7)

(8)

(9)

(10)

(11)

其中,由于工作流調度過程中數據存儲、資源監控等代價與上述代價相比可以忽略不計,從而只考慮任務計算代價和數據傳輸代價.

對于多工作流應用的一個調度方案,其目標是在所有工作流應用的完成時間均滿足截止時間約束的同時,最小化其執行代價.因此,多工作流應用調度問題可形式化定義為:

(12)

2.3.2 不確定性云邊協同環境下的調度

(13)

圖2 三角模糊數的隸屬函數Fig.2 Membership function of triangular fuzzy number

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

基于上述形式化定義(12),模糊云邊協同環境下的多工作流應用調度方案的優化問題可形式化定義如式(22)所示:

(22)

(23)

(24)

(25)

(26)

綜上所述,基于上述形式化定義(22),模糊云邊協同環境下的多工作流應用調度問題可轉化為式(27)所示:

(27)

3 基于局部關鍵路徑的多工作流應用調度策略

本節首先介紹一些局部關鍵路徑相關的基本變量定義,然后給出基于局部關鍵路徑的多工作流應用調度策略(Workflow applications Scheduling strategy based on Partial Critical Path,WSPCP)的具體描述,用于在滿足每個工作流應用的截止時間約束的情況下,盡可能減少多工作流應用的執行代價.

3.1 基本定義

在本文中,將工作流應用中已經分配到某個服務器的任務稱為已調度任務,反之,則是未調度任務.在完成工作流應用wi的調度前,任務vi,j的最早完成時間(Earliest Finish Time,EFT)可定義如下:

(28)

根據任務vi,j的最早完成時間,定義vi,j的最早開始時間(Earliest Start Time,EST)如下:

(29)

另外,由于虛擬入任務的計算量為0,其在任何服務器上的執行時間均為0,因此虛擬入任務的最早完成時間和最早開始時間為工作流應用的到達時間,即:

EST(vin)=EFT(vin)=αi

(30)

在WSPCP中,為了確保工作流應用wi能夠在截止時間di之前完成,定義任務vi,j的最遲開始時間(Latest Start Time,LST)如式(31)所示,任務vi,j必須在LST(vi,j)前完成調度并開始執行.

(31)

根據任務vi,j的最遲開始時間,定義vi,j的最遲完成時間(Latest Finish Time,LFT)如下:

(32)

同樣地,由于虛擬出任務的計算量為0,其在任何服務器上的執行時間均為0,因此虛擬出任務的最早完成時間和最早開始時間為工作流應用的到達時間,即:

LST(vout)=LFT(vout)=di

(33)

在WSPCP中,局部關鍵路徑(Partial Critical Path,PCP)是其最核心的思想之一.在傳統的調度策略中,往往以工作流應用的單個任務作為調度單元進行調度;與之不同的是,WSPCP將同一局部關鍵路徑上的所有任務作為調度單元進行統一調度,從而有效壓縮依賴任務之間的數據傳輸量,減少數據傳輸代價.對于任務vi,j,其局部關鍵路徑定義如下:

(34)

其中,path(PCP(v),v)表示一條局部關鍵路徑,在任務v之前連接任務v的局部關鍵路徑PCP(v);CP(vi,j)表示vi,j的關鍵父任務(Critical Parent,CP),在任務vi,j的所有直接未調度父任務中,關鍵父任務到任務vi,j的數據最遲傳輸到達,具體定義如下:

(35)

根據上述定義可知,在PCP(vi,j)上的任何一個任務,數據傳輸到達其后繼任務的時間總是最遲的.

3.2 WSPCP

對于泊松到達的多工作流應用,WSPCP實時監測每個工作流應用wi的到達,進行工作流應用的任務調度,在滿足所有工作流應用的截止時間約束的前提下,盡可能減少執行代價.在調度過程中,WSPCP通過為局部關鍵路徑分配局部截止時間,即最遲完成時間,并對整個局部關鍵路徑進行統一調度,而不會對單一任務進行調度,這樣大大壓縮局部關鍵路徑上任務之間的數據傳輸量,減少數據執行代價,具體過程如算法1所示.

算法1.WSPCP

procedureWorkflow_Applications_Scheduling(W,S)

Input:W,S

1.Initialization:M←null;

2.whileany ofWhas not arriveddo

3. ifwiarrivesthen

4. //每次生成1個新的線程,用于處理新到達的wi

5. #pragmaompparallelnum_threads(1){

6. //調用算法2,對wi進行預處理

7. Workflow_Application_Preprocessing(wi);

9.forj=1toj=|Vi|do

10. 初始化任務vi,j為未調度任務;

11. 計算EFT(vi,j),EST(vi,j),LST(vi,j),LFT(vi,j)

12.endfor

13.tstart(vin)=tend(vin)=αi,tstart(vout)=tend(vout)=di;

14. 標記虛擬入任務vin和虛擬出任務vout為已調度任務;

15. //調用算法3,基于局部關鍵路徑思想,調度所有任務

16. Scheduling_All_Parents(M,vout);

17. }

18.else

19. //Waiting for a workflow application arriving;

20.continue;

21.endif

22.endwhile

endprocedure

該算法描述了WSPCP的整體過程,對于泊松到達的工作流應用wi,主要包括3個部分:1)調用算法2,對wi進行預處理,基于wi的結構特征,合并存在有向割邊的相鄰任務,從而減少算法的時間復雜度;2)計算WSPCP過程中需要用到的相關變量,并標記虛擬入任務vin和虛擬出任務vout為已調度任務;3)調用算法3,以虛擬出任務vout作為輸入,基于關鍵父任務迭代機制,尋找帶局部截止日期的局部關鍵路徑,并為局部關鍵路徑分配相應的最適合服務器,并執行所有任務.

3.2.1 工作流應用的預處理過程

由于多工作流應用調度的任務規模較大,通過合并有向割邊可以有效減少任務規模,從而降低算法執行時間.有向割邊的定義為:對于一條有向邊,其出節點的出度為1,且入節點的入度為1,則稱作有向割邊.如圖3所示的工作流應用中,一共存在7條有向割邊,其中相同圖案的任務和有向邊(虛線箭頭)組成的結構即為有向割邊.

圖3 工作流應用中的有向割邊Fig.3 Directed cut-edge in workflow application

在工作流應用的預處理過程中,算法2根據當前工作流應用wi的數據依賴結構特征,將存在有向割邊的相鄰任務進行合并,得到新任務的計算量為相鄰任務之和.對于存在大量有向割邊的工作流應用,如Epigenomics和LIGO[28]等,預處理過程能夠大幅度減少其任務規模,降低WSPCP的執行時間.

算法2.工作流應用預處理

procedureWorkflow_Application_Preprocessing(wi)

Input:wi

1.記錄wi每個任務的入度和出度

2.do{

4.if出節點vi,p的出度為1and入節點vi,q的入度為1then

6. 合并出任務vi,p和入任務vi,q,并更新任務計算量;

7.endif

8.endfor

9.}whilewi存在有向割邊;

endprocedure

3.2.2 調度未調度任務

在算法1中,WSPCP調用算法3,以虛擬出任務vout作為輸入,調度工作流應用wi的所有未調度任務.

算法3.調度任務vi,j的所有未調度父任務

procedureScheduling_All_Parents(M,vi,j)

Input:M,vi,j

1.whilevi,j存在直接未調度父任務do

2.Initialization:v←vi,j,stack←null,PCP(vi,j)←null;

3.whilev存在直接未調度父任務then

4.stack.push(CP(v));

5.v=CP(v);

6.endwhile

7.whilestackis not emptydo

8.PCP(vi,j).append(stack.pop());

9.endwhile

10. //調用算法4,調度任務vi,j的局部關鍵路徑

11. Scheduling_Path(M,PCP(vi,j));

12.foreachvi,p∈PCP(vi,j)do

13. 更新vi,p所有未調度后繼任務的EFT和EST;

14. 更新vi,p所有未調度前驅任務的LST和LFT;

15. Scheduling_All_Parents(M,vi,p)

16.endfor

17.endwhile

endprocedure

3.2.3 調度局部關鍵路徑

在算法3中,Scheduling_All_Parents過程調用算法4,將任務vi,j的局部關鍵路徑統一調度到云邊協同環境中的最適合服務器上.

算法4.調度局部關鍵路徑

procedureScheduling_Path(M,PCP)

Input:M,PCP

1.foreachsk∈Sdo

2. 尋找執行PCP的最適合服務器sk;

3.endfor

4.ifsk不存在then

5. 在滿足PCP的局部截止時間約束完成所有任務的條件下,租賃并初始化一個單位計算代價最小的服務器sk,即最適合服務器;

6.endif

7.將PCP調度到最適合服務器sk上;

8.foreachvi,p∈PCPdo

9.M=M∪(vi,p,sk);

11. 設置任務vi,p為已調度任務;

12.endfor

endprocedure

該算法描述了局部關鍵路徑PCP的調度過程,利用貪心策略尋找執行PCP的最適合服務器.對于局部關鍵路徑PCP,對應的最合適服務器定義如下:云邊協同環境中的某個服務器sk,能夠在PCP對應的局部截止時間內完成PCP上的所有任務,且同時滿足以下3個條件:

(36)

其中,t1和t2分別表示在執行PCP前后服務器sk的實際執行時間,「t1?表示根據要價單元時間uk的向上整合時間.特別地,若服務器sk剛啟動,則t1=0.

2)如果存在多個最低執行增長代價相等的服務器,則選擇實際執行時間最長的服務器sk.

(37)

如果不存在可用的最適合服務器,則租賃并初始化一個單位計算代價最小的服務器sk,同時能夠在滿足PCP局部截止時間約束的條件下完成所有任務.最后,將PCP調度到最適合服務器sk上,同時將所有任務設置為已調度任務.

4 仿真實驗與分析

4.1 實驗設置

所有實驗都在16 GB RAM和3.00GHz Intel i5-9500F CPU的Win 10系統下運行,WSPCP和所有對比調度策略均在Python 3.8環境下實現.

用戶每次提交的工作流應用均來自于Bharathi等[28]所提出的5種小型工作流應用模型:地震科學CyberShake、生物基因學Epigenomics、重力物理學LIGO、天文學Montage和生物信息學SIPHT.每種工作流應用含有約30個任務,具有不同的依賴結構,其計算需求和數據集大小等相關信息均被存儲在xml文件中.在本次實驗中,設置多工作流應用的規模為20個.假定工作流應用的到達是一個強度為λ的泊松過程,工作流應用到達的時間間隔服從參數為λ的指數分布,用戶平均每隔2.5s向云邊協同環境提交工作流應用,則工作流的平均間隔時間為1/λ=2.5,即λ取0.4.因此,對于工作流應用wi,定義其到達時間αi如式(38)所示:

(38)

其中,randexp(λ)用于產生參數為λ的指數分布隨機數.

另外,每個工作流應用都有對應的截止時間約束,并以此來測試調度策略的有效性.對于工作流應用wi,定義其截止時間di如式(39)所示:

di=αi+bl*|W|*HEFT(wi),bl={2.0,2.5,3.0,3.5}

(39)

其中,HEFT(wi)表示用HEFT算法[29]調度工作流應用wi所需的執行時間.參數bl表示截止時間因子.

在模糊云邊協同環境中,假定初始時刻存在5個云服務器(s1,s2,…,s5)和5個邊緣服務器(s6,s7,…,s10).每個服務器具有特定的任務計算能力和單位計算代價.假定云服務器s1,s2,…,s5的計算能力分別為2.5,3.5,5.0,7.5,10.0GHz,邊緣服務器s6,s7,…,s10的計算能力約2.5GHz,分別為2.5,2.6,2.2,2.3,2.7GHz;假定計算能力最強的云服務器s5的單位計算代價為12.5 $/h或(5/24 $/min),以云服務器s5的單位時間計算代價為基準,其余服務器的單位計算代價近似與其計算能力成正比.在工作流應用調度中,可以根據需要動態租賃并初始化具有上述性能的服務器.

目前主流的商業云服務,如Amazon EC2,通常按1分鐘或1小時為要價單元時間μi進行付費.在本次實驗中,用戶提交的工作流應用均為小型規模,選擇以1分鐘為單位進行付費.

兩個服務器si和sj之間的帶寬和單位數據傳輸代價,根據二者所屬環境fi和fj的不同,如表1進行設置.

表1 不同服務器si和sj之間的帶寬Table 1 Bandwidths between different servers

第2.3.2節詳細闡述了如何將計算性能pk和帶寬br,t模糊化為對應的三角模糊數,參數δ1和δ2分別取為0.75和1.2.為了比較實驗結果的好壞,第2.3.2節同時給出了模糊云邊協同環境下的多工作流應用模糊執行代價和模糊完成時間的去模糊化方法,參數?取為1;另外,基于時效性的考慮,設置參數η的值為0.95.

4.2 基準策略

WSPCP是一種啟發式調度策略,為了驗證該策略對于降低多工作流應用模糊執行代價的有效性,在本次實驗中,將以下3個調度策略作為基準策略,用于比較WSPCP和其他基準策略的調度性能.

1)WSGS(Workflow applications Scheduling based on Greedy Strategy):該策略采用與WSPCP相同的預處理方法,在調度過程中,對于泊松到達的每個工作流應用,采用最早完成時間優先[29]的策略為每個任務選擇執行的服務器.當現有服務器無法滿足截止時間約束時,允許在云邊協同環境中租賃并初始化新的服務器.

2)WSPG(Workflow applications Scheduling strategy based on Particle swarm optimization employing Genetic operators):該策略采用服務器和優先級嵌套的編碼策略,服務器編碼采用離散值表示執行任務的服務器編號,優先級編碼采用連續值表示同一時刻服務器中待執行任務的優先級大小;采用PSO-GA更新策略[14]對粒子編碼進行更新以尋找較優的調度方案,參數w,c1,c2根據文獻[14]進行設置,種群規模和迭代次數分別設置為100和1000.

3)WSRS(Workflow applications Scheduling based on Random Searching):該策略采用與WSPG相同的優先級和服務器嵌套的編碼策略,使用隨機搜索策略生成新的種群,在相應的定義域內隨機生成每個粒子的優先級和服務器編碼,并將粒子映射到對應的調度方案,記錄隨機搜索過程中的最優解,每次迭代之間互不影響,最終輸出種群的最優解,即最優調度方案,其中,種群規模和迭代次數分別設置為100和1000.

4.3 實驗結果與分析

4.3.1 不同截止時間約束下的調度性能

為了比較WSPCP和其他基準策略在模糊云邊協同環境中多工作流應用的調度性能,在不同的截止時間約束下,對多工作流應用調度進行4組仿真實驗,包括嚴格(bl=2.0)、 中等(bl=2.5)、微小(bl=3.0)和寬松(bl=3.5)4種截止時間約束,并分析WSPCP在降低多工作流應用模糊執行代價方面的優越性.對于每種截止時間約束,記錄10次獨立重復實驗中的最優和平均模糊執行代價及其適應度(單位:10-3$).表2展示了在不同調度策略下多工作流應用的最優模糊執行代價,其中,最優解用粗體表示,不可行解用符號“*”標記.

表2 不同調度策略下多工作流應用的最優模糊執行代價Table 2 Optimal fuzzy execution cost of workflow applications based on different scheduling strategies

從優化目標來看,本文所提出的調度策略WSPCP在4種截止時間約束下都得到了最優的調度方案,即多工作流應用的模糊執行代價最小,而WSPG的性能次之.WSPCP采用預處理方法合并有向割邊,降低了問題的任務規模;同時將局部關鍵路徑的所有任務作為調度單元進行調度,很大程度上避免了任務之間的數據傳輸,從而減少數據傳輸代價,最終得到最優的調度方案.而WSPG作為一個全局搜索策略,由于受到解空間規模的限制,難以在有限的迭代次數內得到更優的調度方案,但仍然優于傳統的貪心策略,即WSGS.值得注意的是,WSRS在指數級的解空間中進行無差別的隨機搜索,僅在寬松的截止時間約束下可以得到可行的調度方案,對于多工作流調度這一約束優化問題而言,WSRS是無法接受的.

從截止時間約束來看,WSPCP和WSGS在任何情況下都能得到滿足約束的可行調度方案.在嚴格(bl=2.0)的截止時間約束下,WSPG和WSRS是無效的,無法得到可行的調度方案.隨著截止時間約束的放寬(bl≥2.5),多工作流應用的模糊執行代價呈降低趨勢,且WSPG能夠得到可行的調度方案.然而,僅在寬松(bl=3.5)的截止時間約束下,WSRS能夠得到可行解.這是因為多工作流應用調度是一個組合優化問題,具有大量的局部極值點,是不連續的、高度非線性的NP難問題.在嚴格的截止時間約束下,作為全局搜索策略,對于指數級規模的解空間,WSPG在有限的迭代次數內無法得到更優的調度方案,即使它能夠對解空間進行有方向、有目標地探索;而WSRS所采用的隨機搜索策略效率較低,在解空間內進行無差別地探索,難以搜索到高質量的、可行的調度方案.

此外,對于每種截止時間約束下的10次獨立重復實驗,圖4展示了在不同調度策略下多工作流應用的平均模糊執行代價.從圖4中可以看出,在4種截止時間約束下,WSPCP所產生的調度方案下的多工作流應用的平均模糊執行代價均優于其他基準策略.特別地,在嚴格(bl=2.0)的截止時間約束下,相較于其他基準策略,WSPCP對于多工作流應用平均模糊執行代價的降低約為7.5%～70.0%.由此可見,WCPCP在不同截至時間約束下的魯棒性更強.

圖4 不同調度策略下多工作流應用的平均模糊執行代價Fig.4 Average fuzzy execution cost of workflow applications based on different scheduling strategies

綜上所述,相較于其他基準策略,WSPCP將局部關鍵路徑上所有任務作為調度單元進行統一調度,很大程度上避免了任務之間的數據傳輸,減少數據傳輸的時間和代價,從而總是能夠得到更優的可行調度方案.特別地,在嚴格的截止時間約束下,WSPCP仍然可以得到滿足截止時間約束的可行調度方案,同時降低多工作流應用的模糊執行代價,表現出更優的性能.

4.3.2 實際應用中的決策實時性與調度分析

在實際應用中,往往還需要考慮多工作流應用的平均到達率和應用規模等.在極端情況下,多個工作流應用在同一時刻被提交至云邊協同環境中執行,這種情形則考慮調度策略的決策實時性.為了比較WSPCP和其他基準策略在模糊云邊協同環境中的決策時間,在中等(bl=2.5)的截止時間約束下,對4種不同規模的多工作流應用調度進行實驗,包括20、30、50和100,并分析WSPCP的調度決策實時性.對于不同規模的多工作流應用調度,記錄10次獨立重復實驗的總決策時間(單位:s).圖5展示了在不同工作流應用規模下不同調度策略的總決策時間,為了方便對比,圖5的縱坐標采用底數為4的對數刻度,將總決策時間控制在合理的區間范圍內.值得注意的是,當工作流應用的規模為100時,WSPG和WSRS的總決策時間將超過64800s(即18 hour),這是無法接受的決策時間,因此在圖5中不展示二者的實際決策時間,僅以填充圖案為橫線的柱狀表示.

圖5 不同工作流應用規模下不同調度策略的總決策時間Fig.5 Total decision time of different scheduling strategies under different workflow application scales

由圖5可以看出,與全局調度策略WSPG和WSRS相比,兩個啟發式調度策略WSPCP和WSGS在決策時間上具有絕對的優勢,二者的單次決策時間僅1s不到,能夠做到接近實時調度.這是因為WSPCP和WSGS基于有向割邊的預處理機制,降低工作流應用的任務規模,同時采用啟發式方法,基于某種尋優策略,能夠快速得到較優的可行調度方案;而WSPG和WSRS則需要在全局解空間中不斷迭代搜索,由于多工作流應用調度的解空間隨著工作流應用的規模指數級增長,因此需要花費更多的決策時間,此類調度策略更適合靜態調度的情形.相對于WSGS,WSPCP所需的決策時間更久,這是因為對于每個到達的工作流應用,WSPCP需要尋找工作流應用的局部關鍵路徑,從而將其統一調度到服務器上,以減少任務之間的數據傳輸.從4.3.1節的結論來看,同樣是秒級的決策時間,較少的時間差能夠得到更優的工作流應用調度方案,這是值得的.

另外,工作流應用的實際情況,包括其任務規模、任務的計算復雜度、任務之間的數據傳輸量等因素,也是實際調度過程中可能遇到的挑戰.特別地,作為交通系統中的工作流應用之一,車輛識別應用的核心技術是DNN,而工作流應用調度決策是影響車輛識別應用中DNN性能的關鍵問題之一[1].處理能力有限的交通攝像頭會定期記錄道路車輛的圖像,但是通常無法在其截止時間內完成應用,因此往往需要將此類應用提交到云邊協同環境進行處理.在不確定性云邊協同環境中,計算環境的不確定性因素對此類問題的系統延遲影響很大,容易導致對最優調度方案的誤判,很難從眾多方案中選擇最佳的服務器解決方案.本文所提出的調度策略WSPCP能夠為車輛識別應用做出高效的工作流應用調度決策,同時可以降低主要由層內計算和層間數據傳輸在截止時間內引起的執行代價.具體而言,WSPCP可以將車輛識別應用中的復雜DNN層(任務)可以調度到云端執行,而簡單的DNN層(任務)則在邊緣進行處理,云和邊緣平臺之間相互協作,以較低的執行代價和系統延遲執行DNN層;將局部關鍵路徑作為整體統一調度到同一服務器上執行,從而一定程度上避免DNN層(任務)之間的數據傳輸,有效減低數據傳輸產生的代價和時延.

5 結束語

針對模糊云邊協同環境下多工作流應用調度,本文將服務器的計算性能和服務器之間的帶寬表示三角模糊數,以體現云邊協同環境中的不確定性對多工作流應用調度的影響.同時,針對泊松到達的多工作流應用,提出一種基于局部關鍵路徑的多工作流應用調度策略WSPCP,用于優化截止時間約束下多工作流應用的模糊執行代價.實驗結果表明,與其他基準策略相比,所提出的策略在多工作流應用調度方面表現出良好的性能,在不同的截止時間約束下,WSPCP都能獲得多工作流應用最優的可行調度方案,同時實現了模糊執行代價的有效優化.在實際應用中,對于不同規模的多工作流應用,WSPCP展現了良好的決策實時性.同時,針對工作流應用的實際情況,包括工作流應用的任務規模、任務的計算復雜度、任務之間的數據傳輸量等因素,WSPCP具有一定的可行性.

在未來的工作中,希望建立一個適用于現實世界中多工作流應用的實時調度系統,整合云邊協同環境中的計算資源,考慮工作流應用任務規模龐大、多個應用同一時刻到達、工作流應用執行出錯等實際應用的各類極端情況,對IoT設備提交的工作流應用進行高效地調度.同時,根據當前云邊協同環境中服務器的實時負載情況和租賃成本,動態調整服務器的開啟和關閉,進一步優化多工作流應用的執行代價.