楊 單,李超鋒,楊 健

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

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

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

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

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

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

1 概述

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

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

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

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

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

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

螢火蟲位置更新公式為:

熒光素值的公式為:

混沌優(yōu)化的結(jié)果是通過在優(yōu)化變量中加入混沌的狀態(tài),并將混沌范圍擴(kuò)大到優(yōu)化變量的取值范圍中。伴隨著迭代次數(shù)的增多,螢火蟲個(gè)體與xj(t)越接近,導(dǎo)致個(gè)體之間的差異喪失,為了防止這種現(xiàn)象的發(fā)生,對(duì)螢火蟲個(gè)體中處于最差位置的個(gè)體進(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對(duì)式(10)多次迭代混沌序列集合為。

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

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

3.2 云計(jì)算資源分配模型

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

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

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

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

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

3.3 算法步驟

求解步驟如下:

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

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

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

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

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

(3)計(jì)算每一個(gè)螢火蟲的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)個(gè)體得到最優(yōu)的云計(jì)算調(diào)度方案。

算法流程如圖1所示。

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

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

本文所采用的仿真平臺(tái)是酷睿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)行對(duì)比實(shí)驗(yàn)。

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

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

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

4.2 任務(wù)完成時(shí)間對(duì)比

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

在云計(jì)算環(huán)境中,資源如何更加合理分配使用一直是研究熱點(diǎn),針對(duì)基本的螢火蟲算法在求解速度緩慢以及容易陷入局部最優(yōu)的問題,本文在人工螢火蟲算法中引入混沌算法,同時(shí)針對(duì)云計(jì)算資源調(diào)度模型,使用拉格朗日松弛函數(shù)進(jìn)行簡(jiǎn)化。仿真實(shí)驗(yàn)結(jié)果表明,本文算法可以有效地對(duì)云計(jì)算資源進(jìn)行調(diào)度,從而使得任務(wù)的各項(xiàng)參數(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] 李 喬,鄭 嘯.云計(jì)算研究現(xiàn)狀綜述[J].計(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] 李建峰,彭 艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用,2011,31(1):184-186.

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

[7] 李 邐,姚 曄,李 鐵.基于改進(jìn)型人工螢火蟲算法的云計(jì)算資源研究[J].計(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)混沌螢火蟲算法的云計(jì)算資源調(diào)度[J].計(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年度湖北省科技支撐計(jì)劃基金資助項(xiàng)目(2014BDF073)。

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

2014-03-19

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