馬振峰， 李松松

(大連海洋大學(xué) 信息工程學(xué)院，遼寧 大連 116300)

大數(shù)據(jù)的發(fā)展使得云計算面臨著數(shù)據(jù)規(guī)模龐大的問題，云工作流調(diào)度已經(jīng)成為一個重要的研究課題[1-2],它關(guān)系到云計算的成本和效率.但在現(xiàn)實中，工作流調(diào)度是一個NP難題，它不可能在多項式時間內(nèi)產(chǎn)生最優(yōu)解[3].隨著智能計算算法的發(fā)展，采用蟻群算法、遺傳算法、粒子群優(yōu)化算法等智能計算算法來解決云計算工作流調(diào)度問題得到了普及[4-6].文獻[7]使用工作流的動態(tài)關(guān)鍵路徑來找到一個解.文獻[8]提出了一個動態(tài)的工作流調(diào)度方法，使用能夠找到最經(jīng)濟和實用資源的方法，并將幾個任務(wù)合并成一個單一任務(wù).文獻[9]使用各種動態(tài)和靜態(tài)算法來生成一個能夠滿足用戶服務(wù)質(zhì)量的解決方案.文獻[10]開發(fā)了一個能夠滿足期限約束和最小化成本的約束模型，該模型是基于粒子群優(yōu)化方法實現(xiàn)的.

本文提出一種利用截止期感知的云計算調(diào)度方法，將VM分配給需要調(diào)度的工作流，并在處理時間截止期完成工作的調(diào)度.實驗研究表明，提出的算法在求解最小成本和期限約束模型方面優(yōu)于粒子群優(yōu)化方法.

1 理論基礎(chǔ)

1.1 成本最小化和期限約束模型

定義總的執(zhí)行成本(TEC)和總的執(zhí)行時間(TET)如下：

(1)

式中，ETti表示調(diào)度任務(wù)完成的時間，Crj表示單位成本，LSTrj和LETrj分別表示資源rj的開始以及結(jié)束時間.另外，本文設(shè)置以下約束條件，以達到任務(wù)調(diào)度時間和成本的最小化.

MinimizeTEC，TET

(2)

1.2 粒子群優(yōu)化框架

在粒子群優(yōu)化中，每一個粒子有兩個向量x和v.x代表粒子的位置，也是所定義問題的一個解.v決定了在所定義的問題空間中粒子的運動.每個粒子的最佳位置pBest和種群的最佳位置gBest將存儲和更新.對于每個粒子i，每一代的x和v的更新如式(3)和(4)所示：

(3)

(4)

式中d代表向量的維度，w是慣性權(quán)重，c1和c2是加速系數(shù).r1和r2為0～1之間的隨機數(shù).在每一代中，評估每個粒子的適應(yīng)度,更新它們的個體最佳位置和種群的最佳位置.最后，根據(jù)式(3)和(4)更新每個粒子的x和v.

2 利用截止期感知的云計算調(diào)度方法

提出的基于截止期限感知的調(diào)度策略中，調(diào)度程序從不同的用戶處接受任務(wù)請求，將虛擬機作為資源分配給不同的請求，并借助遺傳算法來共同完成任務(wù).

2.1 具體算法介紹

rn表示第n個任務(wù)調(diào)度請求，tn1和tn2分別表示使用VM1和VM2完成調(diào)度任務(wù)rn所需的時間，dwn和drn分別表示調(diào)度任務(wù)rn的等待時間的截止期限和響應(yīng)時間的截止期限，sn和cn分別表示在使用VM1和VM2上任務(wù)rn的開始時間.當(dāng)調(diào)度任務(wù)開始時，算法利用解向量SV存儲作業(yè)請求的調(diào)度序列，并且識別出最短的tn1和tn2.如果最短時間為tn1，則將它對應(yīng)的調(diào)度任務(wù)rn加入SV的最前端，如果最短時間為tn2，則將它對應(yīng)的調(diào)度任務(wù)rn加入SV的尾端.

假設(shè)存在p個實例來完成調(diào)度任務(wù)，則解向量SV可以表示為p個子序列：

S1={ri/(imodp)=1}，S2={ri/(imodp)=2}，…，Sp={ri/(imodp)=0}，

式中：1 ≤i≤n，并且每個子序列Si將依次在VM1、VM2上處理.

在產(chǎn)生p個子調(diào)度序列后，利用啟發(fā)式方法來減少超時.文獻[11]提出的遺傳算法是一個模仿自然選擇過程的啟發(fā)式搜索.它可以根據(jù)選擇、交叉和突變應(yīng)用到優(yōu)化問題中.本文利用遺傳算法來優(yōu)化執(zhí)行時間以減少超時.

(1) 編碼.編碼種群的染色體的方法與粒子群優(yōu)化方法相似，唯一的區(qū)別是本文使用整數(shù)而不是浮點數(shù).坐標(biāo)i的值代表ti運行的資源.例如，dimj=j表示ti運行在資源rj上.

(2) 選擇.本文希望最小化成本，使用1/TEC來評估染色體的適應(yīng)度.公式如下：

(3) 交叉和突變. 每個染色體交叉的概率為Pc.如果滿足條件Random(0,1)

(4) 保持最好的策略. 文獻[12]提出了保持在選擇之前時間段內(nèi)的最優(yōu)解以避免破壞在突變或交叉中最好的染色體.在本文的方法中，假設(shè)有一個全局最優(yōu)染色體，在每一代的運行過程中，如果存在比全局最優(yōu)染色體更好的局部最優(yōu)染色體，則用這個局部最優(yōu)替代全局最優(yōu).提出的算法流程如圖1所示.

3 實驗結(jié)果分析

3.1 實驗設(shè)置

使用不同規(guī)模的數(shù)據(jù)來進行實驗.如果算法運行的代數(shù)FGEN>100 000，我們就可以認為解不存在；否則，當(dāng)找到可行解后，繼續(xù)執(zhí)行3 000次運算，以尋找最優(yōu)解.令Time表示算法執(zhí)行的時間，比較在不同期限約束下粒子群優(yōu)化和本文算法的FGEN和TEC.

在粒子群優(yōu)化方法中，本文設(shè)置c1=c2=2.0,w=0.5，種群規(guī)模為100，遺傳算法的種群規(guī)模也設(shè)置為100.對于遺傳算法的交叉和突變概率，分為兩種情況：(1) 當(dāng)尋找到可行解時，設(shè)置Pc=0.15，Pm=0.008；(2) 反之，則令Pc=0.8，Pm=0.002.為了防止偶然性，本文將兩種算法分別執(zhí)行50次.

3.2 結(jié)果分析

首先，在小規(guī)模的數(shù)據(jù)上驗證兩種算法的性能.假設(shè)調(diào)度任務(wù)的數(shù)量為50個，資源數(shù)量為15種.3個截止時間設(shè)置成80、100和120.表1和圖2所示為本次實驗結(jié)果.在相同的條件下，本文算法的TEC值和計算時間相對于粒子群優(yōu)化算法而言更小.在表1中，剛開始時，期限約束大，兩種算法獲得的可行解FGEN=0.但當(dāng)截止時間變得越來越小，粒子群算法的收斂速度變得比本文算法更快.然而，當(dāng)截止時間變得嚴格時，如80時，使用粒子群算法獲得的可行解的數(shù)量為0，相比之下，本文算法卻依舊能夠獲得多個可行解.

表1 小規(guī)模數(shù)據(jù)下FGEN和TEC不同的期限約束

其次，在小規(guī)模的數(shù)據(jù)上驗證兩種算法的性能.假設(shè)調(diào)度任務(wù)的數(shù)量為100個，資源數(shù)量為30種.3個截止時間設(shè)置成200、300和400.表2和圖3所示為本次實驗結(jié)果.同樣的，由實驗結(jié)果可知，盡管截止時間不同，由本文算法得出的可行解的計算時間總是比粒子群優(yōu)化更少，本文算法具有更好的性能.

表2 大規(guī)模數(shù)據(jù)下FGEN和TEC不同的期限約束

4 結(jié) 論

提出了一個利用截止期感知的云計算調(diào)度方法來解決云計算環(huán)境中的資源調(diào)度問題.該算法能夠在處理時間截止期完成工作的調(diào)度，并且采用遺傳算法來優(yōu)化執(zhí)行時間以減少超時，同時還能夠優(yōu)化任務(wù)調(diào)度的執(zhí)行成本.在不同調(diào)度規(guī)模和不同期限約束下的實驗表明，提出的算法更能適應(yīng)各種期限的約束，能夠以比粒子群優(yōu)化更小的TEC找到一個更優(yōu)解.

參考文獻

[1] 李敬偉, 張皓, 趙麗. 基于改進群搜索優(yōu)化算法的云計算任務(wù)調(diào)度方案[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2017, 39(4): 99-102.

[2] ZHANG Y Q, WANG X F, LIU X F, et al. Survey on cloud computing security[J]. Journal of Software, 2016, 8271(1):302-311.

[3] FANG W, MEI′AN L I, DAUN W. Cloud computing task scheduling based on dynamically adaptive ant colony algorithm[J]. Journal of Computer Applications, 2013, 33(11):3160-3159.

[4] 曾芳桂,趙曼.體育聯(lián)賽中基于GSO算法的賽程優(yōu)化方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2018, 40(1): 72-76.

[5] BHARATHI C, REKHA D, VIJAYAKUMAR V. Genetic algorithm based demand side management for smart grid[J]. Wireless Personal Communications, 2017, 93(2):481-502.

[6] 王東風(fēng), 孟麗. 粒子群優(yōu)化算法的性能分析和參數(shù)選擇[J]. 自動化學(xué)報, 2016, 42(10):1552-1561.

[7] LIU X F, ZHAN Z H, DU K J, et al. Energy aware virtual machine placement scheduling in cloud computing based on ant colony optimization approach[C]// Conference on Genetic and Evolutionary Computation. ACM, 2014:41-48.

[8] CHEN W N, ZHANG J. An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements[J]. IEEE Transactions on Systems Man & Cybernetics，Part C, 2009, 39(1):29-43.

[9] MAO M. Auto-scaling to minimize cost and meet application deadlines in cloud workflows[C]// High PERFORMANCE Computing, Networking, Storage and Analysis. IEEE, 2011:1-12.

[10] MALAWSKI M, JUVE G, DEELMAN E, et al. Algorithms for cost- and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[C]// International Conference for High PERFORMANCE Computing, Networking, Storage and Analysis. IEEE Computer Society, 2012:1-11.

[11] ZHAN Z H, ZHANG J, LI Y, et al. Orthogonal learning particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(6): 832-847.

[12] ZHANG J, ZHAN Z H, LIN Y, et al. Evolutionary computation meets machine learning: a survey[J]. IEEE Computational Intelligence Magazine, 2011, 6(4): 68-75.