基于改進(jìn)混沌螢火蟲算法的云計算資源調(diào)度

楊 單,李超鋒,楊 健

(1.中南民族大學(xué)管理學(xué)院,武漢430073;2.華中科技大學(xué)計算機(jī)學(xué)院,武漢430074)

基于改進(jìn)混沌螢火蟲算法的云計算資源調(diào)度

楊 單1,2,李超鋒1,楊 健1

(1.中南民族大學(xué)管理學(xué)院,武漢430073;2.華中科技大學(xué)計算機(jī)學(xué)院,武漢430074)

為提高云計算資源的利用率,保持負(fù)載平衡,提出一種基于改進(jìn)混沌螢火蟲算法的云計算資源調(diào)度模型。從任務(wù)的完成時間、完成效率、完成安全性3個方面建立云計算資源調(diào)度模型,在螢火蟲算法中引入混沌算法,通過對個體進(jìn)行擾動,加快收斂速度,降低局部最優(yōu)的概率,并引入拉格朗日松弛函數(shù)改進(jìn)云計算模型。基于Cloudsim的仿真實(shí)驗(yàn)結(jié)果表明,該算法能有效避免資源分配的不均衡,縮短任務(wù)完成時間,提高系統(tǒng)的整體處理能力。

云計算;資源調(diào)度;混沌算法;螢火蟲算法;組合優(yōu)化;拉格朗日松弛函數(shù)

1 概述

目前網(wǎng)絡(luò)前沿發(fā)展技術(shù)中的云計算是研究的熱點(diǎn),它將傳統(tǒng)的并行計算、分布計算、網(wǎng)格計算融為一體[1-2]。云計算中資源的服務(wù)質(zhì)量好壞成為衡量云計算效果的一個重要的方面,但是云計算中存在諸多形態(tài)不同的云端,并且云計算任務(wù)具有規(guī)模大、資源異構(gòu)性的特點(diǎn),如何能夠更好地進(jìn)行云計算資源調(diào)度是目前云計算研究的熱點(diǎn)和難點(diǎn)[3]。

云計算資源調(diào)度本質(zhì)是是復(fù)雜組合優(yōu)化問題,而群體智能算法在解決復(fù)雜函數(shù)優(yōu)化問題取得理想的效果[4]。國內(nèi)外學(xué)者在這方面進(jìn)行了一些研究。文獻(xiàn)[5]針對云計算的編程模型框架,將總?cè)蝿?wù)完成時間和平均完成時間作為調(diào)度目標(biāo)適應(yīng)度函數(shù),提出了一種將雙適應(yīng)度函數(shù)的改進(jìn)遺傳算法。文獻(xiàn)[6]對蟻群算法求解云計算任務(wù)調(diào)度問題存在收斂速度慢和容易陷入局部最優(yōu)解的缺陷,提出一種混沌蟻群算法的云計算任務(wù)調(diào)度策略等。文獻(xiàn)[7]提出了一種改進(jìn)的人工螢火蟲算法并應(yīng)用與分配資源的調(diào)度上,比較好地解決均衡網(wǎng)絡(luò)負(fù)載和延長網(wǎng)絡(luò)的問題。本文根據(jù)云計算環(huán)境下資源動態(tài)分配的特點(diǎn),建立云計算資源分配模型,提出云計算資源調(diào)度的混沌螢火蟲算法,同時在云計算分配模型中引入拉格朗日函數(shù)。

2 云計算資源調(diào)度模型的建立

根據(jù)云計算資源調(diào)度的特點(diǎn),將云資源分配初步情況通過如下模型來表示:

其中,Cj表示虛擬機(jī)j的最大計算處理能力;Ii表示作業(yè)i包含的機(jī)器指令條數(shù);Di表示作業(yè)最遲完工時間;yi表示分配給作業(yè)i的資源總和,表示為yi=,其中是表示虛擬機(jī)j占用計算資源總和。為了避免之前描述的資源節(jié)點(diǎn)失效的問題,加入作為約束條件,以保證節(jié)點(diǎn)的資源得到合理的處理,fi(yi)表示為目標(biāo)函數(shù)中效率函數(shù),根據(jù)云計算的資源調(diào)度的要求,云計算資源調(diào)度的最大化為。在本文設(shè)定的模型中沒有考慮虛擬機(jī)上所造成的開銷考慮進(jìn)去,主要是因?yàn)樵贫擞脩舻牟僮飨到y(tǒng)等環(huán)境等諸多因素不同,無法用統(tǒng)一的標(biāo)準(zhǔn)來衡量。同時,模型也沒有考慮做作業(yè)的到達(dá)時間,只是針對目前已經(jīng)排列的云端用戶的作業(yè),考慮到現(xiàn)有的網(wǎng)絡(luò)負(fù)載條件,能夠合理避免擁塞。本文只是考慮了作業(yè)的最遲完成時間,以便能夠保證作業(yè)有足夠的資源在最遲時間之內(nèi)完工。此外,為了更好地保證任務(wù)完成的效率,加入節(jié)點(diǎn)有效率函數(shù)E(i,j)以及節(jié)點(diǎn)安全性函數(shù)S(i,j)。

其中,eij表示任務(wù)ti在虛擬機(jī)xi上的預(yù)期有效率;e(i,j)為任務(wù)ti在虛擬機(jī)xi上的實(shí)際效率;emax為最大效率;emin為最小效率。

其中,sij表示任務(wù)ti在虛擬機(jī)xi上的預(yù)期安全性;s(i,j)為任務(wù)ti在虛擬機(jī)xi上的實(shí)際安全性。

綜合式(1)～式(3),云資源分配模型如下:

3 云計算資源調(diào)度算法

3.1 改進(jìn)的混沌螢火蟲算法

人工螢火蟲算法[8]是一種智群優(yōu)化算法,該算法廣泛使用在函數(shù)和組合優(yōu)化中。在該算法中,通過目標(biāo)函數(shù)適應(yīng)度的值來確定有關(guān)資源分配,將適應(yīng)度的值的高低作為衡量資源分配的參考。假設(shè)螢火蟲的群體為N,第i只螢火蟲所在的位置為(xi,yi);第i只螢火蟲所對應(yīng)的目標(biāo)函數(shù)為f(xi,yi);第i只螢火蟲的螢光素的值為Ti;xj(t)表示第t代的第j個螢火蟲的位置;lj(t)表示第t代的第j個螢光素的值,螢火蟲的視野范圍更新如下:

螢火蟲鄰居選擇的概率為:

螢火蟲位置更新公式為:

熒光素值的公式為:

混沌優(yōu)化的結(jié)果是通過在優(yōu)化變量中加入混沌的狀態(tài),并將混沌范圍擴(kuò)大到優(yōu)化變量的取值范圍中。伴隨著迭代次數(shù)的增多,螢火蟲個體與xj(t)越接近,導(dǎo)致個體之間的差異喪失,為了防止這種現(xiàn)象的發(fā)生,對螢火蟲個體中處于最差位置的個體進(jìn)行混沌,本文采用Logistic映射作為混沌優(yōu)化模型,其混沌優(yōu)化模型的迭代方程為:

其中,μ表示為混沌變量。

混沌優(yōu)化螢火蟲算法策略過程如下:

Step 1設(shè)xi=(xi1,xi2,…,xin),將xi映射到螢火蟲算法優(yōu)化變量的取值范圍內(nèi),其中xmin,xmax分別代表變量的最小和最大值。

Step 2對式(10)多次迭代混沌序列集合為。

Step 3根據(jù)逆映射的原理,引入式(11),得到的可行解的集合為。

Step 4采用混沌映射后螢火蟲個體通過概率q的部分個體,其中t為當(dāng)前迭代次數(shù)。q的計算公式為:

3.2 云計算資源分配模型

拉格朗日松弛函數(shù)[9-10]如下:

其中,δj表示拉格朗日函數(shù)中的松弛變量,它用來表示虛擬機(jī)j的計算剩余使用的能力;γi表示提前完工的時間。從云計算的實(shí)際使用資源的效果上來看,為了讓云端客戶中的資源盡可能的獲得更多的資源,令γi=0,δj=0,將式(14)整理為:

本文為了簡化云計算資源分配模型,采用拉格朗日松弛函數(shù)對其模型式(15)進(jìn)行簡化,得到:

在式(16)中,令拉格朗日因子μ:

其中,sk表示迭代步長;gk表示迭代系數(shù)。

3.3 算法步驟

求解步驟如下:

Step 1初始螢火蟲群數(shù)目N,設(shè)置的最大迭代次數(shù)max。

Step 2對螢火蟲算法中的個體進(jìn)行編碼,并根據(jù)式(8)和式(9)計算單個螢火蟲的熒光素的值,為了優(yōu)先考慮結(jié)果,將螢火蟲群體劃分m個子群。

Step 3更新每一個子群的熒光素的值,具體為:

(1)根據(jù)式(8),找到各自最佳位置和最差位置。

(2)根據(jù)式(9)計算螢火蟲的位置,然后根據(jù)式(10)～式(13)對螢火蟲進(jìn)行更新,得到新個體。

(3)計算每一個螢火蟲的L(xnew),如果L(xnew)＞L(x),則x=xnew,否則再更新。

(4)如果迭代次數(shù)小于max,轉(zhuǎn)到步驟(1)。

Step 4如果滿足終止條件,則尋優(yōu)過程便結(jié)束,否則轉(zhuǎn)向Step2繼續(xù)優(yōu)化。

Step 5根據(jù)最優(yōu)個體得到最優(yōu)的云計算調(diào)度方案。

算法流程如圖1所示。

圖1 改進(jìn)算法流程

4 仿真實(shí)驗(yàn)

本文所采用的仿真平臺是酷睿CPU 3.0 GHz, 2 GB DDR 3,Windows XP操作系統(tǒng),采用CloudSim仿真軟件進(jìn)行仿真實(shí)驗(yàn)。為了更好地驗(yàn)證本文提出的改進(jìn)算法的可行性和性能,在相同條件下與文獻(xiàn)[5]改進(jìn)的遺傳算法、文獻(xiàn)[6]混沌蟻群算法和文獻(xiàn)[7]改進(jìn)的螢火蟲算法進(jìn)行對比實(shí)驗(yàn)。

4.1 算法改進(jìn)前后的收斂值對比

在云計算資源數(shù)為50,任務(wù)數(shù)為10 000的系統(tǒng)中,本文算法和基本螢火蟲算法的調(diào)度方案的求解曲線如圖2所示。從圖2中可以發(fā)現(xiàn),對于基本螢火蟲算法而言,本文算法的尋優(yōu)速度和收斂速度明顯加快,并且比基本螢火蟲算法優(yōu)先達(dá)到最優(yōu)方案,這主要是因?yàn)樵谒惴ㄖ幸牖煦缢惴?全局尋優(yōu)過程中借鑒混沌優(yōu)化策略思想對最優(yōu)個體進(jìn)行混沌擾動,避免了陷入局部最優(yōu)的概率,由于引入拉格朗日函數(shù),從而對云計算模型進(jìn)行簡化,是一個提高了云計算系統(tǒng)資源調(diào)度問題的重要方面。

圖2 算法改進(jìn)前后的收斂值對比

4.2 任務(wù)完成時間對比

本節(jié)針對云計算環(huán)境任務(wù)具有動態(tài)性的特點(diǎn),選取了2個最大規(guī)模和最小規(guī)模的情況下進(jìn)行效果的對比。

(1)小規(guī)模任務(wù)時的算法性能對比

選取10個～70個任務(wù)在在資源數(shù)量為10的云計算系統(tǒng)上進(jìn)行運(yùn)行,得到最優(yōu)調(diào)度方案完成所有任務(wù)的時間變化如圖3所示。從圖3可知,當(dāng)任務(wù)數(shù)較少時,用戶競爭資源的概率較小,發(fā)生資源沖突的概率也較小,各個算法均可以獲得云計算資源調(diào)度性能較優(yōu)的方案,相互之間性能差別不大。

圖3 小規(guī)模情況下的任務(wù)完成時間對比

(2)大規(guī)模任務(wù)時的算法性能對比

選取1萬～7萬個任務(wù)在云計算資源數(shù)為50的平臺上運(yùn)行的,云計算資源調(diào)度方案的任務(wù)完成時間如圖4所示。從圖4可知,隨著任務(wù)數(shù)增加,任務(wù)之間的競爭更為激烈,任務(wù)沖突概率增加,所有算法完成任務(wù)時間逐漸增加,從整個任務(wù)的完成時間來看,本文的算法的任務(wù)完成時間要遠(yuǎn)遠(yuǎn)少于對比算法。對比結(jié)果表明,本文算法利用更新的云計算模型,以及加入混沌因子加快了收斂速度,避免了算法陷入局部最優(yōu)解,更加適合大規(guī)模任務(wù)的云計算資源調(diào)度問題求解。

圖4 大規(guī)模情況下的任務(wù)完成時間對比

4.3 資源節(jié)點(diǎn)數(shù)量對比

選取將10萬個任務(wù)隨機(jī)分配到10個～70個資源節(jié)點(diǎn)進(jìn)行運(yùn)行,結(jié)果如圖5所示。隨著節(jié)點(diǎn)數(shù)的增加,任務(wù)完成時間逐步減少,主要是由于資源節(jié)點(diǎn)數(shù)增加,任務(wù)競爭資源慢慢變?nèi)酢Ｍㄟ^圖5對比結(jié)果表明,本文的算法可以提高云計算任務(wù)調(diào)度問題求解效率和速度。

圖5 資源節(jié)點(diǎn)數(shù)與任務(wù)完成時間的比較

5 結(jié)束語

在云計算環(huán)境中,資源如何更加合理分配使用一直是研究熱點(diǎn),針對基本的螢火蟲算法在求解速度緩慢以及容易陷入局部最優(yōu)的問題,本文在人工螢火蟲算法中引入混沌算法,同時針對云計算資源調(diào)度模型,使用拉格朗日松弛函數(shù)進(jìn)行簡化。仿真實(shí)驗(yàn)結(jié)果表明,本文算法可以有效地對云計算資源進(jìn)行調(diào)度,從而使得任務(wù)的各項參數(shù)達(dá)到最優(yōu)。

[1] Lan F,Yong Z,Ioan R,et al.Cloud Computing and Grid Computing 360-Degree Compared[C]//Proceedings of Grid Computing Environments Workshop.[S.l.]:IEEE Press,2008:268-275.

[2] Vaquero L,Rodero Marino L,Cacerce J,et al.A Break in the CloudsTowardsaCloudeDefinition[J]. SIGCOMM Computer Commumcations Review,2009, 39(1):50-55.

[3] 李 喬,鄭 嘯.云計算研究現(xiàn)狀綜述[J].計算機(jī)科學(xué),2011,38(4):32-37.

[4] Sesum-Cavic V,Kuhn E.Applying Swarm Intelligence Algorithm for Dynamic Load Balancing to a Cloud Based Call Center[C]//Proceedings of the 4th IEEE International Conference on Self Adaptive and SelforganizingSystems.[S.l.]:IEEEPress,2010: 255-256.

[5] 李建峰,彭 艦.云計算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計算機(jī)應(yīng)用,2011,31(1):184-186.

[6] 王 芳,李美安,段衛(wèi)軍.基于動態(tài)自適應(yīng)蟻群算法的云計算任務(wù)調(diào)度[J].計算機(jī)應(yīng)用,2013,33(11): 3160-3162.

[7] 李 邐,姚 曄,李 鐵.基于改進(jìn)型人工螢火蟲算法的云計算資源研究[J].計算機(jī)應(yīng)用研究,2013, 30(8):2298-2333.

[8] Grossman R L.The Case for Cloud Computing[J].IT Professional,2009,11(2):23-27.

[9] Fisher M L.The Lagrangean Relaxation Method for Solving Integer Programming Problems[J].Management Science,1981,27(1):1-18.

[10] Shapiron J F.GeneralizedLagrangeMultipliersin Integer Programming[J].Operations Research,1971, 19(1):68-76.

編輯 索書志

Cloud Computing Resource Scheduling Based on Improving Chaos Firefly Algorithm

YANG Dan1,2,LI Chaofeng1,YANG Jian1
(1.School of Management,South-Central University for Nationalities,Wuhan 430074,China;
2.School of Computer,Huazhong University of Science and Technology,Wuhan 430074,China)

In order to improve the utilization rate of cloud resource scheduling and keep load balance,chaos firefly algorithm is proposed for resource scheduling in cloud computing.Taking into account task completion time,task completion efficiency and task completion safety,a cloud resource allocation model is established.Through introducing chaos algorithm into firefly algorithm,disturbing individuals and strengthening rate of convergence,it lowers the probability of local optimum.Lagrange relaxation function is introduced for lack of resource scheduling in cloud computing.Simulation experimental result shows that the improved algorithm can effectively avoid imbalance in resource allocation,shorten completion time of task and enhance integrated processing capacity of system.

cloud computing;resource scheduling;chaos algorithm;firefly algorithm;combinatorial optimization; lagrange relaxation function

楊 單,李超鋒,楊 健.基于改進(jìn)混沌螢火蟲算法的云計算資源調(diào)度[J].計算機(jī)工程,2015, 41(2):17-20,25.

英文引用格式:Yang Dan,Li Chaofeng,Yang Jian.Cloud Computing Resource Scheduling Based on Improving Chaos Firefly Algorithm[J].Computer Engineering,2015,41(2):17-20,25.

1000-3428(2015)02-0017-04

:A

:TP393

10.3969/j.issn.1000-3428.2015.02.004

2014年度湖北省科技支撐計劃基金資助項目(2014BDF073)。

楊 單(1979-),男,講師、博士研究生,主研方向:云計算,信息管理;李超鋒,副教授、博士;楊 健,講師、博士。

2014-03-19

:2014-07-30E-mail:10806197@qq.com