云环境下基于改进蚁群算法的任务调度
2018-12-20何长杰白治江
何长杰，白治江
(上海海事大学 信息工程学院，上海 201306)
0 引 言
云计算是一种商业计算模型，它将计算任务分配在由大量廉价计算机构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和信息服务[1]。它通过虚拟化技术将软硬件资源形成一个巨大的资源池[2]，当用户需要这些资源时，通过某种调度方式，将资源池中的资源分配给用户任务，云中的资源就像煤气、水和电一样，取用方便，费用低廉。云计算环境下的资源分配实际上根据调度目标将资源分配给云任务[3]，调度目标不同，采取的分配策略也会不同，如以最优跨度、成本最低、服务质量、负载均衡等为调度目标。
目前云计算任务调度是NP完全问题[4]，不少学者提出一些改进的调度算法，如Li Kun等[5]提出了LBACO算法，考虑虚拟机的计算能力、带宽和负载均衡，使得任务执行时间少且负载更加均衡。左利云等[6]提出RCMM调度算法，将任务和资源等级的乘积作为组合值进行Min-Min算法调度，改进算法负载比原始Min-Min更加均衡。张春艳等[7]提出基于分组多态蚁群算法，侦察蚂蚁负责初始化信息素，搜索蚂蚁负责搜索解，使得平均完成时间降低。查英华等[8]提出增强蚁群算法，兼顾任务调度的最短完成时间和负载均衡，对信息素初始化和局部更新，以及节点选择进行改进，减少了算法运行时间，负载更加均衡。王芳等[9]为了解决蚁群算法收敛速度慢和容易陷入局部最优解的缺陷，概率选择时引入混沌扰乱策略，且自适应调整信息素挥发因子，实验表明改进后的算法时间跨度更小。
为了防止蚁群算法陷入局部最优解，文中进行了以下改进:对于没有访问的路径不蒸发信息素，增大其被搜索的概率；奖励局部最优路径及其近邻路径等多条路径，增大了蚁群搜索空间，防止蚁群算法陷入局部最优。
1 云计算任务调度
云计算调度模型如图1所示，分为两级调度，分别是云任务调度和虚拟机调度。其中云任务调度表示在理想或者极优的资源分配情况下，一个Vm应能以共享模式分配给多个终端用户的多个任务。虚拟机调度为Vm寻找合适的Host，再把Vm创建到这个Host上。文中仅仅考虑云任务调度算法。
图1 云计算调度模型
云计算任务调度问题本质是根据某些调度目标将n个任务分配到m个虚拟机上，n通常大于m。使得云平台负载更加均衡，任务完成时间最小，尽可能提高云资源利用率。
任务集合TASK={Task1,Task2,…,Taskn}表示当前任务队列有n个任务，任务指令长度用百万指令(million instructions，MI)表示。
虚拟机集合VM={Vm1,Vm2,…,Vmm}表示云中有m个资源节点。虚拟机处理能力用每秒执行的百万指令数(million instructions per second，MIPS)表示。
TASK到VM的分配关系可以用分配矩阵X表示为：
(1)
(2)
(3)
其中，TaskLengthj表示任务j的指令长度；VmMipsi表示虚拟机i的处理能力。
2 蚁群算法
蚁群算法是Marco Dorigo在1992年提出的一种元启发式仿生算法，模拟蚁群觅食行为过程中发现最短路径的现象。蚂蚁在觅食中释放一种称为信息素(pheromone)的化学物质，蚁群之间通过信息素的浓度变化进行信息交流和相互协作，浓度越高的路径选择的概率越大。虽然每个蚂蚁个体智能有限，但通过群体的搜索、协作和涌现现象可以解决单个个体无法解决的问题。这种方法被很多研究者用于求解大多数NP-Hard优化问题，如旅行商(traveling salesman problem，TSP)、二次分配等组合优化问题[10]。蚁群算法求解TSP的过程描述如下：
Step1：创建antNum只蚂蚁，迭代次数g，初始化信息素矩阵、可访问表、禁忌表以及相关参数。
Step2：随机将蚂蚁分布在n个城市，将初始分配城市节点加入禁忌表Tabuk，第k只蚂蚁从当前城市i选择下一个城市j。概率选择公式如下：
(4)
(5)
Step4：antNum只蚂蚁都搜索完成各自获得一条路径后，对信息素浓度进行更新。信息素更新公式如下：
τij(new)=(1-ρ)τij(old)+Δτij
(6)
(7)
其中，ρ表示信息素的挥发因子；1-ρ表示信息素的残留因子。
Step5：若满足迭代结束条件，则直接打印最优路径结束。否则，重新初始化蚂蚁，跳转到Step2。
3 蚁群算法求解云计算任务调度
将任务到虚拟机的一次分配作为蚂蚁搜索对象[8]，用(Taskj,Vmi)表示一个节点，当所有任务分配给虚拟机之后就形成一系列节点组成的路径。
3.1 启发式因子设置
(8)
(9)
在TSP问题中，dij表示城市i到城市j的距离，而在云计算任务调度问题中，dij表示任务j分配给虚拟机i后的完成时间，包括分配之前虚拟机i已经执行的时间和分配之后任务j在虚拟机i的执行时间。TotalLengthi表示已经分配给虚拟机i的任务指令总长度[11]。etij表示任务j分配给虚拟机i的执行时间，由式3计算可得。
分配完成后，虚拟机i的任务指令总长度需要加上当前分配到的任务j的指令长度，计算公式如下：
TotalLengthi=TotalLengthi+TaskLengthj
(10)
3.2 改进信息素更新规则
经典蚁群算法的信息素更新规则会对全部路径进行信息素挥发，对于蚂蚁未经过的路径，该路径的信息素由于挥发越来越少，趋近于零，导致之后蚂蚁几乎不会选择该路径，降低了蚁群算法的搜索空间[12]。因此文中对信息素更新规则进行改进，迭代过程中，对于没有访问的路径不再挥发信息素。信息素更新公式如下：
τij(new)=
(11)
其中，Δτij表示一次迭代过程中根据各个蚂蚁搜索的路径以及路径的质量进行信息素更新。Δτij=0表明该路径没有信息素更新，亦没有蚂蚁访问，没有访问的路径不再挥发信息素。
3.3 定义问题解
所有蚂蚁遍历完成获得分配方案后，虚拟机i总的执行时间即负载定义为：
(12)
TSP问题中将路径的长度作为解，路径越短，获得的解越好。在云计算任务调度问题中，由于各个虚拟机并行执行，更多地考虑所有任务执行完成的最大时间[13]，因此t次迭代时第k只蚂蚁获得的解定义如下：
Lk(t)=max{Li}
(13)
迭代过程中最优解定义为L*，表示如下：
(14)
3.4 最优解奖励改进
基于精英的蚁群算法对最优路径进行额外奖励，虽然能够加快收敛速度，却容易陷入局部最优解，这是由于精英蚁群算法仅仅奖励局部最优解路径这一条路径，导致这一条路径上的信息素偏高。云计算环境中许多虚拟机的处理能力相当，因此这些虚拟机之间处理相同的任务集所需的执行时间也相当。文中对最优解路径上的Vm*搜索与之处理能力相当的虚拟机，交换两个虚拟机上的任务集得到新的路径，此时的路径定义为近邻路径，对最优路径和近邻路径多条路径进行信息素奖励，有利于发现近邻解，扩大搜索范围。同时给予其他路径很少的奖励，防止最优解的路径与其他路径的信息素差异太大，陷入局部最优。奖励公式如下：
(15)
其中，VmMipsi虚拟机i的处理能力；VmMips*是最优解L*中Taskj分配到的Vm*的处理能力；VmMaxMips是所有虚拟机中处理能力的最大值。
4 实验及结果分析
文中选择墨尔本大学Gridbus项目组提出的云计算仿真软件Cloudsim[14]3.0进行仿真实验，构造蚂蚁类Ant和蚁群类ACO，重载DatacenterBroker类。云仿真器的参数设置如表1所示。
表1 CloudSim中云环境的参数设置
为了保证实验的准确性，将任务数据和虚拟机数据保存在文件中，进行实验时从文件中读取。蚁群算法α值越大，搜索易过早陷入局部最优，β值越大越接近贪婪规则，α一般取值为1，β一般取值为5。蚁群算法参数设置如表2所示。
表2 蚁群参数设置
定义云中资源不平衡程度(degree of imbalance，DI)：
(16)
其中，Lmax是任务分配完成之后集群中最大的虚拟机负载；Lmin是集群中最小的虚拟机负载；Lavg是虚拟机平均负载。DI值越小，集群中的负载就越均衡。
将文中算法和精英蚁群算法进行实验对比。由于蚁群算法的不稳定性，记录十次实验求平均值分别对最大完成时间和不平衡程度两个维度进行比较。
图2 最大完成时间
图2为文中算法和ACO算法在不同任务数下的最大完成时间比较。可以看出，文中算法比ACO算法求得的最大完成时间更小，这是由于新算法对没有访问的路径不再挥发其信息素，增大其被访问的概率，其次奖励了最优路径及其近邻路径等多条路径，同时减小了最优路径与其他路径信息素的差异，扩大了搜索空间，防止蚁群算法陷入局部最优解。
图3为文中算法和ACO算法在不同任务数下的不平衡程度比较。可以看出，文中算法不平衡程度普遍优于ACO算法，表明新算法更加合理有效地使用资源。随着任务数的增加，云中虚拟机负载不平衡程度减小，这是由于任务之间的指令长度相对差异减小，使得虚拟机上的负载差异也减小，因此不平衡程度也随之减小，且随着任务增加不平衡程度下降趋于平缓。
图3 不平衡程度
5 结束语
元启发式算法相比较启发式算法，虽然求解精度高，但运行时间长。基于精英策略的蚁群算法能够加快收敛速度，却容易陷入局部最优。文中对精英蚁群算法进行了改进，首先对迭代过程中没有访问的路径不蒸发信息素，防止该路径信息素越减越少，增大其被访问的概率，扩大蚁群的搜索空间。其次在最优路径奖励时，对最优路径和近邻路径等多条路径进行奖励，增加了奖励路径的数目，扩大了蚁群搜索空间，同时降低最优路径和其他路径的信息素差值，既增强了最优路径又防止蚁群算法陷入局部最优解。实验证明，该算法在最大完成时间和不平衡程度下能求得更优的解，提高了云资源利用率。
