云計算中基于改進遺傳算法的多目標優化調度①

王昱，左利云

(1.廣東石油化工學院 網絡與教育信息技術中心，廣東 茂名 525000；2.廣東石油化工學院 計算機學院，廣東 茂名 525000)

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

1 系統模型

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

圖1 系統結構模型

1.1 資源描述

云計算中調度的資源，主要指虛擬機。模擬亞馬遜云服務的模式，則資源Ru為

Ru=

(1)

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

1.2 任務描述

設任務Ti為任務請求的一個單位，每個資源一次處理一個任務。則任務Ti為

Ti=

(2)

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

1.3 時間和費用模型

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

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

(3)

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

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

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

(4)

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

1.4 多目標優化調度模型

該問題的多目標優化模型表示如下：

(5)

(6)

s.t.tiRu≤TDi，Fi≤TMi

(7)

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

1.5 約束處理—懲罰函數

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

Ftime′(x)=F(x)+α|tiRu-TDi|，Fcost′(x)=F(x)+β|Fi-TMi|

(8)

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

2 基于改進遺傳算法的多目標優化調度方法

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

3 實驗驗證

3.1 實驗環境及參數設置

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

3.2 調度方法性能的評價指標

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

表1 兩個數據中心收費標準參數AB計算價格/(＄/h)0.0850.120存儲價格/(＄/GB)0.060.10傳輸價格/(＄/GB)0.050.10

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

(9)

式中：nv為超出截止時間的任務數；n為總任務數。

3.3 各種方法的調度完成時間

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

圖2 完成時間

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

3.4 各種方法的費用

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

圖3 200個任務時的費用 圖4 500個任務時的費用

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

3.5 截止時間違反率

設置任務為500，截止時間為100～3000 s。通過實驗驗證截止時間超出率這一指標，其結果見圖5。

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

圖5 截止時間違反率

4 結語

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