（计算机应用技术专业论文）基于合作博弈的网格资源管理研究.pdf

摘要 摘要 网格代表了一种先进的技术和基础设旌，其目的是将地理上广泛分布的、异 构的资源集合起来进行共享。由于网格资源的广域性、共享性、异构性、自相似 性等特征，使得网格资源管理成为网格研究的一个重点。网格资源管理将对网格 环境中应用程序的运行产生重要影响，因此，网格资源管理技术的研究对网格计 算技术的发展有着重大的实际意义和研究价值。 基于市场的网格计算模型中，用户和资源之间具有各自的策略，出于自私性 考虑，双方都希望自己的利益最大化，这就需要合理的资源管理方法来平衡这一 矛盾。 本文在研究过程中，主要借鉴了基于市场的网格计算模型和经济学领域颇有 成果的博弈论思想，将网格环境中资源的分配问题转化为合作博弈问题，通过寻 找合作博弈的纳什均衡点来解决资源的分配，基于此，本文提出了一种基于合作 博弈的网格资源管理算法c g r m 和作业调度算法g s a c g r m 。 c g r m 算法思想是将资源作为合作博弈的参与者，作业在资源上的等待时 间作为合作博弈的收益函数，网格环境中的作业到来是一个随机过程，针对某一 时间提交到网格环境中的作业量，通过合作博弈寻找资源之间接收作业量的纳什 均衡点，形成资源合作联盟，来满足用户应用程序的需求。g s a c g r m 参考 m i n m i n 的作业调度策略，将网格中的作业按照资源接收作业的能力进行重新整 合，为新的作业队列设置作业信息，提交到目标资源上进行处理，期望作业在目 标资源上的等待时间最短，并且资源的负载在此次博弈过程中的达到均衡。 文章最后用g r i d s i m 模拟器实现并验证了算法，对实验数据进行了合理的分 析和说明。 关键词网格计算；网格资源；合作博弈；n a s h 均衡 a b s t r a c t a b s t r a c t g r i dc o m p u t i n gr e p r e s e n t sa nm v a n c e dt e c h n o l o g ya n df u n d a m e n t a li n s t r u m e n t t og a t h e ra n ds h a r ev a r i o u sw i d e l yd i s t r i b u t e da n dh e t e r o g e n e o u sr e s o u r c e s s i n c eg r i d r e s o u r c e sa r e w i d e l yl o c a t e d ， s h a r e d b y d i f f e r e n tu s e r s ，h e t e r o g e n e o u sa n d s e l f - r e s e m b l i n g ，t h em a n a g e m e n to fg r i dr e s o u r c e si so n eo ft h ek e yf a c t o r si ng r i d s t u d ya n di so fg r e a ts i g n i f i c a n c et ot h eo p e r a t i o no fa p p l i c a t i o ni ng r i de n v i r o n m e n t t h e r e f o r e ，t h es t u d yo ft h em a n a g e m e n to fg r i dr e s o u r c e si so fb o t hg r e a tp r a c t i c a l a n dt h e o r e t i c a lv a l u ei nt h ed e v e l o p m e n to fg r i dc o m p u t i n gt e c h n o l o g y i nt h em a r k e t - b a s e dg r i dc o m p u t i n gm o d e l s ，u s e r sa n dr e s o u r c eh o l d e r s ，o u to f t h ec o n s i d e r a t i o no fs e l fi n t e r e s t ，h a v et h e i ro w nr e s p e c t i v es t r a t e g i e s ，h o p i n gt o m a x i m i z et h e i ro w nb e n e f i t s t h e r e f o r e ，ar e a s o n a b l er e s o u r c em a n a g e m e n tm e t h o di s n e e d e dt oa c h i e v eab a l a n c ea m o n gu s e r sa n dr e s o u r c eh o l d e r s b ya p p l y i n gt h em a r k e t - b a s e dg r i dc o m p u t i n gm o d e la n dt h ev e r yp r o d u c t i v e g a m et h e o r yi ne c o n o m i cr e s e a r c h ，t h i sp a p e rt u r n st h er e s o u r c ed i s t r i b u t i o ni s s u ei n g r i de n v i r o n m e n tt oac o o p e r a t i v eg a m ei s s u ea n d s o l v e st h i sp r o b l e mb yf i g u r i n go u t an a s he q u i l i b r i u mp o i n ti nt h i sc o o p e r a t i v eg a m e s t a r t i n gf r o mt h i sp o i n t ，t h i sp a p e r h a sp u tf o r w a r dan e wg a dc o m p u t i n gm e t h o dt om a n a g eg r i dr e s o u r c e s ，n a m e l y , c o o p e r a t i o ng a m er e s o u r c em a n a g e m e n t ( c g r m ) a n dan e w g r i d l e t ss c h e d u l i n g a l g o r i t h mb a s e do nc g r m ( g s a - c g r m ) i nt h i sa l g o r i t h m ，r e s o u r c e sa r et a k e na sp l a y e r si nt h ec o o p e r a t i v eg a m e ，w a i t i n g t i m eo f j o b si nt h er e s o u r c e sa r et a k e na st h eu t i l i t yf u n c t i o na n dt h ea r r i v a lo fg r i d l e t s i nt h eg r i de n v i r o n m e n ta sas t o c h a s t i cp r o c e s s t h e n ，a c c o r d i n gt ot h ea m o u n to f g r i d l e t ss u b m i t t e dt ot h eg r i de n v i r o n m e n ta tac e r t a i nt i m e ，an a s he q u i l i b r i u mp o i n t i sw o r k e do u tt od i s t r i b u t et h ea m o u n to fg r i d l e t sa m o n gr e s o u r c e s ，t h u sa l lt h e r e s o u r c e sf o r mac o o p e r a t i v ea l l i a n c ea n dt h en e e d so fd ! i f f e r e n ta p p l i c a t i o n sa r em e t w i t ht h eh e l po fm i n - m i ns c h e d u l i n gs t r a t e g y , t h i sp a p e rr e c o n f i r m sg r i d l e t si ng r i d a c c o r d i n gt or e s o u r c e s r e c e i v i n gc a p a b i l i t yf o rg r i d l e t s ，s e t sn e wj o bi n f o r m a t i o nf o r n e wg r i d l e t sq u e u e sa n ds u b m i t st h e mt ot h eo b j e c tr e s o u r c e sf o rp r o c e s s i n g ，m a k e s s u r et h ew a i t i n gt i m eo fg r i d l e t si nt h eo b j e c tr e s o u r c e si st h es h o r t e s t ，a n df i n a l l y , t h e l o a do fr e s o u r c e sr e a c h e sa ne q u i l i b r i u mi nt h i sg a m ep r o c e s s f i n a l l y , t h i sa l g o r i t h mh a sb e e ns i m u l a t e db yt h eg r i d s i ms i m u l a t o ra n dt h e e x p e r i m e n td a t ah a v e b e e na n a l y z e da n de x p l a i n e d i i i 北京t 、l k 人学t 学硕i 学位论文 k e y w o r d sg r i dc o m p u t i n g ；g r i dr e s o u r c e ；c o o p e r a t i v eg a m e ；n a s he q u i l i b r i u m i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：日期：少。尹g i 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：二雄日期：幽 第l 章绪论 第1 章绪论 本章介绍了论文选题的背景和研究意义，分析了网格计算中资源管理研究 的重要性以及影响网格资源管理的几个关键因素，说明了论文研究的内容及创 新点，最后，介绍了本文内容结构安排。 1 1 课题背景和研究意义 1 1 1 背景概述 随着科技的发展，在越来越多的社会活动中，“计算”已经是一个重要的甚 至是不可或缺的解决问题的方法和工具，计算的规模也呈几何级数增长。第一 台电子计算机e n i a c 具有每秒运算5 0 0 0 次的计算能力，当时的科学家认为人 类从此可以摆脱运算束缚，但是近半个世纪过去了，目前运算能力最快的计算 机几乎是当年e n i a c 百亿倍，但是科学家仍然对越来越大的计算问题备感棘 手。 这样的例子举不胜举。众所周知，爱因斯坦于1 9 1 6 年就提出了相对论，他 的重力定律可以描述宇宙中各种物质间的相互作用，但是此定律很难得到实际 的应用，因为它看似简单，却十分复杂，动辄需要求解上千变量的十组偏微分 方程，运算量可想而知。再例如欧洲空间局的卫星每天传送到地面的图像信息 多达5 0 0 g b ，这么多的数据量，不但需要专用的设备进行存储，还需要强大的 计算机提供计算分析。 动辄海量数据的计算已经不是单个计算机或者本地集群系统可以完成的， 更好的方法是将广域的计算资源进行集成，形成一个超级计算机，提供几乎无 穷的计算能力，网格计算【1 捌应运而生，网格计算是由元计算【3 1 ( m e t a c o m p u t i n g ) 发展而来的。 1 9 9 8 年，由计算网格的奠基者f o s t e r 和k e s s e l m a n 将网格概念定义为动态 的、多机构虚拟组织之间的受控协同资源共享及问题解决。按照此说法，资源 的共享通常是在受控且定义良好的条件与策略下完成的，个体的动态分组、多 组以及为共享定义条件和规则的组织统称为“虚拟组织( v i r t u a lo r g a n i z a t i o n ) 【4 】 o 虚拟组织的概念是网格计算的关键，为了让虚拟组织的各个成员可以从附 近自动构造的资源池中共享资源，需要指定一些必要的协议。虚拟组织的成员 北京t 业大学t 学硕l 学位论艾 根据这些协议进行资源共享。在不同的地域进行资源发现和共享是一项具有挑 战性的工作【5 】，其中的复杂性包括资源发现机制、资源共享办法、需要的规则 和条件、资源的安全等。 本文所要研究的问题就是将博弈论引入网格环境中，将网格中的资源看成 参加合作博弈的主体，资源按照网格中存在的作业数量形成合作联盟，通过合 作博弈求得联盟中资源接收作业能力的平衡点，即合作博弈的纳什均衡点，各 个资源为接收作业的数量达成一致，这就是基于博弈的资源共享的方法。基于 合作博弈，资源形成一个暂时稳定的合作团体，共同完成用户提交的作业。 1 1 2 研究内容 由于网格环境中存在数量惊人并且很可能是异构的计算资源，资源管理成 为网格计算环境中一个重要的研究方向。资源管理通常包括资源发现、资源供 应、资源目录、故障隔离、资源监控等。这其中研究最多的是如何根据用户的 需求从网格资源池中选择合适的资源，高效提供给用户来满足其需求。基于此， 本文的研究内容就是如何选择合适的资源来满足用户的需求。 本文的研究内容和目标是将网格环境中的用户和资源进行抽象，建立一个 简单有效的网格模型，运用博弈论的思想，研究资源分配的均衡性问题，提出 资源分配的新方法。 研究的内容主要在以下几个方面： 1 网格资源动态性和异构性的特点使得很难准确判断资源的负载状况，为 此可以选择一种基于博弈的简单有效的资源配置方案方法，将网格环境 中的资源看成博弈的主体，通过合作博弈来寻找资源接收作业的能力， 从资源自身来解决负载均衡的问题： 2 网格环境下作业和资源所有权不同，用户提交作业之后，由网格作业管 理系统按照资源接收作业能力进行分组，新生成的作业队列被映射到有 处理能力的目标资源上； 3 针对网格计算环境中资源的动态增加，需要提高网格的扩展性，实现网 格资源负载的基本平衡，将重点研究如何准确将作业映射的目标资源， 提高网格作业执行的效率，增加资源的利用率。 论文主要针对网格环境中资源分配问题，基于博弈思想，实现网格资源的 公平、有效的分配，从而提高网格资源的利用率。网格资源分配的是否公平的 关键因素是资源管理策略，因此，研究网格环境中资源的分配问题是本文的主 要内容，在文中具体表现为对资源请求队列的管理、调度及资源分配策略的研 究。 2 第1 章绪论 1 1 3 研究意义 从资源的观点描述，网格就是一个集成的计算与资源环境，或者说是个 计算资源池。资源的存在是构建网格存在的物质基础，网格环境吸纳了各种资 源，将它们转化成一种可以随时获取的、可靠的、标准的计算能力。这里的资 源是一个宽泛的概念，不仅包括各种异构的计算机，同时还包括网络通讯能力、 数据资料、仪器设备、存储备份等各种相关资源。 网格资源的具体实现细节对用户透明【6 】。成熟的网格管理系统首先克服了 地理位置的限制，其次解决了计算能力大小的限制，最后还打破了传统的共享 或协作方面的限制。因此，网格系统研究的核心目的就是突破以往强加在计算 资源之上的种种限制，使人们可以以一种全新的、更自由、更方便的方式使用 计算资源，解决更复杂的问题。 资源管理机制会对网格环境中的应用程序执行效果产生重要影响，资源管 理问题的有效全面解决也是网格走向实际运用的一个关键因素 7 1 。因此，计算 网格资源管理问题的研究，对当前和未来计算网格的发展和应用都将有重要的 理论意义和巨大的实践价值。 本文提出的基于博弈的网格资源管理，将资源看成是博弈主体，寻找到各 个资源之间接收作业的平衡点，被选中的资源形成一个网格计算联盟，每个资 源按照自己的计算能力接收合适的资源，保证作业的及时处理，使得作业在资 源队列中的等待时间最短。计算联盟可以为用户提供高效服务的计算能力，满 足用户的计算需求。 1 2 网格资源管理 网格环境中的资源管理一般包括两部分【8 】： 1 空间上对计算和数据进行分配，包括选取给定任务所需要的资源组合， 将任务交给这些资源去执行，并分配相关的数据和处理能力等； 2 时间上为计算和通信排序，包括在计算资源上为不同的任务进行排序， ， 同时为不同任务之问的通信进行排序。 一个完整的网格环境应该包括网格用户、网格资源和网格信息服务三个最 基本的实体，如图1 1 所示。 北京t q k 大学t 学硕卜学位论文 图1 - 1 网格资源管理结构 f i g u r e1 - ia r c h i t e c t u r eo f 鲥d r e s o u r c em a n a g e m e n t 网格用户是资源的消费者，网格资源是资源的提供者。网格信息服务目录 负责发现资源，将资源信息登记到一张表中，动态刷新以维护资源信息的及时 有效，用户可以从网格信息服务目录中得到所需资源信息，然后作业分发器按 照一定的调度策略将作业流分发且指定到目的资源上，作业处理完成后再返回 给用户。整个过程中，任务一旦提交给网格系统，就处在网格任务管理器的管 理之下，用户只能通过网格任务管理器查询作业的状态。 网格资源管理就是根据用户的要求、在网格资源中寻找合适的资源、并将 资源和用户作业相匹配，为尽可能高效的运行网格应用程序而调度和监视资源 【9 ，l o 】。高效的调度算法和可靠的资源分配方式可以充分利用网格资源的处理能 力，从而提高应用程序的性能1 1 1 。由此可以看出，网格资源管理【1 2 , 1 3 】是网格中 一个复杂的问题。网格中的资源【1 4 】是网格中可以被主体请求使用的实体的总称， 资源共享是网格的一个主要特征，因此资源管理是网格的基本功能模块。 总的来说，资源管理可以解决以下三个实际的问题【1 5 】： 1 解决了计算在地理位置上的限制。网格环境下的资源分布在地理上的各 处，有些资源是无法和特定的地理位置分开的，有些资源是稀缺或者无 法复制的，这就意味着资源的使用是非常受限制的，但是网格将资源集 中在一个“资源池”中，这就解决了地理位置在资源使用上的约束，使 资源的使用者不再关心资源的具体位置； 2 解决了计算在规模上的要求。在计算能力有限的情况下，对需要大规模 计算才可以完成的任务，通常的做法是采用近似方法求得近似解。由于 突破了网格计算的地理限制，所以网格提供的计算能力远远超过我们的 想象，甚至可以说网格提供的计算能力是接近于无限的，在海量计算能 力的支持下，许多以l j f 利用近似方法求解的问题都可以得到完满的解 决； 3 解决了传统的共享或协作方面对计算的限制。网格提供的资源共享允许 4 第l 苹绪论 直接控制资源，而且共享资源的各方在协作时可以以各种各样的方法进 行交流，充分利用网格提供的各种功能，而一般共享只不过是在数据文 件的传输方面进行的。 网格环境中资源管理的难点是网格环境的分布性和动态性，这使得准确判 断资源的负载状态是十分困难的，一些负载预测方法【1 6 ，1 7 】是基于资源性能的不 变性或缓慢变化，这种假设没有考虑未来的负载变化，在一些情况下是不合理 的；另一些方澍1 8 9 1 基于自适应策略，但是实现起来非常复杂。本文选择了一 种新的方法，通过寻求资源联盟的博弈平衡点来控制每个资源接收作业的数量， 期望达到资源负载均衡。 1 3 国内外研究现状 本文提出一种利用博弈思想进行网格资源管理的方法，到目前为止，关于 博弈论在网格资源管理方面的研究大致可分为两类般均衡和纳什均衡， 分别叙述如下： 一般均衡( g e n e r a le q u i l i b r i u m ) t 2 0 】的网格资源管理在假定用户都是理性，即 个人效用最大化的前提下，利用价格和价格浮动反映资源的异构性和供需状况， 各个参与者通过价格自我调节，使整个网格系统协作运行。这种方法通过供需 均衡实现资源的有效配置，具有代表性的学术观点和方法有： b u y y a 2 l 】于2 0 0 1 年提出了一个基于经济的网格模型框架g r a c e ( g r i d a r c h i t e c t u r ef o rc o m p u t a t i o n a le c o n o m y ) ，将分布式计算经济应用于资源管理和 应用调度。澳大利亚m o n a s h 大学的b u y y a 设计的g r a c e 网格资源框架是一 个基于分布式、可计算的经济学体系框架，用于在网格环境中进行资源交易。 g r a c e 架构中定义了一个网格资源代理g r b ( g r i dr e s o u r c eb r o k e r ) 层， 负责资源发现、选择、绑定等关键作业。包括作业控制代理j c a ( j o bc o n t r o l a g e n t ) 、网格浏览器g e ( g r i de x p l o r e r ) 、资源调度器s a ( s c h e d u l ea d v i s o r ) 、交 易管理器t m ( t r a d em a n a g e m e n t e r ) 、部署代理d a ( d e p l o y m e n ta g e n t ) 和网格市 场目录g m d ( g r i dm a n a g e m e n td i r e c t o r y ) ； w o l s k i 2 2 】从计算经济学的角度出发，在计算网格的设置中运用计算经济的 方法控制网格资源的分配。论文中假设了资源消费者和资源生产者，依据物价 稳定、市场平衡、消费者效率和生产商效率的条件测定在商品市场模型和拍卖 模型中的资源分配效率，结果表明商品市场是控制网格资源分配的一种更好的 选择。 a b r 锄s o n 【2 3 】于2 0 0 2 年提出了网格资源代理( b r o k e r ) 的概念。在面向服务 的网格计算环境中，根据经济原则和用户定义的要求，调用资源代理n i m r o d g 处理资源发现、交易、调度。资源代理通过现有的技术进行部署，对资源可以 5 北京t 业人学t 学硕l 学位论义 进行动态选择。 但是，以上讨论的方法在很多情况下是理想化的，只是考虑了资源提供者 和资源消费者之间的简单关系，没有考虑资源消费者之间的相互影响。在这种 条件下达到的均衡点，即使能达到帕累托( p a r e t o ) 最优，也很难满足实际网格环 境的需要。 基于纳什均衡【2 4 】的网格资源管理侧重于多个利益主体的行为所产生的相 互影响与作用的分析，其中个人的最优选择是其他人选择的函数，并将资源管 理看成是一个博弈过程，通过寻求纳什均衡解得到资源的优化配置方案。其主 要成果和方法有： b r e d i n 2 5 】研究了具有串行作业的多个网格用户竞争同一资源的博弈问题， 提出了以基于市场的预算为约束的优化作业执行时间的资源分配策略，在论文 设计的资源分配策略下，代理( a g e n t ) 之间存在唯一的纳什均衡； m a h e s w a r a n 2 6 】认为单一或者组合拍卖不适合管理网格环境中的资源，因此 提出了基于纳什均衡的拍卖可划分资源的优化用户费用的资源分配策略。可以 证明基于这种策略，在非线性请求下任意代理之间都存在唯一的纳什均衡点。 k w o k 2 7 】于2 0 0 5 年提出了一个层次化网格的博弈论模型，考虑了资源的自 私行为对整个网格作业执行性能的影响，论文有个非常重要的结论：资源的自 私行为对整个网络环境而言不一定就是有害的，如果资源都采用了相同的最优 策略，在文章的分析下，纳什均衡的效果不是最好。 相比国外的成体系的研究，国内将博弈论引入网格计算方面的研究还是比 较少见的，国内的研究主要以建立资源管理模型为基础，研究在网格环境中资 源的共享问题，比较有代表性的有： 吉林大学的李伟提出了一种基于合作博弈的网格资源管理模型【2 8 】，该模型 中，每个节点都是一个资源提供者，而资源使用者在使用资源的时候，需要综 合考虑生产者的各种指标。模型中的调度策略是一种竞争机制，该模型对任务 调度进行了测试，能实现很好的负载平衡以及利益公平。联盟由若干节点组成， 一旦结成联盟，能形成稳定和公平的合作和竞争。但是模型中不考虑网络延迟、 网络带宽等因素，合作模型联盟是固定的，对网格环境中资源的负载没有确定 ! 的分析。 大连理工大学的李志洁博士提出了基于序贯博弈的资源管理策略【2 引。文章 针对已经存在的分配策略对网格资源负载评估的不足，作者提出了一种基于序 贯博弈的优化用户时间的网格资源分配策略。此方法建立在将正比例资源共享 的网格环境中的多用户竞争计算资源的问题转化为多人序贯博弈，通过寻找该 博弈过程中各个阶段的纳什均衡点来预测资源的负载，利用此负载信息生成所 有用户的最优出价组合和资源优化价格，根据各用户的出价按比例分派资源。 6 第l 苹绪论 作者利用g r i d s i m 模拟器对算法进行了验证，得出利用序贯博弈方法预测资源 负载是可行的，且可以很好的使用网格环境下异构资源的动态特征。 文献 3 0 】针对网格环境中资源共享的异构性、分布性、并行性等特征，以 一般的博弈论为基础，建立了网格资源竞价博弈模型，依靠市场机制，提出了 一种基于博弈论的资源共享的协同算法，实现网格资源的优化协同共享。 以上文献主要研究了博弈论在网格资源管理中的应用和实现。 1 4 论文结构 本文共五章，各章内容如下： 第一章：主要介绍论文选题的背景和研究意义，明确论文研究的内容和创 新点，介绍了论文的结构安排； 第二章：介绍了网格的体系结构，并详细说明了网格中资源发现和分配的 方法，指出资源发现是把资源和用户连接起来的重要环节，并且详细的介绍了 g r i d s i m 网格模拟器的体系结构和利用模拟器进行网格环境模拟的流程； 第三章：介绍了博弈论相关知识和概念，着重介绍了博弈问题的解，即纳 什均衡存在的条件和最优性等相关背景知识，分析了网格环境满足博弈存在的 条件，为本文的研究做理论准备； 第四章：本章是论文的重点，首先分析了网格环境中的博弈现象，然后将 网格环境中的用户和资源进行抽象分析，提出了一种单纯的网格环境模型，将 资源作为合作博弈的参加者，作业在资源上的等待时间作为收益函数，基于合 作博弈理论，提出基于博弈论的网格资源分配算法c g r m 和作业调度算法 g s a - c g r m ，期望从资源自身的计算能力出发，选择恰当的作业分配策略，提 高网格环境的高效运作； 第五章：对第四章中提出的算法用g r i d s i m 进行模拟，详细的从博弈过程、 作业提交和作业等待时问方面对实验数据进行了分析； 结论：对本文研究工作进行总结，指出本文研究中还存在的一些问题和不 足，给出了下一步研究课题拟解决的问题。 7 第2 章资源管理技术基础 第2 章资源管理技术基础 2 1 网格基本框架 需要用辩证的方法来理解网格环境。网格本身是一个整体的概念，网格的 作用就是将资源进行整合，为用户提供一种单纯的计算能力。但是从网格自身 来讲，网格也是按照一定的方式将资源进行整合，所以网格也有自身的结构。 网格体系结构就是对网格进行立体的剖析，标识出网格的基本组成部分，说明 整个网格环境整体是由哪些部分结合到一起的。 到目前为止，有代表性的网格体系结构有两个： 1 f o s t e r 等提出的五层沙漏结构； 2 f o s t e r 等结合w e bs e r v i c e 提出的开放网格服务结构o s g a ( o p e ng r i d s e r v i c ea r c h i t e c t u r e ) 。 2 1 1 网格五层沙漏结构 五层沙漏结构【3 1 】中最重要的思想就是以“协议 为中心。协议是指为了实 现特定的操作而定义的分布式系统元素之间交互的方式及交互过程中交换的信 息结构。这里定义的协议侧重于元素之间的相互行为，而不是元素内部的特征。 这种五层网格结构通过协议实现一种机制，并且进一步管理和开发新的共享关 系。 这里的共享更加强调对计算机、数据和其他资源的直接访问。并且共享是 可以高度控制的，需要在资源的使用者和拥有者之间谨慎的定义共享的范围、 条件、内容等。上文多次提到的“虚拟组织 就是基于这个共享规则形成的一 个集合体。 五层沙漏结构并不提供严格的规范，也并不对所需要的协议做简单的堆砌， 而是对该结构中各个部分组件的通用要求进行定义，将这些组件形成一定的层 次关系，每一层的组件具有相同的特征，上层组件可以在底层组件的基础上建 造。这种层次性的结构如图2 1 所示： 9 北京t 业人学t 学硕l ：学化论史 图2 1 网格五层沙漏结构 f i g u r e2 - 1a r c h i t e c t u r a lo f 鲥d 在这个五层结构中，根据各个组成部分与共享资源的抽象距离，将共享资 源进行操作、管理和使用的功能分散在不同的层次上。从图2 1 中可以看到， 越往下则越接近物理的共享资源，反之则屏蔽了底层的物理结构，越往上则更 加侧重抽象共享资源的标识。每个层面主要的作用如下： 1 构造层( f a b r i c ) 。构造层是由具体的物理或者逻辑资源构成，提供资源 的查询机制，通过对局部资源的有效管理，向上层提供对这些资源进行 访问的接口。构造层中资源提供的功能越多，则资源之间可以支持的高 级共享操作就越多； 2 连接层( c o n n e c t i v i t y ) 。为构造层提供安全的数据通讯能力，实现资源 自建的相互通讯，使得互相孤立的资源之间建立了联系。链接层定义了 核心的通讯和认证协议，用于网格中的网络事务处理，实际应用中，这 些通讯协议大部分来自t c p i p 协议栈； 3 资源层( r e s o u r c e ) 。实现对单一资源的共享，资源层协议针对的是单 个的局部资源，忽略全局状态和跨越分布式资源集合的原子操作，这个 协议集合很小，而且需要尽量的标准化； 4 汇聚层( c o l l e c t i v e ) 。协调多种资源的共享，汇聚层协议描述的是资源 的共性，并不关心具体资源的细节特征，说明不同的资源集合之间是如 何相互作用的，汇聚层组件可以进行自由的裁剪，以适应不同的需要； 5 应用层( a p p l i c a t i o n ) 。应用层是在虚拟组织环境中存在的，这是网格 环境向用户呈现的形式，将整合的资源提供给虚拟组织以解决具体的问 题。 从网格资源用户的观点看网格结构，应用是根据在任意层次上定义的服务 来构造的，更加详尽的分层如图2 2 所示【1 1 1 ，图中提出网格需要的基本协议和 服务。在每一层，都定义了相应的协议，提供对相关服务的访问，这些服务包 括资源管理、数据存储、资源发现等等。在每一个层次中，a p i 定义为执行特 定服务交换协议信息的具体实现，这罩的应用可以调用更高级的框架和库，这 1 0 第2 章资源管理技术基础 些框架自身可以定义协议、服务和a p i 。 l l 服务 语言与框架 山 i a p i s d k 汇聚层a p i & s d k s 00 汇聚层服务1 服务汇聚层服务 、， 上 资源a p i & s d k s 0 资源服务层协议 资源服务 上 链接层a p i s 上 链接层协议 1 ， 构造层 议 图2 - 2 用户角度的网格结构 f i g u r e2 2a r c h i t e c t e do fg r i df r o mu s e rv i e w 五层结构的另一个重要的特征就是沙漏结构，因为各部分协议的数量是不 同的，对于最核心的部分，需要能够实现上层各种协议向核心协议的映射，同 时实现核心协议向下层其他各种协议的映射。核心协议在所有支持网格计算的 地点都应该得到支持，因此，核心协议的数量就不能太多，操作性需要很强， 这样核心协议就成为了网格层次机构中的一个瓶颈，形式上可以认五层结构是 一个哑铃型，中间小而两头大，资源层和连接层共同组成这一哑铃型中间比较 细的部分。 有的文献上也认为，这种沙漏形式的核心思想和微内核的操作系统可以进 行类比，即操作系统只需要实现某些关键基本功能，大量的与特定外设有关和 与应用有关的部分交给其他的部分来实现。一个小的内核是有利于移植的，可 以比较好的得到支持和实现，增加系统的可操作性。网格环境中资源是多样的， 需求更是复杂的，因此介于需求和资源之间的这个核心部分是很重要的，这也 说明网格环境中研究的重点和难点都集中与此，这也是本文选题的一个理论需 要。 2 1 2 开放网格服务体系结构 开放网格服务体系( o g s a ) 1 3 2 1 是以服务为中心的“服务结构 ，这里的服 务是指具有特定功能的网络化服务。为了突出以服务为中心的特点，o g s a 定 义了“网格服务”的概念。网格服务是一种w e bs e r v i c e 3 3 1 ，它提供一组接1 2 1 ， 这些接口的定义明确并且遵守特定的惯例，以求解决服务发现、动态服务创建、 生命周期管理等问题。按照o g s a 的解释，将网格中的一切都认为是服务，这 北京t 业人学t 学硕i j 学位论艾 里网格就成为网格服务的集合。网格服务可以按照不同的方式聚集起来满足不 同的需要。构建开放网格服务体系的两大支撑技术是网格技术和w e bs e r v i c e 。 o g s a 中不同的功能是由不同的网格服务接口实现的，主要的接口如下： 必须的服务接口( g r i ds e r v i c e ) 、句柄映射( h a n dm a p ) 、注册服务( r e g i s t e r ) 、 创建临时服务( f a c t o r y ) 、主键服务( p r i m a r yk e y ) 、通知机制接口( n o t i f i c a t i o n s o u r c e n o t i f i c a t i o ns i n k ) 等。 2 2 资源发现和分配方法 2 2 i 资源发现 资源发现是把资源和用户连接起来的重要环节，网格环境中的资源管理节 点需要知道哪些资源是可用的，并且需要知道这些资源的相关信息，利用这些 信息，管理节点可以优化资源的合理分配。在网格环境中，比较常见的资源发 现模型有抽取模型、推送模型和抽取推送模型。 资源发现的结果是识别网格环境中可以满足作业需求的可用资源。资源发 现有如下几种方式： ( i ) 抽取模型 在这种资源发现模型中，与管理节点相关联的单一进程的作用是查询网格 资源、收集资源信息。用于收集资源信息的抽取模型会有相对较小的通信负载。 此模型的缺点是容易收集到一些陈旧的信息，这些信息可能已经过期，或 者已经不能够描述此刻资源的状况，对管理节点产生误导，并且当管理节点域 中的资源数量很庞大时，资源发现的过程就会花费大量的时间，资源管理节点 和各个资源之间的通讯负载压力过大。 ( 2 ) 推送模型 在这种资源发现模型中，管理域中的每个资源都必须有一个自己的进程， 这个进程负责收集本地资源的信息，并将这些信息送到管理节点上，管理节点 维护一张表来记录和监视每个资源的动态，管理节点就可以即时知道资源发生 变化，对资源的变化适时做出对策。 如果资源的信息变化频率过于频繁，那么管理节点需要频繁的更新监视每 个资源的信息表，显然必定会产生一定的通信负载。 ( 3 ) 抽取推送模型 这是以上两个模型的折中方法，抽取推送模型介于以上两种模型之间，与 网格调度中的分层模型有类似的体系结构。环境中每一个资源都需要有一个进 程收集当地资源的信息，但是并不是将信息发送给中央管理节点，在当地资源 和中央管理节点之间还有一个局部的管理节点，局部管理节点接收当地资源的 1 2 第2 章资源管理技术展础 信息，维护当地资源的系统状态表，在这个层面上运用了推送方式进行资源发 现。局部管理节点和中央管理节点之间以抽取方式进行资源发现。 2 2 2 资源分配 资源分配是根据已经提交的作业所携带的信息，将作业和资源进行匹配的 过程。这需要借助合理的作业描述语言来实现，资源描述语言同时兼具两方面 的任务，一方面它提供资源的详细信息，另一方面它代替资源的请求者说明需 求。 网格环境中存在着大量的异构资源，同时又是一个多用户的动态环境，所 以对资源的分配需要考虑两个方面的问题： 1 如何从请求同一个资源的多个用户中选择合适的一个或者多个用户来 使用该资源； 2 如何从多个可用资源中选择一个或者多个可以满足作业需要的资源给 用户使用。 假设不考虑协同条件的约束，资源分配将是如何选择一个满足使用者需要 的资源，资源的分配就不需跨越不同的本地资源管理域，每一个资源都处在特 定的资源管理节点之下。一个资源管理节点拥有多个资源，这些资源对外没有 相对的独立性，只是作为资源的一种属性存在，资源的管理节点将本地资源的 特殊信息屏蔽起来，对外只提供一种通用可识别的计算能力。 本文中将资源需求表示为疋= ，i ，眨，) ，网格环境中的七个资源管理节点 用向量表示为兄= 矿，学，茸) ，资源分配就是找到一个节点朋，使得在节点m 上的用户需求和资源能力满足如下的偏序关系 r i r s ，f 【l ，刀】 成立。 寻找资源的分配过程可以有不同的方法，这也会对资源分配效率产生不同 “f ( s 。，s ：，) ，j f 舅 根据定义，严格均衡必然是纯策略均衡。收益函数受到轻微扰动是时，由 于严格不等式仍然得到满足，所以严格均衡仍然是严格的。和参与个体对于均 衡策略与非均衡反应无差异的均衡相比，严格均衡具有更好的性质，严格均衡 对于博弈性质的多种小变动仍然是稳健的。 如果所有参与个体预测特定纳什均衡会出现，那么没有参与个体有动力采 用与均衡不同的行动。因此有且只有纳什均衡具有性质使得参与个体可以预测 到它，预测到他们的对手也会预测的它，如此继续。与之相反，任何固定的非 纳什组合出现，就意味着至少有一个参与者“犯了错误”，或者是在给定预测条 件下最优化自己的收益时犯了错误。并不是这样的错误不会发生，在一些特定 的条件下很有可能发生错误，然而对其进行预测要求研究者对于博弈的结果要 比参与者多，这也是博弈论的大多数实际应用着眼于纳什均衡的原因。 定理2 1 ( d e b r e u ，1 9 5 2 ；g l i c k s b e r g , 1 9 5 2 ；f a n ，1 9 5 2 ) 考察策略式博弈 g = ，s ，u ) ，其策略空间是欧式空间的非空紧凸集。如果收益函数对是连续且 拟凹的，那么存在纯策略纳什均衡。 说明：纳什均衡存在的必要条件是： 1 最是欧式空间上的一个非空、紧致凸集； 2 u i ( 5 ) 在s 上是连续的，准凹函数。 由定理2 1 可以得到，通过微分方程可以判断一个博弈过程是否满足纳什 均衡条件，即：如果舻= s 1 ，s 0 ，s l + ) 是满足博弈的纳什均衡，则必然满足方程： ，、 丝幽! 堕：! 型：0 ，i i a s l 推论1 ( n a s h ，1 9 5 0 ) 每个有限策略式博弈均具有混合策略均衡。【4 l 】 证明：有限行动集合上的混合策略的集合是一个单纯形，即为欧式空间的 非空紧致凸集，而参与个体自身的混合策略，收益是多项式的，因此是拟凹的， 第3 章博弈论相关知识 这意味着反应映射是凸集空间。如果收益函数不是连续的，反应映射不在具有 闭图和不再是非空的。 以上定理只给出了纳什均衡可能存在的条件，至于结果是否最优，博弈个 体是否选择其作为自己的执行策略，还需要比较其他不同的博弈结果。 定义2 3p a r e t o 最优点。 fll 策略s 是p a r e t o 最优的，当且仅当对于协耋s ，j u i ( s + 净e u io ) 。 1 i = li = 1 说明：此定理仅作说明。帕累托最优指一种状态，即不使其他参与个体状 况更加糟糕的情况下，而不可能通过任何方式使得另一部分参与者的状况变得 更好。如果存在一种策略使得没有任何人的状况变得更糟的条件下，至少由一 个人的状况变得更好，则这种策略就成为帕累托改进。 所有当现状不是最好的时候，总存在着帕累托改进的可能；相应的，如果 没有任何改进的可能，则目前的状态已经达到帕累托最优。 纳什均衡虽然通过了一致的预测检验，但并不一定是最好的预测，在一些 局势中如果认为可以获得精确预测那会过于轻率，对此要注意这样一个事实， 博弈的最可能结果实际上取决于比策略式提供的更多的信息，定理2 1 中给出 的必要条件，在博