（计算机软件与理论专业论文）基于最优竞胜标的网格资源市场优化研究.pdf

原创性声明 l i i i i iui i i i l ui i i i i i ii ii 18 3 3 6 6 7 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者： 匙舌甘 日期：上ofp 年e 月乙6i t 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑卅i 大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州 大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、 缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学 位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑 州大学。保密论文在解密后应遵守此规定。 学位论文作者：恕毛甘 日期：b7 0 年s 月l 6 日 摘要 摘要 网格计算是解决各种大规模计算的下一代极具潜力的计算平台。通过网格 可以把分散在世界上不同地理位置的资源整合起来实现对资源的全面共享。网 格计算最关键的问题是如何有效的协调和分配资源使整个网格环境健康高效的 发展。 本文以网格计算为背景，研究如何利用经济模型来选取参与计算的网格资 源和任务，使得整个网格市场收益达到最大化。经济网格模型中求解组合双拍 卖最优竞胜标问题，就是买卖双方开始进入拍卖流程前，在满足资源供不小于 求的条件下，选择优秀的买家和卖家进入到拍卖市场中参与竞拍。本文通过引 入一种融合粒子群算法和遗传算法的新型算法来确定组合双拍卖最优竞胜标， 实现整个市场的收益最大化。该算法通过在粒子群算法中引入遗传算法，借鉴 了遗传算法中交叉、变异和选择等遗传算子的思想，对粒子群中的粒子与其个 体最优粒子和全局最优粒子进行相应操纵，来获得新粒子，有效克服粒子群算 法容易陷入局部最优值的缺陷，重新在搜索空间寻找全局最优值。同时在改进 的粒子群算法里引入信任的概念，选取信任值高的卖家和买家参与组合拍卖和 市场交易，防止恶意卖家或买家参与竞拍，较大程度的排除了由于执行信任值 低的任务或资源，使整个网络陷入紊乱和瘫痪的可能，进而可以提高网格资源 调度的成功率，优化网格系统的整体性能。 实验采用g r i d s i m 仿真软件对组合双拍卖进行模拟实现，实验结果证明与 改进遗传算法、离散粒子群算法相比，本文改进的粒子群算法应用于组合双拍 卖模型中使得整个市场的收益最大，并且保证了参与拍卖过程的每一个参与者 尽可能多地受益。 关键字网格资源调度组合双拍卖粒子群信任g r i d s i m a b s t r a c t g r i dc o m p u t i n gi st h em o s tp o t e n t i a l n e x tg e n e r a t i o nc o m p u t i n gp l a t t o mt 0 s 0 1 v ev a r i o u s1 【i n d so fl a r g e - s c a l ec o m p u t i n g w i t hi t sh e l p , w ec a l li n t e g r a t e a l lt h e r e s o u r c e st l l a ts c a t t e r e dd i f f e r e n tl o c a t i o n si nt h ew o r l d , t oa c h i e v et h ea c c e s sf o r a l l f o rr e s o u r c e s t h ek e yo fg r i dc o m p u t i n gi sh o w t oc o o r d i n a t ea n ds c h e d u l et h e r e s o u i e se f f e c t i v e l y ，t om a k et h eg a da c h i e v et h eo p t i m a lp e r f o r m a n c e t 1 1 i sp a p e ri ss e ti nt h eg r i dc o m p u t i n g , t or e s e a r c hh o w t os e l e c tt om v o i v em 鲫da 咖叫i n gr e s o u r c e sa n dt a s k su s i n g t h ee c o m o m ym o d e l i _ l l e0 p 1 。l m a l c o m p 甜t i o nf o rw i n n e rp r o b l e mi nt h ec o m b i n a t o r i a l d o u b l ea u c t i o no fe c o n c t m o d e l i t sp r o b l e mi st h a tb o t hp a r t i e sa r er e q u i r e dt oc h o o s et h eg o o db u y e r sa i l d s e l l e r so nt l l ec o f l d i t i o nt h a tr e s o u r c e ss u p p l yn o tm o r et h a nd e m a n d f o r , b e f o r et h e y e n t e rm ea u c t i o np r o c e s s t h i sp a p e ri n t r o d u c e s an e wi n t e g r a t i v ea 1 9 0 n u l l l l o t p a n i c l es w 锄o p t i m i z a t i o n a n dg e n e t i ca l g o r i t h m t od e t e r m i n et h eo p 乜m 甜 c o m p e t i t i o nf o rw i n n e ri n c o m b i n a t o r i a ld o u b l ea u c t i o n a n dm a k et h eb 耐l to t m a r k e tm a 】【i m i z a t i o n t h i sa l g o r i t h m i n t r o d u c e st h eg e n e t i ca l g o r i t h m i n t ot h e p 矾d es w a n i lo p t i m i z a t i o na l g o r i t h m ，c r o s s r e f e r e n c et h ei d e ao f c r o s s ，m u t a t i o n 觚d s d e c t i o ni nt h eg e n e t i ca l g o r i t h m t og e tt h en e wp a r t i c l e , b ym a k i n g c o l l 诧：s p o n d l n g o p e r a t i o no nt h ep a r t i c l e s i n p a r t i c l es w a r m ，i n d i v i d u a l a n dg l o b a lo p t i m a l p 枷d e s i te a s i l yo v e r c o m ep s o i n t oal o c a lo p t i m u nv a l u eo ft h i si n h e r e n tf l a w 锄d f i n dt h eg l o b a lo p t i m u ma g a i ni nt h e s e r a c hs p a c e m e a n w h i l e ，i ti n t r o d u c e st h e c o n c 印t i o no ft r u s tv a l u ei n t ot h ei m p r o v e dp a r t i c l es w a r m a l g o r i t h m ，t os e l e c tb u y 粥 锄ds e l l e r s 、i 也ah i g ht r u s tv a l u et h a t c a ne n t e r i n t ot h ec o m b i n a t o n a ld o u b i e a u c t i o n 锄dm a r k e tt r a n s a c t i o n ，a n dt op r e v e n t m a l i c i o u ss e l l e r sa n db u y e r st ob l d i n t 1 1 i s w a y ，i tg r e a t l yg e t sr i do f t h ep o s s i b i l i t yo fm a k i n gt h ew h o l en 咖7 0 r ki n t o d i s o r d e ra n dp a r a l y t i c ，w h e ni m p l e m e n t i n g t h et a s k so rr e s o u r c e sw i t hl o wt r u s tv a l u e i nt u m ，c a ni n c r e a s et h es u c c e s sr a t eo f o v e r a l lp e r f o r m a n c eo fg a ds y s t e m e x p e r i m e n t ss i m u l a t e t h ea c h i e v e g a d r e s o u r c es c h e d u l i n gt oo p t i m i z et h e o fc o m b i n a t o r i a l d o u b l ea u c t i o n ，u s i n g 1 i a b s t r a c t g r i d s i ms i m u l a t i o n s o f t w a r e e x p e r i m e n t a l r e s u l t ss h o wt h a t c o m p a r e d w i t h i m p r o v e dg e n e t i ca l g o r i t h ma n dd i s c r e t ep s o ，t h i si m p r o v e da l g o r i t h mc a nm a k et h e s y s t e mr e t u r n sb e s tw h e nu s i n gi ti nt h ec o m b i n a t o r i a ld o u b l ea u c t i o nm o d e l a n d e n s u l et h ep a r t i c i p a t i o no f e a c ha u c t i o ng e tm o r eb e n e f i t 嬲m u c 嬲p o s s i b l e k e yw o r d s ：g r i d ；r e s o u r c es c h e d u l e ；c o m b i n a t o r i a ld o u b l ea u c t i o n ；p a r t i c l es w a r m o p t i m i z a t i o n ；t r u s tv a l u e ；g r i d s i m ； i i i 目录 目录 1 绪论l 1 1 研究背景1 1 2 网格简介1 1 2 1 网格概念1 1 2 2 网格特点- 2 1 2 3 网格目的2 1 3 网格资源调度3 1 4 经济模型在网格中的引入3 1 5 本文主要研究内容5 1 6 本文的主要工作6 1 7 本文的组织结构6 2 基于经济模型的网格资源调度分析8 2 1 基于经济理论的网格资源管理模型8 2 1 1g e s a 8 2 1 2g c o m m e r c e 8 2 1 3g r a c e 8 2 1 4n i m r o d g 9 2 2 经济模型中的两个重要角色9 2 3 几种基本经济模型1 0 2 3 1 商品市场模型1 0 2 3 2 标价模型1 0 2 3 3 仪价模型1 1 2 3 4 投标合同模型1 1 2 3 5 拍卖模型1 2 2 4 第三方代理组合双向拍卖模型1 2 t v 目录 2 5 本章小结1 5 3 信任计算模型1 6 3 1 信任概念1 6 3 1 1 信任相关概念1 6 3 1 2 信任特性1 7 3 2 几种典型的信任模型1 8 3 2 1a b d u l r a h m a n 信任计算模型1 8 3 2 2b e t h 信任计算模型1 8 3 2 3j o s a n g 信任计算模型1 8 3 2 4a z z e d i n 信任模型1 8 3 3 本文改进的信任计算模型1 9 3 3 1 信任值的计算1 9 3 3 2 直接信任计算1 9 3 3 3 间接信任值2 0 3 3 4 总体信任值2 3 3 4 本章小结2 3 4 改进粒子群算法求解组合双拍卖竞胜标2 4 4 1 基本粒子群算法2 5 4 2 求解组合双拍卖竞胜标数学模型2 5 4 3 改进粒子群算法实现过程与设计2 6 4 3 1 编码策略2 6 4 3 2 适应度函数2 7 4 3 3 信任值函数2 7 4 3 4 选取初始种群2 7 4 3 5 更新策略2 8 4 3 6 算法终止2 9 4 3 7 算法基本流程3 0 v 目录 4 4 本章小结3 2 5 基于g r id s i m 网格组合双向拍卖仿真实验3 3 5 1 网格模拟器g r i d s i m 3 3 5 1 1g r i d s i m 概述3 3 5 1 2g r i d s i m 的体系结构3 4 5 1 3g r i d s i m 模拟实体：3 6 5 1 4g r i d s i m 仿真流程3 6 5 1 5 用户及资源模拟3 7 5 2 本文改进的粒子群算法相关操作4 0 5 2 1 交叉操作4 0 5 2 2 变异操作4 2 5 2 3 选择操作4 2 5 3 仿真实验与分析4 3 5 3 1 实验环境数据4 4 5 3 2 与其他算法实验结果进行比较4 5 5 3 3 第三方代理模式模拟4 6 5 4 本章小结4 9 6 总结与展望5 0 6 1 总结5 0 6 2 展望5 0 参考文献5 2 个人简历及在学期间发表的学术论文及科研课题5 6 个人简历5 6 在学期间发表的学术论文5 6 在学期间参与的科研课题及获奖情况5 6 v i 目录 致谢5 7 v i i 1 绪论 1 绪论 1 1 研究背景 网格技术诞生于上个世纪9 0 年代中期，是近年来国际上兴起的一种重要的 信息技术，其思想来源于电力网【1 1 。人们通过开关开电灯时，并不需要考虑这 种可以照亮房间的能量是从那儿来的。通常情况下，我们也不用关心能量是否 来源于水电、火电、还是核电，或者其他可替代能源，更不用考虑这些电站位 于何处。因为它们构成了电力网，对于电力网中大量不同的应用来说，他们连 接到电力网的简单的接口，常常是通过一个电插座就可以达到直接获取电能的 目的。电力网中的能量是作为市场上的商品进行交易的，其价格也是随着供求 关系的变化而变化的。 借鉴上述思想，可以设想一个以类似的方式获取计算能力的情景。在这个 情景中，用户的任务将在它所需要的最合适的资源上运行，其中需求较低的任 务可以在计算能力弱些的本地计算机上运行，而数字密集型任务可以在远程的 超级计算机上运行。调度器用来将用户的任务分配给它需要的资源，并且这个 过程对于终端用户是隐藏的。这种透明地接入到远程计算资源的方式与许多用 户使用计算机的方式正好相同。通常情况下，用户并不关心它的任务是在何处 完成的，只要能够确保其任务的顺利运行以及将运行结果快速地返回给用户就 可以了。透明性也同样适用于数据存储的应用方面，用户一样不用知道他们所 访问数据的地理位置。这种透明性与电力网中用户不用关心电能是如何实现以 及在何处产生是相似的。 1 2 网格简介 1 2 1 网格概念 网格研究的先驱、g l o b u s 项目的负责人l a nf o s t e r 提出了3 条判断网格 的标准【2 】： ( 1 ) 使用标准、开放、通用的协议和接口：网格是建立在多功能的协议和 接口之上，其协议和接口用于解决认证、授权、资源存取和资源发现等基本问 题； 1 绪论 ( 2 ) 协调非集中控制的资源：网格整合各种资源，协调不同用户关系，这 些资源和用户处于不同的管理区域和组织域。网格解决在这种分布式环境下的 资源管理策略、安全、费用以及权限等问题； ( 3 ) 提供非平凡的服务：网格允许协调使用资源，以得到多种服务质量， 满足不同用户需求。如系统响应时间，数据流通量、有效性、安全性等； 由于网格处于动态发展的过程中，因此目前还没有一个被大众普遍接受的 定义。i a nf o s t e r 给网格下的定义慰3 】：网格就是动态的、多机构虚拟组织之 间的受控协同资源共享以及问题解决。简单地讲，一大批异构的资源组成了一 个网格，这些资源以一致的方式进行交互和运转。 1 2 2 网格特点 网格具有以下几种特尉4 】【5 】【9 】： ( 1 ) 分布性： 网格资源通常是跨管理区域的资源，这些资源分属于不同的地理位置，网 格资源可能是计算资源、存储资源、数据资源等； ( 2 ) 异构性： 网格可以包含多种异构资源，对于这些异构资源来说，其操作系统、计算 方式、计算接口、体系结构等在多个层次上都可以具有不同的结构； ( 3 ) 自治性： 网格资源提供者对资源有高度的自主管理能力。自治性通常是指网格资源提 供者可以根据自身的情况有自愿加入或退出网格的权力； ( 4 ) 虚拟性： 网格把实际的物理资源抽象为虚拟的逻辑网格资源，网格资源使用者只需 要遵循标准网格接口发出资源请求消息，就可以获得符合该要求的资源。但是 网格向资源使用者屏蔽了物理资源细节，用户只知道“实现什么”，不用在意“如 何实现”； 1 2 3 网格目的 目的5 1 是利用高速互联网把分布于不同地理位置的计算机、存储器、数据 库和软件等各种资源连成一体就像一台超级计算机一样为用户提供一体化信息 的服务。网格最重要的核心是实现网络虚拟环境下的高性能协同工作和资源共 2 1 绪论 享，消除信息孤岛和资源孤岛。 1 3 网格资源调度 在网格环境下资源分配与调度是关键问题，也是一个n p 难问题【6 】，更是网 格应用的基础。同时，调度策略又是资源调度的重中之重，一种高效的资源调 度策略，不但可以减少任务的执行时间和代价，提高服务质量，还能够充分有 效利用网格上的资源，吸引更多的资源拥有者把自身的资源投放到网格上来使 用。 在网格环境下，构成资源调度问题的基本因素包括：网格用户的任务、网格 资源以及资源调度的策略。一般网格资源调度模型可以简化如下图1 1 所示阴： 图1 1 网格资源调度模型 用户通过向网格系统提交任务来共享网格资源，网格资源调度程序再按照 某种策略将这些任务分配给合适的资源，所以高效的调度算法可以充分利用网 格系统的处理能力，提高整个网格系统的吞吐量。 网格资源调度的实质就是将m 个异构的、分布式存在的资源调度到n 个相 互独立的任务上，使得任务完成时间最小或消耗的费用最少。所以如何有效的 调度资源，最大限度的实现资源的利用价值，成为网格资源管理研究的主题。 1 4 经济模型在网格中的引入 由于网格环境的动态性，无法预先定义一个供需关系表作为资源和用户任 务的中介。借鉴人类社会的经济调节理论，需要在网格中建立一个经济模型， 通过经济社会中供求关系和资源代价来调节资源与用户任务的平衡，提供一个 公共的解决方案。 资源调度在网格环境中是个非常复杂的问题。在网格环境中，由于分布在 不同地理位置上的各种资源属于不同组织，而且这些组织的计费模型、规则、 3 1 绪论 负荷能力等都不尽相同，并且卖方和卖方的目的、要求、目标以及策略也不相 同，因此一些传统的资源管理和调度方式在网格系统中并不适用。但是采用分 层的管理策略是很好的方法，利用经济模型来调节市场的供求平衡是非常有效 果的【8 ，1 1 1 。 基于经济模型的网格资源分配的实现侧重于将具体的资源管理抽象成为数 学模型，然后依据一定的经济学理论进行分析和模拟。如果从经济学的角度来 看，在网格环境下，资源卖方和资源买方之间实际上是一种买卖关系，资源买 方暂时购买资源的使用权，资源卖方暂时出卖资源的使用权，也就是说，实际 在进行买卖的商品是资源的使用权。在这个过程中，资源卖方目标是获取最大 的经济利益而且能够使自己的资源得到充分的使用，而资源买方的目标则是在 自己的一些约束条件下( 例如完成时间、预算等) 获取尽可能多又好的资源来满足 自己的需求并且又不需要花费更多的经济代价。所以在网格资源调度中，资源 买方和资源卖方通过市场交易来获得各自的利益，各取所需。因此通过类比实 际生活中的某些经济行为，研究各种经济模型的运行机制，然后结合网格资源 分配和任务调度的特点进行一定的选择，就可以找出适合的、高效的经济模型 以便应用到网格资源调度【9 】中去。 网格是一个异构的、动态的分布式环境，资源的使用和资源的供应都是在 不断地变化之中，通过引入经济学，特别是基于价格的市场机制进行网格资源 管理有如下优点【胁1 4 】： ( 1 ) 通过引入和研究经济模型，能够最终通过市场供需平衡来调节资源的优 化配置，这是引入经济模型最大的优点。 ( 2 ) 早先的网格研究大多数都是为了学术研究而开发的，这些系统中只考虑 了资源如何是协调工作的，而没有考虑最重要的问题还是资源的价格因素。因 为大部分资源都不是免费使用的，加入经济代价，能保障双方各自的利益。 ( 3 ) 网格系统是一个动态的、异构的分布式环境，用户和资源加入、退出网 格系统都是不断变化的。通过经济学原理中的市场价格机制，有利于调节网格 资源的供需平衡。当供不应求的时候，通过提高资源价格，可以减少资源买方， 增加资源卖方：当供过于求的时候，通过降低资源价格，可以增加资源买方，减 少资源卖方，达到短暂的供需平衡，通过价格杠杆调节资源的分配。这样就能 够很好的反映出网格的动态性。 ( 4 ) 提供了一种经济激励，根据优先级的高低来决定先后顺序，例如时间紧 4 1 绪论 迫的任务就可以优先执行，便于提供o o s 服务。 ( 5 ) 利用现成的微观经济模型来解决网格资源调度问题，经济策略关系到每 个资源买方和资源卖方的利益，所以经济模型应用到网格资源调度中有很好的 意义，强调了市场优先、经济优先。根据市场的供求关系来分配资源，保证了 买卖双方的最大利益的获得。 1 5 本文主要研究内容 为了使网格资源调度高效有序的进行，本文采用第三方代理组合双拍卖模 型来进行资源的调度，本文的主要工作是在进入第三方代理组合双拍卖流程前， 利用改进的粒子群算法选取出优秀的买卖双方，也就是竞胜标参与拍卖，从而 使整个市场的收益最大化。如何拍卖和交易的过程不是本文研究的重点。 所谓市场收益最大化就是指网格市场中的买卖双方都能得到各自利益的最 大化，资源买方能够以较少的经济代价获取满足自己需要的各种资源，资源卖 方能够获得更多的经济利益并且使自己的资源得到充分利用。当用经济杠杆进 行衡量时，按常理来说，资源买方希望购买资源出的钱越低就越满意，而资源 卖方希望出售资源的价格越高就越满意，但是往往因为买方出价过低或者卖方 出价过高而最终达不成交易。为了使交易顺利进行，买方就要在自己能力范围 内提高价格，而卖方在自己的成本之上降低价格。假设资源买方对需要购买资 源组合的出价设为正数，资源卖方对自己要出售资源组合的标价设为负数，并 且限定条件市场中资源是供不小于求的。利用改进的粒子群算法选取组合双拍 卖竞胜标，其中竞胜标包括买卖双方，粒子群的一个解也就是代表组合双拍卖 竞胜标的一个解。适应度函数就是中标的买卖双方各自期望价格的总和，总和 越大则适应度函数就越大，表明市场的收益越大，则市场中交易成功的几率就 越高。 该算法通过在粒子群算法中引入遗传算法，借鉴了遗传算法中交叉、变异 和选择等遗传算子的思想，对粒子群中的粒子与其个体最优粒子和全局最优粒 子进行相应操纵，来获得新粒子，有效克服粒子群算法容易陷入局部最优值这 一固有缺陷，重新在搜索空间寻找全局最优值。同时在改进的粒子群算法里引 入信任的概念，来选取信任值高的卖家和买家参与组合拍卖和市场交易，改进 的粒子群算法的适应度函数是整个市场中选中的竞胜标出价和标价累加，结果 5 1 绪论 数越大表明市场的收益越大。确定了竞胜标以后才能进入真正的市场进行拍卖， 这样可以防止恶意节点参与竞拍，较大程度的排除了由于执行信任值低的任务 或资源，使整个网络陷入紊乱和瘫痪的可能，进而可以提高网格资源调度的成 功率，优化整个网格系统的整体性能。 1 6 本文的主要工作 本文的主要工作如下： ( 1 ) 通过分析几种信任值模型的优缺点，得到一种改进的信任值模型，在改 进的粒子群算法里引入信任值的概念，来选取信任值高的卖家和买家参与组合 拍卖和市场交易，防止恶意卖家或买家参与竞拍。 ( 2 ) 针对传统粒子群算法过早收敛的不足，设计出一种融合粒子群优化算法 和遗传算法的新型算法，来解决组合双拍卖竞胜标问题。 ( 3 ) 在g r i d s i m 网格仿真环境中，本文改进的粒子群算法分别与改进的遗传 算法、离散粒子群算法求解竟胜标产生市场总收益进行比较，并且对第三方代 理组合双拍卖经济网格模型进行模拟分析。 1 7 本文的组织结构 本文分六章，每章内容安排如下： 第1 章介绍了课题来源背景，网格的概念、特点以及网格资源调度的特点、 目标及分类，并介绍了论文的主要工作。 第2 章介绍了基于经济理论的网格资源管理模型的研究现状及几种基本的 经济模型，介绍了第三方代理组合双向拍卖模型。 第3 章通过分析几种信任模型的优缺点，得到一种改进信任值模型框架， 并引入到改进的粒子群算法中。 第4 章根据传统粒子群算法过早收敛的缺陷，设计出一种融合粒子群优化 算法和遗传算法的新型算法，来求解组合双拍卖竞胜标问题，并详细给出了其 改进的思想与策略以及实现的原理与过程。 第5 章通过第三方代理组合双拍卖模型来展示出组合双向拍卖模型在经济 网格中的实际应用，在选取参与组合双向拍卖竞胜标时采用了加入信任值的改 进粒子群算法，最后在g r i d s i m 网格仿真环境中进行模拟实验，并且比较了本 6 1 绪论 文改进的粒子群算法与改进遗传算法、离散粒子群算法求解竞胜标产生的市场 总收益的结果，并对最实验结果进行分析。 第6 章是对论文工作的总结以及对未来工作的展望。 7 2 基于经济模型的网格资源调度分析 2 基于经济模型的网格资源调度分析 经济学的方法成功地管理了当前人类经济生活中存在的分布性和异构性问 题。经济模型增强了网格的社会结构，保证了它的稳定性和效率。网格计算引 入经济学理论和模型后得到了快速的发展，许多国家和机构都对网格经济产生 浓厚的兴趣，并投入了大量的资金和精力。目前的一些研究项目对于在网格中 使用经济学原理进行资源管理进行了一些探讨。 2 1 基于经济理论的网格资源管理模型 2 1 1g e s a g e s a l l 5 】( 网格经济学服务框架，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 ) 是g l o b a lg r i df o r u m ( g c f ) 的一个工作组计划，目标是在g g f 提供的开放网格 服务架构之上制定关于网格经济学服务架构的一些规范和标准。其中几个关键 项目包括【1 6 1 ：网格经济学服务接口、可交易网格服务和网格银行服务。由于目前 缺乏相关文献，各项工作处于起步阶段。 2 1 2g - c o m m e r c e g c o m m e r c e 是美国田纳西大学的研究项目，利用市场经济学原理在网格 中进行动态资源分配。它是澳大利亚m o n a s h 大学的b u y y a 根据早期市场机制 在分布式系统中的研究成果，由此提出了一种网格资源管理框架。在网格中包 含多种资源，每种资源的价格g c o m m e r c e 根据经济学中的一般均衡理论，利 用每个用户对不同资源的需求，以及网格资源提供商对资源的供给，来计算网 格市场中全部资源的均衡价格。但是g c o m m e r c e 只是给出了模拟结果，并没 有具体实现。 2 1 3g r a c e 澳大利亚m o n a s h 大学的b u y y a 利用早期对市场机制在分布式系统中的应 用研究成果，在 1 7 1 9 中深入探讨了网格环境中的基于经济学的资源管理和调 度问题，并基于一系列应用组件构造了一个网格经济学框架g r a c e ( g r i d 8 2 基于经济模型的网格资源调度分析 a r c h i t e c t u r eo f c o m p u t a t i o n a le c o n o m y ) 1 。7 】【2 1 1 g r a c e 主要用在在网格环境下资源之间的相互交易，是一个分布式的经 济学交易框架，是基于多种经济模型的。由于目前的一些网格系统如g l o b u s ， l e g i o n 等已经提供了大量的、成熟的、可重用的中间件，所以g r a c e 并没有 重新搭建一个网格平台，而是在g l o b u s 之上进行了扩展，补充了一些负责资源 交易的中间件，例如网格市场目录g m d 、网格交易服务器g t s 和用于电子支 付的g b a n k 等等。 2 1 4nim r o d - g n i i l l r o d g 【2 u j 是由澳大利亚m o n a s h 大学的r a j k u m e r 领导的网格经济研究项 目，是计算经济模型的典型代表。采用了计算经济模型对网格资源进行管理， 并且对任务进行调度。其使用基于经济学原理的资源管理方法和调度策略，还 支持用户定义的最终期限以及确保进度最优化的预算。 n i m r o d - g 中使用网格银行，它是管理资源和网格用户账户以及电子付款的 基础设施。基于对市场体制在分布式网格环境下的应用，为了合理地配置资源， 调节资源的供给和需求，n i m r o d g 利用g r a c e t 2 1 】【2 2 1 ( g r i da r c h i t e c t u r ef o r c 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 是层次型的计算市场模型资源管理，它利用网格中间件 g l o b u s 或l e g i o n 提供的服务来发现资源，同时使用他们的网络目录和数据组 织模型。n i m r o d g 支持资源预留，通过g r a c e 体系支撑的网格计算经济服务支 持q o s 。n i m r o d g 支持用户设定资源使用时长，支持在调度优化时考虑预算约 束，使用资源贸易服务来管理网格资源的供求。 2 2 经济模型中的两个重要角色 基于经济的网格中两个关键角色是资源买方和资源卖方。作为网格中的一 个组成部分，它们都有自己的要求和策略。 1 资源买方，也就是用户。资源买方的策略基本思想是：在一定时间范围 内，尽量用最少的经济代价来换取足够的资源满足任务的需要。 2 资源卖方，也就是资源。资源卖方策略的基本思想是：为了吸引顾客( 资 源买方) ，它们将提供具有竞争性服务入口，从而使它拥有的资源得到最大程度 9 2 基于经济模型的网格资源调度分析 的使用和获得最大的经济利益。 2 3 几种基本经济模型 在网格市场，服务提供者( 资源) 和资源使用者( 用户) 各有他们自己的q o s 和期望，并且可以在市场环境里初始化一个资源交易或参加一个协商。反映在 微观经济学理论中，不同的应用环境下有与之适应的不同的经济模型一般存在 以下几种相互关系【2 3 2 5 】： 2 3 1 商品市场模型 商品市场模型是网格中常用的经济模型之一。在该模型中，资源或服务的 价格由卖方来指定，并且卖方对买方按照使用资源的总量进行计价收费，这些 资源包括c p u 、内存、硬盘和网络等。卖方有自己的定价策略可以给资源固定 一个价格，也可以参考多种因素制定价格，或者根据资源的供求关系的变化而 变化。在市场交易前，资源提供者必须在网格市场目录上发布其资源信息。 该经济模型中，网格资源代理的主要任务如下： ( 1 ) 识别最能适合用户要求的资源，并且能够获得资源的主要代价。 ( 2 ) 识别出资源提供者。 ( 3 ) 借鉴以往经验并使用启发式算法为用户任务选择最优资源，这些资源必 须满足用户任务提出的q o s 或者特殊要求，最后把资源调度到这些任务上去执 行。 ( 4 ) 当网格资源完成用户任务，网格用户按照事先协商好的价格付费。 2 3 2 标价模型 标价模型与商品模型相似，在标价模型中，卖方一方面可以通过做广告或 降价等手段吸引买方，为了招揽买方，卖方会提出一些优惠价格和享受优惠的 条件，例如在节假日期间，资源的需求可能减少，而网格卖方能够广播或张贴 优惠的标价来吸引买方以提高资源利用率，所以这些特价资源往往是在资源空 闲或节假日提供，因此使用是有条件的。另一方面也能在资源使用低峰的时侯 提高资源的利用率。买卖双买按照广播出来的价格进行交易，不再需要相互协 商价格。网格资源买卖双方商价议价，是按照标价来进行交易的。 标价模型的资源活动的基本过程如下： 1 0 2 基于经济模型的网格资源调度分析 1 、资源卖方通过资源市场目录公布他们的对网格资源的要求和标价； 2 、资源买方通过查看网格资源市场目录，查找出能够使用的并符合要求的 资源； 3 、如果存在能满足任务要求的资源，开始请求使用： 4 、进行任务到资源的映射； 5 、使用资源，结束后按照协议进行支付费用。 2 3 3 仪价模型 在以上两个模型中，都是资源卖方制定价格，资源买方按照资源卖方制定 的价格来支付费用。而在议价模型中，买卖双方都有自己的代理，议价的双方 是各自的代理。网格资源买方代理和网格资源卖方可以共同商议资源的价格， 买方代理为了获得更低的价格和更长的使用时间，可以与卖方代理进行讨价还 价。买方代理和卖方代理都有自己的目标函数，如果他们的目标一致，就可以 互相协商。 在交易过程中，买方可能通过商议价格用更低的价格获得性能更高的资源。 但是如果议价过程不成功，买方代理和卖方代理不能取得一致的价格，议价过 程就没有取得任何的效益，而且也消耗了系统的资源。所以该模型可能导致资 源的利用率较低。因此，该模型适用于任务时间要求非常宽松，具备一个较长 时间的讨价还价过程，以追求较低的价格。 2 3 4 投标合同模型 投标合同模型【2 6 】是在分布式环境中协商问题使用得最广泛的模型之一。它 模拟商业上常用的制定合同的机制来控制资源的交换，帮助寻找最适合任务执 行的资源。资源买卖双方的代理在这里充当了经理人的角色，而资源卖方则叫 做投标者。这种一对多的方式使得可以根据要执行的资源买方找到最合适的资 源卖方。 从资源卖方的角度来看，投标的过程是： ( 1 ) 从网格市场目录那里接收投标广告； ( 2 ) 评估自身能力以及是否满意该合同； ( 3 ) ! t h 果符合需要，则回应投标； ( 4 ) j t h 果投标被接受，则交付服务； 2 基于经济模型的网格资源调度分析 ( 5 ) 任务完成后返回结果给资源卖方并对资源买方收取费用。 投标模型存在一定的缺陷，任务可能会被分配到一个相对能力较弱的资源 上，因为在投标时相对能力较强的资源可能处于忙碌状态。当投标过程结束后， 网格资源买方只会通知中标的资源，然后将任务分配给该资源，而不会通知其 他未中标而参与投标的资源卖方，因而将可能会造成其它资源的等待，降低资 源利用率。 2 3 5 拍卖模型 ( 1 ) 组合拍卖模型 组合拍卖是拍卖的一种，于1 9 8 2 年提出，与传统的拍卖方式相比，组合拍 卖在分配多种商品时效率更高。由资源买方写下多种商品的组合与对该组合所 出的价格，或由资源买方对资源卖方提供的组合出价。这种拍卖方式比单一物 品拍卖更有效地提高组合物品的价值。 ( 2 ) 双向拍卖模型 双向拍卖市场指资源卖方和资源买方在市场中交易资源时，资源买方可以 出某一买价寻求购买某一资源，资源卖方可以出某一卖价寻求出售某一资源。 在双向拍卖模型中，资源买方和资源卖方都是多个，资源买方订购和资源卖方 出售在交易期间可以在任何时候被提交。如果在某一时刻，公开的投标价和要 价相匹配或者在价格和需求方面一致，那么交易就立即执行。 ( 3 ) 组合双向拍卖模型 组合双向拍卖作为组合拍卖和双向拍卖的结合，是资源买方和资源卖方双 方将多种资源按照不同种类与数量组合成一个标的进行双方报价拍卖的交易形 式。与其他拍卖交易机制相比，组合双向拍卖不仅能通过双方竞价解决单边拍 卖中的垄断问题，而且能通过资源组合显著地降低交易次数与交易成本，提高 效率，并且满足了生产和生活消费日益多样性的需要，因而在现实生活中具有 广阔的应用前景。 2 4 第三方代理组合双向拍卖模型 在网格环境中组合双向拍卖剐分为分布式方式和第三方代理方式，分布式 方式假设网格中竞价信息对资源买方完全透明，故而取消对第三方代理的依赖， 1 2 2 基于经济模型的网格资源调度分析 把其实现的功能交与资源买方本身来判断处理；第三方代理方式假设网格中竞 价信息对资源买方不透明，从而利用第三方代理来进行计费和资源分配等处理。 本文采用第三方代理方式进行双向组合拍卖。为了使得整个市场的收益最 大化，在正式进入第三方代理双向组合拍卖流程前，首先对买卖双方进行筛选， 选取能够使整个市场收益最大的资源买方和资源卖方进入到拍卖市场中参与竞 拍。本文通过引入一种改进的粒子群算法来确定最优竞胜标，从而达到使得整 个市场的效益最大化的目的。改进的粒子群算法求解最优竞胜标问题将在第四 章详细介绍。 原来由资源买方处理搜索、分配定价等功能现在由第三方代理完成，从而 降低资源买方一方模块复杂度。另一方面由于第三方代理模式是全部任务分配 给资源完成后再通知资源买方同时提交任务给资源执行，所以第三方代理模式 的资源利用率较高，在总的时间花费上也会较少，适于