云計算中基于改進遺傳算法的多目標(biāo)優(yōu)化調(diào)度①

王昱，左利云

(1.廣東石油化工學(xué)院 網(wǎng)絡(luò)與教育信息技術(shù)中心，廣東 茂名 525000；2.廣東石油化工學(xué)院 計算機學(xué)院，廣東 茂名 525000)

隨著云計算的普及，云數(shù)據(jù)中心的規(guī)模和數(shù)量迅猛增長，調(diào)度問題成為云計算發(fā)展的關(guān)鍵，調(diào)度策略是云計算實現(xiàn)高效計算的重要因素。對此很多學(xué)者提出了一些解決方案，如對負(fù)載進行管理[1]、對應(yīng)用數(shù)據(jù)進行劃分優(yōu)化[2]等，但無論是針對資源負(fù)載還是數(shù)據(jù)應(yīng)用，都要面對如何盡可能滿足用戶多方面需求的情況下提高調(diào)度效率。而對于這種多目標(biāo)優(yōu)化問題的求解很多學(xué)者提出了采用一些智能仿生算法來實現(xiàn)[3，4]，如非支配排序算法(NSGA-II)[5]、Pareto支配進化算法(SPEA2)[6]、基于參考信息的進化算法(PAES)[7]等。文獻[8]提出了一種偏好向量引導(dǎo)的高維目標(biāo)協(xié)同進化算法。文獻[9]提出了一種利潤敏感的空間調(diào)度方法，其主要目標(biāo)是服務(wù)商利潤最大化，它采用基于遺傳、模擬退火的粒子群優(yōu)化算法實現(xiàn)。文獻[10]針對IaaS的工作流調(diào)度問題，提出了一種進化算法來實現(xiàn)最大化完工時間和成本的優(yōu)化。文獻[11]針對云計算中任務(wù)的截止時間約束問題，提出一種基于二部圖模型的調(diào)度算法。文獻[12]針對端到端延遲約束問題提出一種啟發(fā)式調(diào)度算法。文獻[13]提出一種基于改進粒子群的優(yōu)化算法。文獻[14]為了降低任務(wù)執(zhí)行成本提出一種改進遺傳算法，它的主要目標(biāo)在于降低工作流調(diào)度的成本。文獻[15]提出了一種多目標(biāo)調(diào)度方法，它的主要優(yōu)化目標(biāo)為整個系統(tǒng)的吞吐量。文獻[16]提出了一種融合布谷鳥搜索算法與基于對立的學(xué)習(xí)算法結(jié)合的方法，以提高云計算中的性能并降低成本。這些研究多是從云計算提供方的角度出發(fā)，對云計算系統(tǒng)調(diào)度問題提出的調(diào)度方法，多目標(biāo)優(yōu)化也是針對云計算提供商的角度提出對性能和成本費用的優(yōu)化。基于此，本文將從用戶角度出發(fā)，針對用戶對截止時間和費用的需求差異，研究云計算中的任務(wù)完成時間和費用的均衡調(diào)度問題，從而提高調(diào)度完成效率并減少用戶的花費。本文提出了一種基于改進遺傳算法的調(diào)度方法，同時考慮截止時間和費用預(yù)算兩個約束條件下，盡可能實現(xiàn)時間和費用均衡最優(yōu)化。

1 系統(tǒng)模型

用戶提交任務(wù)至任務(wù)請求管理器，經(jīng)過任務(wù)預(yù)處理至調(diào)度管理器，基于改進遺傳算法的智能調(diào)度方法部署在調(diào)度管理器中，其系統(tǒng)結(jié)構(gòu)見圖1。圖1中，用戶通過用戶接口提交任務(wù)請求至請求管理器，請求管理器將任務(wù)請求信息傳輸至調(diào)度管理器，包括任務(wù)大小、所需數(shù)據(jù)量、完成的截止時間及預(yù)算費用等。調(diào)度管理器中擁有可用云資源信息，如可用資源的計算、傳輸能力和計算、傳輸價格等。任務(wù)提交至調(diào)度管理器時，調(diào)度管理器根據(jù)任務(wù)參數(shù)約束，結(jié)合資源參數(shù)等信息，采用本文提出的多目標(biāo)優(yōu)化算法得到最合適的任務(wù)資源組合，將結(jié)果返回給用戶。

圖1 系統(tǒng)結(jié)構(gòu)模型

1.1 資源描述

云計算中調(diào)度的資源，主要指虛擬機。模擬亞馬遜云服務(wù)的模式，則資源Ru為

Ru=

(1)

式中：Cu為資源計算能力，影響任務(wù)計算時間；Lu為傳輸能力，影響任務(wù)的傳輸時間；Pu為計算價格；Su為存儲價格；Qu為傳輸價格(主要指外部傳輸價格，因亞馬遜云服務(wù)中內(nèi)部傳輸不收費)。

1.2 任務(wù)描述

設(shè)任務(wù)Ti為任務(wù)請求的一個單位，每個資源一次處理一個任務(wù)。則任務(wù)Ti為

Ti=

(2)

式中：TDi為任務(wù)的截止時間；TCi為任務(wù)長度；TLi為任務(wù)計算所需信息量，直接影響任務(wù)的傳輸時間；TMi為任務(wù)的預(yù)算花費。

1.3 時間和費用模型

在任務(wù)調(diào)度時有兩個約束，分別為截止時間和費用。要滿足這兩個約束條件必須要計算調(diào)度模型中任務(wù)的完成時間和花費。

任務(wù)完成時間由任務(wù)計算時間和傳輸時間兩部分組成。此時，由式(1)、式(2)可計算任務(wù)Ti在云計算中的完成時間tiRu為

(3)

由式(3)可得，截止約束條件為tiRu≤TDi。

假設(shè)費用產(chǎn)生主要在云計算的租用上，其主要有計算費用、存儲費用和傳輸費用三部分組成。任務(wù)Ti使用云計算的花費Fi為

Fi=TCi×Pu+TLi×Qu+TLi×Su

(4)

由式(4)可得，費用約束為Fi≤TMi。

1.4 多目標(biāo)優(yōu)化調(diào)度模型

該問題的多目標(biāo)優(yōu)化模型表示如下：

(5)

(6)

s.t.tiRu≤TDi，F(xiàn)i≤TMi

(7)

式中：Ti為任務(wù)i，i=1,2,…,n;Rj為資源j，j=1,2,…,m;fij為滿足費用函數(shù)f(x)的任務(wù)資源分配對；cij為滿足時間函數(shù)c(x)的任務(wù)資源分配對。

1.5 約束處理—懲罰函數(shù)

由于約束參數(shù)與多個變量相關(guān)，為了根據(jù)約束條件更好地調(diào)整并確定相關(guān)變量，可采用柔性約束的處理方法，將懲罰項加入總的時間和費用函數(shù)中，可得到時間和費用的懲罰函數(shù)為

Ftime′(x)=F(x)+α|tiRu-TDi|，F(xiàn)cost′(x)=F(x)+β|Fi-TMi|

(8)

式中：α和β分別為時間和費用的懲罰因子。

2 基于改進遺傳算法的多目標(biāo)優(yōu)化調(diào)度方法

本優(yōu)化問題包括了費用和時間最小兩個優(yōu)化目標(biāo),同時還有截止時間、成本預(yù)算等約束條件,對于這類組合優(yōu)化問題的求解尤其是最優(yōu)解有一定難度。而改進的遺傳算法NSGA-II在解決該類優(yōu)化問題時有一定優(yōu)勢,它降低了非劣排序遺傳算法的復(fù)雜性,具有運行速度快、解集收斂性好等優(yōu)點。它在初始化階段利用初始值進行引導(dǎo),即通過單目標(biāo)遺傳算法獲取NSGA-II初始種群的部分個體,以提高算法的收斂性能。該算法的實現(xiàn)過程簡單描述如偽代碼所示。其中Xij為任務(wù)Ti在時間j時的調(diào)度變量，N為任務(wù)總數(shù)，H為時間總數(shù)。

3 實驗驗證

3.1 實驗環(huán)境及參數(shù)設(shè)置

為了驗證所提調(diào)度方法性能，在云仿真軟件Cloudsim3.0上進行仿真實驗。創(chuàng)建了兩個數(shù)據(jù)中心A和B，兩個數(shù)據(jù)中心中虛擬機數(shù)目分別為20和200，A中虛擬機的配置參數(shù)為：1個CPU，CPU計算能力為200 MIPs，內(nèi)存1 G，硬盤空間2 G，帶寬2 M/s；B中虛擬機的配置參數(shù)均為A中虛擬機配置參數(shù)的2倍。創(chuàng)建了100 ～600個隨機云任務(wù)，其任務(wù)長度為400～1000 MIPs，文件大小為200～400 MB，輸出大小為20～40 MB。

3.2 調(diào)度方法性能的評價指標(biāo)

實驗采用了三個評估指標(biāo)來評估所提調(diào)度方法的性能：任務(wù)完成時間、使用云計算的費用和截止時間超出率。將Min-Min算法[17]、基準(zhǔn)調(diào)度方法(FCFS)[18]和基于蟻群算法的多目標(biāo)調(diào)度方法MOACO，與本評價指標(biāo)中截止時間超出率用于評估超出任務(wù)截止時間的情況，其表示為

表1 兩個數(shù)據(jù)中心收費標(biāo)準(zhǔn)參數(shù)AB計算價格/(＄/h)0.0850.120存儲價格/(＄/GB)0.060.10傳輸價格/(＄/GB)0.050.10

文所提調(diào)度方法進行對比。實驗中的費用參考亞馬遜云服務(wù)的價格(見表1),計算能力等參數(shù)不同,數(shù)據(jù)中心的費用也不同。云計算的費用是根據(jù)任務(wù)計算時間折合計算量,存儲和傳輸費用則根據(jù)任務(wù)本身存儲和傳輸大小統(tǒng)計。

(9)

式中：nv為超出截止時間的任務(wù)數(shù)；n為總?cè)蝿?wù)數(shù)。

3.3 各種方法的調(diào)度完成時間

本實驗中完成時間是在不超過任務(wù)截止時間情況下執(zhí)行任務(wù)花費的時間，通過20次實驗取平均值得到4種方法(MONSGA、MOACO、Min-Min和FCFS)在任務(wù)數(shù)為100～600范圍內(nèi)的完成時間，見圖2。并通過任務(wù)的完成時間來評估4種方法的調(diào)度效果。

圖2 完成時間

由圖2可知，MONSGA表現(xiàn)最好，MOACO次之，尤其是隨著任務(wù)的增多，這兩種方法的優(yōu)勢越明顯。而這4種算法中，F(xiàn)CFS的效果最差。Min-Min算法雖然在完成時間方面較有優(yōu)勢，但隨著任務(wù)的增多其表現(xiàn)不如多目標(biāo)優(yōu)化的仿生算法MONSGA和MOACO，這是由于MONSGA和MOACO算法能隨著代數(shù)增加智能調(diào)整逼近最優(yōu)解，實現(xiàn)多目標(biāo)間的均衡優(yōu)化。而由于MONSGA懲罰因子的增加，并對初始值進行了引導(dǎo)，使得其效果更優(yōu)于MOACO。

3.4 各種方法的費用

為了評估4種方法使用云計算的費用情況，實驗分兩種情況，即在任務(wù)數(shù)分別為200和500時根據(jù)任務(wù)的不同截止時間約束，評估其費用情況，實驗結(jié)果見圖3和圖4。

圖3 200個任務(wù)時的費用 圖4 500個任務(wù)時的費用

由圖3、圖4可知，這4種方法中MONSGA的費用最小，MOACO次之，Min-Min費用最高，這是由于Min-Min算法的目標(biāo)是完成時間最優(yōu)，它總優(yōu)先調(diào)度優(yōu)勢資源，導(dǎo)致費用最高。而MONSGA和MOACO追求多目標(biāo)優(yōu)化，從而實現(xiàn)費用與時間的均衡，其費用相對較少，二者相比，由于MONSGA對初始值進行了引導(dǎo)，其效果比MOACO更好。

3.5 截止時間違反率

設(shè)置任務(wù)為500，截止時間為100～3000 s。通過實驗驗證截止時間超出率這一指標(biāo)，其結(jié)果見圖5。

由圖5可知，截止時間違反率也是MONSGA和MOACO表現(xiàn)最好，由于這兩個多目標(biāo)優(yōu)化算法都考慮了截止時間約束問題。且二者中，MONSGA表現(xiàn)最好，MOACO次之。而Min-Min算法由于追求完成時間最優(yōu)，導(dǎo)致一些大任務(wù)違反截止時間。

圖5 截止時間違反率

4 結(jié)語

為實現(xiàn)云計算中調(diào)度完成時間與費用的均衡優(yōu)化問題，本文提出了一種基于改進遺傳算法的調(diào)度優(yōu)化方法——MONSGA，以任務(wù)的完成時間和費用為目標(biāo)，考慮截止時間和費用預(yù)算約束，并將其與MOACO算法、FCFS算法、Min-Min算法進行對比。結(jié)果顯示，提出的調(diào)度方法MONSGA在完成時間、費用、截止時間違反率三個評估方面均表現(xiàn)最好，且這種優(yōu)勢隨著任務(wù)數(shù)的增加而更明顯。