基于博弈策略的应急资源网格化调度研究

曹杰　王少鹏

摘 要：文章建立基于博弈策略的网格化应急资源调度模型，三个目标函数分别为：（1）完成任务花费的时间最小；（2）整个任务花费的费用最低；（3）任务的生存性。在建立模型之后，结合传统的网格化调度算法，运用基于静态贝叶斯博弈的多目标进化算法（SBG-MOEA）求解模型，得出Pareto最优解集，并针对模型结果将SBG-MOEA算法和经典的NSGA-∏算法进行了比较测试，发现算法SBG-MOEA在收敛性Pareto非支配解的分布性上都表现优异。决策者可以根据实际情况从最优解中选取最符合条件的解。

关键词：突发事件；网格化调度；多目标优化；SBG-MOEA

中图分类号：F253 文献标识码：A

Abstract： The essay establishes meshing model of emergency resource schedule on the basis of game strategies， and the three objective functions are respectively： （1）It takes minimum time to finish the task； （2）It takes the minimum cost for the whole task； （3）Survivability of the task. After establishing the model， combine with traditional meshing schedule algorithm to solve the model with multi-objective evolutionary algorithm（SBG-MOEA）which is based on static bayesian game， then the optimal solution set of Pareto has been concluded. Based on the model result， the comparison test is done between algorithm SBG-MOEA and classical algorithm NSGA-∏. Then it has been found that algorithm SBG-MOEA shows excellent distinction in distributivity of non-dominated solution for convergence Pareto. The decision maker can select the solution which most matches condition from the optimal solution set according to reality.

Key words： emergency； meshing schedule； multi-objective optimization； SBG-MOEA

0 引 言

作为网格计算中的一个关键性问题，网格任务调度受到了众多研究学者的关注。网格利用互联网或专用网络逻辑上分离的各种资源（包括计算机资源、存储资源等）连接起来，采用一定的网格调度算法，将这些任务合理分配到网络节点上运行，达到充分利用资源的效用[1]。网格为用户提供高性能的计算服务，然而对于用户来说，网格确实透明的。为了提高资源利用率和缩短完成任务的时间，就要优化调度方法。因此，网格任务调度实质上是一类优化问题。已经被证实是一类NP完全问题[2]。

当前的网格任务调度算法并不能很好地解决其中存在的问题。我们利用基于博弈策略的多目标进化算法对网格任务调度进行求解，该方法主要考虑了任务完成时间、完成费用和任务的生存性三个方面的指标[3]。

1 网格任务调度概述

1.1 网格任务调度特点及目标

1.1.1 网格任务调度的特点

网格环境下，资源数量多，任务数目大，而且两者的匹配关系复杂。这些使得网格任务调度具有以下几个特点[4]：

（1）任务调度面向异构平台；

（2）采用分布式并行的调度方法；

（3）调度与网络节点内部策略无关；

（4）必须满足扩展性要求。

1.1.2 网格任务调度的主要目标

网络是一个分布性的异构系统。网络上的一个程序可以看作一个任务集。调度问题就是要满足性能要求和约束关系的前提，将众多任务按照一种分配和执行顺序将其分配到各网络节点上。但网络系统是复杂、异构和动态的，而且应用程序对各网络节点的资源要求不同，另外对任务的调度顺序也有要求等，这些问题的存在导致网格任务调度变得非常复杂。不好的调度算法会造成资源调度不合理，任务执行时间延长等问题。因此，网格任务调度算法的主要目的就是要优化调度，提高网格系统的计算性能。主要的性能指标如：负载均衡（Load Blancing）、最优跨度（Optimal Makespan）、服务质量QoS（Quality of Service）和经济原则（Economic Principles）等[5]。

负载均衡，主要保证各个资源节点的负载达到均衡，不会出现某些节点任务分配过多，而其它一些节点“空闲”的现象；最优跨度是关于调度的长度的一个指标，长度越短越好。调度的长度是从第一个任务开始运行到最后一个任务运行完毕经历的时间；服务质量，主要保障用户的任务计算和资源需求等内容。它是对性能、可靠性和可用性等参数的一种表示、协商和管理机制；经济原则，网格环境中的各个资源由于地理位置、机制和政策等因素的不同，其使用费用也不同，经济原则的目标是尽量减少网格调度的费用。endprint

1.2 网格调度算法现状

在现有的研究中，网格调度算法已有大量成果，其中比较经典的有[6-8]：UDA（User Direetly Assigning）算法即用户直接指派。这类算法主要是用户直接将自己的任务指派给某个网格资源去执行。用户往往不知道网格资源的状态如何。而网格调度器仅仅按照用户的指派，将相应任务发送给某个网格资源处理，其他的不多过问。OLB（Opportunistie Load Balaneing）即随机负载均衡算法，其算法思想是：随机的将某个任务分派给某个网格资源。这种方法通过随机分配任务尽量使所有资源都处于工作状态，对网格系统的负载均衡起到一定作用。MCT（Minimum Completion Time）即最小完成时间算法，其算法过程是：按照某一顺序调度所有任务，对每个任务简单的将其分配到最短完成预期的机器上。对于单个任务，该算法可以保证最短时间完成。MIN-MIN算法，其过程是将所有的待调度任务组成一个集合，从集合中找出预期完成时间最短的任务分配给相应的机器执行，从集合中删除任务，继续迭代，直到集合为空停止。MAX-MIN算法是选取最长执行时间作业进行执行，作业执行完毕后从集合中删除，再执行新的调度。

以上传统的调度算法更多的考虑对任务完成时间的优化。根据第一节网格调度问题的特点，网格调度除了最小化任务完成时间以外，还要考虑最小化资金花费、任务存在性等指标。该问题基于以下假设：每个网格资源单位占用时间花费的资金是不同的，显然，运算速度快的机器其单位时间花费要小。因此以此任务调度需要同时优化三个目标：时间最短、花费最小、任务存在性，因此这是一个典型的多目标优化问题，两个目标是一对相互矛盾的优化方向。显然，通过传统的网格调度算法很难解决该问题。

基于此本章提出了基于SBG-MOEA的网格调度算法。该算法首先对网格调度解空间进行遗传编码，通过基于静态贝叶斯博弈模型的多目标遗传算法找出符合网格调度的Pareto[9]解。因为基于博弈模型的多目标遗传算法存在非支配排序和博弈张力两方面的力量共同推动种群向Pareto前沿移动，因此该算法具有很强的全局寻优能力和快速收敛能力，适合于求解在线实时调度问题。

2 算法设计

2.1 问题描述及模型

设：有n个独立任务T=T■，T■，…，T■，其中T■为第i个任务；m个计算机资源R=R■，R■，…，R■表示，其中R■为第j个计算机节点；X■=1表示把任务T■分配到计算资源R■上执行，否则为0；ET是一个n*m矩阵，为任务T■在计算节点上R■的预期执行时间，任务调度时b■表示资源R■的最早可用时间；CT■表示任务T■在计算机节点R■上的预期完成时间，CT■=b■+ET■；m个计算机单位时间价格为D=D■，D■，…，D■；m个计算机的单位时间执行的任务数为S=S■，S■，…，S■。

根据以上定义，考虑到目前网格任务调度主要考虑的是：（1）完成任务t时间最小化。（2）完成整个任务的费用最低。（3）现实计算节点可能会因为硬件错误或软件错误不能保证任务的正常完成，因此还需要考虑任务的存在性即网格计算环境中任务在计算节点上能够正常执行完成的概率[10]，因此待优化目标可以描述为：

f■T，R，X=maxX■×b■×ET■ （1）

CT，R，X=■■λ■×X■×ET■ （2）

DT，R，X=■■D■×X■×ET■ （3）

其中：λ表示计算节点的失效率，CT，R，X代表了网格任务调度所发生的无效情况的累积，它间接地反映了网格任务调度的存在性，其值越小，网格任务的存在性越大。

2.2 算法描述

2.2.1 编码设计

多目标网格调度任务的解是x=x■，x■，…，x■，…，x■形式，其中n为任务数，x■∈R，它表示将任务T■分配给第x■个计算资源，因此本算法采用如下改进的比特编码设计：

n

L L L

0010…101 0100…001 … 1010…011

如果计算资源总数为m个，那么每一个T■需要染色体的长度L=「log■M？骎，编码的长度为n*「log■M？骎。

2.2.2 适应度函数

本文采用任务与资源相配对的关系构成了染色体基因，因为计算资源都是整数。因此，本算法中的变量值即每一段染色体的值也为整数，多目标网格调度优化问题可数学描述为如下的多目标优化问题：

MinF=f■，f■，f■

其中■，即目标函数f■T，R，X，CT，R，X和■■D■×X■×ET■的计算需要网格调度的参数信息，它由具体的问题来决定。这三个目标的求解都是最小化问题。

2.2.3 进化操作

针对具体的网格任务调度问题，在根据问题环境确定了染色体的编码方式和适应度函数计算方法之后，接下来就是要利用我们提出的算法进行优化。主要包括初始化种群、博弈过程和更新归档集等。其中博弈模型描述如下：

博弈参与者，本文设计的多目标网格任务调度主要有完成时间和费用以及生存性三个目标，因为博弈参与人有三个，表示为P=P■，P■，P■；他们会根据收益情况—一定概率选择合作或者惩罚策略，来取得最大的效用值。

种群在进化过程中对应这一个适应值矩阵，通过适应值矩阵我们可以求出收益矩阵，它表示其中一个参与者做出行动都会对另外一个参与者产生一定的收益，用U=■表示。那么他们的支付函数：每个博弈者的最终目标是最大化■u■，即各个博弈者通过博弈追求各个目标上的最优值。

战略空间定义为：S=s■，s■，这里s■代表合作战略，s■代表惩罚策略。

战略概率矩阵定义为：PS=■，它是指一个参与者对另一个参与者选择某种战略的概率。endprint

博弈的整个过程描述为：两个目标对应的博弈参与者根据概率选取策略并采取行动，为了追求自身利益的最大化它们在每次行动后根据损益情况更新混合概率，以实现自己的目标。策略的选择主要依据概率矩阵PS，矩阵的更新根据收益矩阵U。参与者对各个目标有个偏好程度，通过采取的策略来更新各个目标偏好。参与者对各个目标的偏好可以转换为权值向量w

=w■，w■，…，w■，当参与者i选定了一个战略后，将得到一个权值向量，根据这个权值向量计算种群个体的映射适应值，构造子种群，完成一次博弈过程。

2.2.4 算法流程

根据前面定义，整体算法流程如下：

Step1：初始化种群P0、概率矩阵PS，并初始化一个外部归档集，令迭代次数t=0；

Step2：每个博弈参与者给出自己的战略，并采取相应行动；

Step3：产生一个新的种群，令t=t+1；

Step4：计算种群的适应值矩阵FIT，找出其中的非支配个体；

Step5：更新归档集，按照每个博弈参与者的收益情况更新概率矩阵等；

Step6：判断是否满足终止条件，如果满足则输出最终解，算法结束，否则转到Step2。

3 实验仿真分析

3.1 实验参数设置

模拟的网格任务调度情况如下：

网格拥有计算资源数m，任务数n，则有的网格调度方式为m■个，这是一个NP问题：

（1）计算机上有被占用时间B=b■，b■，…，b■满足5，15上随机分布；

（2）任务的网格节点上执行时间满足10，100上的随机分布；

（3）每个节点的失效率λ■满足10-4，10-3上均匀分布；

（4）单位时间执行指令数S=S■，S■，…，S■在1，5上随机分布；

（5）计算机单位时间价格D与S满足函数关系D=gS=0.5*S■+1.5。

3.2 实验结果及分析

3.2.1 仿真实验一

（1）测试问题

本实验的主要目的是对比在不同数量的任务和资源情况下，多目标网格任务调度的优化效果，以及任务完成时间、完成费用和生存性两个指标之间的关系。

（2）参数设置

实验对比了在计算资源数为12 的情况下，任务数分别为300，400，600是求出的最优解的情况；还对比了任务数为400的情况下，计算资源数目分别为9和15的最优解情况。主要参数设置为：种群规模设为100，循环迭代为5 000，归档集大小100，交叉概率为0.6，变异概率为1/N。

（3）实验结果与分析

实验结果分别如图1～图5所示：

图1～图3主要对比了不同任务数下网格化调度结果，图4和图5对比了不同资源数量下的网格化调度结果。通过对上图结果进行比较分析，可以得出如下结论：

（1）多目标网格任务调度问题属于离散型的优化问题，其最优解是不连续的，形状是不规则的，当资源数和任务数不断增加时，图5将分离的Pareto解连接起来更好地刻画了网格调度问题的Pareto解的形状；

（2）网格化调度的完成时间和任务的生存性以及完成任务费用三个指标是相互冲突的，不可能同时获得三者的最优值，即不存在一种调度方式使三个目标同时处于最优的状态；

（3）在计算资源一定的情况下，随着调度任务数量的增加，网格化调度时间不断增加，网格任务调度的失效性不断增加，完成任务费用不断降低。

3.2.2 仿真实验二

（1）测试问题

本实验的主要目的是对比本文算法和NSGA-∏算法在求解多目标网格任务调度问题上的效果。

（2）参数设定

网格调度的任务数为400，计算资源为12，其余参数如上节，主要参数两种算法取相同的参数：种群规模设为100，循环迭代5 000次，归档集100，交叉概率0.6，变异概率0.002。

（3）实验结果与分析

实验进行50组，表1为两种算法的收敛性和分布性指标在50组实验求解结果的平均值。

从表1中我们可以看到，在解得分布性方面SBG-MOEA算法比NSGA∏差，但在解的收敛性分布方面明显优于NSGA∏。网格化调度问题是离散型多目标优化问题，真正的Pareto前沿形状也未必是均匀的，所以评价优化算法好坏主要看覆盖性指标。从表1得出在求解网格化调度问题上优于NSGA∏算法。

4 小 结

本文首先介绍了网格任务调度的基本知识，包括网格任务调度的主要特点，主要目标以及网格任务调度的经典算法。然后针对基于完成时间和完成价格以及生存性的多目标网格化调度问题，提出了基于博弈策略的SBG-MOEA的网格化调度算法。通过实验仿真和结果分析，表明该算法在解决多目标网格任务调度问题上具有较好的收敛性。

参考文献：

[1] 杜晓丽，蒋昌俊，徐国荣，等. 一种基于模糊聚类的网格DAG任务图调度算法[J]. 软件学报，2010，17（11）：2277-2285.

[2] 徐志伟，冯百明，李伟. 网络计算技术[M]. 北京：电子工业出版社，2004：93-124.

[3] 王树鹏，云晓春，余翔湛. 基于生存性和MakesPan的多目标网格任务调度算法研究[J]. 通信学报，2011，27（2）：42-49.

[4] 魏东. 基于混合蚁群算法的网格任务调度研究[D]. 哈尔滨：哈尔滨工程大学（硕士学位论文），2012：31-32.

[5] 张青. 网格环境下任务调度算法的应用研究[D]. 大连：大连海事大学（硕士学位论文），2013：13-14.

[6] 薛桂香. 基于智能优化算法的网格任务调度策略研究[D]. 天津：天津大学（博士学位论文），2010：7-8.

[7] 张维迎. 博弈论与经济信息学[M]. 上海：上海人民出版社，2008：106-135.

[8] 何建敏，刘春林，曹杰，等. 应急管理与应急系统——选址、调度与算法[M]. 北京：科技出版社，2007.

[9] Pareto V. Cours D' Economie politique， volume I and II[M]. Lausanne： F. Rouge， 1896.

[10] 王树鹏，云晓春，鱼翔湛. 基于生存性和 Makespan 的多目标网格任务调度算法研究[J]. 通信学报，2010，27（2）：42-49.endprint