（信号与信息处理专业论文）基于拍卖机制的风格资源分配研究.pdf

重庆邮电大学硕士论文 摘要 摘要 网格是构筑在互联网之上，为人们提供各种资源全面共享的基础设施。网格 技术的最终目的是消除资源孤岛，实现网络虚拟环境中协同工作和问题求解，因 而网格资源管理及分配是网格中的关键技术，资源分配的效率将直接影响到应用 执行的成功率，从而影响网格的功能和性能，对网格资源分配技术进行研究具有 重要意义。同时，网格商业化及其全球化对资源分配提出了更高的要求，不仅要 保证资源分配的高效性，而且还需满足网格用户和资源拥有者的各自需求或利益， 以吸引其加入到网格系统中。在这样的环境中，资源分配策略面临着严峻的挑战。 本文采用经济学中的拍卖模型来解决资源分配的相关问题，围绕如何实现高 效合理地分配网格资源，作了如下研究工作： 1 设计了一种改进的双向拍卖系统结构，利用价格存储器存储当前竞标价格 或交易价格，为实现决策竞标和连续竞标提供了基础条件。采用价格确定功能模 块定制交易价格，保证了用户和资源提供者交易的公平性。 2 给出了一种改进的双向拍卖资源分配方法，实现了同种资源的多单元分 配。首先，建立了拍卖的数学优化模型，利用o 1 规划问题求解确定交易者；其次， 设计了相应的定价策略及资源分配算法，该算法能增加用户和资源提供者双方的 效益，具有补偿性质；最后利用网格仿真工具包g - r i d s i mt o o l k i t 对该算法进行了 仿真验证，结果表明了该资源分配方法具有很高的效率，同时能兼顾用户和资源 提供者的共同利益。 3 针对资源协同工作应用场景，给出了基于组合双向拍卖的网格资源分配机 制，建立了拍卖优化模型，制定了相应的价格机制和分配策略，实现了异构资源 的协同分配，并通过仿真验证了该分配机制满足交易者的效用，具有合理性，可 行性。 关键词：网格，双向拍卖，资源分配，资源管理 重庆邮电大学硕士论文摘要 a b s 仃a c t g r i d , b u i l to nt h ei n t e m e t , e m e r g e s 嬲ak i n do fi n f r a s t r u c t u r et op r o v i d es h a r i n ga l l k i n d so fr e s o u r c e sf o rp e o p l e t h eu l t i m a t eg o a lo f 西dt e c h n o l o g yi st oe l i m i n a t et h e r e s o u r c ei s o l a t e di s l a n d , t or e a l i z ec o o r d i n a t i n gw o r ka n dp r o b l e ms o l v i n gi nt h ev i r t u a l n e t w o r ke n v i r o n m e n t s o ，r e s o u r c em a n a g e m e n ta n da l l o c a t i o ni sav i t a lt e c h n i q u ei n g r i d 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 ss t r a i g h tr e l a t e dt ot h es u c c e s sr a t eo f a p p l i c a t i o ne x e c u t i o n , a n dt h e r e b yi t a f f e c t st h ef e a t u r ea n dp e r f o r m a n c eo ft h e 鲥d i n d i r e c t l y t h e r e f o r e ，r e s e a r c ho nt h et e c h n o l o g ya b o u tr e s o u r c ea l l o c a t i o nf o rg r i di s e x t r e m i t yo fi m p o r t a n c e a tt h es a m et i m e ，t h ec o m m e r c i a l i z a t i o na n dg l o b a l i z a t i o no f t h e g r i dm a k e s r e s o u r c ea l l o c a t i o nb e c o m e sm o r ea n dm o r e c o m p l e x i nt h i s e n v i r o n m e 咄i ti sn e c e s s a r yn o to n l yt oe n s u r et 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 n , b u t a l s ot om e e tt h en e e d so rb e n e f i t so fb o t h 班du s e r sa n dr e s o u r c eo w n e r s o n l yt od os o ， u s e r sa n dr e s o u r c eo w n e r sw a n tt oj o i ni nt h eg r i d t h i sc o n d i t i o nt a k e sr e s o u r c e a l l o c a t i o ns t r a t e g ys e v e r ec h a l l e n g e s a u c t i o nm o d e li ne c o n o m i c si su s e di nt h i st h e s i st os o l v et h er e l a t e dp r o b l e m s a b o u tr e s o u r c ea l l o c a t i o n f o c u so nh o wt oa l l o c a t et h er e s o u r c e se f f e c t i v e l ya n d r e a s o n a b l yi n 班de n v i r o n m e n t , t h ea u t h o r sm a i nw o r k i n g sa r eb e l o w ： 1 a n i m p r o v e ds y s t e ms t r u c t u r eo fd o u b l ea u c t i o nw a sp r o p o s e d ，i nw h i c hp r i c e s t o r a g er e s p o n s i b l ef o rr e c o r d i n gt h ec u r r e n tb i n d i n gp r i c eo rt r a d i n gp r i c et op r o v i d e b a s i ci n f o r m a t i o nf o rt h en e x tb i d d i n ga n dd e c i d i n gb i d d i n g i ta d o p t sp r i c ed e c i d i n g f u n c t i o nt oe n s u r ef a i r n e s so ft r a d i n gp r i c eb e t w e e ng d du s e r sa n dr e s o u r c e p r o v i d e r s 2 a ni m p r o v e dr e s o u r c ea l l o c a t i o nm e t h o db a s e do nd o u b l ea u c t i o nw a s p r o p o s e d , b yw h i c hi tr e a l i z e dm u l t i - u n i t sr e s o u r c ea l l o c a t i o no ft h es a m ek i n dr e s o u r c e f i r s t l y , i te s t a b l i s h e sam a t h e m a t i c a lo p t i m i z e dm o d e l ，u s e s0 1p r o g r a m m i n gp r o b l e m s o l v i n gm e t h o dd e c i d et h et r a d e r s s e c o n d l y , i td e s i g n sa na p p r o p r i a t ep r i c ed e c i d i n g s t r a t e g i e sa n dr e s o u r c ea l l o c a t i o na l g o r i t h m f i n a l l y , 晰m 鲥ds i m u l a t i o nt o o lp a c k a g e w h i c hn a m e dg r i d s i mt o o l k i t , i ts i m u l a t et h eg i v i n gm e t h o da n dt h er e s u l t ss h o wt h a t t h i sa l g o r i t h mh a sh i g he f f i c i e n c ya n dc a np r o v i d et h ec o m m o nb e n e f i t so fb o mu s e r s a n dr e s o u r c e sp r o v i d e r s 3 c o m b i n i n gc o m b i n a t o r i a la u c t i o nm e c h a n i s ma n dd o u b l ea u c t i o nm e c h a n i s m ，a 墅邮电大学硕士论文 a b s t r a c t m e c h a n i s mo fr e s o u r c ec o - a l l o c a t i o nf o r 酣dw a sp r o p o s e d ，b yw h i c hi t r e a l i z e d c o a l l o c a t i o nb e t w e e ns e v e r a lh e t e r o g e n e o u sr e s o u r c e s b ys i m u l a t i o n , t h e r a t i o n a l i t y a n dv a l i d i t yo ft h i sm e t h o dw a st e s t i f i e d k e y w o r d s ：g r i d ，d o u b l ea u c t i o n , r e s o u r c ea l l o c a t i o n ，r e s o u r c em a n a g e m e n t i i i 重庆邮电大学硕士论文第一章绪论 1 1 网格计算研究背景 第一章绪论 随着信息量的急剧增长，应用需求正朝着大规模和高性能等方向发展，这就 要求将分布在不同地理位置上的各种异构资源通过高速互联网连接起来，实现高 性能联合计算和问题协同求解。计算机性能的不断提高以及网络通信技术的革新 为解决大规模应用问题提供了基础条件，网格技术正是在此背景下应运而生的。 简单地讲，网格把整个英特网整合成一台巨大的超级计算机，实现计算资源、存 储资源、数据资源、信息资源、知识资源、专家资源的全面共享。 最初的网格研究来源于美国联邦政府资助的高性能计算项目，其目标是将跨 越地域的多台高性能计算机、大型数据库、贵重科研设备、通信设备、可视化设 备和各种传感器整合成一台巨大的超级计算机系统，以支持科学计算和科学研究， 当时这种技术被称为元计算( m e t a c o m p u t i n g ) 【1 1 。随着网格技术的发展，网格应 用的范围已经从传统的高性能计算和数据密集型应用拓展到更广泛的应用领域， 为全球范围内分布式的、异构的、多样的资源共享提供了重要的基础设施。开放 网格服务体系结构o p e ng 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 ) 的提出，标志着网格 计算与w e b 服务技术的融合，将资源共享的概念扩展为更具普遍意义的服务的共 享和协作。自此以后，网格不再局限于科学研究，它引起了社会各界的广泛关注 和研究，被称为是下一代i n t e m e t l 2 , 3 。 近年来的相关研究使得网格已经具有一定的服务功能，主要包括分布式超级 计算、分布式仪器系统、数据密集型计算、信息集成和远程沉浸等。目前看来， 这些不同的功能逐渐被使用在电子政务、科学研究、信息处理及娱乐等方面。随 着技术的进一步发展以及各种应用需求的增加，网格的功能将会继续增强从而应 用到各行各业中。 资源管理及分配是网格研究中的核心问题。随着未来网格规模的不断扩大以 及各个领域内网格技术的相互融合，全球性统一的网格将会诞生。在这样一个错 综复杂的网格环境中，资源的种类和数量超乎想象，如何有效聚合各种资源实施 统一管理，为用户提供简单透明的访问接口，以及最终实现资源分配将是一个极 具挑战性的问题。计算经济网格体系结构【4 - 7 1 ( 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 l e c o n o m y - g r a c e ) 的提出为网格资源分配的相关问题提供了一个有效解决方案， 采用经济机制能激励资源拥有者贡献资源，吸引网格用户使用网格资源，为建立 统一的、全球化的大规模网格打下了坚实的基础。 重庆邮电大学硕士论文第一章绪论 1 2 课题研究现状 1 2 1 网格技术研究现状 网格中有效利用现有资源的思想引起了社会各界的密切关注，因而，近年来 网格技术一直成为研究焦点。目前，对网格的研究已经从美国和欧洲推广到了世 界各大洲，各个国家和地区都投入了大量的资金进行网格技术研究和网格基础设 施建设，在此期间，出现了许多有影响力的网格项目。 在美国，主要有c o n d o r 、l e g i o n 、g l o b u s 等项目。c o n d o r 项副8 】对高吞吐率 调用问题进行研究，提供队列机制、调度策略、优先级方案、资源监控和资源管 理功能，解决了计算密集型负载管理问题。g l o b u s 项目【9 】对全球的网格研究开发工 作起到了巨大的推动作用，是网格领域内受世人关注的焦点。该项目主要开发一 个面向科学计算的基本软件基础设施，其开发的软件工具包( g l o b u st o o l k i t ) 已 经在世界范围内得到一定程度的使用，用于定义开放网格服务架构( o g s a ) ，同 时提供了安全、可靠的服务创建与管理功能。l e g i o n 1 0 】项目为用户提供单一的、 一致的虚拟机模型，支持透明调度、数据管理、容错、站点自治和多种安全机制， 对基本系统级网格基础设施的开发进行了探索，建立了l e g i o n 网格体系结构。 欧洲联盟支持的欧洲数据网格( e u r o p e a nd a t ag r i d ) 建设了下一代计算基础 设施，提供计算强度大、共享超过1 0 1 4 b 数据的大规模分布式数据库，并对中间 件、基础设施、应用和管理等多个方面的相关问题进行了研究。德国的u n i c o r 项目提供了一套软件，使用已有的万维网技术，通过该软件允许用户在不考虑远 程机的操作系统、数据存储格式、管理过程和策略的情况下向远程高性能计算机 提交作业。 在亚洲，日本的n i n f 是一个全球计算基础设施项目，允许用户访问包括硬件、 软件和数据在内的、分布在广域网上的资源。b r i c k s 项目研究一个评价系统，能够 模拟全球计算系统的不同行为，在典型的高性能全球计算环境上对不同的调度策 略进行分析和评价。在我国，网格研究已列入“8 6 3 计划 ，中国科学院计算技术 研究所开发了连接国内8 个曙光计算中心的网格，提出了“织女星网格计划， 主要对网格操作系统、信息网格和知识网格三个层次进行研究。 不仅如此，为实现全球网格化目标，国际与地区间的研究机构和商业机构展 开紧密合作，致力于网格技术的标准化和商业化。地区网格论坛、国家网格论坛、 网格协作组织等纷纷出现，用以协调成员之间的合作关系、开发标准和协议。其 中，比较有名的有全球网格论坛( g l o b a lg r i df o r u m ：g g f ) 、万维网联盟( w 3 c ) 、 2 重庆邮电大学硕士论文第一章绪论 国家互联网工程任务组( t h ei n t e m e te n g i n e e r i n gt a s k f o r c c ：i e t f ) 、结构化信息 标准促进组织( o r g a n i z a t i o nf o rt h ea d v a n c e m e n to fs 饥c t u r e d i n f o n u a t i o n s t a n d a r d s ：o a s i s ) 。g g f 是一个网格技术论坛的国际组织，是由网格论坛和欧洲 网格论坛以及亚太网格论坛社区合并而成的，它的使命是通过发布指南、标准、 代码等推动和发展网格技术和应用。通过g g f ，大量的早期研究成果，现在正逐 步演化为未来网格标准的基础。 1 2 2 网格资源分配研究现状 在网格技术发展初期，网格的概念仅仅局限于计算网格，主要用于解决大规 模计算密集型数据计算问题，网格的使用范围也非常狭小，主要用于科学研究领 域。在这种情况下，资源分配的目的是提高资源利用率，采用的策略主要为集中 式资源分配。网格之父i a nf o s t e r 提出了基于策略的c p u 资源分配方法【l 卜1 3 】，通 过预先设定好的各种策略集中调度网格资源。g l o b u s 的资源管理分配模型通常采 用这种方法，能有效地提高整个系统的性能和资源利用率。目前，在建立专用网 格或者小型网格系统时，大都采用基于策略的资源分配方法。 随着网格技术的深入发展，网格商业化需求日益明显。传统组织内部的集中 式分配往往不考虑资源使用收费的问题，随着越来越多的资源提供者加入到网格 环境中，同时也出现了专门提供资源给网格用户使用的组织机构。在这样的环境 中，付费机制是不容忽视的问题，因此，学者们将经济学引入到网格中，并提出 了网格经济【1 4 j 的概念。采用经济学模型来实现网格中的资源分配。为加快网格商 业化进程，网格经济近年来得到了广泛关注和深入研究。 目前网格中资源管理体系结构模型可分为三类，包括分层模型、抽象所有者 模型和市场经济模型1 5 , 1 6 。g l o b u s 和l e g i o n 等网格系统采用分层模型进行资源管 理，很好地解决了站点自治性、异构性和联合分配等问题。抽象所有者模型在实 际网格系统中未有实现。n i m r o d g 和j a w s 系统采用计算经济模型，利用市场经 济中的供求原则对资源实施分配。b u y y a 等人在文献【l5 】中对三种模型进行了分析 对比，指出了市场经济模型综合了分层模型和抽象所有者模型的优点，并详细论 述了市场经济模型用于网格环境中实现资源分配的有效性和可行性。随后，文献【4 】 给出了七种用于网格经济的资源分配模型，在网格经济项目( t h eg r i de c o n o m y p r o j e c t ) 中，实现了基于计算经济的网格资源管理体系结构g r a c e ( g r i d a 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 ) 1 7 l7 ，在该模型中，采用网格资源代理 n i m r o d g 来实现资源发现、资源选择和资源调度，并将该调度策略成功应用于参 数扫描型应用。鉴于g r a c e 的研究成果，研究者们加强了对经济模型的分析，通 重庆邮电大学硕士论文 第一章绪论 过理论研究分析和相应的仿真验证了商品市场模型和拍卖模型非常适合动态异构 的网格环境中的资源分配。 在基于拍卖模型的网格资源分配研究中，学者们主要对各种拍卖模型进行研 究，先后提出了单向拍卖、双向拍卖、反向拍卖以及组合拍卖等多种模型以解决 不同应用场合的相关问题，而采用的拍卖协议均为传统协议，很少注重拍卖协议 本身的研究。文献1 18 】从资源拥有者角度出发，研究能增大资源提供者经济利益的 协议，文献r i g 站在资源消费者角度考虑，提出了能减少用户费用的拍卖协议，文 献1 2 u j 分析了现有拍卖协议的不足，并提出了一种改进的双向拍卖协议，实现了多 单元资源的双向拍卖，通过理论验证了该协议满足优势策略激励相容、预算平衡 以及个人理性等特点。 1 3 课题研究的目的和意义 网格未来发展的趋势是大规模化乃至全球化，网格系统研究的目的就是要突 破地域和管理策略等种种限制，使人们能够以一种全新的更自由、更方便的方式 使用资源以解决各种复杂问题。在网格计算环境中，经常需要为用户协同分配多 种不同的资源才能满足其任务执行要求，而网格中的资源遍布全球、种类繁多且 处在不同的管理组织或机构管辖之内，网格资源的这种分布性、多样性以及异构 性给网格最终目标的实现和用户任务的顺利执行带来了严峻的挑战网格资源分 配是整个网格系统中的核心问题和关键技术，必须提供一种行之有效的分配策略 才能促进网格技术的进一步发展。因此，对网格资源分配的研究，在理论方面尤 其是在加快网格经济化进程步伐方面有着不同寻常的意义。现有的拍卖机制和协 议在解决网格中资源分配的问题上有着非常高的效率，但仍然存在着一些不足， 有待进一步研究改进。在网格系统中，一种高效的拍卖机制理当满足如下条件： 有着高效的资源分配成功率； 能增加资源提供者的经济效益，吸引其贡献资源，促进网格的大规模发展； 能减少用户的费用，让其享受到网格带来的实实在在的好处； 考虑异种资源的协同分配； 论文正是从上述因素考虑，研究基于拍卖的网格资源分配机制，针对目前存 在的拍卖协议的不足，提出相应的改进算法，实现网格中资源高效合理地分配。 4 重庆邮电大学硕士论文 第一章绪论 1 4 主要内容及论文组织结构 本文在广泛阅读国内外关于网格资源分配的文献后，在对现有资源分配算法 仔细分析以及吸取前辈的优秀成果的基础上，对基于拍卖机制的资源分配协议进 行了改进，进一步提高了网格资源分配的效率。论文主要内容包括以下几个方面： 第一章，简要介绍了网格技术的相关背景及一些研究组织或项目，总结了网 格中资源分配的研究现状并分析了资源分配需要考虑的几个问题，阐述了本课题 的目的及意义。 第二章，简要介绍了网格的概念及特点；对比分析了几种网格资源管理结构 模型，在此基础上，分析了用于计算经济的各种网格资源分配模型；最后，针对 网格资源的特点，讨论了与课题相关的各种拍卖机制。 第三章，分析了传统双向拍卖模型及资源分配算法的不足，扩展了基于双向 拍卖的资源分配结构模型，并详细介绍了各组成模块的功能；引入优化模型，提 出了一种改进的资源分配策略，并对资源定价及分配算法做了详细介绍；通过仿 真分析验证了改进的资源分配策略的相关性能。 第四章，介绍了组合拍卖的概念，并将其思想与双向拍卖机制相结合，提出 了基于组合双向拍卖的资源协同分配策略：给出了相应的定价和资源分配算法， 并通过仿真验证了该策略的性能。 第五章，对全文进行了总结，给出了未来工作的研究方向。 重庆邮电大学硕士论文第二章网格环境下的资源分配概述 2 1 网格概述 第二章网格环境下的资源分配概述 网格是继万维网之后出现的一种新型网络计算平台，其目的是为用户提供一 种全面共享各种资源的基础设施。网格的概念来自于电力网格，人们希望成熟的 网格如同电网一样，用户只需把设备的插头插入网格的“插座 ，就可以使用网格 中的各种资源，实现资源共享。起初，网格是用来进行科学计算的，也称为计算 网格或元计算机【l 。3 1 ，它是一个分布资源的集合，随着技术的发展和人们需求的提 高，计算网格的功能逐渐增强，它的名字也逐渐被网格所取代。 2 1 1 网格定义 什么是网格? 有人认为网格是通过通信手段将地理上分散的资源无缝集成起 来的一种基础设施，它能够充分吸收各种有用资源，并将它们转化为一种随处可 见的、可靠的、标准且经济的能力。根据用户需求随时为用户提供既经济又方便 快捷的服务。 全球网格研究的领军人物i a nf o s t e r 对网格的概念进行了探讨，并在网格： 一种未来计算基础设施蓝图 2 1 】一书中把网格描述为：“网格是构筑在互联网上的 一组新兴技术，它将高速互联网、计算机、大型数据库、传感器、远程设备等融 为一体，为科学技术人员和普通老百姓提供更多的功能和服务。互联网主要是为 人们提供电子邮件、网页浏览等通信功能，而网格则能提供更多更强的功能，它 能让人们共享计算资源、存储资源和其他资源。”有人把网格看成是未来的互联网， 也常称“下一代因特网【2 2 】一、“国际互联网2 、“下一代万维网等。 资源共享是网格的根本特征，消除资源孤岛是网格的奋斗目标。i a nf o s t e r 认 为，要实现这种共享，必须让供求双方都明确的知道哪些用户有权共享、哪些资 源可以用来共享以及实现共享的各种条件等。他提出了鉴别一个系统是否属于网 格系统的三个条件【3 】： ( 1 ) 在非集中控制的环境中协同使用资源资源共享必须依靠参与者间的 协调才能完成。 ( 2 ) 必须使用标准、开放、通用的接口和协议，否则它只是针对具体应用 的专用系统。 ( 3 ) 面向复杂任务能够提供高质量服务，工作的总效用要大于各部分单独 6 重庆邮电大学硕士论文 第二章网格环境下的资源分配概述 工作效用的总和。 2 2 2 网格的特征 网格是基于分布式技术发展而来的，然而，网格更强调资源共享和互操作性， 能解决动态、异构、多管理策略下协同资源共享问题。因而，与分布式系统相比， 网格有其独特的特征 2 3 】，主要包括： 1 ) 分布与共享 分布性是网格的一个最主要的特点。网格的资源是分布的，组成网格的计算 资源、各种类型的数据库、以及其他的各种设备都是分布在不同地理位置的多个 地方。资源种类多样，规模巨大，跨越的地理范围较广。然而，网格资源却是可 以被充分共享的。即具有访问权限的任何网格用户都可以使用网格上的任何可用 资源。 2 ) 自相似性与适应性 网格的局部和整体之间在组织结构上存在着一定的相似性，由小规模的网格 系统构建成规模较大的网格系统。适应性的另一体现是其具有可演化性，整个环 境可随着网格技术的发展而更新。 3 ) 动态性与多样性 资源的自治性导致了其具有动态性，资源提供者可随时加入或退出格环境、 替换或更新资源，、因而资源状态是动态变化的。同时，网格资源又是异构和多样 的，不同的资源处在不同的管理机构之下，具有不同的访问策略，即使是相同的 类型的资源也通常具有许多不一样的属性。 4 ) 自治性与管理的多重性 一方面，每个资源都有其拥有者，网格资源的拥有者对该资源具有本地管理 权限，拥有对其资源自主管理的能力，这就是网格的自治性。另一方面，网格资 源也必须接受网格系统的统一管理，实现共享和互操作，为更多用户提供方便快 捷的服务。 2 2 网格资源管理 由于网格资源存在异构性、动态性等特征，这使得通过资源管理系统来统一 管理资源为用户提供简单透明的服务成为必然。网格资源管理模块把网格中分散 的各种资源聚集起来，对资源进行抽象，建立物理资源和逻辑资源间的联系，隐 7 重庆邮电大学硕士论文 第二章网格环境下的资源分配概述 藏实际资源使用的具体细节，仅仅为用户提供访问资源的简单接口。资源管理系 统需建立资源共享的策略，协调资源的共享使用，使多个资源请求者可以共享使 用网格中的同一个资源，一个资源请求者可以根据业务需要同时或先后使用网格 中的多个资源。 2 2 j l 网格资源管理系统的基本类型 在资源管理过程中，最重要的是对资源的整个生命周期进行管理，包括从资 源注册、资源共享到资源注销的整个过程，如图2 1 所示。 图2 1 网格资源生命周期管理 首先资源需向资源管理器注册，资源管理器把注册信息写到资源信息库中， 用户需要资源时，向管理器提出请求，资源管理器把与用户请求相匹配的资源信 息返回给用户，用户根据资源的信息与资源建立连接，使用资源。 在资源管理系统中，有资源请求者、资源中介者和资源提供者三类实体，分 别扮演三种角色。根据资源管理过程中信息流动路径不同，资源管理系统存在三 种不同的形式1 2 j 。 直线形：资源请求者向资源中介者提出资源请求，资源中介者为用户寻找 合适的资源并驱动资源工作，为用户提供服务。资源为用户服务的结果仍 然是通过资源中介者返回给资源请求者。 折线形：用户向资源中介者提出请求，资源中介者为用户找到合适的资源 并把资源标识和使用接口等信息返回给用户。用户根据返回信息，组织消 息和数据，驱动资源工作，享用资源提供的服务。 三角形：用户向资源中介者提出请求，资源中介者为用户找到合适的资源 并驱动资源工作，通知资源把服务结果用什么形式、通过哪个地址返回给 请求者。资源开始工作，服务结束后按照中介者提供的消息把服务结果告 诉资源请求者。 8 重庆邮电大学硕士论文第二章网格环境下的资源分配概述 三种基本结构各自适用不同要求的场合下使用。直线形结构用于追求简单用 户接口的场合，折线形适合用户和资源双方需要协商的情况下，而三角形则适合 接口简单又注重输出效果的情况。三者之间的比较如表2 1 所示。 表2 1 资源管理系统结构对比 结构直线形 折线形 三角形 用户接口 简单 复杂简单 请求次数 121 协议通用通用、专用通用、专用 资源中介者功能复杂简单较复杂 2 2 2 网格资源管理系统模型 网格计算环境中的资源在地理上是广泛分布的，而且每个资源都属于不同的 组织机构，有着各自的资源管理机制和策略。因此，对资源的有效管理是实现资 源共享、高性能联合计算和协同问题求解的关键。在网格环境中，主要通过网格 资源管理系统( g r i dr m s ) 来实现对资源的管理。目前，用于构建网格资源管理 系统的基本模型主要有三类： 分层模型( h i e r a r c h i c a lm o d e l ) t l s j 6 2 3 抽象所有者模型( a b s t r a c to w n e rm o d e l ) 【1 5 ，1 6 j 计算市场经济模型( c o m p u t a t i o n a lm a r k e t e c o n o m ym o d e l ) 【5 ，6 刀】 分层模型是g r i df o r u m 在第二次会议上提出来的，g l o b u s 、l e g i o n 、c c s 、 a p p l e s 等网格系统使用该种资源管理模型。其基本思想是将整个资源管理系统分 为若干个功能层，每一层都有自己的独立功能，较高层次的组件可以利用较低层 次组件提供的服务。这种模型中包括调度器、信息服务器、域控制器、监控器、 作业控制器等网格服务部件。这些部件在资源分配、发现、和调度过程中相互协 调来完成用户提交的作业。各部件之间的交互如图2 2 所示1 1 6 】。 网 格 用 户 应 用 程 序 作业 作 业 控 制 代 理 一访问控制代理l 堡些 蓊函陌赢 监控器 图2 2 网格资源管理分层模型【1 6 1 用户提交作业给作业控制器，由其负责作业在系统中的分配和预留，协调与 9 重庆邮电大学硕士论文第二章网格环境下的资源分配概述 系统内部不同组件的交互。作业控制代理调用访问控制代理查询系统作业饱和情 况从而判断是否能够将作业传递给全局调度器。全局调度器利用网格信息系统进 行资源发现并咨询领域代理来决定当前的资源状态和可用的资源。领域控制代理 接受委托负责管理待使用的资源。根据领域代理提供的信息，全局调度器将计算 映射集合并将其传递给分配代理。分配代理负责与领域控制器进行协商对资源进 行预约，然后将这些已预约好的资源传递给作业控制代理用以处理用户的应用。 抽象所有者模型模拟现实生活中的生产消费模式，资源拥有者对应于产品制 造商，资源代理对应于商品供货商，用户可将资源代理视为“抽象所有者 。通常 情况下资源消费者不直接与资源拥有者进行协商，而是与资源代理进行交互，采 用定购和提货的方式进行交易，就如同现实中的商店售货台一样。该模型简洁明 了，但在实际应用中存在许多尚未解决的问题，比如用户如何发现拥有所需资源 的抽象所有者。因此，在网格环境中目前未出现采用抽象所有者模型的资源管理 系统。 计算经济模型综合了抽象所有者模型以及分层模型的特征，既利用了分层模 型中相对成熟的技术又强调了抽象所有者模型中的经济观点，利用经济学的思想 来进行资源管理和调度。其模型结构如图2 3 所耐1 6 1 。 隆源监控i 用 户 应 用 程 序 一一 作 业 控 制 管 理 资源预约i 斗记账 网格用户网格资源代理网格中间件 网格资源控制域 图2 3 网格资源管理计算经济模型1 6 】 计算经济模型主要由网格用户应用程序、网格资源代理、网格中间件以及网 格资源控制域四个部分组成。其主要思想是：网格资源代理利用现有的中间件服 务技术连接用户和网格资源，负责资源发现、资源选择、资源分配等功能。资源 代理主要由五部分构成，它们是作业控制代理、网格探测器、调度顾问、交易管 理者和分配代理。作业控制代理是作业看管的中心组件，负责调度的产生、作业 的创建和状态的保持，并与其他组件进行交互。调度顾问利用网格探测器发现资 1 0 蠢 重庆邮电大学硕士论文第二章网格环境下的资源分配概述 源、选择资源并实施作业分配。 计算经济模型集分层模型和抽象所有者模型两者的优点子一体，利用经济学 观点来管理资源。该模型具有如下特点： ( 1 ) 基于供求原则投资回报机制促进了服务质量的提高和资源的升级，经济 是调节供求关系的最重要的机制。 ( 2 ) 为访问网格资源的用户提供公平的价格机制，并允许对一切资源进行交 易。建立以用户为中心，而不是以系统为中心的调度政策，提供了资源分配和管 理的有效机制。 ( 3 ) 综合了分层模型和合抽象所有者模型的实质。 与分层模型和抽象所有者模型相比较，计算经济模型更适合于网格这样的动 态异构环境，因而受到学术界和网格组织的广泛研究。 2 3 网格中基于经济机制的资源分配 网格资源管理将分布的资源聚集起来，构成异构抽象虚拟的资源池。网格资 源管理的最主要的目的是最终实现资源分配和用户任务全局调度。网格资源分配 过程就是将大量的可用的资源分配给不同的资源请求者使用以解决不同的具体应 用。网格环境是一个多用户多资源提供者的动态环境，为有效管理这些资源，计 算经济资源管理模型是最佳的选择。然而，在这种资源管理模型中，传统的资源 分配方法无法与之相适应，为解决这一问题，网格经济项目研究利用经济学的观 点来实现资源分配的相关问题，并取得了一定的成果。 2 3 1 网格资源及其特点 网格资源1 2 圳是网格中所有可以被用户请求使用的实体的总称，它们具有不同 的形式，功能各异，主要包括计算机软件、计算机硬件、设备和仪器等。除了这 些物理资源外，在网格设备旁工作的人员也是一种重要的资源，称为人类资源， 包括人的知识、能力等多种因素，是网格上最具有伸缩性的资源。根据资源能否 移动的特性可将资源分为可移动资源和不可移动资源，合理移动可移动资源是提 高网格性能的有效途径。网格资源还有可重复使用和不可重复使用之分，不可重 复使用的资源是网格中最宝贵的资源，必须合理、有效地利用这种资源，才能发 挥网格的能力。 与以往的集群系统、并行系统、分布式系统相比，网格中的资源具有其独特 重庆邮电大学硕士论文第二章网格环境下的资源分配概述 的性质1 2 1 ： 1 ) 异构性。网格中的资源种类繁多，功能各异，访问接1 2 1 也不尽相同，本地 管理系统不同，共享规则不同。 2 ) 动态性。网格中的资源可以自由地随时加入和离开网格系统，其在网格环 境中的可获得性是动态变化的。 3 ) 自治性。网格资源的拥有者有着一定的本地管理策略，使得网格资源或强 或弱地有着本地自治能力。 4 ) 二分特性。除了一部分专用的网格资源外，大部分资源都同时作为网格用 户和网格资源所有者共同使用，处在网格管理系统和本地管理系统共同管 理之下。 2 3 2 基于经济学的网格资源分配的优点 网格资源的自治性、动态性及异构性决定了资源管理的复杂性。对于这样一 个大规模、开放式的网络环境，系统未来的负载情况、计算进程和通信所需时间 等都是不确定的，因此，必须采用动态而非静态的资源分配策略。g g f 认为采用 经济学原理实现网格资源分配有助于鼓励资源共享，利于全局资源的合理配置， 并成立了专门的工作组来研究该方案。在网格环境中采用经济模型来管理资源实 现分配主要有以下优点1 2 5 - 2 s 1 ： ( 1 ) 采用付费机制鼓励资源拥有者贡献他们的空闲资源，有助于建立大规模的 网格资源环境。 ( 2 ) 任何用户都可以公平地存取网格资源。只要资源请求者通过一定规则加入 到网格环境中成为网格用户，就可以与其他用户公平竞争资源。 ( 3 ) 有利于调节网格资源的供需平衡。当供不应求时，通过提高资源价格减少 资源使用者，增加资源供给；相反，当供过于求时，降低资源价格，可以 增加资源使用者减少资源供给，使资源供求在平衡点波动，实现全局环境 的负载均衡。 ( 4 ) 提供经济激励制度，促使用户解决低优先级的问题时后退，在资源数量少 的情况下有利于实现阻塞控制。 ( 5 ) 资源使用者可以表达他们的目标和需求，能提供高质量的服务。 ( 6 ) 资源请求者和资源提供者能根据实际情况做出自己的决策，最大化各自的 效用和利益。 1 2 重庆邮电大学硕士论文第二章网格环境下的资源分配概述 2 3 3 基于经济的网格资源分配模型概述 澳大利亚m o n t h 大学的r a j k u m a rb u y y a 等人将市场经济引入网格环境中， 提出了网格经济学，利用经济学模型来管理网格资源，实现资源分配。在该方案中， 资源请求者作为买方，资源拥有者作为卖方，资源分配过程实际上就是买卖双方 的交易过程。b u y y a 等研究人员还提出了计算经济学的网格框架g r a c e ( g r i d a r c h i t e c t u r ef o rc o m p u t i o n a le c o n o m y ) 6 , 7 j7 】，将经济学中的各种经济模型应用到 网格资源分配中，有效地调节了网格环境中计算资源的供需平衡，实现全局资源 的合理分配。 经济学中的许多理论模型都可以应用到网格环境中进行服务价格协商和交 易，实现资源分配，网格中常用的基于经济的资源分配模型主要包括以下几种【5 2 8 】： ( 一) 商品市场模型( c o m m o d i t ym a r k e tm o d e l ) 【5 】 在商品市场模型中，由资源拥有者指定资源或服务的价格，并根据用户消费 的资源数量进行计价收费。定价策略可以根据各种参数，可以是恒定不变的，也 可以是取决于资源的供求关系。通常情况下，服务的价格制定应该能够使资源的 供求关系达到均衡。若采用恒定价格，则一旦价格确定下来，无论服务质量如何 变化它都保持不变，不受供求关系影响；如果采用供求模型，价格变化一般取决 于供求关系的变化，在这种情况下，原则上可以调节供求比例使价格达到新的均 衡点。 ( - - ) 牌价模型( p o s t e dp r i c em o d e l ) 【5 】 牌价模型与商品市场模型比较类似，但也存在不同之处。在牌价模型中，资 源拥有者可以在定的优惠期间发布资源降价公告，广播特定的报价以吸引消费 者建立市场共享或激发用户使用便宜的资源，在这种情况下，牌价一般比通常价 格便宜，因此不需要协商价格。牌价对某些用户可能具有吸引力，例如，在节假 日期间，资源需求可能减少，资源拥有者可以通过发布牌价吸引用户以增加资源 利用率。 ( 三) 议价模型( b a r g a i n i n gm o d e l ) 5 2 8 】 在议价模型中，资源代理代表用户可以与资源提供者讨价还价，获得更低的 价格或更长的使用时间，以满足用户的任务调度需要。资源代理和资源提供者都 有自己的目标函数，只要双方的目标都己达成，那么协商也就完成了。当双方的 初始目标没有达到时，必须至少有一方愿意让步进行再次协商最终才能完成交易， 实现资源分配，否则协商失败。议价过程会造成资源和时间的消耗，在协商次数 过多的情况下，资源分配效率非常地。 ( 四) 招标合同网模型( t e n d e r c o n t r a c t - n e tm o d e l ) 【5 ，2 8 】 重庆邮电大学硕士论文 第二章网格环境下的资源分配概述 该模型在分布式环境中应用最为广泛的服务协商模型之一。它模拟商业中常 用的制定合同的机制来控制货物和服务的交换，为给定的应用寻找一个合适的资 源提供者。在该模型中，将要执行应用的用户或r r 称为经理人，资源拥有者或 r s p 称为潜在的承包人。 从一个经理人的观点来看，制定合同的过程可描述如下： ( 1 ) r r 宣布其需求( 可以使用交易样板) ，并且向r s p 邀请投标； ( 2 ) 有兴趣的r s p 评估该需求，并且通过提交他们的投标以回应； ( 3 ) r r 评估合同并将合同授予最适当的r s p ； ( 4 ) r r 和r s p 单独通信，并使用资源。 从承包人或r s p 的观点来看，制定合同的过程为： 一 ( 1 )