（计算机应用技术专业论文）基于经济原理的网格资源分配策略与算法研究.pdf

大连理工大学博士学位论文 摘要 本文以新的计算基础设施一网格技术为背景，研究如何利用经济学原理来优化网格 资源的配置方案。研究目标是解决网格资源分配中的用户出价问题并验证所提方法的有 效性。本文从资源分配模型、资源分配算法和模拟实验三个层次上对基于经济模型的网 格资源分配进行了研究，内容主要包括并行任务的资源分配、优化用户效用的资源分配、 基于负载预测的资源分配以及有限理性下的资源分配，主要研究成果体现为以下几点： ( 1 ) 提出了一种基于极大熵方法的网格资源分配策略，改善了并行任务的网格资源分 配中用户作业的时间优化问题。具有并行任务的多个用户竞争同一资源的时间优化是一 个极大极小的难解问题，利用极大熵方法将这个难解的问题转化为一个可微的优化问 题，通过二分搜索最优解可得到用户出价的优化方案。讨论了用户出价函数的特征，证 明了该方案的存在性和唯一性。结果表明该方案具有较低的时间复杂度，适于优化大粒 度的并行网格任务的执行时间。 ( 2 ) 提出了一种基于效用函数优化的分配策略，改善了网格用户需求的异构性问题。 利用综合的效用函数来考虑所有网格用户的效用优化，通过柯布一道格拉斯效用函数对 网格资源进行合理分配和管理，综合考虑了用户作业执行费用和执行时间两方面的因 素，较好的反映了经济模型中各变量之间的权衡，给出了网格用户效用函数的两种可行 的优化方案，即基于预算约束的效用优化和基于时限约束的效用优化，并使用拉格朗日 方法解决网格用户效用函数的优化问题。结果表明该策略可使网格用户在能估计资源节 点拥塞度，并能完成其所有任务的前提下，产生一个合理的出价方案。 ( 3 ) 提出了一种基于序贯博弈的网格资源分配策略，改善了网格资源的负载预测问 题。资源负载预测是实现资源优化分配的关键环节，该策略克服了资源的异构性和动态 性对判断资源负载状态的不利影响，将正比例资源共享的网格环境中多用户竞争同一计 算资源的问题形式化为一个多人序贯博弈，通过寻求该序贯博弈中各个阶段博弈的纳什 均衡解，预测资源负载；然后利用此负载信息生成所有用户的最优出价组合和资源的优 化价格；最后根据各用户出价按比例分配资源的计算能力，实现了资源的优化分配。结 果表明该策略能够得到合理的用户出价，降低资源占用时间，较好地适应了网格环境下 异构资源的动态性。 ( 4 耀出了一种基于进化博弈的网格资源分配策略，改善了有限理性用户竞争资源的 策略均衡问题。该策略运用进化博弈论对用户出价策略的演进进行研究，将网格用户视 为有限理性的博弈群，建立了用户出价进化博弈的一般模型。该模型定义了用户出价策 略的效用矩阵，然后利用复制动态方程求解网格用户策略选择比例的进化稳定点，并详 基于经济原理的网格资源分配策略与算法研究 细讨论了各种用户评估函数对进化稳定点的影响，得到的网格用户出价演化的均衡策略 即是进化稳定策略。结果表明进化博弈方法虽然不能直接选择最优策略来实现纳什均衡 但能通过反复博弈，使用户动态地学习并调整自己的策略，克服有限理性的制约，逐步达 到稳定均衡，从而实现了网格资源的优化分配。 关键词：嘲格计算；资源分配；效用；纳什均衡；进化博弈 大连理工大学博士学位论文 a b s t r a c t b a s e d0 nt h en o wc o m p u t i n gi n 丘鼬佃眦血l 托吲dt e c h n o l o g y ，t h i st h e s i sf o c u s 髓0 1 1h o w t o 哪时m i z ct h eg r i dr e s o u r c ：ea l l o c a t i o nu s i n ge c o n o m i ct h e o r y t h eo b j e c t i v eo f t h i sr e s e a r c h i st os o l v et h ep r o b l e mo f g n du s e rb i d si n 面dr e s o u l 悦a l l o c a t i o na n dt ot e s tt h ee f f i c i e n c yo f t h ep r o p o s e ds c h e m e s t h e 鲥dr e s o u r c 4 a l l o c a t i o nb a s e do ne c o n o m i cm o d e li si n v e s t i g a t e d f r o mt w oa 印e c t s ：r c s o u r c ea l l o c a t i o na l g o r i t h ma n ds i m u l a t i o n t h em a i nc o n t e n t sa r et h e r c s o 愀a l l o c a t i o nf o rp a r a l l e lt a s k s r e s 吣ea l l o c a t i o nf o ru s e fu t i l i t yo p t i m i z a t i o n , r e s o u r c 七 a l l o c a t i o nb a s e do nl o a dp r e d i c t i o n , a n dr c s o u l c 宅a l l o c a t i o nu n d f i l b o u n d e dr a t i o n a l i t y t h e 芦i m a r yc o n t r i b u t i o n so f t h i st h e s i si n c l u d e ： ( 1 ) c r d 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 nn 埔x i i m l me n t r o p ym e t h o di sp r o p o s e dt o s o l v et h eo p t i m a lp r o b l e mo fu s e rj o be x e c u t i o nt i m ei nt h e 西dr e s o u r c ea l l o c a t i o nf o r p a r a l l e lt a s k s t h et i m eo p t i m i z a 矗o np r o b l e mo f m u l t i p l eu s e r sw i t hp a r a l l e lt a s k sc o m p 锄g f o rac o m m o nr e s o l e c 宅i sm a x - m i np r o b l e m m a x i l n u l ne n t r o ym e t h o di si n t r o d u c e dt o c o n v e r tt h i sh a r dm a x - n l i np r o b l e mi n t oad i f f e r e n t i a b l eo p 缅l a p r o b l e m b i s e c t i o ns e a r c h i n g m e t h o di su s e dt op r o d u c eas e to fo 州m a lu s e rb i d st oa l l o c a t er c s o u l c 宅c a p a c i t y p r o p o r t i o n a l l y p a r t i c u l a r l y , t h ec h a r a c t e r i s t i c so f t h e u s e fb i df u n c t i o na r cs t u d i e di ne m p h a s i s a n dt h e 耐s 咖a n d u n i q u n c s so f t h i ss t r a t e g yi sp r o v e d t h er e s u l t ss h o wt h a tt h ep r o p o s e d a l l o c a t i o n 咖a t e g yg e n e r a t e sal o wt i m ec o m p l e x i t ya n dt h u sc a ns a t i s f yt h ed y n a m i cn a n eo f g i r de n v i r o n m e n l ( 2 ) g r i d1 - e s o u l ea l l o c a t i o ns t r a t e g yb a s e do nu t i l i t yo p t 似o n i sp r o p o s e dt os o l v et h e p r o b l e m o f h e t e r o g e n e i t y o fu s e rr e q u i r e m e n t si ng r i d e s o u 雠a l l o c a t i o n t a k e c o m p r e h e n s i v eu t i l i t yf u n c t i o ni n t oc o n s i d e r a t i o nw h e no p t h n i z i n ga l l 鲥du s e ru t i l i t i e s c o b b - d o u g i a su t i l t yf u n c t i o ni su s e dt oc o n f i g u r e 鲥dr e s o u r c 2b e c a u s ei tr e f l e c t st h et r a d e o f f b e “v 啪v a r i o u sv a r i a b l e so ft h ee c o n o m i cm o d e lf a i r l yw e l l t h es t r a t e g ys y n t h e t i c a l l y c o n s i d e r st w of a c t o r so f e x e c u t i o nc o s ta n de x e c u t i o nt i m eo f u s e r j o b ，a n dg i v e st w of e a s i b l e s c h e m e s ( i e u m i t yo p t i m i z a t i o nu n d e rb u d g e tc o n s t r a i n ta n du t i l i t yo p t i m i z a t i o nu n d e r d e a d l i n e sc o n s t r a i n t ) t oo p t i m i z eg r i du 跚u t i l i t i e s f i n a l l y , t h el a g r a n g i a nm e t h o di su s e dt o s o l v et h eo p t i m a lp r o b l e mo fu s 盯u a j i t yf u n c t i o n t h er e s u l t ss h o wt h a ts t r a t e g yc o u l d p r o d u c ear e a s o n a b l eb i ds c h e m et og u a r a n t e et h ec o m p l e t i o no f 鲥d u s o r si n i t e r a t i e s ( 3 ) g r i dr e s o u r c 七a l l o c a t i o ns t r a t e g yb a s e do ns e q u e n t i a lg a m ei sp r o p o s e dt os o l v et h e p r o b l e mo f l o a dp r e d i c t i o no f g r i dl e s o u r p r e s o u r c el o a dp r e d i c t i o ni sac r u c i a la n dd i f f i c u l t p r o b l e ma f f e c t i n gr c s o u r c 宅a l l o c a t i o no p t i m i z a t i o n t h i ss t r a t e g yo v e r c o m e s t h e d i s a d v a n t a g e so f h e t e r o g e n e i t ya n dd y n a m i cn a t u r eo f g r i dr e s o u r c e t h ep r o b l e mo f m u l t i p l e u s e 辐b i d d i n gt oc o m p e t e f o r8c o l i n ：n o n c o m p u t a t i o n a l 玎器o u r c ei s f o r m u l a t e d嬲a m u l f i - p l a y e rd y n a m i cg a m e t h r o u g hf i n d i n g t h en a s he q u i l i b r i u ms o l u t i o no ft h e - i i i 薹丝竖垦望盟塑鳖鋈塑坌堕堕量苎塑塞； m u l t i - p l a y e rd y n a m i cg a m e r c s o u r c 宅l o a di sp r e d i c t e d u s i n gt h i sl o a di n f o r m a t i o n , a9 吐o f u s e ro p t i m a lb i d si sp r o d u c e dt op a r t i t i o nr e s o u r c ec a p a c i t ya c c o r d i n gt op r o p o r t i o n a ls h m i n g m e c h a n i s m t h er e s u l t ss h o wt h a tt h ep r o p o s e ds t r a t e g yc o u l dg e n e r a t er e a s o n a b l eu s e rb i d s r e d u c er e s o u r c ep r o c e s s i n gt i m e ，a n da d a p tb e t t e rt ot h ed y n a m i cn a t u r eo fh e t e r o g e n e o u s r c i i r c ei n 面de n v i r o n m e n t ( 4 ) g r i dr c 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 ne v o l u t i o n a r yg a m ei sp r o p o s e dt os o l v et h e p r o b l e mo fs t r a t e g ye q u i l i b r i u mw i t hb o u n d e dr a t i o n a lg n du s e r s 1 1 bs t r a t e g yu s i n g e v o l u t i o n a r yg a m et oi n v e s t i g a t et h ee v o l u t i o n a r yp r o c e s so fb i ds t r a t e g yo fg r i du s e r a n e v o l u t i o n a r yg a m em o d e lo fg r i du s e 憾i se s t a b l i s h e d u s i n gt h em e t h o do fr e p l i c a t e d d y n a m i c s ，a ne v o l u t i o n a r ys t a b l es t r a t e g yi sp r o d u c e dt oa l l o c a t ei 0 s o 愀f i n a l l y ，t h e e v o l u t i o n a r ys t a b l ep o 缸a n de v a l u a t i o nf u n c t i o n sc h a r a c t e r i s t i c so f 西d u s e l 甚a r cd i s c u s s e d u n d e rd i f f e r e n tc o n d i t i o n s mr e s u i t ss h o wt h a te v o l u t i o m a yg a m ea p p r o a c hm a k e 班du s 0 1 苫 s t u d ya n da d j u s ts t r a t e g yc o n s t a n t l yt h r o u g hr e p e a t e dg a m e st oa c h i e v ee v o l u t i o n a r ys t a b l e e q u i l i b r i u m , w h i c hl e a d s t oa no p t i m a la l l o c a t i o no f g r i dr e s o u r o k e yw o r d s ：g r i dc o m p u t i n g ；r e s o u r c ea l l o c a t i o n ；o t l l i t y sn a s he q u i l i b r i u m ； e v o l u t i o n a r yg a m e i v 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：銮苎。蕴目期：缱：王壶 大连理工大学博士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：奎盖基作者签名：垒盖基 导师签名： 团咀月一日 大连理工大学博士学位论文 1 绪论 1 1 研究背景 二十世纪的最后十年，i n t e m e t 迅速蔓延到世界各地，成为人们沟通信息和协同工 作的有效工具。更为重要的是，i m e m e t 上汇集了成千上万的计算资源、数据资源、软 件资源、各种数字化设备和控制系统，它们共同构成了生产、传播和使用知识的重要载 体。然而，i n t e m e t 虽然拥有丰富的资源，提供了大量的信息，但缺乏有序管理，查询 信息并不十分便利，信息利用率较低。网上信息未经过有效规范和整理，搜索结果往往 需要人工整理。这种信息查找方式的缺点是：除了查找信息困难、使用效率不高外，还 有垃圾邮件、非法网站、病毒黑客等信息安全隐患。另一方面，网络带宽、网络地址、 网络资源将更加丰富。此时最重要的一个问题就是如何将物理上互连的众多资源汇聚起 来，联合服务，并提供有效管理，使之形成一个有机的整体，发挥最大效益这就是网 格的目标。因此，网格不是某一种可有可无的技术，而是i n t e r n e t 必然的发展方向。 网格技术【l 2 3 l 诞生于上个世纪9 0 年代中期，其思想来源于电力网格。人们在使用用 电力资源时，无需区别是否是水电，火电，还是核电，也不用考虑这些电站位于何处， 因为它们构成了电力网格【4 】。借鉴了这种思想，网格技术发展迅速，从最初将超级计算 机连接成为一个可远程控制的元计算机系统( m e t a c o m p u t e r s ) ，发展到目前试图提供一种 能够聚集网络上的各种高性能计算机、服务器、p c 、信息系统、海量数据存储和处理系 统、应用模拟系统、仪器设备和信息获取设备等广泛分布的各种资源，进行大规模计算 和数据处理的通用基础支撑结构，为各种应用开发提供底层技术支撑，将i n t e m e t 变为 一个功能强大、无处不在的计算设施。尤其是2 0 0 1 年，i a nf o s t e r 领导的g l o b u s 项目小 组把网格技术建立在w e bs e r v i c e 技术之上，并推出基于开放式网格服务体系结构o g s a 的g t 3 ，在全世界范围内掀起了包括科技界和工业界的网格研究热潮。 网格技术旨在支持虚拟组织的资源共享与协同工作，它的重要基础是网络服务( w e b s e r v i c e ) 技术。网格将其中的所有资源都以服务的形式发布出来，并对其功能和访问接 口加以标准化描述，然后在网格注册中心进行规范化登记。我们现在的网络时代可称之 为手工作坊式的网络时代，而网格技术能把网络上的各种资源综合起来，建立起一个全 自动的网络时代，为构建具有高性能处理、海量数据存储和大量诸如传感器和移动设备 等的2 l 世纪人类社会的信息处理基础设施奠定技术基础。因此，网格被认为是继第一 代的t c p i p 、第二代的w e b 网页技术之后的第三代互联网技术，将成为i n t e t n e f t 信息技 术的下一个浪潮。 基于经济原理的网格资源分配策略与算法研究 1 2 网格内涵 网格的核心观念即“网络就是计算机”，这个网络可以大到整个互联网，小到一个 家庭网。简单地讲，网格是把整个互联网整合成一台巨大的超级计算机，实现计算资源、 存储资源、数据资源、信息资源、知识资源、专家资源的全面共享。当然，我们也可以 构造地区性的网格、企事业内部网格、局域网网格、甚至家庭网格和个人网格。最正统 的网格研究来源于美国联邦政府过去十年来资助的高性能计算科研项目。早期还使用过 另一个名词，即“元计算”f 5 1 。这类研究的目标是将跨越地域的多台高性能计算机、大 型数据库、贵重科研设备、通信设备、可视化设备和各种传感器等等，整合成一个巨大 的超级计算机系统，支持科学计算和科学研究。 ( 1 ) 网格定义 评判一个系统是否是网格，基本上，必须看此系统所能提供的应用、商业价值和科 学结论，而不是它的系统结构。网格还处于发展时期，目前仍然没有一个能够被大家一 致认同的概念。不同的人从不同的角度提出了多个不同的网格定义，其中以网格研究的 权威科学家i a nf o s t e r 等人提出的定义为代表： 1 9 9 8 年，在( t h e g r i d ：b l u e p r i n t f o r a n e w c o m p u t i n g m 胁g 岫】c t l l 他i 州一书中，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 在文章。t h ea n a t o m yo ft 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 a n i z a t i o n s 川刀中将网格描述为：在动态的多机构的虚拟组织中协调资 源共享和协同解决问题。这个定义提出了虚拟组织、资源共享和资源协同的思想，细化 并发展了前面的定义。 2 0 0 2 年，i a n f o s t e r 单独撰写了一篇文章“w h a t i s t h e g r i d ? a t h r e e - p o i n t c h e c k l i s t ” 嗍，其中明确定义了网格的概念，给出了判断是否为网格的三项标准。他认为前面定义 的网格，其本质可以用一个简单的指标来鉴别，根据这个指标，网格实际上是这样一个 系统： 协调非集中控制资源一网格整合各种资源，协调各种使用者，这些资源和使用者 在不同控制域中，网格还解决在这种分布式环境中出现的安全、策略、使用费用、成员 权限等问题。否则，只能算本地管理系统而非网格。使用标准、开放、通用的协议和 界面一网格建立在多功能的协议和界面之上，这些协议和界面解决认证，授权，资源发 现和资源存取等基本问题。否则，只算一个具体应用系统而非网格。得到非平凡的服 务质量一网格允许它的资源被协调使用，以得到多种服务质量，满足不同使用者需求， 一2 一 大连理工大学博士学位论文 如系统响应时问、流通量、有效性、安全性、及资源重定位，使得联合系统的功效比其 各部分的功效总和要大得多。 为了深刻理解网格定义的内涵，下面继续讨论潜藏在网格概念之中的特殊问题。 ( 2 ) 虚拟组织 网格最根本的目的就是要共享资源，但网格关心的共享不仅仅是简单的文件交换， 更强调直接对计算机、软件、数据以及其它资源的直接访问，这种需求在工业，科学以 及工程界等许多领域都会遇到。这种共享必须是高度可控的，需要在资源提供者和消费 者之间详细的定义什么可以共享，哪些人可以共享，在什么条件下可以共享。虚拟组织 ( v i r t u a lo r g a n i z a t i o n s ) 就是基于这样的共享规则，由一些个人或者团体形成的集合体。因 此，网格问题基本上就是虚拟组织所遇到的问题。 图1 1 虚拟组织里的资源共事 f i g i 1r e s o u r e es h a r i n gi n v h t u a lo 曜率d z 撕 图1 1 描绘了两个虚拟组织。这里r 表示资源，这些线把人和资源组合到一起，形成一 个虚拟的组织，这个组织可以动态的组合。组织里有的资源可能会失效，有的资源会被重 复使用，这个虚拟组织可以一起解决问题。虚拟组织代表了一种网格计算的应用，包括了 访问控制、授权、使用策略；共享包括不同种类的资源、程序、文件、计算机、传感器 的数据、网络；使用模式包括从单用户到多用户，从对性能敏感到对代价敏感；因此虚 拟组织涉及到服务质量、时序安捧、协同分配等问题。而当前的分布式计算技术并不涉 及这些需要。 基于经济原理的网格资源分配策略与算法研究 总的来说，现在的技术既不适应资源种类的多种多样，也不能提供建立虚拟组织所 需要的资源共享的灵活性和可控制性。因此网格步入了舞台，在过去的五年里，网格界 的研究成果提供了协议、服务和工具，正好可以应付我们在建设可升级的虚拟组织时所 遇到的挑战。这些技术包括支持跨平台计算时证书和政策管理的安全解决方案；支持远 程安全的访问计算、数据和其它资源的资源管理协议和服务；信息查询协议和服务提供 了资源、组织、服务方面的构造和配置信息；数据管理服务在存储系统和应用软件之间 查找和传输数据包。由于网格技术聚焦于动态的、跨组织的资源共享，所以不与其它的 分布式计算技术形成竞争。 要对虚拟组织进行有效操作，需要我们能够在任何潜在的成员之闯建立共享联系。 显而易见，互用性成为焦点。没有互用性，虚拟组织成员被迫采用双边共享安排，此时 不能确保任何两个节点间使用的机制能够被其它的节点使用。没有这样的保证，就不能 在一个统一的网络环境下构成动态的虚拟组织。互用性意味着共同的协议，虚拟组织的 用户们通过这个协议来商议、建立、管理和开发分配关系。下面一节就来讨论网格体系 结构，即构造网格时需要哪些协议，以及它们之间的关系。 ( 3 ) 网格体系结构 网格体系结构就是关于如何建造网格的技术。它给出了网格的基本组成和功能，描 述了网格各组成部分的关系以及它们集成的方式或方法，刻画了支持网格有效运转的机 制。随着人们对网格认识的进一步深化，体系结构也在逐步的演迸。到目前为止，比较 重要的网格体系结构主要有两个：一个是f o s t e r 在2 0 0 1 年提出的五层沙漏结构【刀；另一 个是在以m m 为代表的工业界的影响下，在考虑到w e b 技术的发展与影响后，f o s t e r 等人结合了w e bs e r v i c e 提出的开放网格服务结构( o p e nc - r i ds e r v i c e a r c h i t e c t u r e ，o g s a ) 9 。 五层沙漏结构 五层沙漏结构由f o s t e r 等人在网格发展的早期阶段提出，是一种影响十分广泛的结 构，该结构的一个最重要的思想就是以。协议”为中心，也十分强调服务与a p i ( a p p l i c a t i o np r o g r a m m i n gj u e r f a c 圮) 和s d k ( s o r w a r ed e v e l o p m e n ti t i t s ) 的重要性，不过该 结构主要侧重于定性的描述而不是具体的协议定义。图1 2 是一个网格的五层沙漏结构 模型。该模型根据各组成部分与共享资源之间的距离，将对共享资源进行操作、管理和 使用的功能分散在五个不同的层次。越往下层就越接近于物理的共享资源，因此该层与 特定资源相关的成分就比较多；越往上层就越感觉不到共享资源的细节特征。 沙漏模型自底向上分别是构造层( 伍晰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 ) 构造层连接底层的本地资源和上层，主要是用 大连理工大学博士学位论文 来为上层访问本地资源提供统一接口，屏蔽各地资源的异构性。连接层的基本功能是支 持便利和安全的通信，它定义了在网格环境中的网络事务处理所需的核心的通信和认证 协议。资源层的主要功能是实现对单个资源的共享，建立在连接层的通信和认证协议之 上。汇聚层建立在资源层和连接层形成的协议瓶颈之上，主要负责协调多种资源的共享。 应用层存在于虚拟组织中，是根据任一层次定义的服务构造的。每一层的a p i 都可以看 作与特定服务交换协议信息的实现，应用可以调用更高层的框架和a p i 库。 五层沙漏结构的一个重要特点就是沙漏形状。其内在的含义就是因为各部分协议的 数量是不同的，对于其最核心的部分，要能够实现上层各种协议向核心协议的映射，同 时实现核心协议向下层其它各种协议的映射。核心协议在所有支持网格计算的地点都应 该得到支持，因此核心协议的数量不应该太多，这样核心协议就形成了协议层次结构中 的一个瓶颈。资源层和连接层共同组成了沙漏的瓶颈，是该模型的核心协议部分，起到 了承上启下的作用。 、工具与应用厂 应用层 i 目录代理，资 汇聚层 源调度与监j 空 单个资源f 资源层 管理i 的安全访问、 连接层 计算机、 存储介质、网络、 构造层 传感器等各种资源接 】一 图1 2 五层沙漏结构 f i g 1 2f i v e - l e v e ls a n d g l a s s a r c h i 蛐e 开放服务网格体系结构o g s a 开放网格服务体系结构( 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 ) 是继五层沙漏结构之 后最重要，也是目前最新的一种网格体系结构。该结构是要将网格领域最热门的两个技 术计算网格和w e b 服务结合起来，把原来按照两条路线进行的研究活动归纳到一条 主线上来。构建o g s a 的两大支持技术是g l o b u s 和w e bs e r v i c e 。g l o b u s 是己经被科学 与工程计算领域广泛接受的网格技术求解方案，w e bs e r v i c e 是一种标准的存取网络应 用的框架。不同于以协议为中心的五层沙漏结构，o g s a 是以服务为中心的，主要从用 基于经济原理的网格资源分配策略与算法研究 户的角度来看待网格系统。 o g s a 架构由四个主要的层构成( 参见图1 3 ) 图1 3 开放服务网格体系结构o g s a f i g 1 3o p e o r i ds e r v i c e s a r c h i t e c t u r e ，o g s a 从下到上依次为：资源层。资源的概念是o o s a 以及通常意义上的网格计算的中 心部分，包括物理资源和逻辑资源。物理资源包括服务器、存储器和网络。逻辑资源通 过虚拟化和聚合物理层的资源来提供额外的功能。w 曲服务层以及定义网格服务的 o o s l ( o p e ng r i ds e r v i c e si n f t 舳) 扩展。o g s i 规范定义了网格服务并建立在标准 w e b 服务技术之上。o g s i 利用诸如x m l 与w 曲服务描述语言( w e bs o r v i c 懿d e s c r i p t i o n l a n g u a g e ，w s d l ) 这样的w e b 服务机制，为所有网格资源指定标准的接口、行为与交 互。o g s i 进一步扩展了w e b 服务的定义，提供了动态的、有状态的和可管理的w e b 服务的能力，这在对网格资源进行建模时都是必需的。基于o g s a 架构的服务。o o s a 中所有网格资源( 逻辑的与物理的) 都被理解成服务。w e b 服务层及其o g s i 扩展为这一 层提供了基础设施。g g f 目前正在致力于在诸如程序执行、数据服务和核心服务等领域 中定义基于网格架构的服务。随着这些新架构的服务开始出现，o g s a 将变成更加有用 的面向服务的架构( s e r v i c eo r i e n t e d a r c h i t e c t u r e ，s o a ) 。网格应用程序。随着时间的推 移，一组丰富的基于网格架构的服务不断被开发出来，使用一个或多个基于网格架构的 服务的新网格应用程序亦将出现。这些应用程序构成了o g s a 架构的第四个主要的层。 ( 4 ) 网格与其它技术的联系 当前分布式计算的分支领域没有提供虚拟组织需要的通用的资源共享框架，而网格 一6 一 大连理工大学博士学位论文 技术与现存技术的区别在于提供了通用的资源共享方案。 网格与w e bs o r v i c c 建造o g s a 利用了两大支撑技术，即网格技术( g l o b u s 软件 包) 和w e bs e r v i c e 。g l o b u s 是已被科学与工程计算广泛接受的网格技术求解方案，w e b s e r v i c e 是一种标准的存取网络应用的框架。因此这两种技术经常被放在一起进行比较。 由于w e bs e r v i c e 一开始就设计为在整个异构网络上工作，当前标准还没有考虑其它方 面的复杂性，比如网格已经解决的不同操作系统之间的通信问题，访问基于不同文件系 统的文件等，因此w e bs e r v i c e 自然地需要下层网格软件提供的服务。与此同时，开放 网格服务体系结构o g s a 吸纳了许多w e bs e r v i c e 标准，如w e bs e r v i c e 描述语言 0 f s d l ) 、简单对象访问协议( s o a p ) 、轻目录访问协议( l d a p l 、w e bs e r v i c e 探测 ( w s i n s p e c t i o n ) 等。总而言之，w e bs e r v i c e 需要网格软件作为很好的补充，而新的网格 体系结构又吸纳了w e bs e r v i c e 的优点。 网格与万维网。作为建筑虚拟组织系统和应用的平台，w e b 技术很有竞争力，这 些技术能够出色的支持浏览器用户服务器交互模式。但是他们缺乏在虚拟组织中进行 复杂互动所需要的特性。例如，一个现在典型的利用t l s 来认证的w e b 浏览器并不支 持单一签证或授权技术，如能结合网格和w e b 技术扩展单一签证技术，并集成到浏览 器的话，将实现对许多w e b 服务器的单一签证，赋予w e b 客户代理的能力，这样利用 w e b 技术来建立。虚拟入口”( 对复杂的虚拟组织应用提供一个瘦客户接口) 将更加容 易。 网格与分布式计算。网格计算是一种新的高性能的分布式计算方法。网格计算作 为新一代的分布式计算方法，与传统分布式计算的主要区别在于在没有集中控制机制的 情况下，通过对计算资源进行大规模共享，满足应用对高性能计算要求，并且这种对计 算资源进行大规模共享是动态的、柔性的、安全的和协作式的。 瞬格与企业计算。企业发展技术包括c o r b a ，e n t e r p r i s ej a v ab e a n s ，j a v a2 e n t e r p r i s ee d i t i o n 和d c o m 等系统被设计为用来构造分布式的应用，提供了标准的资源 接口，远程唤醒机制和发现服务，使得在一个组织内部共享资源非常的容易。但是，这 些机制并不涉及建立虚拟组织时的特别需要。典型的共享安排是基于静态的，只限于在 一个组织内部使用。交互的基本形式是客户机一服务器，而不是对等使用多种资源。这 些现象表明网格技术应该在企业计算中占有一席之地。例如，在c o r b a 的例子中，我 们能够使用g s i 机制建立一个对象的代理请求，来解决跨组织的安全问题；能够采用网 格资源实现容易的对象转换，以访问在一个虚拟组织内的资源；能够建立网格激活的命 名和交易服务，使用网格信息服务协议在大的虚拟组织间查询信息资源。 基于经济原理的网格资源分配策略与算法研究 1 3 网格研究现状 网格计算的重要战略意义及其广阔应用前景，使其成为当今吸引众多研究人员和巨 大资金投入的研究热点。各国政府，学术界和商业界分别启动了一系列的研究项目。 1 3 1 国外研究现状 网格作为一个重要的新领域，已经掀起了全球范围的研发热潮。具有代表性的研究 项目和成果主要有g l o b u s 1 0 1 、l e g i o n 1 、c o n d o r i l 2 1 、n e t s o l v e 1 3 1 、n i m r o d l l 4 1 、n t m r o d d l 5 1 、 a p p l e s 1 6 、d a t a g r i d 1 7 】、e - s c i e n c e 1 8 】、j a v a l i n 1 9 】、n i n f 【2 0 、b o n d l 2 1 1 、g r a d s t 2 2 、t e r a g r i d 2 3 1 、 a p c j r i d l 2 4 1 、g r i d 3 1 2 5 、e g e e 2 6 、d g r i d l 2 7 】、a l b a t x v s s 2 s 、m p i c h - g 2 2 9 3 、p p d g i 3 0 、 g r i p h y n t 3 1 1 、g r i dt o d a y 3 2 1 、e n t e r t h e g r i d 3 3 l 、i s t w e bp r o j e c td a t a b a s e 3 4 、e u r o g f i d l 3 5 1 、 d a l d , i e n 3 6 1 、g r i a l 3 7 、g r i d l a b 3 8 j 、g r i p 3 9 、d a t a t a g 4 0 、c r o s s g r i d 4 1 、e g s 0 1 4 2 1 、 b i o g r i d e 4 3 1 、g e m s s t 4 4 、g l i d s t a r t l 4 5 1 、a v o 4 6 1 、s e t i h o m e t 4 7 1 、p u n c h f 4 * 1 、p o p c o r n l 4 9 。 下面简要介绍比较有影响的软件和工具。 g l o b u s 工具软件已经在世界范围内得到了一定程度的使用，对全球的网格研究开发 工作起到了巨大的推动作用，成了网格领域受世人关注的焦点。该项目要开发一个面向 科学计算的基本软件基础设施，利用该设施，把地理位置上分布的计算资源和信息资源 集成起来。该项目研究网格计算的关键理论，开发支持网格计算的工具软件和网格应用 程序，帮助规划和组建大型的网格实验平台。关键理论包括资源管理、网格安全、信息 服务、数据管理等。工具软件是g l o b u s 最重要的成果，目标是能够在各种平台上运行 l e g i o n 是弗吉尼亚大学的一个基于对象的元系统软件项目，始于1 9 9 3 年。它的目 标是为用户提供单一、一致的虚拟机器模型。l e g i o n 是一个基于计算的元系统，支持透 明调度、数据管理、容错、站点自治和多种安全机制。在l e g i o n 内，所有的实体都是 对象，