人工蜂群算法改進(jìn)水波優(yōu)化算法的云資源調(diào)度性能

宋 穎, 梁衛(wèi)芳, 趙 玨, 張福泉, 侯小毛

(1.湖南信息學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院, 湖南 長(zhǎng)沙 410151, 中國(guó);2.湖南工商大學(xué) 計(jì)算機(jī)學(xué)院, 湖南 長(zhǎng)沙 410205, 中國(guó); 3.菲律賓國(guó)家大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院, 馬尼拉 0900, 菲律賓;4. 閩江學(xué)院 計(jì)算機(jī)與控制工程學(xué)院, 福建 福州 350108, 中國(guó); 5. 湖南化工職業(yè)技術(shù)學(xué)院 自動(dòng)化與信息工程學(xué)院, 湖南 株洲 412000, 中國(guó))

云計(jì)算是當(dāng)前大數(shù)據(jù)服務(wù)端的主要形式之一,云端所有資源經(jīng)虛擬化后被統(tǒng)一管理、分配給使用云平臺(tái)的所有任務(wù)[1]。對(duì)于云計(jì)算的用戶端來(lái)說(shuō),用戶最關(guān)心任務(wù)的是執(zhí)行時(shí)間及服務(wù)質(zhì)量,而云計(jì)算服務(wù)端希望采用最少的資源來(lái)提供用戶滿意的服務(wù),這兩者均與云資源的合理調(diào)度有關(guān)。云資源調(diào)度使資源和任務(wù)的動(dòng)態(tài)分配得以實(shí)現(xiàn)[2]。當(dāng)資源量相對(duì)于任務(wù)量較充裕時(shí),用戶端的實(shí)時(shí)訪問(wèn)需求比較容易滿足,但是實(shí)際情況是,為了節(jié)省能耗和降低計(jì)算資源成本,云計(jì)算服務(wù)端所提供的資源量往往有限。目前關(guān)于云資源調(diào)度的研究主要是集中在資源量受限的情況下采用各種算法來(lái)實(shí)現(xiàn)資源-任務(wù)的動(dòng)態(tài)精細(xì)分配。

當(dāng)前,關(guān)于云資源調(diào)度的研究較多,其中的一個(gè)重要研究方向就是各種群智能算法在云資源調(diào)度場(chǎng)景中的應(yīng)用。例如,孫力等[3]將量子遺傳算法和蟻群優(yōu)化算法組合用于云資源調(diào)度,通過(guò)群智能算法搜索最佳調(diào)度參數(shù)組合,即最優(yōu)個(gè)體。鄭春梅等[4]采用差分進(jìn)化算法用于云資源調(diào)度,并且為了提高調(diào)度效率,對(duì)差分縮放因子進(jìn)行自適應(yīng)優(yōu)化。上述研究均采用群智能算法來(lái)實(shí)現(xiàn)云資源調(diào)度,表現(xiàn)出了較好的執(zhí)行效率,但是,這2種云資源調(diào)度算法均側(cè)重于調(diào)度時(shí)間,僅將調(diào)度執(zhí)行時(shí)間作為目標(biāo)函數(shù)進(jìn)行優(yōu)化,沒(méi)有考慮任務(wù)成本或者負(fù)載均衡等指標(biāo),而且調(diào)度的任務(wù)數(shù)量并不多。

本文中嘗試將水波優(yōu)化(water wave optimization,WWO)算法[5]應(yīng)用于多目標(biāo)函數(shù)的云資源調(diào)度,將資源-任務(wù)集抽象成多個(gè)水波個(gè)體,通過(guò)水波的運(yùn)動(dòng)操作來(lái)求解資源-任務(wù)分配的最優(yōu)個(gè)體,從而獲得調(diào)度分配參數(shù)組合。為了改善WWO算法的資源調(diào)度性能,將人工蜂群(artificial bee colony,ABC)算法用于WWO算法的核心參數(shù)優(yōu)化求解,通過(guò)ABC算法的蜜源搜索優(yōu)化方式,獲得最優(yōu)核心參數(shù),以最優(yōu)核心參數(shù)構(gòu)建的云資源調(diào)度模型,力求資源調(diào)度性能更好。與標(biāo)準(zhǔn)WWO算法相比,ABC-WWO算法的承載任務(wù)量分布更均勻且負(fù)載均衡指標(biāo)更小。

1 WWO算法

WWO算法主要是通過(guò)水波的3種運(yùn)動(dòng)方式來(lái)實(shí)現(xiàn)優(yōu)化求解。

(1)

波長(zhǎng)更新方式[6]為

λ′=λα-(f(x)-fmin+ε)/(fmax-fmin+ε),

(2)

式中:λ′為更新后的波長(zhǎng);α為水波衰減系數(shù);ε為大于0且近似于0的數(shù)。

2)折射操作。設(shè)水波xd服從高斯隨機(jī)分布函數(shù)N(μ,σ),

(3)

(4)

式中μ、σ分別為均值和標(biāo)準(zhǔn)差。

(5)

波長(zhǎng)求解公式[8]為

(6)

(7)

式中β為碎波系數(shù)。

2 基于ABC-WWO算法的云資源調(diào)度模型

2.1 ABC-WWO算法

ABC算法通過(guò)蜜蜂的蜜源i搜索完成既定范圍內(nèi)的尋優(yōu)操作。設(shè)蜜蜂總維度為D,偵測(cè)蜂在第d維搜索邊界[Ld,Ud]的運(yùn)動(dòng)位置為Xid[10],

Xid=Ld+rand(0, 1)×(Ud-Ld)。

(8)

假設(shè)蜜源i的第d維坐標(biāo)為Vid,偵測(cè)蜂Xid尋找蜜源的移動(dòng)操作[11]為

Vid=Xid+φ(Xid-Xjd),

(9)

式中j≠i,表示不同于蜜源i的另一個(gè)蜜源;φ為[1,1]的隨機(jī)值;Xjd為搜索邊界[Ld,Ud]內(nèi)排除Xid以外的任意坐標(biāo)。

偵測(cè)蜂每運(yùn)行一次將其記錄的舊蜜源和新蜜源Vi=[Vi1,Vi2,,Vid]進(jìn)行適應(yīng)度值對(duì)比,以更新蜜源,適應(yīng)度求解函數(shù)Fi[12]為

(10)

式中fi為第i個(gè)蜜源的適應(yīng)度,對(duì)比Vi和Xi,選擇兩者適應(yīng)度高的作為新蜜源。

偵測(cè)蜂將蜜源信息廣播給追隨蜂,追隨蜂有自由選擇蜜源的權(quán)利,按照概率pi選擇蜜源[13],即

(11)

式中S為偵測(cè)蜂獲得的所有蜜源數(shù)。

當(dāng)?shù)螖?shù)G滿足時(shí)G=Gmax,輸出當(dāng)前蜜源坐標(biāo)即為最優(yōu)解,算法停止,否則轉(zhuǎn)到式(8)—(11)繼續(xù)迭代。

2.2 云資源調(diào)度模型的構(gòu)建

云資源調(diào)度模型的主要任務(wù)是將n個(gè)任務(wù)分配至m個(gè)云資源中,因此,首先需要根據(jù)任務(wù)的執(zhí)行的資源需要,可以構(gòu)建任務(wù)-資源矩陣,其中第t個(gè)任務(wù)對(duì)第r個(gè)資源的執(zhí)行時(shí)間為M(t,r),則任務(wù)t在資源r上的執(zhí)行完畢時(shí)間Mct(t,r)為

Mct(t,r)=Ms(r)+M(t,r),

(12)

式中Ms(r)為資源r開(kāi)始被使用的時(shí)間。若任務(wù)t只需要使用資源r,那么任務(wù)t的整個(gè)執(zhí)行時(shí)間Ct為

Ct=Mct(t,r)。

(13)

當(dāng)云計(jì)算服務(wù)平臺(tái)的任務(wù)并行執(zhí)行時(shí),云資源調(diào)度模型中所有任務(wù)的調(diào)度時(shí)間M為

(14)

在式(12)中, 任務(wù)t的執(zhí)行時(shí)間只使用了1個(gè)資源(資源r), 當(dāng)任務(wù)需要使用多個(gè)資源時(shí), 云資源調(diào)度模型將變得復(fù)雜。在云資源調(diào)度模型的優(yōu)化研究中, 常將所有任務(wù)調(diào)度時(shí)間作為優(yōu)化的目標(biāo)函數(shù)。僅將單一的調(diào)度時(shí)間作為目標(biāo)函數(shù)不符合云計(jì)算的現(xiàn)狀。 為了解決這個(gè)問(wèn)題, 本文中云資源調(diào)度模型將云計(jì)算任務(wù)調(diào)度時(shí)間、調(diào)度成本及負(fù)載均衡度作為云資源調(diào)度優(yōu)化的目標(biāo), 提高云資源調(diào)度性能。

設(shè)該模型的任務(wù)t使用的r個(gè)虛擬機(jī)資源Vr的成本為Rcu(t,r),那么所有任務(wù)的成本Q為

(15)

模型的負(fù)載均衡指標(biāo)Id為

Id=(Cmax-Cmin)/Cave,

(16)

式中Cmax、Cmin和Cave分別為所有云資源調(diào)度任務(wù)中執(zhí)行時(shí)間的最大值、最小值和平均值。

綜上,所提云資源調(diào)度模型的優(yōu)化目標(biāo)變?yōu)?/p>

F=λ1M+λ2Q+λ3DI,
s.t.λ1+λ2+λ3=1 ,

(17)

式中λ1、λ2和λ3分別為3個(gè)優(yōu)化指標(biāo)的權(quán)重系數(shù)。

2.3 模型的執(zhí)行流程

基于ABC-WWO算法的云資源調(diào)度流程如圖1所示。初始化云資源調(diào)度模型的實(shí)例參數(shù)組合,將任務(wù)、資源、任務(wù)的資源使用時(shí)間及資源的成本量化并抽象化為不同的水波。WWO算法的適應(yīng)度函數(shù)為云資源調(diào)度的所有任務(wù)完成時(shí)間、虛擬機(jī)使用成本和負(fù)載均衡指標(biāo)加權(quán)之和的最小值。計(jì)算所有水波適應(yīng)度,并執(zhí)行水波優(yōu)化操作。不斷更新水波群的最大適應(yīng)度,且將水波衰減系數(shù)α和碎波系數(shù)β作為ABC算法的優(yōu)化對(duì)象,從而得到最優(yōu)個(gè)體,即所需云資源調(diào)度參數(shù)組合。

圖1 基于人工蜂群-水波優(yōu)化算法的云資源調(diào)度流程

3 實(shí)例仿真

為了驗(yàn)證ABC-WWO算法在云資源調(diào)度中的性能, 進(jìn)行實(shí)例仿真, 仿真平臺(tái)為Cloud Sim, 其中仿真平臺(tái)提供的任務(wù)數(shù)量為30～1 000, 參與計(jì)算的虛擬機(jī)數(shù)量為10～100, 所有參與運(yùn)算的虛擬機(jī)配置及優(yōu)先級(jí)均相同, 仿真資源具體配置如表1所示。

表1 仿真平臺(tái)配置

3.1 WWO的改進(jìn)性能

為了驗(yàn)證ABC算法對(duì)WWO的改進(jìn)性能,分別采用WWO、 ABC-WWO算法進(jìn)行云資源調(diào)度性能仿真,虛擬機(jī)資源數(shù)量為m=10,任務(wù)執(zhí)行時(shí)間如圖2所示。從圖中可以看出,在虛擬機(jī)資源數(shù)量一定時(shí),任務(wù)數(shù)量的增多將導(dǎo)致云資源調(diào)度的時(shí)間增加,對(duì)比WWO、 ABC-WWO算法發(fā)現(xiàn),在任務(wù)數(shù)量小于100時(shí),兩者的資源調(diào)度時(shí)間非常接近。當(dāng)任務(wù)數(shù)量為100～600時(shí),兩者的調(diào)度時(shí)間雖然都在增加,但WWO算法執(zhí)行時(shí)間增加更快,2種算法的執(zhí)行時(shí)間差距逐漸增大,表明經(jīng)過(guò)ABC優(yōu)化后,WWO算法的云資源調(diào)度執(zhí)行時(shí)間明顯縮短。

圖2 水波優(yōu)化(WWO)算法和人工蜂群(ABC)-WWO算法的云資源調(diào)度時(shí)間對(duì)比

對(duì)2種算法的負(fù)載均衡性能進(jìn)行仿真,差異化設(shè)置任務(wù)數(shù)量,其中10臺(tái)虛擬機(jī)資源分別所承載的任務(wù)數(shù)量統(tǒng)計(jì)結(jié)果如表2所示。

表2 水波優(yōu)化(WWO)算法和人工蜂群(ABC)-WWO算法的承載任務(wù)量

從表2中可以看出,在相同任務(wù)的虛擬機(jī)資源調(diào)度時(shí),與WWO算法相比,ABC-WWO算法的任務(wù)量分配明顯更均勻,當(dāng)任務(wù)量為100時(shí),WWO算法給虛擬機(jī)6分配了18個(gè)任務(wù),而給虛擬機(jī)10僅分配了3個(gè)任務(wù),這種任務(wù)分配數(shù)量差距過(guò)大的情況將導(dǎo)致不同虛擬機(jī)“忙”和“閑”分布不均,導(dǎo)致云資源調(diào)度性能不佳。當(dāng)任務(wù)量大于100時(shí),WWO算法的調(diào)度分配趨于平衡,但與ABC-WWO算法相比,其分配均衡性明顯較差。

繼續(xù)對(duì)2種算法的負(fù)載均衡指標(biāo)進(jìn)行性能仿真,進(jìn)一步驗(yàn)證2種算法的調(diào)度均衡性能,結(jié)果如圖3所示。由圖可見(jiàn),隨著任務(wù)量的變化,WWO算法的負(fù)載均衡指標(biāo)值明顯大于ABC-WWO算法的,表明WWO算法的執(zhí)行時(shí)間最大值和最小值差值較大,其云資源調(diào)度的均衡能力較ABC-WWO算法差。從圖中還可以看出,負(fù)載均衡指標(biāo)與任務(wù)量的關(guān)系不明晰,兩者沒(méi)有呈現(xiàn)規(guī)律性變化。

圖3 水波優(yōu)化(WWO)算法和人工蜂群(ABC)-WWO算法的負(fù)載均衡指標(biāo)

3.2 不同算法的云資源調(diào)度性能

為了驗(yàn)證不同調(diào)度算法的云資源調(diào)度性能,分別與采用蟻群優(yōu)化(ACO)算法[14]、 粒子群優(yōu)化(PSO)算法[15]、 螢火蟲算法(FA)[16]與ABC-WWO算法的云資源調(diào)度模型進(jìn)行仿真對(duì)比。

3.2.1 不同任務(wù)數(shù)量的調(diào)度性能

設(shè)置資源個(gè)數(shù)為50,差異化設(shè)置使用云資源的任務(wù)數(shù)量,驗(yàn)證不同算法的資源調(diào)度時(shí)間,結(jié)果如圖4所示。由圖可以看出:當(dāng)任務(wù)數(shù)量小于200時(shí),4種算法的執(zhí)行時(shí)間非常接近,主要原因是虛擬機(jī)資源數(shù)量為50,與任務(wù)數(shù)量相比,虛擬機(jī)資源比較充裕,調(diào)度算法的性能差異不是特別明顯;當(dāng)任務(wù)數(shù)量為200～1 000時(shí),4種算法的執(zhí)行時(shí)間差異度明顯增大,ACO算法耗時(shí)最長(zhǎng),FA算法略優(yōu)于PSO算法,ABC-WWO算法最省時(shí),表明ABC-WWO算法的云資源調(diào)度性能最優(yōu)。

ACO—蟻群優(yōu)化算法; PSO—粒子群優(yōu)化算法;FA—螢火蟲算法; ABC-WWO—人工蜂群-水波優(yōu)化算法。圖4 資源數(shù)量相同時(shí)不同云資源調(diào)度算法的執(zhí)行時(shí)間

3.2.2 不同資源數(shù)量的調(diào)度性能

為了驗(yàn)證4種算法在不同資源數(shù)量時(shí)的云資源調(diào)度性能,差異化設(shè)置參與云計(jì)算的虛擬主機(jī)數(shù)量,任務(wù)數(shù)量設(shè)置為1 000,驗(yàn)證不同算法的資源調(diào)度時(shí)間,結(jié)果見(jiàn)圖5。從圖中可以看出,隨著虛擬主機(jī)數(shù)量的變化,ABC-WWO算法的執(zhí)行時(shí)間最短,FA算法的次之,ACO算法的最長(zhǎng)。當(dāng)資源數(shù)量小于60時(shí),4種算法的執(zhí)行時(shí)間差異較明顯;當(dāng)資源數(shù)量為60～100時(shí),4種算法的執(zhí)行時(shí)間差異度明顯減小,原因是虛擬機(jī)資源數(shù)量增加,各種調(diào)度算法的優(yōu)化性能體現(xiàn)不是特別明顯。綜上所述,在對(duì)云資源進(jìn)行調(diào)度時(shí),云服務(wù)平臺(tái)本身的資源數(shù)量對(duì)執(zhí)行時(shí)間的影響最為關(guān)鍵,但在資源數(shù)量有限時(shí),調(diào)度算法的尋優(yōu)能力就變得尤為重要。

ACO—蟻群優(yōu)化算法; PSO—粒子群優(yōu)化算法;FA—螢火蟲算法; ABC-WWO—人工蜂群-水波優(yōu)化算法。圖5 任務(wù)數(shù)量相同時(shí)不同云資源調(diào)度算法的執(zhí)行時(shí)間

3.2.3 收斂性能

對(duì)4種不同算法的收斂性能進(jìn)行仿真, 驗(yàn)證在資源數(shù)量為50時(shí)不同算法的資源調(diào)度穩(wěn)定性及效率, 結(jié)果如圖6所示。 由圖可以看出, 雖然任務(wù)數(shù)量的變化對(duì)4種算法的云資源調(diào)度執(zhí)行時(shí)間影響明顯, 但4種算法的迭代次數(shù)差異并不大。 當(dāng)任務(wù)數(shù)量為100、 200時(shí), 4種算法的執(zhí)行時(shí)間在迭代80次后達(dá)到穩(wěn)定; 當(dāng)任務(wù)數(shù)量為500、 800時(shí),4種算法的執(zhí)行時(shí)間均在迭代90次左右達(dá)到穩(wěn)定。 總之, 從資源調(diào)度穩(wěn)定性來(lái)看, 4種算法差距較小, 但從資源調(diào)度的執(zhí)行時(shí)間來(lái)看, ABC-WWO算法仍占優(yōu)勢(shì)。

4 結(jié)語(yǔ)

采用ABC-WWO算法用于云資源調(diào)度, 通過(guò)ABC算法對(duì)水波衰減系數(shù)和碎波系數(shù)的優(yōu)化求解, 有效提高了WWO算法在云資源調(diào)度中的適用性, 相比于基于常用算法的云資源調(diào)度模型, 在相同任務(wù)數(shù)量或者相同資源數(shù)量的條件下, 采用ABC-WWO算法均能夠獲得更優(yōu)的調(diào)度性能, 且云服務(wù)平臺(tái)虛擬機(jī)資源負(fù)載均衡性方面更為出色,特別適用于云資源的大規(guī)模調(diào)度。