多云環(huán)境下帶截止日期約束的科學(xué)工作流調(diào)度策略

林兵，郭文忠，陳國(guó)龍

?

多云環(huán)境下帶截止日期約束的科學(xué)工作流調(diào)度策略

林兵1,2,3，郭文忠2,3,4，陳國(guó)龍2,3

（1. 福建師范大學(xué)物理與能源學(xué)院，福建 福州 350117；2. 福建省網(wǎng)絡(luò)計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室（福州大學(xué)），福建 福州 350116；3. 空間數(shù)據(jù)挖掘與信息共享教育部重點(diǎn)實(shí)驗(yàn)室，福建 福州 350003；4. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350116）

針對(duì)多云環(huán)境下帶截止日期約束的科學(xué)工作流調(diào)度問題，提出一種基于遺傳算法操作的自適應(yīng)離散粒子群優(yōu)化算法（ADPSOGA），目的是在盡可能滿足工作流截止日期前提下，減少其執(zhí)行代價(jià)。該方法考慮多云之間的通信代價(jià)、虛擬機(jī)的啟動(dòng)和關(guān)閉時(shí)間以及多云之間不同的帶寬通信波動(dòng)；為了避免傳統(tǒng)粒子群優(yōu)化算法（PSO, particle swarm optimization）存在的過早收斂問題，引入遺傳算法的隨機(jī)兩點(diǎn)交叉操作和隨機(jī)單點(diǎn)變異操作，有效提高種群進(jìn)化過程中的多樣性；在充分考慮數(shù)據(jù)通信代價(jià)和任務(wù)計(jì)算代價(jià)的情況下，設(shè)計(jì)一種基于工作流截止日期約束的代價(jià)驅(qū)動(dòng)調(diào)度策略。實(shí)驗(yàn)結(jié)果表明，ADPSOGA在波動(dòng)因素存在情況下，對(duì)工作流截止日期滿足和執(zhí)行代價(jià)控制方面具有良好的性能表現(xiàn)。

云計(jì)算；截止日期約束；工作流調(diào)度；波動(dòng)性

1 引言

隨著云計(jì)算技術(shù)[1]的不斷發(fā)展，當(dāng)前云市場(chǎng)上出現(xiàn)多個(gè)云服務(wù)提供商共存的“多云”局面[2]。云計(jì)算彈性供應(yīng)虛擬資源并按需付費(fèi)的性質(zhì)，為處理大規(guī)?？茖W(xué)工作流（以下簡(jiǎn)稱工作流）提供便利[3]。然而，云異構(gòu)環(huán)境下的任務(wù)調(diào)度是一個(gè)NP-hard問題[4]，工作流自身的子任務(wù)之間存在復(fù)雜的時(shí)間依賴和數(shù)據(jù)依賴關(guān)系，且多個(gè)云服務(wù)提供商之間存在諸多差異（如要價(jià)機(jī)制、實(shí)例類型、通信帶寬等），因此，需要一種合適的調(diào)度策略在盡可能滿足工作流服務(wù)質(zhì)量（QoS, quality of service）前提下，減少其執(zhí)行代價(jià)。當(dāng)前云環(huán)境下的工作流調(diào)度策略大多是在傳統(tǒng)分布式計(jì)算環(huán)境（如網(wǎng)格）的工作流調(diào)度算法基礎(chǔ)上做一些改進(jìn)，未考慮云環(huán)境自身特性[3,5,6]，或一些調(diào)度策略僅考慮在靜態(tài)單一云環(huán)境中，單純追求執(zhí)行時(shí)間最小化目標(biāo)，未對(duì)帶約束的工作流（如截止日期）的代價(jià)優(yōu)化調(diào)度問題展開研究[7,8]。

關(guān)于多云環(huán)境存在波動(dòng)因素的帶截止日期約束工作流的代價(jià)驅(qū)動(dòng)調(diào)度問題，目前國(guó)內(nèi)外還未有相關(guān)研究工作。而其中最具相關(guān)性的研究工作是關(guān)于單云環(huán)境存在波動(dòng)因素的基于截止日期約束的工作流調(diào)度研究[1]，該工作利用傳統(tǒng)粒子群優(yōu)化（PSO, particle swarm optimization）調(diào)度策略來(lái)處理全局的工作流子任務(wù)調(diào)度方案。受到文獻(xiàn)[1]的啟發(fā)，提出一種基于遺傳算法操作的自適應(yīng)離散粒子群優(yōu)化算法（ADPSOGA, adaptive discrete particle swarm optimization with genetic algorithm），主要研究的問題及思路包括3個(gè)部分：首先，該方法考慮多云環(huán)境下更多的基本要素，如多云之間的數(shù)據(jù)通信代價(jià)、虛擬機(jī)的啟停時(shí)間以及多云之間的差異化帶寬通信速率，同時(shí)還考慮虛擬機(jī)的性能波動(dòng)和帶寬通信波動(dòng)；其次，為了避免傳統(tǒng)PSO存在的過早收斂問題，引入遺傳算法的隨機(jī)兩點(diǎn)交叉操作和隨機(jī)單點(diǎn)變異操作，有效提高種群進(jìn)化過程中的多樣性；最后，在充分考慮數(shù)據(jù)通信代價(jià)和工作流子任務(wù)計(jì)算代價(jià)的前提下，設(shè)計(jì)一種基于工作流截止日期約束的代價(jià)驅(qū)動(dòng)調(diào)度策略。

2 相關(guān)工作

近年來(lái)，傳統(tǒng)分布式環(huán)境下的工作流調(diào)度已得到廣泛研究。網(wǎng)格環(huán)境下調(diào)度工作流的目標(biāo)通常是最小化工作流執(zhí)行時(shí)間。Chen等[9]設(shè)計(jì)一種網(wǎng)格環(huán)境下基于蟻群優(yōu)化（ACO, ant colony optimization）的工作流調(diào)度方法，其目的是優(yōu)化工作流執(zhí)行時(shí)間，同時(shí)滿足其QoS需求。Cao等[10]提出基于鏈表調(diào)度和組調(diào)度的工作流調(diào)度算法，該方法可以有效降低工作流執(zhí)行時(shí)間，并提高網(wǎng)格環(huán)境下的資源利用率。Higashino等[11]提出基于PSO和遺傳算法（GA, genetic algorithm）的混合工作流調(diào)度策略，實(shí)驗(yàn)表明該方法在執(zhí)行時(shí)間優(yōu)化方面效果明顯。另外，部分研究工作在調(diào)度策略中考慮工作流執(zhí)行代價(jià)因素。苑迎春等[12]基于逆向分層思想，將截止日期約束轉(zhuǎn)化為層截止約束，在滿足約束前提下大幅度降低工作流執(zhí)行代價(jià)。Abrishami等[13]提出網(wǎng)格環(huán)境下基于局部關(guān)鍵路徑（PCP, partial critical path）的代價(jià)驅(qū)動(dòng)工作流調(diào)度策略，實(shí)驗(yàn)表明該方法能夠在滿足截止日期約束前提下降低工作流執(zhí)行代價(jià)。Khajemohammadi等[14]設(shè)計(jì)一種基于遺傳算法的多目標(biāo)工作流調(diào)度策略，通過分層工作流模型達(dá)到同時(shí)優(yōu)化執(zhí)行時(shí)間和執(zhí)行代價(jià)的目標(biāo)。

上述方法為網(wǎng)格環(huán)境下工作流調(diào)度的機(jī)遇和挑戰(zhàn)提供寶貴經(jīng)驗(yàn)。然而，云計(jì)算環(huán)境和網(wǎng)格環(huán)境在資源供應(yīng)和資源要價(jià)機(jī)制上存在巨大差異[1]。沈虹等[15]提出云環(huán)境下帶準(zhǔn)備時(shí)間和截止日期約束的代價(jià)驅(qū)動(dòng)工作流調(diào)度算法，實(shí)驗(yàn)表明該算法可以在合理的CPU時(shí)間內(nèi)減少工作流執(zhí)行代價(jià)。Malawski等[3]提出調(diào)度工作流組的動(dòng)態(tài)和靜態(tài)算法，其目的是在滿足預(yù)算和截止日期雙約束的前提下提高工作流組的完成率。該工作提到虛擬機(jī)需要一定時(shí)間來(lái)啟動(dòng)工作，然而其僅考慮一種虛擬機(jī)類型，不符合現(xiàn)實(shí)云環(huán)境。肖鵬等[16]在經(jīng)典的CPOP算法和HEFT算法基礎(chǔ)上，引入啟發(fā)式策略并設(shè)計(jì)2種工作流能耗感知調(diào)度算法CPOP-MECP和HEFT-MECP，目的是降低工作流子任務(wù)之間的數(shù)據(jù)訪問能耗開銷。Mao等[17]提出一種動(dòng)態(tài)的工作流組調(diào)度方案，基于按需付費(fèi)模式優(yōu)化工作流組的總執(zhí)行代價(jià)，該工作考慮多種虛擬機(jī)類型，然而該方案對(duì)于代價(jià)優(yōu)化的單一工作流調(diào)度并不適用。部分研究工作引入PSO指導(dǎo)云環(huán)境下的工作流調(diào)度問題，并取得良好效果。Wu等[5]提出基于PSO的單一工作流調(diào)度方案，他們分別針對(duì)截止日期約束的代價(jià)優(yōu)化問題和預(yù)算約束的執(zhí)行時(shí)間優(yōu)化問題展開研究，該工作的虛擬機(jī)類型和數(shù)量是固定的，不符合云環(huán)境彈性供應(yīng)性質(zhì)。Pandey等[18]設(shè)計(jì)一種基于離散PSO的優(yōu)化求解單一工作流調(diào)度執(zhí)行代價(jià)問題，該工作同樣忽略云環(huán)境資源彈性提供的性質(zhì)。以上云環(huán)境下的工作流調(diào)度工作均考慮單個(gè)云服務(wù)提供商，未對(duì)多云環(huán)境展開研究。

多云協(xié)同計(jì)算的定義由Keahey等[19]提出。而Fard等[2]提出一種同時(shí)優(yōu)化執(zhí)行時(shí)間和執(zhí)行代價(jià)的多云環(huán)境下工作流調(diào)度策略，他們雖然考慮虛擬資源的彈性供應(yīng)，但忽略虛擬資源的異質(zhì)性，僅考慮一種虛擬機(jī)類型。之前研究工作中[20]提出多云環(huán)境下帶截止日期約束的代價(jià)驅(qū)動(dòng)工作流調(diào)度策略，該策略引入局部關(guān)鍵路徑理論，對(duì)工作流的子任務(wù)進(jìn)行局部整體分配，達(dá)到壓縮數(shù)據(jù)通信、減少執(zhí)行代價(jià)的目的，然而該策略并未考慮波動(dòng)因素對(duì)調(diào)度結(jié)果帶來(lái)的干擾，同時(shí)該工作忽略云間的數(shù)據(jù)通信代價(jià)和實(shí)例啟停時(shí)間等因素。

云環(huán)境下關(guān)于科學(xué)工作流調(diào)度的相關(guān)工作分析如表1所示。其主要分成6類：設(shè)施環(huán)境、應(yīng)用類型、環(huán)境波動(dòng)性、目標(biāo)、限制條件和方法。其中，設(shè)施環(huán)境包括單云和多云環(huán)境，應(yīng)用類型包括作業(yè)、單工作流和工作流組，環(huán)境波動(dòng)性包括靜態(tài)和動(dòng)態(tài)，目標(biāo)分為代價(jià)和時(shí)間要求，限制條件包括截止日期和預(yù)算約束，方法主要包括數(shù)學(xué)規(guī)劃、啟發(fā)式和元啟發(fā)式。表1中的“+”代表存在該性質(zhì)，“?”代表不存在該性質(zhì)。

3 問題定義

工作流調(diào)度模型框架如圖1所示，它主要包括工作流、多云環(huán)境以及代價(jià)驅(qū)動(dòng)調(diào)度器。

工作流是用有向無(wú)環(huán)圖(,)來(lái)表示，其中，表示包含個(gè)任務(wù)的頂點(diǎn)集合{1,2,…,t}，而則表示任務(wù)之間數(shù)據(jù)依賴關(guān)系{12,13,…,e}。每條數(shù)據(jù)依賴邊e=(t,t)代表任務(wù)t和任務(wù)t之間存在數(shù)據(jù)依賴關(guān)系，其中，任務(wù)t是任務(wù)t的直接先驅(qū)（父）節(jié)點(diǎn)，而任務(wù)t則是任務(wù)t的直接后繼（子）節(jié)點(diǎn)。在工作流調(diào)度過程中，一個(gè)任務(wù)必須在其所有先驅(qū)節(jié)點(diǎn)都已被執(zhí)行完畢后，才能開始執(zhí)行。在某個(gè)給定的代表工作流的有向無(wú)環(huán)圖中，把沒有先驅(qū)節(jié)點(diǎn)的任務(wù)稱為“入任務(wù)”，同理，把沒有后繼節(jié)點(diǎn)的任務(wù)稱為“出任務(wù)”。每個(gè)工作流都有一個(gè)對(duì)應(yīng)的截止日期()，當(dāng)某個(gè)調(diào)度策略能夠在對(duì)應(yīng)截止日期前執(zhí)行完成該工作流，則稱其為一種可行解。

表1 云環(huán)境下關(guān)于科學(xué)工作流調(diào)度的相關(guān)工作分析

圖1 工作流調(diào)度模型

多云環(huán)境中存在多個(gè)云服務(wù)提供商={,,…,}，服務(wù)提供商提供多種虛擬機(jī)實(shí)例類型S={s1,s2,…,s}。每種類型的虛擬機(jī)實(shí)例都有其特定的計(jì)算能力和存儲(chǔ)能力，假設(shè)虛擬機(jī)在執(zhí)行子任務(wù)過程中有足夠的存儲(chǔ)空間來(lái)存儲(chǔ)傳輸數(shù)據(jù)[17]，因此，本文主要關(guān)注虛擬機(jī)計(jì)算能力（即CPU數(shù)量）。子任務(wù)t在虛擬機(jī)vm上的估計(jì)執(zhí)行時(shí)間為(t,vm)，給定任務(wù)在不同類型虛擬機(jī)上的執(zhí)行性價(jià)比不同。

同一個(gè)云服務(wù)提供商的基礎(chǔ)設(shè)施通常都集中在較小區(qū)域內(nèi)，而不同云服務(wù)提供商的基礎(chǔ)設(shè)施則相距較遠(yuǎn)[2]，因此，假設(shè)單云的云內(nèi)帶寬要快于不同云之間的云間帶寬。云服務(wù)提供商內(nèi)，數(shù)據(jù)從子任務(wù)t傳輸?shù)阶尤蝿?wù)t的云內(nèi)通信時(shí)間為intra(e,)，而數(shù)據(jù)在云服務(wù)提供商和之間的通信時(shí)間為，如式(1)和式(2)所示。

其中，(e)是子任務(wù)t傳輸?shù)阶尤蝿?wù)t的數(shù)據(jù)量大小，intra()是云的云內(nèi)帶寬，而inter(,)則是云和云之間的云間帶寬。假設(shè)單個(gè)虛擬機(jī)上的帶寬無(wú)窮大[8]，因此，當(dāng)2個(gè)子任務(wù)被分配到同一臺(tái)虛擬機(jī)上執(zhí)行時(shí)，intra(e,)的值為0。

不同云之間的數(shù)據(jù)通信代價(jià)將會(huì)影響到最終的調(diào)度決策[16]，c,q表示從云通信1 GB的數(shù)據(jù)量到云所需的單價(jià)。不考慮資源監(jiān)控、數(shù)據(jù)存儲(chǔ)和負(fù)載均衡等業(yè)務(wù)產(chǎn)生的代價(jià)，因?yàn)檫@些代價(jià)與計(jì)算代價(jià)或數(shù)據(jù)通信代價(jià)相比可以忽略不計(jì)[3]。

代價(jià)調(diào)度器的目的是在滿足截止日期約束的前提下，最小化工作流執(zhí)行代價(jià)。調(diào)度器的輸入包括工作流信息（結(jié)構(gòu)、數(shù)據(jù)、依賴等）和多云環(huán)境信息（虛擬機(jī)、帶寬、要價(jià)等），其輸出是對(duì)應(yīng)的調(diào)度方案。整個(gè)調(diào)度方案的定義為=(,,total,total)，其中，表示一組需要啟用的虛擬機(jī)資源，={1,2,…,vm}，={(t,vm)|t∈,vm∈}表示工作流中子任務(wù)對(duì)應(yīng)虛擬機(jī)資源的映射關(guān)系，total表示工作流的執(zhí)行完成時(shí)間，而total則表示工作流總執(zhí)行代價(jià)。每臺(tái)虛擬機(jī)都有對(duì)應(yīng)的虛擬機(jī)類型s以及對(duì)應(yīng)的開啟時(shí)刻(vm)和關(guān)閉時(shí)刻(vm)。當(dāng)子任務(wù)被調(diào)度完成后，都有一組對(duì)應(yīng)的實(shí)際執(zhí)行開始時(shí)間(t)和實(shí)際執(zhí)行完成時(shí)間(t)，且“出任務(wù)”不會(huì)再產(chǎn)生并通信數(shù)據(jù)。因此，工作流執(zhí)行完成時(shí)間total和對(duì)應(yīng)的總執(zhí)行代價(jià)total分別如式(3)和式(4)所示。

其中，式(4)的前半部分表示虛擬機(jī)的執(zhí)行代價(jià)，后半部分表示數(shù)據(jù)通信代價(jià)。子任務(wù)t是子任務(wù)t的后繼節(jié)點(diǎn)，(t)和(t)分別表示執(zhí)行t和t的服務(wù)提供商。當(dāng)t和t由同一個(gè)云服務(wù)提供商執(zhí)行時(shí)，s為0（即不產(chǎn)生云間數(shù)據(jù)通信），否則，s為1。

基于以上相關(guān)定義，多云環(huán)境下帶截止日期約束的工作流調(diào)度問題，可形式化表示為式(5)，其核心思想是在追求執(zhí)行代價(jià)total最低的同時(shí)，使執(zhí)行時(shí)間total小于或等于工作流截止日期()。

4 ADPSOGA調(diào)度策略

本節(jié)首先介紹基礎(chǔ)PSO，然后具體介紹ADPSOGA調(diào)度策略。

4.1 PSO

PSO是一種基于鳥群社會(huì)行為的動(dòng)物進(jìn)化計(jì)算技術(shù)，它是在1995年由Kennedy等[22]提出的。粒子在PSO中尤為重要，每個(gè)粒子代表優(yōu)化問題的候選解，它們可以在整個(gè)問題空間范圍內(nèi)移動(dòng)。每個(gè)粒子以某種速度移動(dòng)更新自己的移動(dòng)方向，該速度受粒子自身情況、粒子自身最佳歷史位置以及整個(gè)種群的歷史最佳位置這3個(gè)方面影響。為了判斷每個(gè)粒子在問題空間中的不同位置所產(chǎn)生解的優(yōu)劣性，引入適應(yīng)度函數(shù)來(lái)評(píng)估每個(gè)粒子的解質(zhì)量。每個(gè)粒子是由它自身的位置和速度決定，它們根據(jù)周圍粒子和自身的經(jīng)驗(yàn)在問題搜索空間中不斷迭代更新調(diào)整自己的位置和速度。其中，速度根據(jù)式(6)進(jìn)行更新，位置根據(jù)式(7)進(jìn)行更新。

4.2 ADPSOGA

從以下7個(gè)部分具體闡述ADPSOGA。

4.2.1 問題編碼

提高算法搜索效率和性能，需要一種好的編碼方式。編碼策略的評(píng)價(jià)標(biāo)準(zhǔn)主要考慮其健全性、完備性和非冗余性3個(gè)基本原則[23]。

定義1 健全性。編碼空間中的某個(gè)編碼粒子，必須對(duì)應(yīng)問題空間中的某個(gè)潛在問題優(yōu)化解。

定義2 完備性。問題空間中的全部可行解，都能在編碼空間中被相應(yīng)的粒子表現(xiàn)出來(lái)。

定義3 非冗余性。問題空間中的潛在解，只能和編碼空間中的相關(guān)粒子一一對(duì)應(yīng)。

其中，(,s,vm)表示該子任務(wù)被分配到云中實(shí)例類型是s的第個(gè)具體實(shí)例上。粒子上的每一個(gè)節(jié)點(diǎn)位被嵌套劃分成3個(gè)小分位，分別表示云服務(wù)提供商、實(shí)例類型和具體實(shí)例，因此，編碼空間大小是子任務(wù)數(shù)量的3倍。初始化種群時(shí)，粒子的節(jié)點(diǎn)小分位各自隨機(jī)初始化為0到其對(duì)應(yīng)最大值之間的整數(shù)值。圖2展示調(diào)度包含8個(gè)子任務(wù)工作流的粒子編碼策略，其中假設(shè)多云環(huán)境包含3個(gè)云服務(wù)提供商，且每個(gè)云服務(wù)提供商均提供8種實(shí)例類型。因此，坐標(biāo)值是從0~2，s坐標(biāo)值是從0~7。由圖2可知，子任務(wù)1被分配給云第0個(gè)云中類型是00的虛擬機(jī)000。

圖2 粒子編碼

性質(zhì)1 云提供商—實(shí)例類型—具體實(shí)例的嵌套離散編碼方式滿足編碼完備性和非冗余性基本原則，但不滿足編碼的健全性基本原則。

粒子的每個(gè)編碼分位代表對(duì)應(yīng)子任務(wù)的分配位置，滿足完備性原則。不同編碼粒子分別代表不同調(diào)度方案，問題空間的某個(gè)可行解只與編碼空間的一個(gè)編碼粒子對(duì)應(yīng)，因此，滿足非冗余性原則。部分粒子存在對(duì)應(yīng)問題空間中不可行解情況，例如，調(diào)度方案超過工作流截止日期，因此，不滿足健全性原則。

4.2.2 初始化資源池

多云環(huán)境資源的彈性供應(yīng)模式，導(dǎo)致算法無(wú)法得到初始資源集合。對(duì)于PSO而言，初始化資源池的大小將決定搜索空間的范圍，對(duì)算法復(fù)雜度以及工作流執(zhí)行性能起著關(guān)鍵作用。當(dāng)初始化資源池太小時(shí)，會(huì)出現(xiàn)本可以在截止日期前完成的工作流，由于資源的缺乏而無(wú)法及時(shí)完成。當(dāng)初始化資源池太大時(shí)，PSO編碼的潛在解過于龐大，使算法無(wú)法及時(shí)收斂。一種簡(jiǎn)單可行的初始化資源分配方案，是為每個(gè)子任務(wù)分配多云環(huán)境中所有類別的虛擬機(jī)各一臺(tái)，這樣可以保證搜索空間的多樣性和完整性。然而，這種方案的初始化資源池intial的大小為·Num(vm)，搜索空間比較大，增加算法復(fù)雜度。其中，為工作流中的子任務(wù)數(shù)量，Num(vm)為所有云服務(wù)提供商的實(shí)例類型數(shù)量總和，其定義為

其中，Num(p)為云服務(wù)提供商所提供的實(shí)例類型數(shù)量。

為進(jìn)一步壓縮搜索空間，同時(shí)保持原有潛在解的多樣性，設(shè)計(jì)初始化資源池intial的大小是|S(w)|Num(vm)，其中，S(w)是工作流中的最大可并行子任務(wù)集合。由于除了S(w)中的子任務(wù)外，其他子任務(wù)都會(huì)和S(w)中的子任務(wù)存在直接和間接的依賴關(guān)系，所以該初始化資源策略可以保證每個(gè)子任務(wù)都有選擇一種類型實(shí)例的機(jī)會(huì)，從而保證潛在解的多樣性，同時(shí)降低搜索空間。

4.2.3 適應(yīng)度函數(shù)

粒子的適應(yīng)度函數(shù)是用來(lái)評(píng)價(jià)2個(gè)相比較粒子的優(yōu)劣性，通常較小的適應(yīng)度函數(shù)值對(duì)應(yīng)的粒子較優(yōu)。由于前期的粒子編碼策略不滿足健全性原則，即會(huì)出現(xiàn)工作流的執(zhí)行時(shí)間超過對(duì)應(yīng)截止日期，所以需要對(duì)可行解和超過截止日期的不可行解的適應(yīng)度函數(shù)區(qū)分定義。判斷2個(gè)粒子優(yōu)劣的適應(yīng)度函數(shù)分3種不同情況定義。

情況1一個(gè)粒子是可行解，另一個(gè)粒子是不可行解。毫無(wú)爭(zhēng)議地選擇可行解，其適應(yīng)度值定義為

情況2 2個(gè)粒子都是可行解。選擇執(zhí)行代價(jià)較低的粒子，其適應(yīng)度值定義為

情況3 2個(gè)粒子都是不可行解。選擇執(zhí)行時(shí)間較小的粒子，因?yàn)樵摿Ｗ舆M(jìn)化后更有可能變?yōu)榭尚薪?。其適應(yīng)度值定義為

4.2.4 粒子的更新策略

如式(6)所示，PSO包括3個(gè)核心部分：慣性部分、個(gè)體認(rèn)知部分和社會(huì)認(rèn)知部分。為克服傳統(tǒng)PSO存在的過早收斂缺陷，ADPSOGA引入遺傳算法的變異和交叉操作，對(duì)式(6)中相應(yīng)部分進(jìn)行更新操作。粒子在時(shí)刻的更新方式為

其中，M()表示變異操作，C()和C()表示交叉操作。

式(6)中的慣性部分結(jié)合遺傳算法中變異操作思想，慣性部分的更新方式為

其中，1為0~1的隨機(jī)數(shù)。M()隨機(jī)選取粒子中的一個(gè)分位，不規(guī)律改變其分位值，且新值必須都在對(duì)應(yīng)的閾值內(nèi)。

圖3為對(duì)圖2編碼粒子的變異操作，隨機(jī)選擇粒子的一個(gè)分位mp1，mp1位置上的值由(0,1,2)更新為(1,2,0)，該變異符合調(diào)度準(zhǔn)則。

圖3 慣性部分的變異操作

式(6)中的個(gè)體認(rèn)知和社會(huì)認(rèn)知部分結(jié)合遺傳算法交叉操作思想，其更新結(jié)果分別如式(16)和式(17)所示。

其中，2和3為0~1的隨機(jī)數(shù)，C()（或C()）隨機(jī)選擇粒子的2個(gè)分位，將分位之間的數(shù)值與對(duì)應(yīng)（或）分位之間的數(shù)值進(jìn)行交叉。

圖4為個(gè)人（或社會(huì)）認(rèn)知部分的交叉操作，隨機(jī)產(chǎn)生2個(gè)交叉位置（即cp1和cp2），將粒子cp1和cp2位置之間的值替換為（或）在該區(qū)間的值。

圖4 個(gè)人（或社會(huì)）認(rèn)知部分的交叉操作

4.2.5 粒子到調(diào)度結(jié)果的映射

編碼粒子到調(diào)度結(jié)果的映射如算法1所示。

算法1 編碼粒子到調(diào)度結(jié)果的映射

procedure Schedule_Generation(,intial,)

1) 初始化:←,←,total← 0,total← 0

2) 計(jì)算[||×|intial|]

3) 計(jì)算intra[||×||],inter[||×||, ||×||]

4) for= 0 to= ||?1

5)t=[],r(i)=R[()]

6) ift為真實(shí)入任務(wù)then

7) ifr(i)未啟動(dòng)then

8) 啟動(dòng)r(i),r(i)=boot(r(i)),(r(i)) = LETr(i)?boot(r(i))

9) end if

10)STt=r(i)

11) else

12) 調(diào)用max(t)過程, max= max(t)

13) ifr(i)未啟動(dòng)then

14) 啟動(dòng)r(i),r(i)=max(max,boot(r(i))),

(r(i)) = LETr(i)?boot(r(i))

15) end if

16)STt=max(max, r(i))

17) end if

18)=[][()]

19) for each childtoftdo

20) ift被調(diào)度到與t同一個(gè)云中，但不同的虛擬機(jī)上then

21)+=intra[][]

22) else ift被調(diào)度到與t不同的云中 then

23)+=inter[i][c]

24) end if

25) end for

26)ETt= STt + exe

27)=∪(t,r(i),STt,ETt)

28) ifr(i)?then

29)=∪{ r(i)}

30) end if

31)r(i)=r(i)

32) end for

33)根據(jù)式(3)和式(4)分別計(jì)算total和total

34)輸出調(diào)度方案及其對(duì)應(yīng)結(jié)果= (,,total,total)

算法1的輸入包括工作流、初始化資源池intial和編碼粒子。首先，對(duì)調(diào)度方案=(,,total,total)的四元素初始化（第1)行）。初始化后，計(jì)算每個(gè)子任務(wù)對(duì)應(yīng)不同類型實(shí)例的估計(jì)執(zhí)行時(shí)間矩陣[||×|intial|]，矩陣中的元素[][]表示子任務(wù)t在虛擬機(jī)mv上的估計(jì)執(zhí)行時(shí)間（第2) 行）。計(jì)算子任務(wù)之間的數(shù)據(jù)量在單云和多云之間的估計(jì)通信時(shí)間，intra[][]表示單云中子任務(wù)t產(chǎn)生的數(shù)據(jù)量通信到子任務(wù)t所需的估計(jì)時(shí)間，inter[][][][]表示子任務(wù)t產(chǎn)生的數(shù)據(jù)量從云通信到云的子任務(wù)t所需的估計(jì)時(shí)間（第3)行）。

經(jīng)過以上操作，目前已得到從編碼粒子得到候選解的全部信息。逐步掃描粒子的各個(gè)分位，生成對(duì)應(yīng)的和集合?；凇皢栴}編碼”，粒子的編碼分位對(duì)應(yīng)子任務(wù)，分位的值對(duì)應(yīng)實(shí)例資源，因此，確定子任務(wù)t被分配到實(shí)例r(i)上（第5)行）。第6)~17)行是計(jì)算子任務(wù)t的估計(jì)開始時(shí)間STt，這里有2種情況。

1) 子任務(wù)t是真實(shí)入任務(wù)，即其沒有直接先驅(qū)子任務(wù)。當(dāng)虛擬機(jī)r(i)可用時(shí)，子任務(wù)t立刻開始執(zhí)行，其估計(jì)開始時(shí)間STt為虛擬機(jī)r(i)的已租賃時(shí)間LETr(i)。另外，需要判斷虛擬機(jī)r(i)是否已開啟，如果未開啟，則需要啟動(dòng)虛擬機(jī)，虛擬機(jī)的已租賃時(shí)間LETr(i)即虛擬機(jī)的初始化時(shí)間boot(r(i))。

2) 子任務(wù)t不是入任務(wù)，即其有一個(gè)或多個(gè)父任務(wù)。子任務(wù)t不但需要等待資源空閑時(shí)才可執(zhí)行，還得等待其所有父任務(wù)執(zhí)行完成，并將產(chǎn)生數(shù)據(jù)通信到虛擬機(jī)r(i)上才可執(zhí)行。調(diào)用max_(t)過程計(jì)算子任務(wù)t等待時(shí)間和數(shù)據(jù)通信代價(jià)，同時(shí)考慮虛擬機(jī)r(i)是否已被啟動(dòng)。

計(jì)算完子任務(wù)t的估計(jì)開始時(shí)間STt，需要根據(jù)其在虛擬機(jī)上的估計(jì)執(zhí)行時(shí)間和數(shù)據(jù)通信時(shí)間，來(lái)計(jì)算子任務(wù)t的估計(jì)結(jié)束時(shí)間ETt（第18)~26)行）。對(duì)于數(shù)據(jù)通信時(shí)間的計(jì)算，需要根據(jù)其后輩子任務(wù)t是否與子任務(wù)t分配在同一個(gè)云中來(lái)確定，這里有3種情況。

1)t與t在同一臺(tái)虛擬機(jī)上執(zhí)行，則通信時(shí)間為0。

2)t與t在同一個(gè)云中但不同虛擬機(jī)上執(zhí)行，則通信時(shí)間為intra[][]。

3)t與t分別在不同云（如云和云）上執(zhí)行，則通信時(shí)間為inter[i][c]。

子任務(wù)t調(diào)度到虛擬機(jī)r(i)，其開始時(shí)間STt和結(jié)束時(shí)間ETt等四元素的映射關(guān)系添加到集合中（第27)行）。隨后判斷虛擬機(jī)r(i)是否已被添加到租賃資源中，如果未被添加，則進(jìn)行添加（第28)~30)行）。虛擬機(jī)r(i)的最新已租賃時(shí)間，等于子任務(wù)t的估計(jì)完成時(shí)間（第31)行）。最后，根據(jù)式(3)和式(4)分別計(jì)算工作流的總執(zhí)行時(shí)間和總執(zhí)行代價(jià)。輸出編碼粒子對(duì)應(yīng)的調(diào)度方案。子任務(wù)的等待時(shí)間和通信代價(jià)如算法2所示。

算法2 子任務(wù)的等待時(shí)間和通信代價(jià)

procedure max_(t)

1) 初始化：wait← 0,tranfer← 0

2) for each parenttoftdo

3) ift被調(diào)度到與t同一個(gè)云中，但不同的虛擬機(jī)上then

4)wait=max(wait,intra[][])

5) else ift被調(diào)度到與t不同的云中 then

6)wait=max(wait,inter[p][i] )

7)tranfer+=(e)c,p

8) end if

9) end for

10) 輸出最長(zhǎng)等待時(shí)間wait, 通信代價(jià)tranfer

首先，初始化等待時(shí)間wait和數(shù)據(jù)通信代價(jià)tranfer（第1)行）。子任務(wù)t等待時(shí)間等于其所有父任務(wù)中最大的數(shù)據(jù)通信時(shí)間（第3)~6)行）。當(dāng)子任務(wù)t和其父任務(wù)t分配到不同云中時(shí)，才考慮數(shù)據(jù)通信代價(jià)（第7)行）。

4.2.6 參數(shù)設(shè)置

式(6)的慣性權(quán)重因子能夠決定PSO的收斂性和搜索能力[4]。當(dāng)較小時(shí)，算法具有較強(qiáng)的局部搜索能力；否則，算法具有較強(qiáng)的全局搜索能力。在算法執(zhí)行初期，更注重問題空間搜索的多樣性和粒子全局搜索能力，隨著搜索深入，后期則更加注重局部搜索方面的能力。因此，慣性權(quán)重因子的權(quán)值應(yīng)隨著算法迭代次數(shù)的增多而逐漸減少。式(18)是經(jīng)典的慣性權(quán)重因子調(diào)整策略。

其中，max和min分別是初始化時(shí)設(shè)定的最大值和最小值，cur和max分別表示當(dāng)前算法迭代次數(shù)和初始化設(shè)定的最大迭代次數(shù)。

以上的經(jīng)典慣性權(quán)重因子調(diào)整策略，的變化僅和迭代次數(shù)有關(guān)，不能很好地滿足實(shí)際問題的非線性和復(fù)雜多變特性。慣性權(quán)重因子的權(quán)值大小應(yīng)該隨著種群粒子的進(jìn)化而不斷演變，因此，構(gòu)建一種根據(jù)當(dāng)前種群粒子的優(yōu)劣而自適應(yīng)調(diào)整的慣性權(quán)重因子調(diào)整策略。如式(19)所示，該策略基于當(dāng)前粒子與全局歷史最優(yōu)粒子之間的差異程度來(lái)調(diào)整慣性權(quán)重因子大小。

其中，(X?1,gBest?1)表示粒子X?1和全局歷史最優(yōu)粒子gBest?1之間的不同分位的位數(shù)大小，是工作流中子任務(wù)的個(gè)數(shù)大小。當(dāng)(X?1)值較小時(shí)，表示粒子X?1和gBest?1之間差異程度較小，所以應(yīng)該減小的權(quán)值，以保證粒子可在小范圍內(nèi)更好搜索，找到優(yōu)化解；否則，應(yīng)該增加的權(quán)值，使粒子的搜索空間變大，以便更快找到優(yōu)化解空間。因此，慣性權(quán)重因子的權(quán)值計(jì)算式更新為

另外，算法的2個(gè)認(rèn)知因子1和2采用線性增減策略進(jìn)行設(shè)置[24]。其更新方式如式(21)和式(22)所示。

其中，1_start和2_start分別表示參數(shù)1和2迭代的初始值，1_end和2_end分別表示參數(shù)1和2迭代的最終值。

4.2.7 算法流程

ADPSOGA流程如圖5所示，具體步驟如下。

步驟1 初始化ADPSOGA中種群大小、最大迭代次數(shù)、慣性權(quán)重因子和認(rèn)知因子等參數(shù)的數(shù)值，隨機(jī)生成初始種群。

步驟2 根據(jù)第4.2.5節(jié)的粒子映射策略以及式(11)~式(13)計(jì)算各個(gè)粒子不同情況下的適應(yīng)度值，從中選擇適應(yīng)度值最小的粒子作為種群全局最優(yōu)粒子，將第一代中每個(gè)粒子設(shè)置為其自身歷史最優(yōu)粒子。

步驟3 根據(jù)粒子更新式(14)~式(17)更新粒子。

步驟4 重新計(jì)算每個(gè)粒子的適應(yīng)度值，若當(dāng)前粒子的適應(yīng)度值小于其自身歷史最優(yōu)值，則將新粒子更新為其自身歷史最優(yōu)粒子。

圖5 ADPSOGA流程

步驟5 若當(dāng)前粒子的適應(yīng)度值小于種群全局最優(yōu)粒子的適應(yīng)度值，則將該粒子更新為種群全局最優(yōu)粒子。

步驟6 檢查是否滿足算法終止條件，如果滿足，則算法終止；反之，轉(zhuǎn)到步驟3。

5 實(shí)驗(yàn)仿真與結(jié)果

本文的模擬實(shí)驗(yàn)是在64位Windows 7系統(tǒng)環(huán)境下，其配置是8 GB內(nèi)存和2.30 GHz的i7 Intel處理器?；谖墨I(xiàn)[24]，ADPSOGA的參數(shù)設(shè)置如下。種群大小為100，最大迭代次數(shù)為1 000，1_start= 0.9，1_end= 0.2，2_start =0.4，2_end =0.9。

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

工作流測(cè)試樣例采用Bharathi等[25]研究的來(lái)自5個(gè)不同科學(xué)領(lǐng)域的工作流：天文學(xué)（Montage）、地震科學(xué)（CyberShake）、生物基因?qū)W（Epigenomics）、重力物理學(xué)（LIGO）以及生物信息學(xué)（SIPHT）。這些工作流具有不同結(jié)構(gòu)，它們的信息（如子任務(wù)大小、數(shù)據(jù)通信量和依賴關(guān)系等）被存儲(chǔ)在xml格式的文件中。對(duì)于每種工作流，選取其中3個(gè)數(shù)量級(jí)：小型（約30個(gè)任務(wù)），偏小型（約50個(gè)任務(wù)）和中型（約100個(gè)任務(wù)）。由于子任務(wù)在具體實(shí)例上的執(zhí)行時(shí)間存在波動(dòng)，因此，假設(shè)工作流子任務(wù)的大小呈正態(tài)分布，其變化率區(qū)間為(?10%,10%)[1]。

基于Amazon服務(wù)帶寬[20]，假設(shè)單云的云內(nèi)帶寬為20 Mbit/s。不同云之間的通信代價(jià)如表2所示，這些數(shù)值是通過帶寬測(cè)試工具iperf測(cè)試得到，主要針對(duì)Amazon EC2的悉尼區(qū)域(C1)、Rackspace(C2)和GoGrid(C3)。

表2 不同云之間的通信代價(jià)

假設(shè)帶寬大小變化率滿足最大減少19%、均值減少9.5%、標(biāo)準(zhǔn)差為5%的正態(tài)分布[1]。另外，假設(shè)虛擬機(jī)的初始化時(shí)間是97 s，要價(jià)區(qū)間是1 h[21]。表3是不同云之間的數(shù)據(jù)通信價(jià)格，該表數(shù)值來(lái)自各自云服務(wù)提供商的官方網(wǎng)站。

表3 不同云之間的數(shù)據(jù)通信價(jià)格（美元·GB?1）

每個(gè)工作流都有一個(gè)對(duì)應(yīng)的截止日期，以此來(lái)測(cè)試調(diào)度策略性能。選擇5個(gè)不同的截止日期D()來(lái)測(cè)試本文涉及的調(diào)度方法。

其中，()是用HEFT算法[26]調(diào)度工作流的執(zhí)行時(shí)間，r則是從集合{1.5, 2, 5, 8, 15}中依次取值。

5.2 對(duì)比算法

為了驗(yàn)證ADPSOGA調(diào)度策略的有效性，通過改寫文獻(xiàn)[20]的靜態(tài)MCPCPP調(diào)度策略和文獻(xiàn)[1]的WPSO調(diào)度策略，使它們適應(yīng)多云環(huán)境，并作為本文的對(duì)比算法。

MCPCPP調(diào)度策略是在靜態(tài)多云環(huán)境下，在滿足工作流截止日期前提下，追求執(zhí)行代價(jià)最低。該方法通過合并包含共同“割邊”的相鄰子任務(wù)，降低算法復(fù)雜度并減少數(shù)據(jù)通信時(shí)間；分配子截止日期到局部關(guān)鍵路徑上，并對(duì)局部關(guān)鍵路徑進(jìn)行整體調(diào)度，壓縮數(shù)據(jù)通信時(shí)間和代價(jià)；通過調(diào)度局部關(guān)鍵路徑到“最適合”實(shí)例上，進(jìn)一步減少工作流執(zhí)行代價(jià)。然而，該策略未考慮多云之間的數(shù)據(jù)通信代價(jià)，也忽視了實(shí)例啟停時(shí)間對(duì)調(diào)度結(jié)果的影響。因此，在對(duì)比試驗(yàn)中，MCPCPP調(diào)度策略同時(shí)考慮云間的數(shù)據(jù)通信代價(jià)和實(shí)例啟停時(shí)間。

WPSO調(diào)度策略是在單云環(huán)境下，在滿足工作流截止日期前提下，追求執(zhí)行代價(jià)最低。該方法利用傳統(tǒng)PSO的連續(xù)編碼方式，其子任務(wù)和實(shí)例的映射關(guān)系是通過選取編碼粒子的實(shí)數(shù)取整部分來(lái)實(shí)現(xiàn)，粒子更新方式是基于式(6)的傳統(tǒng)方式。為了和本文算法形成對(duì)比，WPSO經(jīng)過適當(dāng)改寫就可以適合多云環(huán)境的工作流調(diào)度。WPSO的總體框架和文獻(xiàn)[1]相同，但在考慮初始資源池時(shí)，需要考慮多云環(huán)境下的所有實(shí)例類型，另外，還需要考慮多云之間數(shù)據(jù)傳輸?shù)耐ㄐ糯鷥r(jià)，其慣性權(quán)重因子和認(rèn)知因子1、2的設(shè)置依然參照文獻(xiàn)[1]。

5.3 結(jié)果評(píng)價(jià)

為了測(cè)試ADPSOGA、MCPCPP和WPSO策略在多云環(huán)境存在波動(dòng)因素的工作流調(diào)度性能，對(duì)各種波動(dòng)因素的生成函數(shù)隨機(jī)取值，并對(duì)每種因素各進(jìn)行100組實(shí)驗(yàn)，綜合深入考察各個(gè)調(diào)度策略性能。

表4 ADPSOGA和WPSO在D1(w)達(dá)到gBest的迭代次數(shù)

表5 ADPSOGA和WPSO在D5(w)達(dá)到gBest的迭代次數(shù)

另外，由于測(cè)試的5個(gè)類型工作流的結(jié)構(gòu)和子任務(wù)大小存在差異，因此，需要對(duì)工作流執(zhí)行代價(jià)的結(jié)果進(jìn)行歸一化處理。引入工作流標(biāo)準(zhǔn)執(zhí)行代價(jià)()，如式(24)所示。

其中，()表示采用本文任何一種調(diào)度策略產(chǎn)生的工作流執(zhí)行代價(jià)，而()則表示利用不考慮截止日期約束的最廉價(jià)調(diào)度策略[6]所產(chǎn)生的工作流執(zhí)行代價(jià)。

表4和表5分別表示在100組重復(fù)測(cè)試中，ADPSOGA和WPSO這2種基于PSO的調(diào)度策略在1()和5()不同截止日期下，得到各自全局歷史最優(yōu)值的平均迭代次數(shù)。由表4和表5可知，隨著工作流子任務(wù)數(shù)量的增加，2種算法得到各自全局歷史最優(yōu)值的平均迭代次數(shù)均明顯增多。這主要是因?yàn)樽尤蝿?wù)數(shù)量的增加，使基于編碼策略的粒子維度增加，粒子更新過程中也產(chǎn)生更多的新粒子和更大種群規(guī)模，從而導(dǎo)致出現(xiàn)更多的候選解粒子，并擴(kuò)大問題域的搜索空間，使搜索到最佳解的迭代次數(shù)增多。隨著截止日期約束的變化，2種不同算法達(dá)到的平均迭代次數(shù)并未發(fā)生明顯改變，反而是不同調(diào)度策略之間在同等環(huán)境下的迭代次數(shù)存在明顯區(qū)別，這說明截止日期約束對(duì)迭代次數(shù)的影響并不顯著。同等條件下，ADPSOGA調(diào)度策略的平均迭代次數(shù)明顯高于WPSO調(diào)度策略。ADPSOGA調(diào)度策略的自適應(yīng)慣性權(quán)重因子和漸進(jìn)式增減認(rèn)知因子的設(shè)置，導(dǎo)致其編碼粒子更具有多樣性，在算法執(zhí)行初期更加注重問題空間的廣泛性搜索，而后期則傾向于對(duì)算法收斂性的關(guān)注，從而產(chǎn)生更佳的全局歷史最優(yōu)值。而WPSO調(diào)度策略主要采用連續(xù)的編碼和更新方式來(lái)解決工作流調(diào)度這個(gè)離散問題，這種編碼方式容易陷入局部最優(yōu)，從而過早收斂，導(dǎo)致產(chǎn)生的優(yōu)化結(jié)果并非最優(yōu)結(jié)果。

圖6是多云環(huán)境存在波動(dòng)因素的5種中型工作流在3種不同調(diào)度策略（即MCPCPP、ADPSOGA和WPSO）中的完成率。該完成率是指在相應(yīng)的100組測(cè)試中，工作流完成時(shí)間達(dá)到對(duì)應(yīng)截止日期約束要求的比例大小。從圖6中的5個(gè)子圖可以發(fā)現(xiàn)，隨著截止日期的增大，基于PSO的ADPSOGA和WPSO這2種調(diào)度策略的完成率都呈上升趨勢(shì)。特別在5()階段，除了CyberShake工作流，2種調(diào)度策略的完成率都達(dá)到了100%。MCPCPP調(diào)度策略的完成率明顯低于其他2種調(diào)度策略，其完成率變化規(guī)律與截止日期之間不存在明顯的相關(guān)性，即其完成率不隨著截止日期約束的寬松而得到明顯提升。在Montage、Epigenomics和LIGO工作流的測(cè)試樣例中，MCPCPP調(diào)度策略在不同的截止日期約束下的完成率均為0，主要是因?yàn)镸CPCPP調(diào)度策略過于強(qiáng)調(diào)壓縮子任務(wù)之間的數(shù)據(jù)通信代價(jià)，這種操作方式對(duì)動(dòng)態(tài)因素的抗干擾能力較弱。

圖6 多云環(huán)境存在波動(dòng)因素的5種中型工作流在不同調(diào)度策略的完成率

圖6(a)是3種調(diào)度策略在不同截止日期約束下的Montage工作流完成率。ADPSOGA調(diào)度策略在1()和2()階段的完成率明顯優(yōu)于WPSO調(diào)度策略。WPSO調(diào)度策略在1()階段的完成率還不到30%，但在3()階段就達(dá)到近80%，稍遜于ADPSOGA調(diào)度策略。在4()和5()階段，ADPSOGA和WPSO調(diào)度策略均達(dá)到100%的工作流完成率。圖6(b)則是3種調(diào)度策略的CyberShake工作流完成率。在1()階段，WPSO調(diào)度策略的完成率超過20%，排在3種策略之首，其次是MCPCPP調(diào)度策略，完成率最低的是ADPSOGA調(diào)度策略。但隨著截止日期約束不斷寬松，如在3()階段之后，ADPSOGA調(diào)度策略就處于優(yōu)勢(shì)地位，其完成率均超過另外2種調(diào)度策略。在5()階段，ADPSOGA和WPSO這2種調(diào)度策略的工作流完成率均接近100%，但MCPCPP調(diào)度策略卻只有不足10%的完成率。這主要還是歸因于MCPCPP過分壓縮子任務(wù)間的數(shù)據(jù)通信。圖6(c)是3種調(diào)度策略的Epigenomics工作流完成率。與圖6(a)和圖6(d)相似，MCPCPP調(diào)度策略在所有截止日期約束下的完成率均為0，除了過分壓縮數(shù)據(jù)的原因外，還主要跟這3種工作流的結(jié)構(gòu)和對(duì)應(yīng)子任務(wù)大小有關(guān)。這3種工作流均包含較多只占實(shí)例小部分單位執(zhí)行時(shí)間的子任務(wù)，通過MCPCPP調(diào)度策略的整合壓縮，在同一個(gè)路徑上的這些子任務(wù)被統(tǒng)一分配給特定執(zhí)行實(shí)例。當(dāng)環(huán)境波動(dòng)時(shí)，這些子任務(wù)路徑的實(shí)際執(zhí)行時(shí)間往往超過估計(jì)值，所以使工作流無(wú)法在截止日期前完成。另外，各階段的ADPSOGA和WPSO調(diào)度策略的完成率相當(dāng)接近，均超過85%。圖6(d)是3種調(diào)度策略的LIGO工作流完成率。ADPSOGA在1()和2()階段的完成率明顯優(yōu)于WPSO。同時(shí)在3()之后，它們二者的完成率基本相同，均接近100%。圖6(e)是3種調(diào)度策略的SIPHT工作流完成率。在1()階段，ADPSOGA調(diào)度策略的完成率最高，達(dá)到85%。在2()階段，ADPSOGA完成率稍遜于WSPO。在后續(xù)階段，基于PSO的2種調(diào)度策略的完成率均達(dá)到100%。

綜上，MCPCPP調(diào)度策略在多云環(huán)境存在波動(dòng)因素的適應(yīng)性最差。ADPSOGA和WPSO調(diào)度策略在截止日期約束寬松的情況下，均能獲得良好的完成率。在截止日期約束嚴(yán)格的情況下，ADPSOGA調(diào)度策略相比于其他2種策略，性能更加優(yōu)越。這主要是因?yàn)锳DPSOGA的編碼策略和更新方式，使其獲取更加多樣的進(jìn)化種群，適應(yīng)動(dòng)態(tài)變化環(huán)境。

圖7是3種不同調(diào)度策略（即MCPCPP、ADPSOGA和WPSO）在對(duì)應(yīng)3種不同截止日期（即1()、3()和5()）約束下的工作流平均標(biāo)準(zhǔn)執(zhí)行代價(jià)和平均執(zhí)行時(shí)間（每個(gè)結(jié)果針對(duì)100組重復(fù)測(cè)試樣例）。每個(gè)子圖中的3條線，分別表示對(duì)應(yīng)的3個(gè)截止日期參考線，目的是為了確定相關(guān)工作流平均執(zhí)行時(shí)間是否超過對(duì)應(yīng)截止日期。同一圖中同時(shí)展示執(zhí)行代價(jià)和執(zhí)行時(shí)間的目的是為了尋找執(zhí)行時(shí)間滿足截止日期約束，同時(shí)其執(zhí)行代價(jià)最低的有效調(diào)度策略。

圖7(a)是Montage工作流的平均標(biāo)準(zhǔn)執(zhí)行代價(jià)和平均執(zhí)行時(shí)間。MCPCPP調(diào)度策略在3個(gè)截止日期約束下的平均標(biāo)準(zhǔn)執(zhí)行代價(jià)()都是最低的，但其對(duì)應(yīng)的平均執(zhí)行時(shí)間均遠(yuǎn)超過截止日期參考線，因此，該調(diào)度策略在3個(gè)截止日期約束下均不是有效調(diào)度方法。在1()、3()和5()階段，ADPSOGA和WPSO調(diào)度策略均滿足截止日期約束，且ADPSOGA調(diào)度策略的()最低。尤其在3()階段，ADPSOGA調(diào)度策略的優(yōu)勢(shì)顯得尤為明顯。相對(duì)于其他工作流而言，3種調(diào)度策略在執(zhí)行Montage工作流時(shí)，產(chǎn)生更大的平均標(biāo)準(zhǔn)執(zhí)行代價(jià)()，其大約是在同等條件下調(diào)度SIPHT工作流的20倍。造成巨大差距的原因主要是因?yàn)椴煌愋凸ぷ髁鞯淖陨斫Y(jié)構(gòu)和子任務(wù)大小存在差異。對(duì)于Montage工作流而言，其第2層中含有許多子任務(wù)，該層子任務(wù)在最快虛擬機(jī)上的執(zhí)行時(shí)間都不超過15 s。在要價(jià)區(qū)間是1 h的實(shí)驗(yàn)環(huán)境下，這些子任務(wù)都只占用虛擬機(jī)整個(gè)要價(jià)區(qū)間的很小一部分。為了滿足截止日期約束，需要啟動(dòng)更多的高速虛擬機(jī)來(lái)處理Montage工作流相關(guān)子任務(wù)，造成資源浪費(fèi)、對(duì)應(yīng)標(biāo)準(zhǔn)執(zhí)行代價(jià)過高。MCPCPP調(diào)度策略往往將第2層子任務(wù)壓縮到少數(shù)幾臺(tái)高速虛擬機(jī)上執(zhí)行。當(dāng)存在波動(dòng)因素時(shí)，其結(jié)果往往是執(zhí)行時(shí)間超過對(duì)應(yīng)截止日期約束。

對(duì)于CyberShake工作流，在1()階段，3種調(diào)度策略的平均執(zhí)行時(shí)間均超過對(duì)應(yīng)截止日期參考線，說明它們均不滿足截止日期約束。雖然ADPSOGA調(diào)度策略的()最低，但無(wú)法判定其就是最優(yōu)調(diào)度策略，因?yàn)槠洳粷M足截止日期約束條件。在3()和5()階段，其整體情況與Montage類似。MCPCPP調(diào)度策略雖然在5()階段()最低，但其不滿足相應(yīng)截止日期約束條件。另外，2種基于PSO的調(diào)度策略均滿足對(duì)應(yīng)截止日期約束，其中ADPSOGA調(diào)度策略的平均標(biāo)準(zhǔn)執(zhí)行代價(jià)()最低，其是相對(duì)MCPCPP和WPSO調(diào)度策略的最優(yōu)調(diào)度方法。

對(duì)于Epigenomics工作流，MCPCPP調(diào)度策略雖然在每個(gè)階段的平均標(biāo)準(zhǔn)執(zhí)行代價(jià)()都是最低的，但其對(duì)應(yīng)的平均執(zhí)行時(shí)間均明顯高于截止日期參考線，因此，MCPCPP調(diào)度策略不是有效方法。在滿足約束條件的調(diào)度策略中，ADPSOGA調(diào)度策略在3個(gè)階段的優(yōu)勢(shì)較為明顯，其不僅在工作流平均執(zhí)行時(shí)間上處于最低值，而且相應(yīng)的平均標(biāo)準(zhǔn)執(zhí)行代價(jià)()也是最低的。這主要是因?yàn)锳DPSOGA調(diào)度策略的編碼技巧和更新方式，使其獲得更大的種群類別和問題搜索空間，能夠更好地適應(yīng)動(dòng)態(tài)多云環(huán)境。

圖7 不同調(diào)度策略在3種截止日期下的工作流標(biāo)準(zhǔn)執(zhí)行代價(jià)和執(zhí)行時(shí)間

相對(duì)于LIGO和SIPHT工作流，3種調(diào)度策略的表現(xiàn)情況與Epigenomics工作流類似，在此不再贅述。

綜上，MCPCPP調(diào)度策略雖然工作流平均標(biāo)準(zhǔn)執(zhí)行代價(jià)()通常較低，但其往往不滿足對(duì)應(yīng)的截止日期約束，不能算是好的調(diào)度方法。WPSO調(diào)度策略雖然通常滿足截止日期約束，但其產(chǎn)生的平均標(biāo)準(zhǔn)執(zhí)行代價(jià)()一般不理想。ADPSOGA調(diào)度策略相對(duì)于所有測(cè)試樣例，在滿足截止日期約束下的平均標(biāo)準(zhǔn)執(zhí)行代價(jià)()表現(xiàn)是最優(yōu)的。

6 結(jié)束語(yǔ)

本文提出一種基于PSO和GA更新算子的多云環(huán)境下ADPSOGA工作流調(diào)度策略。該算法綜合考慮云間數(shù)據(jù)通信代價(jià)、虛擬機(jī)啟停時(shí)間和云環(huán)境下波動(dòng)干擾因素等。其是以工作流截止日期為約束，優(yōu)化工作流總執(zhí)行代價(jià)的元啟發(fā)式算法。通過對(duì)5個(gè)類型的中型工作流的調(diào)度測(cè)試表明，ADPSOGA調(diào)度策略在多云環(huán)境存在波動(dòng)因素干擾下，對(duì)帶截止日期約束的工作流調(diào)度具有更佳的有效性和適應(yīng)性。

未來(lái)工作中，將進(jìn)一步考慮壓縮初始資源池大小的方法，使算法的執(zhí)行效率進(jìn)一步提升。另外，將對(duì)動(dòng)態(tài)波動(dòng)的影響因子逐一分析，找出干擾最大的若干影響因子，進(jìn)一步提高算法的頑健性。

[1] RODRIGUEZ M A, BUYYA R. Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J]. IEEE Transactions on Cloud Computing, 2014, 2(2): 222-235.

[2] FARD H M, PRODAN R, FAHRINGER T. A truthful dynamic workflow scheduling mechanism for commercial multicloud environments[J]. IEEE Transactions on Parallel & Distributed Systems, 2013, 24(6): 1203-1212.

[3] MALAWSKI M, JUVE G, DEELMAN E, et al. Cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[C]//International Conference for High Performance Computing, Networking, Storage and Analysis. 2012: 1-11.

[4] MASDARI M, SALEHI F, JALALI M, et al. A survey of PSO-based scheduling algorithms in cloud computing[J]. Journal of Network & Systems Management, 2017, 25(1): 1-37.

[5] WU Z, NI Z, GU L, et al. A revised discrete particle swarm optimization for cloud workflow scheduling[C]//International Conference on Computational Intelligence and Security, 2010: 184-188.

[6] ABRISHAMI S, NAGHIBZADEH M, EPEMA D H J. Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[J]. Future Generation Computer Systems, 2013, 29(1): 158-169.

[7] MATTOSO M, DIAS J, OCA?A K A C S, et al. Dynamic steering of HPC scientific workflows: a survey[J]. Future Generation Computer Systems, 2015, 46(C): 100-113.

[8] ZENG L, VEERAVALLI B, ZOMAYA A Y. An integrated task computation and data management scheduling strategy for workflow applications in cloud environments[J]. Journal of Network & Computer Applications, 2015, 50(C): 39-48.

[9] 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, 2008, 39(1): 29-43.

[10] CAO H, JIN H, WU X, et al. DAGMap: efficient and dependable scheduling of DAG workflow job in grid[J]. The Journal of Supercomputing, 2010, 51(2): 201-223.

[11] HIGASHINO W A, CAPRETZ M A M, TOLEDO M B F D, et al. A hybrid particle swarm optimization-genetic algorithm applied to grid scheduling[J]. International Journal of Grid & Utility Computing, 2016, 7(2): 113-129.

[12] 苑迎春, 李小平, 王茜, 等. 基于逆向分層的網(wǎng)格工作流調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào), 2008, 31(2): 282-290.

YUAN Y C, LI X P, WANG Q, et al. Bottom level based heuristic for workflow scheduling in grids[J]. Chinese Journal of Computers, 2008, 31(2): 282-290.

[13] ABRISHAMI S, NAGHIBZADEH M, EPEMA D H J. Cost-driven scheduling of grid workflows using partial critical paths[J]. IEEE Transactions on Parallel & Distributed Systems, 2012, 23(8): 1400-1414.

[14] KHAJEMOHAMMADI H, FANIAN A, GULLIVER T A. Fast workflow scheduling for grid computing based on a multi-objective genetic algorithm[C]//Communications, Computers and Signal Processing. 2013: 96-101.

[15] 沈虹, 李小平. 帶準(zhǔn)備時(shí)間和截止期約束的云服務(wù)工作流調(diào)度算法[J]. 通信學(xué)報(bào), 2015, 36(6): 183-192.

SHEN H, LI X P. Algorithm for the cloud service workflow scheduling with setup time and deadline constraints[J]. Journal on Communications, 2015, 36(6): 183-192.

[16] 肖鵬, 胡志剛, 屈喜龍. 面向數(shù)據(jù)密集型工作流的能耗感知調(diào)度策略[J]. 通信學(xué)報(bào), 2015, 36(1): 149-158.

XIAO P, HU Z G, QU X L. Energy-aware scheduling policy for data-intensive workflow[J]. Journal on Communications, 2015, 36(1): 149-158.

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

[18] PANDEY S, WU L, GURU S M, et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//IEEE International Conference on Advanced Information Networking and Applications. 2010: 400-407.

[19] KEAHEY K, TSUGAWA M, MATSUNAGA A, et al. Sky computing[J]. IEEE Internet Computing, 2009, 13(5): 43-51.

[20] LIN B, GUO W, XIONG N, et al. A pretreatment workflow scheduling approach for big data applications in multicloud environments[J]. IEEE Transactions on Network & Service Management, 2016, 13(3): 581-594.

[21] WOO S S, MIRKOVIC J. Optimal application allocation on multiple public clouds[J]. Computer Networks, 2014, 68(11): 138-148.

[22] KENNEDY J, EBERHART R. Particle swarm optimization[C]//IEEE International Conference on Neural Networks. 2002: 1942-1948.

[23] SU J S, GUO W Z, YU C L, et al. Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network[J]. Chinese Journal of Computers, 2014, 37(2): 445-456.

[24] SHI Y, EBERHART R. A modified particle swarm optimizer[C]// IEEE World Congress on Computational Intelligence. 1998: 69-73.

[25] BHARATHI S, CHERVENAK A, DEELMAN E, et al. Characterization of scientific workflows[C]//Workflows in Support of Large-Scale Science. 2008: 1-10.

[26] TOPCUOGLU H, HARIRI S, WU M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel & Distributed Systems, 2002, 13(3): 260-274.

Scheduling strategy for science workflow with deadline constraint on multi-cloud

LIN Bing1,2,3, GUO Wenzhong2,3,4, CHEN Guolong2,3

1. College of Physics and Energy, Fujian Normal University, Fuzhou 350117, China 2. Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing (Fuzhou University), Fuzhou 350116, China 3. Key Laboratory of Spatial Data Mining & Information Sharing, Ministry of Education, Fuzhou 350003, China 4. College of Mathematics and Computer Science, FuzhouUniversity, Fuzhou 350116, China

In view of the deadline-constrained scientific workflow scheduling on multi-cloud, an adaptive discrete particle swarm optimization with genetic algorithm (ADPSOGA) was proposed, which aimed to minimize the execution cost of workflow while meeting its deadline constrains. Firstly, the data transfer cost, the shutdown and boot time of virtual machines, and the bandwidth fluctuations among different cloud providers were considered by this method. Secondly, in order to avoid the premature convergence of traditional particle swarm optimization (PSO), the randomly two-point crossover operator and randomly one-point mutation operator of the genetic algorithm (GA) was introduced. It could effectively improve the diversity of the population in the process of evolution. Finally, a cost-driven strategy for the deadline-constrained workflow was designed. It both considered the data transfer cost and the computing cost. Experimental results show that the ADPSOGA has better performance in terms of deadline and cost reducing in the fluctuant environment.

cloud computing, deadline constraint, workflow scheduling, fluctuation

TP338

A

10.11959/j.issn.1000-436x.2018006

林兵（1986-），男，福建福清人，博士，福建師范大學(xué)講師，主要研究方向?yàn)樵朴?jì)算技術(shù)、計(jì)算智能及其應(yīng)用。

郭文忠（1979-），男，福建泉港人，博士，福州大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橛?jì)算智能及其應(yīng)用。

陳國(guó)龍（1965-），男，福建莆田人，博士，福州大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槿斯ぶ悄?、網(wǎng)絡(luò)安全。

2017-05-24；

2018-01-01

郭文忠，fzugwz@163.com

國(guó)家重點(diǎn)研發(fā)計(jì)劃基金資助項(xiàng)目（No.2017YFB1002000）；國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61672159）；福建省科技創(chuàng)新平臺(tái)計(jì)劃基金資助項(xiàng)目（No.2009J1007, No.2014H2005）；海峽政務(wù)大數(shù)據(jù)應(yīng)用省級(jí)協(xié)同創(chuàng)新中心基金資助項(xiàng)目

: The National Key R&D Program of China (No.2017YFB1002000), The National Natural Science Foundation of China (No.61672159), The Technology Innovation Platform Project of Fujian Province (No.2009J1007, No.2014H2005), The Foundation of The Fujian Collaborative Innovation Center for Big Data Application in Governments