基于遗传算法的云任务调度改进算法

任金霞， 黄艺培， 钟小康

（江西理工大学电气工程与自动化学院，江西 赣州341000）

0 引 言

随着信息化时代的到来，云计算[1—3]的商业化越来越火热.它是集合大量的计算储存等资源具有信息化时代特征的新型计算方式，是信息化时代以来的又一次巨变.它使用先进的虚拟化技术抽象计算储存等物理资源并通过专门软件实现自动管理，用户通过租赁的方式提交业务申请能够按照业务的需要获得各类服务.云服务提供商根据用户提交的任务申请通过调度中心为其分配资源，然而，在云计算环境下，复杂的云计算资源及云任务的多样性使得云任务的调度成为困扰云服务提供商的一个难题.

由于在复杂的云计算环境中，云任务的调度本身是一个NP难问题，而各种智能算法被普遍认为是解决NP难问题[4]的一种较先进的算法，能够在一定条件下得到较优的解决方案，甚至最佳解决方案.因此，很多研究学者使用启发式智能算法来处理云任务调度的难题，继而出现了各种基于改进智能算法（遗传算法[5]、匈牙利算法[6]、蚁群算法[7]、粒子群算法[8,9]）的任务调度策略，当然，也有经典的方法，像基于贪心思想的调度策略[10]等.不管何种云任务调度策略,在云计算商品化的过程中满足用户要求尽可能快地完成任务的同时还应兼顾云平台的效率，均衡虚拟机的负载来提高资源的利用率.因此，文中针对云任务的调度问题提出一种改进的遗传算法，同时对任务执行的完成时间和虚拟机负载的均衡情况进行优化，以达到提高系统吞吐量和资源利用率的目的.

1 问题描述

云环境下，通过虚拟化技术从大批物理资源中抽象出不同性能的虚拟机；云平台出于各种因素的考虑，针对特定的任务集将若干台虚拟机集合到一起构造出一个虚拟资源集；再通过云平台特有调度策略把任务集中的所有待处理的任务提交到该虚拟资源集中的虚拟计算节点上处理.这个过程对每个用户来说都感觉是自己独自占用一台计算机，对云服务提供商来说为了充分发挥云平台的性能，按照哪一种调度策略来分配任务是至关重要的.

为使仿真研究工作更为方便，对具有复杂性和多变性的云计算提出如下假设：

1）忽略带宽、数据传输等对任务执行时间的影响，假定一个任务所需的执行时间等于该任务的长度除以运行该任务的虚拟机的执行速度.

2）云平台是每隔一段时间形成一个任务集并对其进行资源分配，每个任务是相互独立的，且多个任务分配在同一台虚拟机时，按先进先出原则执行任务.

3）云任务和虚拟机资源的表示如下所述.

T={t0,t1,…,tn-1}表示云计算的任务集；其中n为云任务的数量.ti={tid,tlength,tdata,trres}表示第i个任务的属性，tid表示任务的ID，tlength表示任务的总长度，tdata表示任务处理所需的相关数据，trres表示任务希望获得的资源属性情况，主要包括资源的计算能力、内存、带宽，由此可量化任务的QoS性能需求.

V={v0,v1,…,vm-1}表示云平台为相应任务集提供的虚拟机集合，即虚拟资源集；其中m为虚拟机的数量.vi={vid,vmip,vram,vbw}表示第i台虚拟机的性能，vid表示虚拟机的序号，vmip表示虚拟机的计算能力，vram表示虚拟机的内存，vbw表示虚拟机的带宽.在同一台虚拟机上执行的任务遵循先进先出原则.任务集中的所有任务执行完后，云平台收回其对应的虚拟资源集中的虚拟机以便下一次的调度.

2 云任务调度改进算法

遗传算法是由美国J.Holland教授借鉴生物界进化规律在1975年提出的一类随机搜索算法；通过选择、交叉、变异来实现寻优，具备较强的全局搜索能力、前期搜索效率高，但局部搜索能力较差、后期对可行解的搜索速度非常慢、容易产生过早收敛的现象.文中主要对遗传算法的变异操作及变异算子进行改进加快算法收敛速度，搜索最优解.

2.1 云任务调度改进算法的具体描述

采用双精英保留策略对遗传算法进行比例选择操作，引入虚拟机相对适应度，改进遗传算法的变异操作加强全局搜索能力及加快搜索速度，利用公式（5）评价个体的优劣，对整个解空间进行迭代搜索，直到满足迭代终止条件找到适应度值最大的个体，输出最优解.算法流程图如图1所示.

图1 算法流程

2.2 编码方式

将遗传算法传统的0，1编码方式改为实数直接编码方式；每个个体的染色体有多少个基因取决于任务集的任务数量，每个基因的基因值就表示该虚拟资源集中虚拟机的序号.在种群中有若干个个体，每一个个体对应着一个任务集的分配方案，例如：假定虚拟机数量为4台，任务数为8个，则其个体的基因个数为8个，基因值为4台虚拟机所对应序号的其中一个；若有编码为（2，0，3，3，1，2，2，1）的个体，则解码得：0号虚拟机执行任务1，1号虚拟机执行任务4和7，2号虚拟机执行任务0、5和6，3号虚拟机执行任务2和3.

2.3 适应度函数

对某个个体的染色体进行解码可得到一个任务集的分配方案，每台虚拟机上执行的任务各不相同，设第j台虚拟机上分配了w个任务，则第j台虚拟机完成其分配到的任务所用的时间F（j）为：

其中表示第j台虚拟机执行分配在该机上的第i个任务所用的时间.

由公式（1）可得出：所有任务总的执行完成时间TF为：

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

TF越小，用户的评价越好.同时，对云服务提供商来说，虚拟机资源的负载均衡性也非常重要，文中按文献[9]中所提的方法用虚拟机完成其所分配到的任务所用的时间F（j）来表示虚拟机j的负载量，则虚拟资源集的平均负载量AL和负载均衡标准差BL分别为：

其中 F（j）可由公式（1）计算得到；m 表示虚拟机的数量.由此可知，BL理想值为0，BL越小，各虚拟机的负载量越接近，调度策略越合理，资源利用率就越高，同时公式（2）中的所有任务总的执行完成时间TF也会越小.

基于以上分析可得出用来评价个体优劣的适应度函数为：

其中 BL 由公式（4）求得，TF 由公式（2）求得，适应度函数值越大说明个体越优秀.

2.4 改进变异操作

设计自适应变异算子，根据定义的虚拟机相对适应度以轮盘赌选择的方式来进行变异操作.

2.4.1 虚拟机相对适应度

在虚拟资源集中有m台可用的虚拟机；它们之间的配置（参数）都不可能完全一样，而虚拟机的执行速度是影响虚拟机处理任务最主要的性能.

定义1：第k台虚拟机相对适应度VRFk为：

其中表示虚拟资源集中第k台虚拟机的执行速度,TVmips表示虚拟资源集中全部虚拟机的执行速度之和,m表示虚拟机的总数.

由公式（6）可知：执行速度快的虚拟机其相对适应度也要大，且所有虚拟机相对适应度之和等于1.

2.4.2 改进后变异操作过程

如果变异算子设置的较大，变异操作就可以看成是对局部可行解进行随机搜索更优解的一个过程，这使得遗传算法的整体性能和全局搜索能力在迭代开始都会严重退化；如果设置的太小，则在迭代后期会失去局部搜索能力和群体的多样性.因此，对于变异算子的设定应根据需要随迭代过程自适应，变异算子mutateRate为：

其中i为迭代次数.

设定好变异算子后对变异操作进行改进：要对哪一个基因进行变异操作采取随机选择的方式选定，以虚拟机相对适应度VRF为基础构建轮盘，采用轮盘赌方式选择；执行变异操作后基因值就变成了轮盘赌选定的VRF所对应的虚拟机序号.VRF值越大虚拟机的性能就越好，被轮盘赌选中的概率也越大.例如：假定VRF0=0.1,VRF1=0.2,VRF2=0.3,VRF3=0.4，对虚拟机4台任务数6个，染色体编码为（2，0，3，1，2，1）的个体进行变异；若随机选择要变异的基因为第0个，轮盘赌选到VRF3；则变异后个体染色体编码为（3，0，3，1，2，1）.

3 仿真实验与分析

采用澳大利亚墨尔本大学Rajkumar Buyya教授领导团队开发的云仿真器CloudSim3.0[11]来进行仿真实验.用Java编程语言在MyEclipse10.7软件下对CloudSim平台的DatacenterBroker类进行扩展，写入一个新方法：bindCloudletsToVms IGA()，调用该方法来实现根据文中算法定义的云任务调度策略的模拟，以及进行相关测试和实验.在云任务调度仿真实验中，文中算法（Improved Genetic Algorithm，IGA）与传统遗传算法（Genetic Algorithm，GA）及经典的Min-Min算法在任务完成时间和负载均衡情况两个方面进行比较，验证文中算法的性能.

通过随机发生器随机产生任务集和虚拟资源集，任务长度在 [1000,6000)区间，虚拟机执行速度在 [100,500)区间.IGA算法的种群规模size=80，最大迭代次数L=500，交叉算子crossoverRate=0.75.GA算法的变异算子mutateRate=0.1，其余参数与IGA算法一致.

实验一：虚拟机的数量为100台不变，任务的数量为500个不变，重复10次实验取平均值，得到如图2所示随算法迭代次数的增加IGA算法和GA算法在任务完成时间方面收敛情况的对比结果.

图2 IGA算法和GA算法的收敛情况对比

结果分析：从图2中可以看出，与GA算法相比改进后的IGA算法能够更快地达到收敛效果，且任务完成时间的收敛值降低了约10%.

实验二：当虚拟机数量为100台不变，任务的数量从100个开始，每次增加100个，一直到500个时.重复10次实验取平均值，三种算法任务完成时间比较如图3所示，虚拟机负载均衡标准差的比较如图4所示.

结果分析：当虚拟机数量一定时，在任务完成时间方面从图3中可知，文中算法效果最好，并且随着任务数的增加优势慢慢加大.在负载均衡标准差方面，从图4中可以看出，文中算法取得的效果是最好，随着任务数的增加文中算法都能够稳定在10以下，GA算法基本在30以上，且很不稳定，而Min-Min算法则在25左右.由此可知，当虚拟机数量不变而任务数不断增加时，文中算法在任务完成时间和负载均衡标准差上都比另外两种算法取得更好的效果.

图3 三种算法任务完成时间的比较

图4 三种算法虚拟机负载均衡标准差比较

实验三：当任务数为500个不变，虚拟机的数量从50台开始，每次增加50台，一直到250台时.同样反复10次实验取其平均值，三种算法任务完成时间比较如图5所示，虚拟机负载均衡标准差的比较如图6所示.

图5 三种算法任务完成时间的比较

图6 三种算法虚拟机负载均衡标准差的比较

结果分析：从图5和图6中可以看出，当任务数一定时，文中算法的任务完成时间一直保持着一定的优势，在负载均衡标准差方面，一开始就保持着一定优势，随着虚拟机数量的不断增加，文中算法一直稳定在5附近，而GA算法为25左右，Min-Min算法在20左右，且都不稳定.因此，当存在很多云任务时，文中算法会取得更好的效果，这正是实际云环境的特点.

4 结 论

文章针对云环境下任务调度问题，以任务完成时间和虚拟机负载均衡为目标，提出了一种改进遗传算法的云任务调度改进算法.通过虚拟机执行速度的不同，引入虚拟机相对适应度的概念，促使变异操作直接朝更优的方向发展来优化结果.通过仿真实验证明该算法比改进前及Min-Min算法都有更好的效果，应用于云平台中是可行的.文中算法优化目标主要考虑的是影响系统吞吐量的任务集完成时间，并没有考虑到与用户体验密切相关的QoS需求.服务质量QoS是衡量用户对所使用云服务满意程度的标准，含有用户时间需求、性能需求、费用需求和能耗需求等，不同用户的需求各不相同.后续将对如何保证系统吞吐量的同时又能够最大程度的满足用户QoS需求进行研究.

[1]Armbrust M,Fox A,Griffith R,et al.A view of cloud computing[J].Communications of the ACM,2010,53(4):50-58.

[2]Endo P T,Rodrigues M,Goncalves G E,et al.High availability in clouds:systematic review and research challenges[J].Journal of Cloud Computing,2016,5(1):16.

[3]刘鹏.云计算（第二版）[M].北京:电子工业出版社，2011.

[4]Kiselyov O.Scheduling algorithms and NP-complete problems[J].Dr Dobbs Journal,1997,22(2):107-109.

[5]李建峰，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31(1):182-187.

[6]任金霞，何富江.快速降阶匈牙利算法的云计算任务分配模型[J].江西理工大学学报，2014，35(3):63-67.

[7]张春艳，刘清林，孟珂.基于蚁群优化算法的云计算任务分配[J].计算机应用，2012，32(5):1418-1420.

[8]王波，张晓磊.基于粒子群遗传算法的云计算任务调度研究[J].计算机工程与应用，2015，51(6):84-88.

[9]冯小靖，潘郁.云计算环境下的DPSO资源负载均衡算法[J].计算机工程与应用，2013，49(6):105-108.

[10]崔雪娇，曾成，徐占然，等.基于贪心算法的云计算资源调度策略[J].微电子学与计算机，2016，33(6):41-44.

[11]Rodrigo N.Calheiros,Rajiv Ranjan,Anton Beloglazov,et al.CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software:Practice and Experience,2011,41:23-50.