基于改进粒子群算法的云计算资源调度模型的研究

赵 宏 伟

(沈阳大学 信息工程学院, 辽宁 沈阳　110044)

基于改进粒子群算法的云计算资源调度模型的研究

赵 宏 伟

(沈阳大学 信息工程学院, 辽宁 沈阳110044)

摘要:为实现云计算资源的合理运用和负载均衡,提出了云计算资源的动态调度管理框架,设计了一种考虑各虚拟机资源数、各虚拟机性能,以及当前的负载情况的资源分配算法,实现了一种改进的粒子群算法的云计算资源动态调度模型.实验结果表明,此调度模型能有效改善动态资源的分配,提高云计算系统中资源的利用率.

关键词:分布式; 云计算; 粒子群; 负载平衡

云计算[1]是一种计算方式,通过互联网,以资源的形式提供给用户.目前,在云计算的各个方面都有了大量的研究,比较著名的系统如Google公司推出的Hadoop的体系结构和Amazon的弹性计算云系统(elasticcomputecloud,简称EC2)等[2].在云计算系统中,由于云计算的复杂性和不确定性,云资源呈现动态变化的特点,为了提高资源利用率和系统的吞吐率,如何进行资源的调度成为了云计算系统中的核心.

目前,学术界在云计算环境下的资源调度方面已经进行了大量研究工作,2009年,NimBus等提出了基于贪婪算法的云计算资源调度模型,该云计算模型简单,并没有考虑载负载平衡;文献[3]提出了一种云资源调度模型----云效用最大化模型,与传统调度模型相比,目标函数不再是最小化最大完工时间,而是以达到效用最大为调度目标,但难以满足日益增长的云计算规模;文献[4]根据云计算的弹性化和虚拟化等新特性,提出了云计算中虚拟机放置的自适应管理模型和虚拟机放置多目标优化遗传算法,但云计算系统模型考虑不完美,并且最优化达不到期望的效果.随着仿生智能算法的发展,不少学者提出了基于蚁群算法、粒子群算法、遗传算法等的云计算资源调度模型,这些仿生智能算法具有搜索能力强、并行性好等特点,可以快速找到云计算资源最优调度方案,有效提高云计算资源的利用效率[5].然而,仿生智能算法在实际应用中,它们均存在易陷入局部最优解,收敛速度慢等缺陷,有时不能获得最优资源调度方案,这就需要对仿生智能算法进行改进和完善[6].

从以上分析可知,云计算系统中的资源请求时,根据资源调度动态变化的特点,需要考虑各个方面的因素,因此,本文设计的调度框架,综合考虑了SLA、应用性能、负载平衡、结点性能、虚拟机性能等多个因素,设计了云计算资源的动态调度管理框架,并设计了一种高效率的改进的PSO算法.

1云计算环境下的动态资源调度框架

图1云计算资源的动态调度管理框架

Fig.1Dynamicschedulingmanagementframeworkofcloudcomputingresources

针对传统云计算系统中调度系统结构的优缺点,提出了一种综合考虑SLA、应用性能、负载平衡、结点性能、虚拟机性能等多个因素的云计算调度系统框架,调度系统的结构如图1所示.在云计算系统中调度分为两级调度:一级调度为任务级调度,主要作用是为用户提交的任务提供相应的虚拟机资源,达到虚拟机资源的有效使用;二级调度为虚拟机布置调度,主要功能是把虚拟资源合理布置到物理机资源上,以达到物理机资源的最优配置.

整个调度系统框架主要由以下部分组成:

(1) 云计算平台门户.主要通过WEB方式,负责接收用户提交的各类任务,平台门户中包括SAAS、PAAS、IAAS等各类应用服务.

(2) 资源描述模块.资源描述模块接收到任务后,首先判断任务所调度应用的类型,从而获取应用性能(应用所需资源情况);其次,根据用户的服务质量(SLA),得到用户所能接受的任务处理结果,例如最小完成时间或最低费用等,并把分析结果发布给资源预测模块.

(3) 资源预测模块.该模块主要根据资源描述模块提供SLA和应用性能的信息,对用户提交的任务进行资源需求预测.

(4) 虚拟资源调度模块.该模块主要根据资源预测模块预测的结果和VM资源的使用情况,包括VM的CPU利用率、内存使用情况和I/O使用情况等信息,采用基于粒子群的多目标优化方法,得到相应资源池,在相应的资源池中,获取云环境中最优的虚拟资源,进行资源配置,布置任务.

(5) 资源池(POOL)模块.调度系统设计了不同应用类型的资源池,包括计算密集型、存储密集型和应用密集型等各类的资源池.调度系统根据用户提交任务的情况,进行不同资源池的调度,这时,资源池也将把本资源池的情况,发布给VMMomiter模块.

(6)VMMomiter模块.主要功能包括:①VMMomiter监视虚拟资源(VM)和物理资源结点(PM)的使用情况,提供所监视的信息,并确定什么时候进行全局的VM布置;②监视虚拟资源(VM)的过载或低载,确定什么时候进行VM迁移;③基于虚拟机规则器产生的布置策略,进行全局虚拟机放置;④基于虚拟机规则器产生的迁移策略,进行虚拟机迁移,及将这些虚拟机迁移到哪个结点.

(7) 物理资源调度模块.物理资源调度模块实质上是VM放置模块,主要是将VM映射到PM,物理资源调度模块的任务是通过改变VM的布局和配置来满足不同POOL和不同应用性能的目标.

(8) 虚拟机规则器模块.虚拟机规则器,根据物理资源调度模块提供的多目标优化产生的策略,通知VMMomiter进行资源的布置或迁移.策略主要刻画了应用性能与所需资源关系模型,实现了在虚拟机资源配置中满足一定性能的条件上,提高资源的使用效率.

(9) 物理资源模块(PM).物理资源模块主要包括一些服务器、存储空间等硬件设备,这些设备分布在各个结点,统一作为云计算中心的基础设施,供虚拟资源使用.

2基于改进粒子群算法FPSO的多目标优化

由于在云计算环境中,资源调度分为两级调度:一级的虚拟资源调度,主要是为用户任务分配可用的虚拟资源,另一级是物理资源调度,主要是虚拟机布置到适合的物理机资源的调度.物理资源调度可以通过Kvm、Vmvare等中间件的虚拟机模板,完成虚拟机到物理资源的映射.因此,本文主要针对虚拟资源调度模型进行研究.

2.1基本粒子群算法

基本的PSO算法利用式(1)和式(2)来计算在D维空间中的优化问题,第t代的第d维(d=1,2,3,…,D)的速度和位置可以表示如下:

2.2改进粒子群算法FPSO

改进粒子群算法主要是把负载的指标和服务质量指标引入到基本PSO算法中, 本文对于PSO的改进主要体现在粒子群的初始化和适应度函数(Fitness)设计方案上, 对于一个粒子的适应度计算, 通过式(3)即可. 式(3)用来优化服务质量和应用负载两个目标, 一旦发现有直接影响云计算系统性能的延迟, 就触发第二级调度调度程序, 进行虚拟机迁移或重新布置虚拟机. 式(3)列出了云资源调度系统的虚拟机调度的模型.

(1) 负载的指标.主要考虑CPU利用率、CPU就绪队列长度、内存使用情况和磁盘访问频度,以及I/O速度等.

(2) 服务质量的指标.云计算系统中,每隔一个固定的小时间段,虚拟机向VMMoniter提供虚拟机负载信息,VMMoniter根据汇报信息进行更新.资源是动态产生的,在本模型中考虑的负载指标主要包括各虚拟机当前负载、性能、任务数等.我们可以静态或动态地确定负载指标的权重.

通过计算公式(3),函数Prank(Si)给出对应于虚拟机Si的服务质量,得到虚拟资源的质量指标.

Prank(Si)=min(E(Si),LifeTime(Si))+

式中,E(Si)是虚拟机的平均执行的时间,LifeTime(Si)是为Si的生存周期, 其中lic是Si和VMMoniter(c)之间需要传输的数据量,bic是Si和VMMoniter(c)之间传输的网络带宽,a1,a2,…,an是选定的负载指标;k1,k2,…,kn是权重.如果有资源请求到达,对每个虚拟机采用式(3)的方法计算得到初始化的粒子群,其中每个粒子是一个调度方案,最后基于式(1)、式(2)求出最优解,基于粒子群算法优化调度算法,流程如图2所示.

云计算环境下虚拟资源调度的FPSO的步骤:

步骤1首先根据式(3)云计算系统资源初始化虚拟资源池的粒子数,将资源池分为n个粒子.

图2　基于FPSO粒子群算法优化调度算法流程

步骤2针对初始粒子群,设置初始位置和初始速度.

步骤3根据式(3)计算每个粒子的适应度值,并从中选择最优粒子作为个体最优解.

步骤4根据式(1),式(2)更新粒子群的速度和位置,并与个体最优解和群体最优解进行比较,根据结果更新个体最优解.

步骤5对终止条件进行判断,若满足则对群体最优粒子位置进行解码,得到云计算资源的最优调度方案,否则,返回步骤3继续进行迭代.

3实验及结果分析

实验算法部分,选择Sphere、Rosenbrock、Griewank[7]标准测试函数用于测试提出的FPSO算法的性能,并与PSO算法进行了性能比较.3个函数中前两个是单峰函数,后一个是多峰函数.实验工具采用MATLAB7,种群的初始设置如表1所示.

表1　测试函数参数设置

实验结果如表2所示.从表中可以看出,在3种测试函数中,FPSO算法获得的平均适应度值几乎都要好于PSO算法,在Sphere、Rosenbrock 2个函数中的表现尤为明显.FPSO算法获得的标准方差也要小于PSO算法,并且FPSO算法能够避免收敛较快而陷入局部最优.因此,FPSO比PSO算法更稳定,具有较强的鲁棒性.

表2　FPSO与PSO结果比较

本文对Cloudsim云计算的模拟平台进行了扩展,重写一系列的类,模拟了云计算的计算和网络资源,结果见图3～图6.

在模拟实验中,进行100次迭代,基于PSO资源分配算法和本文提出的FPSO云计算的资源分配算法的收敛效果比较,从图3可以看出考虑负载指示FPSO收敛更快.在设置用户提交200个任务,分别进行任务完成时间、负载平衡和服务质量的情况进行实验比较,图4、图5可以看出,在保证负载平衡的情况下,FPSO随着任务的增加,完成时间要少于基于PSO的资源调度算法,图6显示出FPSO的服务质量要优于PSO.

总体实验表明,采用PSO资源分配算法比较简单,并不考虑虚拟机的实际负载情况,资源处理的响应时间较长,而采用本文提出的基于改进的粒子群FPSO资源分配算法,资源是动态分配的,可以使各个虚拟机的负载得到均衡,加快了资源调度的速度,有效缩短任务的完成时间.从图4结果来看,本算法在迭代次数较多、节点较多,有效资源较少的情况下工作效率明显比PSO资源分配算法高,而这种情况正是云环境所具有的特点.所以本算法在云计算环境中更有优势,提高了整个云计算系统的并行运行的效率.

图3　两种资源分配算法迭代收敛比较

图4　两种资源分配算法完成时间比较

图5　两种资源分配算法负载平衡比较

图6　两种资源分配算法服务质量比较

4结论

本文提出了一种改进的粒子群的云计算系统的动态调度系统,并分析了云计算系统调度所涉及到的具体的模式和技术,提出了云计算资源的动态调度管理框架,给出了框架系统结构形式,然后设计并实现了一种综合考虑各虚拟机任务数和各个虚拟机性能以及当前的负载情况的改进的粒子群资源分配算法FPSO.对于二级调度系统采用原始的虚拟机模板方式,通过VMMoniter对虚拟机进行监测,用来解决云计算系统调度中存在的延迟等问题,最后通过实例验证本文提出的方法相对于其他方法的优越性.

参考文献:

[1] ARMBRUST M, FOX A, GRIFFITH R. A view ofcloud computing[J]. Communications of the ACM, 2010,53(4):50-58.

[2] COELLO C, CARLOS A, LECHUGA M S. MOPSO: a proposal for multiple objective particle swarm optimization[C]∥Proceedings of IEEE Congress on Evolutionary Computation, USA, Honolulu: IEEE, 2002:1051-1056.

[3] GOIRI I, GUITART J, TORRES J. Characterizing cloud federation for enhancing providers profit[C]∥3rd International Conference on Cloud Computing (CLOUD 2010), 2010:123-130.

[4] 师雪霖,徐恪. 云虚拟机资源分配的效用最大化模型[J]. 计算机学报, 2013,36(2):252-262.

(SHI X L, XU G. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013,36(2):252-262.)

[5] 李强,郝沁汾,肖利民,等. 云计算中虚拟机放置的自适应管理与多目标优化[J]. 计算机学报, 2011,34(12):2256-2257.

(LI Q, HAO X F, XIAO L M. Adaptive management and multi-objective optimization for virtual machine placement in cloud computing[J]. Chinese Journal of Computers, 2011,34(12):2256-2257.)

[6] 田冠华,孟丹,詹剑锋. 云计算环境下基于失效规则的资源动态提供策略[J]. 计算机学报, 2010,33(10):1859-1872.

(TIAN G H, MENT D, ZHAN J F. Reliable resource provision policy for cloud computing[J]. Chinese Journal of Computers, 2010,33(10):1859-1872.)

[7] 雷德明,严新平. 多目标智能优化算法及其应用[M]. 北京:科学出版社, 2009:19-59.

【责任编辑: 肖景魁】

(LEI D M, YAN X P. Intelligent multi-objective optimization algorithm and application[M]. Beijing: Science Press, 2009:19-59.)

Resource Schedule Model Base on Improved PSO in Cloud Computing

ZhaoHongwei

(School of Information Engineering, Shenyang University, Shenyang 110044, China)

Abstract:A dynamic dispatching management framework is proposed to implement the rational use and load balancing of the resource of cloud computing. A resource allocation algorithm is designed, which comprehensively applies PSO and considers the resource numbers and performance of each virtual machine and current loading conditions. An improved cloud computing resources dynamic scheduling model based on PSO is realized. The result of the experiment indicates that the scheduling system can improve the efficiency of dispatching service and the utilization ratio in the cloud computing system.

Key words:distributed; cloud computing; particle swarm; load balance

中图分类号:TP312

文献标志码:A

文章编号:2095-5456(2015)06-0507-05

作者简介:赵宏伟(1976-),男,辽宁沈阳人,沈阳大学副教授.

基金项目:辽宁省自然科学基金资助项目(2013020011).

收稿日期:2015-03-27