云计算中基于cloudsim的蚁群调度算法研究

张翰林　谢晓燕

摘要：介绍了云计算仿真工具cloudsim，在描述其架构的基础上，实现了cloudsim模拟云环境下调度策略的过程。引入蚁群算法，并基于蚁群算法实现了对cloudsim中调度策略的拓展，并与轮循、贪心等传统代数算法进行对比分析测试。结果表明，蚁群算法在应对云计算中海量任务和数据处理时，由于传统代数算法。

关键词：云计算，cloudsim，蚁群算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）03-0219-02

云计算按照服务类型，大致可以分为三类：将基础设置作为服务Iaas、将平台作为服务paas、将软件作为服务saas。然而，不管何种类型的云计算服务，都有不同的、负责的组件，配置环境和部署条件的要求，因此，在异构真实的云环境下，对云端调度分配策略的优劣的评价，以及由调度策略所带来的云端设备的复合、节能、系统规模性能进行量化、评价是非常不易的。所以，本文引入云计算仿真工具Cloudsim，构建一个云环境下的分布式系统模拟器来实现云计算试验的模拟。

与此同时，目前广泛应用于云计算的如先到先服务FCFS算法、Greedy贪心算法[2]等，由于算法本身的特点，均是传统代数算法静态建模完成的，并不能针对网络中各种不确定变化做出对应的调整。而蚁群优化算法作为一种智能算法，在经过多次迭代后，任务必然能分配给一个合理的虚拟机。因此，本文在介绍Cloudsim架构、工作原理的同时，通过cloudsim搭建了一个云计算平台，并在此平台下，对FCFS算法、Greedy贪心算法以及蚁群优化算法进行的对比测试和分析。结果证明蚁群优化算法对于网络中突发情况的应对是较优的。

1 cloudsim介绍

1.1 cloudsim体系结构

Cloudsim是澳大利亚墨尔本大学Rajkumar Buyya教授领导团队开发的云计算仿真器，是一个通用的、可拓展的支持建模和模拟的仿真框架，并能进行云计算基础设施和管理服务的实验。其体系结构[1]如图：

1.2 cloudsim技术实现

由上图的体系结构图可知，开发人员主要通过cloudsim的最高层用户代码层来实现仿真模拟。通过对该层提供的一些基本实体（如主机、虚拟机、应用、用户数量、应用类型等）的拓展，从而达到（1）建立应用配置请求和任务负载分配请求（2）通过模拟出的云场景，测试自定义配置运行的鲁棒性（3）基于云平台扩展实现自定的调度策略。

Cloudsim是开源的，其用户代码层为开发人员提供了一系列可供拓展的实力和方法，通过拓展这些接口来实现用户自己的调度或分配策略，进行相关科研测试。本文主要进行调度策略的研究，故需要对DatacenterBroker类进行拓展，实现自定义的调度策略，完成对算法的模拟并进行测试和试验分析。

具体的仿真步骤如下：（1）初始化cloudsim包，主要是在其他实体创建前对cloudsim的参数包括日期、用户数量、跟踪日志等进行初始化。

（2）创建数据中心，是在虚拟机的生命周期内负责管理虚拟机的一组主机。通过调用API函数，完成创建数据中心的工作。

（3）创建数据中心代理，负责在云计算中，根据用户的Qos要求以及现有云资源协调用户和服务供应商并部署服务。

（4）创建虚拟机，并对虚拟机的参数进行设置，并提交给任务代理。

（5）创建云任务，生成指定参数的云任务。

（6）调用自定义的任务调度策略，将云任务分配到虚拟机

（7）启动仿真，执行整个仿真流程。

（8）统计试验结果。

2.1 蚁群算法的原理

觅食原则：每只蚂蚁能够在感知的环境里寻找食物，如果发现食物则直接向该方向前进；如果没有，则检查感知环境内的食物信息素，向着信息素浓度高的地方走去。同理，寻找蚁穴的方式是感知环境内的蚁穴信息素。

前进原则：每只蚂蚁都会向着信息素浓度高的方向前进，如果在感知范围内没有相关的信息素提示，则会依照原来行进的方向继续走下去。此外，蚂蚁能够识别刚刚走过的位置，防止蚂蚁原地不动。

躲避障碍原则：蚂蚁在觅食过程中，如果遇到障碍物，会随机选择一个方向继续行进；当然，如果有信息素提示，会按照觅食原则前进。

依据以上蚁群算法的原则，蚂蚁的个体之间虽然没有直接关联，但蚂蚁同蚂蚁之间通过信息素进行信息的交互传递。在觅食过程中，会依据之前经过的蚂蚁所留下的信息素来选择它们要走的路径。所以，大量蚂蚁组成的群体行为实质上形成了一种学习信息的反馈现象，这也就是蚁群算法的一大特点----正反馈机制。根据这一特点，通过模仿蚂蚁群体的行为，实现最优。整个过程如图2所示：

2.2 算法流程

步骤1：任务开始；

步骤2：任务T1、T2、…、Tn参数，并进行任务分类；

步骤3：利用蚁群算法进行资源分配；

步骤4：所有任务是否执行成功？若为否，返回步骤3，若为是，执行步骤5；

步骤5：释放占用资源

步骤6：任务结束

3仿真及结果分析

本文使用Cloudsim3.0进行仿真实验，通过重写DataCenterBroker类、Cloudlet类对cloudsim进行拓展，分别编写了Greedy贪心算法和ACO蚁群算法，并将这两种算法和Cloudsim自带的RR轮循算法进行对比。

仿真说明：

一、对于虚拟机的运算速度和云任务的长度，取值大量的过高或过低都不符合实际情况，所以为了实验的有效性，依照高斯分布在设定的长度区间内随机产生虚拟机的运算速度和云任务长度。

二、虚拟机粒度最小化，设定单个虚拟机同一时间段内只具有处理单个任务的能力，对于那些性能较好具有并发计算能力的虚拟机，根据它的运算能力将其划分为多个虚拟机。

三、对于等量的云任务，调度策略完成任务时间越短则认为该策略执行效率越高，由于云计算中的各个虚拟机计算资源间是并发处理子任务序列的，所以完成所有子任务所需的执行时间是各虚拟机完成子任务时间集合中的最大值，故采用MCT作为算法的评价标准。

实验结果如图3所示。

由图3可以看出：Cloudsim自带的RR算法的MCT是最大的，这主要是因为该算法采用的是简单的轮循，虽然算法简单，但却并未进行任何优化，自然它耗费的时间就比较多。图中数据还可以看出，当任务数在小于50的范围内，ACO蚁群算法并不如Greedy贪心算法用时少，主要原因是蚁群算法的性质适合在训练集庞大，训练时间较长的情况下进行，由于具有迭代学习的过程，其时间复杂度相对Greedy算法较高。但也正是由于该原因，当任务数大于100后，由于ACO迭代学习的次数增加，所以能针对网络环境中突发的各种情况进行应对，因此得到的结果也更准确，这一点是Greedy算法所不具备的。

在云计算环境中的任务分配问题中，除了要考虑直接影响用户满意度的任务完成时间之外还应充分考虑系统的负载平衡性，图4表示了当任务数为200的时候，各虚拟机的负载对比：

从图中可以看出，由于RR算法是按照顺序分配的原则进行资源调度的，所以虚拟机的负载最不平衡；Greedy在设计时由于并未考虑的网络中突发的各种情况，所以会当任务数较多时，会出现大量的调度失败以及重调度，所以虽然负载均衡程度由于RR算法，但是也存在不均衡的缺点；而蚁群算法通过利用自身不断迭代学习的特性，实现了虚拟机的负载相对均衡。

4总结

由于云计算环境的复杂性、异构性和不确定性，对资源分配的调度分配策略和负载均衡的要求也不断提高。本文通过对蚁群算法特性的研究，利用Cloudsim云仿真工具实现了蚁群算法在云环境中资源分配调度策略的实现。

实验结果表明，ACO蚁群算法在应对海量任务和数据处理的时候，无论是MCT任务最大完成时间还是负载均衡性能都由于传统RR伦循算法和Greedy贪心算法。后续将继续考察诸如云平台中数据迁移的开销、引入安全性约束条件、服务间资源资源共享等问题，这些都需要将现有的ACO蚁群算法进一步改进与完善。

参考文献：

[1] 刘鹏.云计算[M].2版.北京： 电子工业出版社，2011.

[2] 田文洪，赵勇.云计算资源调度管理[M].国防工业出版社，2011.

[3] 王永贵，韩瑞莲.基于改进蚁群算法的云环境任务调度研究[J].计算机测量与控制，2011，19（5）：1203-1204.

[4] 倪庆剑，邢汉承，张志政，等.蚁群算法及其应用研究进展[J].计算机应用与软件，2008（8）：12-16.