基于化學反應優化與蟻群優化融合的云工作流調度

胡紅宇 陳 政

1(永州職業技術學院計算機系 湖南 永州 425000) 2(湖南工學院計算機與信息計算學院 湖南 衡陽 421001)

0 引 言

工作流模型廣泛應用于大規模科學計算領域中的問題建模，如天文學領域、地球科學領域、天體物理學領域、生物信息學等領域[1]。工作流的結構包含多個任務節點和有向邊，能以典型的有向無循環圖DAG的形式來建立表達模型。工作流結構中的頂點即為科學計算任務，有向邊給出計算任務間的順序關系，即明確給出兩個任務間的執行次序。科學工作流規模大、任務量多、結構較復雜，而云計算這種靈活按需的提供模式則為其提供了一種更高效的運行環境。云計算以按需方式向用戶提供服務[2]，其服務類型包括軟件即服務SaaS、基礎設施即服務IaaS、平臺即服務PaaS。基礎設施即服務的IaaS云計算環境以虛擬機形式提供硬件資源，更加適用于科學工作流調度問題的執行環境[3-4]。

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

綜合以上的分析可以看出，云環境中工作流調度無法滿足用戶給定的期限時間約束，或者在進行任務調度時無法選擇最優的虛擬機類型，從而導致過高的資源利用代價。同時，有一些研究考慮的環境比較單一化，所能調度的任務類型具有一定的特定性，無法滿足不同結構類型的任務的調度需求與調度適應性。為了解決這一問題，本文提出一種滿足截止時間約束基于化學反應優化機制和蟻群優化機制融合的工作流調度算法CRO-ACO。通過結合CRO尋優快速和ACO在提高解質量上的優勢，以盡可能高的約束滿意度來得到工作流任務的調度方案，從而實現云工作流在執行時間與執行代價上的均衡優化目標，最后通過幾種典型工作流結構作為數據源對算法性能進行分析。

1 系統模型

1.1 云計算模型

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

本文所討論的云計算模型為亞馬遜的彈性計算Amazon EC2中按需模式提供的IaaS云模型。該模型可以提供虛擬化式的計算資源、存儲資源和網絡帶寬資源，對物理底層資源的復雜性實現透明化操作。運用模型中的云計算，用戶可以根據其應用需求進行添加或釋放虛擬機實例類型。假設所有的存儲服務和計算資源均處于相同的數據中心中。因此，在虛擬機間的高速數據傳輸與其提供的帶寬是對等的。對于異構虛擬機構成的云資源系統模型，每一種可用的虛擬機類型均可以作為任務調度的選擇目標，并基于虛擬機的處理能力和資源占用狀態進行任務調度目標的優化與映射求解。

1.2 應用模型

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

圖1為一個高斯應用的DAG結構圖，由9個任務構成，計算代價矩陣如表1所示，表明每個任務在三個不同虛擬機上的執行代價。DAG中邊上的權值代表任務間的數據傳輸量，即邊權重Cweight(ti,tk)。邊e(ti,tk)的通信代價C(ti,tk)則為兩個任務ti和tk間傳輸數據所花的時間，表示為：

(1)

式中：B為平均帶寬。當兩個任務調度到相同的虛擬機上時，由于虛擬機內的通信網絡是極高速網絡，因此兩個任務間的通信代價可以忽略不計，表示為e(i,k)=0。

任務ti在虛擬機VMj上的執行時間為ET(ti,VMj)，計算為：

(2)

式中：MI表示任務ti的指令執行數量，即百萬指令數；MIPS表示虛擬機VMj的每秒執行的百萬指令數。

任務ti在虛擬機VMj上的開始時間TST定義為：

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

C(ti,tk)}}

式中：Timavail(VMj)表示虛擬機VMj開始執行一個新任務的就緒時間；FFT(tk)表示任務tk的最終完成時間(tk是ti的父節點任務，k=1,2,…,n)。任務ti在虛擬機VMj上的完成時間TFT可表示為TFT(ti,VMj)，計算為：

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

(3)

圖1 一個高斯應用的DAG示例

表1 計算代價矩陣

2 算法設計

本節提出一種新的兩階段混合算法實現云計算中的工作流調度算法CRO-ACO，平衡可用云資源上的負載，在不違背截止時間約束的前提下最小化調度時間。第一階段通過應用化學反應優化機制CRO快速地尋找近似最優解，第二階段通過應用蟻群優化機制ACO進一步改進調度解的質量，進而得到全局最優解。兩階段的優化機制使得本文算法可以充分利用CRO的低時間復雜度和ACO對于候選解質量的改進。

2.1 化學反應優化機制

化學反應優化機制CRO模擬了在封閉容器中的分子之間以及分子與容器內壁之間進行的一系列化學反應過程，每一次反應均會產生一個或兩個新的分子。每個分子擁有唯一的結構，代表一個解Φ。化學反應優化機制的優勢在于可以通過分子的墻壁碰撞、分子的分解、分子間碰撞、分子的合成四個步驟快速找到任務調度方案的近似最優解，得到充分擴展的解空間，為后續對于解的進一步篩選和優化生成較為多樣和優異的種群個體。

調度過程中，一個分子由兩個原子集合組成，第一個集合α代表DAG任務，第二個集合β代表分配至集合α中的任務的虛擬機的集合，圖2為一個分子結構示例，即一個調度解，給出一種任務與虛擬機集合間的映射情形。

圖2 一個分子Φ

每個分子表現出的特征為解的勢能E(適應度函數f(S)=EΦ)和動能K。CRO利用動能K和勢能E代表是否接收或拒絕一個新生成的分子代表的解。然而，計算每個分子的動能K的時間復雜度較高，本文算法將簡化該過程，僅利用E值來評估新生成的分子解的質量。算法1給出計算適應度值E(即工作流調度長度)以評估是否接受新解Φ的過程。

算法1適應度計算

輸入:solution S with scheduling queue

//輸入調度隊列中的調度解

輸出:makespan

//輸出工作流的執行時間

1. add all atoms/tasks inTQaccording to solutionΦ

//根據解Φ將所有原子/任務添加至任務隊列TQ

2. addVMsinVMQaccording to solutionΦ

//根據解Φ將虛擬機添加至虛擬機隊列VMQ

3. whileTQis not empty

//若TQ非空

4. selecttifromTQand the correspondingVMifromVMQ

//選擇TQ中的任務ti與VMQ中的VMi進行映射

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

//根據解Φ計算TFT

6. removetifromTQ

//從TQ中移除任務ti

7. removeVMifromVMQ

//從VMQ中移除VMi

8. end while

9. return fitness valueSL=EΦ

//返回適應度值

算法1中，根據當前解Φ，所有任務被放入一個任務隊列TQ中，對應的VMs以相同的順序被放入虛擬機隊列VMQ中。此時，TQ中任一任務ti調度至隊列VMQ的VMi上。算法1計算每個任務的完成時間TFT直到獲得葉子任務的完成時間為止，最終，返回葉子任務的TFT作為工作流的調度長度。

CRO中，分子總共經過四種化學反應：墻壁碰撞、分解、分子間碰撞、合成。

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

圖3 墻壁碰撞示例

利用分子墻壁碰撞后即可得到一個新的分子Φ’，然后，化學反應優化CRO計算新生成分子勢能適應度EΦ’。如果滿足EΦ’≤D，D為工作流執行的截止時間，則算法接受新分子Φ’并將其存儲在候選調度解集中；否則，將丟棄新分子。

2) 分解。與分子的墻壁碰撞過程類似，分子分解也是基于單分子的反應過程。然而，分子分解反應的結果是產生兩個分子Φ1’和Φ2’。新分子的產生過程如下：(1) 算法隨機選擇兩個數i和j，i

圖4 分子分解示例

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

圖5 分子間碰撞示例

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

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

圖6 分子合成示例

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

算法2改進的化學反應優化算法過程Modified CRO

輸入:workflow tasks andVMlist//以有向無環圖的形式輸入

//工作流各個任務以及待分配的虛擬機列表

輸出:pool of scheduling solutions

//輸出調度解集合

1. initializepop-size

//初始化種群規模

//生成隨機解作為初始解

3. add the solutions to solution pool

//將解添加至解集合

4. whilepop-size>0

//若種群規模大于0

5. select random solutionΦifrom solution pool

//從解集合中選擇隨機解Φi

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

//在解Φi上進行分子的墻壁碰撞操作

7. call algorithm 1(Φ’)

//計算新生成的新分子Φ’的適應度

8. ifEΦ’≤D

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

//若適應度值小于等于截止時間

9. add SOto solution pool

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

10. end if

11. select randomΦifrom solution pool

//從解集合中選擇地隨機解Φi

12. call decomposition collision operation (Φi)

//在解Φi上進行分子分解操作

13. call algorithm 1(Φ’)

//計算新生成的新分子Φ’的適應度

14. ifEΦ’≤D

//若適應度值小于等于截止時間

15. addΦ’ to solution pool

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

16. end if

17. select randomSifrom solution pool

//從解集合中選擇隨機解Si

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

//在解Φi上進行分子碰撞操作

19. call algorithm 1(Φ’)

//計算新生成的新分子Φ’的適應度

20. ifEΦ’≤D

//若適應度值小于等于截止時間

21. addSoto solution pool

//將其添加至解集合

22. end if

23. select randomΦifrom solution pool

//從解集中隨機地選擇一個解Φi

24. call synthesis collision operationΦi

//調用分子合成操作

25. call algorithm 1(Φ’)

//計算新分子的適應度

26. ifEΦ’≤D

//若適應度小于等于截止時間約束

27. addΦ’ to solution pool

//添加至解集合

28. end if

29.pop-size=pop-size-1

//更新種群規模

30. end while

31. return sol_pool

//返回調度解的候選集合

2.2 蟻群優化機制

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

算法3是ACO的具體過程。

算法3改進的蟻群算法過程Modified ACO

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

//對螞蟻作初始化操作

2. initializeτivfor each path betweentiandVMv

//將ti與VMv間的每條路徑τiv進行初始化

3. while tasks-list is not empty repeat

//若任務隊列非空

4. fork=0 toy

//在所有螞蟻上循環執行

//根據概率螞蟻k為所選擇任務ti選擇合適的VMv

6. insertVMvin Tabukand remove it form allowedk

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

7. remove the selected_Task from Task_list

//從任務隊列中移除所選任務

8. update local pheromone

//更新局部信息素

9. end for

10. end while

11. return a new solution

//返回新的解

12. update global pheromone

//更新全局信息素

1) 信息素初始化。當任務i調度至虛擬機v時，即可以生成一條信息素量為τiv的新路徑。利用CRO，ACO根據與初始解相同的順序將每個螞蟻調度至一個具體的VM上，然后，對第i條邊上的信息素進行初始化：

(4)

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

(5)

式中：τiv表示任務ti調度到VMv的信息素;allowedk表示仍未被選擇的螞蟻中antk的可用虛擬機。同時，該過程中被選擇的虛擬機被存儲在Tabuk中。另外，定義螞蟻尋優過程中的啟發信息：

(6)

式中：代表輪次r時antk的能見度，P(ti,VMv)為任務ti調度至VMv的代價。由于任務在不同虛擬機上執行時間和代價具有很大不同，利用γ調節對于執行時間和執行代價的優化偏好。若用戶偏好執行代價，則1-γ將大于γ。

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

(7)

式中：Tk(r)表示輪次r時的Tabuk，Tabuk即為antk已經訪問過的虛擬機集合;Lk(r)表示antk代表的調度長度與執行代價之和；Q表示控制參數。在產生新解之后，全局信息素更新為：

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

(8)

2.3 算法步驟

CRO-ACO由CRO和ACO融合組成，可以以更低的時間復雜度及更快的速度得到低代價的工作流調度解。同時，算法在設計過程中對原始的CRO和ACO進行相關改進，使其能夠擁有更高的搜索效率和求解性能。

首先，本文設計的CRO-ACO通過減少傳統CRO的步驟，從而以更低的時間復雜度來搜索解空間。其次，利用相同次數的四種化學反應操作使得生成的分子具有更好的多樣性。同時，CRO-ACO設計的適應度函數直接可用于判定工作流調度問題的可行解，優于傳統CRO中與多參數關聯的適應度設計機制。

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

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

算法4化學反應優化與蟻群優化融合調度算法CRO-ACO

輸出:an cloud workflow DAG

//輸工作流DAG結構

輸入:final scheduling solution

//輸出最優調度解

1. call algorithm 2

//調用執行修正的CRO

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

//從解集中選擇最優的十個調度解存入Good_list隊列

3. initialize r

//對迭代輪次進行初始化操作

4. put count=10

//設置計數器的計數

5. while count>0

//若計數器的計數大于0

6. selectSifrom Good_list

//從Good_list中選擇輸入解Si

7. whiler>0

//若此時輪次大于0

8.r=r-1

//更新當前算法迭代輪次

9. call algorithm 3(Si)

//在解Si調用修正的蟻群算法

10. call algorithm 1(S0)

//計算輸出解So的適應度

11. if SL(S0)≤D

//若解S0的適應度小于等于截止時間

12.Si=S0

//更新原始輸入解

13. else

14. addSito Final_list and go to step 17

//添加Si至最終解中并轉至步驟17

15. end if

16. end while

17.count=count-1

//更新計數器的計數

18. end while

19. return the solution with lowest cost and lowest makespan

//返回具有最小代價和最小執行時間的調度解

3 仿真實驗

3.1 實驗配置

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

圖7 工作流的結構特征和任務分布

虛擬機相關參數參考亞馬遜的Amazon EC2[12]給的虛擬機參數配置，仿真實驗中配置五種類型虛擬機，具體參數如表2所示。其中，ECU衡量的是CPU的計算能力，一個ECU相當于1.2 GHz的CPU計算能力，虛擬機的性能變化參考文獻[13]進行建模，以此給出異構的任務執行環境。五種虛擬機類型所能提供的內存數量、計算單元量、內核數量、資源利用的價格均不相同，這樣可以體現任務調度時選擇資源的差異性。

表2 VMs類型

對于CRO-ACO的初始參數設置如下：初始種群規模pop-size=50，螞蟻數量y=30，揮發因子ρ=0.5，τc=0.3，迭代輪次r=10。使用同類型的幾種工作流調度算法進行性能比較，包括：傳統的化學反應優化算法CRO[14]，傳動的蟻群算法ACO[15]，基于遺傳操作的GA[16]，截止時間約束下云科學工作流調度PSO[17]。

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

DeadlineCRO-ACO=MHEFT×(1+δ)

(9)

式中：δ表示截止時間約束因子；MHEFT表示通過由經典工作流算法調度算法HEFT[18]得到的最小執行時間。若截止時間為硬約束，則設置0≤δ<1.2；若截止時間為軟約束，則設置1.2≤δ≤3.2。實驗中約束因子δ值以步長0.4遞增。動態變化的約束因子的增長可以在實驗中觀察算法對于約束緊密程度的依賴性和適應性，從而使算法能夠適應不同的應用場景。

3.2 實驗分析

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

表3 截止時間滿意度 %

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

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

圖8 執行時間

圖9 執行代價

綜合以上實驗中得到的對于截止時間的滿意度情況、執行代價和執行時間情況等實驗結果，可以看出，本文設計的CRO-ACO可以在盡可能高的截止時間滿意度下降低執行代價和執行時間。雖然無法在兩個指標上均達到最優，但在硬約束條件下，CRO-ACO在四種工作流結構中均擁有最高的約束滿意度且更低的執行代價。而截止時間約束相對寬松后(軟約束下)，本文算法可以同時降低執行時間和執行代價。

4 結 語

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