基于粒子群算法的云工作流调度优化研究

孙妍姑

（淮南师范学院计算机学院，安徽淮南232038）

基于粒子群算法的云工作流调度优化研究

孙妍姑

（淮南师范学院计算机学院，安徽淮南232038）

随着云计算的发展，其应用流程日趋复杂，而工作流系统能对复杂流程进行抽象定义，所以被作为一种有效的解决方案提出。针对QoS优化目标（如时间、成本等），用户的个性化需求和约束，以及工作流内任务之间的依赖关系约束等问题，可采用多目标PSO算法进行调度优化。多目标PSO算法既充分照顾到QoS约束，符合云计算环境中工作流调度的实际情况，又返回Pareto最优解集，其中的非劣解从不同程度优化目标，可以应用适应度函数选择一个合适的调度方案。

云工作流调度；QoS；PSO；调度优化

云计算是在网格计算、分布式计算及并行计算基础上发展起来的一种主流的计算模型，它将分布在不同地理位置上的资源（计算资源和存储资源）封装成服务，向Internet应用提供三大服务模式，即IaaS、PaaS和SaaS①Wu Z,Liu X,Ni Z,et al,A Market-Oriented Hierarchical Scheduling Strategy in Cloud Workflow System,The Journal of Supercomputing,Vol.63,No.1,2013,pp.1-38.。随着大数据应用范围的扩展，云计算也不断发展，其应用流程日趋复杂，而工作流系统能够对复杂的工作流程进行抽象定义，为用户提供方便，所以被作为一种有效的解决方案提出。

在云环境中，如何对工作流任务进行最优调度，是云工作流最重要的核心技术之一。在进行调度优化时，主要针对QoS②王岩，汪晋宽，汪翠荣：《QoS约束的云工作流调度算法》，《东北大学学报》（自然科学版）2014年第7期，第939-943页。优化目标进行考虑，如时间、成本等因素，此外，还要考虑用户的个性化需求和约束，工作流内任务之间的依赖关系约束等。这是一个典型的多目标优化问题，而智能算法是解决此类问题的重要方法，如粒子群优化算法、蚁群优化算法等。

本文对云计算环境下的工作流系统进行研究，分析了主要的云工作流调度算法的优缺点，提出基于多目标粒子群算法的云工作流调度策略。

1 云工作流系统中的任务调度算法

1.1 云工作流系统

云工作流是在云计算环境下工作流管理系统的一种新的应用。通过虚拟化技术，云工作流管理系统对所有的计算或存储资源统一管理，使任务调度可以有序高效地进行，实现业务流程自动化。云工作流系统并不是云计算和工作流模式的简单嫁接，而是针对云计算的特性制定相应的规则，以保证工作流中任务的执行和部署，并建立新型的云工作流系统架构③李学俊，徐佳，王福田：《云工作流系统中能耗感知的任务调度算法》，《模式识别与人工智能》2016年第9期，第790-796页。（见图1）。

云工作流系统按层次分为4层：应用层、平台层、统一资源层和基础架构层。基础架构层为虚拟化资源（计算、存储、网络资源）的提供者，如阿里云数据中心、谷歌云数据中心等。统一资源层由工作流运行所需的软、硬件服务资源组成，负责执行每一项分配好的任务。平台层是上层用户应用和下层虚拟化统一资源的中间层，是云工作流系统的开发和运行平台，主要作用是将用户应用中的任务映射于某一虚拟化资源。应用层为实际业务流程的工作流应用程序，为用户应用提供了统一的接口。统一资源层和基础架构层的维护一般由外部云服务提供商维护，应用层和平台层一般是独立进行自我维护。

图1 云工作流系统架构

1.2 云工作流任务调度

在云工作流系统发展初期，一方面由于云计算环境规模较小，另一方面费用问题是云服务提供商很关注的重点，所以很多研究着重于如何优化任务执行的成本，降低云环境的使用费用，任务调度的优化目标是单目标优化。现在随着云环境规模的不断扩大，在工作流任务调度优化中需要考虑的因素也越来越多，包括时间、成本、系统可靠性等，所以越来越多的研究开始关注QoS，强调通过有效的QoS管理来提高服务质量。

云工作流系统的任务调度属于NP-hard问题，应用群智能算法进行调度效果较好，比如蚁群算法ACO、粒子群算法PSO①Zhang L,Chen Y,Sun R,et al,A task scheduling algorithm based on PSO for grid computing,International Journal of Computational Intelligence Research,Vol.4,No.1,2008,pp.37-43.。蚁群算法是通过对蚂蚁觅食行为的科学模拟和研究得出的用于解决组合优化难题的智能算法。ACO可以用于单目标优化调度，如并行虚拟机的最大完成时间优化调度，也可以进行多目标同时优化，如综合考虑时间、成本等QoS约束的优化调度。文献②伍章俊：《云工作流服务组合与活动调度策略研究》，合肥工业大学博士学位论文，2011年。根据云工作流服务资源的QoS约束，结合用户偏好，提出了一种云工作流资源组合算法，将云服务分为服务选择和服务调整感知组合两个部分。在服务选择部分综合考虑时间、成本、可靠性等多约束因素，设计了多目标蚁群算法，求解Pareto解集和优化解。文献③蒲汛：《群集智能及其在分布式系统中的应用研究》，电子科技大学博士学位论文，2012年。针对在云计算环境中如何构建多约束的QoS组播路由的问题，设计了一种基于改进Pareto的蚁群算法。该蚁群算法能在给定的QoS下快速找出Pareto非劣解，同时引入激励更新机制提高算法的收敛速度，从而能够较快地搜索到全局（近似）最优解。

粒子群算法是基于自然界中鸟类、鱼类等群体动物的合作行为，受群体智能启发而建立的启发式优化算法。PSO算法具有参数少、算法简单、收敛快、鲁棒性好等优点，被广泛应用于多种优化问题。文献④郭力争：《云计算环境下资源部署与任务调度研究》，东华大学博士学位论文，2015年。在多数据中心环境下，为了优化用户的性能体验，降低使用费用，采用PSO来优化数据部署和任务调度，并提出嵌入可变领域搜索的PSO，从而提高了算法的求解精度。文献⑤姚光顺：《面向工作流任务的云计算资源多目标与容错调度研究》，东华大学博士学位论文，2016年。应用PSO对多目标要求下的具有依赖关系的云工作流进行任务调度优化，为避免PSO陷入局部最优解，算法还加入了一个基于内分泌系统中促激素和释放激素工作机制的进化策略，使该PSO算法能更好地进行多目标调度。

2 多目标粒子群优化算法

2.1 多目标优化

由于云计算的用户群体的目标偏好各有不同，同时要考虑云工作流调度中QoS的各个因素，可见云工作流任务调度是一个多目标优化问题。而PSO算法本身主要处理的是单一目标优化问题，不能直接应用于多目标优化，所以需要对PSO算法进行改进。

一个多目标优化问题可如下定义：

x=(x1,x2,···，xa)∈X是a维决策向量，目标个数为b，y=f(x)=(y1,y2,···，yb)∈Y为目标向量，X为搜索空间，Y是目标空间。

多目标优化问题很难有能够达到所有目标最优的最优解，求解时期望解能够落在一个潜在的解决方案集合中，称此集合为Pareto最优解集合。Pareto最优解集中的解会从不同程度优化多目标。

本文重点考虑OoS的成本和时间两个标准。时间标准是从用户提交一个工作流应用到返回结果的总时间（执行时间和网络传输时间）。成本标准是依据云供应商提供服务所要求的价格乘以该服务的实际执行时间。

2.2 PSO算法

在PSO算法中，粒子的集合称为种群，依据不同的问题设置适应度函数，以计算每个粒子位置的好坏，第i个粒子的位置和速度的表示为：

空间维度为d维，boundmin和boundmax为解空间的上、下界；xid和vid表示第i个粒子在第d维的位置和速度分量。在迭代中，粒子的位置和速度更新公式为：

r1，r2为[0,1]间的随机数，c1,c2为学习因子，且c1+c2=2，ω为惯性权重是第t-1次迭代的个体第t-1次迭代的全局最优解。

2.3 多目标PSO算法

2.3.1 关键变量、函数设定

这里多目标PSO算法所关注的目标是时间优化和成本优化，修改后的PSO算法中，粒子的位置：

Ti表示一个任务，Pj表示云服务节点，二元组表示Ti,Pj之间的映射关系。

粒子的速度：

w(v)是权值，即可行分配v的可能性。

多目标问题的决策变量是一个可行的调度方案，这里即为二元组集合M。两个目标函数如下：

多目标PSO算法要找到一个Pareto最优解集，其中每一个解都是一个调度方案，然后从中选择一个合适的。选择时可以利用评估函数，也可以随机选择。随机选择不易陷入局部最优，但收敛速度慢，在多目标优化中效果不好，所以这里设定评估函数为：

wT为表示对时间关注度的权值，wC为表示对成本关注度的权值，wT+wC=1。

2.3.2 多目标PSO算法

多目标PSO算法流程为：

1.计算每个任务的优先级，并把任务按优先级降序排列。

2.对粒子群中的每一个粒子做循环：

（1）随机初始化粒子S[i]，即所有任务随机映射到服务节点；

（2）初始化速度V[i]；

（3）初始化个体极值Pbest[i]=S[i]。

3.计算每个粒子的目标函数值。

4.AddPareto()。

5.种群迭代更新（依据最大迭代次数），对粒子群中的每个粒子做循环：

（1）根据适应值函数选择全局极值Gbest;

（2）计算粒子的新速度；

（3）计算粒子的新位置；

（4）计算粒子的目标函数值；

（5）计算粒子的当前适应值，如果当前适应值比个体极值Pbest[i]好，则更新Pbest[i]，否则不更新；

（6）Addpareto()。

6.返回。

三、实验结果及分析

实验平台采用WorkflowSim，用多目标PSO算法和HEFT、Min-Min两种算法做比较。多目标PSO算法参数设置为：种群规模100，最大迭代次数60，初始种群随机进行初始化，阈值θ=0.6，认知系数c1=1，社会系数c2=1。表1显示的是云环境中1组云服务，使用HEFT算法和Min-Min算法进行调度的结果。

表1 HEFT算法和Min-Min算法调度结果

多目标PSO算法生成的是一组Pareto最优解集，其中包含的非劣解的T(M)∈[38.5,81.8]，C(M)∈[0.136,0.257]，适应值最优的解支配HEFT和Min-Min算法产生的解，多目标PSO算法的调度结果较优。

多目标PSO算法的优点是可以充分照顾到QoS中的多种约束，符合云计算环境中工作流调度的实际情况，同时返回的是一个Pareto最优解集合，其中的非劣解从不同程度优化目标，可以应用适应度函数或用户自主选择一个合适的调度方案。

Research on Partical Swarm Optimization based scheduling for cloud workflow system

SUN Yangu

With the development of cloud computing,its application process is more complex.The workflow system can do abstract definition on complex flows,so it is proposed as a effective solution.On the problems of QoS demands such as cost and time,users'personal demands,and the constraint among workflow tasks,we can use multi-objective PSO to schedule.The multi-objective PSO can attend QoS constraint according with the real condition of cloud workflow system,and return a Pareto optimal solution set.The solutions in the set optimize targets in different degrees,then we can use fitness function to select a suitable scheme.

cloud workflow scheduling;QoS;PSO;scheduling optimization

TP393

A

1009-9530（2017）05-0101-03

2017-08-17

安徽省高校省级自然科学研究项目“基于网格的语义工作流关键技术研究”（KJ2013Z304）

孙妍姑（1978-），女，淮南师范学院计算机学院讲师，研究方向：云计算、工作流、群智能算法。

（责任编辑：汪太文）