云计算环境下基于改进粒子群算法的任务调度

张照胜，李蜀瑜

（陕西师范大学 计算机科学学院，陕西 西安 710119）

云计算环境下基于改进粒子群算法的任务调度

张照胜，李蜀瑜

（陕西师范大学 计算机科学学院，陕西 西安 710119）

为了优化云计算环境下任务调度，考虑调度过程中任务的最短完成时间、系统的负载均衡和经济成本3个目标约束，然而3个目标约束之间存在冲突，因此提出了一种使用改进粒子群优化算法来解决云计算任务调度中多目标优化问题，达到同时兼顾3个目标约束的目的。选择惯性权重的模糊自适应策略对粒子群算法进行改进，从而能很好的平衡粒子的全局搜索能力和局部搜索能力，尽量避免过早收敛和陷入局部极值，并且引入移动子和负载因子的概念，用于实现算法对云计算环境下的任务调度。仿真结果表明，该算法对多目标优化问题，具有较好的寻优能力。

云计算；任务调度；粒子群算法；最短完成时间；负载均衡；经济成本

云计算[1]是分布式计算的一种，是网格计算[2]和并行计算的发展，是这些计算科学概念的商业实现。其最基本的概念是，庞大的计算处理任务透过网络被自动拆分成很多较小的子任务，再交由多部服务器所组成的庞大系统经搜寻、计算分析之后将处理结果回传给用户。

由于云计算所面对的计算任务数量十分庞大，任务调度和资源分配问题是决定云计算效率的重点与难点。文献[3]中对云计算的优点和面临的问题进行了综述；文献[4]中基于文化算法和粒子群算法的混合，进行云计算资源的调度，提高了系统资源的利用率，保持了系统的负载均衡；文献[5]中引入动态多群体协作和变异粒子逆向飞行的思想与PSO结合，进行云计算服务集群资源调度，优化系统的负载均衡；文献[6]中基于对粒子群算法的惯性权重进行改进和引入个体最优位置的平均值的概念，依据云计算中的任务分配建模过程，优化云计算在调度中任务派发速度和资源利用率；文献[8]中通过对云计算环境下的数据部署进行问题描述和建模，构造粒子群算法适应度函数，优化了传输和处理所需的时间和费用；文献[9]中采用粒子群算法，对云计算任务调度中的最小任务完成时间和最快任务响应时间这两个目标约束进行优化；文献基于鱼群算法中的聚群行为有较强的跳出局部极值的能力，能表现出全局收敛性好等特点，在粒子群算法中建立粒子中心的概念，利用聚群特性进行优化，进而改进粒子群算法的全局收敛能力；文献[10]引入粒子的搜索中心概念，分析搜索中心在全局最优解和局部最优解之间均匀分布，优化粒子群算法的收敛速度和稳定性；文献[11]构造了一种对惯性权重进行调整的非线性函数，在速度更新公式中增加了动态的随机数，并引入在一定条件下对粒子位置重新扩散机制，提高群体后期的多样性，很好的改善了算法的寻优性能；文献[12]引入人工免疫系统中的克隆变异选择机制和精英粒子学习机制（柯西分布的精英学习策略），增加粒子种群的多样性和增强粒子逃离局部极值，提高多峰值函数优化时全局寻优能力；文献[13]中基于改进的粒子群算法，对云计算环境下任务调度中最短完成时间、经济成本和能耗3个目标约束进行优化，但没有考虑负载均衡这一重要目标约束。鉴于以上文献对云计算的任务调度目标约束的优化仅限于单个或两个，或未考虑负载均衡这一重要目标约束，以及对粒子群算法改进策略的分析研究。

因此，本文中我们考虑3个目标约束，即任务的最短完成时间、负载均衡和传输处理的经济成本，并采用改进的粒子群算法优化多目标约束条件下的任务调度。

1 问题模型

在这个部分，用形式化的方式描述了系统模型。最终期望达到的目标是，既满足用户对服务质量的要求，又满足云服务提供商的要求。因此，首先描述了云计算任务调度模型，其次描述了云计算任务调度的最小完成时间、负载均衡和经济成本3个目标约束。通过对云计算任务调度模型和3个目标约束的描述，得出要解决的是一个多目标优化问题。

1.1 云计算任务调度

目前，云计算环境下，Google提出的Map/Reduce编程模式是主流，该模式分为Map（映射）和Reduce（规约）两个阶段，把一个大任务拆分成多个较小的子任务，然后再将子任务进行分配，本文只考虑子任务相互独立的情况。通过将子任务合理的分配到资源结点上，从而使得任务的完成时间达到最小，系统的负载达到均衡，经济成本最少。

在云计算环境下，将N个相互独立的子任务分配给M个资源结点。其中，任务集表示为 T={t1，t2，…，tN}，tj（j=1，2…，N）表示第j个子任务。资源结点集表示为VM={{vm11，vm12，…，vm1k}，{vm21，vm22，…，vm2k}，…，{vmm1，vmm2，…，vmmk}}vmij（i= 1，2，…，m；j=1，2，…，k）表示第i个虚拟机上的第j个资源结点，每个子任务只能在一个资源结点上执行。任务集T与虚拟机上资源结点集VM的分配关系可用矩阵X表示为：

1.2 云计算任务调度的目标约束

1.2.1 最短完成时间

最短完成时间是从提交所有子任务开始，直到最后一个子任务执行完成所需要的时间。N个子任务t1，t2，…，tN，可能分布在空间不同的位置，N个子任务是相互独立的，m个虚拟机VM1、VM2、...、VMm，分布在空间不同的位置。N个子任务发出请求，任务调度器首先会根据每个任务当前的位置，将任务分配到距离该任务最近的一个虚拟机，该距离表示发出该任务请求的用户与响应该任务请求的虚拟机之间的地理位置距离。一个虚拟机表示一个Logical cluster，一个Logical cluster由若干个物理机组成，一个物理机表示一个资源结点[14]，一个子任务对应一个资源结点。假设一个虚拟机包含k个资源结点，虚拟机个数m，系统资源结点总数M=m*k。

每个子任务的数据量映射为百万条指令，order1表示任务ti需要处理的数据量。receivek：k={1，2，...，m}表示虚拟机k每小时可接收多少百万条指令，sendk：k={1，2，...，m}表示虚拟机k每小时可发送多少百万条指令，processk：k= {1，2，...，m}表示虚拟机 k每小时可处理多少百万条指令。

初始分配传输时间：初始时刻子任务j分配到虚拟机p上的传输时间

转移时间：如果子任务j所分配的虚拟机p过载，那么需要将该任务从虚拟机p转移到未过载的虚拟机q，转移时间为

执行时间：子任务j在虚拟机q上的执行时间

子任务j在虚拟机q上期望完成时间为ECTqj=TTpj+MTpqj+ ETqj，那么max{ECTqj}为总任务的完成时间，Cmax=max{ECTqj}，优化目标是总任务的完成时间最短。

1.2.2 负载均衡

当分配到某个虚拟机上的任务过多，而有些虚拟机上分配的任务可能又太少，这就会造成整个系统的资源负载不均衡、系统的性能下降和资源的浪费。因此，为了使得整个系统负载均衡，本文给出的策略是，将已分配任务但未过载的虚拟机和未分配任务的虚拟机（任务数为0）按分配的任务量从小到大排列，将过载虚拟机上多余的任务移动到未过载或未分配的虚拟机上。为了表示每个虚拟机的负载情况，定义了负载因子的概念。

虚拟机vmi上分配的子任务数为α，承载子任务的上限为β，定义负载因子θi，其中θi=α-β，如果θi>0，那么虚拟机i就处于过载状态，如果θi<0，那么虚拟机i就处于未过载状态。

Then 1.负载不均衡；2.将过载虚拟机（θi>0）上多余的子任务向未过载虚拟机（θi<0）上转移；3.整个虚拟机系统的负载因子

优化的目标是整个虚拟机系统的负载因子θ的值最小。

1.2.3 经济成本

在负载均衡模型中，将过载的虚拟机上的多余的任务重新分配到未过载的虚拟机上，在重新分配的过程中，如果采用优先选择未分配或已经分配任务量最少的虚拟机策略，可能出现的情况是，待分配的任务与该虚拟机的距离较远，这样就会增加传输时间和传输成本，从而增加任务的总完成时间，同时也增加了经济成本。基于经济成本因素的考虑，再重新分配时，优先选择离该任务最近的虚拟机。

定义：总成本=处理成本+移动成本

子任务j在虚拟机q上处理的费用pcqj，处理时间为ETqj，单位时间的处理费用为pl，其中l∈{1，2，…，m}

子任务的处理成本：

所有任务的处理成本：

子任务的移动成本：

所有任务的移动成本：

总成本AC=PC+TC，优化的目标是完成全部任务的总成本AC最少。

2 模糊自适应粒子群算法

粒子群算法是1995年Eberhart博士和Kennedy博士受鸟类族群觅食讯息传递的启发，提出的一种基于群体协作的随机搜索算法，该算法优点是实现容易、收敛速度快、求解精度高。但是，标准粒子群算法在搜索过程中，容易过早收敛和陷入局部极值。基于ω起着权衡局部最优能力和全局最优能力的作用，本文使用模糊技术，借鉴文献[15]提出的惯性权重模糊自适应策略，使用不同的惯性权重更新同一代种群。

2.1 移动子和操作符

本文采用顺序编码，即虚拟机的序列编号作为粒子的编码规划，子任务的数量决定编码长度，一个粒子对应虚拟机上子任务的一个分配序列。假设子任务数N为18，虚拟机个数m为4时，粒子（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4）可为一个可行的调度策略。为了更好地将该算法应用于云计算任务调度，本文引入了移动子的概念，并对粒子群算法的速度和位置更新公式中的操作符赋予了新的含义。

定义1（移动子），（j，p，q），j∈{1，2，…，N}，p，q∈{1，2，…，m}，if（p=q），doNothing，表示将p号虚拟机上的子任务j移动到q号虚拟机上。

定义2（减法操作（X1-X2））

设pi，pj为粒子i和j的位置，则pi-pj为粒子i和j的位置减法操作，结果为一组移动序列。A=（3，1，2，4，1，3，2，1，1，2，4，1，3，4，2，3，2，4），B=（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4），由于A（4）=4，B（4）=1，第一个移动子为（4，1，4），所以最后得 到 的移动 序 列 为 {（4，1，4），（6，1，3），（14，1，4，），（16，1，3），（17，1，2）}

定义3（加法操作（X+V））

将一组移动序列V作用于某个粒子位置X得到新位置。

例如：（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4）+{（4，1，4），（6，1，3），(14，1，4)，（16，1，3），（17，1，2）}=（3，1，2，4，1，3，2，1，1，2，4，1，3，4，2，3，2，4）

定义4（乘法操作（r×V））

r为实数，取值范围为[0，1]，k表示速度V的移动子的个数，r×V表示选取速度V的前r×k（取整）个移动子

例如：0.5×{(4，1，4)，（6，1，3），（14，1，4），（16，1，3）}={（4，1，4），（6，1，3）}

定义5（合并操作（v1⊕v2））

速度v1与v2合并为一个新的速度v。

例 如 ：{（4，1，4），（6，1，3）}⊕{（14，1，4），（16，1，3）}= {（4，1，4），（6，1，3），（14，1，4），（16，1，3）}

根据上述定义，本文使用如下公式更新粒子

速度更新公式：

位置更新公式：

2.2 自适应调整惯性权值

为了很好的平衡粒子的全局搜索能力和局部搜索能力，使其不至于过早收敛和陷入局部极值，借鉴文献[15]惯性权重的模糊自适应策略，应用到粒子群优化算法中。

隶属函数：

其中，di表示第i个粒子的佳粒子距，N为种群规模，S1、S2为控制参数，α、β为调整参数，满足条件S10，β>0。

惯性权重自适应调整函数：

其中，cIter为当前迭代次数，MaxIter为最大迭代数，ws、we分别为w的初始值和结束值。

2.3 适应度函数

本文考虑了任务调度过程中的3个目标，即最短完成时间、负载均衡和经济成本。用改进的pso来解决多目标优化问题，适应度函数Fitness（i）定义为：

式中，α+β+γ=1，α=0.5，β=0.3，γ=0.2。其中α、β、γ分别表示各目标的权重。

2.4 模糊自适应PSO算法

模糊自适应PSO的云计算任务调度算法的基本执行步骤如下：

图1 模糊自适应PSO算法流程

3 实验与分析

3.1 仿真环境及算法设置

建立仿真环境，测试硬件为：Intel（R）Core（TM）i5-2400 3.10GHz，4.00G RAM，采用亚马逊EC2的处理定价模式和亚马逊CloudFront的数据传输定价模式，实验采用CloudSim云计算仿真工具对标准PSO算法和M-PSO算法进行仿真实验，并对实验结果进行分析和对比。表1为实验初始时的参数取值。

表1 本文算法主要参数设置

其中，达到最大迭代次数MaxIter或全局最优值连续50次没有变化为算法的终止条件。

3.2 实验结果与性能分析

我们依据亚马逊的收费方式对10个虚拟机进行模拟，用PSO方法和M—PSO方法分别对云计算任务进行调度，仿真结果如图2，图3所示。图2表示30个粒子，分别使用PSO方法和M—PSO方法，经过1000次的迭代后，3个目标约束在三维空间中粒子的分布情况，从图中可以看出，M—PSO方法在系统负载均衡、最短完成时间和费用方面与PSO方法比较，都表现出了较优的效果，且粒子分布比较集中，更能找到全局最优解。图3表示PSO方法和M—PSO方法随着迭代次数的增加适应度值的收敛情况，从图中可以看到，PSO收敛过早，并且陷入了局部极值，而M—PSO收敛的效果比PSO更好。

图2 粒子目标约束空间的分布

图3 适应度值收敛过程

4 结论

文中研究了云计算环境下任务调度模型，定义了最短完成时间、负载均衡和经济成本3个目标约束的模型，采用标准粒子群算法和改进的粒子群算法对云计算环境下多目标约束的任务调度问题进行优化，仿真结果显示，3个有互相冲突的目标约束最终达到了一种均衡择中状态，并且改进的粒子群算法表现的性能优于标准粒子群算法。本文只考虑了云计算环境下任务调度的3个目标约束和切割后的子任务间相互独立的情况，而在实际应用中情况比较复杂，还有其他因素需要考虑，比如QoS约束，节能约束等，并且子任务之间并非相互独立，而是存在密切联系的，因此下一步研究的目标是在考虑更多的目标约束条件和子任务之间并不是相互独立的情况下，如何继续不断提高云计算任务调度的综合性能。

[1]李乔，郑啸．云计算研究现状综述[J]．计算机科学，2011，38（4）：32-37．

[2]许元飞．网格计算中任务调度算法的仿真研究[J]．计算机仿真，2011，28(8)：75-78．

[3]Armbrust M，Fox A，Griffith R，et al.Above the Clouds:A Berkeley view of cloud computing[J].Eecs Department University of California Berkeley，2009，53(4):50-58.

[4]孟令玺，李洪亮．基于CA-PSO算法的云计算资源调度策略[J]．计算机仿真，2013，30(10)：406-410．

[5]刘万军，张孟华，郭文越．基于MPSO算法的云计算资源调度策略[J]．计算机工程，2011，37(11)：43-45．

[6]李媛媛，曲雯毓，栗志扬，等．一种快速收敛粒子群优化算法在云计算中应用[J]．华中科技大学学报：自然科学版，2012:34-37．

[7]郭力争，耿永军，姜长源，等．云计算环境下基于粒子群算法的多目标优化[J]．计算机工程与设计，2013，34(7)：2358-2362．

[8]Anju Baby.Load balancing in cloud computing environment using pso algorithm[J].International Journal For Research In Applied Science and Engineering Technology，2014，2（4）：156-163.

[9]李荣钧，常先英．一种新的混合粒子群优化算法[J]．计算机应用研究，2009，26（5）：1700-1702．

[10]吴晓军，杨战中，赵明．均匀搜索粒子群算法[J]．电子学报，2011，39（6）：1261-1266．

[11]任小波，杨忠秀．一种动态扩散粒子群算法[J]．计算机应用，2010，30（1）：159-161．

[12]林国汉，章兢，刘朝华．免疫综合学习粒子群优化算法[J]．计算机应用研究，2014，31（11）：3229-3233．

[13]Yassa S，Chelouah R，et al.Multi-objective approach for energy-aware workflow scheduling in cloud computing environments.[J].Scientific world journal，2013，pp:1-13.

[14]E.Pacini，C.Mateos，et al.Dynamic scheduling based on particle swarm optimization for cloud-based scientific experiments[J].Clei Electronic Journal，2014，14（1）：1-14.

[15]郭文忠，陈国龙．求解TSP问题的模糊自适应粒子群算法[J]．计算机科学，2006，33（6）：161-163．

Task scheduling based on improved particle swarm optimization in cloud computing environment

ZHANG Zhao-sheng，LI Shu-yu
（School of Computer Science，Shaanxi Normal University，Xi’an 710119，China）

For optimizing the task scheduling of cloud computing environment，it processes to consider the shortest completion time，load balancing，system constraints and economic costs of the three objectives，however，there is still have a conflict between these three objectives of constraints，thus we propose a method of using improved Particle swarm optimization（PSO）algorithms to solve the purpose of cloud computing task scheduling for multi-objective optimization problem to consider the three objectives constraints.Improving the global search ability and local search capability by using Fuzzy Adaptive Inertia Weight PSO strategy so that the particles can be well balanced to avoid premature convergence and local extremum，introducing the concept of the moving element and the load factor for the realization of task scheduling algorithm for cloud computing environments.Simulation results show that the algorithm for multi-objective optimization problem has better search capability.

cloud computing；task scheduling；PSO；the shortest completion time；load balancing；economic costs

TN602

A

1674－6236（2016）15-0005-04

2016-01-05 稿件编号：201601020

国家自然科学基金（41271387）

张照胜（1989—），男，湖北黄冈人，硕士。研究方向：云计算。