基于多维QoS约束的网格任务负载均衡调度模型及算法

张 宏，陈 森

（周口师范学院 计算机科学与技术学院，河南 周口466001）

随着计算商业化的发展，负载均衡和服务质量QoS（Quality of Service）成为任务调度过程中考虑的两个重要内容.笔者通过建立连续性QoS效应函数的方式，调整不同目标的权重值来协调用户不同任务的特性倾向，从而更好地满足用户对不同目标最优值的需求.在此基础上，借助于经典的遗传算法，通过对遗传算子的重新设计，提出一种基于多维QoS约束的网格负载均衡优化任务调度算法（Load Balance and Multie QoS Optimization Genetic Algorithm，LGGA）.

1 网格系统调度模型和优化目标

1.1 网格系统任务调度模型

首先形式化定义异构环境和参数模型.

定义1 异构环境使用一个五元组表示，即HDC＝｛P，M，T，D，C｝.

P＝｛p1，p2，p3，…，pm｝，表示异构网格系统包含m个物理节点；

M＝｛m1，m2，m3，…，mn｝，表示n个相互独立的、不可分割的任务；

T＝｛t1，t2，t3，…，tm｝，表示物理节点单位时间的计算量；

D为资源分配矩阵，dij＝1（1≤i≤n，1≤j≤m）表示第i个任务分配到节点j上，dij＝0表示第i个任务未分配到节点j上；

C＝｛c1，c2，c3，…，cm｝表示任务在物理节点上单位时间执行费用.

定义2 用户提交任务信息使用四元组表示，即MI＝｛AC，ECT，Deadline，cost｝.

AC＝｛ac1，ac2，ac3，…，acn｝，aci表示任务i的计算量；

ECT＝｛ect1，ect2，ect3，…，ectn｝，ecti表示任务i的期望执行时间；

cost＝｛cost1，cost2，cost3，…，costn｝，costi表示任务i的期望执行费用；

Deadline＝｛dl1，dl2，dl3，…，dln｝，dli表示任务i的最迟完成时间.

1.2 效应函数

效应函数U（x）表达了用户对某一要素x的满意程度，每一个QoS要素对应一个效应函数.不失一般性，笔者只考虑任务执行费用和时间效应.

1.2.1 费用效用函数

任务mi的费用效应函数UP（mi）定义为公式（1）.

在式（1）中costmin和costmax分别表示任务mi在m个物理机上执行的最小费用和最大费用.如果costi介于costmin和costmax之间，说明存在物理机满足用户费用需求，否则不存在物理机满足用户需求，必须丢弃此任务.UP（mi）的范围是［0，1］.

1.2.2 执行时间效用函数

执行时间是任务调度器必须考虑的另一个重要特征，任务mi的执行时间效应函数UT（mi）定义为公式（2）.

在式（2）中ectmin和ectmax分别表示任务mi在m个物理机上的最短执行时间和最长执行时间.

1.2.3 集成总效用函数

使用α和β分别表示用户对费用和执行时间的权值分配，任务mi的执行费用P和执行时间T的集成总效应函数Utotal（P，T）使用公式（3）表示.

通过修改α和β，可以形成不同费用和执行时间权重组合，如果UT（mi）＝0或者UP（mi）＝0，则Utotal（P，T）＝0.因此对于相同的效用值，可以得到不同的费用和执行时间的组合.

1.3 优化目标

基于多维QoS约束的网格任务负载均衡优化目标模型可以使用公式（4）表示.

LBj表示计算节点j的负载，LB表示系统平均负载.σ值反映了系统负载均衡的性能，σ＝0时，系统达到理想的负载均衡的效果.Ui表示任务mi的总效应值，U为所有任务总效应函数值的和.

2 算法设计

由于网格任务调度已被证明是一个NP难问题，而基于进化理论的GA非常适合解决复杂条件下的优化问题.为了增强GA的广度搜索能力和加快算法的收敛速度，引入一个针对特定问题的调整算子，同时加入了局部搜索算子增强其局部搜索能力，使设计的基于多维QoS约束的任务调度算法（LGGA）兼具较强的全局和局部搜索能力，从而获取更好的调度结果.

下面分别给出LGGA算法的局部搜索算子、选择算子、交叉算子、变异算子和调整算子的设计及算法伪代码.

2.1 局部搜索算子

针对任务中可能存在强QoS约束的情况，为了提高算法搜索的效率，设计一种新的局部搜索算子.在算法初始阶段，找出具有强QoS约束的任务，然后计算出这些任务所对应的计算节点集合.如任务m2为强QoS约束，只有物理节点p2和p3能够满足QoS约束.在交叉和变异的过程中优先考虑任务m2，在对系统负载均衡的影响不超过ξ（ξ为经验值，随系统任务量和计算能力动态调整）的情况下，优先分配p2和p3.

2.2 选择算子

选择算子以轮盘赌选择方式为基础，引入QoS效用值.QoS效用值越大，适应值就越好.笔者采用精英选择策略，除了选择负载均衡性能好的个体外，还选择一些QoS效用值大但负载均衡性能差的个体，增强了种群的多样性.

2.3 交叉算子

为了增强搜索的广度和效率，设计一种新的交叉算子，即对父代中的两个个体对应位中的值相加后取模求余.如果余数为0且该任务为强QoS约束类型，又同时满足父代对应位相同且等于物理节点的个数，则执行局部搜索算子.如m＝10，n＝5，第二位为执行局部搜索算子后的基因，第四位为没有执行局部搜索算子后的基因，交叉过程如图1所示.

2.4 变异算子

变异算子目的在于增加种群的多样性，是对个体在满足特点概率时的小的扰动.笔者设计一个均匀变异算子，即设x＝（x1，x2，x3，…，xn）为参加变异的个体，当满足特点概率时，以均匀概率的方式依次从每个任务对应的节点集合中选择一个节点s，替换掉xi，执行n次，得到一个新的个体d＝（d1，d2，d3，…，dn）.该变异算法设计简单，且可以有效防止算法陷入局部最优.

图1 交叉算子执行前后示意图

2.5 调整算子

为了使更多任务可以满足QoS约束以达到提高任务调度成功率和QoS综合效益值的目的，设计了一个调整算子.

把该染色体映射成机器调度，随机找到一个不满足QoS约束的任务mi和对应的计算节点pj，将此任务分配到随机产生的一台机器pr上，计算节点的负载均衡度.如果此时的负载均衡度提高，则将该任务调整到机器pr执行，计算出调整后染色体编码；否则，不调整.

2.6 算法流程

LGGA算法伪代码：

（1）初始种群：变异概率为pm，交叉概率为pc，种群规模为N，进化代数为G.采用直接整数编码的方式，生成规模为N的初始种群，记为X（0），当前进化代数g＝0；

（2）交叉：以杂交概率从X（t）中选择两个个体Xi和Xj作为父母进行杂交，杂交后集合记为Nc；

（3）变异：对初始种群进行概率为pm的均匀变异操作，产生变异后代种群记为Nm；

（4）选择：采用设计的精英选择策略和改进的轮盘赌选择算子，从X（t）∪Nc∪Nm中选择N-1个个体，组成下一代规模为N的种群X（t＋1）；

（5）判断终止条件，如果没有满足，转步骤（2）.

3 实验仿真结果与分析

为了评估提出的模型与算法，首先给出仿真环境和参数设置，而后将提出的LGGA算法与经典的Min-Min，Sufferage和基本遗传算法（GA）等启发式算法比较，验证LGGA算法在任务调度成功率、最迟完成时间、系统负载均衡和总QoS效应值方面的有效性.

3.1 实验环境及参数设置

基于JAVA语言设计开发一个有网格任务发生器GridTaskGenerator和任务调度器GridTask-Schedule构成的网格系统仿真器.GridTaskGenerator负责随机产生具有不同需求的任务，Grid-TaskSchedule负责模拟网格环境，其主要职责是任务调度.每个任务到达服从λ＝λi的泊松分布，每个任务的计算量服从λ＝ωi的泊松分布.λi取值范围为0.2～0.9，ωi取值范围为5～20；物理节点的计算能力取值范围为20～40.LGGA的运行参数主要依据多次试验的经验值而设置：种群规模大小为500，交叉概率为0.75，变异概率为0.1，算法最大迭代次数为100.

3.2 仿真结果分析

本小节从任务调度成功率、最迟完成时间、总QoS效应值和负载均衡四个指标对提出的LGGA进行综合评价.任务调度成功率决定了（在一个调度周期中）被成功调度的任务个数；最迟完成时间指任务的调度跨度，即从第一个任务执行到最后一个任务完成所经历的时间段；总QoS效应值指一个调度中所有任务的QoS效应值的和.总QoS效应值可以从全局评价调度的质量，反应用户总的满意程度.系统负载均衡反映了系统中任务分配的合理性.

仿真实验主要考查在网格环境（资源数量）不变而任务数从100个到800个变化情况下，不同指标的变化情况，如图2所示.从图2（a）可以看出，随着任务数量的增加，四种算法的最迟完成时间都会增加.其中Sufferage算法的最迟完成时间最短，这是因为Sufferage算法没有考虑QoS约束，并且从全局考虑任务的次好情况.而其他三个算法的最迟完成时间区别不大.从图2（b）可以看出，随着任务数量的增加，四种算法的负载均衡性能都有所下降，而GA算法和LGGA算法的变化幅度较Min-Min和Sufferage算法更小，且更平稳.并且LGGA算法比传统的GA算法具有微弱的负载均衡性能优势.从图2（c）可以看出，随着任务量的增加，任务的总QoS效应值变大，其中LGGA算法的QoS效应值最大.从图2（d）可以看出，随着任务量的增加，任务完成率变小.在四种算法中，任务量相同的情况下LGGA算法具有较高的任务完成率，与图2（c）中LGGA算法具有较高的QoS效应值相对应.

总之，仿真实验证明，在同等条件下，LGGA算法与经典的Min-Min，Sufferage和基本遗传算法（GA）等算法比较，在任务完成率、总QoS效应值和负载均衡中具有较好的综合性能.

图2 网格环境不变而任务数量改变情况下不同指标的优化比较图

4 小结

从满足网格系统负载均衡的问题出发，构建任务调度模型和反映用户满足度的综合QoS效应函数.对于不同QoS因素设计了不同的效应函数.为了提高任务调度成功率，LGGA算法在传统的GA算法基础上，重新设计了选择算子，并在交叉算子中，增加局部搜索算子，增加了搜索的深度和精度.通过引入一个调整算子，进一步提高了任务调度成功率.下一步的工作将研究非独立、可分任务在动态任务调度中的优化问题.

［1］孙伟峰，覃振权，李明楚，等.一种多QoS约束网格任务调度算法［J］.电子学报，2011，39（5）：1115-1120.

［2］罗慧敏，阎朝坤.一种基于任务竞争力的工作流调度算法［J］.河南大学学报：自然科学版，2012，42（1）：87-91.

［3］Fang Dong，Junzhou Luo.A Grid Task Scheduling Algorithm Based on QoS Priority Grouping［C］.Proceedings of the Fifth International Conference on Grid and Cooperative Computing，2006：58-61.

［4］T Amudha，T T Dhivyaprabha.QoS Priority Based Scheduling Algorithm and Proposed Framework for Task Scheduling in a Grid Environment［C］.IEEE-International Conference on Recent Trends in Information Technology，2011：650-655.

［5］Huang Hai-yu，He Da-ke.Grid task schedule algorithm based on load balance［J］.Computer Engineering，2010，36（2）：58-60.

［6］杨锦，李肯立，吴凡.异构分布式系统的负载均衡调度算法［J］.计算机工程，2012，38（2）：166-169.