正在加载图片...
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