人工蜂群算法改進水波優化算法的云資源調度性能

宋 穎, 梁衛芳, 趙 玨, 張福泉, 侯小毛

(1.湖南信息學院 計算機科學與工程學院, 湖南 長沙 410151, 中國;2.湖南工商大學 計算機學院, 湖南 長沙 410205, 中國; 3.菲律賓國家大學 計算機與信息技術學院, 馬尼拉 0900, 菲律賓;4. 閩江學院 計算機與控制工程學院, 福建 福州 350108, 中國; 5. 湖南化工職業技術學院 自動化與信息工程學院, 湖南 株洲 412000, 中國)

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

當前,關于云資源調度的研究較多,其中的一個重要研究方向就是各種群智能算法在云資源調度場景中的應用。例如,孫力等[3]將量子遺傳算法和蟻群優化算法組合用于云資源調度,通過群智能算法搜索最佳調度參數組合,即最優個體。鄭春梅等[4]采用差分進化算法用于云資源調度,并且為了提高調度效率,對差分縮放因子進行自適應優化。上述研究均采用群智能算法來實現云資源調度,表現出了較好的執行效率,但是,這2種云資源調度算法均側重于調度時間,僅將調度執行時間作為目標函數進行優化,沒有考慮任務成本或者負載均衡等指標,而且調度的任務數量并不多。

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

1 WWO算法

WWO算法主要是通過水波的3種運動方式來實現優化求解。

(1)

波長更新方式[6]為

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

(2)

式中:λ′為更新后的波長;α為水波衰減系數;ε為大于0且近似于0的數。

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

(3)

(4)

式中μ、σ分別為均值和標準差。

(5)

波長求解公式[8]為

(6)

(7)

式中β為碎波系數。

2 基于ABC-WWO算法的云資源調度模型

2.1 ABC-WWO算法

ABC算法通過蜜蜂的蜜源i搜索完成既定范圍內的尋優操作。設蜜蜂總維度為D,偵測蜂在第d維搜索邊界[Ld,Ud]的運動位置為Xid[10],

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

(8)

假設蜜源i的第d維坐標為Vid,偵測蜂Xid尋找蜜源的移動操作[11]為

Vid=Xid+φ(Xid-Xjd),

(9)

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

偵測蜂每運行一次將其記錄的舊蜜源和新蜜源Vi=[Vi1,Vi2,,Vid]進行適應度值對比,以更新蜜源,適應度求解函數Fi[12]為

(10)

式中fi為第i個蜜源的適應度,對比Vi和Xi,選擇兩者適應度高的作為新蜜源。

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

(11)

式中S為偵測蜂獲得的所有蜜源數。

當迭代次數G滿足時G=Gmax,輸出當前蜜源坐標即為最優解,算法停止,否則轉到式(8)—(11)繼續迭代。

2.2 云資源調度模型的構建

云資源調度模型的主要任務是將n個任務分配至m個云資源中,因此,首先需要根據任務的執行的資源需要,可以構建任務-資源矩陣,其中第t個任務對第r個資源的執行時間為M(t,r),則任務t在資源r上的執行完畢時間Mct(t,r)為

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

(12)

式中Ms(r)為資源r開始被使用的時間。若任務t只需要使用資源r,那么任務t的整個執行時間Ct為

Ct=Mct(t,r)。

(13)

當云計算服務平臺的任務并行執行時,云資源調度模型中所有任務的調度時間M為

(14)

在式(12)中, 任務t的執行時間只使用了1個資源(資源r), 當任務需要使用多個資源時, 云資源調度模型將變得復雜。在云資源調度模型的優化研究中, 常將所有任務調度時間作為優化的目標函數。僅將單一的調度時間作為目標函數不符合云計算的現狀。 為了解決這個問題, 本文中云資源調度模型將云計算任務調度時間、調度成本及負載均衡度作為云資源調度優化的目標, 提高云資源調度性能。

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

(15)

模型的負載均衡指標Id為

Id=(Cmax-Cmin)/Cave,

(16)

式中Cmax、Cmin和Cave分別為所有云資源調度任務中執行時間的最大值、最小值和平均值。

綜上,所提云資源調度模型的優化目標變為

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

(17)

式中λ1、λ2和λ3分別為3個優化指標的權重系數。

2.3 模型的執行流程

基于ABC-WWO算法的云資源調度流程如圖1所示。初始化云資源調度模型的實例參數組合,將任務、資源、任務的資源使用時間及資源的成本量化并抽象化為不同的水波。WWO算法的適應度函數為云資源調度的所有任務完成時間、虛擬機使用成本和負載均衡指標加權之和的最小值。計算所有水波適應度,并執行水波優化操作。不斷更新水波群的最大適應度,且將水波衰減系數α和碎波系數β作為ABC算法的優化對象,從而得到最優個體,即所需云資源調度參數組合。

圖1 基于人工蜂群-水波優化算法的云資源調度流程

3 實例仿真

為了驗證ABC-WWO算法在云資源調度中的性能, 進行實例仿真, 仿真平臺為Cloud Sim, 其中仿真平臺提供的任務數量為30～1 000, 參與計算的虛擬機數量為10～100, 所有參與運算的虛擬機配置及優先級均相同, 仿真資源具體配置如表1所示。

表1 仿真平臺配置

3.1 WWO的改進性能

為了驗證ABC算法對WWO的改進性能,分別采用WWO、 ABC-WWO算法進行云資源調度性能仿真,虛擬機資源數量為m=10,任務執行時間如圖2所示。從圖中可以看出,在虛擬機資源數量一定時,任務數量的增多將導致云資源調度的時間增加,對比WWO、 ABC-WWO算法發現,在任務數量小于100時,兩者的資源調度時間非常接近。當任務數量為100～600時,兩者的調度時間雖然都在增加,但WWO算法執行時間增加更快,2種算法的執行時間差距逐漸增大,表明經過ABC優化后,WWO算法的云資源調度執行時間明顯縮短。

圖2 水波優化(WWO)算法和人工蜂群(ABC)-WWO算法的云資源調度時間對比

對2種算法的負載均衡性能進行仿真,差異化設置任務數量,其中10臺虛擬機資源分別所承載的任務數量統計結果如表2所示。

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

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

繼續對2種算法的負載均衡指標進行性能仿真,進一步驗證2種算法的調度均衡性能,結果如圖3所示。由圖可見,隨著任務量的變化,WWO算法的負載均衡指標值明顯大于ABC-WWO算法的,表明WWO算法的執行時間最大值和最小值差值較大,其云資源調度的均衡能力較ABC-WWO算法差。從圖中還可以看出,負載均衡指標與任務量的關系不明晰,兩者沒有呈現規律性變化。

圖3 水波優化(WWO)算法和人工蜂群(ABC)-WWO算法的負載均衡指標

3.2 不同算法的云資源調度性能

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

3.2.1 不同任務數量的調度性能

設置資源個數為50,差異化設置使用云資源的任務數量,驗證不同算法的資源調度時間,結果如圖4所示。由圖可以看出:當任務數量小于200時,4種算法的執行時間非常接近,主要原因是虛擬機資源數量為50,與任務數量相比,虛擬機資源比較充裕,調度算法的性能差異不是特別明顯;當任務數量為200～1 000時,4種算法的執行時間差異度明顯增大,ACO算法耗時最長,FA算法略優于PSO算法,ABC-WWO算法最省時,表明ABC-WWO算法的云資源調度性能最優。

ACO—蟻群優化算法; PSO—粒子群優化算法;FA—螢火蟲算法; ABC-WWO—人工蜂群-水波優化算法。圖4 資源數量相同時不同云資源調度算法的執行時間

3.2.2 不同資源數量的調度性能

為了驗證4種算法在不同資源數量時的云資源調度性能,差異化設置參與云計算的虛擬主機數量,任務數量設置為1 000,驗證不同算法的資源調度時間,結果見圖5。從圖中可以看出,隨著虛擬主機數量的變化,ABC-WWO算法的執行時間最短,FA算法的次之,ACO算法的最長。當資源數量小于60時,4種算法的執行時間差異較明顯;當資源數量為60～100時,4種算法的執行時間差異度明顯減小,原因是虛擬機資源數量增加,各種調度算法的優化性能體現不是特別明顯。綜上所述,在對云資源進行調度時,云服務平臺本身的資源數量對執行時間的影響最為關鍵,但在資源數量有限時,調度算法的尋優能力就變得尤為重要。

ACO—蟻群優化算法; PSO—粒子群優化算法;FA—螢火蟲算法; ABC-WWO—人工蜂群-水波優化算法。圖5 任務數量相同時不同云資源調度算法的執行時間

3.2.3 收斂性能

對4種不同算法的收斂性能進行仿真, 驗證在資源數量為50時不同算法的資源調度穩定性及效率, 結果如圖6所示。 由圖可以看出, 雖然任務數量的變化對4種算法的云資源調度執行時間影響明顯, 但4種算法的迭代次數差異并不大。 當任務數量為100、 200時, 4種算法的執行時間在迭代80次后達到穩定; 當任務數量為500、 800時,4種算法的執行時間均在迭代90次左右達到穩定。 總之, 從資源調度穩定性來看, 4種算法差距較小, 但從資源調度的執行時間來看, ABC-WWO算法仍占優勢。

4 結語

采用ABC-WWO算法用于云資源調度, 通過ABC算法對水波衰減系數和碎波系數的優化求解, 有效提高了WWO算法在云資源調度中的適用性, 相比于基于常用算法的云資源調度模型, 在相同任務數量或者相同資源數量的條件下, 采用ABC-WWO算法均能夠獲得更優的調度性能, 且云服務平臺虛擬機資源負載均衡性方面更為出色,特別適用于云資源的大規模調度。