云環(huán)境下一種多維QoS約束的工作流調(diào)度算法

劉振鵬, 劉曉丹， 張錫忠, 蔄志賢

(1.河北大學(xué) 電子信息工程學(xué)院 河北 保定071002； 2.河北省保定市教育考試院 信息處 河北 保定 071000； 3.河北大學(xué) 計算機科學(xué)與技術(shù)學(xué)院 河北 保定 071002)

云環(huán)境下一種多維QoS約束的工作流調(diào)度算法

劉振鵬1，3, 劉曉丹1， 張錫忠2, 蔄志賢3

(1.河北大學(xué) 電子信息工程學(xué)院 河北 保定071002； 2.河北省保定市教育考試院 信息處 河北 保定 071000； 3.河北大學(xué) 計算機科學(xué)與技術(shù)學(xué)院 河北 保定 071002)

云計算以用戶為中心按需提供服務(wù)，云環(huán)境下必須關(guān)注用戶的服務(wù)質(zhì)量(QoS).云計算工作流調(diào)度的QoS目標約束條件，不僅有工作流完成時間，還包括調(diào)度預(yù)算、系統(tǒng)的可靠性以及安全性等，多維QoS約束的工作流調(diào)度算法的研究至關(guān)重要.為此，提出一種基于生物共生演算法(symbiotic organisms search，SOS)的多維QoS約束的工作流調(diào)度算法(QoS-SOS).首先為工作流中的每個任務(wù)分配適當(dāng)?shù)膬?yōu)先級，將非支配解的思想融入到生物共生演算法中，從而獲得分布均勻的Pareto最優(yōu)解集來解決多維QoS約束的工作流調(diào)度問題.實驗結(jié)果表明, QoS-SOS不僅擁有較快的收斂速度，而且有很好的尋優(yōu)能力，還能夠根據(jù)用戶的偏好選擇側(cè)重不同的優(yōu)化方案，從而適應(yīng)于大規(guī)模的云環(huán)境.

云計算； 服務(wù)質(zhì)量； 生物共生演； 工作流調(diào)度

0 引言

云計算是一種新興的技術(shù)趨勢，用戶可以根據(jù)自己的需求從其租用軟件、硬件、基礎(chǔ)設(shè)施和計算資源等[1].近年來，云計算通過互聯(lián)網(wǎng)擴展了現(xiàn)有的信息技術(shù)能力，成為一個低成本、快速的服務(wù)交付模式[2].它允許用戶訪問服務(wù)，就像水、電、煤氣和電話等公共設(shè)施一樣，用戶既不必考慮在哪里提供服務(wù)，也不用去了解他們是如何進行交付的[3].正是因為云計算的取用方便快捷、費用低廉，它越來越備受人們的關(guān)注，用戶量也日益增多.

云計算系統(tǒng)擁有大量的節(jié)點，很難要求所有節(jié)點擁有同樣的性能[4]，這就導(dǎo)致了云環(huán)境的異構(gòu)性.現(xiàn)在的大數(shù)據(jù)應(yīng)用都是非常復(fù)雜的，并不能夠僅僅通過幾個任務(wù)來進行描述，故工作流就被用來表示更加復(fù)雜的大數(shù)據(jù)應(yīng)用.如何將云環(huán)境下工作流任務(wù)映射并調(diào)度到合適的計算節(jié)點，成為新的研究方向.工作流調(diào)度是通過工作流調(diào)度控制，自動分配和管理相關(guān)任務(wù)在共享資源上的執(zhí)行[5].在云計算中，工作流調(diào)度通過訂購各種資源將每個任務(wù)分配到相關(guān)的云服務(wù)以獲得滿意的服務(wù)質(zhì)量[6].

相比于常規(guī)的云任務(wù)調(diào)度問題，云工作流調(diào)度不僅僅要考慮用戶服務(wù)質(zhì)量QoS(像執(zhí)行時間、用戶花銷等因素)的約束，還需要考慮工作流內(nèi)各個任務(wù)之間相互依賴關(guān)系.許多啟發(fā)式和進化算法被提出用于解決工作流調(diào)度問題，如遺傳算法[7]、蟻群優(yōu)化算法[8]、粒子群優(yōu)化算法[9].本文提出一種基于生物共生演算法的多維QoS約束的工作流調(diào)度算法，以有效地提高云環(huán)境下工作流調(diào)度的效率.

1 問題描述以及數(shù)學(xué)建模

1.1 云系統(tǒng)模型

本文所提出的云系統(tǒng)模型主要包括3個模塊，如圖1所示.

圖1 云模型結(jié)構(gòu)圖Fig.1 Structure of cloud model

1) 用戶模塊 多個云用戶通過網(wǎng)絡(luò)將任務(wù)提交上傳到云端的任務(wù)處理單元.

2) 任務(wù)處理單元模塊 該模塊負責(zé)定時收集用戶的任務(wù)的執(zhí)行信息，首先將用戶提交的工作流中的子任務(wù)進行優(yōu)先級的確認，并按照降序排列，形成新的任務(wù)調(diào)度隊列；再將數(shù)據(jù)中心管理器所提交的虛擬機信息收集，根據(jù)任務(wù)調(diào)度策略對任務(wù)進行處理，映射到較為合適的虛擬機上，使得任務(wù)可以更優(yōu)化地處理.

3) 數(shù)據(jù)中心模塊 一是數(shù)據(jù)中心管理器，通過它將數(shù)據(jù)中心的虛擬機信息(如內(nèi)存、處理速度MIPS等)進行收集，再提交給任務(wù)調(diào)度器模塊；二是基礎(chǔ)設(shè)施即分布式數(shù)據(jù)中心集群，其中包括多個數(shù)據(jù)中心DC.每個數(shù)據(jù)中心含有多臺主機，通過虛擬化技術(shù)，每臺主機被虛擬化到一系列異構(gòu)的虛擬機上，即虛擬機集合就分別映射到了主機集合上.

1.2 QoS目標函數(shù)

由于云計算環(huán)境的動態(tài)及不確定性，用戶服務(wù)質(zhì)量的優(yōu)化與管理變得至關(guān)重要.云環(huán)境下工作流調(diào)度的QoS目標約束條件(總的執(zhí)行時間、調(diào)度費用、系統(tǒng)的可靠性及安全性等)無一不影響著用戶體驗和滿意度.本文主要考慮工作流完成時間和用戶花費兩個QoS目標約束條件，則QoS目標約束函數(shù)為Minmize(Total_time)和Minmize(Total_cost).

工作流中任務(wù)被調(diào)度到計算資源，它的實際完成時間Total_time即為出口任務(wù)Texit的完成時間.而云工作流中成本花費包括執(zhí)行成本Execution_cost和通信成本Communication_cost兩部分，則執(zhí)行一個云工作流的成本定義如下：

其中:ti代表任務(wù)Ti在被調(diào)度到虛擬機上運行的執(zhí)行時間；Unit_ecosti表示在該虛擬機執(zhí)行單位時間的花銷；Dataij指的是任務(wù)Ti和Tj之間的通信數(shù)據(jù)；Unit_ccostij表示單位通信成本.

2 算法描述

本文在生物共生演算法的基礎(chǔ)上進行改進，從而來適應(yīng)云環(huán)境的工作流調(diào)度的優(yōu)化問題.針對多維QoS約束的問題，引入非支配解的概念，提出了一種多維QoS約束的工作流調(diào)度算法(QoS-SOS)，以解決多目標優(yōu)化問題.

2.1 生物共生演算法

生物共生演算法(symbiotic organisms search,SOS)[10]是一種基于種群的元啟發(fā)式算法,它與粒子群等算法相類似，都是模仿的自然現(xiàn)象，其性能優(yōu)于其他啟發(fā)式算法(GA，PSO等).它最初是用于解決連續(xù)搜索空間數(shù)值優(yōu)化問題.在SOS中，主要包括共生、共棲、寄生3個階段.在各個階段中，每一個生物體與其他生物體隨機相互作用，并重復(fù)這個過程，直到滿足終止條件為止.

2.2 非支配解

也就是說，對于任意的兩個決策變量X1和X2，在任意的目標函數(shù)中，X2都優(yōu)于X1,或者存在某一目標函數(shù)，X2不小于X1，則X2為非支配解(Pareto解).

因此，要解決多個QoS目標約束函數(shù)的多目標優(yōu)化問題，需要找到一組盡可能接近Pareto最優(yōu)域的解，并希望找到的解能夠盡可能分布均勻.然而，多個QoS約束目標之間存在沖突，如時間和成本，降低執(zhí)行時間的代價務(wù)必會增加開銷，同樣降低成本也必然影響執(zhí)行的時間.Pareto最優(yōu)解所對應(yīng)的目標函數(shù)是無法比較其優(yōu)劣的，在某一個非支配解的基礎(chǔ)上改進任何一個目標函數(shù)的同時，必然會引起一個或多個其他的目標函數(shù)變化.

為了滿足用戶QoS需求，本文算法中選擇使用一個可行的帶有權(quán)值的適應(yīng)值函數(shù)：

fitness=α*Total_time+β*Total_cost，

其中：α+β=1,0≤α，β≤1，α、β分別表示時間和成本的權(quán)重，體現(xiàn)了用戶對時間和成本關(guān)注的程度.權(quán)重α、β的不同必然會導(dǎo)致本文算法求得的優(yōu)化解集的不同.

2.3 優(yōu)先級確定

確定優(yōu)先級的目的，在于通過計算每個子任務(wù)的優(yōu)先級，并且通過優(yōu)先級的大小將子任務(wù)進行合理有序的排列，這樣便確定了本文算法中所應(yīng)用的生物共生演算法中生物體(即任務(wù))的排序，進而可以展開后續(xù)的工作，將任務(wù)分配到合適的虛擬機上進行處理.通過子任務(wù)的平均完成時間和任務(wù)之間的通信時間來確定任務(wù)優(yōu)先級，則一個任務(wù)的優(yōu)先級指的是從DAG中的出口任務(wù)Texit向上遍歷到所求的任務(wù)之間所有經(jīng)過的節(jié)點的平均時間和平均通信時間之和，可以表示為

(1)

2.4 多維QoS約束的工作流調(diào)度

在生物共生演算法的基礎(chǔ)上，借鑒離散粒子群算法中的離散化思想來適應(yīng)云計算離散環(huán)境，引入非支配解的思想，來滿足多維QoS的多目標約束，從而獲得Pareto最優(yōu)解集.表1中為基于多維QoS約束的工作流調(diào)度偽代碼，大致可以分為以下7個步驟.

表1 QoS-SOS偽代碼

Step1 確定任務(wù)的優(yōu)先級.根據(jù)公式(1)計算工作流應(yīng)用DAG中每個子任務(wù)的優(yōu)先級.

Step2 根據(jù)step1中所得的任務(wù)優(yōu)先級，對工作流中的任務(wù)重新進行排序.因為任務(wù)優(yōu)先級越高，任務(wù)越應(yīng)該優(yōu)先執(zhí)行，所以將任務(wù)進行降序排列.

Step3 初始化.采用隨機的方式對整個生態(tài)系統(tǒng)E中的各個生物體進行初始化，也就是說調(diào)度方案的隨機初始化，計算當(dāng)前生態(tài)系統(tǒng)各個生物體的適應(yīng)度值.

Step4 添加生態(tài)系統(tǒng)中的非支配解到一個外部存檔EA中，并刪除被該解支配的所有解.

Step5 進行共生、共棲、寄生3個階段，根據(jù)計算新的生物體適應(yīng)度，判斷是否進行更新，當(dāng)新的生物體適應(yīng)度大于原來的適應(yīng)度時，則進行更新替換；否則不發(fā)生變化.

Step6 添加生態(tài)系統(tǒng)中的非劣解，當(dāng)生態(tài)系統(tǒng)中的E[i]不被EA中的任何解所支配時，就將E[i]加入外部存檔，并且刪除EA中被E[i]所支配的所有解.

Step7 如果滿足循環(huán)終止的條件，返回外部存檔EA，此時EA則表示是一個調(diào)度方案集合；否則跳轉(zhuǎn)至step5繼續(xù)優(yōu)化.

本文所提出的算法最終獲得的是一個Pareto最優(yōu)的解集，這個解集就是解決方案的集合.集合中的每個解都是一個調(diào)度方案，用戶可以通過個人意愿和偏好選擇其中某一個解決方案，或者直接選擇本算法所推薦的調(diào)度方案.

3 仿真實驗

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

為了對本文所提出的算法進行測試評估，使用基于Cloudsim擴展WorkflowSim[12]平臺對QoS-SOS與已有的經(jīng)典算法HEFT算法、Min_Min、Max-Max進行對比實驗.

云服務(wù)資源處理能力的不同，就導(dǎo)致了它們價格的不同.一般說來，執(zhí)行成本和通信成本是反比于執(zhí)行時間和通信傳輸時間的，即執(zhí)行速度和執(zhí)行的成本是成正比的.因此，假設(shè)云環(huán)境下?lián)碛?種云服務(wù)資源，可依據(jù)表2來為云服務(wù)資源進行定價.在WorkflowSim中，搭建一個擁有6組服務(wù)資源的云環(huán)境，并且每組云資源各擁有4種云服務(wù)資源.

算法QoS-SOS的參數(shù)設(shè)置如表3所示.

表2 云服務(wù)資源類型

表3 QoS-SOS算法參數(shù)設(shè)置

3.2 實驗結(jié)果及分析

工作流Montage、Cybershake[13]和Gaussian Elimination[14]等代表了現(xiàn)實世界中的問題，常被作為基準來評估所提出的算法. Cybershake工作流是被南加州地震中心用來確定一個地區(qū)的地震災(zāi)害危險程度的[15-16].Cybershake是計算密集型和數(shù)據(jù)密集型工作流，不僅含有任務(wù)節(jié)點的數(shù)量可以不同，而且還可以處理大型的數(shù)據(jù)集，非常適合來驗證本文所提出算法的有效性.

在相同的條件下，對QoS-SOS、HEFT算法、Min_Min、Max-Max在Cybershake不同節(jié)點數(shù)30、50、100、1 000下分別進行了測試，并觀察比較結(jié)果.

在QoS-SOS算法中，每次試驗所得解是一組解集，由于所得解的數(shù)量較多，我們只在對比圖中畫出了部分解進行對比.由圖2可以看出，QoS-SOS所得的解是一個最優(yōu)解集，其中的每一個解都不絕對地用簡單的優(yōu)于或劣于其他的解來進行評價，這是由于執(zhí)行時間的變化影響著執(zhí)行的成本.此外，還可以看出，QoS-SOS算法產(chǎn)生的解支配HEFT、Min_Min、Max-Min算法產(chǎn)生的解.在不同任務(wù)節(jié)點的實驗中，不論是在時間還是成本上，本算法比其他3種算法具有絕對的優(yōu)勢.這是因為在HEFT算法中只考慮了優(yōu)化任務(wù)執(zhí)行時間，忽略了任務(wù)執(zhí)行的成本；而QoS-SOS將兩個方面的優(yōu)化目標都進行了考量.其次，相比于Min_Min、Max-Min算法，QoS-SOS算法利用任務(wù)優(yōu)先級嚴格遵守和保持了任務(wù)之間的依賴關(guān)系，并且優(yōu)化了任務(wù)的調(diào)度次序.

圖2 當(dāng)CyberShake節(jié)點為30、50、100、1 000時,各算法的對比

因此，QoS-SOS算法性能方面表現(xiàn)極為顯著，具有一定的有效性，極大程度上優(yōu)化了工作流調(diào)度的時間和成本.

4 結(jié)論

針對解決云環(huán)境下用戶服務(wù)質(zhì)量的優(yōu)化問題，建立了新的工作流調(diào)度云系統(tǒng)模型和相應(yīng)的數(shù)學(xué)模型，對本文所提出的算法進行了詳細的闡述.通過云工作流仿真平臺WorkflowSim，對QoS-SOS算法進行了仿真測試，并與HEFT、Min_Min、Max-Min算法進行了對比試驗.結(jié)果表明QoS-SOS算法不僅可以提供一組解，而且性能明顯優(yōu)于其他3種算法，極大程度上優(yōu)化了工作流執(zhí)行時間和總成本.然而，本文僅僅考慮了執(zhí)行時間和總成本兩個優(yōu)化目標，未來還可以考慮兩個或者兩個以上的優(yōu)化目標(如能耗、可靠性等).

[1] HAYES B. Cloud computing[J]. Communications of the ACM, 2008, 51(7):9-11.

[2] KAUR P D, CHANA I. A resource elasticity framework for QoS-aware execution of cloud applications[J]. Future generation computer systems, 2014, 37(7):14-25.

[3] 楊曉暉,丁文卿.云存儲環(huán)境下基于CP-ASBE數(shù)據(jù)加密機制[J].河北大學(xué)學(xué)報(自然科學(xué)版),2016,36(4):424-431.

[4] NARSIMHA R C H. A CIM (common information model) based management model for clouds[C]//2012 IEEE International Conference on Cloud Computing in Emerging Markets.Honolulu,2012:1-5.

[5] KAUR N, AULAKH T S, CHEEMA R S. Comparison of workflow scheduling algorithms in cloud computing[J]. International journal of advanced computer science and applications, 2011, 2(10):9036-9051.

[6] ALKHANAK E N, LEE S P, KHAN S U R. Cost-aware challenges for workflow scheduling approaches in cloud computing environments: taxonomy and opportunities[J]. Future generation computer systems, 2015, 50(C):3-21.

[7] AHMAD S G, MUNIR E U, NISAR W. PEGA: a performance effective genetic algorithm for task scheduling in heterogeneous systems[C]// High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS).Liverpool,2012:1082-1087.

[8] 王杰,李慧慧,彭金柱.一種擬隨機初始化模擬退火粒子群算法[J].鄭州大學(xué)學(xué)報(理學(xué)版),2016,48(3):75-81.

[9] TAHERI J, LEE Y C, ZOMAYA A Y, et al. A bee colony based optimization approach for simultaneous job scheduling and data replication in grid environments[J]. Computers and operations research, 2013, 40(6):1564-1578.

[10]CHENG M Y, PRAYOGO D. Symbiotic organisms search: a new metaheuristic optimization algorithm[J]. Computers and structures, 2014, 139:98-112.

[11]ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE transactions on evolutionary computation, 1999, 3(4):257-271.

[12]CHEN W, DEELMAN E. WorkflowSim: a toolkit for simulating scientific workflows in distributed environments[C]// IEEE International Conference on E-Science.Chicago,2012:1-8.

[13]JUVE G, CHERVENAK A, DEELMAN E, et al. Characterizing and profiling scientific workflows[J]. Future generation computer systems, 2013, 29(3):682-692.

[14]ARABNEJAD H, BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE transactions on parallel and distributed systems, 2014, 25(3):682-694.

[15]GRAVES R, JORDAN T H, CALLAGHAN S, et al. Cybershake: a physics-based seismic hazard model for southern california[J].Pure & applied geophysics, 2011, 168(3/4):367-381.

[16]CALLAGHAN S, MAECHLING P, SMALL P, et al. Metrics for heterogeneous scientific workflows: a case study of an earthquake science application[J]. International journal of high performance computing applications, 2011, 25(3):274-285.

(責(zé)任編輯：王海科)

A Workflow Scheduling Algorithm of Multi-QoS Constraints in Cloud Computing Environment

LIU Zhenpeng1,3, LIU Xiaodan1, ZHANG Xizhong2, MAN Zhixian3

(1.SchoolofElectronicInformationEngineering,HebeiUniversity,Baoding071002,China; 2.InformationDepartmentofBaodingExaminationAuthority,Baoding071000,China; 3.SchoolofComputerScienceandTechnology,HebeiUniversity,Baoding071002,China)

As cloud computing provided user-centered and on-demand services, the quality of service (QoS) must be concerned in the cloud environment. Not only the execution time of the workflow but also scheduling budget, system reliability and security, etc. were included in the objective constrained QoS of cloud workflow scheduling. The study of the workflow scheduling algorithm based on multi-QoS constraints became a matter of indispensable role.A workflow scheduling algorithm based on symbiotic organisms search for multidimensional QoS constraints was proposed. Firstly, priorities were assigned for each task appropriately in the workflow.The concept of non-dominated solution was incorporated into the symbiotic organisms search algorithm. The uniformly distributed Pareto optimal solution set could be obtained to solve the problem of workflow scheduling problem with multi-QoS constraints. The experimental results showed that the QoS-SOS not only had faster convergence rate and an excellent optimization ability, but also could get different optimization schemes based on the user’s preferences, which could be adapted to the large-scale cloud environment.

cloud computing; quality of service; symbiotic organisms search; workflow scheduling

2016-06-21

國家科技支撐計劃項目(2013BAK07B04)．

劉振鵬(1966—)，男，河北保定人，教授，主要從事云計算和信息安全研究，E-mail:lzp@hbu.edu.cn；通訊作者：張錫忠(1966—)，男，河北滄州人，高級工程師，主要從事大數(shù)據(jù)和數(shù)據(jù)挖掘研究，E-mail:zxz@hbu.edu.cn．

TP301.6

A

1671-6841(2017)02-0090-06

10.13705/j.issn.1671-6841.2016319