计算机网络工程论文范文云计算任务调度混合算法

　　这篇计算机网络工程论文范文为提高云计算速度，描述云计算任务调度问题，及混合优化算法，并实验对本文的任务调度算法进行性能分析，提出可行性办法。《上海信息化》(月刊)创刊于2000年，由《上海信息化》杂志社主办。是国内第一本全面反映政府、企业信息化建设的综合类公开出版刊物。杂志定位为政府信息化的窗口，企业信息化的舞台，IT从业人员的讲坛。创刊以来，杂志立足长三角，面向全国，以创新开放的理念、丰富贴切的内容、广泛深入的触角，以及鲜活生动的人物报道，在业界产生了较大影响。获“世博报道优秀期刊”。

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

　　关键词： 混合算法; 云计算; 任务调度; 遗传算法; 模拟退火算法

　　0 引 言

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

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

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

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

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

　　2 混合优化算法

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

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

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

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

　　[Tk+1=λTk] (1)

　　式中：[λ]正数，并且略微低于1;[k]是降温次数[8]。

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

　　[FtimeI=1completeTimeI·uLB] (2)

　　[uLB=i=1MsumTimeiM×completeTimeI] (3)

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

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

　　[FcostI=1completeCostI] (4)

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

　　[FitnessI=α·FtimeI+β·FcostI] (5)

　　式中：[α]和[β]均在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所示。测试结果表明，使用的四种任务调度算法测试过程中，在算法迭代起始阶段，四种算法对任务完成时间和计算成本的优化效果基本相同，但在迭代中后期，各种算法的优化性能显现出差异。仅对任务完成时间优化的常规遗传算法对任务完成时间起到较好的优化，但是对于计算成本没有较好的优化效果，使用该种任务调度算法，计算成本较高。而仅对计算成本优化的常规遗传算法对计算成本起到较好的优化，但是对于任务完成时间没有较好的优化效果，使用该种任务调度算法，任务完成时间较长。而使用同时对任务完成时间和计算成本优化的任务调度算法能够较好平衡任务完成时间和计算成本。另外本文使用的混合算法，在遗传算法的循环寻优过程中，利用模拟退火算法的局部寻优能力和能够避免陷入局部最小值的优点，同时对遗传算法的交叉、变异概率进行自适应改进，使得对任务完成时间和计算成本优化效果更加明显，要优于常规遗传算法。

　　4 结 语

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

转载请注明来自发表学术论文网：http://www.fbxslw.com/dzlw/11172.html