方伯芃，孫林夫

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031； 2.西南交通大學(xué) 制造業(yè)產(chǎn)業(yè)鏈協(xié)同與信息化支撐技術(shù)四川省重點(diǎn)實(shí)驗(yàn)室，四川 成都 610031)

0 引言

隨著云計(jì)算技術(shù)的迅速發(fā)展及云服務(wù)模式的不斷成熟，IT領(lǐng)域正發(fā)生著重大變革。作為一種新的服務(wù)提供模式，云計(jì)算以其高效、靈活、可定制、可擴(kuò)展的特點(diǎn)幫助用戶大大降低了軟硬件的購(gòu)買與維護(hù)成本。通過互聯(lián)網(wǎng)，云計(jì)算向用戶提供各種計(jì)算、存儲(chǔ)和應(yīng)用資源服務(wù)，如基礎(chǔ)設(shè)施即服務(wù)(Infrastructure as a Service, IaaS)、平臺(tái)即服務(wù)(Platform as a Service, PaaS)和軟件即服務(wù)(Software as a Service, SaaS)等[1-2]，不同用戶可按各自需求租賃所需的云服務(wù)資源，并依據(jù)服務(wù)類型和使用時(shí)間支付相應(yīng)的服務(wù)費(fèi)用。

云工作流是云計(jì)算環(huán)境下工作流的一種新型應(yīng)用模式，它集成云計(jì)算及工作流的技術(shù)特征與模式特點(diǎn)，根據(jù)不同租戶需求，將特定的業(yè)務(wù)流程部署在云平臺(tái)中，并允許多個(gè)租戶能同時(shí)在云中設(shè)計(jì)、配置和操作各自的業(yè)務(wù)流程，并實(shí)現(xiàn)數(shù)據(jù)、性能和執(zhí)行3個(gè)層次的隔離[3]。與傳統(tǒng)工作流相比，其應(yīng)需服務(wù)、隨需而變、按需支付的服務(wù)特征有效地為租戶節(jié)約了成本開支，提高了工作效率，極適用于那些因缺少資金和人力而無(wú)法購(gòu)買與運(yùn)維工作流系統(tǒng)的企業(yè)用戶。云計(jì)算中的工作流不僅在應(yīng)用模式上發(fā)揮了更大的優(yōu)勢(shì)，還為租戶提供了諸多的高效、便利與靈活，與此同時(shí)，云工作流的運(yùn)行環(huán)境也較先前發(fā)生了巨大的改變，從而使傳統(tǒng)的工作流資源調(diào)度方法不再適用于新模式，需在云環(huán)境下重新分析與設(shè)計(jì)相關(guān)的模型方法。

目前，關(guān)于工作流的調(diào)度問題已有較多研究成果，根據(jù)調(diào)度目標(biāo)的不同，現(xiàn)有研究主要從工作流的完成時(shí)間、服務(wù)質(zhì)量和云資源使用成本3個(gè)角度對(duì)問題展開分析。

最為常見的工作流調(diào)度目標(biāo)是如何更有效地縮減工作流響應(yīng)完成時(shí)間，這也是早期在網(wǎng)格計(jì)算環(huán)境下工作流調(diào)度需要考慮的問題。肖志嬌等[4]針對(duì)工作流資源配置優(yōu)化問題展開研究，提出一種基于分層嵌套遺傳算法的資源優(yōu)化方法，在成本約束下針對(duì)資源專業(yè)化/一般化程度及資源數(shù)量進(jìn)行配置優(yōu)化，從而最小化工作流實(shí)例的平均響應(yīng)時(shí)間；Amalarethinam等[5]針對(duì)網(wǎng)格工作流調(diào)度問題展開研究，通過建立工作流任務(wù)調(diào)度模型，提出一種最小化完成時(shí)間網(wǎng)格工作流調(diào)度算法，基于該算法實(shí)現(xiàn)了網(wǎng)格工作流完成時(shí)間的最小化；衣楊等[6]針對(duì)工作流流水時(shí)間資源優(yōu)化問題建立了最小化流水時(shí)間的工作流資源優(yōu)化數(shù)學(xué)模型，并在此基礎(chǔ)上設(shè)計(jì)了精英保存策略改進(jìn)型遺傳算法，實(shí)現(xiàn)了工作流最小流水時(shí)間的調(diào)度尋優(yōu)。

上述研究能有效降低工作流的完成時(shí)間，提升執(zhí)行性能與效率。然而，在云環(huán)境下，僅考慮工作流的執(zhí)行時(shí)間是不夠的，因?yàn)樵骗h(huán)境中的工作流是通過服務(wù)的形式滿足不同租戶業(yè)務(wù)流程需求，所以提升租戶服務(wù)質(zhì)量(Quality of Service, QoS)往往是云工作流調(diào)度關(guān)注的重點(diǎn)，現(xiàn)有的一些研究則致力于解決滿足租戶期限約束下最小化租戶服務(wù)費(fèi)用的問題。李學(xué)俊等[7]針對(duì)云工作流任務(wù)調(diào)度優(yōu)化問題，提出一種基于新型自適應(yīng)慣性權(quán)重計(jì)算法則的改進(jìn)粒子群算法，在此基礎(chǔ)上得出云工作流截止期限約束下服務(wù)費(fèi)用最低的調(diào)度方案；王巖等[8]針對(duì)實(shí)例密集型云工作流資源調(diào)度問題，提出一種基于QoS約束的云工作流調(diào)度算法，以尋求截止期限約束下有效降低云工作流服務(wù)費(fèi)用的調(diào)度策略；Verma等[9]針對(duì)云工作流調(diào)度優(yōu)化問題進(jìn)行研究，考慮云模式中不同類型的定價(jià)模型，提出一種基于截止時(shí)間約束的啟發(fā)式遺傳算法，在此基礎(chǔ)上實(shí)現(xiàn)滿足期限約束下云工作流服務(wù)費(fèi)用的最小化；鄭敏等[10]將云服務(wù)費(fèi)用價(jià)格函數(shù)定義為常值型與周期分段型兩類模型，研究云工作流任務(wù)調(diào)度開銷問題，并提出一種基于動(dòng)態(tài)規(guī)劃的云工作流調(diào)度算法，得出截止時(shí)間約束下租戶服務(wù)開銷最低的調(diào)度方案。

云工作流的執(zhí)行需占用一定的云資源，云服務(wù)提供商的運(yùn)營(yíng)成本也是需要重點(diǎn)考慮的內(nèi)容之一，因此現(xiàn)有部分研究側(cè)重于探索云工作流成本感知與云資源調(diào)度優(yōu)化問題。文一憑等[11]對(duì)云工作流的隱私與成本感知技術(shù)進(jìn)行研究，針對(duì)云工作流執(zhí)行過程中的計(jì)算成本、傳輸成本、存儲(chǔ)成本建立云資源使用成本模型，在粒子群與模擬退火算法基礎(chǔ)上引入任務(wù)優(yōu)先級(jí)計(jì)算策略，提出一種具有隱私與云資源使用成本感知能力的云工作流調(diào)度方法，尋求隱私保護(hù)約束下云資源使用成本最低的調(diào)度方案；沈虹等[12]針對(duì)帶準(zhǔn)備時(shí)間和截止期約束的云工作流資源調(diào)度問題建立問題優(yōu)化模型，并提出一種混合分布估計(jì)優(yōu)化方法，建立了云工作流任務(wù)與云基礎(chǔ)設(shè)施資源服務(wù)間的選擇對(duì)應(yīng)關(guān)系，得出帶準(zhǔn)備時(shí)間和截止期約束下云資源租賃成本最低的調(diào)度方案；Durillo等[13]針對(duì)亞馬遜彈性計(jì)算云工作流調(diào)度問題，分析了云工作流執(zhí)行過程中的計(jì)算、傳輸與存儲(chǔ)3類執(zhí)行成本，并提出一種基于Pareto規(guī)則的表調(diào)度啟發(fā)式算法，以尋求云工作流完成時(shí)間最短及執(zhí)行成本最低的多目標(biāo)調(diào)度優(yōu)化方案；Mollajafari等[14]針對(duì)截止期限約束的云工作流資源調(diào)度問題，提出一種從基因編碼到調(diào)度方案的新型映射規(guī)則，然后利用遺傳算法進(jìn)行調(diào)度尋優(yōu)，求解出流程任務(wù)與服務(wù)資源間的最優(yōu)映射關(guān)系，以得到截止時(shí)間約束下云資源使用成本最低的調(diào)度方案。

現(xiàn)有文獻(xiàn)面對(duì)不同調(diào)度目標(biāo)展開了諸多研究，但大多都從單個(gè)角度對(duì)問題進(jìn)行分析與優(yōu)化，忽略了調(diào)度中不同主體間利益的博弈與共贏。實(shí)際上，云工作流的資源調(diào)度無(wú)論對(duì)租戶還是云服務(wù)提供商都有十分重要的意義，調(diào)度優(yōu)化的目標(biāo)需綜合考慮租戶QoS和云服務(wù)提供商的運(yùn)營(yíng)成本。

另外，現(xiàn)有研究大多針對(duì)云工作流任務(wù)集與虛擬機(jī)類型集間的部署關(guān)系進(jìn)行調(diào)度優(yōu)化，在調(diào)度過程中未考慮或簡(jiǎn)化了虛擬機(jī)的負(fù)載約束和實(shí)例數(shù)量，例如文獻(xiàn)[15]在處理云工作流調(diào)度問題時(shí)假設(shè)“各種類型的虛擬機(jī)擁有足夠的能力執(zhí)行任務(wù)，在執(zhí)行過程中其計(jì)算能力不會(huì)變化，且每類虛擬機(jī)擁有足夠多的虛擬機(jī)實(shí)例[15]”，然而在實(shí)際中，虛擬機(jī)實(shí)例存在著諸如CPU、內(nèi)存、存儲(chǔ)等多種類型的資源負(fù)載約束，它們中的任何一種資源出現(xiàn)超載都將對(duì)虛擬機(jī)的整體性能造成極大影響，最終波及租戶的服務(wù)質(zhì)量；但若是為了均衡負(fù)載而隨意增加虛擬機(jī)實(shí)例數(shù)量，則會(huì)造成虛擬機(jī)資源的閑置浪費(fèi)，加大云服務(wù)提供商的運(yùn)營(yíng)成本。因此，云工作流的調(diào)度目標(biāo)不僅需要考慮云工作流任務(wù)集與虛擬機(jī)類型集間的部署關(guān)系，更需要考慮任務(wù)集與虛擬機(jī)實(shí)例集間的部署關(guān)系以及各類虛擬機(jī)實(shí)例的數(shù)量大小。

云工作流技術(shù)融合了工作流系統(tǒng)與云計(jì)算平臺(tái)兩者的技術(shù)特征，既具有工作流的流程配置特性，又具備云計(jì)算平臺(tái)的多租戶特征，然而在現(xiàn)有研究中，調(diào)度的算法模型更多考慮單個(gè)或某些特定流程的資源調(diào)度，對(duì)面向多租戶環(huán)境下，針對(duì)多個(gè)結(jié)構(gòu)不同、規(guī)模不一的云工作流進(jìn)行統(tǒng)一調(diào)度的研究還比較少。

因此，本文從租戶的服務(wù)質(zhì)量和云服務(wù)提供商的運(yùn)營(yíng)成本雙方利益出發(fā)，建立面向QoS與成本感知的云工作流調(diào)度模型，在此基礎(chǔ)上設(shè)計(jì)基于任務(wù)序列劃分的兩段式編碼遺傳算法(Genetic Algorithm based on two segment coding of Tasks Order Division，TOD-GA)，在保證租戶租約約束及虛擬機(jī)實(shí)例負(fù)載約束條件下，求解出多租戶環(huán)境下，云工作流任務(wù)集與虛擬機(jī)類型集間的最優(yōu)部署關(guān)系、任務(wù)集與虛擬機(jī)實(shí)例集間的最優(yōu)部署關(guān)系，以及各類型虛擬機(jī)需創(chuàng)建的最優(yōu)實(shí)例數(shù)量，從而實(shí)現(xiàn)租戶服務(wù)費(fèi)用與云資源使用成本的最優(yōu)化。最后，通過算例仿真分析驗(yàn)證了模型的有效性。

1 問題描述與模型建立

面向QoS與成本感知的云工作流調(diào)度問題涉及多類集合概念，不同集合元素間又存在多種映射關(guān)系，為了較好地對(duì)問題進(jìn)行描述并建立數(shù)學(xué)模型，給出以下定義：

(1)

(2)

i∈[1,n]。

問題可分兩個(gè)階段(如圖1)，第一階段Stage-T，租戶集提出m種云工作流需求，云服務(wù)提供商對(duì)其解析出任務(wù)集合T，并與n類不同配置的虛擬機(jī)形成映射關(guān)系

(3)

云服務(wù)提供商需保證在調(diào)度方案MapT-VMC下，m個(gè)云工作流均滿足租戶租約約束。該階段為nT個(gè)任務(wù)放入n類虛擬機(jī)的放置問題，復(fù)雜度為O(nnT)。

第二階段Stage-V，云服務(wù)提供商為實(shí)現(xiàn)方案MapT-VMC，需確定各類虛擬機(jī)的實(shí)例數(shù)量，并建立任務(wù)集與虛擬機(jī)實(shí)例集間的映射關(guān)系

MapT-Vm=

(4)

面向QoS與成本感知的云工作流調(diào)度模型從云工作流執(zhí)行時(shí)間、云工作流服務(wù)費(fèi)用和云資源使用成本3方面展開分析。

(1)云工作流執(zhí)行時(shí)間

(5)

(6)

(7)

云工作流執(zhí)行時(shí)間為工作流內(nèi)所有任務(wù)均執(zhí)行完成需要的時(shí)間，則有

(8)

為保證對(duì)于任意流程租約約束，云服務(wù)提供商必能提供一種方案予以滿足，假設(shè)將任務(wù)集T內(nèi)的全部任務(wù)分配給Vmc集中性能最優(yōu)的虛擬機(jī)時(shí)，必有Tbpj≤Dlj(j∈[1,m])。

(2)云工作流服務(wù)費(fèi)用

(9)

則對(duì)于m個(gè)租戶，云工作流的總服務(wù)費(fèi)用

(10)

(3)云資源使用成本

云服務(wù)提供商將租戶流程任務(wù)部署在多個(gè)虛擬機(jī)實(shí)例中，以支撐m個(gè)云工作流運(yùn)作，虛擬機(jī)的總使用成本

(11)

k∈[1,q],i∈[1,n],e∈[1,ni]。

(12)

綜上所述，面向QoS與成本感知的云工作流調(diào)度模型可描述為：

min(α1×CBP+α2×Cvm)。

(13)

s.t.

Tbpj≤Dlj,j∈[1,m];

k∈[1,q],i∈[1,n],e∈[1,ni]。

(14)

2 基于任務(wù)序列劃分的兩段式編碼遺傳算法

本章首先對(duì)調(diào)度方案的編碼進(jìn)行研究，分析傳統(tǒng)編碼規(guī)則在求解云工作流調(diào)度問題時(shí)存在的不足，提出一種新的編碼規(guī)則，在此基礎(chǔ)上構(gòu)建TOD-GA，并設(shè)計(jì)編碼的約束性檢驗(yàn)與修正算法，以處理遺傳進(jìn)化中產(chǎn)生的不可行解染色體集，最后針對(duì)算法編碼特性設(shè)計(jì)相應(yīng)的遺傳算子，實(shí)現(xiàn)迭代過程中的選擇、交叉與變異。

2.1 調(diào)度方案編、解碼規(guī)則

對(duì)于云工作流調(diào)度問題，現(xiàn)有研究的方案編碼規(guī)則主要為基于任務(wù)與虛擬機(jī)映射關(guān)系的編碼(Tasks and Virtual machines Mapping coding, TVM)規(guī)則，該類編碼將每個(gè)基因看做是一個(gè)任務(wù)，基因的取值則是該任務(wù)與虛擬機(jī)間的映射關(guān)系[11-12,15]，如圖2所示。該類編碼可較好解析出任務(wù)集與虛擬機(jī)類型集間的映射關(guān)系MapT-VMC，但卻無(wú)法得出任務(wù)集與實(shí)例集間的映射關(guān)系MapT-Vm，也無(wú)法確定各類虛擬機(jī)需要的實(shí)例數(shù)量，以至于需在MapT-VMC基礎(chǔ)上再進(jìn)行n次調(diào)度來(lái)獲取MapT-Vm與ni(i∈[1,n])。

為此，本文提出一種基于任務(wù)序列劃分的兩段式編碼(two segment coding of Tasks Order Division, TOD)規(guī)則，將調(diào)度中的Stage-T與Stage-V兩個(gè)環(huán)節(jié)解析為編碼的兩個(gè)分段，從而實(shí)現(xiàn)云工作流調(diào)度方案編碼的映射。

AreaT和AreaV兩區(qū)域相互作用，解析出任務(wù)集T與虛擬機(jī)集Vmc間的映射關(guān)系MapT-VMC、任務(wù)集T與實(shí)例集Vm間的映射關(guān)系MapT-Vm，以及虛擬機(jī)vmci(i∈[1,n])實(shí)例的數(shù)量ni。

(1)對(duì)Stage-T階段映射關(guān)系MapT-VMC的解析

(15)

(2)對(duì)Stage-V階段映射關(guān)系MapT-Vm及實(shí)例數(shù)量ni的解析

該階段針對(duì)Stage-T階段得出的映射關(guān)系MapT-VMC設(shè)計(jì)MapT-Vm映射算法，以解析出vmci(i∈[1,n])虛擬機(jī)實(shí)例的數(shù)量ni和實(shí)例與任務(wù)間的映射關(guān)系MapT-Vm。因?yàn)樘摂M機(jī)實(shí)例是任務(wù)的載體，任務(wù)運(yùn)行中需占用一定資源，所以將任務(wù)分配給虛擬機(jī)實(shí)例時(shí)，需保證被分配任務(wù)集占用的各類資源總量應(yīng)低于虛擬機(jī)實(shí)例中各類資源的最大可用量，即需滿足式(12)的負(fù)載約束條件，則vmci(i∈[1,n])型虛擬機(jī)的MapT-Vm映射算法流程如下：

其中：堆棧Tstacki包括tt=Tstacki.Pop()和Tstacki.Push(tt)兩類方法，分別對(duì)Tstacki進(jìn)行出堆棧操作和入堆棧操作，方法Pop()取出Tstacki中的棧頂元素，將其保存在tt中，方法Push(tt)則將任務(wù)tt放入Tstacki中；Tstacki包含一個(gè)屬性Tstacki.Length，用于標(biāo)記堆棧內(nèi)元素的數(shù)量，初始化后有Tstacki.Length=mi。

步驟3堆棧Tstacki的棧頂元素出堆棧，tt=Tstacki.Pop()；更新Tstacki內(nèi)的元素?cái)?shù)量，Tstacki.Length--；令e=1。

(16)

判斷堆棧Tstacki是否為空，即判斷Tstacki.Length=0是否成立，若成立則執(zhí)行步驟8，否則執(zhí)行步驟3。

步驟6e=e+1，判斷e≤ni是否成立，若成立則執(zhí)行步驟4，否則需增加vmci虛擬機(jī)實(shí)例以滿足任務(wù)tt的運(yùn)行需求，執(zhí)行步驟7。

2.2 編碼的約束性檢驗(yàn)與修正算法

云工作流的調(diào)度包括m個(gè)租約約束Dl={Dlj|j∈[1,m]}，因?yàn)檫z傳算法并不具備處理約束問題的能力，所以種群在進(jìn)化中可能演繹出不符合租約約束的染色體，為避免該類染色體在尋優(yōu)迭代中對(duì)種群的進(jìn)化產(chǎn)生影響，需對(duì)演化中的種群進(jìn)行約束性檢驗(yàn)。

(17)

(18)

步驟1通過拓?fù)渑判蛩惴ǖ贸鯞p集m個(gè)云工作流的拓?fù)湫蛄蠺opoSort。

步驟2初始化j=1，v=1。

步驟7判斷j=m是否成立，若不成立則j=j+1，v=1，執(zhí)行步驟3，否則執(zhí)行步驟8。

PopuUnfisible=PopuUnfisible∪GP。

(19)

步驟10算法結(jié)束。

不符合租約約束的染色體需進(jìn)行修正，為較好說(shuō)明不可行解染色體的修正過程，給出以下定義：

(20)

i∈[1,n],wi∈[1,w]。

(21)

ΔCt=(Cvti2-Cvti1)×nb;

(22)

②云資源的總使用成本，由式(11)可知，云資源使用成本與各類虛擬機(jī)建立的實(shí)例數(shù)量有關(guān)，若將較多的任務(wù)從vmci1遷移至vmci2，則將導(dǎo)致vmci1實(shí)例數(shù)量減少，vmci2實(shí)例數(shù)量增加，虛擬機(jī)總使用成本Cvm的變化量

(23)

因此，染色體在修正過程中如何進(jìn)行任務(wù)的遷移調(diào)度，從而使修正后的染色體總服務(wù)費(fèi)用增量和總云資源使用成本增量盡可能小是值得考慮的。由于不同虛擬機(jī)間任務(wù)的遷移對(duì)總服務(wù)費(fèi)用增量和總使用成本增量的影響不一，為較好描述染色體修正過程中任務(wù)在虛擬機(jī)間的遷移對(duì)流程服務(wù)費(fèi)用與云資源使用成本的影響程度，給出變遷代價(jià)與變遷等級(jí)的定義：

(24)

(25)

定義13和定義14將n類虛擬機(jī)間任務(wù)變遷的代價(jià)劃分為n-1個(gè)等級(jí)，PopuUnfisible內(nèi)染色體需按變遷等級(jí)由低至高逐一遷移虛擬機(jī)內(nèi)的任務(wù)，染色體修正算法流程如下：

步驟1初始化pi=1。

(26)

更新關(guān)系集MapT-VMC：

(27)

步驟6判斷wi=w是否成立，若不成立，則wi=wi+1，c=1，執(zhí)行步驟4，否則執(zhí)行步驟7。

步驟8判斷pi=Pn是否成立，若不成立，則pi=pi+1，執(zhí)行步驟2，否則執(zhí)行步驟9。

步驟9種群中全部染色體編碼修正完畢，算法結(jié)束。

染色體的修正過程從云工作流服務(wù)費(fèi)用與云資源使用成本兩類目標(biāo)出發(fā)，通過α1，α2引導(dǎo)染色體在修正中選擇優(yōu)化目標(biāo)。可以看出，當(dāng)α1=1時(shí)，染色體的修正將完全以服務(wù)費(fèi)用增量最低為目標(biāo);當(dāng)α2=1時(shí)，染色體的修正則以使用成本增量最低為目標(biāo)。

2.3 遺傳算子設(shè)計(jì)

遺傳算法迭代進(jìn)化過程主要包括選擇、交叉、變異3個(gè)步驟，選擇是對(duì)種群中染色體優(yōu)勝劣汰的過程，TOD-GA采用輪盤賭算子完成種群染色體的選擇操作。

(28)

P∈{A,B}。

步驟4初始化y=1。

步驟7判斷y=nCross是否成立，若不成立則y=y+1，執(zhí)行步驟5，否則執(zhí)行步驟8。

至此，編碼GA的兩段式交叉算子流程結(jié)束，編碼GB的交叉流程同上所述。

(29)

(30)

步驟11判斷x=d是否成立，若不成立，則x=x+1，執(zhí)行步驟10,否則執(zhí)行步驟12。

步驟12完成編碼GP的變異。

至此，編碼GP的兩段式變異算子流程結(jié)束。

遺傳算法的適應(yīng)度描述了染色體編碼的優(yōu)劣程度，是遺傳進(jìn)化選擇中優(yōu)勝劣汰的評(píng)判標(biāo)準(zhǔn)，本文以降低云工作流服務(wù)費(fèi)用與虛擬機(jī)使用成本為優(yōu)化目標(biāo)，由式(13)得適應(yīng)度函數(shù)

α1∈[0,1],α1+α2=1。

(31)

綜上所述，TOD-GA流程如下：

步驟1初始化種群大小Psize、迭代次數(shù)Gen、交叉率pc和變異率pm，依據(jù)TOD編碼規(guī)則隨機(jī)生成初代種群Popu0，初始化當(dāng)前代數(shù)gi=0。

步驟4求解Popugi內(nèi)各染色體的適應(yīng)度，獲取當(dāng)代最優(yōu)染色體，更新全局最優(yōu)染色體。

步驟5判斷gi=Gen是否成立，若不成立，則執(zhí)行步驟6，否則執(zhí)行步驟7。

步驟6使用本章遺傳算子對(duì)種群Popugi進(jìn)行選擇、交叉、變異操作來(lái)更新種群，令gi=gi+1，執(zhí)行步驟2。

步驟7算法結(jié)束，得出最優(yōu)調(diào)度方案。

3 仿真分析

本章將針對(duì)不同規(guī)模云工作流調(diào)度問題進(jìn)行多次實(shí)驗(yàn)，以驗(yàn)證算法的適應(yīng)性與有效性，并與兩類基于任務(wù)與虛擬機(jī)映射編碼規(guī)則的遺傳算法進(jìn)行對(duì)比實(shí)驗(yàn)和結(jié)論分析。本文算法通過MATLAB R2009實(shí)現(xiàn)，CPU為Inter(R)Core(TM)i7 2.00 GHz，內(nèi)存為4 G。

3.1 實(shí)驗(yàn)算例設(shè)計(jì)

仿真實(shí)驗(yàn)涉及的參數(shù)主要包括虛擬機(jī)參數(shù)、流程參數(shù)、任務(wù)參數(shù)和模型參數(shù)4部分，各類型參數(shù)設(shè)計(jì)如下：

(1)虛擬機(jī)參數(shù)規(guī)則

一般云服務(wù)提供商向租戶提供多類服務(wù)，這些服務(wù)被部署在云基礎(chǔ)設(shè)施提供商所提供的虛擬機(jī)上[18](如Amazon EC2)，或者在云服務(wù)提供商自己的服務(wù)器上[19]，仿真算例主要依據(jù)前者設(shè)計(jì)云服務(wù)提供商的云資源使用成本。

虛擬機(jī)的參數(shù)配置信息參考Amazon EC2的虛擬機(jī)類型模板[11，18]，分別使用小型、中型、大型、超大型和高CPU型(Small，Medium，Large，Extra Large，High-CPU)5類虛擬機(jī)模板，各類型虛擬機(jī)主要考慮CPU、內(nèi)存和存儲(chǔ)3類資源，不同型號(hào)虛擬機(jī)根據(jù)其配置擁有不同的使用成本與服務(wù)費(fèi)用，各參數(shù)如表1所示。

表1 不同類型虛擬機(jī)實(shí)例的參數(shù)設(shè)置

(2)流程參數(shù)規(guī)則

(32)

各云工作流的租約約束期限以其最快完工時(shí)間為準(zhǔn)，在此基礎(chǔ)上增加δj倍，故設(shè)云工作流bpj的租約約束期限D(zhuǎn)lj=min(Tbpj)×(1+δj)，其中:min(Tbpj)表示當(dāng)將流程bpj內(nèi)的全部任務(wù)放入計(jì)算能力最優(yōu)的虛擬機(jī)中時(shí)，流程bpj所需要的執(zhí)行時(shí)間;δj∈[uδ-0.5,uδ+0.5]為租約期限增量系數(shù)，滿足δj～N(uδ,0.192)，其中租約期限增量系數(shù)均值uδ∈{0.5,1.0,1.5,2.0}。

(3)任務(wù)參數(shù)規(guī)則

(4)模型參數(shù)規(guī)則

設(shè)定云工作流服務(wù)費(fèi)用系數(shù)和云資源使用成本系數(shù)(α1,α2)∈{(1,0),(0.5,0.5),(0,1)}、遺傳算法種群大小Psize=20、迭代次數(shù)Gen=500、交叉率pc=0.8、變異率pm=0.1。

3.2 仿真算例驗(yàn)證分析

為驗(yàn)證本文算法的有效性，選用兩類基于任務(wù)與虛擬機(jī)映射編碼規(guī)則的遺傳算法(Genetic Algorithm based on Tasks and Virtual machines Mapping coding, TVM-GA)進(jìn)行對(duì)比實(shí)驗(yàn)，分別記作TVM-GA1和TVM-GA2，各算法設(shè)計(jì)如下：

(1)TVM-GA1算法采用基于任務(wù)與虛擬機(jī)映射的編碼規(guī)則，以式(13)為目標(biāo)函數(shù)、式(14)為調(diào)度約束條件，通過兩點(diǎn)交叉算子與基本位變異算子更新種群，并使用2.2節(jié)算法對(duì)種群內(nèi)的染色體進(jìn)行約束性檢驗(yàn)與修正，遺傳進(jìn)化中設(shè)定種群大小為20，迭代次數(shù)為500，交叉率為0.8，變異率為0.1。該算法通過TVM編碼規(guī)則解析出Stage-T階段任務(wù)集與虛擬機(jī)集間的映射關(guān)系MapT-VMC，然后分析當(dāng)前全部虛擬機(jī)實(shí)例的資源可用率，并以資源占用最大優(yōu)先為分配原則，通過貪心準(zhǔn)則求解出Stage-V階段任務(wù)集與實(shí)例集間的映射關(guān)系MapT-Vm，求解過程如下：

(33)

步驟3遍歷虛擬機(jī)實(shí)例集Vmi內(nèi)的全部實(shí)例，找出當(dāng)前可用率最大的實(shí)例編號(hào)e*與資源編號(hào)k*，若當(dāng)前最大可用率存在多個(gè)實(shí)例或多個(gè)資源，則從中隨機(jī)選出一個(gè)實(shí)例和一個(gè)資源，有

k∈[1,q]}。

(34)

步驟4遍歷未分配的實(shí)例任務(wù)集Tseti，找出占用資源k*最大的任務(wù)tta*，若對(duì)于資源k*存在多個(gè)任務(wù)占用該資源最大，則從中隨機(jī)選出一個(gè)任務(wù)，有

tta*.rtk*=max{tta.rtk*|a∈[1,nTset]}。

(35)

(36)

將任務(wù)tta*從Tseti中移除：

(37)

步驟7判斷任務(wù)集Tseti是否為空，即nTset=0是否成立，若成立則執(zhí)行步驟9，否則執(zhí)行步驟3。

(2)TVM-GA2算法采用基于任務(wù)與虛擬機(jī)映射的編碼規(guī)則，算法在尋優(yōu)過程中不對(duì)染色體進(jìn)行修復(fù)操作，而是借鑒文獻(xiàn)[15]的方法，通過將不可行染色體目標(biāo)值進(jìn)行放大來(lái)降低其適應(yīng)度值，以期在選擇進(jìn)化中過濾掉該類染色體。算法的適應(yīng)度函數(shù)為

F(Gp)=

(38)

式中：α1∈[0,1],α2∈[0,1],α1+α2=1;懲罰系數(shù)λ=w/m為對(duì)不可行染色體給予的目標(biāo)值懲罰比例，w(w∈[1,m])為染色體GP中存在的無(wú)法滿足租約約束的云工作流數(shù)量。TVM-GA2算法通過兩點(diǎn)交叉算子與基本位變異算子更新種群，遺傳進(jìn)化中設(shè)定種群大小為20、迭代次數(shù)為500、交叉率為0.8、變異率為0.1，算法求解任務(wù)集與實(shí)例集間映射關(guān)系MapT-Vm的過程與TVM-GA1算法相同。

驗(yàn)證實(shí)驗(yàn)選取問題規(guī)模m=15，云工作流服務(wù)費(fèi)用系數(shù)與云資源使用成本系數(shù)(α1,α2)=(0.5,0.5)，針對(duì)租約期限增量系數(shù)均值uδ∈{0.5,1.0,1.5,2.0}進(jìn)行4次仿真實(shí)驗(yàn)，并求出3類算法在不同uδ下的最優(yōu)解進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)比實(shí)驗(yàn)從各算法的最優(yōu)解方案租約滿足情況與最優(yōu)解質(zhì)量?jī)煞矫嬲归_分析。

(1)最優(yōu)解方案租約滿足情況方面

分別解析uδ=1.5時(shí)3類算法最優(yōu)解對(duì)應(yīng)的調(diào)度方案，計(jì)算出m個(gè)流程的執(zhí)行時(shí)間，如圖5所示。

圖中橫坐標(biāo)為全部流程的任務(wù)集，各流程內(nèi)的任務(wù)按照拓?fù)湫蝽樞蚺帕?，可以看出TOD-GA算法與TVM-GA1算法得出的最優(yōu)解方案均能滿足全部流程的租約約束，而TVM-GA2算法最優(yōu)解方案會(huì)導(dǎo)致部分流程的執(zhí)行時(shí)間超出租約期限。再分別對(duì)比不同程度租約期限uδ∈{2.0,1.5,1.0,0.5}下，TVM-GA2算法租約的滿足情況，如圖6所示。

可以看出，當(dāng)租約期限較寬裕時(shí)，TVM-GA2算法可勉強(qiáng)滿足租約約束，隨著uδ的逐漸遞減，TVM-GA2算法的租約滿足情況也在隨之降低，當(dāng)uδ較小時(shí)，幾乎所有租戶流程的執(zhí)行時(shí)間均超出了租約期限。若令NTOD,NTVM1,NTVM2為3類算法最優(yōu)解方案滿足租約約束的流程數(shù)量，則定義STOD,STVM1,STVM2為3類算法的租約滿足率，有

Sτ=Nτ/m,τ∈{TOD,TVM1,TVM2}。

(39)

3類算法的租約滿足情況如表2所示。

表2 3種算法最優(yōu)解方案的租約滿足情況

(2)最優(yōu)解質(zhì)量方面

分別計(jì)算不同uδ下3類算法最優(yōu)解方案得出的目標(biāo)函數(shù)值，如圖7所示。

τ∈{TOD,TVM1,TVM2}。

(40)

3類算法最優(yōu)解的質(zhì)量如表3所示。

表3 3類算法最優(yōu)解的質(zhì)量情況

為更客觀顯示各算法的性能，算例選取問題規(guī)模m∈{25,15,5};考慮云工作流服務(wù)費(fèi)用系數(shù)和云資源使用成本系數(shù)(α1,α2)∈{(1,0),(0.5,0.5),(0,1)}，租約期限增量系數(shù)均值uδ∈{1.5,1.0}。3類算法對(duì)比實(shí)驗(yàn)的結(jié)果如表4所示。

表4 3類算法的對(duì)比實(shí)驗(yàn)

從表4中對(duì)3類算法租約滿足率STOD，STVM1和STVM2的對(duì)比可以看出，TVM-GA2算法在各種情況下幾乎均無(wú)法同時(shí)保證全部租戶流程都滿足租約約束，這是由于在尋優(yōu)過程中，TVM-GA2算法并不對(duì)種群進(jìn)行染色體修復(fù)操作，而是通過降低不可行染色體適應(yīng)度的方式減少該類染色體在選擇進(jìn)化中的存活率，這種處理方式在種群中的可行染色體數(shù)量占據(jù)絕對(duì)優(yōu)勢(shì)時(shí)有一定的效果，當(dāng)種群中含有大量不可行染色體時(shí)，僅通過遺傳選擇將無(wú)法過濾掉劣勢(shì)染色體，錯(cuò)誤的基因信息將隨父代大量地繼承到子代，從而誤導(dǎo)種群進(jìn)化的正確方向，使種群在迭代多次后仍然無(wú)法擺脫這些致命缺陷?？梢钥闯?，在具有相同m和(α1,α2)時(shí)，STVM2將隨uδ的減少而減少，這是因?yàn)楫?dāng)uδ減少時(shí)，各租戶流程的約束時(shí)間變得更為嚴(yán)格，減少了問題的可行解數(shù)量，增加了種群中不可行染色體的比例，從而加劇了進(jìn)化中錯(cuò)誤基因遺傳到下一代的概率。然而，因?yàn)門OD-GA和TVM-GA1算法在每代進(jìn)化后都會(huì)對(duì)種群染色體進(jìn)行修復(fù)，有效避免了進(jìn)化過程中不可行染色體的產(chǎn)生，使這兩類算法的最優(yōu)解方案在各種情況下均滿足全部流程的租約約束。

從表4中對(duì)比3類算法最優(yōu)解的目標(biāo)函數(shù)值ObjTOD，ObjTVM1，ObjTVM2可以看出，TVM-GA2算法最優(yōu)解的目標(biāo)函數(shù)值普遍較大，這是由于該類算法得出的最優(yōu)解中存在較多流程無(wú)法滿足租約約束，從而使算法適應(yīng)度函數(shù)中的懲罰系數(shù)過高，最終導(dǎo)致目標(biāo)值的放大；另外， TVM-GA2算法也存在部分目標(biāo)函數(shù)值較小的情況，如表中算例m=5，(α1,α2)=(1,0)，uδ=1.0，這是由于當(dāng)種群中含有大量不可行染色體時(shí)，錯(cuò)誤的基因信息將種群進(jìn)化方向引入了歧途，遺傳算法無(wú)法過濾掉這些缺陷基因，但又為得到更小的目標(biāo)函數(shù)值，便以犧牲流程執(zhí)行時(shí)間為代價(jià)，通過將任務(wù)分配給性能更差的虛擬機(jī)換取目標(biāo)函數(shù)值的減少，因此該情況下TVM-GA2算法的租約滿足率STVM2普遍較低。

TVM-GA1在進(jìn)化中通過編碼修正算法可以有效保證租約滿足率，其解質(zhì)量相對(duì)TVM-GA2有了一定提高，然而因?yàn)榛谌蝿?wù)與虛擬機(jī)映射關(guān)系編碼規(guī)則的局限，算法在Stage-V階段計(jì)算任務(wù)集與實(shí)例集間的映射關(guān)系MapT-Vm時(shí)采用了貪心準(zhǔn)則，使算法在該階段對(duì)云資源使用成本的優(yōu)化更易陷入局部最優(yōu)，所以隨著云資源使用成本系數(shù)α2的逐漸遞增，TVM-GA1算法相比TOD-GA算法的解質(zhì)量逐漸變差。

TOD-GA在各種情況下的最優(yōu)解質(zhì)量均優(yōu)于TVM-GA1與TVM-GA2算法，這是由于該算法采用的基于任務(wù)序列劃分的兩段式編碼可統(tǒng)籌解析Stage-T階段任務(wù)集與虛擬機(jī)類型集的映射關(guān)系MapT-VMC，以及Stage-V階段任務(wù)集與實(shí)例集的映射關(guān)系MapT-Vm，將問題兩個(gè)階段的方案整合后作為整體進(jìn)行啟發(fā)式尋優(yōu)，得到面向租戶QoS與云服務(wù)提供商運(yùn)營(yíng)成本的云工作流調(diào)度最優(yōu)方案。

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

云工作流調(diào)度無(wú)論對(duì)提升租戶QoS，還是降低云服務(wù)提供商運(yùn)營(yíng)成本都具有重要意義。目前，在該領(lǐng)域已有較多有價(jià)值的研究，但如何在多租戶環(huán)境下充分考慮流程租約約束和實(shí)例負(fù)載約束，如何從博弈共贏的角度構(gòu)建云工作流的資源調(diào)度優(yōu)化，從而實(shí)現(xiàn)租戶與云服務(wù)提供商雙方利益的最優(yōu)化，在目前研究中還是一個(gè)盲點(diǎn)。本文分析了現(xiàn)有云工作流調(diào)度研究中存在的不足，在此基礎(chǔ)上以租戶流程租約和虛擬機(jī)實(shí)例負(fù)載為約束，研究面向QoS與成本感知的云工作流調(diào)度問題，分析問題在調(diào)度中涉及的兩個(gè)階段，剖析問題模型不同階段的調(diào)度策略，指出傳統(tǒng)編碼規(guī)則在調(diào)度過程中無(wú)法有效處理任務(wù)集與實(shí)例集間的映射關(guān)系，以及無(wú)法較好確認(rèn)虛擬機(jī)實(shí)例數(shù)量等問題，為此設(shè)計(jì)了一種新的編碼規(guī)則，在此基礎(chǔ)上建立TOD-GA，依據(jù)編碼特征設(shè)計(jì)遺傳算子實(shí)現(xiàn)種群的迭代進(jìn)化，并提出一種編碼約束性檢驗(yàn)與修正算法，以保證迭代進(jìn)化中種群染色體的質(zhì)量。通過與兩類傳統(tǒng)編碼規(guī)則的遺傳算法進(jìn)行多次不同規(guī)模的對(duì)比實(shí)驗(yàn)，表明本文算法得出的最優(yōu)解方案在租約滿足情況與解質(zhì)量方面均優(yōu)于其余兩類遺傳算法。

本文僅考慮了虛擬機(jī)實(shí)例的負(fù)載約束問題，在實(shí)際調(diào)度中，云資源的分配還存在負(fù)載均衡問題，如何在得出的方案中進(jìn)一步實(shí)現(xiàn)負(fù)載均衡優(yōu)化，將是下一步值得研究的問題。

[1] YU Le, ZHAO Shuai, ZHANG Yang, et al. Application of cloud workflow technologies in business intelligence SaaS platform[J]. Computer Integrated Manufacturing Systems,2013,19(8):1738-1747(in Chinese).[于 樂,趙 帥,章 洋,等.云工作流技術(shù)在商業(yè)智能SaaS中的應(yīng)用[J].計(jì)算機(jī)集成制造系統(tǒng),2013,19(8):1738-1747.]

[2] SHANG Shifeng, JIANG Jinlei, ZHENG Weimin. CWFlow:a cloud-based workflow framework with adaptive resource utilization[J]. Journal of Tsinghua University,2013,53(3):415-420(in Chinese).[尚世鋒,姜進(jìn)磊,鄭緯民.CWFlow:支持資源自適應(yīng)使用的云工作流框架[J].清華大學(xué)學(xué)報(bào),2013,53(3):415-420.]

[3] HUANG Hua, PENG Rong, FENG Zaiwen. Cloud workflow model construction based on reflection mode and supporting multi-tenant dynamical configuration[J]. Computer Integrated Manufacturing Systems,2013,19(8):1727-1737(in Chinese).[黃 華,彭 蓉,馮在文.基于反演模式支持多租戶動(dòng)態(tài)配置的云工作流模型構(gòu)建[J].計(jì)算機(jī)集成制造系統(tǒng),2013,19(8):1727-1737.]

[4] XIAO Zhijiao, CHANG Huiyou, YI Yang. Optimization of workflow time performance through optimized resources configuration with cost constraint[J]. Journal of System Simulation,2006,18(11):3320-3323(in Chinese).[肖志嬌,常會(huì)友,衣 楊.成本約束下工作流時(shí)間最小化的資源配置優(yōu)化[J].系統(tǒng)仿真學(xué)報(bào),2006,18(11):3320-3323.]

[5] AMALARETHINAM D I G, SELVI F K M. A minimum makespan grid workflow scheduling algorithm[C]//Proceedings of International Conference on Computer Communication and Informatics. Washington, D.C.,USA:IEEE,2012:1-6.

[6] YI Yang, ZOU Tengyue, RONG Fuli. Model and algorithm for workflow resource optimization to minimize total flow time[J]. Systems Engineering and Electronics,2008,30(7):1264-1268(in Chinese).[衣 楊,鄒騰躍,容福麗.最小化流水時(shí)間的工作流資源優(yōu)化模型和算法[J].系統(tǒng)工程與電子技術(shù),2008,30(7):1264-1268.]

[7] LI Xuejun, XU Jia, ZHU Erzhou,et al. A novel computation method for adaptive inertia weight of task scheduling algorithm[J]. Computer Research and Development,2016,53(9):1990-1999(in Chinese).[李學(xué)俊,徐 佳,朱二周,等.任務(wù)調(diào)度算法中新的自適應(yīng)慣性權(quán)重計(jì)算方法[J].計(jì)算機(jī)研究與發(fā)展,2016,53(9):1990-1999.]

[8] WANG Yan, WANG Jinkuan, WANG Cuirong, et al. Modified scheduling algorithm for cloud workflow based on QoS[J]. Journal of Northeastern University,2014,35(7):939-943(in Chinese).[王 巖,汪晉寬,王翠榮,等.QoS約束的云工作流調(diào)度算法[J].東北大學(xué)學(xué)報(bào),2014,35(7):939-943.]

[9] VERMA A, KAUSHAL S. Deadline constraint heuristic-based genetic algorithm for workflow scheduling in cloud[J]. International Journal of Grid and Utility Computing,2014,5(2):96-106.

[10] ZHENG Min, CAO Jian, YAO Yan. Cloud workflow scheduling algorithm oriented to dynamic price changes[J]. Computer Integrated Manufacturing Systems,2013,19(8):1849-1858(in Chinese).[鄭 敏,曹 健,姚 艷.面向價(jià)格動(dòng)態(tài)變化的云工作流調(diào)度算法[J].計(jì)算機(jī)集成制造系統(tǒng),2013,19(8):1849-1858.]

[11] WEN Yiping, LIU Jianxun, CHEN Congyang. Privacy-aware and cost-aware workflow scheduling in clouds[J]. Computer Integrated Manufacturing Systems,2016,22(2):294-301(in Chinese).[文一憑,劉建勛,陳聰陽(yáng).隱私與成本感知的云工作流調(diào)度方法[J].計(jì)算機(jī)集成制造系統(tǒng),2016,22(2):294-301.]

[12] SHEN Hong, LI Xiaoping. Algorithm for the cloud service workflow scheduling with setup time and deadline constraints[J]. Journal on Communications,2015,36(6):183-192(in Chinese).[沈 虹,李小平.帶準(zhǔn)備時(shí)間和截止期約束的云服務(wù)工作流調(diào)度算法[J].通信學(xué)報(bào),2015,36(6):183-192.]

[13] DURILLO J, PRODAN R. Multi-objective workflow scheduling in Amazon EC2[J]. Cluster Computing,2014,17(2):169-189.

[14] MOLLAJAFARI M,SHAHHOSEINI H. A cost-optimized GA-based heuristic for scheduling time-constrained workflow applications in infrastructure clouds using an innovative feasibility-assured decoding mechanism[J]. Journal of Information Science and Engineering,2016,32(6):1541-1560.

[15] CAO Bin, WANG Xiaotong, XIONG Lirong, et al. Searching method for particle swarm optimization of cloud workflow scheduling with time constraint[J]. Computer Integrated Manufacturing Systems,2016,22(2):372-380(in Chinese).[曹 斌,王小統(tǒng),熊麗榮,等.時(shí)間約束云工作流調(diào)度的粒子群搜索方法[J].計(jì)算機(jī)集成制造系統(tǒng),2016,22(2):372-380.]

[16] WU Zhangjun, LIU Xiao, NI Zhiwei. Forecasting model for activity durations in cloud workflow based on chaotic time series[J]. Computer Integrated Manufacturing Systems,2013,19(8):1920-1927(in Chinese).[伍章俊,劉 曉,倪志偉.基于混沌時(shí)間序列的云工作流活動(dòng)運(yùn)行時(shí)間預(yù)測(cè)模型[J].計(jì)算機(jī)集成制造系統(tǒng),2013,19(8):1920-1927.]

[17] YAN Weimin, WU Weimin. Data structure[M]. Beijing:Tsinghua University Press,2007:180-183(in Chinese).[嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社,2007:180-183.]

[18] MENG Fanchao, ZHOU Xuequan, CAO Zufeng, et al. Multi-tenant SaaS application placement algorithm based on cost optimization[J]. Computer Integrated Manufacturing Systems,2014,20(6):1508-1518(in Chinese).[孟凡超,周學(xué)權(quán),曹祖鳳,等.基于成本優(yōu)化的多租戶SaaS應(yīng)用優(yōu)化放置算法[J].計(jì)算機(jī)集成制造系統(tǒng),2014,20(6):1508-1518.]

[19] WU Linlin, GARG S K, BUYYA R. SLA-based resource allocation for software as a service provider(SaaS)in cloud computing environments[C]//Proceedings of the 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Washington, D.C.,USA:IEEE Computer Society,2011:195-204.