基于化學(xué)反應(yīng)優(yōu)化與蟻群優(yōu)化融合的云工作流調(diào)度

胡紅宇 陳 政

1(永州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系 湖南 永州 425000) 2(湖南工學(xué)院計(jì)算機(jī)與信息計(jì)算學(xué)院 湖南 衡陽(yáng) 421001)

0 引 言

工作流模型廣泛應(yīng)用于大規(guī)模科學(xué)計(jì)算領(lǐng)域中的問(wèn)題建模，如天文學(xué)領(lǐng)域、地球科學(xué)領(lǐng)域、天體物理學(xué)領(lǐng)域、生物信息學(xué)等領(lǐng)域[1]。工作流的結(jié)構(gòu)包含多個(gè)任務(wù)節(jié)點(diǎn)和有向邊，能以典型的有向無(wú)循環(huán)圖DAG的形式來(lái)建立表達(dá)模型。工作流結(jié)構(gòu)中的頂點(diǎn)即為科學(xué)計(jì)算任務(wù)，有向邊給出計(jì)算任務(wù)間的順序關(guān)系，即明確給出兩個(gè)任務(wù)間的執(zhí)行次序。科學(xué)工作流規(guī)模大、任務(wù)量多、結(jié)構(gòu)較復(fù)雜，而云計(jì)算這種靈活按需的提供模式則為其提供了一種更高效的運(yùn)行環(huán)境。云計(jì)算以按需方式向用戶提供服務(wù)[2]，其服務(wù)類型包括軟件即服務(wù)SaaS、基礎(chǔ)設(shè)施即服務(wù)IaaS、平臺(tái)即服務(wù)PaaS。基礎(chǔ)設(shè)施即服務(wù)的IaaS云計(jì)算環(huán)境以虛擬機(jī)形式提供硬件資源，更加適用于科學(xué)工作流調(diào)度問(wèn)題的執(zhí)行環(huán)境[3-4]。

云工作流調(diào)度是NP難問(wèn)題，為了解決這一問(wèn)題，Abrishami等[5]利用一種局部關(guān)鍵路徑的思路設(shè)計(jì)了一種工作流調(diào)度算法，該算法可以在降低任務(wù)執(zhí)行代價(jià)的同時(shí)確保滿足工作流的截止時(shí)間約束。Poola等[6]分別針對(duì)效率優(yōu)先和費(fèi)用優(yōu)先的原則設(shè)計(jì)了兩種工作流調(diào)度算法，但均是單個(gè)目標(biāo)函數(shù)下的無(wú)約束最優(yōu)化問(wèn)題，這顯然并不符合云工作流調(diào)度中資源利用有償以及任務(wù)執(zhí)行有時(shí)間限制的實(shí)際調(diào)度特征。Rodriguez等[7]利用粒子群PSO進(jìn)化的思想設(shè)計(jì)了一種工作流調(diào)度算法，雖然算法考慮了云資源在使用時(shí)的彈性特征和虛擬機(jī)資源提供能力的異構(gòu)特征，但是并沒(méi)有解決粒子群進(jìn)化過(guò)程中的粒子早熟問(wèn)題，使得最終得到的解還有進(jìn)一步改進(jìn)空間。Malawski等[8]利用混合整數(shù)非線性進(jìn)化的思想在混合云計(jì)算環(huán)境中設(shè)計(jì)了一種工作流任務(wù)調(diào)度方法，其目標(biāo)與本文目標(biāo)是相類似的，都是實(shí)現(xiàn)截止期限約束下的任務(wù)執(zhí)行代價(jià)的優(yōu)化，但文獻(xiàn)[8]中考慮的環(huán)境是比較單一的，所支持的調(diào)度任務(wù)類型具有特定性，對(duì)于不同結(jié)構(gòu)的任務(wù)結(jié)構(gòu)不具備適應(yīng)性。類似地，鄭敏等[9]也利用動(dòng)態(tài)規(guī)劃的思想設(shè)計(jì)工作流調(diào)度算法，進(jìn)而求解多約束的工作流調(diào)度問(wèn)題，但其考慮的虛擬機(jī)資源單一，未考慮多類型虛擬機(jī)提供環(huán)境。

綜合以上的分析可以看出，云環(huán)境中工作流調(diào)度無(wú)法滿足用戶給定的期限時(shí)間約束，或者在進(jìn)行任務(wù)調(diào)度時(shí)無(wú)法選擇最優(yōu)的虛擬機(jī)類型，從而導(dǎo)致過(guò)高的資源利用代價(jià)。同時(shí)，有一些研究考慮的環(huán)境比較單一化，所能調(diào)度的任務(wù)類型具有一定的特定性，無(wú)法滿足不同結(jié)構(gòu)類型的任務(wù)的調(diào)度需求與調(diào)度適應(yīng)性。為了解決這一問(wèn)題，本文提出一種滿足截止時(shí)間約束基于化學(xué)反應(yīng)優(yōu)化機(jī)制和蟻群優(yōu)化機(jī)制融合的工作流調(diào)度算法CRO-ACO。通過(guò)結(jié)合CRO尋優(yōu)快速和ACO在提高解質(zhì)量上的優(yōu)勢(shì)，以盡可能高的約束滿意度來(lái)得到工作流任務(wù)的調(diào)度方案，從而實(shí)現(xiàn)云工作流在執(zhí)行時(shí)間與執(zhí)行代價(jià)上的均衡優(yōu)化目標(biāo)，最后通過(guò)幾種典型工作流結(jié)構(gòu)作為數(shù)據(jù)源對(duì)算法性能進(jìn)行分析。

1 系統(tǒng)模型

1.1 云計(jì)算模型

云計(jì)算是一種通過(guò)互聯(lián)網(wǎng)提供計(jì)算服務(wù)的新型模式，其主要的服務(wù)類型包括：軟件即服務(wù)模式SaaS，基礎(chǔ)設(shè)施即服務(wù)模式IaaS和平臺(tái)即服務(wù)模式PaaS。云計(jì)算利用虛擬機(jī)化技術(shù)以虛擬機(jī)的方式提供所有資源。因此，用戶可以以虛擬機(jī)的形式租用高性能的計(jì)算資源來(lái)執(zhí)行自身任務(wù)。虛擬機(jī)在其CPU速率、CPU內(nèi)核數(shù)量、內(nèi)存大小、存儲(chǔ)、單位時(shí)間租用價(jià)格上均擁有不同的配置。根據(jù)虛擬機(jī)VM的配置，其定價(jià)也不相同，這表明越快的虛擬機(jī)越貴。

本文所討論的云計(jì)算模型為亞馬遜的彈性計(jì)算Amazon EC2中按需模式提供的IaaS云模型。該模型可以提供虛擬化式的計(jì)算資源、存儲(chǔ)資源和網(wǎng)絡(luò)帶寬資源，對(duì)物理底層資源的復(fù)雜性實(shí)現(xiàn)透明化操作。運(yùn)用模型中的云計(jì)算，用戶可以根據(jù)其應(yīng)用需求進(jìn)行添加或釋放虛擬機(jī)實(shí)例類型。假設(shè)所有的存儲(chǔ)服務(wù)和計(jì)算資源均處于相同的數(shù)據(jù)中心中。因此，在虛擬機(jī)間的高速數(shù)據(jù)傳輸與其提供的帶寬是對(duì)等的。對(duì)于異構(gòu)虛擬機(jī)構(gòu)成的云資源系統(tǒng)模型，每一種可用的虛擬機(jī)類型均可以作為任務(wù)調(diào)度的選擇目標(biāo)，并基于虛擬機(jī)的處理能力和資源占用狀態(tài)進(jìn)行任務(wù)調(diào)度目標(biāo)的優(yōu)化與映射求解。

1.2 應(yīng)用模型

一個(gè)科學(xué)工作流應(yīng)用由任務(wù)群組構(gòu)成，可模擬為一個(gè)有向無(wú)環(huán)圖DAG的結(jié)構(gòu)，表示為一個(gè)四元組G(T,E,W,C)，其中：T表示任務(wù)集合，T={t1,t2,…,tn};E表示任務(wù)間的邊集合;W表示任務(wù)的計(jì)算代價(jià);C表示任務(wù)間的通信代價(jià)。在DAG中，每條邊e(ti,tk)代表任務(wù)ti和tk間的依賴約束，表明ti是tk的父節(jié)點(diǎn)，任務(wù)tk是ti的子節(jié)點(diǎn)，任務(wù)ti必須在tk開始執(zhí)行前得以完成。同時(shí)，若DAG中存在一個(gè)沒(méi)有父節(jié)點(diǎn)的任務(wù)，則為根節(jié)點(diǎn)，而沒(méi)有子節(jié)點(diǎn)的任務(wù)則為DAG的葉子節(jié)點(diǎn)。工作流模型最佳的表達(dá)結(jié)構(gòu)是圖論中的有向無(wú)環(huán)圖模型，該模型可以明確工作流結(jié)構(gòu)中所有任務(wù)間的偏序關(guān)系，即前驅(qū)與后繼關(guān)系，以此約束任務(wù)間的執(zhí)行次序。另外，工作流結(jié)構(gòu)中的入口任務(wù)與出口任務(wù)在有向無(wú)環(huán)圖中也可以明確表示。基于有向無(wú)環(huán)圖模型，算法設(shè)計(jì)中對(duì)于任務(wù)的調(diào)度選擇也更加便利。

圖1為一個(gè)高斯應(yīng)用的DAG結(jié)構(gòu)圖，由9個(gè)任務(wù)構(gòu)成，計(jì)算代價(jià)矩陣如表1所示，表明每個(gè)任務(wù)在三個(gè)不同虛擬機(jī)上的執(zhí)行代價(jià)。DAG中邊上的權(quán)值代表任務(wù)間的數(shù)據(jù)傳輸量，即邊權(quán)重Cweight(ti,tk)。邊e(ti,tk)的通信代價(jià)C(ti,tk)則為兩個(gè)任務(wù)ti和tk間傳輸數(shù)據(jù)所花的時(shí)間，表示為：

(1)

式中：B為平均帶寬。當(dāng)兩個(gè)任務(wù)調(diào)度到相同的虛擬機(jī)上時(shí)，由于虛擬機(jī)內(nèi)的通信網(wǎng)絡(luò)是極高速網(wǎng)絡(luò)，因此兩個(gè)任務(wù)間的通信代價(jià)可以忽略不計(jì)，表示為e(i,k)=0。

任務(wù)ti在虛擬機(jī)VMj上的執(zhí)行時(shí)間為ET(ti,VMj)，計(jì)算為：

(2)

式中：MI表示任務(wù)ti的指令執(zhí)行數(shù)量，即百萬(wàn)指令數(shù)；MIPS表示虛擬機(jī)VMj的每秒執(zhí)行的百萬(wàn)指令數(shù)。

任務(wù)ti在虛擬機(jī)VMj上的開始時(shí)間TST定義為：

TST(ti,VMj)=max{Timavail(VMj),max{FFT(tk)+

C(ti,tk)}}

式中：Timavail(VMj)表示虛擬機(jī)VMj開始執(zhí)行一個(gè)新任務(wù)的就緒時(shí)間；FFT(tk)表示任務(wù)tk的最終完成時(shí)間(tk是ti的父節(jié)點(diǎn)任務(wù)，k=1,2,…,n)。任務(wù)ti在虛擬機(jī)VMj上的完成時(shí)間TFT可表示為TFT(ti,VMj)，計(jì)算為：

TFT(ti,VMj)=TST(ti,VMj)+ET(ti,VMj)

(3)

圖1 一個(gè)高斯應(yīng)用的DAG示例

表1 計(jì)算代價(jià)矩陣

2 算法設(shè)計(jì)

本節(jié)提出一種新的兩階段混合算法實(shí)現(xiàn)云計(jì)算中的工作流調(diào)度算法CRO-ACO，平衡可用云資源上的負(fù)載，在不違背截止時(shí)間約束的前提下最小化調(diào)度時(shí)間。第一階段通過(guò)應(yīng)用化學(xué)反應(yīng)優(yōu)化機(jī)制CRO快速地尋找近似最優(yōu)解，第二階段通過(guò)應(yīng)用蟻群優(yōu)化機(jī)制ACO進(jìn)一步改進(jìn)調(diào)度解的質(zhì)量，進(jìn)而得到全局最優(yōu)解。兩階段的優(yōu)化機(jī)制使得本文算法可以充分利用CRO的低時(shí)間復(fù)雜度和ACO對(duì)于候選解質(zhì)量的改進(jìn)。

2.1 化學(xué)反應(yīng)優(yōu)化機(jī)制

化學(xué)反應(yīng)優(yōu)化機(jī)制CRO模擬了在封閉容器中的分子之間以及分子與容器內(nèi)壁之間進(jìn)行的一系列化學(xué)反應(yīng)過(guò)程，每一次反應(yīng)均會(huì)產(chǎn)生一個(gè)或兩個(gè)新的分子。每個(gè)分子擁有唯一的結(jié)構(gòu)，代表一個(gè)解Φ。化學(xué)反應(yīng)優(yōu)化機(jī)制的優(yōu)勢(shì)在于可以通過(guò)分子的墻壁碰撞、分子的分解、分子間碰撞、分子的合成四個(gè)步驟快速找到任務(wù)調(diào)度方案的近似最優(yōu)解，得到充分?jǐn)U展的解空間，為后續(xù)對(duì)于解的進(jìn)一步篩選和優(yōu)化生成較為多樣和優(yōu)異的種群個(gè)體。

調(diào)度過(guò)程中，一個(gè)分子由兩個(gè)原子集合組成，第一個(gè)集合α代表DAG任務(wù)，第二個(gè)集合β代表分配至集合α中的任務(wù)的虛擬機(jī)的集合，圖2為一個(gè)分子結(jié)構(gòu)示例，即一個(gè)調(diào)度解，給出一種任務(wù)與虛擬機(jī)集合間的映射情形。

圖2 一個(gè)分子Φ

每個(gè)分子表現(xiàn)出的特征為解的勢(shì)能E(適應(yīng)度函數(shù)f(S)=EΦ)和動(dòng)能K。CRO利用動(dòng)能K和勢(shì)能E代表是否接收或拒絕一個(gè)新生成的分子代表的解。然而，計(jì)算每個(gè)分子的動(dòng)能K的時(shí)間復(fù)雜度較高，本文算法將簡(jiǎn)化該過(guò)程，僅利用E值來(lái)評(píng)估新生成的分子解的質(zhì)量。算法1給出計(jì)算適應(yīng)度值E(即工作流調(diào)度長(zhǎng)度)以評(píng)估是否接受新解Φ的過(guò)程。

算法1適應(yīng)度計(jì)算

輸入:solution S with scheduling queue

//輸入調(diào)度隊(duì)列中的調(diào)度解

輸出:makespan

//輸出工作流的執(zhí)行時(shí)間

1. add all atoms/tasks inTQaccording to solutionΦ

//根據(jù)解Φ將所有原子/任務(wù)添加至任務(wù)隊(duì)列TQ

2. addVMsinVMQaccording to solutionΦ

//根據(jù)解Φ將虛擬機(jī)添加至虛擬機(jī)隊(duì)列VMQ

3. whileTQis not empty

//若TQ非空

4. selecttifromTQand the correspondingVMifromVMQ

//選擇TQ中的任務(wù)ti與VMQ中的VMi進(jìn)行映射

5. calculateTFT(ti,VMi) according to solutionΦ

//根據(jù)解Φ計(jì)算TFT

6. removetifromTQ

//從TQ中移除任務(wù)ti

7. removeVMifromVMQ

//從VMQ中移除VMi

8. end while

9. return fitness valueSL=EΦ

//返回適應(yīng)度值

算法1中，根據(jù)當(dāng)前解Φ，所有任務(wù)被放入一個(gè)任務(wù)隊(duì)列TQ中，對(duì)應(yīng)的VMs以相同的順序被放入虛擬機(jī)隊(duì)列VMQ中。此時(shí)，TQ中任一任務(wù)ti調(diào)度至隊(duì)列VMQ的VMi上。算法1計(jì)算每個(gè)任務(wù)的完成時(shí)間TFT直到獲得葉子任務(wù)的完成時(shí)間為止，最終，返回葉子任務(wù)的TFT作為工作流的調(diào)度長(zhǎng)度。

CRO中，分子總共經(jīng)過(guò)四種化學(xué)反應(yīng)：墻壁碰撞、分解、分子間碰撞、合成。

1) 墻壁碰撞。墻壁碰撞是單分子反應(yīng)行為，即一個(gè)分子Φ與封閉容器壁發(fā)生碰撞，其結(jié)果是產(chǎn)生一個(gè)新分子Φ’。新分子有著與老分子不同的特征。在碰撞中，算法首先從0至n-1中隨機(jī)選擇一個(gè)原子/任務(wù)i，針對(duì)示例原子atomk發(fā)現(xiàn)atomi的最近父節(jié)點(diǎn)。接著，算法存儲(chǔ)atomi在處于k+1的最近父節(jié)點(diǎn)的下一位置，并且將原子從位置i+1移動(dòng)至位置i。類似地，算法利用相同的方法在集合β中交換虛擬機(jī)VMi和虛擬機(jī)VMk的位置。圖3是利用圖1所示的高斯應(yīng)用DAG進(jìn)行墻壁碰撞的詳細(xì)過(guò)程，所選擇的值i=3、k=0，然后，t3與t0發(fā)生碰撞，產(chǎn)生新節(jié)點(diǎn)t1，t3與新節(jié)點(diǎn)t1發(fā)生位置交換。最后，算法同時(shí)交換了處于位置i和位置k上的虛擬機(jī)。

圖3 墻壁碰撞示例

利用分子墻壁碰撞后即可得到一個(gè)新的分子Φ’，然后，化學(xué)反應(yīng)優(yōu)化CRO計(jì)算新生成分子勢(shì)能適應(yīng)度EΦ’。如果滿足EΦ’≤D，D為工作流執(zhí)行的截止時(shí)間，則算法接受新分子Φ’并將其存儲(chǔ)在候選調(diào)度解集中；否則，將丟棄新分子。

2) 分解。與分子的墻壁碰撞過(guò)程類似，分子分解也是基于單分子的反應(yīng)過(guò)程。然而，分子分解反應(yīng)的結(jié)果是產(chǎn)生兩個(gè)分子Φ1’和Φ2’。新分子的產(chǎn)生過(guò)程如下：(1) 算法隨機(jī)選擇兩個(gè)數(shù)i和j，i

圖4 分子分解示例

3) 分子間碰撞。分子間的碰撞操作可以通過(guò)兩個(gè)分子的輸入生成兩個(gè)新的分子。具體步驟如下：(1) 在0至n-1之間隨機(jī)選擇兩個(gè)數(shù)i和j，通過(guò)選擇的隨機(jī)數(shù)將Φ1和Φ2劃分為seg.1、seg.2和seg.3三個(gè)部分；(2) 通過(guò)繼承分子Φ1的seg.2和分子Φ2的剩余部分產(chǎn)生一個(gè)分子Φ1’；(3) 用相同的方式，產(chǎn)生新子Φ2’。如圖5所示，對(duì)于i=1和j=4，第一個(gè)分子Φ1’通過(guò)添加來(lái)自于分子Φ1中的原子t1、t2、t3和t4，以及分子Φ2的剩余原子組成。類似地，第二個(gè)分子Φ2’通過(guò)繼承分子Φ2的seg.2{t2,t1,t3,t4}和分子Φ1的剩余原子組成。若滿足條件EΦ1’≤D和EΦ2’≤D，則可接受分子Φ1’和Φ2’作為新的候選解。

圖5 分子間碰撞示例

4) 分子合成。合成操作的輸入為兩個(gè)分子Φ1和Φ2，輸出為一個(gè)新的分子Φ’。兩個(gè)分子間的合成操作步驟如下：(1) 在0至n-1間隨機(jī)選擇一個(gè)數(shù)i；(2) 通過(guò)i值將分子劃分為左半部分left和右半部分right；(3) 在不違背任務(wù)間的順序約束的前提下，新分子Φ’繼承Φ1的左半部分left和Φ2的右半部分right。

圖6為分子合成的示例。選擇隨機(jī)數(shù)i=4，將兩個(gè)分子結(jié)構(gòu)Φ1和Φ2劃分為左右兩個(gè)部分。為了創(chuàng)建新分子Φ’，Φ’的左半部分通過(guò)添加Φ1的左半部分{t0,t1,t2,t3,t4}，并結(jié)合Φ1的右半部分原子{t6,t5,t7,t8,VM0,VM2,VM1,VM0,VM1,VM1,VM2,VM2,VM0}得到新分子。若滿足EΦ’≤D，即可接受分子Φ’作為新的候選解放入解池中。

圖6 分子合成示例

為了使CRO在運(yùn)行四種分子操作上具有較高的公平性，本文對(duì)CRO進(jìn)行修改，使其運(yùn)行完全相同的四種分子操作步驟，從而使得算法能夠得到充分的解空間結(jié)構(gòu)。改進(jìn)CRO的具體步驟如算法2所示。

算法2改進(jìn)的化學(xué)反應(yīng)優(yōu)化算法過(guò)程Modified CRO

輸入:workflow tasks andVMlist//以有向無(wú)環(huán)圖的形式輸入

//工作流各個(gè)任務(wù)以及待分配的虛擬機(jī)列表

輸出:pool of scheduling solutions

//輸出調(diào)度解集合

1. initializepop-size

//初始化種群規(guī)模

//生成隨機(jī)解作為初始解

3. add the solutions to solution pool

//將解添加至解集合

4. whilepop-size>0

//若種群規(guī)模大于0

5. select random solutionΦifrom solution pool

//從解集合中選擇隨機(jī)解Φi

6. call on-wall collision operation(Φi)

//在解Φi上進(jìn)行分子的墻壁碰撞操作

7. call algorithm 1(Φ’)

//計(jì)算新生成的新分子Φ’的適應(yīng)度

8. ifEΦ’≤D

Costanza等人 [2]對(duì)全球生態(tài)系統(tǒng)服務(wù)價(jià)值（Ecosystem Services Value,ESV）進(jìn)行了定量估算，其研究成果使生態(tài)系統(tǒng)服務(wù)價(jià)值評(píng)估的原理和方法從科學(xué)意義上得以明確。謝高地等人根據(jù)中國(guó)的實(shí)際情況，制定了中國(guó)陸地生態(tài)系統(tǒng)單位面積生態(tài)服務(wù)價(jià)值，考慮到蘇州市的具體情況，確定蘇州各類型土地的生態(tài)服務(wù)價(jià)值系數(shù)（表1）。根據(jù)謝高地等人的方法計(jì)算蘇州市生態(tài)系統(tǒng)服務(wù)價(jià)值，其公式為：

//若適應(yīng)度值小于等于截止時(shí)間

9. add SOto solution pool

//將該分子解添加至解集合

10. end if

11. select randomΦifrom solution pool

//從解集合中選擇地隨機(jī)解Φi

12. call decomposition collision operation (Φi)

//在解Φi上進(jìn)行分子分解操作

13. call algorithm 1(Φ’)

//計(jì)算新生成的新分子Φ’的適應(yīng)度

14. ifEΦ’≤D

//若適應(yīng)度值小于等于截止時(shí)間

15. addΦ’ to solution pool

//將該分子解添加至解集合

16. end if

17. select randomSifrom solution pool

//從解集合中選擇隨機(jī)解Si

18. call inter-molecular ineffective collision operation(Φi)

//在解Φi上進(jìn)行分子碰撞操作

19. call algorithm 1(Φ’)

//計(jì)算新生成的新分子Φ’的適應(yīng)度

20. ifEΦ’≤D

//若適應(yīng)度值小于等于截止時(shí)間

21. addSoto solution pool

//將其添加至解集合

22. end if

23. select randomΦifrom solution pool

//從解集中隨機(jī)地選擇一個(gè)解Φi

24. call synthesis collision operationΦi

//調(diào)用分子合成操作

25. call algorithm 1(Φ’)

//計(jì)算新分子的適應(yīng)度

26. ifEΦ’≤D

//若適應(yīng)度小于等于截止時(shí)間約束

27. addΦ’ to solution pool

//添加至解集合

28. end if

29.pop-size=pop-size-1

//更新種群規(guī)模

30. end while

31. return sol_pool

//返回調(diào)度解的候選集合

2.2 蟻群優(yōu)化機(jī)制

蟻群優(yōu)化機(jī)制ACO是受螞蟻種群在其巢穴與食物源之間尋找最短行進(jìn)路徑的啟發(fā)得到的，蟻群個(gè)體間通過(guò)沿途釋放的信息素取得聯(lián)系。螞蟻通過(guò)計(jì)算概率P來(lái)選擇路徑行進(jìn)，而P則依賴于路徑上的信息素量。當(dāng)任一路徑上的信息素增加時(shí)，選擇該條路徑的蟻群數(shù)量也相應(yīng)增加。因此，每個(gè)新解將優(yōu)于前解。利用蟻群算法進(jìn)一步優(yōu)化調(diào)度解的優(yōu)勢(shì)在于：利用正反饋機(jī)制，使得螞蟻的搜索尋優(yōu)過(guò)程不斷收斂，最終逼近最優(yōu)解；搜索過(guò)程是分布式的，多個(gè)個(gè)體同時(shí)計(jì)算，極大提高搜索能力和運(yùn)行效率；其啟發(fā)式的概率搜索方式不會(huì)導(dǎo)致搜索過(guò)程陷入局部最優(yōu)，易于找到全局調(diào)度最優(yōu)解。

算法3是ACO的具體過(guò)程。

算法3改進(jìn)的蟻群算法過(guò)程Modified ACO

1. assignyants onmVMsaccording to the initial CRO solution//根據(jù)初始CRO的解分配y個(gè)螞蟻到m個(gè)虛擬機(jī)上，以此

//對(duì)螞蟻?zhàn)鞒跏蓟僮?/p>

2. initializeτivfor each path betweentiandVMv

//將ti與VMv間的每條路徑τiv進(jìn)行初始化

3. while tasks-list is not empty repeat

//若任務(wù)隊(duì)列非空

4. fork=0 toy

//在所有螞蟻上循環(huán)執(zhí)行

//根據(jù)概率螞蟻k為所選擇任務(wù)ti選擇合適的VMv

6. insertVMvin Tabukand remove it form allowedk

//將VMv插入Tabuk，并從allowk中移除VMv

7. remove the selected_Task from Task_list

//從任務(wù)隊(duì)列中移除所選任務(wù)

8. update local pheromone

//更新局部信息素

9. end for

10. end while

11. return a new solution

//返回新的解

12. update global pheromone

//更新全局信息素

1) 信息素初始化。當(dāng)任務(wù)i調(diào)度至虛擬機(jī)v時(shí)，即可以生成一條信息素量為τiv的新路徑。利用CRO，ACO根據(jù)與初始解相同的順序?qū)⒚總€(gè)螞蟻調(diào)度至一個(gè)具體的VM上，然后，對(duì)第i條邊上的信息素進(jìn)行初始化：

(4)

2) 下一任務(wù)的虛擬機(jī)選擇。每個(gè)螞蟻在特定輪次r中利用概率P(由式(5)定義)為下一個(gè)任務(wù)ti選擇虛擬機(jī)VMv。基于螞蟻的適應(yīng)度函數(shù)，ACO在為任務(wù)選擇虛擬機(jī)VM時(shí)將以更低的代價(jià)為依據(jù)。

(5)

式中：τiv表示任務(wù)ti調(diào)度到VMv的信息素;allowedk表示仍未被選擇的螞蟻中antk的可用虛擬機(jī)。同時(shí)，該過(guò)程中被選擇的虛擬機(jī)被存儲(chǔ)在Tabuk中。另外，定義螞蟻尋優(yōu)過(guò)程中的啟發(fā)信息：

(6)

式中：代表輪次r時(shí)antk的能見度，P(ti,VMv)為任務(wù)ti調(diào)度至VMv的代價(jià)。由于任務(wù)在不同虛擬機(jī)上執(zhí)行時(shí)間和代價(jià)具有很大不同，利用γ調(diào)節(jié)對(duì)于執(zhí)行時(shí)間和執(zhí)行代價(jià)的優(yōu)化偏好。若用戶偏好執(zhí)行代價(jià)，則1-γ將大于γ。

3) 信息素更新。在螞蟻創(chuàng)建路徑后，更新每條路徑上的信息素：

(7)

式中：Tk(r)表示輪次r時(shí)的Tabuk，Tabuk即為antk已經(jīng)訪問(wèn)過(guò)的虛擬機(jī)集合;Lk(r)表示antk代表的調(diào)度長(zhǎng)度與執(zhí)行代價(jià)之和；Q表示控制參數(shù)。在產(chǎn)生新解之后，全局信息素更新為：

τiv(r+1)=(1-ρ)τiv(r)+Δτiv(r)

(8)

2.3 算法步驟

CRO-ACO由CRO和ACO融合組成，可以以更低的時(shí)間復(fù)雜度及更快的速度得到低代價(jià)的工作流調(diào)度解。同時(shí)，算法在設(shè)計(jì)過(guò)程中對(duì)原始的CRO和ACO進(jìn)行相關(guān)改進(jìn)，使其能夠擁有更高的搜索效率和求解性能。

首先，本文設(shè)計(jì)的CRO-ACO通過(guò)減少傳統(tǒng)CRO的步驟，從而以更低的時(shí)間復(fù)雜度來(lái)搜索解空間。其次，利用相同次數(shù)的四種化學(xué)反應(yīng)操作使得生成的分子具有更好的多樣性。同時(shí)，CRO-ACO設(shè)計(jì)的適應(yīng)度函數(shù)直接可用于判定工作流調(diào)度問(wèn)題的可行解，優(yōu)于傳統(tǒng)CRO中與多參數(shù)關(guān)聯(lián)的適應(yīng)度設(shè)計(jì)機(jī)制。

此外，CRO-ACO也改進(jìn)了傳統(tǒng)ACO以獲取更高質(zhì)量的調(diào)度解。傳統(tǒng)的ACO始于一個(gè)隨機(jī)化初始解，然后通過(guò)迭代不斷改進(jìn)得到近似最優(yōu)解或到達(dá)最大輪次為止。該策略具有以下不足：1) 隨機(jī)化的初始種群生成方法使得ACO需要迭代很長(zhǎng)時(shí)間才能找到近似最優(yōu)解；2) 傳統(tǒng)ACO通過(guò)計(jì)算一個(gè)概率值將所選任務(wù)分配至一個(gè)虛擬機(jī)，而概率值依賴于隨機(jī)初始種群的信息素以及所選任務(wù)被調(diào)度的執(zhí)行時(shí)間，導(dǎo)致算法在短期內(nèi)不可能得到一個(gè)較優(yōu)解；3) 提供了過(guò)多的重復(fù)解，使得下一輪次的解較前一輪次的改進(jìn)幅度不大。CRO-ACO中所應(yīng)用的蟻群優(yōu)化機(jī)制則避免了以上不足。

CRO-ACO由兩個(gè)部分組成，如算法4所示。第一個(gè)部分中，步驟1-步驟2使得算法利用修改的CRO選擇代價(jià)最低的十個(gè)最優(yōu)候選調(diào)度解。算法將初始的最優(yōu)化存儲(chǔ)在Good_list中，即通過(guò)這一階段的改進(jìn)化學(xué)反應(yīng)優(yōu)化機(jī)制CRO可以快速地尋找近似最優(yōu)解。第二部分，算法利用修改的ACO在Good_list列表中所存儲(chǔ)的每個(gè)解上迭代r次(步驟3-步驟17)，以通過(guò)式(6)修改的P值得到每個(gè)任務(wù)的最小執(zhí)行代價(jià)。即通過(guò)這一階段的蟻群優(yōu)化機(jī)制ACO可以進(jìn)一步改進(jìn)調(diào)度解的質(zhì)量，進(jìn)而得到全局最優(yōu)解。不同于傳統(tǒng)ACO，CRO-ACO可以搜索更大的解空間，而不僅僅是近似最優(yōu)解。同時(shí)，依據(jù)適應(yīng)度函數(shù)，算法還可以實(shí)現(xiàn)在執(zhí)行時(shí)間與執(zhí)行代價(jià)間的均衡。

算法4化學(xué)反應(yīng)優(yōu)化與蟻群優(yōu)化融合調(diào)度算法CRO-ACO

輸出:an cloud workflow DAG

//輸工作流DAG結(jié)構(gòu)

輸入:final scheduling solution

//輸出最優(yōu)調(diào)度解

1. call algorithm 2

//調(diào)用執(zhí)行修正的CRO

2. select the best ten solutions from pol_sol and store them into Good_list

//從解集中選擇最優(yōu)的十個(gè)調(diào)度解存入Good_list隊(duì)列

3. initialize r

//對(duì)迭代輪次進(jìn)行初始化操作

4. put count=10

//設(shè)置計(jì)數(shù)器的計(jì)數(shù)

5. while count>0

//若計(jì)數(shù)器的計(jì)數(shù)大于0

6. selectSifrom Good_list

//從Good_list中選擇輸入解Si

7. whiler>0

//若此時(shí)輪次大于0

8.r=r-1

//更新當(dāng)前算法迭代輪次

9. call algorithm 3(Si)

//在解Si調(diào)用修正的蟻群算法

10. call algorithm 1(S0)

//計(jì)算輸出解So的適應(yīng)度

11. if SL(S0)≤D

//若解S0的適應(yīng)度小于等于截止時(shí)間

12.Si=S0

//更新原始輸入解

13. else

14. addSito Final_list and go to step 17

//添加Si至最終解中并轉(zhuǎn)至步驟17

15. end if

16. end while

17.count=count-1

//更新計(jì)數(shù)器的計(jì)數(shù)

18. end while

19. return the solution with lowest cost and lowest makespan

//返回具有最小代價(jià)和最小執(zhí)行時(shí)間的調(diào)度解

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)配置

利用經(jīng)典的云環(huán)境仿真工具包CloudSim[10]進(jìn)行算法測(cè)試，從而評(píng)估CRO-ACO的性能，實(shí)驗(yàn)配置中利用目前的四種較經(jīng)典科學(xué)工作流模型作為DAG結(jié)構(gòu)，包括：Montage工作流，LIGO工作流，Epigenomics工作流，CyberShake工作流[11]。這四種科學(xué)工作流由于其應(yīng)用領(lǐng)域與計(jì)算特征的不同，均包含著不同的結(jié)構(gòu)特征，具體結(jié)構(gòu)如圖7所示。Montage工作流任務(wù)偏好于I/O密集型任務(wù)，對(duì)CPU計(jì)算能力要求較低，主要應(yīng)用于天文學(xué)領(lǐng)域；LIGO工作流任務(wù)偏好于計(jì)算密集型任務(wù)，是物理學(xué)引力波領(lǐng)域的工作流形式；Epigenomics工作流任務(wù)以計(jì)算密集型為主，且對(duì)內(nèi)存要求較多，是信息生物領(lǐng)域的工作流形式；CyberShake工作流任務(wù)以數(shù)據(jù)密集型為主，且對(duì)計(jì)算能力和內(nèi)存存儲(chǔ)均有較高要求，是地震學(xué)領(lǐng)域的工作流形式。四種工作流結(jié)構(gòu)代表著完全不同的計(jì)算任務(wù)類型，通過(guò)這種多類型工作流的測(cè)試可以觀察算法在適應(yīng)不同任務(wù)類型下的魯棒性，進(jìn)而論證算法是有效可行的。

圖7 工作流的結(jié)構(gòu)特征和任務(wù)分布

虛擬機(jī)相關(guān)參數(shù)參考亞馬遜的Amazon EC2[12]給的虛擬機(jī)參數(shù)配置，仿真實(shí)驗(yàn)中配置五種類型虛擬機(jī)，具體參數(shù)如表2所示。其中，ECU衡量的是CPU的計(jì)算能力，一個(gè)ECU相當(dāng)于1.2 GHz的CPU計(jì)算能力，虛擬機(jī)的性能變化參考文獻(xiàn)[13]進(jìn)行建模，以此給出異構(gòu)的任務(wù)執(zhí)行環(huán)境。五種虛擬機(jī)類型所能提供的內(nèi)存數(shù)量、計(jì)算單元量、內(nèi)核數(shù)量、資源利用的價(jià)格均不相同，這樣可以體現(xiàn)任務(wù)調(diào)度時(shí)選擇資源的差異性。

表2 VMs類型

對(duì)于CRO-ACO的初始參數(shù)設(shè)置如下：初始種群規(guī)模pop-size=50，螞蟻數(shù)量y=30，揮發(fā)因子ρ=0.5，τc=0.3，迭代輪次r=10。使用同類型的幾種工作流調(diào)度算法進(jìn)行性能比較，包括：傳統(tǒng)的化學(xué)反應(yīng)優(yōu)化算法CRO[14]，傳動(dòng)的蟻群算法ACO[15]，基于遺傳操作的GA[16]，截止時(shí)間約束下云科學(xué)工作流調(diào)度PSO[17]。

為了測(cè)試算法性能，以一種靈活的方式改變工作流的截止時(shí)間約束從而觀察算法的適應(yīng)性。具體方法為：將所有工作流任務(wù)按序選擇最快的虛擬機(jī)進(jìn)行執(zhí)行，并計(jì)算最小執(zhí)行時(shí)間，以該執(zhí)行時(shí)間作為執(zhí)行截止時(shí)間的下限值。然后，通過(guò)一個(gè)約束因子改變實(shí)際截止時(shí)間。同時(shí)，在不同的約束因子設(shè)置下，設(shè)置兩種截止時(shí)間約束類型：硬約束和軟約束。截止時(shí)間的具體計(jì)算公式為：

DeadlineCRO-ACO=MHEFT×(1+δ)

(9)

式中：δ表示截止時(shí)間約束因子；MHEFT表示通過(guò)由經(jīng)典工作流算法調(diào)度算法HEFT[18]得到的最小執(zhí)行時(shí)間。若截止時(shí)間為硬約束，則設(shè)置0≤δ<1.2；若截止時(shí)間為軟約束，則設(shè)置1.2≤δ≤3.2。實(shí)驗(yàn)中約束因子δ值以步長(zhǎng)0.4遞增。動(dòng)態(tài)變化的約束因子的增長(zhǎng)可以在實(shí)驗(yàn)中觀察算法對(duì)于約束緊密程度的依賴性和適應(yīng)性，從而使算法能夠適應(yīng)不同的應(yīng)用場(chǎng)景。

3.2 實(shí)驗(yàn)分析

1) 對(duì)于截止時(shí)間滿足度的性能評(píng)估。表3為不同算法對(duì)截止時(shí)間滿意度的情況，該滿意度描述的是所有在截止時(shí)間內(nèi)執(zhí)行的工作流占總體執(zhí)行量的比例。換言之，若該次工作流調(diào)度過(guò)程可以使得所有任務(wù)在截止時(shí)間以內(nèi)完成，則認(rèn)為是一種成功的工作流調(diào)度；否則，則認(rèn)為工作流調(diào)度失效。對(duì)于Montage的硬約束，CRO-ACO擁有高于CRO 92%的滿意度，對(duì)于CyberShake和LIGO，CRO-ACO優(yōu)于CRO88.5%，對(duì)于Epigenomics，CRO-ACO優(yōu)于CRO 84.5%。顯然，對(duì)于硬約束，CRO在每種工作流中均無(wú)法滿足截止時(shí)間約束，而CRO-ACO比CRO更優(yōu)。同樣地，對(duì)于其他三種工作流結(jié)構(gòu)，無(wú)論硬約束或軟約束，CRO-ACO均擁有比ACO、GA和PSO更高的約束滿意度。

表3 截止時(shí)間滿意度 %

此外，若截止時(shí)間為軟約束，CRO的性能是有所提高的，但綜合來(lái)看，無(wú)論是軟約束還是硬約束，CRO的性能均是較差的，主要原因是CRO忽略了云工作流中資源提供的動(dòng)態(tài)特征以及虛擬機(jī)性能的動(dòng)態(tài)變化。該算法也沒(méi)有考慮延時(shí)問(wèn)題，這對(duì)工作流的執(zhí)行時(shí)間有較大影響。CRO-ACO考慮了這些因素，可以通過(guò)化學(xué)反應(yīng)較快得到調(diào)度候選解，還可以通過(guò)蟻群優(yōu)化提高候選解的質(zhì)量，以確保在截止時(shí)間以內(nèi)得到執(zhí)行時(shí)間和執(zhí)行代價(jià)的同步最優(yōu)解。GA和ACO兩種算法在一定程度上忽略了虛擬機(jī)的性能變化，其調(diào)度方案并非最優(yōu)。PSO雖然也是智能優(yōu)化算法，但基于PSO的調(diào)度方案在進(jìn)行解的編碼時(shí)缺乏資源信息，可能導(dǎo)致因虛擬機(jī)性能的不同而違背截止時(shí)間約束。

2) 工作流的執(zhí)行時(shí)間和執(zhí)行代價(jià)的性能評(píng)估。圖8為算法的執(zhí)行時(shí)間情況，圖9為算法的執(zhí)行代價(jià)情況。同時(shí)，圖中在橫坐標(biāo)上的取值若小于或等于1.2，則截止時(shí)間約束對(duì)應(yīng)為硬約束；取值若大于1.2，則對(duì)應(yīng)為軟約束。可以看出，相比而言，傳統(tǒng)的CRO基本上在不同結(jié)構(gòu)類型的工作流中得到的執(zhí)行時(shí)間均是最長(zhǎng)的，同時(shí)其執(zhí)行代價(jià)也較小，算法很難滿足給定的工作流截止時(shí)間約束，導(dǎo)致其執(zhí)行代價(jià)小但也無(wú)法完成最優(yōu)化調(diào)度目標(biāo)，違背了約束。其他三種算法中，本文設(shè)計(jì)的CRO-ACO在Montage工作流中擁有比PSO約低9%的執(zhí)行時(shí)間，比ACO低23%，比GA低27%。對(duì)于LIGO，CRO-ACO的執(zhí)行時(shí)間比GA低21%，比PSO低44%，比ACO低42%。對(duì)于CyberShake，CRO-ACO的執(zhí)行時(shí)間比ACO低5%，比GA低25%，比PSO低16%。對(duì)于Epigenomics，CRO-ACO的執(zhí)行時(shí)間比PSO低19%，比ACO低45%，比GA低37%。同樣可以看出，CRO-ACO在執(zhí)行代價(jià)上也優(yōu)于其他算法。由此可見，同時(shí)考慮執(zhí)行時(shí)間和執(zhí)行代價(jià)的CRO-ACO在兩個(gè)指標(biāo)間做到很好的平衡，并沒(méi)有為了僅僅優(yōu)化執(zhí)行代價(jià)指標(biāo)而一味增加任務(wù)的執(zhí)行時(shí)間，這利于算法通過(guò)融合化學(xué)反應(yīng)優(yōu)化和蟻群優(yōu)化機(jī)制的兩階段求解方法，使得同步考慮效率與代價(jià)因素的適應(yīng)度在兩階段中進(jìn)一步降低，所得到的任務(wù)調(diào)度解也進(jìn)一步接近于全局最優(yōu)解。

圖8 執(zhí)行時(shí)間

圖9 執(zhí)行代價(jià)

綜合以上實(shí)驗(yàn)中得到的對(duì)于截止時(shí)間的滿意度情況、執(zhí)行代價(jià)和執(zhí)行時(shí)間情況等實(shí)驗(yàn)結(jié)果，可以看出，本文設(shè)計(jì)的CRO-ACO可以在盡可能高的截止時(shí)間滿意度下降低執(zhí)行代價(jià)和執(zhí)行時(shí)間。雖然無(wú)法在兩個(gè)指標(biāo)上均達(dá)到最優(yōu)，但在硬約束條件下，CRO-ACO在四種工作流結(jié)構(gòu)中均擁有最高的約束滿意度且更低的執(zhí)行代價(jià)。而截止時(shí)間約束相對(duì)寬松后(軟約束下)，本文算法可以同時(shí)降低執(zhí)行時(shí)間和執(zhí)行代價(jià)。

4 結(jié) 語(yǔ)

為了解決云計(jì)算環(huán)境中科學(xué)工作流的調(diào)度優(yōu)化問(wèn)題，本文提出一種基于化學(xué)反應(yīng)優(yōu)化與蟻群優(yōu)化融合的工作流調(diào)度算法。在傳統(tǒng)化學(xué)反應(yīng)優(yōu)化的基礎(chǔ)上，設(shè)計(jì)四種分子化學(xué)反應(yīng)操作，不僅增加種群分子的多樣性，還能以較快的速度獲得調(diào)度問(wèn)題的候選解。為了提高前一化學(xué)反應(yīng)優(yōu)化階段中調(diào)度解的質(zhì)量，利用修正的蟻群優(yōu)化機(jī)制對(duì)調(diào)度解進(jìn)行精煉。通過(guò)兩種優(yōu)化機(jī)制的融合最終得到在截止時(shí)間約束時(shí)工作流調(diào)度問(wèn)題的最優(yōu)解。最后，通過(guò)構(gòu)建四種不同類型的科學(xué)工作流進(jìn)行仿真測(cè)試。結(jié)果表明，工作流調(diào)度算法在截止時(shí)間約束滿意度、降低執(zhí)行時(shí)間和執(zhí)行代價(jià)方面均優(yōu)于其他算法。未來(lái)的研究方向可以圍繞工作流的執(zhí)行能耗和安全可靠等因素展開，進(jìn)一步設(shè)計(jì)整合以上目標(biāo)的工作流調(diào)度算法，使云計(jì)算環(huán)境中的工作流調(diào)度問(wèn)題更加地貼近現(xiàn)實(shí)云環(huán)境，并對(duì)其可行性和有效性給出數(shù)據(jù)驗(yàn)證。