（计算机应用技术专业论文）基于非完全信息博弈的网格资源分配策略研究.pdf

大连理工大学硕士学位论文 摘要 网格计算作为一种基于高速网络、面向大区域的高性能并行和分布式计算，将地理 上分布的、隶属于不同机构的计算、存储等资源构成一台虚拟的超级巨型机，完成以往 单机乃至机群都无法解决的高复杂性计算问题。其中资源管理在网格体系中一直是个复 杂而艰巨的问题。本文针对网格环境中资源的动态、异构以及分布的特性，利用微观经 济学与统计学中的理论研究了一种优化网格资源分配的新方法。研究目标是提高资源分 配效率并验证该方法的正确性。本文从资源分配模型，理论证明，实验模拟三个层面上 对该方法进行了分析。具体的研究工作主要分为以下几个方面： ( 1 ) 分析了开放式网格体系结构( o p e ng r i ds e r v i c e sa r c h i t e c t u r e ，o g s a ) 和五 层沙漏式结构，在此基础上对三种用于网格资源管理的模型( 层次模型，抽象所有者模 型和市场经济模型) 进行对比研究，着重论述了市场经济模型在网格计算环境下公平， 高效，便捷等特点。分析了近年来解决市场网格资源分配问题的几种模型，并总结了资 源分配领域的几大矛盾问题以及目前解决方法中存在的主要不足。 ( 2 ) 分析比对多种市场经济网格环境下资源分配模型的基础之上，提出一种“多 赢家式的网格资源拍卖模型( m u l t i - w i n n e r sa u c t i o nm o d e l ，m w a w ) ，即多个用户竞 拍一种网格资源。它基于非完全信息博弈理论，通过制定明确的规则，让竞拍者通过价 格竞争来确定最终竞拍价，在资源提供者未能给待拍资源定价以及竞拍者彼此独立的情 况下公平，灵活地形成竟拍价，即纳什均衡解，并且达到利益的最优化。其快速，公平， 可靠的特性以及代价小，便于交易协议的开发等优点非常适合网格环境异构与分布式的 特性。 ( 3 ) 首次将隐马尔科夫预测模型( h i d d e nm a r k o vp r e d i c t i o nm o d e l ，h m p m ) 应 用到对网格用户出价的预测上。建立了离散时间的h m m 模型并对之前t 一1 个时刻在以每 个用户提交的资源需求 ，乃，一 为可观测状态序列条件下本轮分配中用户使用资源 的单位出价状态进行预测，从而计算出其能获得所需资源的概率。删理论对在网格计 算这一高度动态，异构且随机的环境下资源使用者与提供者的行为进行了恰当的数学描 述，使得预测结果更加准确，从而提高了资源分配的效率。 ( 4 ) 从理论上证明了“多赢家 式分配方法的可行性。且可以最大化系统收益。 m w a m 作为以经济学理论为依托的网格资源分配模型，本文从纳什均衡解的存在性，激励 相容性，个人理性，系统收益这几方面分析证明了其适用性与高效性。 ( 5 ) 通过实验模拟验证了删m 在网格中的可行性与其自身优势。实验一方面对h m m 预测的准确性，以及删f a m 在市场网格中的适用性做了纵向分析：另方面选取序贯博 基于非完全信息博弈的网格资源分配策略研究 弈资源分配算法，双向拍卖分配算法，基于q o s 的资源分配算法，以及“第一价格 拍 卖算法，“第二价格 拍卖算法同本文的“多赢家”算法进行横向比较，从不同层面验 证了结论。 通过对理论证明与实验结果的分析可知，本文提出的“多赢家 式资源分配方法满 足微观经济学中的激励相容性与个人理性，有较大的准确性与灵活性；同时最优化系统 收益，提高资源利用率，增大了交易双方的收益，能更好地适应市场网格环境。 关键词：隐马尔科夫预测；非完全信息纳什均衡；资源分配；“多赢家”式拍卖 大连理工大学硕士学位论文 r e s e a r c h e so ng r i dr e s o u r c ea l l o c a t i o ns t r a t e g yb a s e do ni n c o m p l e t e i n f o r m a t i o ng a m e a b s t r a c t a sak i n do fl a r g ea r e ao r i e n t e dd i s t r i b u t e dc o m p u t i n gb a s e do nt h eh i 曲s p e e dn e t w o r k , t h e 鲥dc o m p u t i n gi n t e g r i t sd i f f e r e n tc a l c u l a t i n ga n dm e m o r yr e s o u r c e w h i c hl o c a t e g e o g r a p h i l ya n dd i s t r i b u t e d l yt oc o m p l e t et h eh i g h l yc o m p l e xc o m p u t i n gp r o b l e m so n es i n g l e p co rag r o u po fp c sc a l ln o td ob e f o r e t h ef i e l do fr e s o u r c em a n a g e m e n ti sa l w a y sat o u g h t a s ki n 鲥dc o m p u t i n g m sp a p e rr e f e r st ot h et h e o r yo fm i c r o e c o n o m i ca n ds t a t i s t i c ，a n d 晰n gan o v e lm e t h o dt h a tc o u l do p t i m i z et h eg r i dr e s o u r c ea s s i g n m e n t t h et a r g e t i st o i m p r o v et h ee f f i c i e n c yo f a l l o c a t i o na n dv a l i d a t et h ec o r r e c t i o no ft h i sm e t h o d t h e r ea r et h r e e a s p e c ti nt h i sp a p e r ，i n c l u d i n gt h er e s o u r c ea l l o c a t i o nm o d e l ，t h e o r yp r o v a t i o n , e x p e r i m e n t s i m u l a t i o n t h ef o l l o w i n gi st h ee x a c tw o r kt h i sp a p e rc o n t a i n s ： a n a l y z et h eo g s aa n df i v el a y e rh i e r a r c h i c a lc o n f i g u r a t i o n , a n dc o m p a r et h r e ek i n d so f 酣dr e s o u r c em a n a g m e n tm o d e lw i t i le m p h a s i s i n gt h em a r k e t i n gm o d e l sf a i r ，h i g he f f i c i e n t , c o n v e n i e n tc h a r a c t o r s t h e nt h ec l e a rd e s c r i p t i o no fs e v e r a lm o d e l su s e dt os o l v et h ep r o b l e m o f 班dr e s o u r c ea l l o c a t i o ni nt h em a r k e t i n g 鲥de n v i r o n m e n tw i l lb eg i v e n a tl a s t , t h i sp a p e r s u m m e r i z at h em a i np r o b l e ma n dt h el i m i t a i o nd u r i n gt h eg r i dr e s o u r c ea s s i g n i n gp r o c e s s a f t e rr e s e a r c h i n gt h o s em a r k e t i n gm o d e l s ，o n en o v e lm o d e ln a m e d ”m u l t i w i n n e r s ”酣d r e s o u r c ea u c t i o nm o d e l i tm e a n sn u m e r a lu s e r sc o m p e t ef o ro n ek i n do fr e s o u r c ei n 鲥d i n c a s et h er e s o u r c ep r o v i d e rc a l ln o td e c i d et h ec l e a rp r i c eo ft h er e s o u r c ea n dt h eu s e r sa r e i n d e p e n d e n tt oe a c ho t h e r ，t h es o l v a t i o nt h i sp a p e ro f f e r sc o u l dm a k et h ef m a lp r i c eo ft h e r e s o u r c ef a i r l ya n dn e a r l y ，w h i c hi st h ep r o g r e s so fs o l v i n gt h en a s he q u i l i b r i m i t sf a s t n e s s ， f a i r n e s sa n dr e l i a b l i t yq u i t ef i tt ot h e 鲥de n v i r o n m e n t a p p l yh i d d e nm a r k o vp r e d i c t i o nm o d e li n t og a dc u s t o m e r sp r i c ep r e d i c t i o nf i r s t l y s e t u pd e s c r i e st i m eh m m ，a n dp r e d i c tt h ep r i c ep e rp i e c eo fr e s o u r c e ，o nc o n d i t i o nt h a te v e r y c u s t o m e r sr e q u i r e m e n to f r e s o u r c et lp i e c e so f t i m eb e f o r e r l ，吃，：1 c o u l db ek n o w n , i n o r d e rt oc o m p u t et h ep r o b a b a l i 锣f o re v e r yu s e rt og e tt h er e s o u r c et h e yn e e d h m mt h e o r y g i v et h ep r o p e rd e s c r i p t i o nt og r i dw i n lc h a r a c t o r so fd y n a m i ca n dr a n d o m n e s s ，i nr e s u l tt h a t t h ee f f i c i e n c yo fr e s o u r c ea l l o c a t i o ni si m p r o v e d 、 n l cp r o v i n gp r o g r e s sw i l lb eg i v e nt os h o wt h ef e a s i b l i t yo fm w a ma n dt h ec a p a b i l i t y t om a x i m i z et h es y s t e mp r o f i t a st h ee c o n o m i c ab a s e dt h e o r y ，m w a mi sp r o v e dc o r r e c t l y f r o mf o u ra s p e c t sc o n t a i n i n gt h ee x s i s t e n c eo fn a s he q u i l i b r i u m ，i n s p i r e - t o l l e r a t i n g ，p e r s o n a l r e a s o n a b l i t y ，s y s t e mp r o f i t - h l 基于非完全信息博弈的网格资源分配策略研究 t h r o u g ht h ea n a l y s i so fp r o v a t i o ni nm a t ha n dt h er e s u l to fe x p e r i m e n t , t h em w a m t h i s p a p e rr e f e r st os a t i s f yt h et h e o r y si ne c o n o m i c ，a n dn o to n l yo p t i m i z et h ep r o f i to ft h ew h o l e s y s t e ma n db o t ht h eu s e r sa n dr e s o u r c ep r o v i d e r ，i m p r o v et h er e s o u r c ee f f i c i e n c y ，b u ta l s o s h o wi t su s e f u la n du t i l i z a b l ec h a r a c t e rt ot h eg r i d k e yw o r d s ：h i d d e nm a r k o vp r e d i c t i o n ；u n c o m p l e t e di n f o r m a t i o ng a m e ； r e s o u r c ea l l o c a t i o n ；“m u l t i - w i n n e r s ”a u c t i o n 一i v 大迕理t 大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：基王韭完全焦! 曼谴銮鲍圆整盗塑金醒篚坠珏究 作者签名：五阻吼l 年卫月卫日 大连理工大学硕士学位论文 1 绪论 1 1 研究背景 i n t e r n e t 发展至今，已如水银泻地，遍布世界各个角落。它巨大的存储量，高效的 信息传输能力，便利了人与人之间信息的沟通交流。i n t e r n e t 上聚集了数以万计的网络 资源，如计算资源、存储资源、数据资源、软件资源、各种数字化设备和程控系统等， 它们通过虚拟化的链接，统一的管理，彼此之间协同计算成为传播和使用信息的重要载 体。随着信息技术市场飞速发展，业界长期追求的以技术为中心的做法将逐渐让位于以 人为中心的模式。计算机系统总体结构已经历了三种模式的演变：首先是大型机终端 模模式，它使用方便易于管理，但开放性差，不易拓展，价格昂贵；其次是客户服务 器模式，集中在大型主机中的服务器功能被分散到多台独立的开放式服务器，通过网络 与各类客户机相联；接下来是服务器聚集模式，它用一套物理上集中式服务器同时提供 多台独立服务器的功能，并将尽量多的功能从客户端移回集中式服务器端，以提高系统 的可管理性。然而，如1 1 所示，目前网络处理能力每九个月就翻一倍，而摩尔定律指 出每个集成电路中晶体管数量每1 8 个月会翻一倍，那么，处理器的发展速度与网络处 理能力相比存在很大的差距。因此业界需要一种关键的网络技术，它必须能够更加有效 地利用微处理器，从而确保网络处理能力与处理器成本之间的平衡，这种技术就是网格 计算。纵观计算机系统结构的发展可谓“合久必分，分久必合 ，网格计算技术的出现 可以看成是新的“分 ，即服务器均物理地分布到各地，但仍保持虚拟的单一系统映像， 也可以看成是一种特殊的“合”。 喜 譬 萋 a235 帕耵b 群讲y 髑糟 图1 1 摩尔定律与存储发展，光纤发展的比较 f 塘1 1 t h ec o m p a r a t i o no fm o l a rl a w , d e v e l o p m e n to fs t o r a g ea n df i b r e 器 基于非完全信息博弈的髓格资源分配策略研究 网格( g r i d ) 一词来源于电力网( p o w e rg r i d ) 1 。人们使用电力网络时，无需区分 是水电，火电还是核电，也不用考虑这些电站位于何处，应为他们已经构成了电力网格。 当一个组织机构在努力保持竞争力时必须考虑很多因素：减少计算费用、增加计算吞吐 量、加快对市场的响应、改进生产服务质量和产品创新等。尽管对计算力的需求非常大， 但是许多现有的系统都没有得到充分利用，使许多计算周期没有使用，而实际上这些计 算周期可以用于满足不断增长的计算资源需求。网格计算可以把连接在网络上的各种自 治资源和系统有效地组合起来，实现资源共享、协同工作和联台计算，更加有效而灵活 地使用分布式计算资源，从现有的系统中获取更加有用的汁算力，帮助组织机构获得竞 争优势。 网格计算出了需要对任务、信息和资源进行适当的匹配和优化，还要对对资源进行 台理的虚拟化。更进一步来讲，网格计算的核心可以看作是信息和任务负载的虚拟化。 图1 2 显示了网格计算的组件。任务负载虚拟化切断了它和基础设施之问的依赖关系， 在适当的时间动态地配置，以确保在正确的资源上智能地执行任务负载任务负载管理 器会实现这种功能，但最初是作业调度嚣来启动任务并安排相关人物操作的；信息虚拟 化使得网格数据在用户面前形成了一个特殊的视图用户可以以自己喜好的方式来访问 它，如同在本地访问一样。使得个人与机器达到一种前所未有的融合状态。 图12 网格计算组件 f i g l2t h em o d u l e so f g r i dc o m p u t i n g 大连理工大学硕士学位论文 】i mg r a y 在1 9 9 9 年的图灵奖获奖演说中指出了计算机的研究开发的三个主要脉 络，即巴贝奇问题( 如何构造计算机系统) 、布什问题( 人机之间有什么关系、如何使 用计算机) 以及图灵问题( 机器智能) 。其中的布什问题，网格计算将给出一个全新的 思想，即“人机社会 。它不仅很好地抽象了杂乱的市场需求和用户需求，为科学研究 提供一个共性的方向，而且自利克莱德提出艄人机共生”思想已过去了4 3 年，随着网络 计算时代的临近，”人机社会”的思想是n 人机共生”的自然进化，能够更好地概括新时代 的科学问题。 1 2 网格计算研究现状 网格计算重要的战略意义和广阔的应用前景，使其成为当今吸引众多研究人员和巨 大资金投入的研究热点，各国政府，学术界和商业界分别启动了一系列的研究项目。 1 2 1 国内研究现状 2 l 世纪初，中科院计算所联合十几家科研单位，承担了8 6 3 重点项目“国家高性能 计算环境 的研发任务。该项目的目标是建立一个分布式环境下支持异构平台的计算 网格示范系统，它把我国的8 个高性能计算中心通过i n t e r n e t 连接起来，进行统一的 资源管理、信息管理和用户管理，并在此基础上开发了多个计算型的网格应用系统，取 得了一系列研究成果。随后，科技部召开了“网格战略研讨会 ，确认将网格的研究和 应用列为“8 6 3 计划”的一个专项，随即成立了专项专家组。8 6 3 网格专项投资3 个亿， 主要任务是研制面向网格的万亿次级高性能计算机、具有数万亿次聚合计算能力的高性 能计算环境；开发具有自主知识产权的网格软件；建设科学研究、经济建设、社会发展 和国防建设急需的重要应用网格；制定若干与网格相关的国家标准，参与制定国际标准， 使一批发明专利和软件获得受理和登记，形成自主知识产权。 在我国，已经完成的网格研究项目主要有：清华大学的先进计算基础设施a c i 2 1 ， 即高级计算架构( a d v a n c e dc o m p u t a t i o n a li n f r a s t r u c t u r e ) 和以中科院计算为主的国 家高性能计算环境n h p c e ( n a t i o n a lh i g hp e r f o r m a n c ec o m p u t i n ge n v i r o n m e n t ) 。 在清华a c i 系统中，清华大学研制的高性能计算机“t h n p s c 一2 ”与上海大学研制的 高性能计算机“自强2 0 0 0 通过高速网络连接在一起，此外还连接了4 个应用结点。 这6 个地理位置不同的网格节点可以同时召开网络会议。除此之外，还开发了相应的中 间件，可以构成跨地区、跨学科的“虚拟实验室 研究环境。清华a c i 系统具有一套健 全的资源管理系统、任务管理系统、用户管理系统及安全服务与监控系统。清华a c i 系 统于2 0 0 1 年6 月通过了鉴定。 目前我国正在研发的网格项目主要有： 基于非完全信息博弈的网格资源分配策略研究 中国教育科研网格口1 ( c h i n ag r i d ) ，中国教育科研网格计划是教育部“十五”2 1 1 工程服务体系建设的重大专项，受国家高技术研究发展计划( 8 6 3 计划) 项目支持。它 是迄今为止最宏大的网格工程，它将在教育科研网上把全国1 0 0 所2 1 1 工程建设的重点 大学的资源广泛共享起来，形成为国家科研教育服务的大平台。 上海网格h 1 ( s h a n g h a ig r i d ) ，它是上海市委2 0 0 3 年组建的重大科技攻关项目，计 划由上海市委投资9 0 0 万元，并带动资金5 0 0 0 万元，为其两年。其目标是在两年内， 依托国家8 6 3 自然科学基金，国家教育部和地方重大科研攻关项目的最新研究成果，研 究符合国际标准的信息网格体系结构和关键技术，开发具有自主知识产权和推广价值的 信息网格系统软件、应用开发环境和虚拟研究平台，通过对虚拟组织中的计算、数据、 软件等各种信息的共享和协同，家里具有上海特色的信息网格，并初步实现交通信息网 格典型应用。 织女星网格哺1 ( v e g ag r i d ) ，它是中科院在8 6 3 自然科学基金与科学院创新基金的 支持下，自行研发的网格项目织女星网格具有大规模的数据处理能力，高性能计算能 力以及资源共享和提高资源利用率的能力，和国外其他网格项目相比，它的最大特点是 面向服务的网格，即不仅支持科学计算，还支持其他服务，如通信服务、数据服务、信 息服务、计算服务、交易服务等等。 1 2 2 国外研究现状 ( 1 ) 美国网格技术研究发展现状 美国在信息技术领域就一直处于世界领先地位。从2 0 世纪9 0 年代中期开始，美国 自然科学基金会、n a s a 等组织、部门以及美国军方都相继投入大量资金用于各自领域 内的网格研究项目。到目前为止美国政府用于网格技术基础研究经费已达5 亿美元。本 文将就几个典型的网格研究项目分别进行介绍。 g l o b u s 嘲是目前全球最有影响的网格研究计划之一，主要项目成员有美国阿贡国家 实验室、芝加哥大学、南加州大学。i b m 公司现在也参与其中。其主要研究任务分4 个 方面：网格基础理论和关键技术研究；软件及工具的开发；试验平台的建立；网格应用 的开发。根据g l o b u s 的观点，在网格计算环境下，所有可用于共享的主体都是资源， 如计算机、高性能网络设备、昂贵的仪器、大容量的存储设备、各种科学数据、各种软 件等是资源，分布式文件系统、数据库缓冲池等也可以理解为资源。g l o b u s 实际上关心 的不是资源的实体本身，而是如何把资源安全、有效、方便地提供给用户使用。所以从 共享的角度考虑，g l o b u s 将主要研究重点放在了资源的访问接口或访问界面上。目前， 大连理工大学硕士学位论文 g l o b u s 把在商业计算领域中的w e bs e r v i c e 技术融合进来，希望能够对各种商业应用提 供广泛的、基础性的网格环境支持，实现更方便的信息共享和互操作。 c o n d o r 口1 是维斯康星一麦迪逊大学的网格研究项目。该系统具备选优能力，提供队 列机制、调度策略、优先级方案、资源监控、资源管理等服务功能。用户提交作业后， c o n d o r 把作业放在队列中，选择合适的时间运行用户的作业并监控其运行过程。作业运 行结束时，它提交作业给用户。用户提交作业既可以是串行作业，也可以是并行作业。 n e e sg r i d ：n e e s ( n e t w o r kf o re a r t h q u a k ee n g i n e e r i n ga n ds i m u l a t i o n ) 项目是美国 自然科学基金会1 9 9 9 年推出的研究计划，此项目将持续1 5 年，其资金费用将超过1 0 0 亿美元。到2 0 0 4 年1 1 月已建成了连接美国1 5 个主要从事地震工程研究的机构和实验 室。该系统的主要特点是将美国地震研究机构和实验系统连接起来，能够远程控制进行 试验，实现工具和资料等资源共享。n e e s 把设备站点、数据仓库和大范围地震工程研 究社区结合成一个更加紧密的虚拟组织，研究者可以远程观察和操作实验，使用标准的 标记发布，使用精确的数据仓库，访问计算资源和开源分析工具，利用协作工具进行实 验、执行、分析、访问和发布。 。l e g i o n 是弗吉尼亚大学于1 9 9 3 年提出的基于对象的元系统软件项目。它采用不同 于g 1 0 b u s 的方法，所有的网格组件、资源和服务都使用一个软件对象表示，这些对象 能通过一个单一聚合的命名空间达到。l e g i o n 允许应用开发者选择和定义系统级的责 任，其目标是为用户提供单一、一致的虚拟机器模型。l e g i o n 建立了可用的、高效的、 分布式系统，解决诸如分布性、易编程性、容错、安全、网站自治等问题。 n a s ai p g ：i p g ( i n f o r m a t i o np o w e rg r i d ) 是美国国家航空和宇航局( n a s a ) 的一 个高性能计算与数据网格项目。使用i p g 中间件，网格用户就可以从任何地方访问广泛 分布的异构资源。i p g 的任务是为n a s a 的科学与工程人员提供一个解决问题的平台。i p g 的主要目标是建立一个网格环境原型一个异构的、分布计算、数据和仪器环境，以 提供统一的资源访问。i p g 系统的主要应用领域为：高性能计算、高能物理和海量数据 存储。 a p p l e s ( 应用层调度) 是加利福尼亚大学网格计算实验室进行的一个研究项目，研 究对象是面向应用层的调度。a p p l e s 在异构系统上分别调度并行应用。它采用静态、动 态应用和系统信息选择功能进行应用计算的构造并预测其性能，与相关的资源管理系统 交互完成应用任务。 p u n c h 项目已实施若干年，拥有遍布几十个国家的几千个用户。其目的是开发一个 把环球信息网变成分布式并行计算门户的国际互联网计算平台。p u n c h 能够实现在用户、 基于非完全信息博弈的网格资源分配策略研究 应用服务提供者、存储仓库、c p u f a r m s 之间的管理和中介资源。p u n c h 是近十几年来发 展较快的研究项目。 ( 2 ) 欧洲网格计算发展现状 欧洲d a t a g r i d 于2 0 0 0 年1 2 月2 9 日正式立项，由欧盟提供9 8 0 万欧元资金，项目 完成期限为3 年。项目主要完成者除了c e r n 外，还有法国国家科学研究中心c n r s ( f r e n c h n a t i o n a lc e n t r eo fs c i e n t i f i cr e s e a r c h ) 、欧洲空间研究中心意大利分部e s a e s r i n ( c e n t r eo ft h ee u r o p e a ns p a t i a la g e n c yi ni t a l y ) 、意大利国家原子物理研究所 i n f n ( i t a l j a nn a t i o n a li n s t i t u t eo fn u c l e a rp h y s i c s ) 、荷兰国家原子物理和高 能研究所n i l ( h e f ( d u t c hn a t i o n a li n s t i t u t eo fn u c l e a rp h y s i c sa n dh i g he n e r g i e s ) 和英国粒子物理和天文研究委员会p p a r c ( b r i t i s hc o u n c i lo fr e s e a r c hi np a r t i c l e p h y s i c sa n da s t r o n o m y ) 除了这六家外，还与其他十几家研究机构和工业界建立了 合作研究协议。d a t a g r i d 主要针对c e r n 的高能物理应用，解决海量数据的分解存贮和 处理问题，同时将之扩展到其他应用，如地球观察应用和生物应用，并寻找将其推广的 可能。解决好c e r n 的应用，d a t a g r i d 的研究就可以取得战略性胜利。 “全球l h c 计算网格”是欧洲核子研究中心2 0 0 9 年4 月3 日宣布正式启动的迄今最 大规模的分布式运算网络，它将为设在欧洲的大型强子对撞机( l h c ) 提供强大的数据运 算支持。这个运算网共包括分布在全球3 3 个国家和地区的1 4 0 多个计算中心，参与运 算的科研人员将多达7 0 0 0 名，每年可分析和管理大型强子对撞机数据超过1 5 0 0 万g 。 1 2 3 发展趋势和面临的挑战 网格计算未来的发展趋势大致有三种： 首先是标准化趋势，如同i n t e m e t 需要依赖t c p i p 协议一样，网格也需要依赖标准的 协议才能共享和互通；其次是技术融合趋势，网格项目的开发转向了w e bs e r v i c e 的平台， 构筑了一层通用的、与平台无关的信息和服务交换设施，从而屏蔽了互联网中千差万别 的差异；最后是大型化趋势，美国政府单在网格技术的基础研究上，每年投入的经费就 高达5 亿美元t e r a g r i d 项目始于2 0 0 1 年8 月，由n s f 投资5 3 0 0 万美元，次年1 0 月又追加 3 5 0 0 万美元；美国物理网格g r i p h y n ( g r i dp h y s i c sn e t w o r k ) 计划建立每秒千万亿次级 别的计算平台，用于数据密集型计算。美国军方正在实施的全球信息网格g i g ( g l o b a l i n f o r m a t i o ng r i d ) 预计在2 0 2 0 年完成。目前，g i g 没有专项经费，但美国国防部每 年在信息技术上的投资高达2 2 0 亿美元。i b m 在2 0 0 1 年8 月宣布，将投入4 0 多亿美元进行 “网格计算创新计划”( g r i dc o m p u t i n gi n i t i a t i v e ) ，全面支持网格计算。英国政府 大连理工大学硕士学位论文 宣布投资1 亿英镑，用以研发“英国国家网格 ( u l ( n a t i o n a lg r i d ) 。除此之外，欧 洲还有d a t a g r i d 、u n i c o r e 、m o l 等网格研究项目正在开展。其中，d a t a g r i d 涉及到欧 盟的2 0 几个国家，是一种典型的“大科学 应用平台。日本n t t 数据公司联合i n t e l 、 s g i 等，在2 0 0 2 年中期开展了为期6 个月的网格计算试验。试验将连接日本家庭、企业和 学术机构的1 0 0 万台p c ，集合处理能力将达到每秒6 5 万亿次浮点运算。2 0 0 2 年1 1 月， 日本产业技术综合研究所网格计算研究中心宣布，在由多台个人电脑通过网络连接组成 网格计算环境下，实现了日美之间创纪录的7 0 7 m b p s 的数据传输。 网格作为广域环境下的基础设施，其面临的挑战越来越多地显现出来，发展网络计 算，重大基础问题必须解决。通信带宽将会大大提高，通信延迟将会降低，通信质量会 有明显提高，但是，这些都很难从根本上缓解网络计算现状与需求之间的矛盾，难以实 现“广泛共享、有效聚合、充分释放 的目标。因此，发展网络计算，必须解决许多重 大的基础问题，以下是几个重要基础问题： ( 1 ) 成长性与稳定性的统一问题。i n t e r n e t 是一个无集中控制的不断成长的系统。 这种成长性表现为i n t e r n e t 的地域不断扩大，大量分布异构的资源不断更新与扩展，各 局部自治系统之间的关联关系不断动态变化，使用i n t e r n e t 的人群越来越广泛，进入 i n t e r n e t 的方式不断丰富。如何在一个不断成长的网络计算环境上，为完成用户任务确 定所需的资源集合，进行有序的组织和管理，保证所需资源及其关联关系的相对稳定， 建立相对稳定的计算系统视图，是实现网络计算的前提。 ( 2 ) 自治条件下的协同性问题。i n t e r n e t 是由众多局部自治的系统构成的大系统。 这些局部自治的系统能够在自身的局部视图下控制自己的行为，为各自的用户提供各自 的服务，但是它们缺乏与其它系统协同工作的能力，尤其是与跨领域系统的协同工作能 力。面对系统的局部自治性，如何建立多个系统资源之间的关联关系，保持系统资源之 间共享关系定义的灵活性和资源共享的高度可控性，如何在多个层次上实现局部自治系 统之间的协同工作，共同完成任务，这是实现网络计算的核心问题。 ( 3 ) 异构环境下的系统可用性问题。i n t e r n e t 中的各种资源存在着形态、性能、 功能、以及使用和服务方式等多个方面的差异，这种多层次的异构性和系统状态的不确 定性造成了用户有效使用系统各种资源的巨大困难。在网络计算环境中，如何准确简便 地用程序设计语言等方式描述应用问题和资源需求，如何使软件系统能够适应异构动态 变化的环境，保证网络计算的系统可靠性，使用户能够便捷有效地开发和使用系统聚合 的效能，是实现网络计算的关键问题。 基于非完全信息博弈的网格资源分配策略研究 1 3 网格的内涵与体系结构 网格计算的实际上是指通过建立大规模计算和数据处理的通用基础支撑结构，将网 络上的各种高性能计算机、服务器、p c 、信息系统、海量数据存储和处理系统、应用模 拟系统、虚拟现实系统、仪器设备和信息获取设备( 例如传感器) 集成在一起，为各种 应用开发提供底层技术支撑，将i n t e r n e t 变为一个功能强大、无处不在的计算设施。 1 9 9 2 年，美国国家超级计算应用中心( n c s a ) 的c h a r l i ec a t l e t t 和l a r r ys m a r r 提出“元 计算的概念。他们为了在网络上构筑虚拟计算机环境、执行大规模平行计算处理而开 展研究。1 9 9 5 年，伊利诺伊大学的t o md ef a n t i 和阿贡国家实验室的r i c ks t e v e n s 等人根据1 w a y 计划，进行了最早的大规模元计算实验。这一计划通过高速广域网连接 了全美地区1 7 家计算中心，实施了虚拟现实实验等很多应用验证。以i - w a y 计划为开 端，1 9 9 6 年阿贡国家实验室的i a nf o s t e r 和南加利福尼亚大学的c a r lk e s s e l m a n 的研 究组启动了g l o b u s 计划，开发用于高性能分布式计算的中间件。1 9 9 8 年，表示“网格 技术 概念的蓝图出台了 1 3 1 网格的定义 评判一个系统是否是网格，基本上，必须看这个系统所能提供的应用、商业价值和 科学结论，而不是它的系统结构。网格还处于发展时期，目前业界还没有一个标准的， 大家认同的概念。其中以“网格之父i a n f o s t e r 等人提出的定义为代表： 1 9 9 8 年，在，n l eg r i d ：b l u e p r i n tf o ra n e wc o m p u t i n gi n f r a s t r u c t u r e 哺1 一书中，i a n f o s t e r 和c a r lk e s s e l m a n 尝试着给出了网格的定义：计算网格是一个软硬件的基础设施， 提供了对高端计算能力可靠、一致、普遍并且廉价的访问。该定义强调了软件与硬件是 网格系统构成的基础。 2 0 0 0 年，i a nf o s t e r 和s t e v et u e c k e 在文章ma n a t o m yo f t h eg r i d ：e n a b l i n g s c a l a b l ev i r t u a lo r g n i z a t i o n s 中将网格定义为：在动态的多机构的虚拟组织中协调资 源共享和协同解决问题这个定义突出了虚拟组织、资源共享和协同的概念，更加细化 了前者的描述 2 0 0 2 年，i a nf o s t e r 单独撰写了一篇文章( w h a ti st h eo d d ? at h r e ep o n tc h e c h i s t ) n 其中明确定义了网格的概念，给出了判断是否为网格的三项标准。他认为网格是这样 的个系统： 大连理工大学硕士学位论文 ( 1 ) 协调非集中控制资源。网格整合各种资源，协调各种使用者，这些资源和使 用中在不同的控制域中，网格还解决在这种分布式环境中的安全、策略、使用费用、成 员权限等问题。否则，只能算作本地管理系统而非网格。 ( 2 ) 使用标准、开放、通用的协议和界面。网格建立在多功能的协议和界面之上， 这些协议和界面解决认证，授权，资源发现和资源存取等基本问题。 ( 3 ) 得到非平凡的服务质量。网格允许它的资源被协调地使用，以得到多种服务 质量，满足不同使用者的需求，如系统响应时间、流通量、有效性、安全性、资源重定 位等，使得联合后的系统相比各部分系统的功效总和要大很多。 1 3 2 网格体系结构 网格体系结构是关于如何建造网格的技术，包括对网格基本组成部分和各部分功能 的定义和描述，网格各部分相互关系与集成方法的规定，网格有效运行机制的刻画。显 然，网格体系结构是网格的骨架和灵魂，是网格最核心的技术，只有建立合理的网格体 系结构，才能够设计和建造好网格，才能够使网格有效地发挥作用。目前网格体系结构 的设计已有了一定的研究，其中层次协议结构和开放网格服务体系结构( o p e ng r i d s e r v i c ea r c h i t e c t r u e ，o g s a ) 是最重要最具代表性的两个。 ( 1 ) 层次型结构 层次协议结构是在g l o b u s 项目中提出的具有一般性的网格体系结构。它是以协议 为中心的协议结构，强调协议在网格的资源共享和互操作中的地位。根据协议结构中各 组成那个部分与共享资源的距离，将对共享资源进行操作、管理和使用的功能分散在5 个不同的层次，分别是构造层( f a b r i c ) ，连接层( c o n n e c t i v i t y ) ，资源层( r e s o u r c e ) ， 汇集层( c o l l e c t i v e ) 和应用层( a p p l i c a t i o n ) 。图1 3 显示了层次型结构的模型。基于 五层协议的网格体系结构使得不同的网格应用可以再统一的网格体系结构框架下使用 相同的底层协议。 构造层它们是物理或逻辑实体，作用是向上提供可供共享的资源。 连接层是网格中网络事务处理通信和授权控制的核心协议。构造层提交的各种 资源间的数据交换都在这一层的控制下实现，并实现各资源间的授权验证、安全控制等。 资源层共享单独的资源，定义在个别资源上的共享操作的安全协商、创始、监 控、控制、记账和付费方面的协议。这些协议的实现调用构造层的功能来访问和控制本 地的资源。资源层只关心单个的局部资源，不考虑跨分布收集的全局性和原子性( 如事 务) 问题。 基于非完全信息博弈的网格资源分配策略研究 汇集层定义全局的、跨所有资源捕捉相互作用的协议和服务，实现多个资源的 协调、汇集，供虚拟组织的应用程序共享、调用。 应用层由网格( 虚拟组织) 用户中操作的应用组成。应用程序通过各层