基于改进差分进化算法的云计算资源调度策略

张红

(甘肃中医药大学 网络与信息管理中心，兰州 730000)

近年来，随着计算机技术的发展，云计算成为人民大众所关注的热点问题，凭借高计算能力、可扩展性、易访问性、高性价比等特点，已在很多领域引起关注并获得应用.云计算是在很多技术的支持下产生的，传统的计算机技术和网络技术，如虚拟化技术，网格存储技术，分布式技术和并行计算技术[1].云计算就是利用多种从传统计算机技术将全球各地的资源整合起来，根据用户的需求动态的分配一定资源，用户支付一定费用.实质上云计算是一种以营利为最终目标的、无限供应所需资源、需要高水平硬件设备支持的商业模式，为用户动态的提供服务[2].对于供应商来说，云计算理念的实现需要硬件支持，提供软件技术的支持，还要提供合适的动态资源分配调度策略，我们可以最大化我们的利益并满足供应商的需求.对于用户来说，只是需要通过互联网进行简单的输入操作，支付一定的费用，就可以使用到在本地无法获得的资源.云计算本质就是将互联网上闲散的资源、设备进行整合，最终实现实时动态的共享[3].

目前，许多学者对云计算的资源调度问题进行了研究，引入了不少算法，例如为了提高收敛速度，加快搜索，改进粒子群优化算法如贪婪粒子群算法等.节能DAG 的调度方法，提高了能源效率.基因型-表现型映射关系(GPM)来改进遗传算法，消除了进化算子和修复阶段的开销所施加的限制，极大地提高了解的质量和收敛速度.基于集群的任务调度算法，解决数据密集型任务实现调度长度及效率的优化，对虚拟机的消耗进行限制，实现了资源调度能源消耗的最小化；一种基于代理的架构，将不同的组件部署在高性能计算云服务上，加速资源使用，帮助用户选择和排名服务的供应商，设计特殊索引来管理供应商信息，却没有考虑服务质量参数，没有考虑系统优化等问题[4-5].差分进化算法是基于群体差异的启发式随机算法，在收敛速度和稳定性方面较好，适用范围较广.虽然DE算法有很多优点，但是其存在着参数选择不易、后期的收敛速度变缓、容易陷入局部最优解等缺点.可以依据实际问题对基本DE算法进行改进，得到更高效、更合理的改进DE算法，求得较优的解成功应用到不同领域的实际问题中去[6].

本文的云任务调度策略采用改进差分算法的变异操作，以加强全局搜索能力及加快搜索速度，对整个解空间进行迭代搜索，直到满足结束条件并找到适应度函数值最大的个体，输出最优解.通过实验证明，本文算法在时间成本、功耗成本、负载均衡性、优化资源以及合理调度资源等方面具有一定的改进效果.

1 云计算的资源调度

当用户存在需求，会向互联网提出请求，云端接收到用户的请求后，发送至资源调度中心，它会根据用户的要求和所需要的资源，在众多的资源中找到最佳的资源节点，并将用户请求提交至该资源上进行处理，这个过程被称为云计算资源调度(Cloud Computing Resource Scheduling,CCRS).解决CCRS问题的最终目标是为了找到最佳的资源分配，将多个用户请求任务与空闲的云计算资源找到一种最合理的映射方式，使得资源分配“最佳”,对于云计算资源调度问题，由于系统的复杂性，任务调度是对于各种类型的虚拟资源节点的调度.

可以将CCRS问题简述为数学模型为用户任务到云计算资源的一种映射:f(t→r).设用户请求为t(t1，t2，t3，t4,…，tn)云端的资源为r(r1，r2，r3，r4,…，rm)，使得目标函数f(f1，f2，f3，f4,…，fn)求得最优解，用户请求与云端资源是多对一的映射关系.CCRS问题映射图如图1所示.

当前对云计算核心服务的分为三种模型，基础设施即服务(Infrastructure as a Service，IaaS)模型、平台即服务(Platform as a Service，PaaS)模型，以及软件即服务(Software as a Service，SaaS)模型.

(1)基础设施即服务(IaaS)：IaaS是云计算服务模型的最低层，计算主机，存储中心和通信网络协同工作以构建IaaS基础架构.云计算的独特虚拟化技术使IaaS能够为客户提供定制服务，如数据信息存储，海量数据计算，负载平衡监控和重要数据备份.除了提供卓越的处理能力外，IaaS还能够按需动态重新配置云计算资源并将其安装在IaaS.由于IaaS的存在，用户可以快速获得 DevOps的强大功能.仅根据业务的实际需要使用计算机资源和中间件模型.通过配置，包装和包装操作，可以在很短的时间内快速完成新IT产品的交付[7].

(2)平台即服务(PaaS)：PaaS服务提供商提供支持的工具和编程语言，消费者只需要在其上部署自己的应用程序.PaaS依靠托管服务为编程模型，身份认证，数据库管理，访问控制，系统管理和数据挖掘提供多种选择.云计算服务提供商使用编程代码和开发模式，程序开发人员可以使用网络上的数据资源，从而可以实时更新和优化云计算平台中的各种云服务程序.

(3)软件即服务(SaaS)：云计算服务模型的顶端是SaaS，它提供集中托管应用程序，使企业客户能够将应用软件部署到SaaS供应商的硬件服务器上运行.SaaS能够根据某些服务协议，通过网络快速直接地为企业客户提供符合企业应用程序的软件应用程序服务.只要能够登录互联网，企业客户就可以在任何PC设备和移动设备上享受SaaS提供的服务.SaaS支持快速部署应用程序，采用基础架构共享，无需企业客户在基础架构维护上花费太多精力和费用.SaaS采用订阅付款方式,SaaS的应用软件具有良好的专业性，管理复杂的软硬件维护、安全可用性和性能等工作.SaaS 作为将来软件行业发展的必然模式，目前已经应用到电子商务、在线教育、行政审批以及医疗服务等不同的专业领域[8].云计算核心服务的示意图如图2所示.

图2 云计算核心服务示意图

根据云计算核心服务的三种不同形式，CCRS问题的研究也大致可以分为这三类优化目标主要考虑到两个方面：一方面，供应商应该在最小化优化目标的同时满足用户质量服务参数QoS(Quality of Service)；另一方面，供应商同样希望能够使得自身资源利用最大化，从而提高经济效益.

用户任务分配是云计算资源管理的一项重要工作，三种任务分配控制模式在云计算环境中,任务的调度模式一般分为中心控制模式(Centralized model)、去中心控制模式(Decentralized model)、混合模式(Hybrid model)[9].下图3是三种任务分配的控制方式.

图3 三种任务分配控制方式

2 差分进化算法

差分进化算法是一种基于种群进化的优化算法，具有良好的稳定性、可靠性和鲁棒性.差分进化算法由于其优越性使得它在多个领域得到广泛应用，例如在电力系统动态经济调度、车间调度、约束性优化、电磁学和光学等，它吸引了国内外学者的关注[10,11].

本文以较为流行的DE算法DE/rand/1为例介绍一下DE算法的三种操作和基本步骤[12,13].

(1)变异操作：

(1)

(2)交叉操作：

(2)

(3)选择操作：

(3)

以下是基本差分进化算法的步骤：

① 初始化参数：种群规模NP；变异因子F;变异因子空间维数D；进化代数t=0.

③ 个体评价：计算每个个体的适应度值.

3 云资源调度改进差分算法的设计

云计算的资源调度主要由大量不同的资源节点组成的，不同的资源节点具有不同的处理能力；要处理的大多数任务都是大数据任务，需要存储和计算海量数据.不同任务分配的资源也不同；用户对于任务需求的满意程度不同，有的是需要保证任务的实时性，有的是需要巨大的存储空间，还有的是需要任务完成的准确和高效.图4为本文云计算资源调度的示意图.

图4 云计算资源调度示意图

本文使用公式(3)评估个体的最优解，并对虚拟机和云任务的信息进行迭代循环处理，直到找到具有最优适应值的个体或满足迭代终止条件，最后输出最优解.本文通过变异概率自适应调整的改进差分进化算法(ATMPIDE)调度云计算资源，其操作步骤如下:

(1)首先随机初始化参数，包含最大迭代次数或其它迭代终止条件、种群规模、交叉概率和变异概率等参数.虚拟机适应度函数的设定如下：

对某个个体按规则解码后就可得出任务集的一种资源分配方案，每台虚拟机的任务各不相同.假设在第j台虚拟机上分配了w个任务，则第j台虚拟机完成其分配到的任务所用的时间F(j)为：

(4)

(2)种群评价，计算所有个体的适应度值，评估各个个体的优劣程度，保留当代种群的最优个体，将其标记为全局最优值和当前最优值.

由公式(4)可得出：所有任务总的执行完成时间TF为：

(5)

其中，m表示虚拟机的数量.

虚拟资源集的平均负载量LC和负载均衡标准差LSD分别为：

(6)

(7)

由公式(5)和(6)可得出适应度函数为：

(8)

其中，适应度函数值越大表明该个体就越优秀.

(3)判断是否满足迭代终止条件，否则进入下一步.

(4)采用轮盘赌选择操作，选出优秀个体并将优质基因传递给下一代，实行精英保留方式，避免那些优秀个体在逐代进化中流失.

(5)按照预先设定好的交叉概率选择当前种群的个体来执行多点交叉操作，改变染色体的基因排列，生成更多不一样的个体，确保群体的多样化.

(6)选择当前群体的个体根据自适应变异概率进行变异操作.变异概率能够适应度的值自动设定阈值，在个体基因上随机选择多个位置，每个位置进行小范围变异，根据变异的阈值，若产生的随机数小于阈值，则发生变异，否则不发生变异.

随迭代过程自适应的变异概率Pm为：

(9)

其中i为迭代次数，i∈[0.05,0.35].

虚拟机的适应度所对应的序号由变异操作后基因值确定.适应度值越高，虚拟机的性能越好，选择起来就越容易.

(7)评价当前种群，计算所有个体适应度值，并找出哪个最大值被标记为当代最优个体，采用选择准则，若新个体适应度值大于原先最优个体适应度值，则接受新个体，并以新个体代替种群中的旧个体，若新适应度值小于原适应度值，则拒绝接受新个体.

(8)确定是否满足循环终止条件，如果满足，则输出最终结果；否则，算法跳转到步骤4继续循环执行.

图5为本文算法的基本流程图.

图5 ATMPIDE 算法基本流程图

4 仿真实验与分析

本文采用云计算仿真器 CloudSim3.0 来进行仿真实验，然后调用ATMPIDE 方法来实现该算法定义的云任务调度策略的模拟实验.本文的云任务调度仿真实验从负载均衡、任务完成时间和收敛速度等方面对本文提出的改进差分算法ATMPIDE 与 DE 及 FIFO 算法进行对比，验证本文所提算法 ATMPIDE 的性能.先进先出(FIFO)算法是CloudSim自带的任务调度算法，主要的调度思想是以完成一个任务以后才能开始另一个任务，以排队方式进行任务分配和处理.

仿真实验针首先对 ATMPIDE 与DE 及 FIFO在负载均衡方面进行比较.当虚拟机数量分别为 100 台、200台和300台时，任务的数量从100 个到 600 个结束，比较三种算法的虚拟机负载均衡标准差，如图 6-图8 所示.

图6 虚拟机数为100台时的负载均衡标准差

图7 虚拟机数为200台时的负载均衡标准差

图8 虚拟机数为300台时的负载均衡标准差

从上面运行结果可以得出，当虚拟机数量一定时，ATMPIDE 在负载均衡方面取得的效果是较好的，随着任务个数的增加，负载均衡标准差在 10附近；DE的负载均衡标准差在 20 左右；而 FIFO的负载均衡标准差则在 25上下振荡.对比结果表明，改进的差分进化算法在任务数量多、复杂度高的环境下具有量高的调度性能.

下面分别对 ATMPIDE 与DE 及 FIFO 在虚拟机数量为150台时，任务数为100、200和300时的完成时间进行比较.三种算法任务完成时间的比较分别如图 9-图11 所示.

图9 任务数为100时的完成时间

图10 任务数为300时的完成时间

图11 任务数为500时的完成时间

虚拟机负载均衡标准差的理想值为 0，其值越小，各虚拟机的负载量越接近，调度策略越合理，资源利用率就越高；同时，总任务完成时间 也很可能会更小.从上面运行结果可知，当虚拟机数量维持不变时，不管任务量是多少，ATMPIDE 的完成时间最小，其次是 DE，最后是 FIFO，随着任务数量的提升，ATMPIDE 表现出较为明显的优势.这说明，总体上改进的差分进化算法收敛速度较快且优化精度较高.

可以看到不管任务数量和虚拟机数量如何变化，改进的DE算法ATMPIDE 能够更有效地实现较好的目标区域的搜索，降低了任务的完成时间，保持节点的负载均衡，同时能有效克服局部最优及早熟现象，提高云计算任务调度的利用率，在优化资源以及合理调度资源方面具有较好的效果.

5 结语

本文针对云计算资源调度问题，以虚拟机负载均衡及任务完成时间为目标，设计出了一种改进差分进化算法，改进了差分变异操作，促使变异操作朝更优的方向来优化计算结果，加快了搜索速度，提高了全局搜索能力，通过仿真实验对ATMPIDE算法与 DE 及 FIFO进行比较，结果表明本文所提出的算法取得了一定的改进效果.