（计算机软件与理论专业论文）基于双向拍卖的网格资源分配和定价研究.pdf

2 jj1_l， j a b s t r a c t i nt h i sp a p e r , w ei n t r o d u c e dt h e 西d sd e f i n i t i o n ，a r c h i t e c t u r ea n dr e l a t e dw o r ka t h o m ea n da b r o a da n da n a l y z e dt h ef e a s i b i l i t yo fa d d i n ge c o n o m yt h e o r yt o 鲥d s y s t e m t h em a i nr e s e a r c h e so fo u rs t u d ya let h er e s o u r c ea l l o c a t i o na n dp r i c i n gs t r a t e g y a d o u b l ea u c t i o n - b a s e dr e s o u r c ea l l o c a t i o nm o d e l ( d a r a m ) w a s p r o p o s e do nt h eb a s i s o ft h ed o u b l ea u c t i o ni ne c o n o m i ct h e o r y i tm a i n l yc o n t a i n st h ef o l l o w i n gf o u rp a r t s ： g r i di n f o r m a t i o ns e r v e r ( g i s ) ，g r i dm a r k e ta u c t i o n e e r ( g m a ) ，u s e rb r o k e r ( u b ) a n d g r i ds e r v i c ep r o v i d e r ( g s p ) t h e 鲥du s e r sc a nb i df o rm e r e q u i r e dr e s o u r c e st ob u y w h i l et h es e r v i c ep r o v i d e r sc a ns e l lt h er e s o u r c e st h e yo w n ，s ot h i sm o d e li m p r o v e dt h e e f f i c i e n c yo ft h er e s o u r c ea l l o c a t i o n w e d e s i g n e dan e wr e s o u r c ea l l o c a t i o na n dp r i c i n ga l g o r i t h mi no u rs t u d y , w h i c hi s s u i t a b l ef o rt h ed a r a m i nt h i sm o d e l ，g m aa r r a n g e dt h eb i dp r i c e so fu s e rb r o k e r si n d e s c e n d i n go r d e r , w h i l et h eo p e n i n gb i do f 鲥ds e r v i c ep r o v i d e r sw a sa r r a n g e di n a s c e n d i n go r d e r , f i n a l l yt h et r a n s a c t i o nf e ec a nb ef i x e du n i f o r m l y t h eq u a n t i t yo f t r a n s a c t i o n si sd e t e r m i n e db yt h er e l a t i o nb e t w e e nm a r k e ts u p p l ya n dd e m a n d ，w h i c h e n s u r e st h a tt h er e s o u r c ec a nb ed i s t r i b u t e di nar e a s o n a b l ew a y t h eb u y e r sa n d s e l l e r ss h o u l dp a yt ot h ea u c t i o n e e r a tt h es a m et i m e ，t h ep r o p o s e dd o u b l ea u c t i o nm o d e l w a sp r o v e ds a t i s f yb u d g e tb a l a n c e ，i n c e n t i v ec o m p a t i b i l i t ya n di n d i v i d u a lr a t i o n a l e a tl a s t ，w em a d et h es i m u l a t i o ne x p e r i m e n t sw i t h 鲥ds i m u l a t i o nt o o lg r i d s i m t h e r e s u l t ss h o w e dt h a tt h en e wr e s o u r c ea l l o c a t i o na n dp r i c i n gs t r a t e g yi sb e t t e rt h a nt h e t r a d i t i o n a lo n e s k e y w o r d s ：d o u b l ea u c t i o n ；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 ；b u d g e tb a l a n c e 4 目录 第一章绪论1 1 1 网格技术概论1 1 2 网格体系结构4 1 3 研究背景8 1 4 本文主要的研究工作一9 1 5 本文的组织结构l0 第二章基于经济理论的网格资源管理1 1 2 1 在网格资源管理中引入经济学的优势1 1 2 2 网格经济的研究1 2 2 3 网格资源管理中的常见经济模型1 4 2 4 拍卖模型( a u c t i o nm o d e l ) 一16 2 5 常见定价方式一l9 2 6 本章小结2 0 第三章基于双向拍卖的网格资源分配和定价算法研究2 l 3 1 双向拍卖的优势2 1 3 2 双向拍卖的交易流程2 l 3 3 基于双向拍卖的资源分配模型( d a r a m ) 2 3 3 4d a r a m 中资源分配和定价算法研究2 4 3 5 性质论证2 8 3 6 本章小结2 9 第四章仿真实验3 0 4 1 网格模拟器介绍3 0 4 2g r i d s i m 概述一3 2 4 3 基于g r i d s i m 的d a r a m 中资源分配仿真3 6 4 4 本章小结3 8 第五章总结和展望3 9 5 1 本文所做工作总结3 9 5 2 展望3 9 参考文献4 1 攻读学位期间的研究成果4 5 致谢4 6 学位论文独创性声明4 7 学位论文知识产权权属声明4 7 i；l 0 llr 0 _ 第一章绪论 1 1 网格技术概论 第一章绪论 网格【i 】主要经历了三个发展阶段。第一阶段是萌芽时期，起源于2 0 世纪9 0 年 代，当时主要是一些元计算实验和千兆网的实验床：2 0 世纪9 0 年代中晚期开始， 进入了网格发展的第二阶段实验期，这时开始出现一些奠基性和丌创性的研究 项目，比如学术性研究项目l e g i o n t 2 1 、g l o b u s 2 1 ，i - w a y t 2 】项目以及一些应用；第三 阶段是网格的迅速发展时期，本世纪以来，人们对计算服务网格进行了大量的研究、 开展了很多应用项目，并且出现了有巨大影响力的组织全球网格论坛g g f t 3 l ( g l o b a lg r i df o r m ) ，它致力于制订全球网格计算的规范和标准。 目前，各国政府都投入了大笔资金建设网格基础设施，研究网格技术。网格也 不再只是局限于科学研究，许多的商业机构和科研机构越来越意识到网格技术的重 要性，正致力于将网格推广和应用在更广泛的领域比如工程、科学和商业等领 域，掀起了研究网格的热潮并且取得了丰硕的成果。虽然网格技术仍然不是特别成 熟，但在某些大型行业领域，网格系统己经进入了实际运行阶段。 1 1 1 网格的概念 网格是一种新的技术和思想，是一种把地理位置上的分散资源集成起来的基础 设施，通过这种基础设施，用户无需了解这个基础设施上的资源的具体细节，就可 以使用自己所需要的资源。网格的物理基础是分布式资源和通信网络。计算机池、 集群、计算机、设备、仪器、传感器、存储设施、数据、软件等实体都属于网格上 的资源，并且这些实体工作时需要的相关数据和软件也属于网格资源。 以人们现在已经非常习惯的一些日常现象举例：打开电源开关就可以照明；打 开水龙头就会有水流出，而人们完全不必考虑这些电力和水来自什么地方，它们却 会在需要的时候出现在人们身边。于是大家有了这样的设想：我们是不是可以用同 样的方式来得到和使用纷繁复杂的网络资源呢? 网格技术的出现便为这一设想提供 了可能性。自网格思想提出，它的最终目的便是构建如同公共设施的共享的、可靠 的计算系统。 网格是一种新兴技术，便具有新兴技术的两个主要特征：一、不同的群体赋予 不同的名词来称谓它；二、网格的精确含义和内容是不断变化的。人们对网格的界 定可分为狭义的网格观和广义的网格观。 狭义网格观的代表人物是美国阿岗纳( a r g o n n e ) 国家实验室资深科学家、g l o b u s 青岛人学硕十学位论文 的项目领导人l a nf o s t e r 。2 0 0 2 年7 月，在w h a t st h eg r i d ? at h r e ep o i n tc h e e k l i s t ) ) 中，l a nf o s t e r 认为网格必须同时满足下面三个条件： ( 1 ) 在非集中控制环境中协同使用资源； ( 2 ) 使用标准的、丌放的、通用的协议和接口( 即g l o b u s ) ； ( 3 ) 提供非平凡服务。 这三个条件如此严格，像p 2 p ( p e e rt op e e r ) 、m u l t i c l u s t e r 、e n t r o p i a 、s u ng r i d e n g i n e 、c o n d o r 等均被排除在网格之外。 而另外的一些人则赞同广义的网格观，并称其为巨大全球网格【5 】( g r e a tg l o b a l g r i d ，g g g ) ，它不仅将计算网格、信息网格、数据网格、商业网格、知识网格包 括其中，而且还包括一些已存在的网络计算模式，如进化计算、对等计算( p 2 p ) 等等。 和其他系统相同，网格中也是包含两种实体主体和客体。网格活动的驱动 者是网格主体，它是在网格中有自主活动能力的实体，由网格主体发出网格活动指 令。而网格客体是在网格中不能自主活动的实体，网格活动进行的场所、操作实现 的工具等都属于网格客体。网格客体是需要在网格主体的驱动下才能进行相应动作， 根据请求的内容为请求者提供相应功能。除网格主客体外，网格系统中还包含网格 策略，以表示网格主体和网格客体之间的关系。 1 1 2 网格的本质和特点 网格作为新一代的网络计算与应用技术，其本质不是它的规模，而是它充分利 用了互联网络中现有的软硬件资源，支持广域环境上的存储、数据、计算、信息和 知识资源的共享、互用与互通、消除资源孤岛，从而以较低成本获得高性能。 网格的目标是将地理上分布、系统上异构的多种计算资源通过高速的网络连接 起来，以协同解决大型的应用问题、进行广域信息资源的分布共享，最终把整个的 因特网整合成一台超级的虚拟计算机。网格需要为用户提供应用接口和统一的编程， 并将硬件边界、进程通信和同步的复杂性屏蔽，以此来为用户提供单一的虚拟机器。 网格概念的精髓是指：首先网格是指跨管理域的资源的集合体；而后是指基于 这些资源的协同问题的求解技术。为了实现网格资源的协同求解，要涉及信息领域 的诸多的技术，如分布计算技术、并行计算技术、信息安全、知识工程、数据挖掘 和软件代理等。 近些年来，国内外对网格的研究都取得了很大的进展，并出现了许多与网格相 关的术语，如信息网格( i n f o r m a t i o ng r i d ) 、计算网格( c o m p u t i n gg r i d ) 、w e b 服务和元计算系统【6 】( m e t a s y s t e m ) 等。以上这些相关的研究方向有下述的主要特 点。 ( 1 ) 应用成本低： 2 第一章绪论 利用因特网中各种已有的软、硬件资源来支持各种应用，不仅可以节省应用的 成本，而且还可以带动各学科的研究水平的快速提高。 ( 2 ) 网格资源是有很强分布性的： 网格资源通常是跨管理域的、这些资源属于不同组织，它们之间有的建立了信 任关系，有的没有，管理这些没有信任的网格资源面临着重大的挑战。通过安全技 术如身份认证等可以防止非法用户通过网络使用或者获取任何的网格资源，保障数 据安全性。通过数据隐藏和权限控制技术使用户只能获取到允许的信息和知识，而 不能窃取未授权信息。 ( 3 ) 网格资源具有较大异构性： 分布在广域网不同管理域的资源是具有异构性的，网格资源异构性主要是表现 在以下几个方面： 每个系统可能会具有不同的数据表示； 每个系统可能会安装不同体系结构的处理器； 每个处理器可能会有不同的处理器速度； 每个系统的内部消息可能会有不同的通信速度； 每个系统可能会采用不同的通信协议； 任何两个系统间消息通信带宽可能会有不同。 通过将异构的资源映射成统一管理的逻辑资源，实现资源动态收集，处理和调 度是网格资源管理系统的关键。 ( 4 ) 没有形成公认协议标准： 不同网格计划项目采用不同体系结构，l e g i o n 课题组采用了面向对象体系结构 以开发元计算系统；n e t s o l v e 课题组采用了代理技术来开发科学计算网格；g l o b u s 的t o o l k i t 体系结构现在则成为像i b m 这样大企业支持的事实上的标准，被称为开 放网格服务体系结构( o p e ng r i ds e r v i c ea r c h i t e c t u r e ，o g s a ) 。在o g s a 中纳入 i b m 的w e bs e r v i c e s ，就形成了开放网格服务基础构件( o p e ng r i ds e r v i c e i n f r a s t r u c t u r e ，o g s i ) 。 ( 5 ) 网格资源具有自治性、动态性、扩展性： 网格首先需要保证网格节点的自治性。自治性是指网格系统不应该影响节点原 有的功能，节点有权利自愿加入或者退出网格。网格资源的动态性需网格具有自适 应性。通过信息传感器来发现临时性加入的网格资源，并发现其可用性。网格的扩 展性是要解决网络节点增多、资源规模扩大、应用增加等情况下，不降低网格的性 能的问题。 网格资源的分布广、成分复杂，某一资源出现失败或者故障的可能性较高；资 源拥有者也有可能中途加入或者退出网格系统，这时网格软件应能动态监视系统资 源状况，根据需要来重构系统，从而支持各种应用获得最佳资源服务。 3 青岛人学硕+ 学位论文 1 2 网格体系结构 所谓网格体系结构，就是指如何建造网格的技术。 网格体系结构对网格各组成部分的关系、集成方式( 或方法) 进行了描述；给 出了网格基本组成与功能；对支持网格有效运转的机制进行了刻画。 随着元计算概念的提出( 8 0 年代中后期) ，到计算网格的出现( 9 0 年代中期) ， 网格体系结构经历了几个发展阶段，重要的标志有：2 0 0 1 年的五层沙漏结构等多层 的网格体系结构；2 0 0 2 年出现的技术体系o g s i 及开放网格服务体系结构o g s a ； 2 0 0 4 年在o g s a 的基础上又进一步提出了网络服务资源框架w s r f ( w s r e s o u r c e f r a m e w o r k ) 。另外还有代理网格体系结构n e t s o l v e 、g l o b u s 的积木体系结构、基于 对象模型的网格结构等其他的网格体系结构。 1 2 1 五层沙漏模型 五层沙漏体系结构【7 】是一种具有代表性的网格体系结构，由i a nf o s t e r 等提出， 其应用背景是科学研究领域。它是一个协议结构、以协议为中心，集成远程异构资 源和服务；是一个允许访问的基础平台。 沙漏结构的设计有以下几点原则： ( 1 ) 参与的开销要保持最小。提供一些作为基础的核心服务；移植方便、与 o s 内核类似。 ( 2 ) 允许局部的控制，需管辖多种资源。 ( 3 ) 需支持适应性。 ( 4 ) 用于构造高层特定领域的应用服务。 根据共享资源与各组成部分之间的距离，五层沙漏结构分别在五个层次分散开 对共享资源进行管理、操作和使用的各功能，从下至上依次为构造层( 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 1 所示。 其中，对各层的结构功能可描述如下： 构造层的功能是向上提供了一套访问的工具和接口，对局部资源进行控制。 连接层基于i n t c m e t 协议，针对g r i d 网络事务处理定义了验证和通信协议，实 现了资源之间地相互通信。 资源层建立在连接层的认证协议和通信之上，定义了一系列包括审计及时付费、 安全初始化监视控制单个资源的共享操作在内的协议，从而在单个组织内实现了 资源共享。 汇聚层主要是在多个资源组织之间协调资源的共享。 应用层存在于虚拟组织环境中，以应用程序员的角度来看网格结构，应用的构 4 第一章绪论 造是在任意层次定义的服务的基础之上。 应用层 工具及应用 汇聚层 蒜 资源层 ) 篙萎墓蓑蒿 ( 与连接层 构造层 纛赫冀纛等 图1 1 五层沙漏结构图 由图1 1 可见，五层结构中的连接层、资源层共同形成了瓶颈，使得这个结构 呈现出沙漏的形状。五层结构中内在的含义就是其中的各部分协议具有不同的数量， 对于结构中的最核心部分，要能够实现在所有支持网格计算的地点，核心协议都应 得到支持，因此核心协议不应有太多的数量，于是在协议层次结构中核心协议就形 成了瓶颈。 1 2 2 开放网格服务体系结构 2 0 0 2 年6 月，在全球网格论坛( g g f ) 上，g l o b u s 联盟首次提出了开放网格服务 体系结构o g s a 8 】( 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 bs e n ，i c e 【9 】技术，在五层沙漏结构基础上提出来的，但是从 1 2 1 节可知，以协议为核心的五层沙漏结构强调的是资源共享；而o g s a 却是以服 务为核心，这里的服务包括网络、存储资源、软件和计算资源等，而这都是一般意 义的服务，即为服务共享。o g s a 的结构如图1 2 所示。 o g s a 包括了w e bs e r v i c e 技术和网格技术这两大关键技术，定义了网格服务 ( g r i ds e r v i c e ) 地概念，使服务的思想更加明确和具体。把每一件事情均看做一个 网格服务就是o g s a 结构的含义，所以说它是面向服务的一种体系结构。并且o g s a 把互操作问题划分为两个子问题协议的识别和标准服务接口的定义，具体内容 包括局部远程透明，讨论标准接口定义机制，单一服务语义和自适应局部o s 服务 等。即为以标准的方式表达服务的功能，可以将任何实现激活，最后利用系统功能 及其已有的资源达到将资源虚拟化的目的。 5 青岛人学硕+ 学位论文 一个网格服务即为一个w e b 服务，能够兼容、扩展w e bs e r v i c e ，同时具有自 动产生c s 代码，服务的发现、描述等w e bs e r v i c e 特性，提供具有状态地服务。 简单说来，网格服务= 服务数据+ 接h 行为。因此网格在o g s a 结构中，可以看作 是网格功能服务的一个扩展集合。o g s a 的服务类型包括大量的瞬时服务和部分少 量的永久服务，并且服务遵循行为和网格服务接口的定义。 总之，o g s a 的基本思想是以服务为中心，o g s a 中的一切都是服务。这一结 构的意义就在于它没有将网格局限在科学和工程计算为中心的学术研究领域，而是 扩展到以分布式系统服务集成为主要特征的广泛的社会经济活动领域。 应用 o g s a 体系结构服务 o g s i w 曲s e r v i c e s o g s ao g s ao g s ao g s ao g s ao g s a 消息目录 安全 工作流文件系统数据 o g s ao g s ao g s a 网络 服务存储 图1 2o g s a 结构图 1 2 3 开放网格服务基础架构 o g s i 1 0 l ( o p e ng r i ds e r v i c ei n f r a s t r u c t u r e ) 是作为o g s a 的核心规范提出的， 2 0 0 3 7 正式发布o g s i1 0 版。o g s i 规范通过扩展使用w e b 服务定义语言 x m l s c h g i l l a 和w s d l ，以解决具有状态属性的w e b 服务问题。 o g s i 定义了核心行为和接口用来管理网格服务，包括信息模型( 监测和发现的 基础) 、生命周期及命名和绑定( 实现虚拟化的基础) 。发现服务属性、提供描述、管 理服务生命周期、创建服务实例和订购事件等是o g s i 的实现目的。除此之外，还 定义了信息交互、服务的创建管理以及定义了客户和网格服务之间的交互方式。因 为o g s i 需要接口组合、扩展，为了满足这些要求，w 3 cw s d l 工作组在w s d l l 2 版本中定义了标准接口的扩展，从而扩展了w s d l l 1 版本，定义出用于描述和命 名服务的g w s d l 、用于组内成员规则和成员管理的服务组( 注册的基础) ，此外还有 基本的错误类型。 另外，o g s i 被重要的商业组织和开源技术支持，这是它所具有的强大优势， 6 第一章绪论 使它的发展前景更为广阔，如在l b n lp y g l o b u s ( p y t h o n ) ，g l o b u st o o l k i t3 0 ( j a v a ， c ) ，uv i r g i n i a oo g s i n e t ( n e t ) ，um a n c h e s t e r ( p e r l ) ，ue d i n b u r g h ( n e t ) 和f u j i t s u u n i c o r e ( j a v a ) 平台或工具包中均可实现。 这样说来，前一节介绍的o g s a 平台服务就可以说是以o g s i 为基础的高层核 心服务，比如合同协商，数据访问与融合，服务发现，管理模型，安全和策略，消 息传递与监测等等，这些标准服务是在o a s i s ，g g f 等组织中均有定义的。 但是，对o g s i 也存在一些不满，主要集中在以下几点： ( 1 ) “面向对象”过于多，w e bs e r v i c e 是有状态的，而纯w e bs e r v i c e 实际 上是不存在状态和实例的。 ( 2 ) 由于不能使用现有的x m l 工具和w e b 服务开展工作，从而使扩展w s d l 非常困难。 ( 3 ) 在一个定义中存在了太多的混杂材料，却没有划分清晰的功能，从而支持 增量的发展。 ( 4 ) 由于推迟发布了w s d l 2 0 ，导致o g s i 重复了一些w s d l 的工作。 1 2 。4w e b 服务资源框架 2 0 0 4 年3 月，由i b m 、b e a 以及微软联合发布了w s a d d r e s s i n g 协议。i b m 和g l o b u s 联盟基于该协议规范迅速推出了w s p f t 】( w e bs e r v i c er e s o u r c e f r a m e w o r k ) w e b 服务资源框架。o a s i s ( 结构信息标准化促进组织) 随即成 立了两个技术委员会w s n t c ( 网络服务通告技术委员会) 和w s r f t c ( 网络 服务资源框架技术委员会) 。 w s r f 的产生和发展主要是由于以下原因： ( 1 ) o g s i 定义的基础之上，w s d l 的扩展类似于新的w s d l 2 0 支持的功能， 同时引入了状态服务。 ( 2 ) w e bs e r v i c e 技术的发展十分重要，如w s m e t a d a t a e x c h a n g e 提供了发布 服务的一些信息、w e b a d d r e s s i n g 独立于传输协议定位服务。 ( 3 ) w s d l 2 0 的出现。 此外，要求w e bs e r v i c e 可以提供用户操作服务和访问的状态数据，也需要定 义出用于管理服务状态数据的规范，便于应用以可操作和标准的方式观测、发现和 交互状态资源，而且因为要利用w e bs e r v i c e 的功能，所以不可以和w e bs e r v i c e 冲 突。 总的说来，w s r f 的需求基本源于三个方面：系统管理、网格计算以及商业计 算。它的目标就是可以根据w e bs e r v i c e 标准的建议，对w e bs e r v i c e 标准进行扩展， 并且定义出状态资源管理的规范。所以说从o g s it ow s r f 的过程实际上是个发展 和重构的过程。除此之外，还需要定义状态资源的w e bs e r v i c e 访问模式，w e ：b 7 青岛人学硕十学位论文 s e r v i c e 和“状态”的结合方式也需要在其规范中指出。 1 3 研究背景 因为网格的应用前景十分广泛，网格计算已经引起了各国工业界、学术界以及 政府高度的重视，成为了现今国际上研究的一个热点及前沿领域。 国际上目前已经出现了一大批的网格研究项目，其中：美国的c o n d o r 、l e g i o n 、 g l o b u s 等；同本的n i n f 等；澳大利亚的n i m r o d g 等；欧洲的m o l 、d a t a g r i d 等 是最具代表性的研究项目。 l e g i o n 项目起源于1 9 9 3 年弗吉尼亚大学地一个基于对象的元系统软件的项目。 l e g i o n 项目支持数据管理、透明调度、站点自治、容错和多种安全机制；它的目标 是为用户提供一致、单一的虚拟机器模型。 g l o b u s 项目始于2 0 世纪9 0 年代，由美国阿冈国家实验室承担，是目前国际上 极具影响力的网格计算项目之一。g l o b u s 项目的最初目标是把全美国的高性能计算 机中心网络化，从而提高高性能计算的使用效率，推进美国大学和研究机构研发进 度。网格计算环境中的各种资源共享，任一成员、用户、资源可以随时加入组织， 共同协作来完成各种分布式任务和应用。g l o b u s 工具软件在世界范围内得到了广泛 的应用，为全球的网格技术研究做出了巨大的贡献。 中国的网格研究开始于1 9 9 8 年，起步比国外要晚。但是由于非常重视网格的研 发，自2 0 0 0 年以来国内的网格研究取得了很大进展。国内开展的主要网格项目有： 先进计算机基础设施北京上海试点工程a c i ( a d v a n c e dc o m p u t a t i o n a l i n f r a s t r u c t u r e ) ，上海网格( s h a n g h a ig r i d ) ，高速互连研究试验网络( n s f c n e t ) ， 地质调查应用网格n g g ( n a t i o n a lg e o l o g i c a lg r i d ) ，数字林业应用网格，科学数 据网格s d g ( s c i e n t i f i cd a t ag r i d ) ，数字灌区网格，织女星网格( v e g ag r i d ) ，中 国教育科研网格( c h i n ag r i d ) ，中国国家网格c n g r i d ( c h i n an a t i o n a lg r i d ) 等。 上海信息网格【1 2 j 的目标是：依托地方重大科研攻关项目最新的研究成果、国家 教育部、国家自然科学基金和国家8 6 3 ，开发具有推广价值和自主知识产权的应用 开发环境、虚拟研究平台和信息网格系统软件，研究符合国际标准的关键技术和信 息网格体系结构，通过虚拟组织中的数据、计算、软件等各种各样信息的协同和共 享，初步实现交通信息网格的典型应用、建立出具有上海特色的信息网格。 由中科院计算所研发的织女星网格，使之具备下述几种能力是该项目的目标： 高性能计算能力、大规模的数据处理能力、以及具有提高资源利用率和资源共享的 能力。 教育部2 1 1 工程公共服务体系建设的重要专项之一的中国教育科研网格覆盖了 国内2 0 所高校，在2 0 0 5 年完成该项目的一期建设，这个项目的目标在于：将广泛 分布在高校中异构的海量资源和中国教育科研网c e r n e t 集成起来，消除资源孤 8 第一章绪论 岛，实现c e r n e t 环境下资源的有效共享，提供有效的服务，从而形成为国家教学 科研服务的大平台。 由国家8 6 3 高新技术研究发展计划资助的中国国家网格专项旨在建立面向国家 高性能计算环境，如政府部门、企业、科研机构、高等院校。中国国家网格专项的 主要任务包括：开发具有自主产权的网格应用软件；建设中国国家网格实验床 ( c n g d d ) ；建立具有4 万亿次以上计算能力的网格主节点；建设社会发展、科学 研究、国防建设和经济建设急需的重要应用网格。 1 4 本文主要的研究工作 1 4 1 本文研究内容和意义 我们可以看到，在网格的发展历程中网格技术在各个应用领域都有着巨大的潜 力，因此，研究网格中的关键技术，进而优化网格系统性能，便成为推动网格发展 进程的一项重要任务。 把网格计算和经济模型结合起来，使以系统为中心的网格环境转变为以用户为 中心的网格环境，对网格的发展有着跨越性的进步，具有巨大的实践意义。首先， 为了开展网格服务，经济模型将激励网格资源提供者构建大规模的网格环境，并且 明显有利于规范资源的请求和供应。其次，通过提供这样一个经济激励机制，用户 将会大量减少盲目请求高服务质量的资源，从而有利于提高系统的可靠性和吞吐量。 最后，网格计算和经济模型结合后，可以使网格资源提供者和网格用户之间互惠互 利，更加促进网格系统的飞速发展。 在网格经济环境中，网格资源管理是个难点，也是重点，传统资源管理方式难 以适应自治的、动态的、广域的网格环境。因此提出新的网格资源分配模型，并且 在这模型基础上提出合理的资源分配和定价策略，有效提高交易成功率和系统收益， 是网格发展中的一个重要研究方向。 本文便是在基于经济的网格资源管理范畴内，对网格资源分配和定价展开研究。 1 4 2 本文所做的主要工作 随着经济机制在网格环境中的引入，基于经济机制的网格资源管理，受到越来 越多的关注。其中，拍卖经济理论也已成为比较成熟的理论框架体系，得到了许多 普遍性结论，逐渐运用在网格环境中；但是随着经济社会飞速发展，传统的拍卖模 式已经不足以应对新的拍卖交易需求，尤其是在网格市场中参与交易的买卖双方数 量日益增长，更是对传统的拍卖机制提出了挑战。而双向拍卖却是恰好适用于网格 市场中买卖双方众多的交易，在网格资源管理中具有不可忽视的广阔前景，关于双 向拍卖理论在网格市场的应用更是应运而生。 9 青岛人学硕十学位论文 因此，本文基于双向拍卖理论，提出了一种新的资源分配模型，使得网格资源 买卖双方可以充分根据自己的实际需求和条件，参考以往相应资源的成交价格，得 到全面的交互，从而提高交易的成功率，节约交易时间和成本，实现网格市场中资 源的灵活管理。 并且，本文基于这个新的网格资源分配模型，提出相应的资源分配和定价策略。 在一次拍卖中，使得所有相应资源的交易价格相同，并且买卖双方可以交易多单位 的资源。通过统一拍卖方式，实现交易双方付费的灵活调节，同时考虑了双向拍卖 预算平衡、优势策略激励相容和个人理性的特点。 最后，利用网格模拟器g r i d s i m 对本文提出的网格资源分配和定价策略进行仿 真实验，证明本文的研究是可行并且有效的。 1 5 本文的组织结构 本论文结构如下： 第一章，绪论。首先介绍了网格的概念以及体系结构，其次对国内外研究现状 进行了分析。进而阐述了本文的主要研究工作和组织结构。 第二章，基于经济理论的网格资源管理。介绍了在网格资源管理中引入经济学 的优势和两种网格经济体系结构；并分析了目前在网格资源管理中常见的几种经济 模型，尤其是拍卖模型。 第三章，基于双向拍卖的网格资源分配和定价算法研究。这是本文的重点和创 新点所在。在本章提出了基于双向拍卖的资源分配模型，并详细阐述了适用于此模 型的资源分配和定价算法。 第四章，仿真实验。在g r i d s i m 环境下对本文所提出的网格资源分配策略进行 模拟测试，并和传统资源分配策略进行对比，表明本文所提出的策略的优越性。 第五章，总结和展望。总结了本篇论文的内容，并对以后基于本文内容的研究 工作进行了展望。 l o 第二章基丁经济理论的网格资源管理 第二章基于经济理论的网格资源管理 在大范围内实现资源共享正是网格的目的，所以，我们要面对的一个非常关键 的问题就是在网格环境中怎么做到有效的资源管理。 在资源管理的传统形式中，任务应该在哪里执行，是由确定的花费函数来决定 的。但是这些花费函数的一个共同点就是都以系统为中心，而不是由用户的质量 ( q o s ) 参数驱动，这些质量参数包括服务传送时间片、存取价格等；大部分系统都假 定资源的使用是按照相同价格的，这是与实际情况相悖的。因为网格用户的真正意 愿可能是综合考虑需求、优先权、可供使用的预算和价值协商得到某个特定价格， 而并不一定是要用最高的价格购买最有效的资源，因此，资源的实际使用情况，在 传统资源管理方法中不能得到很好反应。 经济学方法中，由网格用户的要求直接驱动调度的确定，而不是由单个调度实 体静态的完成。经济模型与只关注运行作业时软硬件花费的常规花费模型不同，塔 主要关注的是针对最终用户的服务收费。充满着竞争的经济市场中的主要驱动力正 是基于可用资源和需求的贸易，所以，网格资源拥有者之间及单个用户之间的竞争 是我们需要重视的。 本章中首先说明了在网格资源管理领域，经济理论的独特优势；然后分析了两 种网格经济体系结构；并在对几种可用于网格资源管理的经济模型做了简要介绍后， 尤其详细地介绍了拍卖模型；最后，我们介绍了目i j 在网格领域存在的主要定价方 案，从而为下一章中新的资源分配和定价方案提供了充分的理论基础。 2 1 在网格资源管理中引入经济学的优势 借鉴了现实生活中的商品交易这一活动过程，基于经济理论的网格资源管理成 为进行资源分配的方法之一，这种方法的前提便是实际应用中大量资源的有偿使用。 可以容易想到，要吸引资源提供者加入网格系统，就必须充分保证他们的利益，因 此，在网格环境中，资源提供者可以通过转让计算资源来获得利益，相对而言，资 源消费者可以通过购买资源来完成一些在自己的已有资源上无法完成的大型作业。 由此可见，网格环境下的资源分配涉及了资源消费者、资源提供者的个体行为，这 就让我们自然联想到用微观经济学中的一些经济模型，和经济学理论作为支持，来 管理网格资源。 之所以能够在网格资源管理中得到重视，是因为经济理论具有以下显著特征： ( 1 ) 鼓励资源提供者贡献他们的空闲资源、并使他们从中获利，从而用以协助 建立出大规模网格系统。并且根据资源“优质优价 的原则，鼓励更好资源的拥有 青岛人学硕十学位论文 者加入到网格中来，从而通过提供服务以得到利润。 ( 2 ) 所有的资源都可以通过经济的方式，得到统一的处理。参与交易的商品可 以包括：数据、内存、计算能力、仪器、网络带宽、设备、存储能力等。 ( 3 ) 以经济模型作为管理系统资源的基础，可以使得任何用户均可以公平地存 取网格资源。通过制定一定的规则，凡是通过这些规则的资源提供者，就可以加入 到网格环境中来与其他请求者公平竞争资源。 ( 4 ) 根据经济学理论，采用经济模型，有利于对网格资源的供需平衡进行调节： 情况一，供不应求时，可以通过提高资源的价格来增加资源提供者、减少资源消费 者；情况二，供过于求时，可以通过降低资源的价格来减少资源提供者、增加资源 消费者。由此可见，通过引入经济学理论，由价格的浮动来反映资源的供需情况变 化、由供需平衡来实现资源的优化分配，能够很好表现网格的动态特征。 ( 5 ) 允许按照q o s 需求，找到合适的资源给用户任务使用。这样，既能使资 源的浪费尽可能减少，又可以满足用户方面要求。即使在资源管理中，资源确定成 交价格时完全按照它自身的性能表现，那么该任务所匹配到的资源也几乎是此种情 况下得到的最优解。另外，提供了一种经济激励机制，用户在解决低优先级问题时 往后搁置，这样，就可以优先的执行时间紧迫的任务，从而便于提供q o s 服务。 ( 6 ) 提供了有效的资源管理和分配机制。 ( 7 ) 为了适应网格市场的不同需求，可以在网格的资源管理框架中，方便地利 用各种经济模型。资源消费者和资源提供者可以根据自己的实际情况来做出决策， 从而最大化各自的效用和利益。此外，将经济理论应用于网格环境，也极大的促进 了网格服务和现实经济的接轨，大幅度的推进了网格的发展。 2 2 网格经济的研究 2 2 1 网格经济体系结构 关于如何搭建网格经济环境的技术就称之为网格经济体系结构，它给出了网格 经济的基本组成和相应功能，描述了网格经济市场中各个组成部分的关系和这些组 成部分的集成方式或方法，刻画出了有效支持网格经济运转的机制。截至目前，有 两个网格经济体系结构比较重要：一是由全球网格论坛g g f 发布出的网格经济服务 结构g e s “1 3 】；另一个就是由r a j k u m a rb u y y a 提出的分布式计算经济网格体系 结构乜r a c e 【1 4 】。 下面分别介绍这两种网格经济体系结构。 ( 1 ) g e s a 体系结构： g e s a 结构由o g s a 发展得到，组成部分包括o g s a 中的基础服务和扩展服务。 在o g s a 的基础上，g e s a 增加了收费、支付和记账等功能，它能够实现现有网格 1 2 第二章基于经济理论的网格资源管理 服务的封装，这种封装的实现是通过设置提供者出售资源时的报价和用户使用服务 的费用，因此 兑g e s a 是o g s a 结构的过渡，从而保持了强大的灵活性。 在g e s a 内部体系结构中，服务数据单元( s e r v i c ed a t e ) 中包含了网格服务的基 础元素，而附加的对服务经济状态进行描述的服务是由可记账的网格服务( s e r v i c e c h a r g i n g ) 产生的。网格用户通过标准网格服务接口( s e r v i c ei n t e r f a c e ) 实现对网格资源 的访问，授权用户的任何调用都必须通过基础网格服务验证( c o n t r a c tv e r i f i c a t i o n ) 。 服务调用完成后，由扩展的服务资源使用服务( o g s ar e s o u r c eu s a g es e r v i c e ) 对服务使用资源的情况进行记录。费用计量是根据服务调用过程中的资源( c p u 时 问、磁盘空间或内存等) 数量，而并非根据服务调用次数收费。使用服务产生的费 用传送给另一扩展服务网格银行服务