林 濤, 王 昊, 李 鵬

(河北工業(yè)大學 人工智能與數(shù)據(jù)科學學院,天津 300130)

0 引 言

云計算是一種基于分布式計算、并行計算和網(wǎng)格計算的新型的商業(yè)計算模式[1]。云計算采用服務的方式為用戶提供動態(tài)虛擬化資源池[2],可以將用戶提交的任務分配給分布式計算機資源池進行合理調(diào)度。由于資源是有限的,因此云計算系統(tǒng)服務是有償?shù)腫3,4],在海量數(shù)據(jù)面前,云計算任務的調(diào)度成為影響云計算系統(tǒng)性能的關鍵因素,也決定了完成用戶任務的成本,因此,如何充分利用云中資源對任務進行高效調(diào)度是云計算中的重點和難點。

近幾年,一些人工智能算法已經(jīng)被廣泛的應用到任務調(diào)度問題中。文獻[5]提出了一種完全多項式的在線算法,并采用整數(shù)規(guī)劃方式減少應用程序延遲,優(yōu)化云計算任務的卸載和調(diào)度策略,從而最大化節(jié)約資源。文獻[6]將網(wǎng)絡存儲感知和貪心算法相結合,提出了一種貪心改進算法,大幅減少了數(shù)據(jù)在數(shù)據(jù)鏈路層所消耗的時間。文獻[7]提出了一種多目標調(diào)度方案,即MOCS,實現(xiàn)了云計算環(huán)境下的低功耗和調(diào)度效率的優(yōu)化。文獻[8]針對資源虛擬化環(huán)境中的混合型負載調(diào)度問題,采用“最小能耗比例優(yōu)先”的策略進行調(diào)度,在“調(diào)度偏差”和“相對能效”兩方面優(yōu)勢明顯。但這些方法在處理海量任務調(diào)度方面的效果均不夠理想,且考慮影響因素過于單一。

本文通過分析云計算任務資源分配問題,綜合考慮任務完成時間和執(zhí)行能耗等因素,采用改進的差分進化算法制定合適的任務調(diào)度機制,以期快速而高效地為虛擬機資源盡可能地均衡分配任務。仿真實驗的結果表明,本文提出的基于改進差分進化算法的云計算任務調(diào)度算法有效減少了云計算任務的完成時間,并大幅降低了任務的執(zhí)行能耗。

1 云計算獨立任務調(diào)度模型

云計算平臺是在“需求付費”的原則下可同時為多個用戶提供服務,且滿足用戶的多服務質(zhì)量(quality of service,QoS)目標約束條件[9,10],但云計算在滿足用戶的同時,還應提高云服務提供商的收益。該調(diào)度模型著重考慮用戶所關心的完成時間以及云服務提供商在意的能耗。

1.1 變量描述

任務調(diào)度是根據(jù)一定的約束規(guī)則將應用任務集與可用資源集建立的一種合理映射的關系。云環(huán)境下的任務分配目標是將M個任務合理的派發(fā)給云服務器上N個可利用的資源進行執(zhí)行,盡可能減少任務的執(zhí)行時間和執(zhí)行能耗。R為資源節(jié)點rj的集合j∈[1,n],其中,n為云服務器可利用的資源數(shù)量；T為應用任務ti的集合,i∈[1,m],m為待調(diào)度計算任務的數(shù)量。通常,在任務調(diào)度過程中可用資源節(jié)點數(shù)量遠遠小于參與調(diào)度的任務數(shù)量,即r?m。

將云計算任務調(diào)度問題用一個四元數(shù)組∑:(T,P,TIME,E)進行描述,其中，T為待調(diào)度的計算任務集合；P為m×n的任務分配矩陣,矩陣P中的元素pij=1表示計算任務ti在資源節(jié)點rj上執(zhí)行,否則pij=0；時間執(zhí)行矩陣TIME是一個m×n的矩陣,其元素timeij表示計算任務ti在資源節(jié)點rj上的執(zhí)行時間；E為m×n的能量消耗矩陣,其元素eij表示任務ti在資源節(jié)點rj上執(zhí)行消耗的能量。

1.2 任務建模

任務完成時間是指任務提交到任務完成,并將調(diào)度完成后的結果反饋給用戶的時間間隔。由于計算任務是并行執(zhí)行的,因此任務完成時間定義為所有計算任務中完成時間最長的任務所用時間

(1)

執(zhí)行能耗是指任務執(zhí)行完后,每個虛擬資源因執(zhí)行任務而消耗的能量。每個調(diào)度方案中所有任務執(zhí)行完成后所消耗的能耗定義為

(2)

式中eij為任務在云服務器上的執(zhí)行能耗,eij=Ecpu·timeij。其中，Ecpu為云服務器CPU能耗,該執(zhí)行能耗與CPU的利用率呈線性關系[11],Ecpu=αcpu·ucpu+γcpu。其中，ucpu為CPU利用率,αcpu和γcpu分別為CPU能耗公式中的固定系數(shù)。

以降低執(zhí)行能耗與任務完成時間為目標,得到的云計算的任務調(diào)度目標函數(shù)可以稱為最小化問題

minf(x)=λ1*AllTime(x)+λ2*EC(x)

(3)

式中λ1,λ2分別為任務完成時間、執(zhí)行能耗的權重,且滿足λ1+λ2=1,λ1>0,λ2>0。

2 改進的差分進化算法

本文提出了一種改進的差分進化算法,基于Levy分布的自適應差分進化(Levy-based adaptive differential evolution,LADE)算法,并將其應用于求解云計算任務調(diào)度問題。

2.1 染色體編碼

本文結合云計算任務調(diào)度的特點,采用資源—任務的間接編碼方式,用戶的計算任務總數(shù)量為染色體長度,每個基因代表一個計算任務,該基因位的位值代表該計算任務分配到相應資源的資源編號。染色體最終編碼格式如圖1所示,ti表示任務編號,i∈[1,m],rj表示資源編號,j∈[1,n]。

圖1 染色體編碼格式

按照上圖的編碼方式可以得到對應的解碼為r3:{t1},r1:{t2},r2:{t3},…,rn:{tm}，由此可以得出,每一條染色體對應一種任務的調(diào)度方案。

2.2 變異操作

本文采用隨機選取種群中兩個不同的個體與待變異個體進行向量合成,產(chǎn)生中間個體Vi(g+1),即

vi(g+1)=xi(g)+F[i]×(xp1(g)-xp2(g))

(4)

式中g為進化代數(shù),xi(g)為第g代種群中第i個個體,xp1(g),xp2(g)分別為第g代種群中隨機選取的兩個不同個體。F[i]為每個個體特定的縮放因子,滿足取值范圍為[0,1]的柯西分布[12]

Fi=CauchyRandom(μF,0.1)

(5)

μF的更新方式

μF=(1-c)·μF+c·meanL(SF)

(6)

式中SF為所有成功變異的個體的F值的集合,meanL(?)為Lehmer均值[12]

meanL(SF)=∑FeSFF2∑FeSFF

(7)

2.3 交叉操作

對第g代個體{xi(g)}及其變異的中間體{vi(g+1)}進行交叉操作

(8)

式中jrand為[1,2,…,D]為的隨機整數(shù)。每個個體i均有特定的交叉概率CR[i],滿足Levy分布,其概率密度函數(shù)[13]

(9)

式中α,γ為Levy分布的2個特征參數(shù)；0<α≤2,γ>0。

2.4 貪婪選擇

DE采用貪婪算法來選擇進入下一代種群的個體,選取適應值更好的個體進入下一代,本文中,由于任務調(diào)度問題屬于最小化問題,因此,選取適應值較小的個體進入下一代

(10)

2.5 DE任務調(diào)度算法的總流程

結合前文建立的多用戶任務調(diào)度模型,得到改進之后的DE算法流程圖如圖3所示。

圖3 算法流程

3 實驗結果與分析

設計了2個實驗方案：一是選取測試函數(shù)對比其他算法,驗證本算法尋優(yōu)的優(yōu)越性；二是在Windows操作系統(tǒng)下,主頻為2.5 GHz,采用Cloudsim-3.0.2[14]云計算模擬平臺對本文算法的實際調(diào)度性能進行模擬仿真,并與傳統(tǒng)DE[15]算法和jDE[16]算法進行比較。實驗中通過改變?nèi)蝿諈?shù)來測試在不同計算任務數(shù)下算法的表現(xiàn)性能。

3.1 尋優(yōu)測試

采用3個準測試函數(shù)：Sphere、Rosenbrock和Rastrigin對傳統(tǒng)DE算法、jDE算法和LADE算法的性能進行了對比測試,所有算法的運行結果如圖4所示。

圖4 三種算法對三個準函數(shù)的尋優(yōu)收斂曲線

對圖4的分析可以看出,對3個準測試函數(shù),LADE算法的性能均優(yōu)于其他兩個算法,對比結果表明,不管對于單峰函數(shù)還是多峰函數(shù),LADE算法在迭代次數(shù)范圍內(nèi)表現(xiàn)出了良好的性能,目標函數(shù)值曲線下降速度快,尋優(yōu)精度高,在一定程度彌補了算法易陷入局部最優(yōu)的不足。

3.2 云計算調(diào)度測試

將設計的LADE算法在云計算模擬平臺Cloudsim上進行模擬仿真。實驗時所用的具體參數(shù)設置如表1。

為了盡量避免誤差,本文將每組實驗都進行10次,實驗結果如圖5。

表1 仿真實驗各種類數(shù)據(jù)參數(shù)

圖5 不同任務數(shù)量下三種調(diào)度策略任務仿真結果

由圖5中可以看出,在計算資源不變的情況下,任務數(shù)量很小時,LADE和標準DE、jDE算法的差別不大,都能找到近似最優(yōu)解。但隨著任務數(shù)量的增多,調(diào)度復雜度也隨之上升,LADE算法相比其他兩個調(diào)度算法的優(yōu)勢愈加明顯,說明LADE算法在任務數(shù)量多,復雜度高的環(huán)境下依然具有良好的調(diào)度性能。

表2顯示了DE、jDE和LADE等3種算法分別在任務數(shù)為100,200,300,400,500時得到的適應值的均值、最大值、最小值、中值、標準差的對比結果。由表2可以看出,相較于其他兩種算法,LADE得到的適應值對于所有的任務數(shù)都表現(xiàn)出了它的優(yōu)勢。當任務數(shù)為100時,LADE取得的適應值均值為1.74×103,其中最優(yōu)的適應值為1.65×103,而其他兩種算法最優(yōu)的適應值為1.92×103；隨著任務數(shù)的不斷增加,當任務數(shù)為500時,LADE取得的適應值均值為9.38×103,其中,最優(yōu)的適應值為9.21×103,而其他兩種算法最優(yōu)的適應值為1.06×104。可以看出,LADE在進化初期就有著很強的全局搜索能力,隨著任務數(shù)越來越多,難度的提高,適應值相差也越來越多,LADE的優(yōu)勢也就越加明顯。

另外,由表2還可以看出,隨著任務數(shù)的不斷增加,適應值也越來越大,這是因為任務數(shù)增加,相應的執(zhí)行時間和執(zhí)行能耗也會增加,對應的適應值也會隨之增大。但是,對于不同的任務數(shù)量,LADE均表現(xiàn)出其明顯優(yōu)勢。

表2 三種算法適應值對比結果

4 結束語

實驗結果證明：相對于傳統(tǒng)DE算法和jDE算法,本文算法在計算資源有限,復雜度高的情況下的計算任務調(diào)度具有較明顯的優(yōu)勢,能大幅減少任務的完成時間和執(zhí)行能耗,在現(xiàn)代大規(guī)模云計算中有著廣泛的應用前景。