基于改进蚁群优化算法的云计算调度方法∗

王恩重 陶传奇

（1.南京理工大学计算机科学与工程学院 南京 210094）（2.南京航空航天大学计算机科学与技术学院 南京 210016）（3.计算机软件新技术国家重点实验室（南京大学） 南京 210023）

1 引言

随着IT和互联网技术的飞速发展，传统的应用也变得越来越复杂，需要支持更多的用户、更强的计算能力，同时也需要更加的稳定安全，而为了支撑这些不断增长的需求，企业不得不去购买和升级各类硬件设备和软件资源，另外还需要一个完整的运维团队来支持这些设备或软件的正常运作，包括安装、配置、测试、运行、升级以及保证系统的安全等。这会使得企业开销变得非常巨大，并且随着数量或规模的增加费用也会不断提高。这对于大型互联网企业会造成一定压力，而对于中小型企业更是有致命性威胁。大数据时代，数据量呈现爆炸式的增长速度，现有的计算机硬件水平和信息处理能力已经出现瓶颈，云计算的诞生是解决这种难题的“良药”。

自云计算概念被提出到现在，已有10年时间，如今云计算以其可伸缩性、高可靠性、低成本以及按需服务等诸多特点吸引了无数研究人员和企业的关注，成为了当今时代的热门话题。云计算是分布式存储、虚拟化、并行计算等技术的集合体，如同数据库连接池一样，它将云中所有的可用资源整合成为一个庞大的资源库，达到资源随用随取的目的，很好地解决了大数据快速计算和高效存储的问题，同时也有效地避免了PC机和小型数据中心的性能瓶颈。目前云计算已经逐步扩展并慢慢融入到我们的生活中，国外的谷歌、亚马逊［1］、IBM［2］、微软等公司已经率先推广云计算业务，国内也有阿里巴巴、腾讯、百度等大型互联网公司纷纷加入云计算行列，并有许多中小型企业也紧随其后。

云计算的本质是为用户提供快速可靠的服务，用户只需在终端将任务发送到云数据中心，即可使用云平台来完成各种需求，并最终获取处理结果。云数据中心由大量的服务器和网络设备构成，随着用户数量的逐步增多，将会有成千上万的任务等待云来处理，因此设计出高效的云计算调度算法是云计算研究的关键所在。

Agarwal［3］等提出了基于遗传算法的任务调度算法，在缩短任务完成时间方面有一定效果。文献［4］提出基于最短任务延迟时间的改进蚁群算法，在保证调度公平性和效率前提下有效缩短了任务延迟时间。文献［5］以烟花算法作为云计算任务调度算法，在任务执行时间和负载均衡两个方面做优化，相对于粒子群算法和遗传算法有较好的效果。文献［6］通过改进蚁群算法，考虑虚拟机计算能力、网络带宽等因素，在负载均衡和任务执行时间上有一定提升。Wang［7］等基于云计算和自适应遗传算法的特性，提出了基于时间跨度和负载均衡的双适应遗传算法，采用贪心算法对种群进行初始化，引入方差来描述节点间的负载密集度和多适应函数的权重。该算法相比于自适应遗传算法，有更好的负载均衡度和最大完工时间。Sheng［8］等针对任提出了一种基于模板的遗传算法结合用户QoS约束的任务调度方法，根据处理器的CPU、带宽等因素计算出应该分配给每个处理器的任务最大尺寸，以此作为模板，将任务分割为多个子集并通过遗传算法将这些子集合理分配到每个处理器。该算法可以有效缩短任务的最大完工时间。

本文通过对云计算任务调度中常用的蚁群优化算法进行分析，总结算法中的不足，分别在信息素更新和信息素挥发两个方面对算法进行了改进，并通过实验对算法进行了验证。

2 云计算任务调度

云计算系统中的节点存在复杂性和异构性等特点，随着用户数量的增加，云计算任务队列中的用户任务急剧增加，如何高效地进行任务调度，提高任务执行效率和资源利用率是云计算研究的重中之重。

针对云计算中庞大的任务量，任务调度一般会对任务进行切分，首先将用户提交的任务集合划分为多个子任务，然后根据每个子任务的不同，并考虑虚拟资源节点的使用情况，合理进行任务和虚拟资源的映射。该问题可以描述为：按照一定的策略将m任务分配到n异构的虚拟资源节点上（n＜m），用Task={T1，T2，…Tm}表示所有待执行子任务的集合，用VMN={V1，V2，…Vn}表示虚拟资源节点的集合，限制一个子任务只能在一个虚拟资源节点上运行，则任务和虚拟资源节点的映射关系如式（1）所示：

其中TmVn表示子任务和虚拟机的对应关系。任务调度最终将达到平均执行时间最小、资源利用充分、服务质量良好等目的。云计算任务调度原理图如图1所示。

图1 云计算任务调度原理图

3 算法描述

传统的任务调度算法包括FCFS（First Come First Served）算法，RR（Round-Robin）算法［9］，SJF（Shortest Job First）算法，Max-min算法［10］，Min-min算法［11］等。云计算资源调度问题是一个NP完全问题，启发式任务调度算法相比于基本的任务调度算法有更大的优势。常见的启发式任务调度算法有遗传算法［12］、模拟退火算法［13］、蚁群算法［14］和粒子群算法［15］等。

蚁群算法是由意大利学者M.Dorigo等于20世纪90年代模拟真实蚂蚁的觅食行为过程而提出的一种启发式仿生优化算法［16］。目前，它已被广泛用于解决大多数NP类问题的优化求解，如旅行商问题、图像着色、车辆调度、网络路由、多重背包等静态组合优化和动态组合优化问题［17］。在后续的算法演变中，为了更真实地模拟蚂蚁觅食的过程，出现了蚁群优化算法。本文的算法改进主要针对蚁群优化算法。

3.1 蚁群优化算法模型

假设在云计算环境中，现有n个虚拟机等待执行任务，有m个任务等待处理，有x只蚂蚁，蚂蚁在觅食的过程中会在路径上留下信息素，下一只蚂蚁觅食时会根据信息素浓度选择路径，路径选择的概率公式如下所示：

其中ηij表示子任务i选择虚拟机j时的启发因子，它的值定义为表示第j个任务在第i个虚拟机上的执行时间和任务传输时间的和，即，其中TLi表示第i台虚拟机上的总任务量，MIMPSi表示第i台虚拟机对任务的处理速度，TSj表示传递到第i台虚拟机的任务j的任务量，BWi表示第i台虚拟机的带宽。τij表示任务j选择虚拟机i的信息素，α表示信息素启发系数，代表路径上信息素的影响程度，α越大，则对蚂蚁选择路径的影响越大。β表示期望启发系数，代表期望对路径选择的作用。另外，使用tabu表示禁忌表，蚂蚁走过的路径将被加入禁忌表，防止路径重复。allowedk表示蚂蚁可以选择的下一个虚拟机，也即除禁忌表以外的其他路径。

蚂蚁在寻找最优路径时，伴随着信息素浓度的改变，公式如下：

其中，Δτij(t)表示所有蚂蚁信息素的增量之和，Δτikj(t)表示第k只蚂蚁在经过路径（i，j）时所产生的信息素，Q为算法引入的系数，Lk表示第k只蚂蚁所走过的路程，ρ为信息素挥发系数，它的值介于0和1之间，它的作用是为了防止算法陷入局部最优解。

3.2 改进的蚁群优化算法

3.2.1 信息素更新方式的改进

蚁群算法在搜索最有路径时会出现收敛速度慢，搜索效率低的问题。本文针对这个问题，在蚁群算法的信息素更新公式中引入奖惩系数，当蚂蚁在行进的过程中如果发现了最优（即最短）路径，则立即根据奖惩系数给当前路径予以“奖励”，即对信息素增加相应的值，从而加强该路径的信息素浓度。如果当前路径比上一次的路径更长，则根据奖惩系数对当前路径进行“惩罚”，即将信息素减去相应的值来削弱改路径的信息素浓度。在当前蚂蚁的整个搜索过程中，通过对比，找出长度最长的路径（即最差解），对之进行“严惩”，即根据奖惩系数将最差路径的信息素减去更大的值，在最大程度上减少其对蚂蚁选择路径的干扰。

其中ω为引入的奖惩系数，Lcur为当前路径的总长度，Llast为上一次的路径的总长度。当出现最优路径时，对当前信息素浓度增加作为奖励，当出现相对较差路径时，则对当前信息素浓度减去作为惩罚，当出现最差路径时，则对当前信息素浓度减去作为严惩。

3.2.2 信息素挥发系数的改进

蚁群算法中，信息素挥发系数ρ对算法的搜索性能有较大影响，ρ值越大，全局搜索能力将越差；ρ值越小，则局部搜索能力越差，因此合理的处理ρ值，会直接影响到搜索的结果，使用 ρ(t+1)表示更新后的信息素挥发系数，本文采用的ρ值更新公式如下：

其中gen表示算法迭代到第gen代，μ表示比例系数，为固定常数，ρmin为 ρ值得最小临界值。余弦函数在0～之间的曲线图如图2所示。

图2 余弦函数在0～之间的曲线图

算法中通过将算法迭代的代数（0，gen］按比例映射到（0，］之间，通过上述方式，将 ρ值以余弦函数递减方式更新，从而达到兼顾局部搜索和全局搜索的目的。

4 改进蚁群优化算法求解步骤

1）对算法进行初始化；

2）将x只蚂蚁随机分配到相应的虚拟机上；

3）对每只蚂蚁移动到下一个节点的概率Pikj进行计算，然后将蚂蚁移动到计算结果指示的节点上；

4）当蚂蚁移动到新的节点上后，更新其经过路径的信息素，并修改禁忌表；

5）重复执行步骤2），3），4），直到整个蚁群中的每个蚂蚁都找到一个可行路径为止；

6）对比所有可行路径，通过式（4）对当前最优路径进行“奖励”，对最差路径进行“严惩”，对比上一个路径长的路径进行“轻罚”；

7）对所有路径上的信息素进行全局更新；

8）如果迭代次数达到预设迭代次数，则终止搜索，得出最优解。

算法的伪代码如下：

Begin

初始化算法参数、任务集合T、虚拟资源节点集合V、蚂蚁数量X、最大迭代次数gen；

将X只蚂蚁随机分布到虚拟资源节点集合V上，并对每只蚂蚁的禁忌表tabu、各路径信息素浓度进行初始化；

While（达到迭代次数）do

For each蚂蚁do

While（当前蚂蚁找到可行路径）do

根据式（2）计算概率来选择下一个资源节点执行任务；

当蚂蚁移动到新的节点上后，更新其经过路径的信息素，并修改禁忌表；

当蚂蚁找到可行路径，记录路径总长度。

End while

对比可行路径，记录最优和最差路径，通过式（4）对当前最优路径进行“奖励”，对最差路径进行“严惩”，对比上一个路径长的路径进行“轻罚”；

更新最优路径中任务和虚拟节点的对应关系；End for

通过式（3）来更新所有路径的信息素浓度；

重新随机选择蚂蚁的位置；

End while

给出最优路径，并记录负载均衡度值；

End

5 实验验证与分析

本文使用Cloudsim进行模拟实验验证改进蚁群算法（MACO）在云移动应用测试任务调度方面的可行性。实验中使用的硬件环境是三星笔记本电脑，具体配置为Intel（R）Core（TM）i5-7300HQ CPU@2.5GHz，8G内存，500G硬盘，Windows10操作系统，使用Intellij Idea搭建CloudSim运行环境。CloudSim的执行步骤如下：

1）对CloudSim进行初始化；

2）创建数据中心；

3）创建DatacenterBroker，用于协调和分配资源；

4）创建虚拟机；

5）将虚拟机添加到虚拟机列表中，同时将虚拟机列表提交到DatacenterBroker；

6）创建云任务集合；

7）将云任务（Cloudlet）添加到云任务集合中，并提交到DatacenterBroker；

8）开始仿真，仿真结束后打印结果。

5.1 实验参数设置

在实验中设置虚拟机的个数为20个，任务个数分别设置为50，100，150，200，250，300个，蚂蚁数为20个，迭代次数为100次。文中对蚁群算法的参数取值如表1所示。

5.2 实验结果及分析

根据表1设置的算法参数进行实验，首先将本文的改进蚁群算法（MACO）同传统的蚁群优化算法（ACO）进行实验比较，两个算法分别执行10次，对所得结果取平均值，对比图如图2所示。

图3 MACO，ACO算法任务执行时间对比

从图3中可以看出，当任务量比较小时改进蚁群算法（MACO）和原始蚁群优化算法（ACO）的任务执行时间相差在3s左右，随着任务量的逐步增大，改进的蚁群算法在任务执行时间上的优势更加明显，当任务量达到300个时，两种算法的任务执行时间相差10s多，因此相比之下MACO算法在云测试调度中有更高效率。

相同的实验环境，将改进的蚁群算法同先来先服务算法（FCFS）和Max-min算法进行对比，同样每个算法各执行10次，对得到的结果取平均值，所得结果如如图4所示。

由图3可得，本文的改进蚁群优化算法（MA⁃CO）在任务执行时间上要优于FCFS算法和Max-min算法。由实验数据可得，当任务量为100时，MACO算法的任务执行时间相较于FCFS算法和Max-min算法分别少41s和19s，当任务量增大至300个时，MACO算法的任务执行时间相较于FCFS算法和Max-min算法分别少305s和220s，因此MACO算法的性能要远优于FCFS算法和Max-min算法。

图4 MACO，FCFS，Max-min算法任务执行时间对比

图5 算法负载均衡度比较

图5 显示了MACO、ACO、FCFS和Max-min算法的负载均衡度对比情况，由图可得，MACO算法相对于FCFS算法和Max-min算法，在实现负载均衡上有较为明显的优势，而相对与ACO算法，在保证负载均衡度的前提下可以有效降低任务执行时间，因而MACO算法总体上更具有优势。

综合以上实验可知本文的改进蚁群算法在降低总任务执行时间和实现负载均衡方面都有较好的效果，因而证明了本文算法的可行性。

6 结语

本文介绍了云计算技术特点和现有工作，并对云计算任务调度远离进行了总结，同时提出了一种基于改进蚁群优化算法的云计算任务调度方法。该算法从蚁群算法的信息素更新和信息素挥发两个方面进行改进，并使用CloudSim进行了仿真实验，分别同FCFS、ACO和Max-min算法进行了对比，最终验证了本文调度方法的可行性。将来的工作将进行算法的进一步优化和提高资源利用率，同时也会在保证QoS和降低云数据中心能耗等方面进行研究。