ACOCS：一种云环境下资源调度混合算法

2016-01-08黎煌达,程良伦

计算机工程与科学 2015年6期

ACOCS：一种云环境下资源调度混合算法*

黎煌达,程良伦

(广东工业大学计算机学院,广东广州 510006)

摘要：蚁群算法在优化组合问题中有着重要的意义，传统的蚁群调度算法搜索速度慢、容易陷入局部最优。针对这种情况，结合布谷鸟搜索算法，提出一种基于蚁群算法与布谷鸟搜索算法的混合算法(ACOCS)，用于云环境下的资源调度。该方法有效保留了蚁群算法求解精度高和鲁棒性的特性，并融入了布谷鸟搜索具有快速全局搜索能力的优势。仿真实验结果表明，提出的ACOCS调度算法有效减少了调度所需的响应时间，也在一定程度上提高了系统资源利用率。

关键词：调度；蚁群算法；布谷鸟搜索

中图分类号：TP301.6 文献标志码：A

doi:10.3969/j.issn.1007-130X.2015.06.003

收稿日期：*2014-04-25;修回日期：2014-06-11

基金项目：国家自然科学基金重点资助项目(U2012A002D01)通信地址：510006 广东省广州市广东工业大学计算机学院

作者简介:

Address:Faculty of Computer,Guangdong University of Technology,Guangzhou 510006,Guangdong,P.R.China

ACOCS:A hybrid resource scheduling algorithm in cloud environment

LI Huang-da,CHENG Liang-lun

(Faculty of Computer,Guangdong University of Technology,Guangzhou 510006,China)

Abstract:The ant colony algorithm has great significance in solving composition optimization problems. However, the traditional ant colony scheduling algorithm has some drawbacks such as slow searching speed and easy to fall into local optimum. In view of this situation, combining the ant colony algorithm with the cuckoo search algorithm, we propose a hybrid algorithm (ACOCS) for resource scheduling in cloud environment. This method not only effectively preserves the high accuracy and robustness of the ant colony algorithm , but also integrates the rapid global search capability feature of the cuckoo search algorithm . Simulation results show that the proposed ACOCS scheduling strategy is better than the ant colony algorithm. It not only reduces the response time required for effective scheduling, but also improves the system resource utilization to some extent.

Key words:scheduling;ant colony algorithm;cuckoo search

1引言

云计算是当下一个非常热门的课题，它的思想是把许多有计算能力的设备互联起来，一方面有利于资源的全局共享，另一方面也有效地利用闲置的计算资源。也就是说，其目的是通过架构下一代数据中心作为虚拟服务来增强服务功能，使用户从世界上任何角落都能够获得和部署应用程序，对于满足用户的服务质量的要求具有成本优势[1]。这种模式也顺应了大数据时代的发展，把数据进行分布式的统一管理，减轻了终端的负荷，减少了服务对硬件的依赖。这种方式使得用户一旦能够访问云服务，则可以轻松地获取所需的资源，而且这种收费模式按照所需计算，其概念就和我们的家庭水电的收费一样，这种概念一旦实现，必然会极大地改善我们的生活水平，因此研究这样一个方向是极具意义的。

作为一种新型的计算模式，云计算的资源动态分布，异构多样，这使得它的任务调度策略较为复杂，这也成为了云计算研究中的一大热点，如何有效地让用户任务与当前可用资源进行动态分配和合理调度，提供高质量服务的同时，还综合考虑到可扩展性、执行效率和均衡负载等因素。因此，合理高效地在云环境下进行任务调度是一个非常复杂的问题，也成为了一个重要的课题，目前已经吸引众多学者投入精力去研究。按照调度问题不同，可以把现有的资源调度策略分为两大类：第一类是根据资源异构及资源任务的动态变化提出自适应的调度算法。第二类是将启发式算法运用于资源调度的研究中。如今在这一块的研究中已经取得了一系列的工作成果。文献[2]提出了一种动态资源分配的方法，它考虑了任务请求的到达和销毁时间，并且可以预测系统的计算能力和激活时间。文献[3]提出了一种基于Agent的调度方法，它利用服务代理机制使得用户任务请求间进行有效通信，实现资源的最大化利用。文献[4]提出一种能量感知任务融合技术，以优化云数据中心虚拟集群的能量消耗，任务融合是一种最大化利用资源的方式，可以更好地利用资源并合理地使用IT服务。文献[5]提出了一个基于截止期、可靠性、资源感知的分布式调度系统，此调度系统综合考虑了真实网络拓扑和通信模型，该分布式调度系统使得在低成本条件下的大规模科学计算成为可能。文献[6]提出一种基于遗传-蚁群算法的任务调度策略，集成了这两种算法的双重优点，通过实验证明在大规模任务调度环境下的效率优势。

上述的研究都各有侧重点，也有着不足，但是都给我们一个思路去思考调度问题。文本主要从节约调度时间和功耗的角度出发，通过研究当前的启发式算法来设计高效的调度混合算法，主要的思路是通过蚁群算法和布谷鸟搜索算法的有效融合，提高算法的全局搜索能力，改善算法的收敛速度。并通过实验分析来说明所提出的算法能够在云环境的资源调度中取得较好的效果。

2相关知识

在提出新的混合算法之前，我们必须先对对蚁群算法、布谷鸟搜索算法和云计算下任务调度模型进行介绍，简单分析它们的优缺点，从而进一步研究如何进行融合。

2.1蚁群算法

蚁群算法ACO(Ant Colony Optimization)是受自然界中蚂蚁搜索食物行为的启发而形成的一种智能优化算法。它的思想是模拟蚁群的集体觅食过程中的群体协作行为，实现求解路径上的信息积累反馈，并逐步取得最优路径。算法最早是由意大利学者Dorigo等人提出的，并被应用到TSP等一系列组合优化问题中，目前取得了良好的效果。

与其他启发式算法相比，蚁群算法在信息交换积累方面更加高效，也容易实现优化，因此在求解能力上具有很强的鲁棒性和精确性。而且作为一种随机种群进化算法，具有本质的并行性。但是，蚁群算法一般需要较长的搜索时间，容易出现停滞，造成收敛速度慢，易陷入局部最优。

2.2布谷鸟搜索算法

布谷鸟搜索CS(Cuckoo Search)是2009年由剑桥大学的 Yang Xin-she和 Deb S 开发的元启发式算法。该算法是受到布谷鸟的孵育寄生行为而启发的。重要的是，该算法利用Levy飞行取代了简单的各向同向性随机搜索路径，从而增强了算法的搜索功能。

该算法之所以有较强的搜索性能，主要原因是：(1)有很好的全局搜索和局部搜索的平衡；(2)算法受控制的参数数量较少。在CS算法中主要有两个参数：为群体规模n和发现概率p。一旦n固定下来，p就是控制精英选择和平衡全局搜索与局部搜索的重要工具。与其他启发算法相比，CS算法的优点在于选用参数少、搜索路径优、全局优化能力强。

2.3云任务调度模型

在云计算平台的任务调度中主要有三个方面的任务需要完成。依次为：任务解析、资源检测和资源分配与任务调度，如图1所示。首先，先由任务解析器把用户提交的任务分解成合适的任务执行单元，并放进任务池中。然后，根据每个执行单元之间的约束关系形成任务执行的联系图，一般用有向无环图(DAG)表示；同时，由资源检测单元监测任务处理单元的状态，并将硬件信息反馈给资源分配与调度单元。最后，由该单元完成资源的分配与任务的调度。

Figure 1　Scheduling model of cloud tasks 图1　云任务调度模型

3基于DAG的任务调度模型

本文所研究的问题是由云计算平台抽象而来的，提出的算法是针对任务节点的执行时间和能源消耗作为优化的目标。问题可以描述如下：

输入：以DAG图的形式表示任务节点；

输出：将任务节点分配到云平台上执行，获取最短执行时间和最少的能源消耗，输出任务分配调度方案。

为了方便研究，我们假设计算节点是相同的，也就是各个节点在功能、性能和损耗方面具有同样的等级。而且，我们忽略集群系统中出现的故障处理，而把故障处理时间集成到每个任务的执行时间。对于能耗消耗率的考虑，我们简单地用节点的功率来表示，因为通信的功耗主要取决于数据的大小和通信链路的传输速率。

任务的表现形式是如图2所示的有向无环图G=(n,e)。其中，n表示任务节点；e代表任务之间的约束关系，边上的数值是节点之间的通信成本，代表完成任务所损耗的能量。

Figure 2　Task dependency DAG graph 图2　任务依赖DAG图

4基于蚁群-布谷鸟搜索的任务调度策略

针对第2节中所提出的任务调度模型，本节我们将提出一种混合的ACOCS算法来快速。

蚁群算法凭借其良好的并行性、自组织性、正反馈性和鲁棒性，非常适用于组合优化的问题研究。但是，也存在不少的问题：(1)信息素是该算法最重要的信息载体，因此如何设计优秀的信息素更新策略是一个问题。(2)蚁群觅食搜索的时间较长，对于算法的收敛速度产生较大的影响，而且容易陷入局部最优。为了解决这一问题，本文引入CS算法，该算法需要设置的参数较少，容易实现，而且搜索的能力较强，对于全局搜索的速度较快，因此把它作为蚁群算法中觅食过程的搜索策略可以有效地提高全局搜索的效率，并且可以作为改变全局信息素积累的一种方法。

4.1优化搜索策略

蚁群算法的搜索时间较长，蚁群中单只蚂蚁的运动是随机的，但当问题的规模较大时会增加搜索最优解的难度，而且全局性会变差。混合算法的一大目标就是结合CS算法的搜索优势，并且改善蚁群算法搜索所带来的局部性和收敛慢的缺点。

CS算法的搜索路径与普通的路径不同，它使用的是随机性较强的Levy飞行的搜索方式。这种方式是一个步长大小服从Levy分布的随机游走，而游走方向是服从均匀分布的，并且还使用了具有Levy分布特征的Mantegna法则来选择步行向量。

(1)

其中，⊕是点对点乘法；Levy(λ)就是一个步长大小服从Levy分布的随机游走，可以表示为:

(2)

而步长大小主要通过Mantegna法则来实现。另外，α是步长控制量，主要用来控制方向和补偿大小。

把CS的搜索思想应用于蚁群算法中，可以使一些新解的产生是通过围绕最优解的Levy游走而渐渐达到最优的，这时也加快了局部搜索。而通过偏离较远的位置随机产生的一部分新解是远离当前最优解的，这样就可以确保系统没有陷入局部最优解。

4.2信息素更新策略

蚁群算法中的信息素是非常重要的信息。一个好的信息素分布可以引导蚂蚁快速准确地寻找到最优解，同时蚂蚁本身的行为可以影响和改变信息素的分布。本文所提出的算法首先是利用蚁群算法本身的搜索策略来进行一次迭代，对局部的节点进行信息素的更新。再把所求得的当前最优解转换到CS算法中去进一步迭代，对全局的信息素进行更新。

在时间t,每一个任务被分配到任意节点的概率可以由以下公式计算得出：

(3)

其中，τ是信息素浓度，η为可见度，本文采用η=aP+bC来计算，a和b是人工设置的系数，代表所占的权重；P反映的是节点的计算性能；而C反映的是节点的通信能力。α为信息素取法因子，反映蚂蚁在路径搜索中随机性因素所用的强度，β为期望启发式因子，反映蚂蚁在路径搜索先验性、确定性因素作用的强度。

这样的信息素更新策略有效地利用了CS算法中的精英保留策略，体现了算法局部搜索和全局搜索很好的结合，而且有效增加了混合算法解的多样性，使算法有效地避免陷入局部最优，从而达到全局最优的目的。

4.3算法描述

算法的描述如下：

步骤1初始化算法中的起始值。设定当前的任务数、测试的节点数，还有初始时刻的信息素。

步骤2每个蚂蚁独自进行随机搜索，根据公式(3)计算在搜索过程中留下的信息素，得出一次迭代的解。

步骤3利用上一步中得到的一组当前解初始化为CS算法的起始值，然后利用位置更新公式(1)继续进行搜索，并通过与发现概率对比进行选择，得出一组较优解和较优鸟窝位置。

步骤4把上一步得到的较优位置作为当前节点的信息素保留下来，并根据所选取的计算节点，计算对应的调度方案的调度长度L，并更新全局信息素。

步骤5若迭代次数到达所预定的最大迭代次数，或者迭代出现退化现象，则算法终止。那么，最优调度方案取为当前记录的最优解集。

算法的流程图如图3所示：

Figure 3　Flowchart of ACOCS algorithm 图3　ACOCS算法流程图

5实验分析

为验证本文中所提出的AOCCS算法的性能，采用云计算仿真软件CloudSim进行测试。主要与ACO算法进行比较并分析实验结果。实验的硬件环境为：IntelCorei5-2410M2.3GHzCPU,4GB内存。软件环境为：Windows7操作系统，Eclipse3.2和Java1.6.0语言开发工具，以及CloudSim2.1.1仿真器。

参考文献程序运行过程中需要按照实际情况设定运行时参数，本文涉及到的运行时参数设定由表1给出。由[10]可知道，α的最优取值范围为[1.0,3.0]，这里取中间值2；β的最优取值范围为[2.0,4.0]，这里取中间值3。这里假设节点的通信能力和计算能力均衡，则A取值0.5，B取值0.5。另外，为了节省实验的时间，节点选取10个，蚂蚁数选取20个，最大迭代次数选取100次。如表1所示。

Table 1　 Runtime parameters

表2和图4为ACOCS算法与AOC算法随着任务数增加完成任务调度所需要的时间。由图4可以看出，当任务数较少时，两种算法完成调度的时间差不多，但随着任务数的增加，ACOCS算法的完成时间增长较慢，速度得到明显的提高。

Table 2　 Relationship between the number

Figure 4　Comparison of completion time between the two algorithms 图4　两种算法完成时间比较

表3和图5为ACOCS算法与AOC算法随着任务数增加所消耗的能源量。图5可以看到，当任务数较少时，两个算法的能耗量基本相同，但是当任务数增加之后，ACOCS算法的能耗量得到改善的效果更好。

Table 3　 Relationship between the number of

Figure 5　Comparison of energy consumption between the two algorithms 图5　两种算法能量消耗比较

通过上述实验可以知道，ACOCS算法较于ACO算法在执行时间和能量消耗方面都明显有优势，而且随着任务数的增加，表现出来的性能更好。这都是因为提高了算法的搜索速度和全局性，使得ACOCS算法能够较快地收敛，减少了迭代的次数；而且还保留着ACO原有的并行性优势。

6结束语

本文对云计算的资源调度问题进行了一些探讨，并介绍了当前一些工作成果。在这些工作的启发下，通过对蚁群算法和布谷鸟搜索算法进行深入的研究，分析两种启发式算法可以互相促进的特点，并进一步提出一种基于布谷鸟搜索改进的蚁群算法的资源调度融合算法。该算法主要通过在蚁群算法中融入布谷鸟搜索的优势，增强了蚁群算法的全局搜索和收敛速度。仿真实验测试结果表明，该算法有效减少了调度所需的响应时间，也一定程度上提高了系统资源利用率。接下来的工作是进一步从其他方面来测试该算法的性能，并把这种策略应用到实际的云环境系统。

参考文献:

[1]ChenQuan,DengQian-ni.Cloudcomputinganditskeytechnology[J].ComputerApplication,2009,29(1):2562-2567.(inchinese)

[2]TammaroD,DoumithEA,ZahrSA,etal.Dynamicresourceallocationincloudenvironmentundertime-variantjobrequests[C]//Procof2011IEEE3rdInternationalConferenceonCloudComputingTechnologyandScience,2011:592-598.

[3]SongH,BaeCS,LeeJW,etal.Utilityadaptiveservicebrokeringmechanismforpersonalcloudservice[C]//ProcofMilitrayCommunicationsConference,2011:1622-1627.

[4]HsuCH,ChenSC,LeeCC,etal.Energy-awaretaskconsolidationtechniqueforcloudcomputing[C]//Procof2011IEEE3rdInternationalConferenceon.CloudComputingTechnologyandScience(CloudCom), 2011:115-121.

[5]ZhaoL,RenY,SakuraiK.Aresourceminimizingschedulingalgorithmwithensuringthedeadlineandreliabilityinheterogeneoussystems[C]//Procof2011IEEEInternationalConferenceon.AdvancedInformationNetworkingandApplications,2011:275-282.

[6]DengJian-guang,YuanHua-qiang,ZhaoYue-long.Agridtaskschedulingstrategybusedongeneticalgorithmandantcologyalgorithm[J].ApplicationResearchofcomputer,2011,28(12):4485-4488.(inChinese)

[7]SelvaraniS,SadhasivamGS.Improvedcost-basedalgorithmfortaskschedulingincloudcomputing[C]//Procof2010IEEEInternationalConferenceon.ComputationalIntelligenceandComputingResearch(ICCIC),2010:1-5.

[8]LiL.Anoptimisticdifferentiatedservicejobschedulingsystemforcloudcomputingserviceusersandproviders[C]//Procofthe3rdInternationalConferenceonMultimediaandUbiquitousEngineering,2009:295-299.

[9]WangFan.TheoreticalresearchandapplicationoftheCuckoosearchalgorithm[D].Xi’an:Xi’anPolytechnicUniversity,2011.(inChinese)

[10]SongJin-juan.Animprovedantcolonyalgorithmanditsapplicationinshortestpartproblem[D].Taiyuan：NorthCentralUniversity,2013.(inChinese)

参考文献：附中文

[1]陈全,邓倩妮. 云计算及其关键技术[J]. 计算机应用,2009,29(1):2562-2567.

[6]邓见光,袁华强,赵跃龙. 一种基于遗传—蚁群算法的网格任务调度策略[J]. 计算机应用研究,2011,28(12):4485-4488.

[9]王凡.CuckooSearch算法的理论研究与应用[D].西安：西安工程大学,2011.

[10]宋锦娟. 一种改进的蚁群算法及其在最短路径问题中的应用[D].太原：中北大学,2013.