面向云环境中任务负载的粒子群优化调度策略

胡志刚 常健 周舟

摘   要：随着云环境中任务规模的不断扩大，云计算中心高能耗问题变得日益突出.如何解决云环境中任务分配问题从而有效降低能耗，本文提出了一种改进的粒子群优化算法（Modified Particle Swarm Optimization， M-PSO）.首先构建出一个云计算能耗模型，同时考虑处理器的执行能耗和任务传输能耗.基于该模型，对任务分配问题进行定义描述，并采用粒子群优化算法对问题进行求解.此外，构建动态调整的惯性权重系数函数以克服标准PSO算法的局部最优和收敛速度慢的问题，有效提高系统性能.最后通过仿真实验对该算法模型的性能进行了评估，结果表明M-PSO算法与其他算法相比能有效地降低系统总能耗.

关键词：云计算;任务调度;惯性权重;粒子群优化

中图分类号：TP338.8                             文献标志码：A

PSO Scheduling Strategy for Task Load in Cloud Computing

HU Zhigang1， CHANG Jian1， ZHOU Zhou2？覮

（1. School of Computer Science and Engineering，Central South University，Changsha 410075，China;

2. Department of Mathematics and Computer Science， Changsha University，Changsha 410022，China）

Abstract： As the scale of tasks in the cloud environment continues to expand， the problem of high energy consumption in cloud computing centers has become increasingly prominent. In order to solve the problem of task assignment in a cloud environment and to effectively reduce energy consumption， a Modified Particle Swarm Optimization algorithm （M-PSO） was proposed. First， a cloud computing energy consumption model， which takes into account the processor's execution energy consumption and task transmission energy consumption， was introduced. Based on the model， the task assignment problem was defined and described， and the particle swarm optimization algorithm was used to solve this problem. In addition， a dynamically adjusted inertia weight coefficient function was constructed to overcome the local optimization and slow convergence problem of the standard PSO algorithm， and the strategy can effectively improve the system performance. Finally， the performance of the introduced algorithm model was evaluated by simulation experiments. The results show that the M-PSO algorithm can effectively reduce the total energy consumption of the system compared with other algorithms.

Key words：cloud computing;task scheduling;inertia weight;Particle Swarm Optimization（PSO）

云計算提供了方便和按需的网络访问共享和可扩展的虚拟资源池，如服务器、存储和应用服务[1].但是在配电和散热方面，云计算数据中心会产生巨大的能源成本[2].对于像Google这样的大公司来说，能源成本降低三分之一可以节约成本超过一百万美元.与此同时，政府机构继续推行节能计算[3].因此，降低能源消耗已经成为当今数据中心运营商关注的主要问题.

针对云计算数据中心的能耗问题，文献[4-5]分别提出了一种精确度高的能耗模型来预测云计算数据中心单台服务器的能耗状况，从而实现对整个数据中心的能耗估测.如何在能耗与性能两者间取得平衡，一种典型的思想就是不定期检测系统中的空闲设备，然后将其关闭实现节约能耗的目标[6]. 但这种策略的主要问题在于：硬件设备从关闭状态重新启动达到运行状态，这一过程期间会导致系统性能的下降.而云计算的主要支持技术是虚拟化，以经济高效的方式将单个物理机器分割为多个虚拟机（Virtual Machine，VM），这种技术可以有效地将物理设备逻辑上分成若干子模块，从而实现对物理设备的高利用率.文献[7]基于蚁群算法，提出了一种有效的虚拟机放置策略.在同质和异构服务器的云环境中，将候选VM分组在一起，从全局优化的角度有效地减少了用于分配虚拟机的服务器数量，该策略适用于具有不同大小VM的各种分配问题.

考虑到云服务中计算成本、任务执行截止期限、服务质量（Quality of Service，QoS）、高吞吐量等约束条件，有效的任务调度策略成为云计算中一个重要的研究领域.为了解决云环境中的任务调度和资源分配问题，Yang等人[8]提出了一种基于PSO的算法，将每个子任务分配给适当的资源，并对资源上的子任务进行排序以实现此方案的目标.Verma 等[9]提出基于双准则优先的粒子群算法（Bi-Criteria Priority based Particle Swarm Optimization， BPSO），在可用的云资源上调度工作流任务，并在约束下的执行时间最大限度地降低执行成本. Pandey等人[10]提出了另一种基于PSO的启发式方案，该方案基于PSO给出的解决方案优化了任务-资源映射的成本，兼顾了计算成本和数据传输成本.针对数据密集型工作流的高能耗问题，肖鹏等人[11]提出通过引入“虚拟数据访问节点”的方法来量化评估工作流任务的数据访问能耗开销，并在此基础上设计了一种“最小能耗路径”的启发式策略.这些方法从不同方面对云计算中任务分配问题提出相应的优化方案，从而达到降低能耗开销、提高系统能效.

目前用于解决云计算中任务分配问题的方法各种各样，其中任务分配旨在将适当的任务或作业映射到最合适的可用资源上，可将其抽象归纳为与云计算硬件设施效率有关的组合优化问题之一[12].多处理器调度是一个非常难的问题，为了解决这些问题，粒子群算法被广泛采用，各种应用研究的成果不断涌现.Rodriguez等[13]提出了一种基于元启发式优化技术的粒子群优化算法（Particle Swarm Optimization，PSO），该算法的目的是在满足期限约束条件的同时最小化总体工作流执行成本.文献[12]提出了一个云环境的多目标任务调度方案，尽量减少任务执行时间、任务传输时间、任务执行成本和提高QoS. 文献[14]提出了一个改进的云环境任务调度算法，结合了模拟退火（Simulated Annealing，SA）算法和粒子群算法（PSO）来提高资源利用率. Patel等人[15]提出了一种基于群体智能算法的混合蚁群优化（Ant Colony Optimization，ACO）/ PSO）技术来优化多播树.有一些研究者对文献[16]中提出的基于粒子群优化（PSO）的任务和工作流调度方案进行了深入的分析，提出动态自适应粒子群优化算法（Dynamic Adaptive Particle Swarm Optimization，DAPSO）来增强基本PSO算法的性能，通过最小化特定任务集的完成时间来优化任务运行时间，同时最大化资源利用率[17].这些文献考虑到PSO算法没有交叉和变异运算，结构简单，相比其他算法简单易实现的特点.但缺乏对算法中惯性权重的动态调节，这会使系统易陷入局部最优，导致收敛精度低和不易收敛问题.

PSO算法的搜索过程是一个通过迭代使搜索空间不断缩小的过程，其中全局搜索能力和局部搜索能力的平衡对算法的效率起着至关重要的作用[18].本文针对PSO收敛速度慢，易陷入局部最优的问题，提出一种改进的优化调度策略.考虑到粒子群算法中的惯性权重是影响搜索结果和收敛速度的关键因素[19]，本文提出了一种适用于云计算资源调度的M-PSO算法，来提高收敛速度以及搜索的良好适应性，从而减少系统开销.

1   系统模型

1.1  能耗模型

任务分配问题就是将应用程序的一系列任务合理分配到分布式计算系统中相应的可用资源上，以达到计算资源的负载均衡[20]，减少任务执行的等待时间并提高系统输出效率.用户对调度结果的评价依据有很多，文中主要研究如何减少任务的完成

时间.

本文在任务分配问题中，考虑任务的执行能耗和任务间交互能耗.结合能耗的计算公式E = P × T，任务从进入云计算系统的时刻t0到执行完毕时刻  t1所产生的能耗可表示为：

定义.云计算系统中任务间的交互关系可定义为任务交互图（Task Interaction Graph， TIG） ，其中  代表一个程序的任务，并且T = {1，2，…，m}代表這些任务之间的交互.边权重eij = （Ti，Tj）表示在节点   i和j之间的任务信息交互大小;节点权重wi对应于任务本身大小. 图1表示了一个任务交互图（TIG）的实例.

同样，计算系统可由处理器交互图（Processor Interaction Graph， PIG）表示为G（P，E）， 其中P = {1，2，…，n}表示系统中的处理器集合和边权重djk在任何两个节点之间j和k表示相应处理器之间的路径长度. 分配问题可以正式表示如下：

M：T→P其中M是任务集合T映射到处理器集合的函数.该问题可以描述为：找到一个任务处理器映射实例M;使得在估计使用每个计算资源所引起的总成本P时，所有计算资源中的最大成本被最小化. Eex（M）k是分配给计算资源k的所有任务的总开销. Etr（M）i是任务i与其他未分配在相同处理器上的任务之间的总交互开销.在一个给定的任务分配映射中，系统总开销E（M）是执行开销和交互开销的总和：

在估计所有资源的总开销时，任务分配问题的目标是找到一个任务分配映射M，对于给定的PIG和TIG上具有最小的开销：

Minimize（E（M）    ？坌M）    （3）

1.2   任务分配模型

在云环境中，大量的云用户在不了解系统基础结构的情况下向云服务提供商提交独立任务并从云访问服务.从任务的长度和任务的资源需求来看，任务可视为是异构的[21].

3.2.1   加速因子對适应度的影响

图4（a）表示在任务量300、迭代次数100时，加速因子变量值从1逐渐递增到2的过程中对算法适应度值的影响.由图可以看出，适应度值变化的整体趋势为先增加再递减，但变化过程中并非严格递增和递减，其中存在轻微波动.当加速因子值为1.5时，对应的适应度值达到最大，此时为算法的最优状态.图4（b）表示将任务量增加至800，算法迭代次数增加到200的情况下，加速因子对适应度值的影响.从图可以看出，适应度值的变化趋势和图4（a）相似，同样呈现出先增后减的趋势，并当加速因子取值在1.4至1.6之间达到峰值.由此可以分析出，在不同任务量和迭代次数下，选取加速因子值为1.5时，算法可以有较好的性能表现，故在后面的对比实验中，将其取值为1.5作为系统参数值.

3.2.2   迭代次数对保证率的影响

图5（a）和5（b）分别表示在加速因子变量取值为1.5、任务量为300和1 000的条件下，迭代次数对完成任务分配的保证率的影响.图5（a）中，任务量较少时，保证率随迭代次数的增加变化明显，且曲线的变化较为平滑.初期当迭代次数取值在20至150之间时，保证率上升速度快，说明此时算法对迭代次数要求比较高，适当增加迭代次数对系统有较高的保证率.但当迭代次数逐渐增加至200时，保证率曲线逐渐出现收敛现象，达到250时变化不明显. 图

5（b）中，相应增加任务量，此时IPSO和PSO-ACO算法的保证率曲线变化十分相似，迭代次数在50至200区间时对应的保证率几乎一致，后期到达收敛时，IPSO算法的保证率略微高于PSO-ACO算法.从图5（a）和图5（b）中可以看出，M-PSO算法的保证率始终高于IPSO和PSO-ACO两种算法，并且三种算法在200次迭代以后保证率的变化都逐渐开始收敛，此时迭代次数对算法的影响较小.但随着任务量的增加，各算法本身的保证率也会随着略微降低.

3.2.3   任务负载对系统能耗的影响

图6表示在加速因子取值为1.5、 迭代次数取值为200的条件下，不同的任务数所产生的系统开销.由图可以看出，在任务量为200时，算法ACO的系统开销处于最低，而ACO-PSO和M-PSO算法其次，IPSO算法最高.其原因主要在于，与其他启发式算法相比，蚁群算法具有较强的鲁棒性和较好的求解性能. 同时，在工作任务量较小的情况下，算法的迭代次数对基于PSO的各种改进算法影响不明显.当执行任务量为400时，算法M-PSO和PSO-ACO的开销较低，IPSO算法和ACO算法次之，其原因主要为：当主机负载增加时，基于PSO的算法逐渐体现出其在调度方面的优势.PSO-ACO将ACO的局部搜索和变异操作同时混合到PSO算法中，通过适当调整各自的优势，从而使得PSO-ACO提高了全局优化的能力. 当负载的任务量进一步增大时，M-PSO算法的优化比率很明显.与IPSO，PSO-ACO 和ACO相比，在600个任务和200次迭代的情况下，所提出的算法M-PSO分别降低了总开销的8.5%，7.1%和9.7%，而PSO-ACO与IPSO和ACO相比只降低了2.9%和5.7%的开销.

后期任务量继续增加时，M-PSO算法依然保持着较低开销的优势.由于ACO算法是一种典型的概率算法，算法中设置的参数通常由实验方法经验确定，导致性能的优化与人的经验密切相关，所以很难做到在不同任务量的情况下一直处于最佳的执行效果. 而混合算法PSO-ACO的收敛速度较慢，随着任务量的不断增大算法容易陷入局部最优，导致算法需要较长的搜索时间，其复杂度可以反映出这一点.IPSO算法最主要的问题在于容易过早收敛，这导致其丧失了搜索空间中的种群多样性，进行全局搜索的优化能力较差.

综合以上实验分析，随着负载任务量的不断增大，各算法的性能表现也有所变化.粒子群算法在处理大任务量时具有明显优势，并且加速因子、惯性系数和迭代次数对粒子群算法的性能表现具有较大影响.这意味着基于PSO算法的M-PSO算法通过对惯性权重系数的改进，克服算法收敛和局部最优问题能够实现以相对较低的系统开销执行较大的任务负载量.因此，在云计算环境中分配较大规模任务负载应用时，采用M-PSO算法具有更大的优势.

4   结   论

本文提出了一种基于任务调度的改进粒子群优化算法（M-PSO），实验结果表明：1）在总开销方面， M-PSO算法在处理任务负载量较大时的性能优于负载量较小的;2）随着任务量和迭代次数的增加，所提出的M-PSO任务调度算法在降低总开销方面比其他3种算法（IPSO，PSO-ACO和ACO算法）更有效. 该算法有望应用于实际的云平台，旨在提高能效，降低任务调度的总开销.

参考文献

[1]    ZENG L， VEERAVALLI B， ZOMAYA A Y. An integrated task computation and data management scheduling strategy for workflow applications in cloud environments[J]. Journal of Network & Computer Applications，2015，50（C）：39—48.

[2]    SINGH S，SWAROOP A，KUMAR A，et al. A survey on techniques to achieve energy efficiency in cloud computing[C]// International Conference on Computing，Communication and Automation. IEEE，2017：1281—1285.

[15]  PATEL M K，KABAT M R，TRIPATHY C R. A hybrid ACO/PSO based algorithm for QoS multicast routing problem[J]. Ain Shams Engineering Journal，2014，5（1）：113—120.

[16]  MASDARI M，SALEHI F，JALALI M，et al. A survey of PSO-based scheduling algorithms in cloud computing [J]. Journal of Network & Systems Management，2017，25（1）：122—158.

[17]  Al-MAAMARI A，OMARA F A. Task scheduling using PSO algorithm in cloud computing environments [J]. International Journal of Grid and Distributed Computing，2015，8（5）： 245—256.

[18]  ROSTAMI A，LASHKARI M. Extended PSO algorithm for improvement problems K-means clustering algorithm [J]. International Journal of Managing Information Technology，2014，6（3）：17—29.

[19] BOROWSKA B. Exponential inertia weight in particle swarm optimization [C]// Information Systems Architecture and Technology： Proceedings of 37th International Conference on Information Systems Architecture and Technology C ISAT 2016 C Part IV. Springer International Publishing，2017：265—275.

[20]  BHARATHI P D，PRAKASH P，KIRAN M V K. Energy efficient strategy for task allocation and VM placement in cloud environment[C]// Power and Advanced Computing Technologies. IEEE，2018：1—6.

[21]  MISHRA S K，PUTHAL D，SAHOO B，et al. An adaptive task allocation technique for green cloud computing [J]. Journal of Supercomputing，2018，74（1）：1—16.

[22]  束柬，梁昌勇，徐健. 基于信任的云服務系统多目标任务分配模型[J]. 计算机研究与发展，2018，55（6）：1167—1179.

SHU J，LIANG C Y，XU J. Trust-based multi-objectives task assignment model in cloud service system[J]. Journal of Computer Research and Development， 2018， 55（6）： 1167—1179.（In Chinese）

[23]  JU J H，BAO W Z，WANG Z Y，et al. Research for the task scheduling algorithm optimization based on hybrid PSO and ACO for cloud computing[J]. International Journal of Grid & Distributed Computing，2014，7（25）：217—218.