（计算机软件与理论专业论文）计算网格中基于博弈论的算法机制研究.pdf

上海大学硕士学位论文 摘要 计算网格是把地理上广泛分布的各种计算资源互连在一起，组成充分共享 的资源集成( 即虚拟组织) 。这些资源都有自己的代理( c o m p u t e r ) ，这些代理从自 身的利益出发，操纵自身的资源分配算法，他们的这种自私行为会破坏整个网格 系统的高效性并导致系统的退化。如何解决这些问题就是算法机制研究的范畴。 在计算网格中，各种决策者( 如计算机) 之间协同工作，这种现象就可以看 作是一种博弈( 包括合作和非合作的博弈) 。当这些有限资源追求利益最大化时， 它们将达到一种均衡( 纳什均衡) 。因此不妨考虑利用博弈论，研究算法机制设计， 从而解决计算网格中资源分配问题。 本文首先全面介绍了计算网格的研究背景，意义及国内外研究现状，对博弈 论、算法机制设计研究的相关理论进行了阐述。接着，本文将博弈模型引入分配 机制设计进行建模，给出模型的纳什均衡的求解定理。在此基础上，提出优化分 配算法，证明优化分配算法的有效性。随后，本文设计t r u t h f u l 机制，从理论上 证明该机制满足t r u t h f u l n e s s ，并通过仿真实验，对算法机制进行分析，从实践 上验证了本文所采用的方法的有效性。最后对全文做了一个总结并给出四点今后 的研究方向。 本文的主要贡献为： 1 将博弈论引入分配机制设计进行建模； 2 对分配机制模型进行求解，给出纳什均衡的求解定理： 3 提出优化分配算法，证明优化分配算法的有效性； 4 设计t r u t h f u l 算法机制，证明并通过实验结果验证本文方法的有效性； 5 提出了以后进一步研究的四点内容。 关键词：计算网格，算法机制设计，博弈论，纳什均衡，资源分配 上海大学硕士学位论文 a b s t r a c t c o m p u t a t i o n a lg r i d s ( c g s ) a i mt oo f f e rp e r v a s i v ea c c e s st oad i v e r s ec o l l e c t i o n o fg e o g r a p h i c a l l yd i s t r i b u t e dr e s o u r c e so w n e db yd i f f e r e n ts e l f - i n t e r e s t e da g e n t so r o r g a n i z a t i o n s t h e s ea g e n t sm a ym a n i p u l a t et h er e s o u r c ea l l o c a t i o na l g o r i t h mi nt h e i r o w nb e n e f i t ，a n dt h e i rs e l f i s hb e h a v i o rm a yl e a dt os e v e r ep e r f o r m a n c ed e g r a d a t i o n a n dp o o re f f i c i e n c y , s o l v i n gs u c hp r o b l e m si n v o l v i n gs e l f i s ha g e n t si st h eo b j e c to f a l g o r i t h m i cm e c h a n i s md e s i g n w ec a nr e g a r dt h e p r o c e s so f r e s o u r c ea l l o c a t i o ni nt h ec g s a sag a m ea n dr e g a r d t h ea g e n t si nt h ec g sa st h ep l a y e r si nt h eg a m e e a c ho f t h e mt r i e st om a x i m i z et h e i r o w np r o f i ta n dt h e yw i l lg e ta ne q u i l i b r i u mc a l l e dn a s he q u i l i b r i u ma tl a s t s ow e c a ni n t r o d u c et h eg a m et h e o r e t i cm o d e li n t ot h em e c h a n i s md e s i g nt os o l v et h e p r o b l e m so f r e s o u r c ea l l o c a t i o ni nt h ec g s t h ed i s s e r t a t i o ni ss t r u c t u r e da sf o l l o w i n g ：f i r s t l y , w ep r e s e n tt h eb a c k g r o u n d i n f o r m a t i o no fc g sa sw e l la st h ek n o w l e d g eo fm e c h a n i s md e s i g na n dg a m et h e o r y s e c o n d l y , w ei n ”o d u c et h eg a m et h e o r yc o n c e p tt ob u i l dt h em o d e la n dg i v eo u t t h e o r yt os o l v et h em o d e l n e s t ，t h ei m p r o v e dr e s o u r c ea l l o c a t i o na l g o r i t h mi s h i g h l i g h t e do nt h eb a s i so ft h e s es o l u t i o n s f o u r t h l y , w ed e s i g nat r u t h f u lm e c h a n i s m a n dd o e x p e r i m e n t s t o t e s t i f yt h ee f f e c t i v e n e s so fo n ra p p r o a c h a tl a s t ，t h e d i s s e r t a t i o ni sc o n c l u d e dw i t hf o u rd i r e c t i o n sf o rf u t u r ew o r k t h em a i nc o n t r i b u t i o n so f t h ed i s s e r t a t i o na r ea sf o l l o w i n g ： 1 i n t r o d u c i n gt h eg a m et h e o r e t i cm o d e li n t ot h em e c h a n i s md e s i g n 2 g i v i n gt h e o r yt os o l v et h em o d e la n dg e t t i n gn a s he q u i l i b r i u m 3 o p t i m i z i n ga l l o c a t i o na l g o r i t h ma n dp r o v i n gi t se f f e c t i v e n e s s 4 d e s i g n i n gat r u t h f u lm e c h a n i s ma n dt e s t i f y i n gt h a to u rs o l u t i o n sa r ev a l i d a n de f f i c i e n tb yb o t ht h e o r ya n de x p e r i m e n t s 5 i n d i c a t i n gf o u rd i r e c t i o n sf o r t h ef u r t h e rr e s e a r c h k e yw o r d s ：c o m p u t a t i o n a lg r i d s ，a l g o r i t h m i cm e c h a n i s md e s i g n ，g a m et h e o r y ， n a s he q u i l i b r i u m ，r e s o u r c ea l l o c a t i o n h 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：丛 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 上海大学硕士学位论文 第1 章绪论 1 1 引言 随着计算机网络技术的成熟，基于网络的高性能计算的进一步发展，出现了 网格系统。网格把地理上广泛分布的各种计算资源互联在一起，使得分布在各地 的计算资源相互连接，组成充分共享的资源集成( 即虚拟组织) 。如何充分利用 这些资源是我们迫切需要解决的问题。这些资源都有自己的代理( c o m p u t e r ) ， 这些代理从自身的利益出发，操纵自身的资源分配算法，他们的这种自私行为会 破坏整个网格系统的高效性并且导致系统的退化。如何解决这些问题就是算法机 制研究的范畴。 博弈论译自英文“g a m et h e o r y ”，它进入微观经济学等经济学核心领域只有 不到2 0 年的时间。在最近十多年中，博弈论已经成为经济学中最先进的分析工 具之一，而且扩展到了社会科学的其他许多领域，在信息科学领域的应用也是其 中之一。 具体到网格系统中，各种代理之间协同工作，这种现象就可以看作是一种博 弈( 包括合作和非合作的博弈) 。每个代理都是以自己为中心，都是想实现自身 利益的最大化。为了实现自身利益的最大化，他们将有可能不完全执行预定的协 议，这种自私的行为体现在算法中将直接导致算法的输入变得不确定，同时在算 法运行过程中，某一些代理的行为由于受到其他代理的行为的干扰而使得算法结 果产生偏差。 虽然代理间存在自私行为，但是这些代理有一个共同点，或者说所有的博弈 方有一个共同点，这个共同点就是博弈方的理性。正是有了这个共同点，从而使 得我们可以将博弈论的方法引入算法机制设计，对这些代理的行为做一些分析， 设计出有效的算法机制来解决计算网格中资源分配的问题。 上海大学硕士学位论文 1 2 背景知识 1 2 1 什么是计算网格 网格计算最早由s m a r r 和c a t l e t t 引入，它的直接起源为元计算 ( m e t a c o m p u t i n g ) 4 ，它的概念是在i - w a y 2 0 项目中被提出来的。1 9 9 8 年，在 网格：一种未来计算基础设施蓝图 2 1 一书中写道：一个计算网格是一个硬件 和软件基础设施，此基础设施提供对高端计算能力可靠的、一致的、普遍的和不 昂贵接入。在2 0 0 0 年的一篇题为“网格剖析”【1 的文章中，提出社会和策略问 题，书中指出网格计算关心的是在动态的，多机构的虚拟组织中协调资源共享和 协同解决问题。其核心概念是在一组参与节点( 资源提供者和消费者) 中协商资源 共享管理的能力，利用协商得到的资源池共同解决一些问题。随后，人们渐渐认 识到协议标准化在使异构系统间交互操作和使公共基础设施成为一致可能中的 重要性。在此认识基础上，i a nf o s t e r 等人进一步完善网格定义，认为网格实际 上是满足如下三个条件的系统 2 2 1 ： 1 协调非集中控制资源。网格整合各种资源，协调各种使用者，这些资源 和使用者在不同控制域中，比如，个人电脑和中心计算机；相同或不同公司的不 同管理单元：网格还解决在这种分布式环境中出现的安全，策略，使用费用，成 员权限等问题。否则，只能算本地管理系统而非网格。 2 使用标准、开放、通用的协议和界面。标准是指网格提供的接口是标准 的，网格接口不依赖于接入设备的具体情况，不管它使用何种管理设备，采用什 么样的内部协议，都提供统一的标准接口。开放是指网格系统面向所有设备开放， 只要遵守网格规则，任何设备都可以加入网格。网格建立在多功能的协议和界面 之上，这些协议和界面解决认证，授权，资源发现和资源存取等基本问题。否则 只算一个具体应用系统而非网格。 3 得到非平凡的服务质量。网格允许它的资源被协调使用，以得到多种服 务质量，满足不同使用者的需求，如系统响应时间，流通量，有效性，安全性， 及资源重定位，使得联合系统的功效比其各部分的功效总和要大得多。 因此，网格就是一个集成的计算与资源环境。它能够把整个互联网集成为 台巨大的超级计算机，实现全球范围的计算资源、存储资源、数据资源、信息资 上海大学硕士学位论文 源、知识资源、专家资源、设备资源甚至是人才资源等各种相关的广泛分布的各 种资源的全面共享。 网格的含义可以归纳为如下三方面 3 7 ： 1 从概念上，网格的目标是资源共享和分布协同工作。网格的这种概念可 以清晰地指导行业和企业中各个部门的资源进行行业或企业整体上的统一规划、 部署、整合和共享，而不仅仅是行业或大企业中的各个部分自己规划、占有和使 用资源。 2 网格是一种技术。为了达到多种类型的分布资源共享和协作，网络计算 技术必须解决多个层次的资源共享和合作问题，制定网格的标准，将i n t e m e t 从 通讯和信息交互的平台提升到资源共享的平台。但是目前并行计算、分布计算、 中间件等现行技术远远没有解决多组织之间资源的共享问题，以及广域范围的多 系统之间联合处理和计算等网格计算所面临的关键问题。因此，网格计算技术的 研究具有独特性、紧迫性和挑战性。 3 网格是基础设施，是通过各种网格综合计算机、数据、设备和服务等资 源的基本设施。这种设施的建立，将使用户如同今天我们按需使用电力一样，无 需在用户端配景大量的全套计算机系统和复杂软件，就可以简便地得到网格提供 的各种服务，这样，设备、软件投资和维护开销都将大大减少。 由上述网格的定义和特点可以看出网格计算的意义非常重大，具体体现在： 1 打破了传统共享与协作方面的限制。网格以“虚拟组织”的方法，实现 了全社会范围的资源共享与服务协作。虽然网格资源存在分布性，但网格资源可 以充分共享，分布式网格资源共享问题是网格的核心问题，通过网络服务来实现 物理上分布的网格资源的全局共享，这是网格最本质的意义。 2 解决计算能力的限制，网格可以联合并放大全社会的计算能力，这是目 前无法想象的，网格局部也是网格，体现出“整体大于局部之和”的特性。 3 节约资源，现今的计算机资源利用率远不充分，很多应用又缺乏资源。 网格不仅可以把“资源”送到你的桌面，更可以把“应用”放到网格中完成，连 “桌面”都可以节省。 4 ，解决了资源“自治”问题。网格资源是属于资源的所有者，所有者有权 决定是否向网格开放以及对那些用户开放，并制定共享策略等，所有资源的接受 上海大学硕士学位论文 及取用均取决于网格及其用户。 1 2 2 计算网格项目国内外的研究现状 网格计算的重要战略意义及其广阔应用前景，使其成为当今吸引众多研究 人员和巨大资金投入的研究热点。目前，网格技术的研究引起了全球范围的极大 重视。许多国家，地区的研究组织机构都投入了巨资进行网格技术的研究和网格 基础设施的建设，并已开发了c o n d o r 、l e g i o n 、g l o b u s 等比较有影响力的软件 和工具。继学术界之后，各国政府和商业界也纷纷启动了一系列的研究项目。1 9 9 2 年，美国开始实施高性能计算方面的计划h p c c ，并投入巨资研究解决“巨大挑 战问题”的环境、方法和技术，累计使用的基础研究经费接近五亿美元。美国军 方更为积极。美国国防部己在规划实施一个宏大的计划，称为“全球信息网格” ( g l o b a li n f o r m a t i o ng r i d ) ，这个计划预计在2 0 2 0 年完成。美国海军和海军陆战队 己先期启动一个1 6 0 亿美元的八年项目，包括系统的研制、建设维护和升级来作 为这个计划的一部分。英国政府也不甘落后，已决定投资1 亿英镑，用来建设“英 国国家网格( u kn a t i o n a lg r i d ) ”。韩国政府也已正式宣布建立第三代网络基础之 国家网格基本计划，计划在五年内把分散的高性能电脑通过网络连接起来并加以 利用。 在商界，主要i t 厂商为获取该领域的控制权也展开了积极的竞争。2 0 0 2 年 8 月，m m 宣布投入四十亿美元，启动一个全公司的“网格计算创新计划”，研 发网格计算，与g l o b u s 组织合作，把g l o b u s 标准与支持商用的万维网服务标准 结合起来，开发开放的网格计算标准o g s a ，将网格计算由学术界的科学计算应 用扩展到商业应用，立志要做网格技术的先锋。其它公司也不甘示弱。s u n 公司 宣布推出新的g r i de n g i n e5 3 软件的b e t a 测试版，该软件使企业内的计算机的 连接更为方便。s u n 目前已经启动了以g r i de n g i n e 分布式资源管理软件为基础 的开放源代码战略。m i c r o s o f t 的研究部门也积极参与相关项目，包括容错远程 文件系统f a r s i t e 和分布式系统m i l l e n i u m 的建设。在对等计算领域，i n t e l 是最热 心的鼓吹者，这是因为c p u 是i n t e l 的主要收入来源和核心竞争力所在，而对等 计算技术的主要用途之一是充分挖掘连接在网络上的成千上万p c 的处理能力和 存储能力，以处理一些需要大型机，甚至超级计算机才能承担的任务。此外，s u n 4 上海大学硕士学位论文 也在积极推动对等计算规范j x t a 的制订 目前国际上有影响的几个网格计算研究项目如下： 1 g l o b u s o g s a ，g l o b u s 2 3 是美国阿岗国家实验室的研发项目，全美有1 2 所大学和研究机构参与了该项目。g l o b u s 项目是一个多机构的合作研究项目， 它旨在为计算网格搭建最基本的基础设施以及高级网格服务。g l o b u s 的主要研 究目标有两个，一是网格技术的研究，涉及资源管理、安全、信息服务及数据管 理等网格计算的关键理论：二是相应软件的开发和标准的制定，具体成果是能在 各种平台上运行的网格计算工具软件( t o o l k i t ) ，开发适合大型系统运行的大型应 用程序。g l o b u s 项目还涉及到网格应用的开发及实验床的建立，帮助规划和组 建大型的网格实验平台。g l o b u s 的最新发展是由g l o b u s 组织和m m 在2 0 0 2 年 1 2 月于多伦多举行的g g f ( g l o b a lg r i df o r u m ，即全球网格论坛) 会议上发布的 开放网格服务体系o g s a ，o g s a 汇聚了万维网服务和网格计算的成果，它将服 务定义为一个网络使能的实体，提供对计算资源、存储资源、网络、程序和数据 库等的访问。o g s a 中使用的万维网服务标准包括s o a p 2 4 ，w s d l 2 5 乖i w s i l 2 6 。引入万维网服务后，o g s a 可支持异质环境中服务的发现和组合。 g l o b u s 的层次软件体系结构为网格定义的上层应用服务提供了底层基础设施的 支持。高层服务与资源发现、分配、监控、管理、安全、数据管理以及访问等密 切相关，而较低层次的基础设施( g t 3c o r e ) 是为主机高级服务提供运行框架。 2 c o n d o r , c o n d o r 2 8 是威斯康星麦迪逊大学的研究项目，是一个专用的计 算密集型负载管理系统，是一种利用空闲工作站的作业调度和管理工具。项目开 发、部署和评估支持在大规模分布资源集合上进行高吞吐计算的机制和策略。 c o n d o r 环境采用分层体系，支持串行和并行应用。c o n d o r 中的资源提议和请求 通过其分类公告语言c 1 a s s a d 描述。c 1 a s s a d 使用半结构化数据模型描述资源， 提供相应的查询语言以允许公告发布方在资源提议或请求中说明约束条件。 c o n d o r 可视为平板结构的计算网格。它使用采纳了混合名字空间的可扩展模式， 其存储信息的网络目录未采用x 5 0 0 或l d a p 技术。资源发现基于资源信息周期 性的“推”发布和集中式的查询，其调度器是集中式的。 3 l e g i o n ，l e g i o n 2 7 是弗吉尼亚大学的一个中间件研究项目，是为了网格应 用而设计的基于对象的元系统软件，是面向对象技术在网格计算领域应用的重要 上海大学硕士学位论文 实例，支持透明的调度、数据管理、容错、站点自治和各种安全选项。它将网格 计算环境视为一个世界范围的抽象计算机，其设计目标是让用户在l e g i o n 环境 中只感觉到“台”大的计算机，而网格计算用户在这台大计算机上进行程序设 计，它为处理器、数据系统、文件系统等提供标准的对象表示，从而推动分布式 系统软件的原则性设计。在l e g i o n 中，一切都是对象，l e g i o n 规定了对象交互 的消息格式与高级协议，通过对象的一组方法描述其接口，但是对编程语言及 具体的通信协议没有规定。l e g i o n 的体系结构支持反省，允许用户提供自己的对 象来改变系统级的对象支持机制，它也定义了核心对象的接口和基本的功能，用 于支持系统的基本服务。l e g i o n 除了定义实例之外，同时还制定具体的管理策略。 4 n i m r o d 。gn i m r o d g 2 9 是一个网格资源代理，由四个关键构件组成： 任务管理引擎、调度器、分派器和智能主体。任务管理引擎支持插入用户自定义 的调度器、定制应用或问题解析环境。分派器使用g l o b u s 服务将n i m r o d g 智能 主体部署到远程资源上以管理分派任务的运行。n i m r o d g 调度器则可根据用 户服务质量需求中说明的能力、费用和可用性等租借适合的资源和服务。 n i m r o d - g 支持资源的发现、选择、调度与用户任务在远程资源中的透明运行。 n i m r o d g 相关的研究成果还包括一个称为g r i d s i m 3 0 1 的工具集，提供复杂的 设施以支持网格资源和应用调度的建模和模拟，可用于评估调度算法的性能。 5 n e t s o l v e ，n e t s o l v e 3 1 1 是一个网格应用工具，提供基于远程过程调用 的数值计算编程环境。它由三个部分组成：服务的请求者，服务调度与维护者， 以及服务的提供者。n e t s o l v e 提供了独立于实现语言的计算表达语言，客户端 使用该语言表达请求并提交给n e t s o l v e 智能主体，该智能主体将该请求交给合 适的计算资源去处理，相应的负载平衡策略支持尽可能高效地使用计算资源以确 保高性能。 6 a p p l e s ，应用级调度项目a p p l e s ( a p p l i c a t i o nl e v e ls c h e d u l i n g ) 2 9 是加 利福尼亚大学计算机科学与工程系的网格计算实验室进行的一个研究项目，研究 对象是面向应用层的调度。该项目着重研究和开发在计算网格中调度单个应用的 智能主体。a p p l e s 智能主体根据应用和系统信息选择一组可行的资源集，并通 过其它资源管理系统运行应用任务。a p p l e s 框架包含支持参数化类型应用和 m a s t e r w o r k e r 类型应用的模板，允许在智能主体中重用应用相关的调度器。 上海大学硕士学位论文 a p p l e s 智能主体嵌入到应用中以在网格计算环境中进行资源调度，因而对应用 而言将作业映射到资源的调度是集中式的，但实际运行应用的各个任务则由本地 的资源调度设备负责。 7 d a t a g f i d ，d a t a g r i d 3 2 项目基本思想是把生成的海量数据分散到全球的 计算机上进行处理，并由全球的物理学家共同进行分析。其核心中间件系统 g l o b u s 构造。d a t a g r i d 的主要功能包括负载调度和管理，以适应数据的动态重 新分配、高并发的任务数和不同国家机构的不同管理策略等；数据管理，以支 持统一的名字空间和统一的数据格式、数据的高速移动和复制、远程数据复制实 例的一致性等；系统监控，以协助制订调度策略，调整应用程序的运行性能； 构造层管理，对数量众多的基础构件提供灵活和有弹性的管理，满足严格的时间 约束条件，保证整个系统的容错性：海量存储管理，用统一的接口屏蔽不同站点 的数据存储方式和处理方式之间的差异，无缝融合分布的存储资源。 8 u n i c o r e ，德国联邦教育和研究部的u n i c o r e 3 3 项目，主要合作者为 德国的五家研究机构，包括中等范围天气预报欧洲中心、莱布尼兹计算中心、帕 德博恩并行计算中心、卡尔斯鲁尔大学计算中心以及h p 、m m 、n e c 、欧洲 h i t a c h i 、f u j i t s u 公司等。它的目的是提供一套软件，用户可以在不需要知道远 程计算机的操作系统、数据存储格式以及管理策略的情况下，向远程高性能计算 机提交用户作业。它最大可能地使用己有的万维网技术，为终端用户和计算中心 都提供了强大的运行网格的功能，具体有：简单方便地作业创建和控制：支持多 系统和多点作业：动态流控制；通过x ，5 0 9 证书集成安全；访问远程文件存储和 档案；支持科研和商业应用。用户接口语言用j a v a ，工具用浏览器，授权用户 可以通过接口访问任何地方的u n i c o r e 资源。对于那些重要和经常使用的应用 软件，u n i c o r e 的插件机制允许集成方便使用的接口。 9 e s c i e n c e ，英国e - s c i e n c e 网格被认为是最先进的网格结构。应用主要集 中在科学研究类应用。平均而言，每一个项目的人员投入( 一般在2 0 个工作人员 左右1 、工作时间、科学深度和实用水平比我国的应用项目要好。整体结构还 远未调整成o g s a ，但已有o g s a 的初步共识。目前的状况是：每个应用有一个 p o r t a l 入口，底层资源采用t 2 ，c o n d o r 、数据库、文件、w e bs e r v i c e 等形式， p o r t a l 服务器端软件直接调用物理资源。o g s a p l a t f o r m 层面的东西还很少。 上海大学硕士学位论文 1 0 s e t i h o m e ，加州大学伯克利分校的s e t i h o m e 3 4 项目是对等计 算的一个成功典范。s e t i h o m e 是“s e a r c h f o r e x t r a t e r r e s t r i a l i n t e l l i g e n c e a t h o m e ”( 在家里寻找外星文明) 的缩写，该项目在1 9 9 9 年初开始将分布于世界 各地的2 0 0 万台个人电脑组成计算机阵列，用于搜索射电天文望远镜信号中的 外星文明迹象。项目正式启动以来，已经有三百万志愿者参加。他们从指定的站 点下载射电望远镜收集的信息片段，并用自己的计算机在空闲时间运行分析，从 中寻找宇宙中生命的迹象。项目组称，在不到两年的时间里，这种计算方法己经 完成了单台计算机3 4 5 0 0 0 年的计算量。可见，这种“蚂蚁搬山”式的对等计算 的处理能力十分强大。 相比之下，中国的研究起步较晚，但也正处于快速发展期，许多网格计算项 目得到了国家和各级科研机构的重视以及资金支持。由于网格计算是一项刚起步 的研究，因此在关键技术的研究方面与国外差距不大，基本处于相同的起跑线上。 目前。我国的研究主要集中于中科院计算所、国防科大、江南计算所、清华大学 和浙江大学等几家在高性能计算方面有较强实力的研究单位。具体说来，国内的 网格项目主要有： 1 n h p c e ，中科院牵头的n h p c e 国家高性能计算环境( n a t i o n a lh i 曲 p e r f o r m a n c ec o m p u t i n g e n v i r o n m e n t ) 【3 8 。该项目目前包括上海、北京、西安、 长沙、成都、合肥等几个实验节点，以提高计算网格系统的性能、可扩展性以及 可用性作为长期目标。 2 织女星网格计划，2 0 0 1 年中科院计算所提出织女星网格计划 3 9 。该计 划包括从高到低的知识网格、信息网格、网格操作系统，并研究开发了面向网格 的下一代高性能计算机曙光3 0 0 0 。 3 网格研究列入国家发展8 6 3 计划 4 0 。2 0 0 2 年，网格研究列入国家发展 8 6 3 计划，并投入资金支持网格的基础设施建设和应用研究。它以“需求牵引、 技术跨越、多方协作、聚焦网格”为指导思想，以实现高性能计算机以及核心软 件技术跨越为目标，研制能有效支持科学工程计算、新一代i n t e r n e t 信息服 务和数据库应用，具有资源共享、协同工作能力的国家高性能计算环境，将高性 能计算服务扩展到科教、企业、政府等各领域，推动我国网格应用及其产业的发 展，提高我国的综合国力和竞争力。 上海大学硕士学位论文 4 c h i n a g r i d ，中国教育科研c h i n a g r i d 计划是教育部“十五”2 1 1 工程公共 服务体系建设的重大专项。中国教育科研网格将充分利用中国国家教育科研网 c e r n e t 和高校的大量计算资源和信息资源，开放相应的网络软件，配合网络 计算机的使用，将自治的分布议购的海量资源集成起来，实现c e r n e t 环境下 资源的有效共享，形成高水平低成本的服务平台，成为国家科研教学服务的大平 台。 1 - 2 3 博弈论概述 博弈论( g a m et h e o r y ) 又称对策论，被认为是本世纪应用数学最重要的理 论成果之一。它是研究不同决策主体的行为发生直接相互作用时候的决策以及这 种决策带来的均衡问题。在博弈论的模型中，每个主体的收益不仅取决于他自身 的行为，同时也取决于其他参与者的行为，而个人所采取的最优策略也取决于自 身对其他参与者所采取的策略的预期估计。 博弈论的研究主要经历了以下阶段： 第一个阶段研究的重点是合作博弈( c o o p e r a t i v eg a m e ) 。美国数学家冯诺 依曼( j o h nv o nn e u m a n n ) 和摩根斯特恩( m o r g e n s t e m ) 于1 9 4 4 年出版了博 弈论与经济行为( t h et h e o r yo f g a m e sa n de c o n o m i cb e h a v i o r ) 【3 5 ，在这本著 作中，作者引进了博弈论的扩展形( e x t e n s i v e f o r m ) 表示和正规形( n o r m a l f o r m ) 或称策略性( s t r a t e g yf o r m ) 、矩阵形( m a t r i xf o r m ) 表示，定义了极小化极大 解( m i n - m a xs o l u t i o n ) ，并说明了这种解在所有两人的零和博弈中都存在，提出 了稳定集( s t a b l es e t s ) 解概念，并且正式提出了创造一种博弈论的一般理论， 给出了博弈论研究的一般框架、概念术语、表述方法，提出了较系统的博弈论。 到了2 0 世纪5 0 年代，合作博弈发展到鼎盛期，包括n a s h 4 1 和s h a p l e y 4 2 的“讨价还价”( b a r g a i n ) 模型，g i l l i e s 4 3 提出“核”( c o r e ) 作为合作博弈的 一般解概念。 第二个阶段研究的重点是非合作博弈( n o n c o o p e r a t i v eg a m e ) 。数学家 n a s h 于1 9 5 0 年发表了著名的n a s h 均衡( n a s he q u i l i b r i u m ) 4 4 。t u c k e r 定 义了“囚徒困境”( p r i s o n e r s d i l e m m a ) ，他们的工作基本上奠定了现代非合作博 弈论的基础。非合作博弈与合作博弈的区别在于当事人能否达成一个具有约束力 上海大学硕士学位论文 的协议( b i n d i n ga g r e e m e n t ) ，非合作博弈不需要这样一个协议，从而有更广的 解释力。因为主体之间不合作关系是基本的和长期的，而合作关系是偶然的和暂 时的。另外，在n a s h 的理论框架内，合作博弈可以作为一个特例从非合作博弈 中推导出来。 第三个阶段从2 0 世纪7 0 年代发展至今。从2 0 世纪7 0 年代开始，博弈论 开始受到经济学家的重视，到8 0 年代，博弈论已成为主流经济学的部分。 s e l t e n 4 5 1 9 6 5 年提出了在博弈方选择“相机计划”( c o n t i n g e n tp l a n s ) 的博弈中， 不是所有的纳什均衡都是合理的，因为可能存在“空头威胁”( e m p t yt h r e a t s ) 的问题，并提出用“自博弈完美纳什均衡”( s u b g a m e p e r f e c t n a s h e q u i l i b r i u m ) 对纳什均衡作完美化精炼的思想，并在1 9 7 5 年提出了“颤抖手均衡”( t r e m b l i n g h a n dp e r f e c te q u i l i b r i u m ) 概念。h a r s a n y i 4 6 构造了不完全信息( i n c o m p l e t e i n f o r m a t i o n ) 博弈理论，提出了分析不完全信息博弈问题的标准方法，以及“贝 叶斯纳什均衡”( b a y e s i a n n a s h e q u i l i b r u i m ) 的概念，提出了关于“混合策略” 的不完全信息解释，以及“严格纳什均衡”( s t r i c t n a s h e q u i l i b r i u m ) 。1 9 9 4 至2 0 0 1 年，n a s h 、s e l t e n 、h a r s a n y i 、m i r r l e s s 、v i c k r e y 和s f i g l i t z 相继获得诺贝尔经济 学奖，其主要贡献都与搏弈论紧密相关，这标志着博弈论的应用价值获得了巨大 的肯定。近年来，博弈论的思想和建模方法已渗透到了几乎所有的经济分析领 域。9 0 年后博弈论的应用范围日益外延，已成为自动控制，人工智能等工程领 域中的重要工具。关于本文研究中采用的博弈论模型在后面的章节中有详细的介 绍。 只要一个系统中，有多个可独立地选择自己行为的决策者，而且这些决策者 有着相互作用的优化目标，那么博弈论为研究这些决策者间的交互作用提供了一 个合适的分析框架。具体到计算网格，网格中各个资源的代理之间的行为与市场 中的生产消费问题有很多相似之处。如果将各个决策者( 计算机) 之间的协同工 作看作是一种博弈，当这些有限资源各自独立的优化各自追求自身利益最大化 的时候，各个用户怎样在已有信息的基础上做出理性的决策；同时从整个系统来 看，用户们怎样相互影响，最终达到系统的最优状态或者是均衡状态，这些都是 博弈论在计算机科学中应用的研究方向。结合微观经济学的理论，本文主要将博 弈论引入到算法机制设计的研究中，设计出有效的算法机制，从而解决计算网格 上海大学硕士学位论文 中资源分配问题。 1 2 4 算法机制设计的目的和意义 计算网格中每一个代理从自身的利益出发，操纵自身的分配算法，他们的这 种自私行为会导致系统的低效和退化 1 6 。解决这个问题就是算法机制研究的目 标 1 0 1 。机制设计理论作为博弈论研究的分支，是研究在自由选择，资源交换， 信息不完全及决策分散化的条件下，涉及一套激励机制来达到既定目标的理论 5 4 】。算法机制设计( a l g o r i t h m i cm e c h a n i s md e s i g n ) 把机制设计的理论运用在 算法设计中，针对所有代理的自私的理性行为，实现某种预定目标( o b j e c t i v e f u n c t i o n ) 的协议设计。在算法机制设计中核心的问题是设计一种能够促使代理 说实话( 如实提交其v a l u a t i o n 值) 的协议。 算法机制设计可以分成两大类问题 5 2 。第一类是优化机制问题，用来最大 化机制本身的期望效益值。当代理的v a l u a t i o n 值是独立的并且满足某种概率分 布条件时，可以部分解决这类问题 4 8 】。不幸的是，很多这方面的结果都是否定 4 9 ，5 0 ，5 1 1 。另一类非常重要的设计问题就是u t i l i t a r i a n 机制。u t i l i t a r i a n 机 制的目标是最大化所有代理的v a l u a t i o n 之和。这一类机制问题( 特别地，v c g 机制) 在 1 8 ，5 3 y 9 有充分的讨论。 1 _ 3 相关工作 近年来，将博弈论运用到计算机科学领域已经引起广泛的关注，机制设计作 为博弈论研究的一个子领域，近年来在计算机科学中的调度，拍卖，电子商务等 方面得到越来越多的重视。 一种非常重要的机制设计是v i c k r e y - c l a r k e g r o v e s ( v c g ) 机制【3 6 。n i s a n 和 r o n e n 5 5 最先研究了计算机科学中几个具体的机制问题，如最短路径，调度问 题等，并在【1 8 中指出在一些理性的假设下，任何基于v c g 的机制都是真实可 行的。a r c h e r 和t a r d o s 3 1 用机制设计理论来解决代理的组合优化问题，这些 参与的代理的信息只用一个参数来特征化。t a n t a w i 和t o w s l e y 1 9 1 计算出负载 均衡问题是一个非线性优化问题，并且给出了解的多项式计算。k i m 和 k a m e d a 1 1 弓1 n - - 种更加有效的算法来计算负载分配。l i 和k a m e d a 1 4 ，1 5 设 计了星型和层次型网络中静态负载均衡算法。t a n g 和c h a n s o n 2 设计了几种静 上海大学硕士学位论文 态的负载均衡机制来计算作业分配策略。在 9 】中，d a n i e l 和a n t h o n y 找到一种 框架来特征化公平分配机制，该框架主要针对合作博弈模型，在 8 中他们设计 了一种真实的机制来解决分布式系统中静态负载均衡问题。在他们的方法中，只 有一个决策者来优化整个系统的所有工作，这种方法也称作为s o c i a lo p t i m u m 同样，在【5 ，6 中也介绍了多种类体系中静态负载均衡的研究方法。 1 4 本文的主要研究内容与安排 本文的研究背景来自于上海市教委e 研究院上海高校网格项目，同时受上 海市科委自然科学基金的资助( n o 0 0 j c l 4 0 5 2 ) 。 本文围绕计算网格中资源分配的算法机制设计问题进行了系统的、深入的研 究，重点探讨了基于博弈论方法的算法机制设计。提出了计算网格中资源分配博 弈的一般模型，对模型进行求解，给出优化的分配算法，设计t r u t h f u l 机制并给 出定理对上述问题做出理论证明。同时，本文对提出的算法机制进行了仿真实验 和效用分析。 本文的主要研究内容与安排如下： 第一章介绍了课题的背景及意义，讨论了国内外网格相关课题的研究现状及 当前网格资源分配机制有待解决的问题，简单介绍了基于纳什均衡的现代博弈的 基本思想及应用，阐述了将博弈论及经济学的研究方法引入网格资源分配机制研 究的必要性，并且简单介绍了算法机制设计的目的和意义。 第二章详细介绍了博弈论的相关理论，包括什么是博弈，构成博弈的要素， 博弈的分类，几种典型的博弈模型，什么是纳什均衡，纳什均衡的定义( 纯策略 纳什均衡和混合策略纳什均衡) 以及纳什均衡的性质。 第三章提出了计算网格中资源分配的博弈模型，分析了建立该模型的思想， 该模型的构成要素及特点，限定了该模型的使用条件，给出求解该博弈模型的一 般方法以及在求解过程中需要注意的问题。 第四章首先介绍了算法机制设计需要解决的具体问题，在建立博弈模型的基 础上，进一步给出了求解古诺纳什均衡的具体方法并给出求解定理计算分配策 略。通过分配策略的求解，设计出优化的资源分配算法，从理论上证明了优化算 法的有效性，接着提出t r u t h f u l 算法机制，并且证明设计的算法机制满足 上海大学硕士学位论文 t r u t h f u l n e s s 。通过仿真实验实现算法并对本文方法进行验证，分析了资源分配算 法机制的有效性。