基于改进混沌萤火虫算法的云计算资源调度

杨 单,李超锋,杨 健

(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