D0I:10.13374/1.issnl00103.2007.12.044 第29卷第12期 北京科技大学学报 Vol.29 No.12 2007年12月 Journal of University of Science and Technology Beijing Dee.2007 基于运行时间权矩阵的网格服务匹配问题的优化解 郝卫东杨扬刘宏岚梁泉 北京科技大学信息工程学院，北京100083 摘要为解决在网格环境下满足用户作业对完成时间需求的服务资源调度问题，建立了包括独立匹配器在内的服务网格 三元模型，给出了该模型基于图论的形式化描述，证明了用户作业和服务资源之间完备匹配的充分必要条件.同时构造了基 于传感器反馈的网格服务匹配系统，给出了基于运行时间权矩阵的优化问题描述，并给出了基于离散事件动态系统理论的最 优化解算法·仿真研究表明，该算法比其他算法更能改善网格服务匹配系统的性能指标，在满足服务资源负载均衡的同时提 供了用户作业完成时间的服务质量保证： 关键词服务网格：匹配器：完备匹配：权矩阵：离散事件动态系统：图论 分类号TP393 随着计算技术和高性能通信网络技术的发展， 文引入了对作业运行时间的监控机制，从包含而又 以网格技术为核心的新一代网络计算环境已经成为 超越资源消费者和资源提供者的网格服务匹配系统 当前国际研究的一个热点和前沿领域山，人们对于 的角度提出网格资源调度的性能指标，消除了资源 网络计算环境下资源组织与管理的理论、机制和方 消费者和资源提供者之间存在的策略和目的不一致 法等问题的认识逐步深化，文献[2]提出了一种标 性；另一方面，本文结合所给出的网格服务匹配三元 准的资源管理协议，文献[3]较早地提出了协同服务 模型给出并证明了用户作业和服务资源之间实现完 的概念，并支持在多个管理域之间对资源使用情况 备匹配的充分必要条件；最后，在此基础上，本文揭 进行协调，文献[4]给出了一种标准的资源和任务需 示了基于作业运行时间权矩阵的完备匹配最优化解 求描述机制并在此基础上提出了资源匹配的框架， 的算法并与其他相关算法进行了比较 开放网格服务架构OGSA可把一切（包括资源 和任务)都抽象为开放的网格服务，从而为资源和任 1网格服务匹配模型及形式化描述 务的需求描述和发现、获取奠定了统一的机制和方 资源发现和服务匹配是资源管理中核心问 法，但是，在面向服务的体系结构下网格资源调度 题山.资源发现就是查询网格分布状态的过程，用 仍面临着严重的挑战，首先，不同管理域组织采用 于识别那些特征和状态与资源消费者需求相符合的 不同的策略操纵它们的资源，而且资源消费者和资 资源，服务匹配是从资源发现所提供的候选资源服 源提供者的目的可能不一致甚至相互抵触：其次，许 务集合中选择和指派资源的过程，该过程主要根据 多网格应用，比如电子商务或电子政务应用可中常 一些高层应用的服务质量指标而进行，比如完成时 常涉及的数据传输服务，需要多个资源并发分配，此 间、可靠性或代价.将资源发现从分配操作中分离 时需要通过适当的协作调度机制，使得一组资源，比 有着重要的影响，由于发现并不意味着任何承诺， 如本地网格(local grid),或称集群(cluster)1.o,在 可以将其构建为轻量级的非权威的操作.另一方 同一时段内可用.作业运行时间保证已经成为满足 面，当服务网格采用保证服务质量的预留策略时，服 日益增长的服务质量(QoS)要求的基础设施的核心 务匹配工作成了核心而基本无须资源发现操作， 功能，网格服务与普通Wb服务的一个重要区别 当前网格资源管理中大量行为集中在从资源提 是它引入了服务生命周期的概念，因此网格服务可 供者和资源消费者的角度理解并管理不同组织域内 以作为基础结构正常操作的一部分为了满足用户的 的服务策略，通常地，任务处理通过作业提交来实 某个需求而临时创建1，刀，借助网格服务的特征，本 现，而资源能力通过专门的服务质量接口来提 收稿日期：2006-08-19修回日期：2006-09-27 供[)，考虑到资源匹配不关心资源和服务的核心 基金项目：国家自然科学基金资助项目(No.90412012:No.60673160) 功能本身，而关心该功能执行的方式，比如请求的操 作者简介：郝卫东(1970一)，男，讲师，博士 作何时开始执行，需要多长时间完成，成本或费用如
基于运行时间权矩阵的网格服务匹配问题的优化解 郝卫东 杨 扬 刘宏岚 梁 泉 北京科技大学信息工程学院北京100083 摘 要 为解决在网格环境下满足用户作业对完成时间需求的服务资源调度问题建立了包括独立匹配器在内的服务网格 三元模型给出了该模型基于图论的形式化描述证明了用户作业和服务资源之间完备匹配的充分必要条件．同时构造了基 于传感器反馈的网格服务匹配系统给出了基于运行时间权矩阵的优化问题描述并给出了基于离散事件动态系统理论的最 优化解算法．仿真研究表明该算法比其他算法更能改善网格服务匹配系统的性能指标在满足服务资源负载均衡的同时提 供了用户作业完成时间的服务质量保证． 关键词 服务网格；匹配器；完备匹配；权矩阵；离散事件动态系统；图论 分类号 TP393 收稿日期：2006-08-19 修回日期：2006-09-27 基金项目：国家自然科学基金资助项目（No．90412012；No．60673160） 作者简介：郝卫东（1970—）男讲师博士 随着计算技术和高性能通信网络技术的发展 以网格技术为核心的新一代网络计算环境已经成为 当前国际研究的一个热点和前沿领域［1］．人们对于 网络计算环境下资源组织与管理的理论、机制和方 法等问题的认识逐步深化．文献［2］提出了一种标 准的资源管理协议文献［3］较早地提出了协同服务 的概念并支持在多个管理域之间对资源使用情况 进行协调文献［4］给出了一种标准的资源和任务需 求描述机制并在此基础上提出了资源匹配的框架． 开放网格服务架构 OGSA ［5］把一切（包括资源 和任务）都抽象为开放的网格服务从而为资源和任 务的需求描述和发现、获取奠定了统一的机制和方 法．但是在面向服务的体系结构下网格资源调度 仍面临着严重的挑战．首先不同管理域组织采用 不同的策略操纵它们的资源而且资源消费者和资 源提供者的目的可能不一致甚至相互抵触；其次许 多网格应用比如电子商务或电子政务应用［6］中常 常涉及的数据传输服务需要多个资源并发分配此 时需要通过适当的协作调度机制使得一组资源比 如本地网格（local grid）或称集群（cluster） ［16］在 同一时段内可用．作业运行时间保证已经成为满足 日益增长的服务质量（QoS）要求的基础设施的核心 功能．网格服务与普通 Web 服务的一个重要区别 是它引入了服务生命周期的概念因此网格服务可 以作为基础结构正常操作的一部分为了满足用户的 某个需求而临时创建［17］．借助网格服务的特征本 文引入了对作业运行时间的监控机制从包含而又 超越资源消费者和资源提供者的网格服务匹配系统 的角度提出网格资源调度的性能指标消除了资源 消费者和资源提供者之间存在的策略和目的不一致 性；另一方面本文结合所给出的网格服务匹配三元 模型给出并证明了用户作业和服务资源之间实现完 备匹配的充分必要条件；最后在此基础上本文揭 示了基于作业运行时间权矩阵的完备匹配最优化解 的算法并与其他相关算法进行了比较． 1 网格服务匹配模型及形式化描述 资源发现和服务匹配是资源管理中核心问 题［1］．资源发现就是查询网格分布状态的过程用 于识别那些特征和状态与资源消费者需求相符合的 资源．服务匹配是从资源发现所提供的候选资源服 务集合中选择和指派资源的过程该过程主要根据 一些高层应用的服务质量指标而进行比如完成时 间、可靠性或代价．将资源发现从分配操作中分离 有着重要的影响．由于发现并不意味着任何承诺 可以将其构建为轻量级的非权威的操作．另一方 面当服务网格采用保证服务质量的预留策略时服 务匹配工作成了核心而基本无须资源发现操作． 当前网格资源管理中大量行为集中在从资源提 供者和资源消费者的角度理解并管理不同组织域内 的服务策略通常地任务处理通过作业提交来实 现而资源能力通过专门的服务质量接口来提 供［8—9］．考虑到资源匹配不关心资源和服务的核心 功能本身而关心该功能执行的方式比如请求的操 作何时开始执行需要多长时间完成成本或费用如 第29卷 第12期 2007年 12月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．29No．12 Dec．2007 DOI:10．13374／j．issn1001－053x．2007．12．044
第12期 郝卫东等：基于运行时间权矩阵的网格服务匹配问题的优化解 ,1283 何等，因此，建立独立于资源提供者和资源消费者 是当且仅当对所有的S三V1有如下表达式成立： 的匹配服务，形成服务网格的简化三元模型，该模 Isl≤Ir(S)I (1) 型包括如下部分 其中，R(S)={v∈V2u:∈V1,且(vi,v)是网格 Jobmanager(作业管理器)：服务网格的服务消 G的一条边}. 费者代理，它作为终端用户的入口，提供作业提交、 证明：根据Hall定理，由于G是一个有向偶图， 查询和删除等的处理接口· 因此在G中存在完备匹配的充分必要条件就是 Servicemanager(服务管理器)：服务网格的服务 式(1) 提供者代理.它管理资源，并负责调度合适的作业 为了便于用计算机程序实现完备匹配的判断， 到该资源上运行 给出如下定理 Matchmaker(匹配器)：其功能是通过某种算法 定理2设存在网格G只V1,V2,E,W)符合 寻找消费者和提供者之间可能的匹配，并通知匹配 定义1，令D1表示作业集合V1中顶点的最小度， 的各方进行绑定操作. D2表示服务集合V2中顶点的最大度，那么存在满 下面从图论0]的角度给出上述网格三元模型 足定义2的完备匹配的充分必要条件是当且仅当 的定义 0KD2≤D1 (2) 令有向带权偶图G=V,E,W),其中顶点集 证明：先证必要性，设M是G中从V1到V2 V={v1,2,…,vn},边集E={e1,e2,…,em{,对 的一个完备的匹配，则有V1中的p=V1个顶点 于G中任意一条边(u1,)都存在实数心∈W与 与V2中对应的g=「V2个顶点构成匹配的边集， 之对应，称W为权集，必可将V分成两个子集V1 由定义2知0<p≤q· 和V2,并且满足V1∩V2=0,V1UV2=V,使得 又由于V1中p个顶点至少关联pD1条边，而 G中任意一条边e(e时=(vi,)∈E)的两个端点， V2中q个顶点至多关联qD2条边，若要存在从V1 一个属于V1(如v:∈V1),另一个属于V2(如v∈ V2) 到V2的一个完备的匹配，则必然有pD1≥gD2· 又由于D2>0,D1>0系统才有意义，所以 根据上面的描述，给出服务网格的定义如下， 0<D2≤D1· 定义1定义网格G为有向带权偶图G= 再证充分性，设网格作业S三V1,由于作业集 (V1,V2,E,)的形式，其中用V1表示网格作业 合V1中顶点的最小度是D1,因此对任何属于V1 集合，V2表示网格服务集合，记网格作业集合的作 的网格作业子集S,其中的顶点至少与D1S条边 业个数为p=V1,网格服务集合中的服务个数为 相邻，即D1S给出了S中顶点关联的边数的下 q=Vz;E表示网格作业和网格服务之间可能存 界估计值， 在的匹配；W表示网格作业和网格服务之间某个匹 配的数量指标，本文中赋予它作业完成时间的含义， 设R(S)=∈Vzv:∈V1,且(ui,)是网 格G的一条边，由于服务集合V2中顶点的最大 即0：∈W表示在服务j上完成作业i所花费的时 间，其中=1,2，…，p;=1,2,…,q 度是D2,因此对任何属于V1的网格作业子集S, 定义2设存在网格GV1,V2,E,W)符合 最多有D2R(S)条边与R(S)中的顶点关联，所 定义1，若存在E*三E,使得E*中任意两边均不相 以D2R(S)给出了S中顶点关联的边数的上界 邻，则称E为G中的一个匹配.若在E中再加 估计值 上任意一条边e,E*U1el中必存在着相邻的边，则 因此，比较这两个估计值可得如下不等式： 称E为G中极大匹配，G中边数最多的匹配称为 D1S≤D2R(S) (3) 最大匹配，其元素个数称为G的匹配数，若E*是 已知0<Dn2≤D1,有： 一个最大匹配，且|E*I=min V1,|V2I{,则称 DzR(S)|≤D1lR(S)l (4) M为G中的一个完备匹配， 根据式(3)有： 在上述定义的基础上，根据Hal定理o),可得 D1lsl≤D2R(S)l≤D1lR(S)l,(5) 如下定理， 推出|S|≤|R(S).根据定理1得存在从作 定理1设存在网格G只V1,V2,E,W)符合 业V1到服务V2的完备匹配 定义1，若存在网格作业S二V1,则存在满足定义2 特别地，当D2=D三t≥1时定理2仍成立， 的与之对应的网格服务的完备匹配的充分必要条件 称其为t条件
何等．因此建立独立于资源提供者和资源消费者 的匹配服务形成服务网格的简化三元模型．该模 型包括如下部分． Jobmanager（作业管理器）：服务网格的服务消 费者代理．它作为终端用户的入口提供作业提交、 查询和删除等的处理接口． Servicemanager（服务管理器）：服务网格的服务 提供者代理．它管理资源并负责调度合适的作业 到该资源上运行． Matchmaker（匹配器）：其功能是通过某种算法 寻找消费者和提供者之间可能的匹配并通知匹配 的各方进行绑定操作． 下面从图论［10］的角度给出上述网格三元模型 的定义． 令有向带权偶图 G＝〈V EW〉其中顶点集 V ＝｛v1v2…v n｝边集 E＝｛e1e2…em｝对 于 G 中任意一条边（ vivj）都存在实数 wij∈ W 与 之对应称 W 为权集必可将 V 分成两个子集 V1 和 V2并且满足 V1∩ V2＝∅V1∪ V2＝ V 使得 G 中任意一条边 eij（eij＝（ vivj）∈ E）的两个端点 一个属于 V1（如 vi∈ V1）另一个属于 V2（如 vj∈ V2）． 根据上面的描述给出服务网格的定义如下． 定义1 定义网格 G 为有向带权偶图 G ＝ 〈V1V2EW〉的形式．其中用 V1 表示网格作业 集合V2 表示网格服务集合记网格作业集合的作 业个数为 p＝｜V1｜网格服务集合中的服务个数为 q＝｜V2｜；E 表示网格作业和网格服务之间可能存 在的匹配；W 表示网格作业和网格服务之间某个匹 配的数量指标本文中赋予它作业完成时间的含义 即 wij∈ W 表示在服务 j 上完成作业 i 所花费的时 间其中 i＝12…p；j＝12…q． 定义2 设存在网格 G＝〈V1V2EW〉符合 定义1若存在 E ∗⊆ E使得 E ∗中任意两边均不相 邻则称 E ∗为 G 中的一个匹配．若在 E ∗ 中再加 上任意一条边 eE ∗∪｛e｝中必存在着相邻的边则 称 E ∗为 G 中极大匹配．G 中边数最多的匹配称为 最大匹配其元素个数称为 G 的匹配数．若 E ∗是 一个最大匹配且｜E ∗｜＝min｛｜V1｜｜V2｜｝则称 M 为 G 中的一个完备匹配． 在上述定义的基础上根据 Hall 定理［10］可得 如下定理． 定理1 设存在网格 G＝〈V1V2EW〉符合 定义1若存在网格作业 S⊆ V1则存在满足定义2 的与之对应的网格服务的完备匹配的充分必要条件 是当且仅当对所有的 S⊆ V1 有如下表达式成立： ｜S｜≤｜R（ S）｜ （1） 其中R（ S）＝｛vj∈ V2｜vi∈ V1且（ vivj）是网格 G 的一条边｝． 证明：根据 Hall 定理由于 G 是一个有向偶图 因此在 G 中存在完备匹配的充分必要条件就是 式（1）． 为了便于用计算机程序实现完备匹配的判断 给出如下定理． 定理2 设存在网格 G＝〈V1V2EW〉符合 定义1令 Dv1表示作业集合 V1 中顶点的最小度 Dv2表示服务集合 V2 中顶点的最大度那么存在满 足定义2的完备匹配的充分必要条件是当且仅当 0＜ Dv2≤ Dv1 （2） 证明：先证必要性．设 M 是 G 中从 V1 到 V2 的一个完备的匹配则有 V1 中的 p＝｜V1｜个顶点 与 V2 中对应的 q＝｜V2｜个顶点构成匹配的边集 由定义2知0＜ p≤q． 又由于 V1 中 p 个顶点至少关联 pDv1条边而 V2 中 q 个顶点至多关联 qDv2条边若要存在从 V1 到 V2 的一个完备的匹配则必然有 pDv1≥qDv2． 又由于 Dv2＞0Dv1＞0系统才有意义所以 0＜ Dv2≤ Dv1． 再证充分性．设网格作业 S⊆ V1由于作业集 合 V1 中顶点的最小度是 Dv1因此对任何属于 V1 的网格作业子集 S其中的顶点至少与 Dv1｜S｜条边 相邻即 Dv1｜S｜给出了 S 中顶点关联的边数的下 界估计值． 设 R（ S）＝｛vj∈ V2｜vi∈ V1且（ vivj）是网 格 G 的一条边｝由于服务集合 V2 中顶点的最大 度是 Dv2因此对任何属于 V1 的网格作业子集 S 最多有 Dv2｜R（ S）｜条边与 R（ S）中的顶点关联所 以 Dv2｜R（ S）｜给出了 S 中顶点关联的边数的上界 估计值． 因此比较这两个估计值可得如下不等式： Dv1｜S｜≤ Dv2｜R（ S）｜ （3） 已知0＜ Dv2≤ Dv1有： Dv2｜R（ S）｜≤ Dv1｜R（ S）｜ （4） 根据式（3）有： Dv1｜S｜≤ Dv2｜R（ S）｜≤ Dv1｜R（ S）｜ （5） 推出｜S｜≤｜R（ S）｜．根据定理1得存在从作 业 V1 到服务 V2 的完备匹配． 特别地当 Dv2＝ Dv1≡ t≥1时定理2仍成立 称其为 t 条件． 第12期 郝卫东等： 基于运行时间权矩阵的网格服务匹配问题的优化解 ·1283·
.1284 北京科技大学学报 第29卷 该最优化问题的求解难点是其中不仅涉及连续 2网格服务匹配问题及其最优化解 变化的时间变量D,而且涉及代表特定事件是否 在网格环境下，为了保证电子商务或电子政务 发生的取离散值(1或0)的离散事件变量e,·当i, 等核心多媒体应用的服务质量(Q$),采用的典型 j的维数比较少时，可以用基于定义2的图形方法 策略是引入预留机制.引入预留使得用户有可能知 求解，但当i,j的维数比较多时，须采用矩阵统一 道所需要的服务资源的能力，比如网络带宽、CPU 表达连续时间变量W和离散事件变量E,把求解完 时钟周期和硬盘空间容量，但是可能不知道这些资 备匹配的过程看作一个对矩阵进行不断变换的逐步 源将执行什么应用，事实上，用户只希望其应用在 收敛的动态过程，借助离散事件动态系统理论进行 所给的资源等级上可保证任务的执行而不关心也不 求解。该最优化问题求解中的矩阵变换是根据如下 了解执行任务所需要的具体资源性能：另一方面，资 的性质：如果从权矩阵W=(心)的一行（列）各元 源提供者也不希望公开其资源能力将如何使用的细 素分别减去该行（列）的最小元素，得到新矩阵W'= 节信息而通常只承诺用户可获得的对资源能力的保 (心可)，那么以W为系数矩阵的匹配问题的最优化 证.因此从控制原理的角度分析，包含作业和 解E=(e)和原问题的最优解相同3]， Jobmanager、服务和Service Manager的网格可被看 因此，可得该最优化问题求解算法如下： 作一个黑箱或灰箱，从控制系统的性能指标看，一 (1)置匹配矩阵E的各个元素的值为0： 般而言，服务匹配方案的主要目的是负载平衡：但对 (②)从权矩阵的每行元素减去各行的最小元 于预留的服务而言，除了要保证各个服务分担负载， 素，如果某列存在全部非零元素时，再从该列减去最 还必须考虑用户的满意程度，避免某些用户的作业 小元素，使得各行各列至少有一个为零元素： 执行时间过长， (3)由新的权矩阵W中零元素最少的行开始 通过引入传感器(sensor),比如NetLoggerl山， ARM2]工具，作为作业运行时间的监控机制，以检 选出一处零元素，即选择i和j,使w=0; 测当前在资源上运行的任务的状态，比如作业启动、 (4)令选出的零元素0对应的匹配矩阵的元 素e=1; 作业正在运行、作业挂起、作业激活、作业完成等信 息，并记录相关状态事件发生的时间戳轨迹，可以刻 (5)令选出的零元素0所在的权矩阵W中第 画出网格作业的完成时间等反馈信息，对于现在的 i行、第j列的其他零元素取某个极大值，如可取 CPU处理器，如SPARC V9、Itanium都包含高精度 心中最大元素的值或取计算精度允许的最大值； 的时钟，Intel Pentium系列处理器还具有用户级指 (6)如果匹配矩阵E中每行每列都有且仅有 令可实现对高精度时钟的低延迟访问，这进一步保 一个元素的值为1，则求解完成，并记E=E*,否则 证了网格作业运行时间检测的准确性 返回第(3)步 为了既满足负载平衡，又保证作业执行时间， 上述算法中E的维数是t,符合完备匹配的t Match Maker必须在有关作业和服务的运行状态的 条件，因此该算法一定收敛 反馈信息如作业完成时间心：基础上，求解出作业 3计算机仿真和系统实现 和服务之间的完备匹配 下面给出符合定义1和定义2的满足t条件的 取以下数据进行仿真，一个任务包含并发作业 网格作业网格服务匹配的优化问题的数学形式 A、B、C和D,它们分别在集群服务甲、乙、丙、丁上 求匹配e与=ei,使得mim匀之 运行时的完成时间权矩阵W如下： 0前e时其中 3010090 40 心∈W表示在服务j上完成作业i所花费的时间， 120 40 160 130 e的取值范围为1或0. 80120 140 130 1,指派作业i到服务j上运行时 50 80 100 70 e时一0，不指派作业i到服务j上运行时 运用MATLAB软件包根据上述匹配算法可求 约束条件： 得匹配矩阵E*如下： 0 =1,j=1,2,…,t 0 0 E 1 0 合y=1,i=1,2,…,t 001
2 网格服务匹配问题及其最优化解 在网格环境下为了保证电子商务或电子政务 等核心多媒体应用的服务质量（QoS）采用的典型 策略是引入预留机制．引入预留使得用户有可能知 道所需要的服务资源的能力比如网络带宽、CPU 时钟周期和硬盘空间容量但是可能不知道这些资 源将执行什么应用．事实上用户只希望其应用在 所给的资源等级上可保证任务的执行而不关心也不 了解执行任务所需要的具体资源性能；另一方面资 源提供者也不希望公开其资源能力将如何使用的细 节信息而通常只承诺用户可获得的对资源能力的保 证．因 此 从 控 制 原 理 的 角 度 分 析包 含 作 业 和 Jobmanager、服务和 ServiceManager 的网格可被看 作一个黑箱或灰箱．从控制系统的性能指标看一 般而言服务匹配方案的主要目的是负载平衡；但对 于预留的服务而言除了要保证各个服务分担负载 还必须考虑用户的满意程度避免某些用户的作业 执行时间过长． 通过引入传感器（sensor）比如 NetLogger ［11］、 ARM ［12］工具作为作业运行时间的监控机制以检 测当前在资源上运行的任务的状态比如作业启动、 作业正在运行、作业挂起、作业激活、作业完成等信 息并记录相关状态事件发生的时间戳轨迹可以刻 画出网格作业的完成时间等反馈信息．对于现在的 CPU 处理器如 SPARC V9、Itanium 都包含高精度 的时钟Intel Pentium 系列处理器还具有用户级指 令可实现对高精度时钟的低延迟访问这进一步保 证了网格作业运行时间检测的准确性． 为了既满足负载平衡又保证作业执行时间 MatchMaker 必须在有关作业和服务的运行状态的 反馈信息如作业完成时间 wij 基础上求解出作业 和服务之间的完备匹配． 下面给出符合定义1和定义2的满足 t 条件的 网格作业—网格服务匹配的优化问题的数学形式． 求匹配 eij ＝ e ∗ ij 使得 min ∑ t i＝1 ∑ t j＝1 wijeij．其中 wij∈ W 表示在服务 j 上完成作业 i 所花费的时间． eij的取值范围为1或0． eij＝ 1 指派作业 i 到服务 j 上运行时 0 不指派作业 i 到服务 j 上运行时 约束条件： ∑ t i＝1 eij ＝1j ＝12…t ∑ t j＝1 eij ＝1i ＝12…t 该最优化问题的求解难点是其中不仅涉及连续 变化的时间变量 wij而且涉及代表特定事件是否 发生的取离散值（1或0）的离散事件变量 eij．当 i j 的维数比较少时可以用基于定义2的图形方法 求解．但当 ij 的维数比较多时须采用矩阵统一 表达连续时间变量 W 和离散事件变量 E把求解完 备匹配的过程看作一个对矩阵进行不断变换的逐步 收敛的动态过程借助离散事件动态系统理论进行 求解．该最优化问题求解中的矩阵变换是根据如下 的性质：如果从权矩阵 W＝（ wij）的一行（列）各元 素分别减去该行（列）的最小元素得到新矩阵 W′＝ （ w′ij）那么以 W′为系数矩阵的匹配问题的最优化 解 E ∗＝（e ∗ ij ）和原问题的最优解相同［13］． 因此可得该最优化问题求解算法如下： （1） 置匹配矩阵 E 的各个元素的值为0； （2） 从权矩阵的每行元素减去各行的最小元 素如果某列存在全部非零元素时再从该列减去最 小元素使得各行各列至少有一个为零元素； （3） 由新的权矩阵 W′中零元素最少的行开始 选出一处零元素即选择 i 和 j使 w′ij＝0； （4） 令选出的零元素 w′ij对应的匹配矩阵的元 素 eij＝1； （5） 令选出的零元素 w′ij所在的权矩阵 W′中第 i 行、第 j 列的其他零元素取某个极大值如可取 w′ij中最大元素的值或取计算精度允许的最大值； （6） 如果匹配矩阵 E 中每行每列都有且仅有 一个元素的值为1则求解完成并记 E＝ E ∗否则 返回第（3）步． 上述算法中 E 的维数是 t符合完备匹配的 t 条件因此该算法一定收敛． 3 计算机仿真和系统实现 取以下数据进行仿真．一个任务包含并发作业 A、B、C 和 D它们分别在集群服务甲、乙、丙、丁上 运行时的完成时间权矩阵 W 如下： W＝ 30 100 90 40 120 40 160 130 80 120 140 130 50 80 100 70 ． 运用 MATLAB 软件包根据上述匹配算法可求 得匹配矩阵 E ∗如下： E ∗＝ 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 ． ·1284· 北 京 科 技 大 学 学 报 第29卷
第12期 郝卫东等：基于运行时间权矩阵的网格服务匹配问题的优化解 ,1285 因此，网格作业和网格服务的完备匹配是：甲完 匹配策略下网格作业的总完成时间分布曲线、 成C作业，乙完成B作业，丙完成D作业，丁完成A 由图1可见，最优策略的编号为22，其总运行 作业，此时总完成时间为： 时间为260ms,与基于权矩阵的服务匹配优化算法 的结果相同；而最差策略的编号是10，其总运行时 min220je=w14十02十031十w43= =1=1 间为470ms,不同的服务匹配策略之间的总运行时 40+40+80+100=260ms 间最大相差210ms·在穷举算法下各种策略的平均 多个作业并发运行时整个任务的完成时间为完 总运行时间为371.25ms,本文给出的优化算法与之 成D作业的时间100ms 相比使服务匹配系统性能改善42.78%. 事实上，在本实例中存在最多C1C3C2C1=24 当网格作业和网格服务的数量增加时，穷举算 种不同的匹配策略，图1是采用穷举搜索法时不同 法是低效的，而且可能产生组合爆炸。因此，考虑与 500 智能搜索策略一爬山法一相比较，并以运行时 400 间为爬山法的启发条件，计算从W(1,1)=D11开 300 200 始，此时运行时间为30ms,此后以运行时间增长最 100 小为目标进行搜索，计算结果如图2所示，此时的 优化策略是甲完成A作业，乙完成B作业，丙完成 10 1316 19 22 匹配策略编号 C作业，丁完成D作业，总运行时间为280ms·与本 文给出的优化算法相比，爬山法给出的是次优解，而 图1不同匹配策略运行结果分析 Fig.1 Result of different matchmaking strategies 最优解与之相比使服务匹配系统性能改善7,69% 1.1) 30+40-70m5 30+160=190m5s 30+130-160ms 2,2) 23) 2,4) 70+140-210m5 70+130=200m5 160+130-290ms 160+120-280ms 33) 3.4) 3,4) 3.2) 210+70-280ms 200+100=300ms290+80=370m5 280+70-350m5 肌4,4) 肌4,3) 4,2) 4,4) 图2爬山法的搜索结果 Fig.2 Result of the mountain climbing method 为了在网格系统上实现本文给出的优化算法， 数关系，因此上述优化算法可进一步推广并应用于 采用MATLAB COM Builder将程序编译为单独的 降低请求网格资源的经济成本，这对网格服务匹配 ActiveX对象，并由VB.Net语言编写程序调用该对 系统的商业化运营有潜在促进价值， 象.其硬件环境为：曙光天潮TC4000L超级计算机 系统作为网格计算集群系统，曙光天阔R220A服务 参考文献 器作为集群节点服务器，曙光天阔R220XP作为网 [1]Foster I.Kesselman C.The Grid 2:Blueprint for a New Com- 格集群管理服务器， puting Infrastructure.2nd ed.San Fransisco:Morgan Kaufmann Publishers Inc,2004:1 4结论 [2]Czajkowski K,Foster I,Karonis N,et al.A resource manage- ment architecture for metacomputing systems//4th workshop on 本文通过在网格服务模型中引入匹配器，使用 Job Scheduling Strategies for Parallel Processing.Heidelberg: 代表作业运行时间的权矩阵，给出了网格作业一网 Springer-Verlag Publishers Ine.1998:62 格服务匹配的优化解，基于图论证明了服务匹配存 [3]Czajkowski K.Foster I.Kesselman C.Co-allocation services for 在的充分必要条件，经仿真研究表明，与其他算法 computational Grids//8th IEEE International Symposium on High 相比，该优化算法可使服务匹配系统的性能取得较 Performance Distributed Computing.Los Alamitos:IEEE Com- puter Society Press.1999:553 为明显的改善 [4]Raman R.Livny M.Solomon M.Matchmaking:distributed re 考虑到作业完成时间与完成作业的费用存在函 source management for high throughput computing7th IEEE
因此网格作业和网格服务的完备匹配是：甲完 成 C 作业乙完成 B 作业丙完成 D 作业丁完成 A 作业．此时总完成时间为： min ∑ t i＝1 ∑ t j＝1 wijeij＝ w14＋ w22＋ w31＋ w43＝ 40＋40＋80＋100＝260ms． 多个作业并发运行时整个任务的完成时间为完 成 D 作业的时间100ms． 事实上在本实例中存在最多 C 1 4C 1 3C 1 2C 1 1＝24 种不同的匹配策略图1是采用穷举搜索法时不同 图1 不同匹配策略运行结果分析 Fig．1 Result of different matchmaking strategies 匹配策略下网格作业的总完成时间分布曲线． 由图1可见最优策略的编号为22其总运行 时间为260ms与基于权矩阵的服务匹配优化算法 的结果相同；而最差策略的编号是10其总运行时 间为470ms不同的服务匹配策略之间的总运行时 间最大相差210ms．在穷举算法下各种策略的平均 总运行时间为371∙25ms本文给出的优化算法与之 相比使服务匹配系统性能改善42∙78％． 当网格作业和网格服务的数量增加时穷举算 法是低效的而且可能产生组合爆炸．因此考虑与 智能搜索策略———爬山法———相比较并以运行时 间为爬山法的启发条件计算从 W （11）＝ w11开 始此时运行时间为30ms此后以运行时间增长最 小为目标进行搜索计算结果如图2所示．此时的 优化策略是甲完成 A 作业乙完成 B 作业丙完成 C 作业丁完成 D 作业总运行时间为280ms．与本 文给出的优化算法相比爬山法给出的是次优解而 最优解与之相比使服务匹配系统性能改善7∙69％． 图2 爬山法的搜索结果 Fig．2 Result of the mountain climbing method 为了在网格系统上实现本文给出的优化算法 采用 MATLAB COM Builder 将程序编译为单独的 ActiveX 对象并由 VB．Net 语言编写程序调用该对 象．其硬件环境为：曙光天潮 TC4000L 超级计算机 系统作为网格计算集群系统曙光天阔 R220A 服务 器作为集群节点服务器曙光天阔 R220XP 作为网 格集群管理服务器． 4 结论 本文通过在网格服务模型中引入匹配器使用 代表作业运行时间的权矩阵给出了网格作业—网 格服务匹配的优化解基于图论证明了服务匹配存 在的充分必要条件．经仿真研究表明与其他算法 相比该优化算法可使服务匹配系统的性能取得较 为明显的改善． 考虑到作业完成时间与完成作业的费用存在函 数关系因此上述优化算法可进一步推广并应用于 降低请求网格资源的经济成本这对网格服务匹配 系统的商业化运营有潜在促进价值． 参 考 文 献 ［1］ Foster IKesselman C．The Grid2：Blueprint for a New Computing Infrastructure．2nd ed．San Fransisco：Morgan Kaufmann Publishers Inc2004：1 ［2］ Czajkowski KFoster IKaronis Net al．A resource management architecture for metacomputing systems∥4th workshop on Job Scheduling Strategies for Parallel Processing．Heidelberg： Springer-Verlag Publishers Inc1998：62 ［3］ Czajkowski KFoster IKesselman C．Co-allocation services for computational Grids∥8th IEEE International Symposium on High Performance Distributed Computing．Los Alamitos：IEEE Computer Society Press1999：553 ［4］ Raman RLivny MSolomon M．Matchmaking：distributed resource management for high throughput computing∥7th IEEE 第12期 郝卫东等： 基于运行时间权矩阵的网格服务匹配问题的优化解 ·1285·
,1286. 北京科技大学学报 第29卷 International Symposium on High Performance Distributed Com- 性能分析.计算机研究与发展，2005,42(8)：1397 puting.Los Alamitos:IEEE Computer Society Press,1998:140 [10]殷剑宏，吴开亚.图论及其算法.安微：中国科学技术大学出 [5]Foster I.Kesselman C,Nick J.et al.Grid services for distribut- 版社，2003：192 ed system integration.IEEE Comput.2002.35(6):37 [11]Tierney B.Johnstone W,Crowley B.et al.The NetLogger [6们郝卫东，杨扬，王先梅，等。网络环境下的电子商务与电子政 methodology for high performance distributed systems perfor- 务建设.北京：清华大学出版社，2006：112 mance analysis/7th IEEE International Symposium on High [7]Foster I.Jennings N.Kesselman C.Brain meets brawn:Why Performance Distributed Computing.Los Alamitos:IEEE Com- grid and agents need each other3th Internatinal Joint Confer puter Society Press.1998:28 ence on Autonomous Agents and Multiagent Systems.New [12]The Open Group.C807 Systems Management:Application Re- York,2004:8 sponse Measurement (ARM)API.Berkshire:The Open Group [8]单志广，戴琼海，林闯，等.W山请求分配和选择的综合方案 Publishers Inc,1998:1 与性能分析.软件学报，2001,12(3)：355 [13]杨扬，离散事件系统理论与柔性制造系统，北京：冶金工业 [9]曲绍刚，杨广文，林闯，等，基于完成时间的任务分配方案与 出版社，1994：219 Optimized solution to the grid services matchmaking problem based on running time weight matrix HAO Weidong,YANG Yang,LIU Honglan,LIA NG Quan Information Engineering School.University of Science and Technology Beijing.Beijing 100083.China ABSTRACT In order to solve the resource scheduling problem in service grid environment to guarantee the need of user jobs complete time,an independent matchmaker was introduced into the three-element service grid model.The service grid model was formally illustrated based on the graph theory,and the necessary and suffi- cient conditions of complete match of user jobs and grid service resources were also proved.A grid services matchmaking system was const ructed on the base of sensor feedback.The optimal matchmaking problem of the system was formally illustrated based on the running time weight matrix,and the optimal solution arithmetic was proposed based on the discrete event dynamic system theory.Simulation analysis shows that the arithmetic can improve the QoS (quality of services)performance parameter of the grid services matchmaking system,pro- vide the user jobs completed time guarantee and meet the load balance need of grid service resources. KEY WORDS service grid;matchmaker;complete match;weight matrix;discrete event dynamic system the- ory;graph theory
International Symposium on High Performance Distributed Computing．Los Alamitos：IEEE Computer Society Press1998：140 ［5］ Foster IKesselman CNick Jet al．Grid services for distributed system integration．IEEE Comput200235（6）：37 ［6］ 郝卫东杨扬王先梅等．网络环境下的电子商务与电子政 务建设．北京：清华大学出版社2006：112 ［7］ Foster IJennings NKesselman C．Brain meets brawn：Why grid and agents need each other∥3th Internatinal Joint Conference on Autonomous Agents and Mult-i agent Systems． New York2004：8 ［8］ 单志广戴琼海林闯等．Web 请求分配和选择的综合方案 与性能分析．软件学报200112（3）：355 ［9］ 曲绍刚杨广文林闯等．基于完成时间的任务分配方案与 性能分析．计算机研究与发展200542（8）：1397 ［10］ 殷剑宏吴开亚．图论及其算法．安徽：中国科学技术大学出 版社2003：192 ［11］ Tierney BJohnstone WCrowley Bet al．The NetLogger methodology for high performance distributed systems performance analysis ∥7th IEEE International Symposium on High Performance Distributed Computing．Los Alamitos：IEEE Computer Society Press1998：28 ［12］ The Open Group．C807Systems Management：Application Response Measurement （ARM） API．Berkshire：The Open Group Publishers Inc1998：1 ［13］ 杨扬．离散事件系统理论与柔性制造系统．北京：冶金工业 出版社1994：219 Optimized solution to the grid services matchmaking problem based on running time weight matrix HAO WeidongY A NG Y angLIU HonglanLIA NG Quan Information Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China ABSTRACT In order to solve the resource scheduling problem in service grid environment to guarantee the need of user jobs complete timean independent matchmaker was introduced into the three-element service grid model．The service grid model was formally illustrated based on the graph theoryand the necessary and sufficient conditions of complete match of user jobs and grid service resources were also proved．A grid services matchmaking system was constructed on the base of sensor feedback．The optimal matchmaking problem of the system was formally illustrated based on the running time weight matrixand the optimal solution arithmetic was proposed based on the discrete event dynamic system theory．Simulation analysis shows that the arithmetic can improve the QoS （quality of services） performance parameter of the grid services matchmaking systemprovide the user jobs completed time guarantee and meet the load balance need of grid service resources． KEY WORDS service grid；matchmaker；complete match；weight matrix；discrete event dynamic system theory；graph theory ·1286· 北 京 科 技 大 学 学 报 第29卷