基于资源状态蚁群算法的云计算任务分配

黄 俊，王庆凤，刘志勤，王耀彬

（西南科技大学 计算机科学与技术学院，四川 绵阳621010）

0 引 言

云计算［1－3］是将计算资源进行统一管理统一分配的新型计算模型。根据任务的需求分配计算资源是云计算的关键技术之一。由于任务与资源之间的分配是一个N－P 问题，有较多学者采用蚁群算法或其改进算法进行任务分配。如文献 ［4］提出多态蚁群算法，提高任务处理的效率；文献［6］提出基于任务优先级蚁群算法，减少任务完成时间和任务执行时间；文献 ［7］提出能量感知优化蚁群算法，在保证物理机负载平衡的同时降低电量使用。上述研究在一定程度上改善了云计算资源分配的问题，但云计算是一种云端实时多用户作业，资源随任务分配而变化，现有的研究缺乏对资源状态和任务等待时间的考虑。

针对上述问题，本文通过分析云计算这一新型计算模型中的资源与任务的关系，建立具有资源状态、任务等待时间的云计算任务分配问题模型。基于该模型，利用资源状态修正分配可见度、释放信息素，并以最大虚拟机资源时间耗为路径长度，取代标准蚁群算法的全部虚拟机资源时间消耗为路径长度，形成基于资源状态蚁群算法的任务分配。

与轮循、Min－Min［5］进行对比仿真实验，结果表明，基于资源状态蚁群算法的任务分配能够在任务完成时间、资源消耗及任务等待时间上具有较大的优势。与文献 ［6］Cristian Mateos等人提出的蚁群改进算法比较，本文算法在任务完成时间、算法稳定收敛方面取得了较好表现。

1 任务分配模型建立与分析

根据云计算平台的实际工作场景［2，3］问题描述与建模：如图1所示，一个云平台中存在多个平台的用户，每一个平台的用户可以在云平台中运行多个应用，而每一个应用对应着应用的用户请求的多个任务 （如文件下载、一个在线游戏事件等），并有一定配额的虚拟机，通过这些虚拟机完成多个请求，并返回任务结果。针对前面研究者提出对所有任务执行时间和最小为目标，其忽略了任务的等待时间，提出以下问题模型。

图1 云计算场景

假定有一应用，在当前时刻有m 个任务请求，该应用有n个虚拟机的配额。将m 个任务请求的资源为TASK ＝｛task1，task2，…，taskm｝，n 个虚拟提供的资源为VM ＝｛vm1，vm2，…，vmn｝。m 个任务在n 个虚拟机上执行时间表示为TIME ＝｛time1，time2，…，timem｝，等待时间为W ＝

｛w1，w2，…，wm｝。

2 基于资源状态优化蚁群算法的任务分配

蚁群算法来源于旅行商 （TSP）问题，而云计算中的任务调度并不是一个标准的TSP问题。本文中的任务调度问题具有以下不同点：①有多个执行者 （多虚拟机）同时去执行多个任务；②路径的下节点可见度可能变化，随着任务分配，计算资源发生了改变；③路径长度并不是所有花费之和，而是最大花费的执行者，多个虚拟机同时去完成任务，完成的时间应该是虚拟机最大完成时间，以表示这批任务的完成时间。

云计算的实际场景中，资源的状态随着任务的分配发生了变化，该资源对应其它任务执行时间也随之变化。本文改进蚁群算法根据资源状态进行可见度应进行修正；同时，在更新信息素时，以最大虚拟机资源时间耗为路径长度，取代标准蚁群算法的全部虚拟机资源时间消耗为路径长度。

算法过程：

第1步：初始化。信息素矩阵Pheromone。

第2步：初始化antNum 只蚂蚁 （每只蚂蚁的禁忌表TABU、可搜任务表AllowedTask、虚拟机消耗状态COSTVM、Δτ），对每只蚂蚁进行第2－第4步操作。

第4步：更新禁忌表、可搜任务表、虚拟机消耗状态。设 第3步选择了 （taski，vmj），从AllowedTask 中移除taski，在TABU 中加入taski，costVMj＝costVMj＋etcij。更新bestCostk，更新配对序列List＜（taski，vmj）＞。如果AllowedTask不为空，执行第3 步，否则进行第5步。

第5步：每只蚂蚁各自形成一个解，发现最优解。以bestCost最小为最优解判断尺度

第6步：更新信息素浓度。ρ为挥发因子，Q 为单只蚂蚁的全部信息素

第7步：t＋＋；如果t＜MAX ＿GEN，执行第2 步。得到最优解List ＜（taski，vmj）＞，进行CloudSim 模拟器执行，并统计结果数据。

基于资源状态优化蚁群算法的任务分配流程如图2所示。

图2 算法流程

3 实验设计与分析

为了保证实验的有效性，本文设计了一套实验方案，可为云计算任务资源调度算法提供实验环境。

如图3所示，开发实验数据产生工具，设置虚拟机数、虚拟机计算能力范围、任务数、任务资源需求范围、实验数据组数，进生随机产生相应的数据集文件。由不同算法读取相同数据集文件进行最优解求解，将最优解放入CloudSim［9］进行仿真实验，最后通过CloudSim 相关API进行结果统计。

图3 实验设计

本文实验数据设计见表1，其中每种条件数据为10组。通过多次实验，本文中的基于资源状态的蚁群算法收敛速度很快，实验过程中在10－30次迭代能完成收敛，因此将迭代次数设置为30。根据文献 ［10］的实验认证，本文将蚂蚁数设置为任务的个数。

表1 任务资源分配仿真实验数据设置

由于基于时间共享的任务分配任务不需要等待，相对空间共享的任务分配更为简单，实验就基于空间共享任务进行。通过随机轮循 （RR）调度、最小最小 （Min－Min）调度和基于资源状态的蚁群算法 （SACO）进行调度。根据文献 ［10］的研究，将蚁群算法中的参数设置为：α＝1.0，β＝5.0，ρ＝0.5，Q＝1.0。3种算法的仿真环境、任务、虚拟机等参数均相同。所有实验统计均为每个条件10组数据实验结果的平均。除此之外，直接使用文献 ［6］的实验数据进行对比分析。

任务完成时间，为一批任务全部完成的时间，其中包括了等待时间和执行时间。如图4所示，通过轮循完成任务耗时最长，基于资源状态的蚁群算法进行调度任务完成时间最短。其中BACO 是按基本蚁群算法 （可见度不随任务的分配而改变、以所有虚拟机资源消耗和为蚂蚁路径），其效果会随着任务数量的增加而恶化，因为蚂蚁会往资源丰富的虚拟机移动，但事实上蚂蚁越多，资源会越少。本文的RR 算法是采用最小任务在最大空闲的虚拟机上执行，也考虑资源状态的变化，结果较好，但并不是最优。本文的SACO 算法相对RR 算法提高38.37%±0.93%，相对Min－Min算法提高8.42%±4.276%。

图4 任务完成时间

文献 ［6］的蚁群算法、实验及实验结果与本文较为相似，因此与文献 ［6］的实验结果对比，为了排除实验数据的不同因素，以相对CloudSim 自带随机轮循算法结果的比值进行比较，如图5所示，2条曲线分别代表文献 ［6］中蚁群算法数据完成时间与随机轮循算法完成时间比值，和本文SACO 算法完成时间与随机轮循算法完成时间比值。

图5 算法相对RR 算法的完成时间比

可以发现文献 ［6］的蚁群算法提高比例不稳定，表明其算法容易进入局部最优解，而本文算法提高比例相对很稳定，相对RR 算法的时间比例在60%－65%之间，即随任务数变化，能节约了38.27%±0.971%的时间。而文献［6］的实验数据表明节约时间为33.69%±4.567%，以标准差来衡量算法的稳定性，本文的稳定性是其4.7倍。

平台占用时间，是对一批任务占用资源的全部时间和，可以反应任务对平台资源的消耗。如图6所示，实验结果表明，通过基于资源状态的蚁群算法进行调度任务，完成同一批任务，可以占用更少的资源，进而提高平台的资源利用。本文的SACO 相对RR 算法提高10.85%±1.091%，相比Min－Min算法提高1.27%＋0.768%。

图6 平台时间占用

任务的等待时间，是对用户任务响应的指标。如图7所示，实验统计任务的最大等待时间和平均等待时间，结果表明，基于资源状态的蚁群算法进行调度任务，等待时间更短，能够更好的满足用户需求。在用户任务大最响应时间方面SACO 算法相比RR 算法提高51.92% ±10.861%，相比Min－Min 算法提高5.56%±2.899%。在用户任务平均响应时间方面SACO 算法相比RR 算法提高11.35% ±0.945%，相比 Min－Min 算法提高1.06%±1.46%。

图7 任务等待时间

4 结束语

合理的任务调度，可以提高云计算平台的任务执行速度、资源利用率和用户响应时间。本文通过抽象云计算场景，对云计算模型进行分析与建模，提出基于资源状态优化蚁群算法。该算法根据资源状态释放信息素并更新任务资源配对的可见度，能够较好适应云计算的任务调度问题。通过CloudSim 的仿真实验，该算法相对最近Cristian Mateos提出的蚁群改进算法在任务完成时间、算法稳定收敛方面取得了较好表现，以RR 算法为基准节约了38.27%±0.971%的时间，稳定性是其4.7倍；相比较为流行的最小最小算法在任务完成时间、资源利用率及用户响应时间上均有良好表现。

［1］Mell P，Grance T.The NIST definition of cloud computing（draft）［S］.NIST Special Publication，2011.

［2］IBM，What is cloud ［EB／OL］. ［2013－07－12］.http：／／www.ibm.com／cloud－computing／us／en／what－is－cloud－computing.html.

［3］Wesley Chun，What is cloud computing ［BL］.［2013－07－12］.https：／／developers.google.com／appengine／training／intro／whatiscc.

［4］ZHANG Chunyan，LIU Qinglin，MENG Ke.Task allocation based on ant colony optimization in cloud computing ［J］.Journal of Computer Applications，2012，32 （5）：1418－1420 （in Chinese）.［张春艳，刘清林，孟珂.基于蚁群优化算法的云计算任务分配 ［J］. 计算机应用，2012，32 （5）：1418－1420.］

［5］ZHA Yinghua，YANG Jingli.The application of cloud computing simulation platform CloudSim in research of resource allocation ［J］.Software Guide，2012，11 （11）：57－59 （in Chi－nese）.［查英华，杨静丽.云计算仿真平台CloudSim 在资源分配研究中的应用 ［J］.软件导刊，2012，11 （11）：57－59.］

［6］Cristian Mateos，Elina Pacini，Carlos García Garino.An ACO－inspired algorithm for minimizing weighted flow time in cloud－based parameter sweep experiments ［J］.Advances in Engineering Software，2013，56：38－50.

［7］Feller E，Rilling L，Morin C.Energy－aware ant colony based workload placement in clouds［C］／／Proceedings of the IEEE／ACM 12th International Conference on Grid Computing.IEEE Computer Society，2011：26－33.

［8］Babu LD，Krishna PV.Honey bee behavior inspired load balancing of tasks in cloud computing environments［J］.Applied Soft Computing，2013，13 （5）：2292－2303.

［9］Calheiros RN，Ranjan R，Beloglazov A，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 （1）：23－50.

［10］Dorigo M，Birattari M.Ant colony optimization ［M］.Encyclopedia of Machine Learning.Springer US，2010：36－39.