基于烟花算法的云计算任务调度研究

孙凤杰，王克俭*，何振学，高万豪

(1. 河北农业大学信息科学与技术学院，河北 保定 071001；2. 天津城建大学控制与机械工程学院，天津 300384)

1 引言

云计算是基于分布式计算、网格计算以及并行计算发展起来的新型计算模式，并且成为当今社会的一个热点研究方向。云计算中的任务调度算法会影响到云计算的效率。云计算环境下将任务动态地调用给各个虚拟机并提供给用户使用，怎样合理地将任务分配给不同的虚拟资源，进而使得整个系统的性能达到最优效果，是云任务调度算法需要解决的关键性问题[1]。传统的云任务调度算法有：贪心算法、轮询调度算法等，对于少量任务来说，这些算法可以取得较好地效果，但是随着任务数量的不断增加，传统算法存在着完成时间较长、负载不均衡以及资源利用率低等一系列缺点[2]。因此，为了解决传统算法所带来的缺点，一些群体智能算法不断地被应用于云任务调度中，并且成为目前研究的热点，比如遗传算法[3，4]、蚁群算法[5]、粒子群算法[6，7]、烟花算法[8]。

屈迟文等人[9]提出了一种基于改进遗传算法的任务调度算法，该算法通过检测个体相似度增加交叉操作的有效性对算法进行改进，但是没有考虑任务的完成成本。刘峰等人[10]提出了一种基于时间和负载均衡的双适应度函数改进的遗传算法，但是缺乏对任务的完成成本的优化。齐平等人[11]提出了一种将粒子群算法与资源可靠性评估模型相结合的调度算法，虽然解决了资源失效问题，但是没有考虑任务的完成时间和成本。王欣欣等人[12]提出了一种基于任务完成时间和能量消耗的动态遗传算法的云计算资源调度，该算法降低了时间和能量，但是未考虑任务的成本。

谭营等人[12]首次尝试将离散烟花算法用于求解旅行商问题，并且得到了不错的效果，除此之外，烟花算法还被应用于0/1背包问题上[14]、方程组求解问题上[15]、施肥问题上[16]、图像识别领域[16]。在云计算任务调度中，极少的涉及到烟花算法。因此，在云计算中，为了寻找最优的云任务调度方案，使得任务完成时间短、成本低，本文提出了一种将烟花算法与云计算任务调度模型相结合的任务调度算法，并且通过CloudSim进行实验，验证了本文算法的有效性。

2 云计算中任务调度模型

2.1 云任务调度的描述

云任务调度模[18]主要由以下部分构成：任务、任务管理器、任务调度器和云环境，模型如图1所示。在该模型中，云任务调度分为两个级别，第一级别是任务到虚拟机的调度，主要是研究任务调度算法，即当用户提交任务到数据中心时，合理地将任务调度到虚拟机进行执行；第二级别是虚拟机到物理机的调度，即将虚拟机接收的任务调度到合适的主机并运行的过程。本文研究的是第一级别的调度，即云任务调度。 在该任务调度过程中，采用任务调度策略将用户所提交的n个任务合理地分配至m个空闲的虚拟资源上使用(n>m)，进而达到时间短、成本低、负载均衡等目标，其中任务调度策略就是用户所使用的不同的调度算法。

图1 任务调度模型

2.2 云任务调度中的相关定义

本文中用n来表示云任务的数量，m来表示虚拟机的数量，etcij表示第j个任务在第i个虚拟资源上的执行时间，i∈[1，m]，j∈[1，n]，用来计算各个虚拟资源上任务运行完成所需的时间，rcui表示第i个虚拟机的单位成本。本文将任务的完成时间和成本作为云计算中任务调度效果的评价指标。

1)任务完成时间

云计算中任务完成时间是衡量任务调度效果的重要因素之一，任务完成时间如式(1)所示

(1)

(2)

式中，task＿length(j)为第j个任务的长度，mipsi为第i个虚拟机的处理速度。

2)任务的完成成本

除了完成时间外，另一个重要的衡量因素是任务完成成本，任务的完成成本如式(3)所示

(3)

(4)

式中，vm＿cost(i)为第i个虚拟机的花费。

3 基于烟花算法的云任务调度算法

2010年谭营教授和其团队提出了烟花算法[13]，它是通过模拟自然界中烟花爆炸过程所形成的群体智能优化算法，并且具有局部性、随机性以及多样性的特点，主要用于复杂问题的优化。烟花算法把每一烟花作为问题的一个可行解，根据适应度函数来计算每一烟花所产生火花数，适应度值越大的烟花产生的火花数目越多，反之越少，其中烟花爆炸所产生一定数量火花的过程就是搜索邻域的过程。烟花算法主要由爆炸算子、变异算子以及选择策略三部分组成。

3.1 算法的编码

本文采用了资源-任务的编码方式，这种编码方式通俗易懂，操作简单，不易出错。比如烟花为{2，3，4，1，2，3，4，1，2，3}，10个任务分配给4个虚拟资源，编号1、2、3和4的虚拟资源上所对应的任务数为2、3、3和2，即：{{1，2}，{2，3}，{3，4}，{4，1}，{5，2}，{6，3}，{7，4}，{8，1}，{9，2}，{10，3}}，表示1号任务分配给2号虚拟资源，2号任务分配给3号虚拟资源，以此类推，10号任务分配给3号虚拟资源，编码方式如图2所示，Vi为任务Ti执行时所对应的虚拟资源编号，Ti为任务编号。

图2 编码方式

假设有n个任务，m个虚拟资源，一个烟花为{3，2，1，4，3，2，…，m，m-1}，表示第1个任务分配到第3个虚拟资源上，第2个任务分配到第2个虚拟资源上，第3个任务分配到第1个虚拟资源上，第4个任务分配到第4个虚拟资源上，以此类推，任务和虚拟资源所对应的关系如表1所示。

表1 任务与虚拟资源所对应的关系

3.2 适应度函数的设计

在一定程度上适应度值决定着种群个体的生存能力，烟花算法中是通过计算每个烟花的适应度值来确定每个烟花所产生的火花数量，适应度值越大的烟花产生更多的火花，反之，产生更少的火花。本文采用时间适应度函数、成本适应度函数，对于烟花wi的适应度函数如下。

时间适应度函数的定义如式(5)所示

(5)

(6)

式中，u为虚拟资源的利用率情况，该值越大，虚拟资源的利用率越高。

成本适应度函数的定义如式(7)所示

(7)

因此，本文所设计的基于任务完成时间和成本的适应度函数如式(8)

fit(wi)=α×fit1(wi)+β×fit2(wi)

(8)

式中，α∈[0，1]，任务完成时间的权重，β∈[0，1]，任务完成成本的权重。根据自己的偏好决定权重的取值，并且满足α+β=1。

3.3 爆炸算子

算法初始化时，适应度越好的烟花可以产生更多的火花，具有较强的局部搜索能力，适应度越差的烟花可以产生越少的火花。烟花wi所产生的爆炸半径Ri和爆炸火花的数量Si分别如式(9)和(10)所示。

(9)

(10)

式中，fitmin和fitmax分别表示当前烟花种群中适应度最小值和适应度值最大值，fit(wi)为个体wi的适应度值。γ为基本的爆炸幅度，用来调整爆炸半径的大小，ρ为基本的爆炸火花数目，用来控制产生火花数目的大小，δ为极小常数，主要防止分母为0。

为了确保所产生的火花总数比较稳定，避免出现好的烟花数目较多、差的烟花数目较少的状况，需要限制火花个数，如式(11)所示。

(11)

式中，a和b为常数。

3.4 变异算子

为了保证烟花种群的多样性，避免算法出现局部峰值的现象，引入变异算子来产生变异火花，本文采用了高斯变异：先在烟花种群中随机选择一个烟花wi，然后随机选择维度k进行高斯变异操作，如式(12)所示

(12)

在产生爆炸火花和高斯变异火花的过程中，所产生的火花可能会超出边界范围，因此对超出边界的个体采用映射规则，如式(13)所示。

(13)

3.5 选择策略

为了保证烟花种群中优秀的个体传递到下一代中，在产生爆炸火花和高斯变异火花后，种群中包括烟花、爆炸火花以及高斯变异火花，适应度值最大的个体直接被保留至下一代，其余N-1个个体本文采用轮盘赌的方式进行选择，选择概率如式(14)所示。

(14)

(15)

式中，sum(wi)为个体wi与其它个体的欧氏距离，K表示烟花和所产生的火花构成的种群集合。

3.6 算法描述

烟花算法的整体流程如下：

Step1：随机初始化烟花种群，产生N个烟花wi(i=1，2，3，…，N)，最大迭代次数gMax。

Step2：根据式(8)计算适应度值。

Step3：根据式(9)、(10)和(11)计算每个烟花wi的爆炸半径以及所产生的爆炸火花数，产生爆炸火花。

Step4：根据式(12)产生高斯变异火花，若有火花越界，则根据式(13)将超出边界的火花映回到可行域。

Step5：将适应度值最好的烟花或者火花保留到下一代，从烟花种群中根据式(14)和(15)选择N-1个烟花。

Step6 如果迭代次数达到最大值，则输出最终结果，否则，转至Step2。

算法流程图如图3所示。

图3 算法流程图

4 实验结果分析

4.1 实验环境

为了验证本文算法的有效性，本文采用墨尔本大学Buyya教授带领开发的CloudSim平台[19]来模拟云计算环境，并对实验结果进行分析。实验环境：eclipse2018、Intel(R)Core(TM) i5-4210U CPU 1.70GHz 2.40GHz的处理器，4.00GB的内存。算法中主要参数的取值：基本爆炸火花数ρ=40，基本爆炸幅度γ=50，高斯火花个数M=5，参数a=0.8，参数b=0.04，α=0.2，β=0.8。

4.2 实验及结果分析

实验中云任务长度在500-20000之间，虚拟资源的运算能力在1000-5000MIPS之间，最大迭代次数gMax为100，烟花种群大小N为30，将本文算法与GA、PSO和文献[19]TCGA算法进行对比，分析比较任务数的变化对任务的总完成时间和任务的总完成成本的影响。

1)当资源数目为10个时，改变任务的数量从10个到220个，任务数分别是：10、40、70、100、130、160、190、220，然后记录任务总完成时间的变化，如图4所示。

图4 不同任务数下的任务总完成时间结果对比图

从图4中可以得出，当资源数不变时，任务数逐渐增加，本文算法的任务总完成时间要比GA、PSO和TCGA算法少。当任务数比较少时，算法的效果不是特别明显，主要是因为资源数和任务数的差别不是特别大，资源节点有能力去处理这些任务，但是当任务数多于100时，本文算法下的任务总完成时间明显比其它三种算法好，并且本文算法的任务完成时间比GA降低了20%左右，比PSO降低了18%左右，比TCGA算法降低了15%左右。

2)当资源数目为10个时，改变任务的数量从10个到220个，任务数分别是：10、40、70、100、130、160、190、220，然后记录任务总完成成本的变化，如图5所示。

图5 不同任务数下的任务总完成成本结果对比图

从图5可以得出，本文算法的效果优于其它三种算法，并且随之任务数的不断增加，本文算法的效果更明显，并且本文算法的任务总完成成本比GA降低了14%左右，比PSO降低了13%左右，比TCGA算法降低了9%左右。

从以上结果可以看出，本文所提出的基于烟花算法的任务调度算法的效果更好，不仅有效的缩短了任务完成时间，而且降低了任务完成成本。

5 总结

为了降低云计算中任务调度完成时间和成本，并且为了保证种群多样性，避免早熟收敛等问题，本文将烟花算法用于任务调度中。本文算法将任务完成时间和成本同时作为优化目标对云计算中任务进行调度，仿真结果表明，本文算法可以在云计算中实现比较合理地任务调度，缩短了任务的执行时间，并且降低了任务完成成本。

未来的工作中可以考虑其它因素对云计算中任务调度结果的影响，比如网络服务质量，并且为了提高烟花算法的效率，可以在集群环境中研究任务调度问题。