基于改進混沌螢火蟲算法的云計算資源調度

楊 單,李超鋒,楊 健

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

基于改進混沌螢火蟲算法的云計算資源調度

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

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

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

云計算;資源調度;混沌算法;螢火蟲算法;組合優化;拉格朗日松弛函數

1 概述

目前網絡前沿發展技術中的云計算是研究的熱點,它將傳統的并行計算、分布計算、網格計算融為一體[1-2]。云計算中資源的服務質量好壞成為衡量云計算效果的一個重要的方面,但是云計算中存在諸多形態不同的云端,并且云計算任務具有規模大、資源異構性的特點,如何能夠更好地進行云計算資源調度是目前云計算研究的熱點和難點[3]。

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

2 云計算資源調度模型的建立

根據云計算資源調度的特點,將云資源分配初步情況通過如下模型來表示:

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

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

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

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

3 云計算資源調度算法

3.1 改進的混沌螢火蟲算法

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

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

螢火蟲位置更新公式為:

熒光素值的公式為:

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

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

混沌優化螢火蟲算法策略過程如下:

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

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

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

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

3.2 云計算資源分配模型

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

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

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

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

其中,sk表示迭代步長;gk表示迭代系數。

3.3 算法步驟

求解步驟如下:

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

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

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

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

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

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

(4)如果迭代次數小于max,轉到步驟(1)。

Step 4如果滿足終止條件,則尋優過程便結束,否則轉向Step2繼續優化。

Step 5根據最優個體得到最優的云計算調度方案。

算法流程如圖1所示。

圖1 改進算法流程

4 仿真實驗

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

4.1 算法改進前后的收斂值對比

在云計算資源數為50,任務數為10 000的系統中,本文算法和基本螢火蟲算法的調度方案的求解曲線如圖2所示。從圖2中可以發現,對于基本螢火蟲算法而言,本文算法的尋優速度和收斂速度明顯加快,并且比基本螢火蟲算法優先達到最優方案,這主要是因為在算法中引入混沌算法,全局尋優過程中借鑒混沌優化策略思想對最優個體進行混沌擾動,避免了陷入局部最優的概率,由于引入拉格朗日函數,從而對云計算模型進行簡化,是一個提高了云計算系統資源調度問題的重要方面。

圖2 算法改進前后的收斂值對比

4.2 任務完成時間對比

本節針對云計算環境任務具有動態性的特點,選取了2個最大規模和最小規模的情況下進行效果的對比。

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

選取10個～70個任務在在資源數量為10的云計算系統上進行運行,得到最優調度方案完成所有任務的時間變化如圖3所示。從圖3可知,當任務數較少時,用戶競爭資源的概率較小,發生資源沖突的概率也較小,各個算法均可以獲得云計算資源調度性能較優的方案,相互之間性能差別不大。

圖3 小規模情況下的任務完成時間對比

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

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

圖4 大規模情況下的任務完成時間對比

4.3 資源節點數量對比

選取將10萬個任務隨機分配到10個～70個資源節點進行運行,結果如圖5所示。隨著節點數的增加,任務完成時間逐步減少,主要是由于資源節點數增加,任務競爭資源慢慢變弱。通過圖5對比結果表明,本文的算法可以提高云計算任務調度問題求解效率和速度。

圖5 資源節點數與任務完成時間的比較

5 結束語

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

[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].計算機科學,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].計算機應用,2011,31(1):184-186.

[6] 王 芳,李美安,段衛軍.基于動態自適應蟻群算法的云計算任務調度[J].計算機應用,2013,33(11): 3160-3162.

[7] 李 邐,姚 曄,李 鐵.基于改進型人工螢火蟲算法的云計算資源研究[J].計算機應用研究,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].計算機工程,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