基于云计算平台的资源调度优化研究

田玉靖　郭芳郁　张庆余

摘要：云计算平台资源调度既是云计算系统的关键，又直接影响着系统的工作性能。为了提高云计算资源调度的效率，在深入分析粒子群算法和模擬退火算法的基础上，提出了改进粒子群的虚拟机部署算法及任务调度算法。一方面提高了虚拟机到物理机的资源利用率，另一方面在保证任务运行时间最短的前提下优化了负载不均衡问题。最后通过仿真工具CloudSim进行了仿真，验证了算法的有效性。

关键词：云计算；资源调度；粒子群算法；资源利用率；CloudSim

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）30-0187-04

随着互联网商业竞争的日益加剧及虚拟化技术的发展，云计算已然彻底改变了信息技术的获取及处理方式。而云平台资源调度既是云计算的关键，又对云计算系统的工作性能有着直接的影响，因此研究获取一款高效的计算资源调度模型至关重要。

针对云计算集群的异构及不稳定问题，文献[1]提出了一种基于统计分析的Hadoop任务槽分配机制算法RSSO，并在一定程度上提高了集群的性能[1]。为了解决服务器的吞吐量问题，文献[2]通过研究蜂群算法，提出了基于负载分发的蜂群算法的负载平衡机制[2]。此外基于蛙跳算法、免疫进化算法等研究出的资源调度模型，虽均在提高云计算资源效率上做出了贡献，但却存在着易陷入局部最优解、收敛速度慢的缺陷。

为了研究获取更优的云计算调度方案，提高云计算的资源利用率，本研究对粒子群算法的原理进行了研究，并结合实际针对性的对算法进行了改进，提出了基于改进粒子群算法的虚拟机部署算法（simulated annealing-particle swarm optimization，SA-PSO）及基于改进粒子群算法的双适应度任务调度算法（double fitness- particle swarm optimization， DF-PSO）。之后通过仿真证明了提出算法的有效性。

1 云计算资源调度问题描述

云计算资源调度通常分为两步，第一步在虚拟资源层分配任务至虚拟机上，第二步在物理资源层部署虚拟机至物理机上。

研究发现，一方面云平台往往使用简单的虚拟机资源，以牺牲平台负载均衡为代价来提高云平台部署的效率。另一方面云平台所提供的物理资源，是通过放置在物理机上的虚拟机而实现。又由于虚拟机对不同类型的资源需求不同，且物理机的配置也不尽相同，因此需要研究一种在保证部署效率的同时将虚拟资源均衡的调度到物理资源中的办法。

2 基于改进粒子群的虚拟机部署算法

2.1 改进的粒子群算法

传统的粒子群算法（particle swarm optimization，PSO）具有并行处理、鲁棒性好等特点，目前已广泛并成功应用于函数优化、神经网络设计、信号处理等领域。在PSO中当判断得到计算出的适应度优于最优解时，便会将该粒子作为最优解，因此容易出现误将局部最优解定为全局最优解的情况。

模拟退火算法源自固体退火原理，其理念为在退火过程中随着温度的降低，算法自身的概率突跳特性能够促使其在解空间中获得全局最优解，即在温度较高时可以舍弃局部最优解而寻求全局最优解[5]。算法核心为退火概率，计算公式如（1）所示。

[p=e（-△E（kT））] （1）

其中P表示温度T时刻趋于平衡的概率，[△E]表示内能的变化量，T表示温度，K表示Boltzmann常数。

因此为了优化传统粒子群算法的收敛性，选择在其过程中引入了模拟退火算法。当有粒子的适应度劣于最优解时，便通过Metropolis进行二次判断，进而决定舍弃与否。如此便实现了获得局部最优解后能够概率性的跳出，并最终得到全局最优解。如图2所示为改进粒子群算法的流程图。

根据公式（2）并结合改进算法，研究出的适应度淘汰公式如（2）所示。

其中p表示接受适应度的概率，F表示当前适应度，[Fg]表示最优适应度，T表示温度（随迭代次数的增加而减小）。[T=T?k]，k表示变化系数（k=0～1，k越大表示温度降低的越慢）。

得到粒子群的适应度函数值后，根据公式（2）计算其概率并进行取舍。T的初值为第一次迭代时的最优解，当T较大而[F-Fg]较小时，P值较大，这时得到的解会劣于全局最优解，同时也使得有了跳出局部最优解的可能。随着迭代次数的增加，系数k逐渐降低，，当温度低于最小值时，便跳出退火算法，重新根据粒子群算法直至得到全局最优解。

2.2 基于改进粒子群的虚拟机部署算法

对于研究提出的改进粒子群算法，适应度函数是判断粒子优劣性的唯一标准，但其并不唯一，需要具体问题具体分析。因此在对虚拟机的内存、带宽以及计算能力等因素进行综合分析研究后，所得出的负载不均衡度判断适应度函数如公式（3）、（4）、（5）所示。

[F1（x）=1ni=1n（mi-mavg）] （3）

[F2（x）=1ni=1n（bwi-bwavg）] （4）

[F3（x）=1ni=1n（ci-cavg）] （5）

其中[mi]表示i号物理机的内存利用率，[mavg]表示所有物理机内存利用率的平均值；[bwi]表示i号物理机的带宽利用率，[bwavg]表示所有物理机带宽利用率的平均值；其中[ci]表示i号物理机的计算能力利用率，[cavg]表示所有物理机计算能力利用率的平均值。

公式（6）为结合三个不平衡度得到的加权平均值，并以其作为判断粒子优劣性的标准。

[F（x）=1ni=1nαiFi（x）] （6）

其中[αi]表示第i个适应度的影响因子。

将虚拟机分配到物理机上后，各个物理机所耗费资源的平衡度称为资源的负载均衡度。当单台物理机资源占用率过高，而其他某台资源占用率过低的现象发生时，便会出现前一台物理机运行效率大大降低，而另一台则处于闲置状态的情况。加上物理机性能不尽相同的条件，分析得出计算负载均衡并不能以物理机分配资源的多少为标准。因此选取资源占用率为标准，并通过统计标准差对差异进行比较。标准差小时表示各资源的占用率数值更接近，则分配方式均衡。反之则不均衡。

2.3虚拟机部署算法模型

将虚拟机分配到物理机的方式即为虚拟机的部署方式。结合粒子群算法，则定义粒子表示部署虛拟机的方式，粒子位置的变化表示方式的改变，负载不均衡度为粒子优劣性的判断标准。

定义物理机集合为[H=h1，h2，h3，…，hn]，n为物理机总数。虚拟机的集合为[VM=vm1，vm2，vm3，…，vml]，l为虚拟机总数。虚拟机到物理机的部署方案定义为[F?VM×H]，对于任意[（vmi，hj）∈F]，表示将i号虚拟机部署到j号物理机上。且单台物理机上虚拟机所占资源的总量，不得超过其自身资源总量，即：

[?m∈M，Qij≤Rj，j=1，2，…，n] （7）

[Qij]表示将i号虚拟机部署到j号物理机所占用的资源，[Rj]表示i号物理机的资源总量。

定义粒子（长度为l）表示部署方案，如公式（7）所示，其中[ki]表示将i号虚拟机部署到[ki]号物理机。

[x=k1，k2，…，ki，…kl，ki=1，2，…，n] （8）

定义粒子的速度为v，如公式（8）所示，其中[vi]表示第i位的变化量。

[v=v1，v2，…，vi，…vn，vi∈-n，n] （9）

3 基于改进粒子群的双适应度任务调度算法

由于虚拟机数量远小于云平台中的任务数量，因此需要研究获取将任务分配到虚拟机的最优分配方式，即最优的任务调度策略。传统的任务调度方式将重点放在了任务的完成时间上，而忽略了负载的均衡性，对此本研究提出了改进离子群的任务调度算法，来完善这一现象。

3.1 适应度函数

在任务调度算法中仍可沿用第2节所提出的改进粒子群算法，但要针对性的作出改进。为了能够根据虚拟机性能、任务情况等提前预知负载均衡度和任务总耗时，本研究采用了双适应度方法，即任务执行总时间和虚拟机负载均衡度，如公式（10）和公式（11）所示。

[F1（x）=maxr=1lj=1kTime（r，j）] （10）

其中l表示虚拟机总数，k表示r号虚拟机所执行的k号任务，[Time（r，j）]表示r号虚拟机所执行的j号任务运行耗时。考虑到虽然虚拟机间为并行，但虚拟机上任务为串行执行，因此可认为某一虚拟机运行时间的最大值即为任务执行的总耗时。

[F2（x）=1li=1l（mi-mavg）2] （11）

其中l表示虚拟机总数，[mi]表示i号虚拟机所有任务占据的内存总量，[mavg]表示所有虚拟机内存使用量的平均值。同样由于虚拟机上的任务以串行方式执行，因此无需比较内存占用率，而是将分配到每一个虚拟机上任务的内存总量作为计算负载均衡度的标准。

结合上述两个公式，定义粒子的适应度函数为：

[F（x）=1（αF1（x）+βF2（x））] （12）

其中[α]、[β]分别表示任务执行总时间和虚拟机负载均衡度两个适应度的影响因子，其值视实际情况而定，根据需要可以控制其中一项起主导作用。

至此可以得出，通过任务执行总时间和虚拟机负载均衡度两个适应度所共同得出的粒子优劣性，既保证了任务完成时间最短，又保证了虚拟机的负载均衡。

3.2 任务调度算法模型

定义云平台中虚拟机集合为[VM=vm1，vm2，vm3，…，vmn]（n表示虚拟机总数），任务集合为[T=t1，t2，t3，…，tl]（l表示任务总数），将任务分配至虚拟机的方案定义为[F?T×VM]，对于任意，表示将i号任务调度到j号虚拟机上。

定义粒子（长度为l）表示调度方案，如公式（13）所示，其中[ki]表示将i号任务调度到[ki]号虚拟机上。

[x=k1，k2，…，ki，…kl，ki=1，2，…，n] （13）

定义粒子的速度为v，如公式（14）所示，其中vi表示第i位的变化量。

[v=v1，v2，…，vi，…vn，vi∈-n，n] （14）

综合以上双适应度算法，公式（12）所得出的适应度函数值，即为粒子所对应调度策略的运行总时间和负载不均衡度共同作用的结果，值越小则调度策略越优。

4 资源调度算法仿真

仿真实验选取CloudSim工具，实验首先通过建立虚拟数据中心，并根据虚拟机部署算法将虚拟机部署到物理机上，再根据公式计算得出物理机的负载均衡度，以此验证算法的有效性。其次在上一实验的基础上，通过虚拟任务大小、指令长度随机的多个任务，并根据任务调度策略将任务分配至相应的虚拟机，最后通过判断任务执行时间即虚拟机的负载均衡度，来验证算法的有效性。

4.1 算法参数

4.1.1 虚拟机部署算法

将粒子的长度设为9，粒子位置上的数表示虚拟机所分配到的物理机。将迭代次数设为800，并作为算法的结束条件，当迭代次数超过该阈值时，便取此刻的全局最优解为虚拟机部署到物理机的最优方式。

4.1.2 任务调度算法

云任务的创建表如表3所示。

考虑到此次实验运行时间更为重要，因此定义公式（12）中的参数α=4，β=1，在保证负载均衡度的同时使总运行时间最短。

该实验的迭代次数同样设为800，当迭代次数超过该阈值时，便取此时的全局最优解为任务调度的最优方式。

4.2 结果分析

4.2.1 虚拟机部署算法结果分析

为了验证模拟退火算法的引入改善了传统粒子群算法的收敛性，实验将传统粒子群算法（PSO）与提出的虚拟机部署算法（即SA-PSO）相比较，定义F为适应度，Y=1-F为负载均衡度，实验结果如图3所示。

分析图3可知，传统粒子群算法在初次得到最优解后便认定该值为最优解，不再调整。而改进粒子算法由于退火模拟算法的作用，会跳出局部最优解并不断调整，最终获得更优的最优解，证明了引入模拟退火算法的有效性。为了验证改进粒子群算法在虚拟机部署方面的有效性，实验选取在同等条件下只改变虚拟机和物理机的个数，所得到的结果如图4所示。

分析图4可知，系统的负载均衡度会随着物理机和虚拟机个数的增加而降低，但使用改进粒子群算法的负载均衡度要优于传统粒子群算法的负载均衡度，能达到更好的部署效果。

4.2.2 任务调度算法结果分析

定义任务个数范围为50～400，梯度为50。指令长度范围为10000-30000MI，任務长度范围为200-400MB，两者均随机生成。通过提出的任务调度算法（DF-PSO）和贪心算法（GA）对任务进行调度，并比对任务完成的总时间和负载均衡度，得出的结果如图5所示。

分析图5可知，随着任务数量的增加，任务的执行时间几乎相同， GA的调度方式有时更优。

定义负载均衡度Y=1-F/10000，实验得出的任务调度算法（DF-PSO）和贪心算法（GA）的负载均衡度如图6所示。从图分析得出所提出的任务调度算法在负载均衡性上明显优于贪心算法。

分析图5和图6可知，所提出的基于粒子群双适应度任务调度算法，虽然牺牲了一定的任务执行时间，但却在负载均衡上占有很大的优势，因此对资源调度具有一定的价值。

5 结束语

在分析云资源调度方式的基础上，提出了基于改进粒子群的虚拟机部署算法以及基于改进粒子群的双适应度任务调度算法，并通过实验对资源调度算法进行了仿真，证明了算法在提高云计算资源利用效率方面的有效性。

参考文献：

[1] 邓传华，范通让，高峰. Hadoop下基于统计最优的资源调度算法[J].计算机应用研究，2013（2）：417-419+422.

[2] 姚婧，何聚厚. 基于自适应蜂群算法的云计算负载平衡机制[J].计算机应用，2012（9）：2448-2450+2454.

[3] M. Bist， M. Wariya and A. Agarwal， Comparing delta， open stack and Xen Cloud Platforms： A survey on open source IaaS， Advance Computing Conference （IACC）， 2013 IEEE 3rd International， Ghaziabad， 2013， pp. 96-100.

[4] Q. Li and Y. Guo， Optimization of Resource Scheduling in Cloud Computing， Symbolic and Numeric Algorithms for Scientific Computing （SYNASC）， 2010 12th International Symposium on， Timisoara， 2010， pp. 315-320.

[5] 罗中良，刘强，刘小勇. 一类混合模拟退火与蚁群优化算法及其收敛性分析[J].工业仪表与自动化装置，2008（4）：3-6.

[6] 苗壮. 基于CloudStack的IaaS资源调度策略研究[D].哈尔滨工业大学，2014.

[7] 马良. IAAS云计算平台中资源管理和调度技术的研究[D].北京邮电大学，2013.

[8] 王炳旭. 基于IaaS云平台的Hadoop资源调度策略研究[D].北京交通大学，2016.

[9] 张小庆. 基于云计算环境的资源提供优化方法研究[D].武汉理工大学，2013.

[10] Y. Wang， J. Wang， C. Wang， J. Sun and X. Song， "Utility optimization strategy of resource scheduling in cloud computing，" 2016 35th Chinese Control Conference （CCC）， Chengdu， 2016， pp. 5235-5238.

[11] 白凯. IaaS平台资源管理方案的设计与实现[D].西北大学，2012.

[12] 高贵升. 基于OpenStack的计算云的研究与实现[D].成都理工大学，2012.

[13] 王波，张晓磊. 基于粒子群遗传算法的云计算任务调度研究[J].计算机工程与应用，2015（6）：84-88