（计算机应用技术专业论文）经济模型下的网格资源调度算法的研究.pdf

摘要 网格技术是以资源共享为主要特征的下一代互联网技术。由于网格中的资源 具有动态性、多样性、自治性等特点，网格资源调度问题已经成为网格研究的一 个热点和难点问题。网格资源调度的研究主要是针对调度算法的研究。 本文主要对计算经济模型的资源调度算法进行了较为深入的研究。计算经济 模型使资源所有者更积极地提供资源的共享与更新，也使用户使用资源更加方 便。在基于计算经济模型的作业截止期限和预算约束d b c ( d e a d l i n eb u d g e t c o n s t r a i n ) 算法的基础上，本文针对网格中资源的特点和用户的实际需求，改进 了原有算法。改进后的算法迸一步提高了作业完成数量主要工作如下： 1 对当前网格资源调度系统的研究现状、特点傲了相关总结。 2 讨论了网格研究中的计算经济调度模型和调度算法，着重阐述了基于计 算经济模型的作业截止期限和预算约束的几种调度算法。 3 针对用户对计算完成量的需求，对原有的d b c 算法做了一定改进并给出 了代价时间比算法。 4 通过网格模拟器对算法进行了仿真实验，实验表明改进后的算法更好的 满足了用户的计算需求。 关键词：网格资源调度，计算经济模型，d b c 算法，g f i d s i m a b s t r a c t g r i dc o m p u t i n g ，e m e r g i n ga san e wp a r a d i g mf o rn e x t - g e n e r a t i o nc o m p u t i n g , e n a b l e st h er e s o u r c 圮s h a r i n gf o rs o l v i n gl a r g e s c a l ep r o b l e m si nm a n yf i e l d s r e c e n t l y y e a r s ，t h er e s e a r c ho n 函df o c u s e so ng r i dr e s o u r c es c h e d u l i n g b e c a u s et h er e s o u r c e s i n 鲥dh a v et h e s ec h a r a c t e r s ：d y n a m i c s ，d i v e r s i t y , a u t o n o m y , t h er e s o u r c es c h e d u l i n g i ng r i de n v i r o n m e n th a sb e c o m eap r o s p e c t i n gs u b j e c t t h er e s e a r c h e si n c l u d et h e r e s o m c es c h e d u l i n ga l g o r i t h m s i nt h i st h e s i s , t h er g $ o u l c es c h e d u l i n ga l g o r i t h mw h i c hb a s e do i lt h e e c o n o m e t r i c sm o d e lw a sa n a l y z c de x t e n s i v e l y b yt h i sm o d e l t h er e s o u r c ed w n 盯c a l l o f f e ra n du p g r a d es h a r i n g s o i i r sm o l - ea c t i v e l y i na d d i t i o n , t h i sm o d e li sm o r e c o n v e n i e n tt ou s er e s o u r c e s a tt h ef a i l l et i m e , b a s e do nt h ec h a r a c t e r so fg a d l _ e $ o u r c e st h et h e s i sm a d es o m ei m p r o v e m e n to i lt h ep r i m a r ya l g o d t h m s ，w h i c ha r e t h er e s o u r c es c h e d u l i n ga l g o r i t h m sb a s e do nd e a d l i n eb u d g e tc o n s t r a i n a n dt h en e w o n ec a l ls a t i s f yt h eu s e r s n e e do nc o m p l e t e dj o b sm o t h ek e yw o r k so ft h i sp a p e r a r e 晒f o l l o w ： 1 s u m m a r i z eo ft h eg a dr e s o u r c es c h e d u l i n gs y s t e m so np r e s e n ts i t u a t i o na n d c h a r a c t e r s 2 a n a l y s i ss o m ei m p o r t a n tm o d e l sa n da l g o r i t h m si ng a dr e s o u l _ c e ss c h e d u l i n g ， a n df o c u so nt h ea l g o r i t h m sb a s e do nd e a d l i n eb u d g e tc o n s t r a i ni nt h ee e o n o m e t 6 c s m o d e l 3 i m p r o v et h ep m a r ya l g o r i t h m sa n dp r o p o s eai l e wa l g o r i t h mc a l l e d b u d g e t d e a d l i n ea l g o r i t h mt om e e tt h er e q u i r e m e n t so f t a s k sm o r ec o m p l e t e d 4 c o n d u c te x p e r i m e n t so np r o p o s e da l g o r i t h m sb ys i m u l a t o ra n dp r o v et h a tt h e a l g o r i t h mi sr e a s o n a b l e ，a d a p t i v ea n dm o r ef l e x i b l et h a na n yo t h e ra l g o r i t h m s i na w o r d , t h ep r o p o s e da l g o r i t h mc a l li m p r o v et h en u m b e ro f t a s k sc o m p l e t e db e t t e rt h a n t h ep r i m a r ya l g o r i t h m s k e y - w o r d s ：g r i dr e s o u r c es c h e d u l i n g ；e c o n o m e t r i c sm o d e l ；d b ca l g o r i t h m ；g r i d s i m 图表目录 图表目录 图2 - 1 基于计算经济模型的网格资源管理体系结构图1 5 图2 - 2n i m r o d 项目框架结构图。1 7 图z - 3 网格资源经纪代理及其与外部实体的接口图1 8 图3 - 1 原有算法实现流程图乃 图3 - 2 代价时间比算法实现流程图3 l 图4 - 1g r i d s i m 系统结构图3 9 图4 - 2 代价优先算法作业完成数量图4 2 图4 - 3 代价时间比弊法作业完成图4 2 图4 - 4 代价优先算法时间花费图4 3 图4 5 代价时间算法时间花费图 图4 6 时间优先算法作业完成数量图 图4 - 7 时间优先算法时间花费图4 4 图4 - 8 代价一时间优先算法作业完成数量图4 5 图4 - 9 代价一时间算法时间花费图4 5 表4 - 1 仿真资源节点表4 1 术语索0 术语索引 a b s t r a c to w n e r , a o 抽象所有者 a n ta l g o r i t h m s a a蚂蚁算法 c o s t e s t i m a t i o n 代价估计 d e a d l i n eb u d g e tc o n s t r a i n ，d b c 作业截止期限和预算约束 d b ca l g o r i t h m s 基于作业截止期限和预算约束的调度算法 d i s t r i b u t e ds y s t e m st e c h n o l o g yc e n t r e 。d s t c分布式系统技术中心 d o u b l ea u c t i o n 双边拍卖 d u t c ha u c t i o n荷式拍卖，降价拍卖 f i r s t p r i c eo p e n - c r ya u c t i o n 第一价格公开拍卖 f i r s t - p r i c es e a l e d - b i da u c t i o n 第一价格密封拍卖 g r e a tg l o b a lg r i d , g g g 全球大网格 西dc o n s l l m e r g r 网格用户层 g r i dr e s o u r c eb r o k e r , g r b 网格资源经纪层 g r i dm i d d l e w a r es e r v i c e s g r s 网格中间件服务层 蛳ds e r v i c ep r o v i d e r s , g r p 网格服务提供者 g l o b n sr e s o u r c ea l l o c a t i o na n dm a n a g e m e n t ，g r a mg l o b u s 资源分配和管理 g e n e d ca l g o r i t h m s ，g a 遗传算法 1 4 0 n d e t e r m i n i s t i cp o l y n o m i a lp r o b l e m , n p 非确定型的多项式问题 p e e rt op e e r , p 2 p 对等计算 p a r a s i t i cc o m p u t i n g 寄生计算 q u a l i t yo fs e r v i c e q o s 用户服务质量 r e p l i c a t i o nd e c i s i o n s 副本决策 r e s o u r c es e r v i c ep r o v i d e r s r s p 资源服务提供者 r e s o u r c er e q u e s t e r , r r资源请求者 c o n d - p r i c es e a l e d - b i da u c t i 0 1 1 维克瑞拍卖，第二价格密封拍卖 v i r t u a lo r g a n i z a t i o n , v o 虚拟组织 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 习立 2 0 0 7 年6 月 日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ： 查弦2 0 0 7 年f 月 日 第一章绪论 河海大学硕士学位论文 1 1 选题背景 第一章绪论 九十年代中期，美国阿冈国家实验室的一位科学家伊恩福斯特( 1 a nf o s t e r ) 最先把网格这个术语扩展到了计算机领域【l 】。同时，技术进步使得各种计算资源 的能力越来越强。这一切使得在地理上广泛分布的大量计算资源( 包括超级计算 机、集群、工作站、p c 等等) 能集合起来共同进行大规模阀题的求解研究。由此 引出了一种新的网络计算模式网格计算。网格计算是指在动态的、异构的、 广域的虚拟组织( v i r t u a lo r g a 毗哦i o n ) 中进行的协同资源共享和问题求解 2 1 。 到目前为止，对于网格的定义还没有统一的描述，网格之父i a nf o s t e r 认为： “网格是构筑在互联网之上的一种新兴技术，它将高速互联网、计算机、大型数 据库、传感器、远程设备等融为一体，为科技人员和普通用户提供更多的资源服 务和功能。互联网主要为人们提供电子邮件、网页浏览等通信功能，而网格则能 提供更多更强的功能，它能让人们共享计算资源、存储资源和其他资源”。2 0 0 0 年，i a nf o s t e r 在网格的剖析一文中进一步把网格描述为“在动态变化的多 个虚拟机构问共享资源和协同解决问题”【2 l 。就目前来讲，业界对网格概念的描 述可分为狭义和广义两种，狭义网格按照l a nf o s t e r 的观点必须同时满足三个条 件聊：在非集中控制的环境中协同使用资源：使用标准的、开放的和通用的协议 和接口；提供非平凡的服务质量。 很多人更赞同广义的网格概念，称作全球大网格g g o ( g r e a tg l o b a lg r i d ) ， 它不仅包括计算网格、数据网格、信息网格、知识网格、商业网格，还包括一些 已有的网络计算模式，例如对等计算p 2 p ( p c e rt op e e r ) 、寄生计算( p a r a s i t i c c o m p u t i n g ) 等。因此，可以这样认为，i a nf o s t e r 赞成狭义的“网格观”，而g g g 是一种广义的“网格观”1 , 1 - 7 。 由于网格的动态特征，网格中的资源调度涵盖很多方面，可以从多个角度、 多方面进行探讨。在网格环境中，有大量不同需求的应用和大量广域分布的计算 资源这些资源没有全局的控制中心和统一的调度机制，且动态变化。因此，很 多这方面的课题都在尝试探索一种能够适应计算网格环境并能较好协调各方利 第一章绪论河海大学硕士学位论文 益的调度模型。网格调度就不仅要考虑如何按时完成用户的应用，同时还要考虑 如何来协调资源提供者和需求者之间的关系以及资源利用的时效性、网格调度的 适应性等问题。本文研究的计算经济模型正是伴随着这些问题被提出的，文章重 点了研究经济模型下的资源调度算法并尝试改进该模型下的一些调度算法。 1 2 研究现状及进展 网格中的资源调度这一课题跨度很大，既要求对网格相关的理论有一个清楚 的了解，还要求对分布式系统的设计、网络计算、并行设计等相关知识有较强的 把握。而由于网格的动态特征，网格中的资源调度涵盖很多方面，可以从多个角 度、多方面进行探讨。因此，网格调度已经被证明是n p ( 非确定型的多项式问题， n o n d e t e r m i n i s t i cp o l y n o m i a lp r o b l e m ) 难题。本文认为，网格调度的研究现状可 以从国内外网格项目、网格资源调度模型、网格资源调度算法三个方面进行介绍。 1 2 1 网格项目研究现状 国内外许多优秀的网格研究项目都对网格资源管理问题进行了研究。下面列 举几个有代表性网格研究课题。 g l o b u s i s 9 1 以阿冈国家实验室为主，全美有1 2 所大学和研究机构参与开发的 研发性网格项目。g l o b u s 对资源管理、数据管理、信息服务、安全及应用开发 环境等网格计算的关键技术都进行了研究，开发能在各种平台上运行的网格计算 工具软件( t o o l k i t ) 。g l o b u s 资源管理结构包括中介者、协同分配器和g l o b u s 资源 分配和管理( g l o b u sr e s o u r c ea l l o c a t i o na n dm a n a g e m e n t ，g r a m ) 几个部分，它 是应用和资源之间的桥梁。 s e t i ：h o m e 1 0 1 这是由美国加州大学伯克利分校建立的一项旨在利用连入 i n t c r n e t 的成千上万台计算机的闲置能力搜寻地外文明的巨大试验型项目。通过 s e t l h o m e ，世界各地的计算机用户将合作进行一项大型科学试验。每一个参 加者可以通过下载并运行屏幕保护程序的方式以自己的计算机参与检测地外文 明微弱的呼叫信号。 c o n d o r l l l , n l 是由美国威斯康星大学开发的一个机群作业管理系统，其最显著 的特征是充分利用空闲的计算机c p u 时钟周期。在资源池中的工作站被用来执 行作业。当工作站的所有者开始使用该工作站时，c o n d o r 便将运行在该工作站 2 第- 章绪论 河海大学硕士学位论文 上的作业迁移到其它节点上继续运行，从而避免了对工作站所有者的影响。 n i m r o d g l 是由分布式系统技术中i j , ( d i s t d b u t e ds y s t e m st e c h n o l o g yc e n t r e ， d s t c ) 和澳大利亚莫纳什学( m o n a s hu n i v e r s i t y ) 合作开发的一个工具集，其主要 设计目标是提供基于网格环境的大型分布式实验平台，提供一种简单的声明式参 数化建模语言使用户可以规范他们所要提交的作业和需求。该项目建立了计算经 济的资源管理模型，基于作业截止期限和预算约束系列算法是n i m r o d g 项目中 的主要资源调度算法。 还有许多国家和地区也设立了网格计算项目l i q ，如英国的e s c i e n c e 计划0 5 1 ， 日本的n 甜m ，法国的a c ig r i d t 用，荷兰的p o l d e rm e t a c o m p u t e r l l 。增等。这些 项目都对资源管理进行了研究。 国内的网格研究始于2 0 0 0 年，比国外晚几年时间。但由于政府的高度关注， 国内网格“自上而下”的进展也非常迅速。目前我国已经开启了几个大的网格项 目1 5 j ，即科技部负责的中国国家网格c n g r i d 、教育部负责的中国教育科研网格 c h i n a g r i d 、国家自然科学基金委负责的e s c i e n c e 网格研究计划、上海交通信息 网格、中国空间信息网格。其中很多网格项目在资源调度方面都有创新性的研究 成果。 总体来说，国内网格项目的应用范围主要面向科学计算相关的领域。现在国 内网格项目开始越来越多的投入到实际应用当中，如河海大学高性能网格计算平 台，该平台为水利高性能计算服务。项目中的资源调度部分更多地考虑在实际应 用的效果。因此，各种网格研究机构在网格资源调度这个课题上都做出了大量的 理论和应用方面的研究和试验 1 2 2 网格资源调度模型研究现状 网格资源管理系统模型按照体系结构主要分为三类【1 9 l ：计算经济模型、层 次( 分层) 模型、抽象所有者模型。这三类模型分别体现了三种不同的技术思想， 都不同程度的表达了上述的功能需求，其中引入了市场经济机制的计算经济模型 有着很好的应用前景。 1 层次模型被当前大部分网格系统采用，g l o b u s 、l e g i o n 、c c s 、a p p l e s 等系统都是采用层次管理模型。网格资源管理系统的层次模型【1 9 , 2 0 1 是在全球网格 论坛( g l o b a lg r i df o r u m , g g f ) 第二次会议上提出的，在实践中己被大多数网格系 3 第一章绪论河海大学硕士学位论文 统所采用，基本思想就是整个资源管理系统分成若干功能层，较高层次的组件利 用较低层次组件提供的服务实现自身的功能。该模型由被动和主动两种组件构 成。层次模型是当前的大部分网格系统中所使用的资源管理模型，它有如下特点。 有利于对具有站点自治性和底层异构性资源进行管理，并具有较强的 适应性； 能定义可扩展的资源规范语言来解决在线控制问题并使政策具有可扩 展性： 能在一定程度上实现资源的联合分配。 2 抽象所有者模型是订购与传递模型，集中于长期目标。因此将来大部分 p 2 p 计算系统可能会基于此模型。在抽象所有者模型伫1 】中，主要有两种主体：客 户和抽象所有者( a b s t r a c to w i l e l ，a 0 ) 。客户即是传统意义上的资源消费者，而 抽象所有者a o 是此模型的重点。目前尚未出现典型的采用抽象所有者模型的网 格资源管理系统，也许当前颇受欢迎的p 2 p 系统未来会采用该模型。抽象所有者 模型主要有两个特点。 使用作为资源所有者抽象代表的资源经纪代理与用户进行交互； 资源共享过程中遵循类似于快餐店的订购与交货模式。 3 计算经济模型主要遵循经济模型对资源进行发现。目前主要有g r a c e ( t h eg 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 ) 、j a v a m a r k e t 、g c o m m e r c e 、 g e s a ( g r i de c o n o m i cs e r v i c e sa r c h i t e c t u r e ) 。计算经济模型的特点如下。 基于经济原则的投资回报机制，促进了计算服务质量的提高和资源的 升级，价格是调节供求关系的最重要的机制； 为访问网格资源的用户提供公平的价格机制，并允许对一切资源进行 交易； 建立以用户为中心，而不是系统为中心的调度政策，提供了资源分配 和管理的有效机制； 综合了分层模型和抽象所有者模型的实质，吸取了分层模型中高层组 件利用低层组件构建新功能的思想，同时利用了抽象所有者模型中资 源经纪代理的概念【2 2 1 。 实际应用中，有些网格资源管理系统是这三类模型不同程度的混合【1 9 1 ，因 4 第一章绪论河海大学硕士学位论文 此也有一些研究人员将网格管理模型分为四类，即计算经济模型、层次模型、抽 象所有者模型和混合模型【2 3 1 。 1 2 3 网格资源调度算法 目前的网格调度算法主要有两大类：传统的调度算法和计算经济模型下的调 度算法。具体算法如下： 1 m i n - m i n 算法1 2 4 。这是网格作业调度的基础算法之一，其基本思想是将 最好的资源分配给最小的任务，以提高系统吞吐率。 2 m a x - r a i n 算法【2 5 l 。该算法思想正好和m i n - m i n 相反，它是将最好的资源分 配给最大的任务，以获得总体作业的最小完成时间。算法过程和m i n r a i n 类似， 只是将上面第三步在m i n t i m e 中找出最小的元素改为找出最大的元素。 3 s u f f e r a g e 算法1 2 6 。基本思想是计算任务最优和次优资源分配的完成时间 差，将时间差最大的任务分配给能使它最早完成的资源。 4 基于蚂蚁算法的( a n ta l g o r i t h m s ，从) f 2 7 】的网格调度算法。这是种较新 的启发式算法，它是基于蚂蚁觅食的行为。当蚂蚁在寻找食物时，每只走动的蚂 蚁都会在其经过的路上释放信息素，因为信息素会随时间挥发，每条路径上信息 素的强弱代表了其它蚂蚊选择该路径的概率，蚂蚁走动时会选择信息素强的路 径。这样，经过多个蚂蚁的选择，最优路径上的信息素会增加。最终，所有蚂蚁 都将选择最优路径。蚂蚁算法固有的并发性和可扩充性，使得它非常适合于网格 环境下的作业调度。 5 基于遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 【2 8 , 2 9 1 的网格调度算法。这是一种 启发式的智能调度算法。遗传算法是将问题的求解表示成染色体( c h r o m o s o m e ) ， 并将这些染色体置于求解问题环境中，根据适者生存的原则，从中选择出适应环 境的染色体进行复制，通过交叉、变异产生出新一代更适应环境的染色群体，经 过不断进化，最后收敛到一个最适合环境的个体上，求得问题的局部最优解。 6 基于a g e 【的调度算澍圳。a g e n t 技术源自人工智能领域，目前在计算机 领域得到了广泛应用，它为复杂、异构、开放的分布式系统开发提供了新思路和 新途径。基于a g e n t 的作业调度基本思想是：将每个网格资源节点封装成一个 a g e n t ，把网格系统看成一个多层次a g e n t 系统的集合。通过a g e n t ，可以把各种 异构资源抽象成具有相同特性的抽象资源，对上层应用隐藏资源的异构性。这样 5 第一章绪论 河海大学硕士学位论文 的层次结构具有高度可扩展性，适于在网格这样庞大的异构环境中运用。 7 基于经济学的资源调度【3 l i 。是在基于经济模型的网格资源管理系统中使 用的调度算法，引入了市场机制，对每个资源定义其使用价格，希望通过价格竞 争来达到资源的供需平衡。主要有基于作业截止期限和预算约束( d e a d l i n eb u d g e t c o n s t r a i n ，d b c ) 算法等。 1 3 论文的主要工作 本文在广泛阅读国内外关于网格资源调度方面的文献后，对基于计算经济模 型的调度算法进行了一些研究和改迸，并进行了仿真试验。论文的主要研究内容 包括以下几个方面： 1 对当前网格研究项目、网格资源调度模型和资源调度算法的研究情况做 了相关总结。 2 对经济学中的经济模型进行了研究，分析了经济模型的特征。根据网格 的特点分析了几种较成熟的可应用到网格中经济模型。在此基础上进一步研究了 网格中的计算经济模型的结构、特点、功能等。 3 对网格资源调度进行了研究，分析了计算经济网格中用以完成资源查找、 交易和作业分配的网格资源经纪代理模型：在对经济网格中基于作业截止期限和 预算约束( d e a d l i n eb u d g e tc o n s t r a i n ，d b c ) 的代价优先调度算法、时间优先调度 算法、代价时间优先调度算法进行研究的基础上，给出了一种基于d b c 的代价 时间比作业调度算法。 4 利用网格仿真工具g r i d s i m 对基于d b c 的代价时间比调度算法进行仿 真，并分别与代价优先和时间优先调度算法进行了比较，最后对d b c 的代价，时 间比算法的调度性能进行了仿真分析，仿真结果与预想的效果基本一致。实验结 果表明：本文改进的算法是合理的，该算法能为用户提供更大的灵活性，满足用 户的实际需要：在预算时问和代价内，完成作业的数量更多。 本课题来源子： 河海大学科技创新基金“网格计算基础设施试验床的研究与构建”。 河海大学“十五”“2 1 1 工程”建设子项目“高性能工程计算平台”。 本课题意义在于： 6 第一章绪论 河海大学硕士学位论文 1 研究网格环境下的计算经济模型的特点，以充分利用网格中各种资源， 高效的完成计算任务。 2 把计算经济模型引入网格资源管理，通过价格浮动反映资源供需状况的 动态变化，通过供需均衡实现资源优化分配，以满足网格环境下资源分配的动态 性、自治性和异构性。 3 研究网格作业调度算法，给出一种基于作业截止期限和预算约束 ( d e a d l i n eb u d g e tc o n s t r a i n ，d b c ) 的代价时间比调度算法，以满足用户对作业完 成数量的要求。 4 利用合适的网格模拟器验证作业调度算法的正确性和性能，不仅可以获 得较准确的模拟结果，还节省了人力、物力、财力，可以获得很好的经济效益和 社会效益。 1 4 本文的组织结构 全文包括5 个章节，分别安排如下： 第一章绪论 主要介绍网格技术的产生背景，网格资源调度的相关研究现状。 第二章经济模型下的网格资源调度 主要分析了经济学中的经济模型的特点和内容、网格中的计算经济模型以及 网格资源经纪代理模型及其基础上的基于作业截止期限和预算约束的资源调度 算法。 第三章d b c 资源调度算法的实现和改进 分析了原有算法的不足，并给出了改进算法一基于作业截止期限和预算约 束的代价时间比算法。 第四章算法仿真与结果分析 搭建算法仿真环境并对改进算法进行仿真试验，与原有算法进行结果对比并 分析d b c 算法。得出结论。 第五章总结与展望 总结了本文的要点和主要工作，并对本课题的进一步研究方向和未来发展进 行了展望。 7 第二章经济模型下的网格资源调度 河耨大学硕士学位论文 第二章经济模型下的网格资源调度 由于网格中的资源具有广域分布性、异构性、自治性、动态性、二重性等特 点。因此，使得网格资源管理非常复杂，需要建立适应于网格这种复杂环境的特 殊的资源管理系统模型。计算经济管理模型中基于经济原则的投资回报机制可以 促进计算服务质量的提高和资源的升级，为用户提供更优质的服务。本章将重点 介绍网格中计算经济模型、网格资源经济代理模型以及该模型下的算法。 2 1 经济模型概述 经济模型是一种分析方法，是指经济理论的数学表述，是经济管理与决策中 分析复杂经济现象的重要工具。经济模型主要用来研究经济现象问互相依存的数 量关系。 经济模型的目的是为了反映经济现象的内部联系及其运动过程，帮助人们进 行经济分析和经济预测，解决现实的经济问题。 经济模型对现实世界的情况进行简化的描述。现实世界的情况是由各种主要 变量和次要变量构成的，所以非常复杂。因此，除非把次要的因素排除在外，否 则就不可能进行严格的分析或者使分析复杂的难以进行。经济模型通过做出某些 假设，可以排除许多次要因素而建立起模型。这样一来，便可以通过模型对假设 所规定的特殊情况进行分析。 经济系统是最复杂的非线性、非均衡、非完全信息的动态系统【3 2 1 。因此， 非线性模型( 经济模型) 在宏观经济研究中，特别是揭示宏观经济规律时具有不可 替代的重要作用。经济模型的建立有几个原则，第一，经济模型要建立在经济理 论之上，否则经济模型没有经济意义。当经济模型彼用于做政策分析时，一定要 坚持这种原则。第二，模型形式的选择。虽然经济系统是非线性的，但仍可以使 用线性模型来逼近模型经济系统，此时形式是唯一的，只是变量选择问题。理论 上讲，应使用非线性模型来描述经济系统，但此时除同样存在变量选择问题外， 模型的形式选择一个十分困难的问题。因为非线性千交万化，而不是唯一的。况 且模型发散问题就比线性模型突出得多。第三，变量的选择。通常有两种办法。 即逐步剔除法和逐步引入法。变量选择的思路是，定性分析，打开思路：列出所 第二章经济模型下的网格资源调度 河海大学硕士学位论文 有可选变量，并按影响程度排序。此时，可使用经济理论以及业务知识选择变量 和排序，或利用相关系数大小进行排序。变量选定和排序以后，要把重要的变量 选择出来用于建立模型和备选变量，而把非重要的变量放弃f 实际上它们还包括 尚未认识到的因素被视为不变，其影响作用体现在模型中的常数项中) 。第四， 非线性形式的选择。如前所述，非线性模型存在两个致命的问题：一是形式难以 确定i 二是模型发散快。 同时，基于经济学的资源分配中一个重要的因素就是价格，在不同的经济模 型下，资源的定价策略和价格调整方式是不同的。均衡是经济学中一个基本的概 念，它是在一定的假设条件下，市场供需处于平衡的一种状态。均衡分析则是运 用得最为普遍的一种分析方法【3 3 】。根据经济学的一般理论，资源的价格应由其 生产成本和供求关系共同决定，当市场处于均衡状态时，出现均衡价格( 市场出 清价格) ，满足均衡价格的资源分配是最合理和最有效的i 蚓。 由于网格市场环境中包括两个最重要的角色：网格资源提供者和网格资源代 理，他们分别代表生产者和消费者。因此，经济学领域中的一些原理是比较适合 网格环境下的资源分配和任务调度的。在经济学领域，有众多成熟的经济模型值 得借鉴，较流行的有如下几个 3 5 1 ，多商品市场模型、议价模型、拍卖模型、招 标契约模型等。 本章讨论的经济模型按资源价格的确定者来划分可以分为三类：资源拥有者 制定资源价格( 商品市场模型、牌价模型、招标、契约模型) ；双方协商确定价格( 议 价模型) ；资源使用者主动出价( 拍卖模型) 。由于篇幅所限，本文只能重点对拍卖 模型下的资源均衡价格进行分析。 2 1 1 多商品市场模型 在多商品市场模型1 2 3 1 d e ，资源服务提供者( r e s o u r c es e r v i c ep r o v i d e r s 。r s p l 定义他们的服务价格并且根据资源请求者( r e s o u r c er e q u e s t e r , r r ) 的资源消费量 收费。定价策略可以根据各种参数，可以是水平不变的，也可以是取决于资源的 供求关系。通常情况下，服务的价格制定应该能够使资源的供求关系达到均衡。 在水平价格模型中，一旦价格在一定的时期内固定下来，它就保持不变无 论服务质量如何变化，也即它对供求变化不敏感。而在供求模型中，价格变化一 般取决于供求变化。原则上，当要求增加或者供给减少时，价格会增加直到存在 第二章经济模型下的网格资源调度 河海大学硕士学位论文 新的供求均衡。 一般经济均衡理论的主要目的是研究市场经济条件下的资源配置问题，其含 义是在完全竞争的商品市场中，只有当所有市场供需平衡时。经济才处于均衡。 否则就是菲均衡。它是由瑞士洛桑大学经济学教授瓦尔拉斯( l w a l m s ) 在 1 8 7 4 1 8 7 7 年问提出的，而后由著名经济学家阿罗( k a r r o w ) ，德布鲁( gd e b r e u ) 等人完善发展，形成了a r r o w - d e b r e u 模型【3 6 1 。一般经济均衡理论的建立为理论 经济学的研究奠定了坚实的基础，现代许多经济理论的研究都是在这一基础上展 开的。 2 1 2 议价模型 议价是一种最普遍，最原始的商品买卖方式。在现实生活中议价( b a r g a i n i n g ) 即通常的“讨价还价”，是广为人们熟知的它的普遍性和基本性包括人们对 它的熟悉性。到目前为止，经过几十年的发展，议价理论已经基本上形成了一个 完整和成熟的分析框架，这些分析方法已经广泛地被运用于现实问题特别是 工资和就业决定问题的研究【3 5 1 。议价理论可以分为两个分支，合作博弈的议价 理论( 或者叫公理性的议价理论) 和非合作博弈的议价理论( 或者叫战略性的议价 理论) 。 2 1 3 拍卖模型 拍卖作为一种商品交易机制，应用十分广泛。在市场经济中，巨额的经济活 动是通过拍卖的方式进行的【3 7 1 。经常被拍卖的物品包括古董、珠宝、住房，农 产品等有形资产，也包括一些无形资产，如土地使用权，油田开采权等。拍卖也 长用于定向购买物品或服务。比如，数家公司竟投承包一项工程或提供某项服务。 拍卖的最大特点是，价格由竞争的方式来决定，不由卖方说了算，也不是有 买卖双方讨价还价来确定。竞争价格决定的优越性源于非对称信息。卖方不完全 知道潜在买方愿意出的真实价格，这种信息通常只有买方自己知道。每一个潜在 买方也不知道其他买方可能的意愿出价。拍卖的竟价过程可以帮助卖方收集这些 信息，从而把物品卖给愿意付最高价的买方。这不仅达到资源有效配置，也为卖 方取得最高收益。 拍卖可以是公开的也可以是封闭的，常见的拍卖有以下几种方式：英式拍卖 第一价格公开拍卖( f i r s t p r i c eo p e n c r ya u c t i o n ) ；第一价格密封拍卖( f i r s t - p r i c e 1 0 第一：章经济模型下的网格资源调度 河海大学硕+ 学位论文 s e a l e d - b i da u c t i o n ) ；维克瑞拍卖，第二价格密封拍卖( s e c o n d p r i c es e a l e d b i d a u c t i o n ) ；荷式拍卖，降价拍卖( d u t c ha u c t i o n ) ；双边拍卖( d o u b l ea u c t i o n ) 。其中双 边拍卖是最广泛使用地拍卖方式。 在价格方面，一般均衡理论假定的是一种理想的完全竞争市场，由于网格的 异构性、自治性、动态性，使得网格环境非常复杂，且规模庞大，资源提供者之 问直接的竞争和互相制约很大，资源价格不能完全由供给和需求决定；同时，资 源交易的双方并不具备共同知识，网格资源提供者和网格资源消费者之间存在不 完全信息的博弈，可以使用基于贝叶斯纳什均衡理论确定资源分配策略。 博弈论是研究决策主体的行为发生直接相互作用时的决策以及这种决策的 均衡问题，它使用严谨的数学模型研究冲突对抗条件下的最优决策问题。现代博 弈论是在2 0 世纪5 0 一6 0 年代发展起来的，到2 0 世纪7 0 年代，博弈论正式成为 主流经济学。博弈有多种分类，按照参与人之间是否合作可分为合作博弈和非合 作博弈；按照参与人对其他参与人的了解程度可分为完全信息博弈和不完全信息 博弈。 纳什( j o h nn a s h ) 于1 9 5 0 年和1 9 5 1 年发表的两篇关于非合作博弈的重要论 文，证明了非合作博弈及其均衡解的存在性，即著名的纳什均衡。从而揭示了博 弈均衡与经济均衡的内在联系，奠定了现代非合作博弈论的基石。 在纳什均衡的基础上，海萨尼( h a r s a n y i ) 提出了不完全信息静态博弈的贝叶 斯纳什均衡。贝叶斯纳什均衡是这样一种均衡状态：在给定自己类型和别人类型 的概率分布的情况下，每个参与人的期望效用达到了最大化，也就是没有人有积 极性选择其他的战略贝叶斯纳什均衡的一个重要领域是招标或拍卖方面。 网格环境下的贝叶斯纳什均衡是在供需双方不具备完全信息的特定条件下 市场资源配置最优化的一种均衡状态。在不完全信息条件下，如果市场经济参与 者所选的策略处于这样一种状态，即不论其他参与者属于何种类型，每一个参与 者的策略行动一定是关于其他参与者策略行动的最佳反应，称市场处于贝叶斯纳 什均衡状态。根据贝叶斯纳什均衡理论，可以建立网格市场各经济个体在相互竞 争和相互制约以及不具备共同知识的条件下，实现自身利益最大化和资源配置最 优化的模型。 以下基于c h a t t e r j e e 和s a m u e l s o n 的双边叫价拍卖模型讨论其均衡解1 3 8 l 。 第二章经济模型下的孵洛资源谓度河海大学硕士学位论文 i 基本模型 在双边叫价模型中，只有卖方( 资源提供者) 知道资源的生产成本c ，只有买方 ( 资源消费者) 知道资源的预期收益v ，在不完全信息条件下，c 和v 不是共同知 识，卖方要价凡，买方出价p b 。如果只最，则交易发生且交易价格为 p = ( + 8 ) 2 ；如果只 忍，则交易没有发生。此拍卖过程既是一个b a y e s 博 弈过程，买卖双方的要价策略和出价策略构成b a y e s 博弈。 设c 和v 都是在【o ，h 】上服从均匀分布的随机变量，在这个b a y e s 博弈中， 卖方的要价 是c 的函数p “c ) ，买方出价p b 是v 的函数p “v ) 。卖方的效益函 数是： 以= 只+ 名7 2 一c ：主妻2 ： 因为卖方不知道买方预期收益v ，所以卖方的期望盈利w 。为： 形= 隆( z + e ( n i 忍( 矿) ) ) 一c 1 m a 化咒( y ) ) ( z 一，) 上式中e ( 只( 矿) 1 只只( y ) ) 是在卖方要价低于买方出价的条件下，从卖方角 度看，买方出价的期望值。 同样，买方不知道卖方的生产成本c ，所以买方的效益函数和期望盈利w b 为： 巩= y 一只l 忍y 2 ：置譬；妻量 = 舻圭( 最+ e ( 只( c ) 吲c ) e ) ) 】m a ( 即) 最) ( z 叼 上式中e ( c ) f 只( c ) 忍) 是在卖方要价低于买方出价的条件下，从买方角 度看，卖方要价的期望值。 v c ，v e o ，h 】，记使得( 1 ) 式和( 2 ) 式达到极大值的p “c ) 和p “、，) 分别为 f ( c ) 和最( y ) ，即：只+ ( c ) = ，m 。州a x w , ；只( c ) 。曜鼢彤则策略组合 只( c ) ，思( 矿) ) ，就是所求的b a y e s 均衡。 1 2 第- ：章经济模型下的网格资源调度 河海大学硕士学位论文 2 基于线性战略求均衡解 不完全信息的双边b a y e s 博