自适应动态调整粒子群的云计算任务调度

侯 欢 欢

(太原工业学院计算机工程系 山西 太原 030008)

0 引 言

云计算是一种新型的商业计算模式，它是并行计算、分布式计算和网格计算融合发展的结果。云计算的发展一直与大数据密切相关，正是依靠云计算技术才使庞大的数字资源得以高效的分析处理[1]。为提高数据处理的高效性，云计算将每个任务分成若干个相互独立的任务，通过任务调度将任务分配给计算资源进行处理。随着用户需求的日益提高，如何满足用户请求,提高云计算任务调度效率已经成为云计算研究领域的关键问题之一。传统任务调度算法很难均衡云计算环境下的多维约束调度，粒子群优化算法(Partical Swarm Optimization，PSO)是一种群体智能全局寻优的算法[2]。该智能优化算法在优化组合、多目标寻优、聚类分析等领域应用广泛且效果突出[3-5],利用智能优化算法在多维度多任务方面的寻优优势引起了越来越多学者的研究与关注，已成为云计算任务调度的新工具。文献[6]在分组遗传算法的基础上，提出了基于多维资源协同聚合的虚拟机调度策略，对均衡资源分配具有一定的优势；文献[7]提出了基于改进遗传算法的云计算任务调度，通过两个适应度来选择种群，缩短了总任务和平均任务完成时间；文献[8]综合考虑遗传算法和蚁群算法的优势,提出一种遗传-蚁群算法的云计算任务调度优化算法,提高云计算任务求解效率；文献[9]把改进的蚁群算法应用到云计算任务调度中，实现了虚拟机的负载均衡和调度时间的优化；文献[10]针对用户满意度和云提供商利益需求，提出一种融合粒子群和遗传算法的PSOGA改进算法;文献[11]在遗传算法基础上,提出了一种考虑时间、成本、CPU、内存和带宽等多维约束的任务调度算法MCGA；文献[12]针对标准量子粒子群优化算法收敛速度慢、求解效率低的缺陷,提出一种基于改进量子粒子群算法的云计算资源调度方法;文献[13]提出了一种基于非占优排序的混合多目标粒子群优化的工作流调度算法HPSO,使调度解的空间分布更加一致，云环境工作流调度更优化；文献[14]综合考虑任务截止时间、调度预算和可靠性，提出一种多QOS约束离散粒子群优化的任务调度算法,有效解决了多约束任务调度。本文融合改进的分数阶达尔文粒子群算法和多目标函数构造，提出了一种新的云计算任务调度算法。

1 粒子群优化算法及其衍化

1.1 粒子群算法

粒子群优化算法与其他智能优化算法一样，易陷入局部最优、搜索精度不高、后期收敛慢等问题。针对这些问题，国内外学者提出了多种改进算法。文献[15]将达尔文进化理论引入粒子群优化算法中，提出了一种达尔文粒子群优化算法(Darwinian Partical Swarm Optimization,DPSO)。文献[16]将分数阶微分理论引入粒子群优化算法中，提出了分数阶粒子优化算法(Fractional Order Partical Swarm Optimization,FOPSO),通过重排原始速度来修正速度导数以便控制优化算法的收敛速度，取得了不错的效果。受文献[16]的启发，学者Micael将分数阶微分和达尔文进化理论相结合，集中两者的优点应用于粒子群优化算法中，提出了分数阶达尔文粒子群算法(Fractional Order Darwinian Partical Swarm Optimization,FODPSO)。实验结果表明，与其他智能优化算法相比，该算法通过分数阶次α来控制计算精度与收敛速度，由于过度依赖分数阶次α，容易造成局部最优[17]。恰当的权重系数ω不仅能提高寻优能力还能加速收敛速度。但现实中对权重系数ω的设置往往是手动设置固定值，这不利于粒子群对最优解的搜索。

在一个M维目标空间中，Nnum个粒子组成群落，每个粒子的速度和位置更新：

(1)

(2)

第i个粒子位置向量为Xi=(xi1,xi2,…,xiD)，速度向量为Vi=(vi1,vi2,…,viD)，第i个粒子经历过的位置中最优位置Wi=(wi1,wi2,…,wiD)，整个粒子群最优位置Wg=(wg1,wg2,…,wgD)。式(1)中：ω表示惯性系数；c1、c2表示加速系数；R1d、R2d为[0,1]间的随机数；wid表示粒子个体最优值；wgd表示粒子群整体最优值。

1.2 粒子群算法的衍化

DPSO将自然选择理论引入算法中，对粒子群的寿命进行动态缩减。设SC为粒子搜索计数器用以追踪粒子群适应值没有改变次数。当粒子群适应度没有提高时，其中的粒子被删除后，该粒子群的搜索计数器不置为0，而以下式进行设置：

(3)

式中：Nkill表示粒子群适应值没变化期间被删除的粒子数；SCmax表示最大计数值。若粒子群中所有粒子被删除，且当前粒子群数没有超过种群设置数，新建粒子群概率为：

p=r/Nnum

(4)

式中：r为[0,1]间随机数；Nnum表示种群粒子数。文献[17]给出了分数阶次α调整公式：

(5)

通过大量实验可知分数阶次α在[0.5,0.8]之间时，FODPSO算法可取得较快的收敛速度。但是通过式(5)可以看出：随着迭代次数的加大，分数阶次α会线性减小，这势必会使粒子群陷入局部最优和低速收敛。同时根据式(1)可以看出：权重系数ω越大，速度v就大，这有利于扩大最优解的搜索空间；当权重系数ω越小，速度v就小，这会在当前解空间中挖掘更好解，因此权重系数ω的设置不能拘泥于定值。对此，本文通过改变分数阶次α和惯性权重系数ω的调整方式和陷入局部最优的跳出方式，对分数阶达尔文粒子群算法进行改进。

2 改进分数阶达尔文粒子群算法

2.1 基于自适应动态调整权重系数

研究学者统计实验发现，动态的权重系数要比固定设置的能获得更好的寻优结果[18]。借鉴前人研究，将粒子的适应度值引入惯性权重系数ω的调整中，提出了一种基于自适应度动态调整权重系数的方法。设favg为粒子群平均适应度，fbest为粒子群最佳适应度，第i个粒子的适应度为fi，惯性权重系数ω的调整如下：

(6)

式中：ωmin、ωmax表示惯性权重系数ω的最小、最大值。通过式(6)我们可以看出当前粒子适应度与平均适应度差值越大，惯性权重系数ω越小，这有利于局部搜索；反之，当前粒子适应度与平均适应度差值越小，惯性权重系数ω越大，有利于粒子跳出局部进行范围更广的搜索最优解。

2.2 基于进化信息调整分数阶次α

(7)

(8)

(9)

(10)

(11)

基于粒子进化因子fev∈[0,1]，利用高斯图函数得出分数阶次α的调整公式：

(12)

通过式(12)可知，分数阶次α的调整不再依赖迭代次数，而是依据粒子自身的进化信息，这可避免算法因分数阶次α线性减小而引起的局部最优和收敛缓慢。

根据分数阶微分方程的格林瓦德-列特尼科夫(G-L)定义，粒子速度更新策略变为：

(13)

粒子的位置更新依据式(2)进行，其中加速系数满足3≤c1+c2≤4。

2.3 基于Levy飞行特征的局部最优

本文将Levy飞行特性引入改进的分数阶达尔文粒子群算法中，利用Levy飞行特性扩展搜索空间，根据局部最优概率因子popt对算法取得局部最优wg进行位置扰动。

定义局部最优概率因子popt：

(14)

wgd=wgd(1+levy(ξ)tanh(fev))

(15)

式中:Levy(ξ)是随机搜索路径，步长的大小通过levy分布随机数产生且1≤ξ≤3，0≤fev≤1，0≤tanh(·)≤1。

3 云计算任务调度

云计算是利用并行计算来处理大数据，是按需服务的模式，资源调度与网格计算的任务调度相差无几，但云计算以资源虚拟化为前提，通常采用Map/Reduce分布处理技术[19]。云计算任务调度数学模型可表示为：

Model={T,VM,F,A}

(16)

式中：任务集合T={T1,T2,…，Tn}；n表示任务的个数；每个任务都有属性TAi=,sTi、eTi、dTi,TLi分别表示任务的大小、最早开始时间、最迟完成时间和任务执行总时间。虚拟机集合VM={VM1,VM2,…，VMm}，其中m表示虚拟机个数。每个虚拟机都有属性：VAj=,Vcompj、Vcpuj、Vramj、Vbwj分别表示虚拟机j的处理能力、CPU、内存、带宽。

3.1 任务调度的多目标

综合评价云计算任务调度的优良需要从客户最短等待时间、虚拟机资源负载均衡程度及任务完成所耗费用等不同角度进行。

(1) 客户最短等待时间WFi:

(17)

式中：timeij表示任务Ti在所分配的虚拟机VMj上执行所需时间；sum(VMj)表示分配到虚拟机VMj上的任务总数。综上可知客户最短等待时间WFi表示各个虚拟机处理完成分配到的任务Ti的最迟完成时间的最大值。这里需要特别说明，任务的处理时间等于任务指令长度除以运行该任务虚拟机的执行速度：

timeij=TAi/VAj

(18)

(2) 虚拟机资源负载均衡程度ϖ:

(19)

(3) 任务完成所耗费用Cost:

(20)

式(20)体现了虚拟机VMj上处理任务的费用所耗，所用费用与虚拟机的CPU、内存、带宽性能有关。

本文从客户最短等待时间、虚拟机资源负载均衡程度及任务完成所耗费用等三个目标出发综合衡量云计算任务调度的优良，数学模型如下：

minWF,minϖ,minCost

(21)

式中: 目标函数minWF、minϖ、minCost表示客户最短等待时间、虚拟机资源负载均衡程度及任务完成所耗费用等三个目标要同时取得最小值，并且约束条件是任务只能被一个虚拟机执行。

3.2 任务调度多目标函数构造

任务调度的好坏不仅仅由一个目标函数决定，本文将最短等待时间、虚拟机资源负载均衡程度及任务完成所耗费用等三个目标以基于先验偏好[20]构造任务调度满意度函数，再将任务调度的多目标问题转化成单目标问题。设客户最短等待时间的区间为[WFmin,WFmax]，虚拟机资源负载均衡程度满意区间[ϖmin,ϖmax]，任务完成所耗费用区间[Costmin,Costmax]，引入极小值ε，三个目标的计算如下：

(22)

(23)

(24)

利用几何平均法将以上三个目标进行融合，任务调度综合满意度评价为：

(25)

通过式(25)可知，利用几何平均法将三个评价目标转换为综合满意度CS，并且只有当且仅当三个评价目标同时满意度为1时，综合满意度CS才为1。

3.3 粒子编码规则

粒子编码有两种，一是直接编码，另一种是间接编码。本文采用间接编码方式即对每个子任务所对应的虚拟机进行编码，也就是说一个粒子对应着一个任务的分配策略。比如任务数n=3，虚拟机数m=3,任务分解后的子任务数mall=10，粒子编码(2,3,1,2,3,3,2,1,2,1)即为一种可行的任务调度方案。粒子编码如表1所示。

表1 粒子编码

续表1

表1中，任务序号、子任务序号对(3,9)表示第3个任务中的第4个子任务序号为9；子任务序号、虚拟机序号对(2,3)表示把子任务2分配到虚拟机3上去执行。

4 仿真实验

为了验证本文改进算法的优越性，从两个方面进行对比分析：一是利用四种测试函数对比寻优效果；二是通过任务调度对比分析算法的调度性能。采用Cloudsim 3.0云平台软件对算法的实际调度性能进行仿真对比，仿真是在Windows 7系统下，CPU：i5-4460T@2.7 GHz, RAM:4 GB。

4.1 寻优效果对比分析

将本文算法、FOPSO和FODPSO在表2所示的四个标准函数上[17]对比寻优效果。三种粒子群优化算法的参数设置如表3所示。种群规模设为50，最大迭代次数为1 000次。三种粒子群优化算法运行100次取平均。

表2 四个标准函数

表3 参数设置

图1为三种智能优化算法对表2四个标准函数的寻优收敛曲线。

图1 三种粒子群优化算法寻优收敛曲线

由图1可以看出：FOPSO和FODPSO对Rastrigin标准函数的寻优效果一般，过早陷入了局部最优；随着迭代次数的增加，FOPSO和FODPSO在多峰Ackley函数、单峰Sphere、Rosenbrock函数上，收敛速度缓慢，寻优精度不精。而本文改进算法无论是对Sphere、Rosenbrock两种单峰函数还是对Rastrigin、Ackley多峰函数都能在若干次迭代后迅速从局部最优中跳出，并快速搜寻到最优值，扩大了对最优值的全局搜索能力。

4.2 任务调度对比分析

在Cloudsim 3.0平台中将云计算任务调度算法添加到DatacenterBroker类中；通过重置Cloudlet类和VM类进行虚拟机和任务的参数设置。将本文改进算法与文献[10，13，21]进行云计算任务调度，使用最大完成时间、截止时间违背率和虚拟机资源利用率三个云计算任务调度评价指标定量分析调度结果。本文粒子群参数设置详见表3，任务数n=200，资源数m=50，其他算法的参数设置参照对应参考文献。

(1) 最大完成时间。最大完成时间是评价任务调度的重要指标，最大完成时间越小表示任务完成的速度越快，算法的调度性能越好。通过设置不同的任务量，对比各算法的最大完成时间，结果如图2所示。

图2 四种任务调度算法最大完成时间

图2显示了在不同任务总数参与调度的情况下，各调度算法最大完成时间的趋势。随着任务数的增多，各算法完成任务调度的最大完成时间随之增大。文献[13]不仅改进了粒子算法固有的寻优劣势，还综合了任务调度的多目标，将最晚完成时间作为任务调度的考核目标之一，任务完成的最大时间与其他两种算法相比较小。文献[10，21]对粒子群算法的改进并不彻底，粒子群算法任然存在陷入局部最优和收敛过慢的毛病，并且调度考核的目标单一，任务完成最大时间随着任务数的增大而不断增大。本文算法通过调整分数阶次α系数以加速收敛，利用Levy飞行随机扰动以摆脱局部最优，自适应动态调整权重系数来收缩自如地寻找最优值，较为全面地改进分数阶达尔文粒子群算法，并将最短等待时间、资源负载均衡程度及任务完成所耗费用等三个目标规划为单一目标评价函数，以作为任务调度的评价目标，取得了较好的调度效果。

(2) 截止时间未完成率。截止时间是任务调度最根本的要求，也是考量任务调度的基本指标。调度算法对大量任务进行调度时，很难万无一失地在截止时间前完成所有数据处理。截止时间未完成率就是在截止时间未完成的任务数与总任务数的间比值。通过设置不同的任务量，对比各算法的截止时间未完成率，结果如图3所示。

图3 四种任务调度算法截止时间未完成率

图3显示了不同任务总数与截止时间未完成率的关系。随着任务数的增多，本文任务调度算法与文献[13]都维持在较低的截止时间未完成率，两者相比较而言，本文调度算法的未完成率较低，一直保持在5%以下，这是由于本文的目标函数中有客户最短等待时间这一评价约束目标。文献[21]单以截止时间为约束，粒子群优化算法改进不到位，制约了最终的调度结果。文献[10]主要考虑任务与资源的负载率，并没有将任务完成截止时间作为任务调度的约束条件，致使任务截止时间未完成率较高。

(3) 虚拟机资源利用率。虚拟机资源利用率表示虚拟机资源的整体利用程度[22]。公式为:

(26)

式中：tj.stime表示任务j的开始时间；tj.etime表示任务j的结束时间；Δij为布尔变量，若Δij=1表示任务j被分配到虚拟机i上执行，反之亦然；Tetime表示所有任务完成总时间。在任务数n=100的情况下，随机选取10个虚拟机(5,10,18,27,39,46,55,63,72,80)，对比分析各算法在虚拟机上的资源利用率，结果如图4所示。

图4 各算法虚拟机资源利用率对比

图4显示了各算法在不同虚拟机上的资源利用率，在任务数一定的情况下，本文算法的任务调度较为均衡，虚拟机资源利用较为充分，资源利用率始终保持在95%以上。文献[13]综合任务执行代价和执行能耗，以此均衡各虚拟机间的负载，也获得了不错的效果，资源利用率始终保持在90%以上。文献[10]和文献[21]以截止时间或执行综合能耗为评价目标，虚拟机均衡无法圆满地兼顾，资源利用率波动较大，各虚拟机间的负载不够均衡。

5 结 语

本文提出了一种基于分数阶达尔文粒子群的多目标云计算任务调度算法。通过改变分数阶次α和惯性

权重系数ω的调整方式和陷入局部最优的跳出方式，对分数阶达尔文粒子群算法进行改进，融合最短等待时间、资源负载均衡及任务完成所耗费用等三个目标构造任务调度满意度函数，以此搜索任务调度最优解。仿真实验表明，本文改进的调度算法与其他三种调度算法相比，本文调度算法不仅有最低的任务最大完成时间和截止时间未完成率，还较好地完成了虚拟资源的均衡负载。