（计算机软件与理论专业论文）基于经济网格资源分配算法研究.pdf

摘要 网格是继互联网、w e b 之后出现的一种新型网络计算平台，以资源共享为主 要特征。本文是以经济网格的重要框架g r a c e 为基础，对经济网格中资源配置方 案进行研究和优化。研究目标是解决网格资源分配中用户价格协商问题，并验证所 提方法的优越性。本文首先从网格经济g r a c e 基本框架、资源分配的模型着手， 设计并实现了基于价格浮动策略和信誉度评估策略相结合的网格资源分配算法，最 终通过仿真试验对算法进行了评估，内容主要包括基于价格浮动的资源分配、优化 资源选择目标函数、基于信誉度评估的分布式跨域资源分配以及优化价格浮动函 数，主要研究成果为以下几点： ( 1 ) 提出一种基于价格浮动的资源分配策略，改善了资源价格随市场波动的 自适应性。在经济网格中，影响资源价格的因素很多，主要有资源提供者g s p 的 信誉度，交易成功率，交易收益率等。当交易结束后，应及时更新资源的价格，使 资源价格受市场的影响而波动。结果表明，此种方案能提高交易的成功率和网格节 点的收益值。 ( 2 ) 优化了资源选择目标函数。当网格服务消费者( g s c ) 选择g s p 进行交 易之前，通过目标函数确定最终的g s p 。本文设计并实现了所提资源分配策略中的 目标函数，并通过试验验证其合理性。 ( 3 ) 通过分析网格环境中分布式跨域信誉度评估模型，并结合经济原理引入 价格浮动机制，在考虑了跨域交易的网格负载的前提下，提出一种基于信誉度评估 和价格浮动的分布式资源分配策略。通过试验验证具有较好的服务质量和网格通信 开销。 关键字：经济网格；资源分配；目标函数；价格浮动；信誉度 a b s t r a c t g r i di san e wc o m p u t i n gp l a t f o r ma f t e ri n t e m e ta n dw e b i t sm a i nc h a r a c t e ri s s h a r i n gr e s o u r c e s i nt h i sp a p e r , w er e s e a r c ha n do p t i m i z et h eg r i dr e s o u r c ea l l o c a t i o n s c h e m e sb a s e do nt h ei m p o r t a n tf r a m eg p 溘c ei ne c o n o m i cg r i d t h i so b j e c t i v eo ft h i s r e s e a r c hi st os o l v et h ep r o b l e mo fg r i du s e rn e g o t i a t i n gp r i c ei ng r i dr e s o u r c ea l l o c a t i o n a n dt ot e s tt h es c h e m e sp r o p o s e d f i r s t l y , w ei n t r o d u c eg r a c ea n dm o d e l si nr e s o u r c e a l l o c a t i o nb a s e do ne c o n o m i c 鲥d s e c o n d l y , u n i t i n gt h ep r i c ef l u c t u a t i o nt or e p u t a t i o n s c h e m e ，w ep r o p o s eo n en e wr e s o u r c ea l l o c a t i o ns c h e m ea n do n ed i s t r i b u t e dr e s o u r c e a l l o c a t i o ns c h e m ei ne c o n o m i cg r i d a tl a s t ，w et e s tt h e s es c h e m e s ，a n ds h o wt h a tt h e s e n e wm e t h o d sc a ni m p r o v et h er e s o u r c es e r v i c es u c c e s s f u lr a t ea n dt h eg r i dp r o f i t s t h e m a i nc o n t e n t sa r et h er e s o u r c ep r i c ef l u c t u a t i o na l g o r i t h m ，g o a lf u n c t i o ni nr e s o u r c e s e l e c t i o n ，a n dd i s t r i b u t e dr e s o u r c ea l l o c a t i o nb a s e do nr e p u t a t i o na n dp r i c ef l u c t u a t i o n t h ep r i m a r yc o n t r i b u t i o n so ft h i st h e s i si n c l u d e ： 1 g r i dr e s o u r c ea l l o c a t i o n s t r a t e g yb a s e do np r i c ef l u c t u a t i o na n dr e p u t a t i o n m e t h o di sp r o p o s e dt os o l v et h ep r o b l e mo fg s p sp r i c ec h a n g e dt oa d a p tt ot h eg r i d m a r k e t t h e r ea r em a n yi n f l u e n c i n gf a c t o r si ng r i de n v i r o n m e n t ，s u c ha st h er e p u t a t i o n ， t r a d es u c c e s s f u lr a t e ，t h eg s p sp r o f i ta n ds oo n o n c et h et r a d ei se n d ，t h ep r i c cs h o u l d b eu p d a t e dt oa d a p tt ot h eg r i dm a r k e t f r o mt h es i m u l a t et e s t , w ef i n dt h i ss t r a t e g yc a n i m p r o v et h et r a d es u c c e s s f u lr a t ea n dt h eg r i d sp r o f i t 2 o p t i m i z et h eg o a lf u n c t i o n i ne c o n o m i c 鲥d ，w h e ng s c n e e d st os e l e c tt h em o s t a p p r o p r i a t eg s p , m a n yf a c t o r sm a yi n f l u e n tt h eg s c s oa no p t i m a lg o a lf u n c t i o ni s v e r yi m p o r t a n t i nt h i sp a p e r , w ep r o p o s eag o a lf u n c t i o nf o rg s c ，a n dt h et e s tr e s u l t s s h o wt h a ti ti se f f e c t i v e 3 w ep r o p o s ead i s t r i b u t e 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 nt h ev i r t u a l o r g a n i z a t i o n a ld o m a i n ( v o d ) i nt h i ss t r a t e g y , w ec o n s i d e r e dt h en e t w o r kl o a da n d d i s t r i b u t e dr e p u t a t i o nb a s e do nv o d t h et e s tr e s u l t ss h o wt h a tt h es t r a t e g yc a nd e c r e a s e t h en e t w o r kl o a da n d 断dr e s o u r c ec o n s u m p t i o n k e y w o r d s ：e c o n o m i cg r i d ；r e s o u r c ea l l o c a t i o n ；g o a lf u n c t i o n ；p r i c ef l u c t u a t i o n ； r e p u t a t i o n 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：骂z ，多日期：z 叫年，月t 口日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 用) 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密醴 ( 请在以上方框内打“4 ) 日期：哆年f 月口日 日期矽盯月，口日 ，未经许可，任何单位及任何个人不得擅自使 纂一章绪谂 第一章绪论 网格l l 鼬l 计算起源予美国政府资助的高性能计算科研项目。网格计算的网的是 把跨地区的多台高性戆计算机、大型数据库、贵重科研设备、可视化设备和善种传 感器等整合成一个邕丈的超级计算机系统，支持科学计算和科学研究，实现计算资 源、存储资源、数据资源、信息资源、袈箨资源、避信资源、絮谈资源、专家资源 等的全面共享。从董9 9 3 年开始，高性熊计算技术和互联网技术相互融合，酝酿并 产生了继嚣特网、w e b 之霜的第三大技术浪潮，这就是网格计算( g r i dc o m p u t i n g ) 。 1 1 网格技术概述 l 。1 1 网格计算的概念和特点 董) 瓣貉麓概念 囊网格捧这一术语的思想源予酲常生活中公共设施的应用。人们对网格懿界定 大致可以分为两种，群狭义的“网格鼹和广义的搿穗格观嚣。其中狭义“网格溉静 是以g l o b u s l 4 1 项目的领导入i a nf o s t e r 为代表，他曾在1 9 9 8 年出版的网格：2 1 世 纪信息技术基础设施的蓝图一书中这样描述湖格：搿网格是构筑在互联阙土的一 组新兴技术，它将高速嚣联网、高性麓计算机、大趟数据库、传感器、远程设备等 融为一体，为科技人员和普通老酉姓提供更多的资源、功能帮交互性。 蔫另一些入剿赞弱广义蠹孽霹鞯溉0 并把它称俸巨大全球瓣络( g r e a tg l o b a l g r i d ) 它不仅包括计葬隧格、数据霹格、信息网格、知识网格、商业网格，还包播 一些已有的网络计算模式，例如对等计算( p e e r - t o - p e e r ) 、进化计算等。豳予瓣格 处于动态发展的过程中，所以目前还没有一个被普遍接受的定义。网格计算研究的 先导i a nf o s t e r 给网格下的定义是：网格计算1 1 l 是动态多机构虚拟组织中的一个协调 的共享资源和解决闻题的过程。 2 ) 网格的特点 无论是麓革酶计算系统还是复杂的集群系统、弗符系统、分舞式系统，都存在 着不同的资源，如内存、储存空间、带宽等都楚资源。与传统的资源裙魄，阙格资 源具有如下特点。 多层次上的异构性：构成计算网格的计算资源和网络连接常常是高度异构 的，这种异构特性表现在各个层次上，从硬件设备、系统软件到调度策略、安全策 略、使用策略等等都舆有异构性。这是由计算溺格所面临的现实环境决定的网。 可扩充性和w 选择性：两格首先必须保证系统的可扩充性。网格中广域范 青岛大学硕士学位论文 围内的并行与分布式计算，拥有庞大的计算机资源，可扩充性是一个网格的基本特 点。任何应用都可以根据自己在连接特性、开销、安全和可靠性等方面的要求选择 适合的计算资源完成计算。局部的优先级规则、策略和预算方法，在网格环境下将 不再具有良好的可扩展性。 动态性与不可预测性：传统上，高性能应用一般在单独一类系统上开发， 很多特性是固定、可知的。然而，网格的应用要求执行在较广泛的环境中，这种环 境是由适合资源动态构成的。这就导致了执行系统的结构和特性很难确定，动态变 化，无法进行预测。同时，资源在地理上的分布式特性以及网络环境的复杂性更加 剧了这一点。传统的高性能应用系统往往可以预测其对处理机和网络的访问，而在 计算网格中，资源特别是网络链路很可能是共享的，其结果是系统行为和性能随时 间而变化。此外，大规模的计算网格也可能会遇到资源和网络的失效，以致无法保 证基本的服务质量要求，这又会导致应用系统的行为无法预测。在本地化管理的组 织中，这些需求随着时间的变化保持相对稳定，需求能够被比较容易地预测和测量。 与此相反，在网格环境中，需求可能是零星的和不均匀的，因为异构的和分散的用 户群对资源的需求会受到非传统的和难以预计的因素影响。 自治性和管理的多重特性：网格应用所使用的资源通常不是只被一个组织 拥有和管理，而是由多个组织的管理实体管理自身的计算资源1 7 , 8 1 。网格上的资源， 首先是属于某一个组织或个人的，网格资源的拥有者对该资源具有最高级别的管理 权限，网格应该允许资源拥有者对其资源有自主的管理能力，这是网格的自治性。 其次，网格资源也必须接受网格的统一管理，否则不同的资源就无法建立相互之间 的联系，无法实现共享和互操作，无法作为一个整体为更多的用户提供方便的服务， 因此网格的管理具有多重性。不同组织的管理实体可能采用不同的管理机制、不同 的验证机制、授权机制和访问机制，这使得本已令人头疼的网络安全问题更加复杂。 同时，要求网格计算要解决用户代码的远程执行问题、资源的协作分配问题以及分 布和并发调度问题等，而传统的资源分配和收费方法已经不能满足需要。 1 1 2 网格的目标 网格的目标是让网格用户能够容易地访问网格资源【2 l 。在网格上，人们不需要 使用远程登陆( t e l n e t ) 、文件传输协议( 肿) 等网络工具就可以使用远程节点上 的信息资源，还可以共享使用网格上的各种计算资源，包括c p u 、存储器、天文望 远镜、电子显微镜、数据库、软件等。网格的目标本身不在于规模的大小，而在于 可共享资源的种类、共享使用资源的形式、对用户共享资源的要求、共享的透明程 度、接口的简单程度等。网格将分布在不同地理位置的计算机通过国际互联网和网 格软件组成新的计算环境。网格软件中的资源管理模块提供管理各种资源的能力， 2 第一章绪论 为用户共享资源提供良好的接口。通过网格，位于北京的一个用户，可以把自己的 一个计算作业提交给网格，让位于上海的高性能计算机集群为自己完成计算，自己 不必花许多钱去建立一个自己的计算机集群。 1 1 3 网格的发展前景 网格技术凭借其分布式计算模式以及独特的联合计算能力，在学科研究、企业 信息处理、电子政务、个人娱乐方面拥有广泛的应用前景。网格计算利用分布式计 算机网络处理大量计算任务，可以最大限度地利用现有网络的计算能力，而不必为 增加信息处理能力而添置新的设备；通过租用网格的计算能力，可以实现许多以前 因计算能力不够，或者因增加计算能力导致成本过高而难以实现的商业应用。网格 技术发展的必然趋势是全球范围内的标准化、技术融合和大型化【9 】。 1 ) 标准化趋势：就像i n t e m e t 需要依赖t c p i p 协议一样，网格也需要依赖标 准协议才能共享和互通。 2 ) 技术融合趋势：基于o g s a 之后，网格的一切对外功能都以网格服务 ( g r i d s e r v i c e ) 来体现，并借助一些现成的、与平台无关的技术，如x m l 、s o a p 、 w s d l 、u d d i 、w s f l 、w s e l 等，来实现这些服务的描述、查找、访问和信息传 输等功能。这样，一切平台及所使用技术的异构性都被屏蔽。 3 ) 大型化趋势：近些年来，国外包括美、英、日在内的一些国家每年都投入 高额经费，用于跨域甚至跨国的大型网格项目的建设。 1 1 4 网格技术研究现状 1 ) 国外研究现状 美国的g l o b u s 项目是全球最具影响的网格计算项目之一，它对全世界的网 格研发工作起到了巨大的推动作用。该项目要开发一个面向科学计算的基本软件基 础设施，利用这一设施，把不同地理位置上的计算资源和信息资源集成起来。同时， 该项目还研究网格计算的关键理论，具体包括资源管理、网格安全、信息服务、数 据管理等；开发支持网格计算的工具软件和网格应用程序；帮助规划和组建大型的 网格试验平台。 l e g i o n ! l o l 是美国弗吉尼亚大学于1 9 9 3 年提出的一个基于对象的元系统软件 项目。其目标是为用户提供单一、一致的虚拟机器模型。在l e g i o n 内，将硬件和软 件等一些实体都视为对象，每一个对象由其类对象定义和管理，l e g i o n 中类对象的 作用相当于管理者，它除了定义实例之外，还制定管理策略。 ， 欧洲数据网格e d g l l l j ( e u r o p e a nd a t ag r i d ) 是一个国际性的大型研究和技 3 青岛大学硕士学位论文 术发展项目。该项目的主要目标是建设提供计算强度大、共享超过1 0 1 4 b 数据的大 规模分布式数据库的下一代计算基础设施。e d g 主要针对高能物理应用，解决海量 数据的分解存贮和处理问题，提供突破地理局限，允许分布在世界各地的工作者交 互、共享数据和设备，共同开展科学研究的合作环境。 英国政府开展了e - s c i e n c e 【1 2 1 计划，他们认定网格是w o r l dw i d ew e b 的必然 后继者，投资2 亿英镑左右支持网格研究，并确定了用网格计算技术构建e - s c i e n c e ， 为大规模科学研究提供基于i n t e r n e t 的分布式全球操作计算环境。其应用包括粒子 物理、生物信息学、气候环境变化、工程系统设计等多学科领域。e - s c i e n c e 计划联 合多所大学、国家级研究所和工业界共同完成多学科的大规模科研信息基础设施和 环境建设。 u n i c o r n 1 3 】是德国联邦教育和研究部资助的一个项目。参加研究的有中等 范围天气预报欧洲中心、莱布尼兹计算中心、卡尔斯鲁尔计算中心、惠普公司、国 际商务机器公司、富士通公司等。其目的是提供一套软件，该软件支持并允许用户 向远程高性能计算机提交自己的作业，而无需知道远程计算机的操作系统、数据存 储格式、管理策略和过程。它充分利用了已有的万维网技术。授权用户可以通过浏 览器和接口访问任何地方的u n i c o r n 资源。 n o r d u 1 4 】网格是北欧四国挪威、丹麦、瑞典、芬兰利用网格中间件建设的网 格基础设施，n o r d u 网格主要由计算元素、存储元素、复制目录、信息系统、网格 管理器用户接口等部分构成。 b r i c k s 1 5 l 是日本的一个网格研究项目，它是一个性能评价系统，允许在典型 的高性能全球计算环境上分析和评价不同调度策略，同时，它还可以模拟异地全球 计算系统的不同行为，尤其是网络的行为和资源调度算法的行为。n i n f 是日本全球 计算基础设施项目，它允许用户访问分布在广域网上的资源，包括软件、硬件和数 据。n i n f 目前正在实施。 韩国的网格计划之一是n g r i d 1 6 l ，这是韩国情报和通信部支持的一个项目。 n g r i d 的目标是建立韩国国家网格，该项目包括计算网格、数据网格、访问网格和 应用网格。它将韩国的超级计算机和高性能机群连接在一起，建立应用试验床、应 用门户和开发具体的应用程序。 2 ) 国内研究现状 在我国，网格研究已列入“8 6 3 计划 。中国科学院计算技术研究所从1 9 9 6 年 开始了网格技术的研究开发工作。2 0 0 0 年，开发了连接国内8 个曙光计算中心的网 格。中国科学院计算技术研究所把网格研究当作一个长期、重要、具有发展潜力的 研究方向。2 0 0 1 年提出了织女星网格计算，该计划包括从低到高的网格操作系统、 信息网格、知识网格三个层次。三个层次的研究齐头并进，并在三个层次上都取得 4 第一章绪论 了一定的成绩。它设计实现了织女星网格操作系统，并把它当作网格计算环境，在 其上开始相关的研究工作。计算所六个研究室中四个研究室的研究人员参与了织女 星网格的工作。在网格硬件层面，计算所的主要工作是研究下一代曙光高性能计算 机，它们将是面向网格的超级服务器。在网格系统软件层面，计算所正在研究开发 一个网格计算协议栈，以及有效支持网格计算协议的织女星网格操作系统。在网格 应用层面，计算机所主要开展了信息网格和知识网格的研究工作，科学计算类的应 用网格研究则有合作伙伴完成。 我国已开展了“中国国家网格、“教育科研网格 、“织女星网格 和“先进计 算基础设施北京、上海试点工程 等五大网格项目的研究。参与我国网格研究的主 要有中科院计算所、清华大学、华中科技大学、国防科技大学、中国科技大学、江 南计算所等几家在高性能计算方面有较强实力的研究单位。“8 6 3 网格研究项目的 启动使我国的网格研究迅速向世界水平迈进。 1 1 5 网格计算中的资源调度 网格计算的目的是使人们可以无缝地集成广域资源来合作解决问题，因此，在 网格环境里如何有效地管理资源和分配资源就成为影响网格计算是否成功的重要 的因素之一。同时，由于资源在广域上分布、本质上异构、由不同的个人或组织拥 有、具有不同的存取和开销模式、负载和可用性动态变化等，使得网格环境下的资 源管理十分复杂和具有挑战性。下面对网格计算中的资源调度的特点、分类和目标 进行一下概述。 1 ) 网格资源调度特点 传统计算系统的资源管理已经得到了比较充分的研究，如批调度器、工作流引 擎和操作系统。网格资源管理与传统资源管理的目标都是高效、合理地利用资源， 且都具有并发性、共享性和随机性的特点，但他们之间又有着很大的不同，他们的 根本区别在于网格资源具有广域分布性、异构性和动态性。由此可见网格资源的调 度具有如下的几个特点： 资源的分布自治性。资源跨多个管理域，地理上分布、自治、规模庞大， g r m s ( g l o b a lr e s o u r c em a n a g e m e n ts y s t e m ) 需要支持资源、用户的全局命名空间； 资源的共享与私有并存，不同的管理域有不同的本地资源管理系统l r m s ( l o c a l r e s o u r c em a n a g e m e n ts y s t e m ) ，g r m s 对资源无完全的控制，需与l r m s 交互，共 同使用资源。 资源平台的异构性。由于网格系统是由分布在i n t e m e t 上的各类资源组成的， 包括各类主机、工作站甚至p c 机，它们是异构的，可运行在u n i x ，w i n d o w sn t 等多种操作系统下，也可以是上述机型的机群系统、大型存储设备、数据库或其他 s 青岛大学硕士学位论文 设备因此网格系统中的任务调度必须面向异构平台，并在这些平台上实现网格资 源的调度。 资源调度的非集中性。由于网格系统是一个大到整个i n t e r a c t 的分布式系统， 要实现一种全局的统一集中的资源调度管理是很难实现的。因此，网格必须以分布、 并行方式进行资源管理与调度。 资源可扩展性。网格系统初期的计算规模较小，随着超级计算机系统的不 断加入，系统的计算规模也必将随之扩大。因此，在网格资源规模不断扩大、应用 不断增长的情况下，网格系统的资源调度必须具有可扩展性，不致降低网格系统的 性能 资源调度的自适应性。网格中的资源不但是异构的而且网格的结构总是不 停地改变，有的资源出现了故障，有的新资源要加入到网格中，有些资源重新开始 工作等。总之网格的动态性是明显的，所以任务调度系统必须适应网格的这种动态 性，从可利用的资源中选取最佳资源为用户提供应用服务。 资源的协同性。很多网格任务需要跨域协同分配多个资源。g r m s 需完成 跨域的资源协同分配，这需要了解不同域的安全机制、资源特征，进行任务的跟踪， 处理各种形式的异常。 2 ) 网格资源调度分类 从不同的观察角度可把网格中资源调度策略按照不同的标准分类。根据调度策 略的目的，把网格资源调度策略分成三种： 面向应用的调度策略。它是从特定任务的角度来衡量每个可能的调度方案， 从中选择最大程度满足特定任务调度方案要求的资源调度策略。不同的任务可能有 不同的要求，一般的要求是尽量缩短任务执行时间。其他的要求包括：在使用计费 资源时最小化费用；在多个资源可用的情况下优先使用某个资源等。目前大部分调 度策略都属于这一类。 面向系统的调度策略。它是从整个系统的角度来衡量每个可能的资源调度 方案，从中选择能最大程度提高整个系统的性能，如吞吐率、资源利用率、负载均 衡等方案的调度策略。值得注意的是，在一个由许多组织域( o r g a n i z a t i o n a ld o m a i n ) 组成的，有多种任务的网格中，如果把整个网格作为一个系统，它的性能将无法衡 量。所以可以把网格在同一个组织域中的部分作为一个系统，由域中的管理者来进 行系统级的资源调度，即把整个网格划分成多个系统，在每个系统内执行资源管理。 在系统内采用面向系统的调度策略，在客户端采取面向应用的调度策略能在一定程 度上取长补短，同时兼顾应用任务和系统整体的性能。 面向资源市场的调度策略。除了上述两类调度策略外，还有无法划入两种 中任意一种的调度策略，最主要的是面向“资源市场”调度策略。这种调度策略由 6 第一章绪论 澳大利亚m e l b o u r n e 大学的r a j k u m a rb u y y a 最早提出，它的主要思想如下，把网格 环境和市场环境进行类比，用户作为买方，而资源的拥有者作为卖方，资源调度的 过程就是买卖双方的交易过程，并把宏观经济学和微观经济学的各种模型应用到网 格资源调度过程中，如拍卖模型、商品模型等。 3 ) 网格资源调度目标 简单地说，网格资源调度的目标就是要对用户提交的任务实现最优调度，并设 法提高网格系统的总体吞吐率。具体的目标包括：最优跨度( o p t i m a lm a k e s p a n ) 、 服务质量q o s ( q u a l i t yo fs e r v i c e ) 、负载均衡( l o a db a l a n c e ) 、经济原则( e c o n o m i c p r i n c i p l e ) 。 最优跨度。跨度指的是调度的长度，也就是从第一个任务开始运行到最后 一个任务运行完毕所经历的时间。跨度越短说明调度策略越好。当用户向网格系统 提交任务后，最大的愿望之一是网格系统尽快完成自己的任务。可见，实现最优跨 度是用户和网格系统的共同目标。 服务质量q o s 。网格系统要为用户提供计算和存储服务时，用户对服务的 要求是通过q o s 形式反映出来的。资源管理与调度系统在进行分配调度任务时，应 当保障网格应用的q o s 。 负载均衡。在开发并行和分布计算应用时，负载均衡是一个关键问题。网 格系统更进一步扩展了这个问题。网格资源调度是涉及交叉域和大规模应用的调 度，解决好系统的负载均衡是一个非常重要的问题。 经济原则。在经济模型环境中，网格的资源在地理上是广泛分布的，而且 每个资源都归属于不同的组织，都有各自的资源管理机制和政策。根据现实生活中 的市场经济原则，不同资源的使用费用也应是各不相同的。市场经济驱动的资源管 理与任务调度必须使消费双方( 资源使用者和资源提供者) 互惠互利，才能使网格 系统长久地发展下去。 1 2 本文研究背景、目的和意义 随着w e b ，x m l 技术的迅速发展，网格正在从以前以计算驱动的网格环境渐 渐转变为以服务驱动的下一代网格环境i 。同时，网格中用于共享的资源种类也越 来越多，不仅仅限制于物理资源，像带宽资源，安全性能，系统稳定性等逐渐的成 为了网格资源的重要组成部分【1 2 1 。然而，目前大多数网格环境中资源的共享都是 自愿的。大家自觉的把资源拿出来，共同组成一个网格系统，来进行研究和学习。 这就会导致一系列问题。比如用户为了满足自己的服务质量q o s 的需要，总是贪婪 的通过竞争服务资源获得最好的服务质量，这样造成了资源的无效使用，进而降低 了系统的性能。因此将经济模型与网格计算相结合，在网格中加入经济激励机制和 7 青岛大学硕士学位论文 q o s 定价策略便显得非常有必要。当用户将不再无偿使用资源时，用户就会根据自 己对服务质量要求和承受价格，来综合考虑自己所需要申请使用的资源。从而保证 了网格系统的性能。 将网格计算和经济模型相结合，使以系统为中心的网格环境向以用户为中心的 网格环境转变，对网格的发展有着重要的实践意义。首先它将激励资源提供者构建 一个大规模的网格环境，来开展网格服务。并且有助于规范资源的提供和请求。其 次，通过给用户提供一个经济激励机制，将减少对高服务质量资源的盲目请求，提 高了系统的吞吐量和可靠性。最后它可以使用户和资源提供者达到双赢，促进网格 系统的发展。 在网格经济环境中，资源调度系统是其重要的组成部分，它要根据任务信息采 用适当的策略把不同的资源分配给相应的任务。由于网格系统的异构性和动态性， 以及运行于网格系统之中的应用程序对于资源的不同需求，使得资源调度变得极其 复杂。一个不恰当的资源分配策略，将会增加任务的执行时间、降低整个网格系统 的吞吐量，降低网格系统的效率，也会降低网格资源提供者的利润，提高网格资源 使用者的成本。因此，网格经济环境下的资源分配是实现网格经济的关键，也是一 个非常值得研究的课题。 1 3 本文所做的主要工作 网格经济作为网格计算领域中较新的研究方向，目前已经在部分领域有了初步 的应用。但由于理论较不成熟和经济问题的复杂性，在实际应用过程中必然遇到很 多困难，目前，网格经济中各项机制并不完善。主要表现在以下几个方面： 1 ) 定价机制的不成熟性。现今研究的g r a c e 2 2 1 模型中加入了价格浮动机制模 块，但在实际应用中在价格浮动的管理上没有理想的价格浮动函数，使得网格中资 源的动态价格难以得到有效的控制。 2 ) 在网格系统中，为了使多个虚拟组织域间的资源得到共享和合理地分配， 根据现有的分布式信誉度框架下的资源分配策略进行研究，并权衡虚拟组织域间通 信和域内通信，以达到资源的最优分配和高效的系统性能。 本文探讨的是网格经济中的资源分配策略，通过学习现阶段的网格经济模型和 加入价格管理模块和信誉度评估模块的改进模型后，结合资源分配策略研究中的长 处和不足，做了以下相关工作： 1 ) 对g r a c e 模型框架进行系统研究学习，了解并掌握基于信誉评估的g r a c e 模型框架。 2 ) 对价格浮动模块进行深入研究，在基于信誉度的评估模型下，提出一种价 格浮动的资源分配方法，使资源在网格中得到较好地分配，提高了系统的收益情况。 8 第一章绪论 3 ) 结合分布式信誉评估模型，提出并实现了一种分布式跨域访问的资源分配 方法，提高了网格系统的性能和服务质量。 4 ) 通过网格模拟器g r i d s i m 对提出的资源分配策略进行了仿真试验，证明了 本文提出的方法能有效的提高网格的系统性能和服务质量。 1 4 本文的组织结构 本文共分七章： 第一章，绪论。介绍了网格的基本概念，网格的研究现状和热点，介绍了网格 中的资源分配的相关知识。然后说明了本文的研究目的和意义，列出本文所做的主 要工作和后面章节的结构安排。 第二章，网格经济概述。介绍网格计算中引入经济学的目的和意义，介绍目前 经济网格的研究现状和经济网格中的资源管理相关知识。 第三章，基于信誉度的经济网格体系结构。描述在g r a c e 框架中加入信誉度 评估模块和价格浮动模块的新的网格体系结构，介绍框架的核心组成模块。 第四章，基于价格浮动的网格资源分配策略。通过对价格浮动管理模块的描述 提出一种价格浮动函数进行交易价格的管理，并通过理论分析和试验证明这种方法 的可行性和优越性。 第五章，基于信誉度的分布式跨域资源分配策略。提出一种网格环境下跨组织 域的分布式资源分配策略，对分布式信誉评估函数作了改进，考虑了域间通信的开 销因素，提出了优化的目标函数，通过试验证明了此策略将提高网格的性能和服务 质量。 第六章，仿真试验。通过g r i d s i m 网格模拟器对本文提出的分配策略进行仿真 试验，对试验结果进行分析和评价。 第七章，总结和展望。总结了本文的工作，并对以后的研究进行了展望。 9 青岛大学硕士学位论文 2 1 网格经济概念 第二章网格经济概述 经济学的方法成功地管理了当前人类经济生活中存在的分布性和异构性问题。 经济模型增强了网格的社会结构，因此保证了它的稳定性和效率。由于网格环境的 动态性，不可能预先定义一个资源的价格、性能、供求关系的数据表来实现网格资 源的中介。借鉴人类社会的市场调节模型，需要在网格中建立一个市场模型，通过 市场调节供求关系和资源价格，提供一个公共的解决方案。 虽然网格经济目前没有统一的定义，但是通常我们把基于经济机制的网格资源 选择、分配、控制和支付的整个系统( e c o s y s t e m ) 称为网格经济( g r i de c o n o m i c s ) ， 其相关研究领域包括：电子商务、网络经济、基于市场机制的控制( m a r k e t b a s e d c o n t r 0 1 ) 、经济工程学( e c o n o m i c se n g i n e e r i n g ) 等。 竞争的经济模型可提供一些算法、策略和工具，来解决网格系统的资源共享与 分配问题。许多经济模式包括微观经济学和宏观经济学，其原则包括：商品市场模 式、价格发布模式、议价模式、招投标模式、合同网模式、拍卖模式、基于标的比 例( p r o p o r t i o n a l ) 的资源共享模式、协作交换模式、垄断与寡头模式等。 2 2 网格经济的研究现状 网格计算引入经济学理论和模型后得到了快速的发展，许多国家和机构都对网 格经济产生浓厚的兴趣，并投入了大量的资金和精力。 2 2 1u ke - s c i e n c e 项目 u k e s c i e n c e 项目由u k sc o r ep r o g r a m 制定并实施，目的为学术界和商业团体 开发网格经济的基础设施。英国网格支持中心通过u ke s c i e n c e 网格基础设施配置 资源。实施这个项目有两个主要目标：一是开发基于o g s a 的支持网格服务交易基 础设施，在这个基础设施上开发多种经济模型，应用经济模型在u kc s c i e n c e 中心 配置资源。通过分布的实验床开发实用化的网格服务的收费、记账支付系统。另外 一个目的是通过这个项目建立网格经济体系结构国际标准。根据这个项目制定的网 格经济服务结构g e s a 2 3 j ( g r i de c o n o m i cs e r v i c e s a r c h i t e c t u r e ) 标准已经由全球网 格论坛g g f 2 4 1 ( g l o b a lg r i df o r u m ) 发布。 1 0 第二章网格经济概述 2 2 2n i m r o d g 网格资源代理 n i m r o d g 【2 2 】是由澳大利亚m o n t h 大学的r a j k u m e r b u y y a 领导的网格经济研究 项目。n i m r o d - g 是基于对市场体制在分布式网格环境下的应用，为了合理地配置 资源，调节资源的供给和需求，b u y y a 提出了一个分布的计算经济网格体系结构 g r a c e ( g r i da 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 ) ，并开发了基于体系结构 n i m r o d g 的网格资源代理，n i m r o d g 是基于市场模型资源调度管理工具的，它强 调资源的交易和资源服务质量的保证。n i m r o d g 支持用户设定资源使用时长，支 持在调度优化时考虑预算约束，使用资源贸易服务来管理网格资源的供需。 2 2 3g c o m m e r c e 计划 g c o m m e r c e 【冽是美国田纳西大学的研究项目，由r i c hw o l s k i 提出的一种网格 资源管理框架。在网格中包含多种资源，每种资源的价格，g c o m m e r c e 利用的是 经济学中的一般均衡理论而没有采用拍卖模型，根据每个用户对不同资源的需求， 以及网格资源提供商对资源的供给，计算网格市场中全部商品的均衡价格。 2 3 资源分配类型 网格环境中，生产者( 资源提供者g s p ) 和消费者( 资源使用者g s c ) 有着不 同的目标、对象、策略以及供需模式，更重要的是他们分布在地球的不同角落。这 给资源管理与调度带来了挑战，也因此成为各研究结构所关注的焦点。下面介绍一 下调度相关的重要概念和模型。 2 3 1 系统导向和用户导向 系统导向和用户导向是资源管理中常用的两种策略。系统导向是资源管理的传 统策略，它以最优化系统性能为目标，适用于单系统管理领域。而用户导向在力图 满足用户q o s 需求的基础上，专注于为用户提供最好的服务，即保证满足用户认为 非常重要的性能需求，譬如任务完成的最后期限等。q o s 的实现需要系统具备奖惩 功能，因此，用户导向的策略通常模仿经济模型来实现。 系统导向的网格资源管理系统比如l e g i o n ，c o n d o r ，a p p l e s p s t ，n e t s o l v e 采 用的是传统策略，它们将调度决策建立在系统参数相关的某一价格函数基础上，旨 在提高系统吞吐量、利用率以及尽可能早地完成作业而不是提高处理应用程序的效 率。另一方面，它们并不考虑资源访问代价，这意味着程序处理的代价在任何时间 都是等同的，而事实并非如此，当一个作业有最后期限需求时，他所支付的价格理 青岛大学硕士学位论文 当更高一些。终端用户并不想盲目地支付高价，而是在综合需求、价值、优先级和 可支配的预算基础上获得协议价。 基于经济模型的方案中，调度策略在运行过程中根据用户需求实时变化。传统 的价格模型通常只考虑应用程序运行所需的软件和硬件资源代价，而经济模型则根 据用户所享受的服务来收费。资源供给和用户需求之间量的变化影响着资源价格， 正如充满竞争的市场经济模型中，每个用户与其他用户竞争资源，资源拥有者则为 了争取客户也存在着竞争。 2 3 2 资源导向和价格导向 网格中用户需求不一致导致微观经济学的方法被运用到资源分配中。为了开发 有效的分散式资源管理方案，使用了以下两种微观经济学方案：资源导向和价格导 向。在资源导向方案中，每个用户为他当前所拥有的资源计算边界值，并共享给其 他用户。这样高于平均边界值的用户即被分配更多的资源，而低于边界值的用户资 源减少。在价格导向方案中，资源初始分配后为它们指定任意的初始价格。然后价 格根据资源的需求量自发地调整，直到达到供需平衡。当前多数已经实现的分散式 资源分配都采用价格导向的方案。价格导向的解决方案相对简单，计算也更有效率， 因此被广泛采用。 2 3 3 基于代理的调度模型 在处理分布式资源分配方面，基于代理的技术正受到越来越多的关注l 捌。在基 于0 0 s 代理的网格市场中，每个用户为每个数据包标价。当数据包传到一个不拥塞 的路由器，它照常传输；但是如果传到一个拥塞的路由器，只有出价最高的数据包 才被继续传输。赢者只需要支付所有获胜者的最低标价。从博弈论角度来看，这个 模型中用户激励相容，可以达到共赢的局面。但是它存在着规模效应问题，数据包 传输过程中路由器必须处理拍卖竞价，大规模运用将严重影响其性能。 2 3 4 效用驱动的调度模型 微观经济学中，任何市场通过买卖双方价位不停地调整，最终都会达到一个供 需平衡的和谐状态。效用函数驱动的市场机制同样也努力建立供需平衡的资源价格 体系，并且为网格用户实现效用参数最优化。它完全模仿现实生活中的交易，即资 源使用者的代理记录以往消费的价格列表，以便在下次申请资源时做出合理的出 价：保证价位最低并且能获得资源。而资源拥有者则根据市场需求量来调整价格， 稀缺的资源定价高，反之定价低，以保证赚取最大利润。 1 2 第二章网格经济概述 该模型将网格资源分配问题抽象为效用函数，这些函数代表着广大用户执行应 用程序的需求。市场中的代理，代表着不同机构提供的各种各样的网格资源，事先 并不考虑合作却能够协调地分配资源。用户代理需要购买资源完成作业，资源代理 为此向用户收费。因此对用户代理来说存在着两个最优化问题：时间和费用。如果 已知资源的定价，用户代理需要在限定时间内尽可能花最少的钱完成任务。为此， 已经有人提出了以价格导向基