云计算资源调度策略中最小资源矩阵应用的研究

聂清彬 蔡婷 曹耀钦

摘 要： 传统的蚁群算法（ACO）在云计算资源调度的应用中，存在一些资源节点无法满足任务运行所需的硬件配置条件，从而在任务调度算法中造成了大量的浪费以及整体资源调度效率低下等问题。据此提出一种基于最小资源矩阵（ACO?MRM）的改进蚁群算法，抛弃大量不满足任务运行条件的资源节点，减少大量对无效资源节点的计算，加速算法收敛。仿真实验表明，改进的蚁群算法不仅能够提高云计算调度的有效性，而且能缩短任务执行时间和减少运行成本来获取全局最优调度方案。

关键词： 云计算； 蚁群算法； 任务调度； 最小资源矩阵

中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2016）05?0010?04

0 引 言

云计算机是由并行计算，网络计算和分布式计算发展而来的一种新型计算模式。它把云计算中各种资源通过虚拟化技术进行统一的分配和管理，并对外提供服务，形成以用户为中心，实行“按需使用，按量付费”的商业服务模式。基于该商业模式，用户必然关心任务的执行成本以及所花的时间，因此必须要对云中的资源进行合理的分配，最大化的提高资源利用率；用户提交的任务执行成本低，执行的时间短同时让整个系统的负载始终处于一个相对均衡的水平是需要解决的难题。

目前，基于云计算的资源调度算法很多，文献[1]提出了基于改进的TC_LABCO算法，优化了任务执行的时间和成本，在这些改进的蚁群算法调度策略中，任务调度就是在资源和任务之间建立起一个映射关系的过程，让任务合理地分配到资源上来达到优化的目的；但是有一点因为每个任务运行所要求的硬件资源不一致，并非每个资源都能满足每个任务的要求，有的资源节点由于剩余的CPU处理能力不足，无法提供完成任务所需要的最低配置。然而以往的资源调度策略算法依然要对其预测计算，这样就造成了大量的、无效和重复的搜素计算，浪费了时间和资源，降低了整个系统的效率。因此本文以目前相对成熟并被广泛应用的蚁群算法作为基础，结合资源矩阵特点，提出最小资源矩阵算法（ACO?MRM）对目前的蚁群算法进行改进。通过实验证明，改进以后的蚁群算法不仅能节约大量的调度时间，同时降低了任务执行的成本。

1 蚁群算法的基本原理

蚁群算法（Ant Colony Optimization，ACO）是由Dorigo Macro在1992年在其发表的博士论文中提出的一种模拟蚂蚁群体在通过寻找食物过程中去发现路径行为的算法，蚂蚁在觅食过程中，当一只蚂蚁找到食物后，就会在它经过的路径环境中释放一些挥发性的分泌物，称之为信息素，蚂蚁在觅食过程中主要是根据所处的环境中的信息素决定其前进的方向，那么在较短的路径上的信息素的数量就会比较多，这样蚂蚁选择的概率自然就更大，随着最短路径上的信息素的数量越来越多，最终蚂蚁会选择最短的路径。常见的旅行商算法就是通过模拟蚁群算法来获取全局最优解的。

5 算法流程

（1） 初始化云资源中所有虚拟机的信息素的值。

（2） 将n个任务随机地放在m个节点上，也就是把蚂蚁随机地分派到各个虚拟机上，构造资源任务矩阵式（6），在该资源矩阵中，资源与任务形成映射关系，如果该对应的虚拟机无法满足对应任务运行最低要求如式（4），那么将矩阵中[xmn]的值赋给启发因子[η=0，]则说明不会选中该虚拟机来执行该任务；如果对某一个任务，虚拟机节点能够满足任务运行的最低要求，如式（5），那么将[xmn]值赋给启发因子[η=1]，通过该方式，可以为任务[Tj]挑选出那些有能力执行的虚拟机。

（3） 每只蚂蚁根据选择下一跳的式（1）来为下一个子任务选择全局最优的资源节点。

（4） 当某只蚂蚁结束它的路径遍历任务后，通过文献[1]中的TC_LABCO算法找到一种基于时间?成本最优的资源节点后，所有资源节点按照式（9）进行局部更新。

（5） 当所有蚂蚁都完成了路径遍历任务，执行第（6）步，并且找出这次遍历中的最优路径，然后对路径上的所有资源节点进行全局信息素更新，否则的话跳到第（3）步。

（6） 迭代次数[Nc]累加1，统计出最优的方案，保存。

（7） 如果[Nc>Ncmax]（[Ncmax]为最大迭代次数）则算法停止优化，并把结果输出；否则，跳转到步骤（2）继续执行，直到算法停止。

6 实验仿真以及结果分析

为了验证最小资源矩阵以及时间成本控制算法的有效性，通过云仿真工具CloudsSim进行试验测试，在试验中，设置10个虚拟机，迭代次数设置为100，信息素初始值为1，设置任务数从50，100，150，200依次递增，将本文改进蚁群算法和传统的CAO算法以及文献[1]中提出的基于改进的TC_LABCO算法策略进行对比，如图1，图2所示。

从图1可以看出，相比较而言，随着任务数的增加，加入最小资源矩阵算法以后的蚁群算法收敛速度明显比传统的蚁群算法更快，改进以后的蚁群算法在同等条件下执行同样的任务执行时间更短。从图2可以看出，在同等条件下，改进算法执行的费用更低。实验表明，在原始的蚁群算法中，存在大量的无效搜素，导致搜索任务的时间更短，而经过最小资源矩阵改进以后的蚁群算法适应度最小。

7 结 语

本文主要研究了基于蚁群算法在云计算资源调度中的运用，发现以往的蚁群调度算法在资源搜索过程中存在大量的不能满足任务运行的无效资源，从而浪费了大量的时间和成本，使得在云计算环境中任务调度算法效率不高，因此提出了最小资源矩阵算法（ACO?MRM），该算法在适应云计算资源调度算法的前提下，排除了不能满足任务运行的无效资源，使得能够参与运算的都是有效资源，这样的结果使得迭代次数更优，同时具有收敛更快的优势，并使用仿真软件验证了最小资源矩阵算法的有效性。实践证明通过加入该算法，可以使得执行的时间缩短，成本降低以及资源节点负载更均衡，在未来的研究中，还将进一步挖掘加强蚂蚁之间的交流，同时考虑用户的QoS需求，最大限度地提高云计算机中资源调度的合理性和高效性。

参考文献

[1] 李坤.云环境下的任务调度算法研究与实现[D].长春：吉林大学，2012.

[2] 刘万军，张孟华，郭文越.基于MPSO算法的云计算资源调度策略[J].计算机工程，2011，37（11）：43?44.

[3] 张春艳，刘清林，孟珂.基于蚁群优化算法的云计算任务分配[J].计算机应用，2012，32（5）：1418?1420.

[4] 王登科.云计算任务调度算法的研究与实现[D].兰州：西北师范大学，2013.

[5] 姜华杰.基于QoS的云计算资源分配算法[D].太原：太原理工大学，2012.

[6] 王娟，李飞，张路桥.限制解空间的PSO云存储任务调度算法[J].计算机应用研究，2013，30（1）：127?130.

[7] DORIGO M， CARO G D. The ant colony optimization meta?heuristic [J]. New ideas in optimization， 1999， 28（3）： 11?32.

[8] KUN Li， XU Gaochao， ZHAO Guangyu， et al. Cloud task scheduling based on load balancing ant colony optimization [C]// Proceedings of 2011 Sixth China Grid Conference on Annual. Liaoning： IEEE， 2011： 3?9.

[9] DORIGO M. Optimization， learning and natural algorithms [D]. Milano： Politecnico Di Milano， 1992.

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

[11] 吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法[J].计算机研究与发展，1999，36（10）：1240?1245.

[12] 李建峰，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31（1）：184?186.