基于改进蚁群算法的云计算任务调度

张秋明

（玉林师范学院 教育技术中心，广西 玉林537000）

基于改进蚁群算法的云计算任务调度

张秋明

（玉林师范学院 教育技术中心，广西 玉林537000）

利用云中资源进行高效任务调度是保证云计算系统可靠运行的关键问题。提出一种基于改进蚁群优化算法的任务调度方法。算法采用蚂蚁系统的伪随机比例规则进行寻优，防止算法过快收敛到局部最优解，同时结合排序蚂蚁系统和最大最小蚂蚁系统的设计思想完成信息素更新，有效求解优化问题。实验结果显示，该算法具有很好的寻优能力，提高了云资源的利用率。

云计算；蚁群算法；任务调度；资源配置

0　引言

云计算是在分布式计算、网格计算、对等计算之后产生的一种新型计算模型[1]，它真正体现了按需服务的理念。云计算通过整合分布式资源，构建应对多种服务要求的计算平台。而云中具有的资源和待处理的任务都是海量的，如何利用云中资源进行高效的任务调度也就成为云计算系统可靠运行的关键问题。近年来已有学者在云计算调度方面做了大量的研究，如文献[2-5]，这些算法都提高了云计算任务调度的效率，取得了一定的研究成果。

蚁群（Ant Colony，AC）算法是对自然界蚂蚁寻径方式的模拟而得出的一种仿生算法，其中最早的AC算法是蚂蚁系统，在AC算法的基础上发展了许多改进AC算法，如最大最小蚂蚁系统(Max-min Ant System，MMAS)[6]、排序蚂蚁系统(Rank-based Version of Ant System，ASRank)[7]、多群蚂蚁算法（Multi Colony Ant Algorithm）[8]、具有变异特征的蚁群算法（Ant Colony Algorithm with Mutation Features）[9]、基于信息素自适应调整的改进蚁群算法（Improved Ant Colony Algorithm based on Adaptive Adjusting Pheromone）[10]等。AC算法以及其改进算法在求解优化问题上得到了很好的应用，同时在任务调度方面也得到了较多的研究。文献[11-13]分别对蚁群算法进行了改进，并将其应用到敏捷卫星的任务调度上，各有自己的优点与缺点。

针对上述问题，本文基于AC算法在优化求解问题中的优势，提出一种改进AC算法的云计算任务调度方法。为防止优化算法过快收敛，改进算法采用ACS的伪随机比例规则进行寻优，同时将ASRank和MMAS中信息素更新方法进行融合，以完成改进AC算法的信息素更新，有效改善了算法的寻优能力，提高云资源的调度效率。

1　云计算任务调度

与其他已有的网络模式不同，云计算具有其独有的特征。首先云计算将计算和存储能力与单台计算机的原始软件分离，并在用户终端和网络服务中完成这些功能，也就是模型将编程、应用过程和数据存储在网络中，而用户终端仅负责用户交流和获取服务。文献[14]总结云计算的特点为：(1)提供了安全稳定的数据存储中心，用户不用担心数据丢失、软件更新、病毒攻击以及其他事项；(2)对用户设备的基本要求低且方便使用；(3)在不同的地方完成文件的处理，并且能在不同设备上完成文件的共享和应用。

从云计算的特征可以看出，云计算任务调度的本质是将有限的个任务分配给有限的可用资源上，在充分利用云资源基础上使得总的处理时间最短。由于在现实条件下，完成一定的任务需要相应的成本，因此云计算任务调度不仅要以处理时间为衡量标准，还要考虑成本因素，即云计算任务调度是一个时间费用优化问题[4]。

2　改进的蚁群算法

2.1蚁群算法

AC算法是由意大利学者提出的仿生算法，是根据真实世界中蚂蚁寻找食物的行为演变而来。生物学家经过大量研究发现蚂蚁会在经过的道路上释放一种特殊物质，即信息素。信息素可以使在一定范围内的蚂蚁感受到其存在和强度，进而构建它们的行为。蚁群倾向于选择信息素强度大的路径，越多的蚂蚁选择相同的路径，该路径的信息素强度会越大。通过信息素交换信息，蚁群就可以完成积极地信息反馈并找到去往食物的最后路径。一般地，AC算法是一个随机搜索过程，由自适应阶段和合作阶段组成。在自适应阶段，每个候选方法都要根据累积信息自我调整；在合作阶段，所有的候选方法要彼此交换信息，进而寻找出最优方法。

2.2蚁群算法的改进

2.2.1伪随机比例规则寻优

参考蚂蚁系统设计思想，采用伪随机比例规则来实现寻优策略，具体如下：

其中，p0为一个常值且 0≤p0≤1，p为从[0，1]的均匀分布中产生的随机值，Ni代表节点i中的蚂蚁在下一个时刻所能访问的节点的集合，同时Ni中的节点之前没被访问过且访问之后不会违反相应的约束条件。在候选节点选择之前随机产生 p的值。如果 p≤p0，就选择使得τα(i，λ)·ηβ(i，λ)·κγ(i，λ）取最大值的节点为下一时刻的节点；如果 p>p0，蚂蚁就会依概率 P(i，s）随机选择下一时刻的节点。其中P(i，s）的计算形式如下：

其中，τ(i，s)表示第i个与第s个任务之间的信息素强度，η(i，s)为任务执行间隔的影响，κ(i，s）为任务优先级影响，而 α、β、γ则为各个影响因素相应的权重。

2.2.2信息素更新改进

信息素是蚂蚁进行通信的媒介，也是其他蚂蚁进行路径选择的重要依据，因此信息素的更新是AC算法关键问题。本文采用的信息素更新策略分为局部更新和全局更新两方面。在局部更新过程中，如果一只蚂蚁选择了线路ij，其信息素强度可以根据下式进行局部更新：

其中，σ∈(0，1)为调整参数，代表着信息素挥发系数；τ0=1/(nTnn)，Tnn是由最近探索法生成的初始可行方法所产生的访问路径的和。

另一方面，采用ASRank进行信息素的全局更新。在一次迭代过程中，所有路径按照长度进行升序排列，即length1≤length2≤…≤lengthM，其中M为蚂蚁的数量。然后根据路径的长度计算排序路径的权重，长度越短，权重越大。以ω代表全局最优路径的权重，则第r短路径的权重为max{0，ω-r}。当完成一次迭代时，这些路径的信息素值可以根据以下的全局更新规则进行更新：

在基本的AC算法中，只允许全局最优路径进行信息素的更新。而在ASRank中，不同的路径会根据距离被赋予不同的权重，这也就意味着，距离越短，权重越大，在下一次的迭代过程中被选择的概率就越大。然而过多的使用局部最优解会导致信息素的停滞现象，在AC算法中，信息素的值会伴随着局部信息素的增多而减少，进而降低了选择此路径的可能性。MMAS算法对信息素的取值进行了范围限制，保证了每条路径的信息素值都不低于最小信息素值，这样避免了所有蚂蚁选择一条路径的发生，也就避免了信息素的停滞现象。

2.2.3改进蚁群算法流程

本文改进AC算法的流程如图1所示，其过程可概括如下：

(1)H←0，其中H为迭代步数或搜素次数，初始化 τij和 △τij，并将 M个蚂蚁放在N个顶点上；

(2)将蚂蚁的出发点放在当前解集中，按照 2.2.1节中的寻优策略将蚂蚁移至下一位置，同时将下一时刻位置放入当前解集；

(3)计算各蚂蚁的路径长度，并记录当前最优解；

(4)按照2.2.2节中方法对各路径的信息素强度进行更新；

(5)对于各边(i，j)，置 △τij←0，H←H+1；

图1　改进AC算法流程图

(6)如果 H小于预定的迭代次数且没有退化，转至步骤(2)；

(7)输出最优解。

3　仿真实验

为了检验本文改进AC算法在云计算任务调度中的效果，采用仿真实验对其进行验证。采用的仿真环境为2.80 GHz CPU，4 GB内存，500 GB硬盘，Windows XP版本，采用Java语言编程。

任务的处理在虚拟终端上进行，为仿真不同性能的虚拟终端，假设各个虚拟终端的计算能力是随机产生的，取值为[6，10]，同时虚拟终端价格也是随机产生且取值范围为[50，100]。迭代次数取为50，同时在[100，200]范围内随机产生任务长度。为了保证仿真的有效性，进行100次试验，取平均值。

为全面验证算法在云计算任务调度上的优势，分两个方面进行仿真实验：一是保持虚拟终端数量不变的情况下选择不同任务数量，以检测虚拟终端不变下，随着任务数量的增加，改进AC算法性能的好坏；二是任务数量不变情况下选择不同数量的虚拟终端，以检测任务数量不变下，随着虚拟终端的增加，改进AC算法性能的好坏。

在对比算法上选取标准的AC算法，只进行寻优改进的AC算法，只进行信息素更新改进的AC算法和本文的改进AC算法。

3.1任务数量变化的仿真

假设虚拟终端数量为固定数目8个，任务规模从0～100取值，步长为10。仿真结果如图2所示。

从图2可以看出，在虚拟终端数量不变的情况下，随着任务数量的增加，各个算法的最优解值增大。而在不同任务规模下，本文改进AC算法的最优解都要小于标准AC算法、寻优改进的AC算法、信息素更新改进的AC算法。其中寻优改进的AC算法和信息素更新改进的AC算法性能相当，且都优于标准AC算法。

图2　虚拟终端不变任务数量变化条件下各算法的最优解

3.2虚拟终端变化的仿真

假设任务规模固定为50，虚拟终端数量从1～10取值。仿真结果如图3所示。

图3　任务数量不变虚拟终端变化条件下各算法的最优解

从图3可以看出，在任务数量不变的情况下，随着虚拟终端数量的增加，各个算法的最优解值减小。而在不同虚拟终端下，本文改进AC算法的最优解都要小于标准AC算法、寻优改进的AC算法、信息素更新改进的AC算法。其中寻优改进的AC算法和信息素更新该机的AC算法性能相当，且都优于标准AC算法。

本节从两个不同方面的仿真实验验证了本文改进算法在云计算任务调度上的有效性，说明了本文改进AC算法是一种良好的调度方法。

4　结束语

本文针对云计算任务调度问题，提出一种基于改进蚁群算法的任务调度方法。改进AC算法采用AS中的伪随机比例规则设计寻优策略，结合MMAC和ASRank设计信息素更新策略，有效提高了算法的寻优能力，在不同仿真场景下的实验结果验证了算法的有效性。

[1]林闯，苏文博，孟坤，等.云计算安全：架构、机制与模型评价[J].计算机学报，2013，36(9)：1765-1784.

[2]杨镜，吴磊，武德安，等.云平台下动态任务调度人工免疫算法[J].计算机应用，2014，34(2)：351-356.

[3]陈春玲，张瑞霞，曹萌萌.云计算任务调度算法的改进[J].无限互联技术，2014(1)：9-10，20.

[4]李依桐，林燕.基于混合粒子群算法的云计算任务调度研究[J].计算技术与自动化，2014，33(1)：73-77.

[5]董丽丽，黄贲，介军.云计算中基于差分进化算法的任务调度研究[J].计算机工程与应用，2014，50(5)：90-95.

[6]STUTZLE T，HOOS H.MAX-MIN ant system[J].Future Generation Computer Systems，2000，16(8)：889-914.

[7]BULLNHEIMER B，HARTL R F，STRAUSS C.A new rank based version of the ant system:A computational study[J]. Central European Journal for Operation Research and Economics，1999，7(1)：25-28.

[8]MIDDENDORF M，REISCHLE F，SCHMECK H.Multi colony ant algorithm[J].Journal of Heuristics，2002，8(3)：305-320.

[9]WU Q H，ZHANG J H，XU X H.An ant colony algorithm with mutation features[J].Journal of computer research and development，1999，36(10)：1240-1245.

[10]QIN G L，YANG J B.An improved ant colony algorithm based on adaptively adjusting pheromone[J].Information and Control，2002，31(3)：198-201.

[11]郭浩，邱涤珊，伍国华，等.基于改进蚁群算法的敏捷成像卫星任务调度方法[J].系统工程理论与实践，2012，32(11)：2533-2539.

[12]邱涤珊，郭浩，贺川，等.敏捷成像卫星多星密集任务调度方法[J].航空学报，2013，34(4)：882-889.

[13]严珍珍，陈英武，邢立宁.基于改进蚁群算法设计的敏捷卫星调度方法[J].系统工程理论与实践，2014，34(3)：793-801.

[14]LI C L，DENG ZH H.On the value of cloud computing[J]. Library and Information，2009(4)：42-46.

Task scheduling of cloud computing based on improved ant colony algorithm

Zhang Qiuming
(Center of Education Technology，Yulin Normal University，Yulin 537000，China)

Making full use of cloud resources to dispatch tasks efficiently is a key problem to ensure that the cloud computing system reliably runs.A task scheduling method based on improved ant colony optimization algorithm is proposed in this paper.The algorithm is optimized by pseudorandom proportion approach of ant system,to avoid the too fast convergence to local best solution. Meanwhile,the algorithm achieves the pheromone update by the combination of design thought of rank-based version of ant system (ASRank)and max-min ant system(MMAS),and solves the optimization problems effectively.The simulation results show that the algorithm is good in optimization ability,and improves resource utilization.

cloud computing；ant colony algorithm；task scheduling；resource configuration

TP181

A

0258-7998(2015)02-0120-03

10.16157/j.issn.0258-7998.2015.02.029

2014-10-08)

张秋明(1964-)，通信作者，男，硕士，工程师，主要研究方向：计算机网络应用，E-mail：zhangqiuming_2012@126.com。