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

馬振峰， 李松松

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

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

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

1 理論基礎(chǔ)

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

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

(1)

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

MinimizeTEC，TET

(2)

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

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

(3)

(4)

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

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

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

2.1 具體算法介紹

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

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

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

3.2 結(jié)果分析

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

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

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

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

4 結(jié) 論

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

參考文獻(xiàn)

[1] 李敬偉, 張皓, 趙麗. 基于改進(jìn)群搜索優(yōu)化算法的云計(jì)算任務(wù)調(diào)度方案[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 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é)報(bào), 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]. 自動(dòng)化學(xué)報(bào), 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.