基于简化粒子群和蚁群优化的云计算资源调度算法

王 猛，谭跃生（内蒙古科技大学工程训练中心，内蒙古 包头 014010）

基于简化粒子群和蚁群优化的云计算资源调度算法

王 猛，谭跃生
（内蒙古科技大学工程训练中心，内蒙古 包头 014010）

为了提高云计算环境下资源调度的效率，将BPSO-ACO算法应用到云计算的资源调度过程中，通过CloudSim平台的仿真实验，与粒子群算法和蚁群算法做比较，得到在同等条件下，简化粒子群优化和蚁群优化算法（BPSO-ACO）比单独的粒子群算法或蚁群算法在进行资源调度时，总任务的完成时间更短、收敛性更好。

云计算；资源调度；粒子群算法；蚁群算法

0　引言

1　云计算资源调度模型

云计算环境中有n个任务的集合T=（T1，T2， …，Tn） 分配到m个虚拟资源集合VM=（VM1，VM2， …，VMm） 上完成，其中Ti（i=1，2，3…n）表示第i个子任务，VMj（j=1，2，3…m）表示第j个虚拟资源，粒子群中一个粒子位置就是一个可行解，即一个资源分配序列，任务集合T在虚拟资源VM上的分配关系可表示为：

这是一个N维向量，其中xij表示任务i被分配到虚拟资源VMj上，xij是一个可行的资源分配方案。

定义CTij（i∈｛1，2，…，m｝，j∈｛1，2，…，n｝）表示任务Ti在虚拟资源VMj的完成时间:

目标是使得CTmax的值最小。

2　粒子群算法的优化及编码

对于粒子群算法的优化，大多数的改进是通过对参数自适应调整或杂交、变异参数或增加操作算子获得的。上述调整使得PSO算法越来越复杂，使得对于PSO收敛性的定量分析非常麻烦［2-3］。

通过分析粒子群算法可以发现：在粒子群中 ， 粒子速度概念不是必需的，因此 ，只需要考虑粒子位置的直接变化。参数vi代表粒子的速度，粒子速度的不能表示粒子趋近最优解位置的趋势。通过上述分析，粒子群算法可以优化为公式2.1：

在粒子群中，每一个粒子就代表一个可行的调度方案，各虚拟资源节点VMj处理所有分配到该资源节点上的任务的总完成时间CTj，选取CTj｛j=1，2，3，4，5｝中完成时间最长的。

1.1 材料 试验于2017年7月进行，材料选择广西南亚热带农业科学研究所名优茶种植基地1芽1叶黄观音秋季鲜叶。基地位置属南亚热带季风气候，海拔>100 m，全年平均气温21～22 ℃，地势平坦，土壤pH 5.5～6.5。制茶主要设备：摇青机、6CR-35型揉捻机、YX-6CFJ-10B型全自动红茶发酵机、理条机、6CTH型烘干机。检测主要设备：气相-质谱联用仪(GC- MS)、紫外分光光度仪、全自动化学分析仪、电子天平、茶叶审评用具。

3　蚁群算法

3.1信息素初始化

初始阶段，蚁群算法用粒子群算法的调度结果作为其初始节点，并对节点上的信息素加强若干倍数，使得蚁群算法在初期的收敛速度变快，让其尽快搜索到最优解。

3.2路径的选择

现在假设，在t时刻，蚂蚁k选择xij节点的概率如公式3.1所示。

3.3信息素更新规则

当每只蚂蚁经过一个虚拟资源节点或遍历过所有虚拟资源节点的时候，要对虚拟资源节点上的信息素更新。在t+1时刻信息素更新规则如公式3.3和公式3.4所示。

表示信息素的挥发系数，1-ρ表示信息素的残留系数，通常ρ的取值范围是0到1之间。

Δτj（t）表示t时刻，虚拟资源节点VMj上的信息素增量。

其中Q为常数，表示所有任务执行完的总时间，CTi表示任务Ti的执行花费即时间。

4　仿真实验

本文选择CloudSim仿真平台进行仿真实验，将简化粒子群结合蚁群的算法（BPSO-ACO）云计算资源调度模型引入到CloudSim的资源调度系统中，通过仿真实验验证简化粒子群结合蚁群的算法（BPSOACO）的云计算资源调度性能。

本实验中，为了检验粒子群算法（PSO）、蚁群算法（ACO）与简化粒子群结合蚁群算法（BPSO-ACO）的性能，在CloudSim平台下设置3个虚拟资源节点和20到100个子任务，对比分析。

各类算法的参数设置如下描述：

（1）对于简化粒子群算法的参数设置如下：粒子的规模设置为100，c1=c2=2，迭代次数设置为30次。

（2）对于蚁群算法的参数设置如下：蚁群的规模设置为100，α=β=1，ρ=0.7，迭代次数设置为70次。

图1　PSO与BPSO-ACO的对比

（3）对于简化粒子群结合蚁群算法的参数设置如下：与粒子群算法和蚁群算法相同的参数，设置为相同的值，迭代次数设置为100次。通过CloudSim进行20次仿真实验，取平均值，进行测试，结果如图1，图2所示。

图1与图2可以看出，在初始状态，当任务量较少的情况下，BPSO-ACO算法的完成时间与PSO算法、ACO算法的总完成时间相差不多，但是随着任务量的增加，完成时间的差距越来越明显，说明BPSO-ACO算法在任务量大的情况下的收敛性明显好于PSO算法和ACO算法。

通过仿真实验证明：BPSO-ACO算法能够对资源进行合理的调度，总得完成时间要优于PSO算法和ACO算法。

图2　ACO与BPSO-ACO的对比

Arfeen M A， Pawlikowski K， Willig A. A Framework for Resource Allocation Strategies in CloudComputing Environment［J］. Computer Software and Applications Conference Workshops （COMPSACW），2011 IEEE 35th Annual.2011，261-266.

Clerc M， Kennedy J. The particle swarm： Explosion stability and convergence in a multi-dimensional complex space. IEEE Trans.on Evolution Computer， 2002，6（1）：58-73.

Trelea IC. The particle swarm optimization algorithm：Convergence analysis and parameter selection. Information ProcessingLetters， 2003，85（6）：317-325.

10.16640/j.cnki.37-1222/t.2016.14.116