优化粒子群的云计算任务调度算法

谭文安,查安民,陈森博

(1.南京航空航天大学 计算机科学与技术学院，江苏 南京 210016; 2.上海第二工业大学 计算机与信息学院，上海 201209)

优化粒子群的云计算任务调度算法

谭文安1,2,查安民1,陈森博1

(1.南京航空航天大学 计算机科学与技术学院，江苏 南京 210016; 2.上海第二工业大学 计算机与信息学院，上海 201209)

任务调度作为云计算的关键技术之一,却一直没有得到很好的解决。针对云任务调度的特点,基于基本粒子群优化(PSO)算法,文中提出了一种带极值扰动的相关性粒子群优化(EDCPSO)算法。该算法采用Copula函数去刻画随机因子间的相关结构,支持粒子合理利用自身经验信息和群体共享信息,解决了粒子群优化算法在寻优过程中没有考虑随机因子作用而造成全局优化能力不足的缺陷;采用添加极值扰动算子的策略,进一步改进粒子群优化算法,避免了粒子群优化算法在进化后期容易陷入局部寻优现象。仿真结果表明,在相同条件下,带极值扰动的相关性粒子群优化算法优于基本粒子群优化算法和Cloudsim原有调度算法,任务总的完成时间明显减少。

任务调度；云计算；粒子群优化；相关性；极值扰动

1 概 述

为了解决“大用户”、“大数据”和“大系统”带来的一系列挑战,云计算技术应运而生。云计算作为当今信息领域的重大成果,发展迅速。任务调度是云计算的关键技术之一。一个好的任务调度算法,不仅有助于打造一个稳定、健壮、节能的云计算环境,还可以提高用户使用云计算服务的满意度。智能优化算法近年来受到广泛关注,成为解决调度问题的新工具。

1995年,Kennedy等提出粒子群优化(PSO)算法[1]。其基本思想是粒子在寻优过程中,不但要考虑自身的局部认识,而且要考虑种群的全局认识,即每个粒子是在充分利用这两个认知信息的基础上决定下一次的进化方向。由于该算法具有简单、高效、智能背景深刻等优点,被广泛应用于任务调度、机器学习、数据聚类、流程规划等方面。

PSO算法的数学描述如下:

设有一种群,其粒子的个数为m,粒子的维数为n,则有：

第i个粒子的速度表示为:vi={vi1,vi2,…,vid},

1≤i≤m,1≤d≤n；

第i个粒子的位置表示为:xi={xi1,xi2,…,xid},

1≤i≤m,1≤d≤n；

第i个粒子的个体最优解表示为:pi={pi1,pi2,…,pid},1≤i≤m,1≤d≤n；

整个种群的全局最优解表示为:pg={pg1,pg2,…,pgd},1≤i≤m,1≤d≤n。

粒子速度和位置的更新方程如下:

vid(t+1)=ωvid(t)+c1r1(t)(pid(t)-xid(t))+c2r2(t)(pgd(t)-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1)

(2)

其中,ω为惯性权重;c1和c2为加速系数;r1和r2为随机因子。

但是,要将PSO算法运用于云计算任务的调度,需要对其进行改进。

PSO算法在搜索最优解过程中,需要利用个体最优解pi和全局最优解pg。由更新方程可知,二者的利用率依赖于加速系数和随机因子两大因素。为了提高PSO算法的全局寻优能力,文献[2-5]分别针对加速系数进行了改进。但是,目前很少有人对随机因子进行研究。在经典PSO算法中,r1和r2是两个相互独立的随机数。为了深入研究粒子对pi和pg的利用,需要研究一下随机因子。

PSO算法在迭代后期收敛速度变慢,这是PSO算法的一大缺点。文献[6]通过动态修改ω值,兼顾了搜索速度和精度；但对复杂的云计算任务的调度,这种通过改进惯性权重所达到的优化力度和实际效果都有待进一步提高。文献[7]在PSO算法中引入遗传算法,虽然在一定程度上达到了优化目的，但也增加了自身的复杂度。

文中通过优化PSO算法,提出了相关性PSO(CPSO)算法。该算法运用Copular函数建立随机因子之间的相关性,解决了粒子群算法在寻优过程中没有考虑随机因子作用而造成全局优化能力不足的缺陷。之后提出基于前者的带极值扰动的相关性PSO(EDCPSO)算法,解决了PSO算法在迭代后期收敛速度变慢的问题。

2 云计算任务调度问题描述

用户对调度结果的评价依据有很多,文中主要研究如何减少任务的完成时间。

2.1 粒子编码

目前存在多种编码方式,文中选择直接法。

设有t个任务,r个资源,且t>r。当t=10,r=3时,编码序列(3,2,2,1,3,2,3,1,1,2)即为一个粒子。其中,每个任务对应一个资源,例如,任务3对应资源1。

接着是对粒子进行解码,目的在于获取每个资源运行的所有任务。例如,资源1上运行的所有任务有{4,8,9}。

定义矩阵matrix[i,j],用于记录任务i在资源j上的执行时间。则资源j上完成所有任务的总时间为：

(3)

其中,i表示资源j上执行的任务个数;n表示资源j上执行的任务总数。

系统完成所有任务的总时间为：

taskTime=max(resourceTime(j)) (1≤j≤r)

(4)

2.2 种群初始化

2.3 适应度函数

文中主要研究如何优化能够减少任务的执行时间,因此将适应度函数定义为:

(5)

3 相关性PSO算法

3.1 随机因子的认知分析

根据PSO算法的心理学假设,随机因子体现了粒子在认知过程中的非理性行为,反映出粒子作为认知主体的情绪,而加速系数视为粒子对这种情绪的心理效应[8-9]。

由此可知:将随机因子r1和r2设为两个相互独立的随机数,没有考虑粒子在寻优过程中对个体最优解pi和全局最优解pg认知的联系。因此,需要建立认知信息彼此之间的内在关系,即r1和r2之间的相关性。

线性相关系数是一种常见的相关性分析[9]方法,计算公式为：

从上式可知,要求随机变量x和y的相关系数，必须知道它们的期望与方差。然而,有些变量的期望和方差是不存在的。另外,相关系数不能用于描述非线性关系。Copula理论为分析变量之间的相关性开辟了一条新的思路。该理论虽然早在1959年就诞生了,但是一直没有受到大家的关注。直到最近几年才被广泛应用于金融、保险、投资等领域的相关性分析。

3.2 基于Copula的相关性PSO算法

文中使用二元Copula函数可刻画两个变量r1和r2之间的相关性。当然,该函数可推广到多元形式。

3.2.1 二元Copula的相关知识

定义1[10]：如果二元函数C:[0,1]2→[0,1],满足下列两个条件:

(1)对于∀t∈[0,1]，C(t,0)=C(0,t)=0且C(t,1)=C(1,t)=t;

(2)对于u1,u2,v1,v2∈[0,1]且u1≤u2,v1≤v2，有C(u2,v2)-C(u1,v2)-C(u2,v1)-C(u1,v1)≥0,则称函数C为一个Copula。

Sklar定理是一个非常重要的定理,下面给出它的数学描述。

定理1[10]：设随机变量x,y的联合分布函数为H:R2→[0,1],其边缘分布函数分别为Fx,Fy,则存在一个CopulaC:[0,1]2→[0,1],对任意x=(x1,x2)∈R2,有：

H(x1,x2)=C(Fx(x1),Fy(x2))

(6)

由定理1可得下面推论。

推论1[10]：如果C:[0,1]2→[0,1]是一个Copula函数,Fx,Fy分别是随机变量x,y的分布函数,那么存在一个以Fx,Fy为边缘分布的联合分布函数H,满足对任意的(u1,u2)∈[0,1]2,有：

(7)

定理1和推论1的作用在于说明Copula函数的存在性以及它的生成方法。

Copula函数类型很多,使用较多且应用较广的一个当属GaussianCopula，定义如下:

定义2[10]：对任意(u,v)∈[0,1]2,二元GaussianCopula可定义为:

Cρ(u,v)=Φρ(Φ-1(u),Φ-1(v))

(8)

其中，Φ是标准正态分布函数;Φρ是二维正态变量的联合分布函数;Φ-1是Φ的逆函数;ρ是随机变量间的线性相关系数,且1≤ρ≤1。

3.2.2CPSO算法实现

假设随机变量x和y满足x,y～U(0,1),由推论1可知,它们的二元Copula函数实际上为x和y的联合分布函数。因此,文中采用Copula函数研究随机变量r1和r2之间的相关性是可行的,具体定义如下:

H(r1,r2)=C(r1,r2)

(9)

其中,H为随机因子r1,r2的联合分布函数;C为相应的Copula函数。

定义3：在PSO算法基础上,且由式(1)、(2)和(9)共同描述粒子运动轨迹的算法称为CPSO算法。

在CPSO算法中,两大随机因子是服从[0,1]均匀分布且相关的随机变量。因此,CPSO算法实现的难点是如何生成满足给定Copula函数的r1和r2。

CPSO算法实现如下所述：

输入:随机产生的初始种群；

输出:全局最优解pg。

(1)给出算法中所有参数的值;

(2)按照2.1与2.2的要求对粒子进行编码并初始化种群;

(3)根据已知的相关系数ρ,按照步骤(4)～(7)生成相互关联且服从[0,1]均匀分布的随机数;

(4)随机生成相互独立且服从[0,1]均匀分布的变量u1,u2;

(5)根据x=Φ-1(u1),y=Φ-1(u2)计算x,y，其中,Φ是标准正态分布函数;

(7)根据r1=Φ(x),r2=Φ(y)计算r1和r2,则二者即为满足GaussianCopula定义的两个相关随机数;

(8)使用式(5)计算粒子的适应值;

(9)更新粒子的个体最优解pi;

(10)更新种群的全局最优解pg;

(11)按照式(1)、式(2)分别更新粒子的速度和位置;

(12)判断算法是否停止;

(13)若否,则返回步骤(3);若是,取迭代停止时的pg作为最优解。

4 CPSO算法的多样性分析

4.1 粒子认知策略分析

由定义2及正态分布的对称性可以看出:

Cρ(r1,r2)=Φρ(Φ-1(r1),Φ-1(r2))=Cρ(r2,r1)

(10)

上式表明,对于∀ρ,r1,r2具有对称性,其对称轴为直线r1=r2。当ρ在[-1,1]范围内逐渐增大时,r1,r2的取值逐渐向对称轴靠拢。当ρ=1时,r1,r2的取值将会分布在对称轴之上。

CPSO算法中,r1,r2取值的对称性,反映出粒子在迭代过程中对pi和pg的利用率是相同的。随着ρ的增大,r1,r2取值的集中分布性,反映出粒子在迭代过程中对pi和pg的利用率随ρ的增大而增大。

4.2 群体多样性分析

群体多样性反映了种群中每个粒子的差异性,是描述种群进化过程中粒子多样性的一个关键指标。

定理2[11]：CPSO算法中,种群多样性的期望与相关系数ρ(0≤ρ≤1)具有正比例关系。

由定理2可知,为了在寻优过程中始终保持种群较好的多样性,CPSO算法应该给定较大的相关系数ρ。

由定理2可得下面的推论：

推论2：CPSO算法中,种群多样性的期望正相关于粒子对个体最优解和全局最优解的利用率。

5 带极值扰动的CPSO算法

在CPSO算法中,个体最优解pi和全局最优解pg决定了粒子位置的收敛极值。如果每个粒子在逼近收敛极值的过程中不能发现比pg更优的位置,则之后的所有迭代都将无效,因为进化过程已经结束。

5.1 极值扰动

对式(1)和(2)添加扰动算子后变为:

vid(t+1)=ωvid(t)+c1r1(t)(αti>Tipid(t)-xid(t)) +c2r2(t)(βtg>Tgpgd(t)- xid(t))

(11)

xid(t+1)=xid(t)+vid(t+1)

(12)

5.2 EDCPSO算法实现

定义4：在CPSO算法基础上,由式(11)、(12)和式(9)共同描述粒子运动轨迹的算法称为带极值扰动的CPSO(EDCPSO)算法。

修改CPSO算法的第11步:按照式(12)、(13)对粒子的速度和位置进行更新,其他步骤不变,则可得到EDCPSO算法。

6 仿真实验与分析

6.1 仿真实验环境与算法参数

利用Cloudsim构建云计算环境,Eclipse作为开发平台,将文中提出的EDCPSO算法与Cloudsim原有调度算法FIFO、基本PSO算法进行对比分析。其中,算法参数见表1。

表1 EDCPSO算法参数

6.2 实验结果和性能分析

每个实验分别设置5组不同的用户任务、50个资源节点,实验过程中需要记录每次实验结束后任务的总完成时间。所有实验各运行20次,取20次的平均结果作为最终结果。最后得出各个算法的任务完成时间，如图1～3所示。由图可见,EDCPSO算法相比其他两种调度算法更加高效。

7 结束语

文中在分析云计算环境及其PSO算法的基础上,提出了带极值扰动的相关性PSO(EDCPSO)算法。仿真结果表明:该算法相比于Cloudsim原有调度算法和基本PSO调度算法,具有更高的效率,能够减少任务总的完成时间。

文中工作处于理论分析与仿真测试阶段,还需在实际的云计算平台上应用验证；同时EDCPSO算法只是优化了任务的完成时间,而在真实环境中还需考虑其他因素,如平均完成时间、经济效益、负载均衡等。因此，有必要进一步研究和改进该算法,以便拓宽其应用场景。

图1 t=50时的任务总完成时间

图2 t=100时的任务总完成时间

图3 t=500时的任务总完成时间

[1]KennedyJ,EberhartRC,ShiY.Swarmintelligence[M].Singapore:ElsevierSciencePress,2001:202-210.

[2]ParsopoulosKE,VrahatisMN.Recentapproachestoglobaloptimizationproblemsthroughparticleswarmoptimization[J].NaturalComputing,2002,1(2-3):235-306.

[3]RatnaweeraA,HalgamugeSK,WatsonHC.Self-organizinghierarchicalparticleswarmoptimizerwithtime-varyingaccelerationcoefficients[J].IEEETransactionsonEvolutionaryComputation,2010,8(3):240-255.

[4]ArumugamMS,RaoMVC,TanAWC.Anovelandeffectiveparticleswarmoptimizationlikealgorithmwithextrapolationtechnique[J].AppliedSoftComputing,2009,9(1):308-320.

[5] 介 婧,曾建潮,韩崇昭.基于群体多样性反馈控制的自组织微粒群算法[J].计算机研究与发展,2008,45(3):464-471.

[6]ShiY,EberhartRC.Fuzzyadaptiveparticleswarmoptimization[C]//Procofthecongressonevolutionarycomputation.Piscataway:IEEE,2001:101-106.

[7]AngelinePJ.Evolutionaryoptimizationversusparticleswarmoptimization:philosophyandperformancedifferences[C]//Procofthe7thannualconferenceonevolutionaryprogramming.Berlin:Springer-Verlag,1998:601-610.

[8] 王 沛.社会认知心理学[M].北京:中国社会科学出版社,2006:72-86.

[9]EmbrechtsP,McneilAJ,StraumannD.Correlationanddependencyinriskmanagement:propertiesandpitfalls[C]//Procoftheriskmanagement:valueatriskandbeyond.Cambridge:CambridgeUniversityPress,2001:176-223.

[10]NelsenRB.Anintroductiontocopulas[M].2nded.NewYork:Springer-Verlag,2006:10-28.

[11] 申元霞,王国胤,曾传华.相关性粒子群优化模型[J].软件学报,2011,22(4):695-708.

[12]ShiYH,EberhartRC.Populationdiversityofparticleswarms[C]//ProcoftheIEEEworldcongressoncomputationalintelligence.HongKong:IEEEPress,2008:1063-1067.

[13]ClercM,KennedyJ.Theparticleswarm:explosionstabilityandconvergenceinamulti-dimensionalcomplexspace[J].IEEETransactionsonEvolutionComputer,2002,6(1):58-73.

[14] 吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3):416-420.

[15] 胡 旺,李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报,2007,18(4):861-868.

Task Scheduling Algorithm of Cloud Computing Based on Particle Swarm Optimization

TAN Wen-an1,2，ZHA An-min1，CHEN Sen-bo1

(1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016，China; 2.School of Computer and Information,Shanghai Second Polytechnic University,Shanghai 201209,China)

How to schedule cloud tasks efficiently is one of the important issues to be resolved in cloud computing.The Extremum Disturbed Correlative Particle Swarm Optimization (EDCPSO) algorithm based on basic Particle Swarm Optimization (PSO) is proposed for the characteristics of cloud environment.It uses the Copular function to measure correlation structures among random factors,support of particles properly using the individual experience and social sharing information,resolving the demerit that the PSO algorithm lacks of the global optimization ability because of not considering the function of the random factors in the optimization process.Moreover,it uses the strategy of adding extremum disturbed arithmetic operators to improve further the PSO,which resolves the demerit of falling into local extremum in the late evolution for PSO.Simulation shows that EDCPSO is better than PSO and Cloudsim original scheduling algorithm in the same experiment conditions.That is to say,the algorithm can reduce the total completion time of tasks.

task scheduling;cloud computing;PSO;correlation;disturbed extremum

2015-10-15

2016-01-21

时间：2016-06-22

国家自然科学基金资助项目(6127036)；上海第二工业大学重点学科(XXKZD1301)

谭文安(1965-)，男，博士，教授，CCF高级会员，通讯作者，研究方向为软件构架技术、协同计算、服务计算与知识管理、信息化工程及其支持环境研究等；查安民(1987-)，男，硕士研究生，研究方向为云计算、工作流调度与服务计算领域。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0842.004.html

TP301.6

A

1673-629X(2016)07-0006-05

10.3969/j.issn.1673-629X.2016.07.002