微粒群算法在资源调度中的应用研究

摘要采用微粒群智能优化算法对网格资源调度模型进行多目标优化设计,通过仿真实验可以看出该方法和传统算法比具有相当大的优势。

关键词微粒群算法;资源调度;网格

中图分类号TP3文献标识码A文章编号1673-9671-(2010)042-0142-01

网格作为一种新兴的基础设施,目的是把地理位置上分散的资源集成起来,从而实现互联网上所有资源的全面连通。通过资源管理和调度策略,网格平台上的资源调度合理地将任务分配给不同的异构资源,使整个网格系统的运行达到最佳性能或用户最大满意度,实现网络资源共享。资源调度过程中多个实体,不同实体间QoS(Quality of Service)目标不同,甚至相互抵触,这就给资源调度带来了多种可能性。目前网格资源调度的研究的热点问题,集中在协调不同种实体间和同类实体内部的QoS要求的调度算法上,而选择一个高效的调度算是解决资源调度问题的关键。启发式搜索算法通过模拟社会和自然环境中的特定现象,来解决非确定、并行结构、自适应性问题,算法包括遗传算法、蚁群算法、微粒群算法、及其混合方法等。本文采用微粒群智能优化算法,该方法概念简单,易于理解,实现简单、速度快,同时具备很强的鲁棒性。

1调度模型

本文研究的资源调度模型采用批处理模式下独立任务调度。将任务执行时间和执行费用两个方面作为衡量用户满意度的指标,资源分配问题数学模型定义如下:

1)将网格资源节点定义为s,所有节点的集合为网格资源集合,记作,用户提交网格的应用被划分成单个的任务x,记作,。用户在递交任务的同时指定了任务的最长执行时间Deadline,以及可以支付的最大开销Budget值。

2)任务在资源的执行需要支付的费用和预计执行的时间,构成的集合分别对应矩阵

3)任务分配给资源执行,每次分配就确定了一个调度方案,它们构成了资源分配映射方案的集合,,每个映射对应一个矩阵。

优化调度的目的就是在任务分配给各个资源执行过程中,总的“耗费”最小。假设用户对服务资源的QoS需求为,每一维QoS由一个效用函数来表示用户选择某一服务资源时所获得的“利益”。引入效用函数来描述用户的每一维QoS需求,每一维QoS都有自己的组合权重,网格服务的组合QoS即为综合效用函数。与费用、时间相关的效用函数为:(式中D为时延常数,为权重。)

4)网格资源调度可以定义为,根据给定的S,X,EC,ET和U,求一个映射方案map,使得,其中

S.T.: ,

2问题优化设计

本文研究的问题求解得到的结果应是任务在资源上的一个映射,即任务和资源的任意分配方案,通过借鉴遗传算法的染色体编码方法,采用正整数编码方式,用数组r(k,n)表示生成的映射,如r(k,i)=()表示资源分配给任务i执行。

在基本微粒群算法中速度位移模型针对的是连续型的数值求解,而本文的资源调度问题是离散型问题,因此,要对微粒的编码机制以及速度位移模型进行改进,才能使得微粒群算法真正应用于资源调度的寻优过程中。本文对速度位移模型的改进有两个方面:一方面,在计算速度v时采取对按位计算的方式,使离散编码能在连续的空间内飞行;另一方面,在计算位移时,若微粒飞出边界,则等于边界值,最后通过向上取整来求得,保证微粒在目标空间内飞行。

资源调度问题中所有的映射集合MAP为整个微粒的种群,种群中的每个微粒被看作问题的潜在解,种群中第i个微粒用四元组表示,其中为任务分配给资源执行的一个调度方案,表示该方案在映射集合MAP的空间位置;表示粒子i当前的速度;表示粒子i自身搜索过的个体最好位置。 通过对进行解码,求得该映射的时间效用值,表示当前微粒飞行的位置。基于费用、时间两方面的约束,完成任务所需的费用之和不得超过用户所能支付的费用成本,本文采用罚函数法来处理费用-时间约束。取一个很小的分数作为罚系数,用乘上总过载量加到目标函数上,则目标函数转化为:

If

Then

这样,不可行解的适应值很小,在PSO迭代求解过程中,微粒群会逐渐收敛于可行解。

3实验仿真与分析

本文选取基本遗传算法作为比较算法。遗传算法的染色体同样采用非负整数编码,交叉概率取0.8,然后以等概率进行资源交叉,变异概率为0.5。由于遗传算法和微粒群算法都是随机初始,难免会出现过早收敛陷入局部最优等情况,为了使比较数据更具可靠性,本文的数据都是经过多次重复试验获得的平均值。以下是试验结果的比较。

图1反映了两种算法在资源数固定的情况下,核心算法的系统运行时间随任务数量变化的比较,实验结果表明PSO算法的相较于GA算法时间代价小,能够较快收敛。

4结论

本文所给出的算法针对程序中独立任务给出的调度方案,兼顾了时间、费用各个因素的可行方案,本算法能根据用户的需求,在时间允许的情况下尽可能的把任务映射到价格便宜的计算机上,和传统算法比具有相当大的优势。虽然当问题的规模变得极大时,算法的求解较为耗时。但由于PSO算法本身具有并行性,因此可节省大量的求解时间。

参考文献

[1]桂小林.网格技术导论[M].北京:北京邮电大学出版社,2005:16-20.

[2]L. Maozhen,B. Mark.网格计算核心技术[M].北京:清华大学出版社,2006,166-202.

[3]陈东海,顾寅红,杨长生.网格计算中时间和费用限制下的任务调度算法[J].计算机应用,2004,24(8):94-97.

[4]张腾飞,王锡淮,肖健梅.基于微粒群优化的连续属性离散化算法[J].计算机工程,2006,32(3):44-46

[5]李春林,郑辉.网格计算中基于QoS的资源调度优化模型[J].武汉理工大学学报,2008, 32(2):199-202.

[6]谷清范,吴介一,张飒兵等.基于遗传算法的多性能目标网格服务调度算法[J].信息与控制,2005,24(3):279-285.

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文