摘　要：任务调度是云计算实现高效计算的关键技术。本文采用粒子群算法进行任务调度求解，对每个子任务占用的资源采用间接编码方式，考虑时间和成本定义合理的初始化参数，选择合适的适应度函数，尽量避免陷入局部最优。仿真结果表明，改进算法具有寻优能力强、耗时少等优点，实现较为理想的任务调度结果。
关键词：云计算　任务调度　粒子群优化算法
      在云环境中面对巨大的计算型任务，目前的任务调度策略还不能达到所要求的调度效果^[[1]]。例如，遗传算法、分层调度算法、蚁群优化算法、种群初始化方法、与能效相关的耗感知的任务调度算法等，它们都不能达到较好地兼顾调度执行时间最少与成本最低问题，主要原因在于云计算模型中，任务执行所需要的成本也是一个不可忽略的因素。考虑了所有任务完成时间与所有任务完成的总成本这两个方面，设计了基于改进粒子群的任务调度算法，兼顾了任务执行时间和效率，实现执行时间最少的情况下还能使成本最低，从而达到节能的效果。
 
1　任务调度问题
在云计算中处理庞大的计算型任务常采用分布式并行处理的方式进行。云服务器在接收到一个完整的大任务后，采取恰当的方法拆分为若干个子任务，并将自任务合理分配到计算节点上去，当子任务处理完成后，汇总结果给云服务器回传给客户。云计算环境普遍采用是谷歌公司设计开发的Map/Reduce编程模型^[[2]]，工作原理是Map函数将用户提交的任务分解为多个子任务，并将这些子任务按照调度算法分配到虚拟机节点，待子任务执行完，再有Reduce函数将产生的中间结果进行汇总处理，图1表示其执行流程。


图1　Map/Reduce模型执行流程
 
2　粒子群算法
粒子群优化算法(Particle Swarm Optimization，简称PSO)是模拟鸟群觅食行为而发展起来的一种群体协作的随机搜索算法，属于群体智能算法的一种。PSO算法是由J.Kennedy博士和R.C.Eberhart于1995年共同提出的，因其算法程序结构简单、需要调节的参数较少、高效等特点，得到了众多学者的重视和研究^[[3]]。

2.1　间接编码

根据设计的要求采用粒子间接编码方式，每个任务需要占用的计算资源都要给出编码。本文假设R个任务，Z个资源，并且把每个任务又分成了若干个较小的子任务。子任务的总数量表示为：                                              （1）
其中，RNum(s)表示第s个任务所含子任务个数。对子任务的编码如下：
                                          （2）
根据任务的顺序进行编码，第j个任务中的第i个序号是N[j，i]。假设R=3、Z=3、SR=10，粒子(2,3,1,2,3,3,2,1,2,1)是一个可行的调度策略。
对于任务的执行时间，根据设计的要求本文利用矩阵来记录，元素[j,i]表示子任务j在第i个资源上执行的时间。按单位时间计算资源，任务执行的成本费用利用RWCB数组来表示。RWCB[z]表示第z个计算资源单位时间，任务运行的成本费用。
第z个资源执行该资源上第j个子任务，所用的时间用r(z,j)来表示；分配到此资源上的子任务，其数量用m来表示。完成所有任务花费的总时间可以表达为：     
                                           （3）
第s个任务完成时间表示可描述为：
                                      （4)
完成所有任务的总成本可以表示为：
                                                     (5)

2.2　粒子位置和速度的更新

PSO算法中粒子的速度和位置的计算更新公式表示如下：
                           (6)
                                                                                   (7)
其中，表示第个粒子在第代的位置；表示第个粒子在第代的速度；表示第个粒子在第代所经历的历史最优位置；代表全局最优位置；表示算法的惯性权重，在经典算法中它的取值一般为0.942，用于衡量旧的速度对新速度的影响；和为加速常数，一般情况下取值为1；和是相互独立的随机数。对惯性权重进一步优化，提出一种小阻尼随机扰动的改进方法，惯性权重计算公式如下所示：
                             （8）
式中，为引入的小阻尼振动函数，利用小阻尼振动来非线性地控制算法中的惯性权重编号情况，使其随着迭代次数的增加而出现非线性随机扰动现象。在惯性权重中加入了小阻尼随机扰动策略，既增强了种群的多样性，而且还拓展了PSO算法的开拓能力^[3]，有效地避免了停滞现象的发生。图2表示了改进粒子群优化算法的执行流程。


图2  改进PSO算法流程图

3　实验仿真结果及分析

在Matlab R2009b上实现该算法仿真，并将算法应用到云计算平台的资源调度模块中。利用云计算仿真平台CloudSim对两个算法进行了相同云环境下的仿真实验，并进行比较，实验迭代运行200次，根据参考文献[[4]]，算法参数设定为：粒子群规模150，迭代次数t_max=200，学习因子c1=c2=0.926，权重参数w=0.9。把任务数设置为100，则改进PSO算法和标准PSO算法的收敛曲线和任务完成时间分别如图3和图4所示。


图3　改进PSO算法与标准PSO算法总任务完成时间对比
             

图4　高任务强度下算法的任务完成对比情况
从仿真结果可以看出，粒子在前期迭代过程中，经典粒子群算法与本文改进的粒子群在任务总完成时间和成本相差不太大，但随着粒子迭代更新数量的增大，本文改进的粒子群算法所得到的任务完成时间和成本都在不断的减小，明显小于传统的粒子群算法。传统的粒子群算法丢失了一些潜在优良粒子，虽然提高了收敛速度，但是无法有效跳出局部最优状态，过早收敛到局部最优的调度结果上^[4]。本文算法设计了合适的适应度函数，不仅考虑所有任务完成的时间，也考虑所有任务完成所需要的成本费用，该算法任务调度结果表明，所有任务完成所需要的时间缩短了，执行效率也较传统PSO算法提高了。

 

4　结语

对于任务调度算法，一般采用总任务完成时间作为度量标准，却没考虑任务完成所需成本，本文针对云计算的任务调度模型，在改进粒子群算法的基础上，提出了一种改进的任务调度算法，既考虑了所有任务完成的总时间，也考虑了任务完成所需要的总成本。今后将从参数设置、惯性权重等方面进一步研究IPSO算法对任务调度效率的影响，从而进一步提高执行效率，实现更为理想的调度效果和负载均衡。
 
参考文献：
[[1]]骆剑平,