基于混合算法的云计算任务调度方法研究

赵保华

（阿坝师范学院，四川 汶川　623002）

基于混合算法的云计算任务调度方法研究

赵保华

（阿坝师范学院，四川 汶川623002）

目前针对任务调度方法的研究中，为了降低研究难度，通常只针对某一个考量任务调度方法好坏的尺度进行研究，经常会出现优化后的方法以较高的计算成本为代价换来较短的任务完成时间，有时是得不偿失的。因此该文将任务完成时间和计算成本均作为优化的目标，对任务调度方法进行研究，平衡任务完成时间和计算成本，提高云计算的效率。该文使用遗传优化算法对上述提出的任务调度问题进行求解，并将模拟退火算法、自适应机理相结合，建立更加适合云计算任务调度求解的混合优化算法。最后，通过实验分析，以仅对任务完成时间优化和仅对计算成本优化的算法进行比较，该文研究的混合算法的云计算任务调度方法能够有效平衡任务完成时间和计算成本，有效提高云计算的效率，降低其计算成本。

混合算法；云计算；任务调度；遗传算法；模拟退火算法

0　引言

随着互联网技术的不断发展，云计算（Cloud Com⁃puting）这一新兴技术模式应运而生。云计算是由并行计算、分布式计算以及网格计算发展而来，其是一种根据需要，随时随地对计算机设备、应用程序亦或是存储资源等共享资源进行访问的计算模式。云计算体系架构主要由平台即服务（PaaS）、基础设施即服务（IaaS）以及软件即服务（SaaS）三层组成［1⁃3］。

云计算环境下，将一个任务分配成多个子任务，分发到云环境中的各个计算机节点，各个计算机节点执行各自子任务，并将结果返回，组合即得到原任务的解。在不同的环境和任务下，计算节点、任务数量规模以及用户数量各不相同，因此如何高效合理地对云计算环境下任务进行调度，使得任务完成时间最短，消耗成本最低已然成为目前云计算领域研究热点之一［4⁃5］。

在云计算环境中，考量任务调度方法好坏的尺度主要有任务完成时间、带宽资源、负载均衡以及计算成本等。目前，针对任务调度方法的研究中，为了降低研究难度，通常只针对某一个考量任务调度方法好坏的尺度进行研究，问题是经常出现优化后的方法以较高的计算成本为代价换来较短的任务完成时间，有时是得不偿失的，因此本文将任务完成时间和计算成本均作为优化的目标，对任务调度方法进行研究，平衡任务完成时间和计算成本，提高云计算的效率［6］。

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

云计算的任务调度问题主要由提交任务、获取可利用资源信息、执行任务调度策略以及返回计算结果这四部分完成。云计算的任务调度过程如图1所示。首先，用户将任务提交至由多计算资源组成的云计算系统，系统将任务划分为多个子任务；之后，根据特定的任务调度方法，将子任务与云计算环境下的可用计算资源建立联系并分配任务，通常，一个子任务只能够分配给一个可利用计算资源，但是一个可利用计算资源能够接受多个任务；最后各个计算资源将计算结果返回云计算系统并整合结果，完成计算任务［7］。

图1　云计算的任务调度过程

2　混合优化算法

使用遗传优化算法对上述提出的任务调度问题进行求解，并将模拟退火算法、自适应机理相结合，建立更加适合云计算任务调度求解的混合优化算法。常规遗传算法经常容易出现最优的染色体丢失，造成局部寻优能力下降，或者出现早熟线性。模拟退火算法广泛应用于组合优化等领域。模拟退火算法是模拟热力学物理中的冷却与退火过程，其局部寻优能力较强，但是整体寻优能力和效率均不够高。因此本文将遗传算法和模拟退火算法进行混合，发挥各自优点，弥补缺点。在遗传算法的循环寻优过程中，利用模拟退火算法的局部寻优能力和能够避免陷入局部最小值的优点，同时对遗传算法的交叉、变异概率进行自适应改进，以提高算法的寻优效率和收敛精度。混合优化算法的工作流程见图2。

模拟退火算法的工作流程如下：

Step1：将目标函数目前的最优值看作当前最优解。

Step2：设定起始温度θ=T0。

Step3：对退火算法的最大代数tmax和初值t=0进行设定。

Step4：随机变化目前最优点，生成新解求解新的目标函数值，解出增量Δ。

Step5：若增量Δ＜0，则将新的最优解看作目前的最优解，如果增量Δ≥0，并且满足条件，则将新的最优解看作目前的最优解。

Step6：若t＜tmax，则令 θ=T（k），k=k+1，t=t+1，并跳至Step4；若t＞tmax，则使用退火操作后的个体替换原来种群中适应值最弱的个体。

图2　混合优化算法的工作流程

使用上述的模拟退火算法的好处是，若新解性能更好，则将新解作为当前解；若新解恶化，则以一定概率将新解作为当前解，从而确保算法寻找局部最优解的能力。

通常考虑到计算量和可行性，选取如下的降温方式作为模拟退火算法的控制温度下降函数：

式中：λ正数，并且略微低于1；k是降温次数［8］。

设定遗传算法中种群规模为S，资源数量为M，分配子任务个数为N，则生成初始种群表述为：系统随机得到S个长度为N的染色个体，基因值是范围在1～M之间的随机数。遗传算法中的适应度函数会影响算法的收敛速度和收敛精度，个体的适应值大小会影响其遗传到下一代的概率大小。本文研究的云计算任务调度问题，需要对完成所有分配的子任务的时间和成本进行考虑。时间的适应度函数表示为：

式中：uLB是平衡任务负载因子，描述各个资源的利用情况，值越大，利用率越高，则对应的completeTime（I）越低［9］。

成本的适应度函数表示为：

如果适应度函数只对时间约束进行考虑，则计算资源的利用率越低，完成任务时间越长的个体，其适应值越小。如果适应度函数只对成本约束进行考虑，则完成任务所需成本越高的个体，其适应值越小。如果适应度函数同时对时间约束和成本约束进行考虑，则适应度函数为：

式中：α和β均在0～1之间，并且α+β=1。如果α=1，β=0，则通过算法进行任务调度得到的结果是所消耗时间最短；如果α=0，β=1，则通过算法进行任务调度得到的结果是所消耗成本最少［10⁃11］。

3　实验分析

使用墨尔本大学开发的Cloudsim 3.0云仿真平台对本文研究的任务调度算法进行性能分析。使用仅对任务完成时间优化的常规遗传算法和对计算成本优化的常规遗传优化算法以及同时对任务完成时间和计算成本优化的常规遗传算法作为对比。模拟退火算法中，设定初始退火温度为T0=200℃，λ=0.92。遗传算法中，交叉概率 Pc1=0.95，Pc2=0.7，变异概率 Pm1=0.1，Pm2=0.01，α=0.35，β=0.65。设定种群规模为S=100，分配子任务个数为N=1 500，资源数量为M=10，最大迭代次数为200。得到测试结果如图3所示。测试结果表明，使用的四种任务调度算法测试过程中，在算法迭代起始阶段，四种算法对任务完成时间和计算成本的优化效果基本相同，但在迭代中后期，各种算法的优化性能显现出差异。仅对任务完成时间优化的常规遗传算法对任务完成时间起到较好的优化，但是对于计算成本没有较好的优化效果，使用该种任务调度算法，计算成本较高。而仅对计算成本优化的常规遗传算法对计算成本起到较好的优化，但是对于任务完成时间没有较好的优化效果，使用该种任务调度算法，任务完成时间较长。而使用同时对任务完成时间和计算成本优化的任务调度算法能够较好平衡任务完成时间和计算成本。另外本文使用的混合算法，在遗传算法的循环寻优过程中，利用模拟退火算法的局部寻优能力和能够避免陷入局部最小值的优点，同时对遗传算法的交叉、变异概率进行自适应改进，使得对任务完成时间和计算成本优化效果更加明显，要优于常规遗传算法。

图3　云计算任务调度算法测试结果

4　结语

本文将任务完成时间和计算成本均作为优化的目标，对任务调度方法进行研究，平衡任务完成时间和计算成本，提高云计算的效率。将遗传算法和模拟退火算法进行混合，发挥各自优点，弥补缺点。在遗传算法的循环寻优过程中，利用模拟退火算法的局部寻优能力和能够避免陷入局部最小值的优点，同时对遗传算法的交叉、变异概率进行自适应改进，以提高算法的寻优效率和收敛精度。使用Cloudsim 3.0云仿真平台进行对比测试，结果表明：使用同时对任务完成时间和计算成本优化的任务调度算法能够较好平衡任务完成时间和计算成本，另外本文使用的混合算法，对任务完成时间和计算成本优化效果更加明显，要优于常规遗传算法。

［1］王登科，李忠.基于粒子群优化与蚁群优化的云计算任务调度算法［J］.计算机应用与软件，2013，30（1）：290⁃293.

［2］朱宗斌，杜中军.基于改进GA的云计算任务调度算法［J］.计算机工程与应用，2013，49（5）：77⁃80.

［3］朱宇航，郑丽英，邬开俊.基于改进DE的云计算任务调度算法［J］.兰州交通大学学报，2013，32（1）：101⁃106.

［4］邬海艳.基于云计算环境下资源调度算法研究［D］.赣州：江西理工大学，2012.

［5］李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法［J］.计算机应用，2011，31（1）：184⁃186.

［6］王波，张晓磊.基于粒子群遗传算法的云计算任务调度研究［J］.计算机工程与应用，2015，51（6）：84⁃88.

［7］金伟健，王春枝.基于蝙蝠算法的云计算资源分配研究［J］.计算机应用研究，2015，32（4）：1184⁃1187.

［8］吴虎胜，张凤鸣，赵法栋.利用自适应混合遗传算法求解平车装载问题［J］.铁道学报，2013，35（12）：1⁃8.

［9］王灵霞，赵宏.云环境下基于免疫遗传算法的任务调度问题研究［J］.自动化与仪器仪表，2015（3）：114⁃116.

［10］宋芳琴.基于改进的蝙蝠算法在云计算中的资源分配［J］.计算机系统应用，2015，24（8）：128⁃132.

［11］邓见光.云计算任务调度策略研究［D］.广州：华南理工大学，2014.

Research on cloud computing task scheduling method based on hybrid algorithm

ZHAO Baohua
（Aba Teachers College，Wenchuan 623002，China）

In order to reduce the difficulty of study，only the level of stand or fall of task scheduling method is usually con⁃sidered in the researched，but the optimized method often causes a higher computational cost in exchange for shorter task com⁃pletion time，which sometimes is not worth the candle.Therefore，both the task completion time and computation cost are all taken as optimization object in this paper to conduct the research of the task scheduling method，balance the task completion time against computation cost，and improve the efficiency of cloud computing.In this paper，a genetic optimization algorithm is used to solve the proposed task scheduling problem，and the simulation annealing algorithm is combined with adaptive mecha⁃nism to establish a hybrid optimization algorithm which is more suitable for cloud computing task scheduling.The task comple⁃tion time optimization algorithm and cost optimization algorithm are compared by means of experimental analysis.The cloud com⁃puting task scheduling method of the hybrid optimization algorithm can effectively balance the task completion time against com⁃puting cost，effectively improve the efficiency of cloud computation，and reduce its computational cost.

hybrid algorithm；cloud computing；task scheduling；genetic algorithm；simulated annealing algorithm

TN911⁃34；TP393

A

1004⁃373X（2016）12⁃0070⁃03

10.16652/j.issn.1004⁃373x.2016.12.018

2015⁃11⁃30 基金项目：四川省教育厅自然科学重点课题：高校数据中心建设与研究（13ZA0038）；四川省教育厅自然科学重点课题：OpenFlow在校园网的应用方案研究（15ZA0338）

赵保华（1968—），男，四川蓬溪人，副教授，硕士。主要研究方向为计算机及应用、网络技术、高校信息化。