基于改进蚁群算法的网格资源调度研究

陈雨时，曲海成，2+，龚小川

(1.哈尔滨工业大学电子与信息工程学院，黑龙江哈尔滨150001;2.辽宁工程技术大学软件学院，辽宁葫芦岛125105)

0 引言

目前集群计算和网格技术被广泛应用到遥感影像处理系统中。在集群计算环境中，PC机或工作站通过局域网连接，为用户提供高性能计算。由于集群计算处于一个局域网内，所以它的应用具有局限性，通常计算能力也有限。而网格计算是把不同地理位置的网格资源结合起来构成一个虚拟的超级计算机［1］，网格计算对资源的类型及地理位置没有限制，可以为系统提供很强的计算能力［2］。但是网格计算是通过网络把不同地域的计算资源结合起来构成一个整体，这就使它不同于传统的集群计算。网格调度问题与传统集群计算的调度问题相比更加难以解决，主要原因有:网格系统任务的属性更加复杂，如:任务量变大、任务具有优先级、任务对资源的需求限制等;网格资源的属性具有实时多变性、网格资源的多样性、类型的复杂性等特点。因此，网格系统中资源的管理和调度是网格系统中的关键部分，其中任务分配和负载均衡问题是重点需要解决的难题。在网格计算环境中，负载均衡算法的目标是使计算资源上的网格任务尽量达到平衡，所有任务的执行时间最短和每个资源的利用率达到最高［5］。文中提出了一种改进的ACO调度算法，可以使任务在更短的时间内完成，网格资源的利用率显著提高。网格任务为遥感资源的空间检索任务，即:将用户请求的多边形区域 (可能是凸多边形、凹多边形或是带有孔的多边形等)，通过射线法［6］与数据库中记录的多边形区域进行匹配，找出满足用户需求的记录。多边形形状越复杂，任务计算量越大，资源的空闲时间越难掌握，而改进ACO算法适合解决这类问题。

1 网格调度算法分析

网格调度技术主要涉及任务负载均衡算法的性能及优化，主要分为两大类:静态调度算法和动态调度算法。在静态调度算法中，所有任务的信息、资源的信息及网络带宽等信息都是预先知道的，任务必须分配到适合的网格资源执行。静态负载均衡算法主要的缺点是:在任务的执行过程中，所有任务和资源的信息都是固定不变的。相反，动态调度算法是通过获得任务和资源的实时状态信息进行任务的调度，这样就能更准确地进行任务的分发。经过对比实验可以看出，静态负载均衡算法更易实施，但是动态负载均衡算法有更好的效果。

网格资源调度是一个NP完全问题。许多算法已经被应用于解决此问题。常用的算法包括:OLB、MET、MCT、SWA、KPB、Min-Min、Max-Min、Dupplex、MaxStd 和 GA等［3-5］，下面对其进行具体的对比分析。

OLB(opportunistic load balancing)是在不考虑任务执行时间的情况下，按最短的分配表以任意的顺序把每个任务分配给网格资源。OLB算法的目的是为了平衡各网格资源的负载，但由于它没有考虑任务执行时间，所以很难达到网格负载均衡的目的。

MET(minimum execution time)是不考虑网格资源当前的负载情况，把任务分发给执行该任务最快的网格节点。MET算法企图找到好的任务-网格资源匹配，但是由于它没有考虑网格资源目前的任务量，这样会导致各个网格资源节点负载的不平衡性，处理能力强的资源节点总是有很多任务，处理能力差的资源节点可能总是处于空闲状态。

MCT(minimum completion time)算法的思想是把任务分发给最早完成该任务的网格资源节点。其中任务j在资源节点m完成时间定义为任务j在节点m上的执行时间与目前节点m上任务执行所需的时间之和。这是一种同时考虑了任务执行时间和网格资源节点负载情况的启发式算法。

Min-Min算法是首先获得最短执行时间的任务j，以及得到完成任务j的MCT最少的网格资源节点m，然后把任务j分发给网格资源节点m执行。Min-Min与MCT都利用了任务完成时间，但是由于Min-Min算法在每次选择任务的时候选择的是所有任务中最小完成时间的任务，这样将会减少完成所有任务所需的时间。Min-Min算法在网格资源节点负载均衡方面要优于MCT算法。

Max-Min算法与Min-Min算法很类似。同样是选择任务j完成时间最短的网格资源节点，但是与Min-Min算法不同之处是任务j选择的是完成所需时间最大的任务。Max-Min算法更适用于复杂任务的调度问题。但是实验结果表明Max-Min算法不是在所有问题上都优于Min-Min。

MaxStd(maximum standard deviation)在 MaxStd算法中，任务的期望执行时间拥有最高的标准差优先执行。执行的标准差低，在不同的资源节点上任务执行时间变化很小的任务推后执行。

GA(genetic algorithm)是Holland发现的，该算法是模拟自然生物的进化过程，基于达尔文的自然选择准则。GA通过控制大量染色体来实现进化，其中这些染色体是根据问题进行描述的，每个染色体代表解空间的一个潜在解。在每代循环过程中，对染色体的操作主要包含3个:复制、交叉和变异。通过这3个过程，不但可以保留较好的解，还可以产生更好的解。因为GA以上的优点，它现在已经广泛应用于启发式问题的求解问题。同时，很多研究者也把GA应用到了网格任务调度的问题中，并且研究发现GA可以给该问题带来较好的解。

ACO(ant colony optimization)也是一种分布式、启发式算法，ACO的灵感来源于蚂蚁群体寻找食物的行为，算法针对的是离散的优化问题［8］。它的研究模型来源于对真实蚂蚁行为的观测，通过开发真实蚂蚁高度协作行为的自组织原型来 (self-organizing principle)来调动一群人工agent协作解决一些计算问题。蚂蚁都是通过一种“媒介质”来协调他们之间的行动，所谓的“媒介质”指的是一种以环境的变化为媒介的间接通信形式，例如，蚂蚁正在寻找食物时，会在其经过的路上释放一种化学物质 (信息素)，随着路径上的化学物质的增加，也会增大其他蚂蚁走同一条路的概率。ACO通过释放信息素来实现蚂蚁之间的间接通信，从而达到协调工作的目的。ACO算法利用人工蚂蚁agent之间的协作来找到最优或次优解。这种算法也被广泛的应用到许多NP问题中，并且取得的很好的效果。

2 改进ACO算法设计

ACO算法的主要特点有以下几个方面［9-10］:

(1)网格任务调度是一种NP完全问题，由于ACO算法具有很强的自适应性，且具有正反馈的特点，这样加快了网格任务调度的求解过程。

(2)ACO算法是以信息素为介质进行间接通信，通过蚁群释放的信息素可以逐渐地发现最优解。前面也提到了，ACO算法给解决TPS、JSP、GCP等问题组合优化问题提供了很好的求解方式。网格任务调度问题正是一种组合优化问题，它是寻找一种任务与资源的最优组合方式，所以ACO算法同样适用于网格任务调度问题。

(3)ACO算法是蚂蚁之间通过利用释放的信息素协同工作寻找最优解的问题，充分体现了ACO算法中蚂蚁个体之间的协作性与该算法很强的并行性。而网格计算本身是分布式计算中的一种，这样ACO算法就可以利用算法本身的并行性和协作性为网格任务的分配提供方便。

(4)ACO算法反映的是群体智慧，不是个体智慧，所以算法自身具有很强的鲁棒性，对系统初始化条件的要求不是太高，这使得ACO算法可以适用于复杂的网格计算环境。

通过对ACO算法以上几个特点和网格任务调度本身特性的综合分析可以得出，ACO算法适合于求解网格任务调度问题。

本文提出的改进ACO算法主要是在算法中引进了一个向量F=free(j)，1≤j≤m，其中m为网格资源数，free(j)表示资源j处于空闲状态所需的时间。向量F引进以后，根据F可以更好地了解资源的运行情况，更容易掌握其任务负载量，这样为选择最适当的网格资源提供了关键信息，网格任务的调度的效果更佳。

在改进ACO算法中，网格计算系统把每个任务看出一只蚂蚁。图1为改进ACO算法的流程图。

图1 改进ACO算法的流程

改进ACO的算法主要步骤［11-12］为:

(1)获得网格资源的状态信息及任务的相关信息，对F进行初始化，网格资源信息素τj(t)与启发式信息ηj(t)初始化，蚂蚁的数目为任务数n。

(2)选择任务j，获得资源列表信息，计算任务j分配给所有资源的转移概率选择值最大的网格资源作为与任务j匹配的资源。

(3)把任务j分配给资源k执行，更新网格资源节点的信息素。回到步骤 (2)继续执行，直到所有的任务都执行完成。

改进ACO算法包含3个关键部分有:网格计算资源信息初始化、网格资源的选择机制以及信息素的更新。

(1)网格计算资源信息初始化

在改进 ACO算法中，初始化向量 Free(0...m－1)=a，其中a是0＜a＜1，m网格资源的数目，网格计算资源的信息素定义为

启发式信息定义为

(2)网格资源的选择机制

改进ACO算法的网格资源选择机制采用传统ACO算法的计算转移概率机制。该机制对第j个任务，即第j只蚂蚁，分别计算在所有网格资源的转移概率表示在t时刻第j个任务选择资源k的概率的定义为

式中:τj(t)——t时刻网格资源 j的信息素浓度;ηj——网格资源j的启发因子，即ηj=τj(0);α——信息素的重要程度;β——网格资源启发因子的重要程度。由于网格资源的分布性与动态性，大量实验表明 α和 β值都取0.5较合适。

(3)信息素的更新

每当完成一个网格任务j，各网格资源信息素便会进行更新，其中更新准则为

式中:Tij——第 i个任务在资源 j上完成所需的时间，ρ——信息素的持久性 (0＜ρ＜1)，1－ρ表示信息素的挥发系数。

3 实验结果分析

该部分研究使用的是Gridsim仿真平台，Gridsim工具包的主要目的是基于网格计算的大规模分布式资源下的任务分配和资源调度技术。通过Gridsim我们可以仿真拥有数万个资源和上千用户的大规模网格计算环境的研究系统。在Gridsim平台上分别对Random、Min-min、Max-min、ACO算法以及改进ACO算法及进行的相关实验，其中，α和β值都取0.5，ρ取0.8。Free(0...m －1)=1，m 网格资源节点数目。本文针对以上算法做了三组实验，其中前两组实验是分析任务完成时间，第三组实验室分析网格资源的利用率，也叫负载均衡率。在以下实验中，前提条件是所有任务都相互独立以及任务都具有同等优先级。

实验一为固定网格资源节点数为40，任务数目分别为:1000，1500，2000，2500，3000，3500，4000。实验结果如图2所示，从图2中可以看出，随着任务数的增多，完成任务数的时间增大;当任务数一定时，改进Ant算法所花的时间比Ant及其他三种算法所花的时间少很多。

图2 网格节点数为40的实验结果

实验二的条件是任务数为2000，网格节点数分别为10，20，30，40。实验结果如图3所示，图中可以看出，任务数为2000，当网格资源节点数目增多，完成任务所需的时间越来越少;当网格资源节点数目一定时，在任务完成时间上改进蚁群算法明显优于其他算法。

图3 任务数为2000的实验结果

实验三的实验条件是网格任务数为2000，网格资源节点数为10。实验主要研究算法的网格资源利用率，其中资源率的定义为

式中:T1，T2...Tm——m 个网格资源节点各自处理任务所花的时间，max(T1，T2...Tm)——所有网格资源中执行任务时间最长的节点。表1给出了5种算法的资源利用率的一个实验结果。图4为表1的柱状图，从实验结果也可以看出，改进ACO明显优于其他算法，与一般ACO算法相比，网格资源利用率大约提高了15%。综上所述，在网格计算环境下，改进ACO算法 明显优于Random、Min-min、Max-min及ACO网格调度算法，改进ACO算法使网格资源完成任务所花的时间减少以及网格计算资源的利用率有所提高。

表1 网格资源的利用率

图4 网格资源的利用率柱状

4 结束语

网格资源的调度技术是分布式计算中的关键技术，好的资源调度算法对提高整个网格系统的性能起关键作用。本文提出了一种改进ACO网格资源调度算法，更好地解决网格资源的分布性、动态性、可扩展性等问题，尤其对网格任务计算时间不确定的任务，调度效果更加明显。改进ACO算法使网格负载均衡率更高，可以更优地利用网格资源。在接下来的研究中，可以把网格资源的经济效益、社会效益等因素考虑进去，这样可以加快网格资源的商业化的步伐。

［1］Dorigo M，Blum C.Ant colony optimization theory:A survey［J］.Theory Compute Sci，2005，344(2/3):243-278.

［2］Stefka Fidanova，Mariya Durchova.Ant algorithm for grid scheduling problem ［G］.LNCS 3743:Proceedings of the 5th International Conference on Large-Scale Scientific Computing，2006:405-412.

［3］Kousalya K，Balasubramanie P.An enhanced ant algorithm for grid scheduling problem ［J］.International Journal of Computer Sci-ence and Network Security，2008，8(4):269-270.

［4］ZHANG Jun，HU Xiaomin，LUO Xuyao.Ant colony optimization［M］.Beijing:Tsinghua University Press，2007:98-109(in Chinese).［张军，胡晓敏，罗旭耀.蚁群优化［M］.北京:清华大学出版社，2007:98-109.］

［5］WANGXianglin，ZHANGShanqing.The grid:Core techno-logies［M］.Beijing:Tsinghua University Press，2006:168-172(in Chinese).［王相林，张善卿.网格计算核心技术［M］.清华大学出版社，2006:168-172.］

［6］CHEN Ruiqing，ZHOU Jian，YU Lie.Fast method to determine spatial relationship between point and polygon ［J］.Journal of Xi’an Jiaotong University，2007，41(1):59-63(in Chinese).［陈瑞卿，周健，虞烈.一种判断点与多边形关系的快速算法［J］.西安交通大学学报，2007，41(1):59-63.］

［7］Lorpunmanee S，Sap M，Abdullah A，et al.An ant colony optimization for dynamic job scheduling in grid environment［J］.International Journal of Computer and Information Science and Engineering，2007，1(4):207-214.

［8］Huang Han，Wu Chun-Guo，Hao Zhi-Feng.A pheromone-ratebased analysis on the convergence time of ACO algorithm ［J］.IEEE Transactions on Systems，Man，and Cybernetics-PART B:CYBERNETICS，2009，39(4):910-923.

［9］Yan H，Shen X，Li X，et al.An improved ant algorithm for job scheduling in grid computing［C］//Presented at Proceedings of the Fourth International Conference on Machine Learning and Cybernetics，2005:2957-2961.

［10］Li Y.A bio-inspired adaptive job scheduling mechanism on a computational grid［J］.International Journal of Computer Science and Network Security，2006，6(3):1-7.

［11］Faisal Nadeem M，Arash Ostadzadeh S，Stephan Wong，et al.Task scheduling strategies for dynamic reconfigurable processors in distributed systems［C］//Istanbul，Turkey:High Performance Computing and Simulation，2011:90-97.

［12］Pavani G，Waldman H.Grid resource management by means of ant colony optimization ［C］//San Jose，CA:3rd International Conference on Broadband Communications，Networks and Systems，2006:1-9.