第5卷第2期 智能系统学报 Vol.5 No.2 2010年4月 CAAI Transactions on Intelligent Systems Apr.2010 doi:10.3969/i.isgn.1673-4785.2010.02.011 MAS动态协作任务求解模型与算法 蒋伟进12，骆菲2，史德嘉 (1.湖南商学院计算机应用研究所，湖南长沙410205；2.湘潭大学信息工程学院，湖南湘潭4110006) 摘要：针对网格环境的自治性、动态性、分布性和异构性等特征.提出基于多智能体系统(mutil agent system,MAS)博奔 协作的资源动态分配和任务调度模型，建立了能够反映供求关系的网格资源调度动态任务求解算法，证明了资源分配博弈 中Nash均衡点的存在性、惟一性和Nah均衡解.该方法能够利用消费者Agent的学习和协商能力，引入消费者的心理行 为，使消费者的资源申请和任务调度具有较高的合理性和有效性.实验结果表明，该方法在响应时间的平滑性、吞吐率及任 务求解效率方面比传统算法要好，从而使得整个资源供需合理、满足用户QS要求 关键词：资源优化调度；动态协作；博弈计算；MAS 中图分类号：TP393;TP311文献标识码：A文章编号：1673-4785(2010)020161-08 Modeling and solving dynamic collaborative tasks in a multi-Agent system JIANG Wei-jin2,LUO Fei',SHI De-jia (1.School of Computer,Hunan University of Commerce,Changsha 410205,China;2.School of Information Engineering,Xiangtan U- niversity,Xiangtan 411006,China) Abstract:A grid environment is characterized by its autonomy,its dynamic properties,its distributive properties, and its heterogeneity.We proposed a model for dynamic resource distribution and task scheduling based on a multi- agent system(MAS)collaborative game.An algorithm for dynamically solving task scheduling of grid resources was developed.It reflected actual relationships between supply and demand.The existence and uniqueness of a Nash e- quilibrium point in the resource distribution game was proven,and then the Nash equilibrium solution presented. The proposed method can make full use of the learning and negotiating abilities of consumer agents and also intro- duces psychologically driven behavior.In this way the resource application and task scheduling of consumers be- came more reasonable and effective.Experimental results demonstrated that this approach improves smoothness, throughput capacity and task solving efficiency compared to traditional methods.Supply and demand became more manageable,meeting the requirements of quality of service (QoS). Keywords:resource allocation model;dynamic collaboation;game compute;multi-Agent system (MAS) 随着网格技术的飞速发展，网格计算已成为解境下的调度要复杂得多2].虽然随着网格技术的发 决大规模复杂的问题的有效手段.高效的资源调度展以及资源服务化，出现了基于服务的网格标 策略可以充分利用网格系统的处理能力)，从而提 准2]，这在某种程度上统一了资源的呈现方式，简 高网格应用程序的性能，以便更好地利用网格资源. 化了任务调度的接口，但网格环境中资源的自治性 然而要实现高效的网格计算需要处理许多复杂的问 和动态性依然存在.而且，在实际应用中，大量的资 题，其中，资源调度问题是网格研究中所必须解决的 源并不是无偿使用的，要吸引资源的拥有者加入网 一个关键问题.由于网格环境中资源的多样性、自治 格，就必须保证其利益.面对不断变化的资源供求关 性和动态性，使得网格环境下的资源调度比传统环 系，网格资源的价格因素也变得尤为重要「3.因此， 收稿日期：2009-1220. 如何在一个异构、动态、自治的分布式计算环境中支 基金项目：湖南省自然科学基金重点资助项目(06J2033):湖南省社 会科学基金资助项目(07YBB239). 持动态资源的共享和协同，已成为亟待解决的问题。 通信作者：蒋伟进.E-mail:ilwxjh@163.com 分布式系统上的资源调度就是为系统的每一个
·162 智能系统学报 第5卷 计算任务分配一定的资源，并指派占用这些资源的 私行为对整个网格作业执行性能的影响，但没有考 起止时间，以尽可能早地完成任务.资源调度实际上 虑用户的自私行为：Bredin2o]研究了具有串行任务 是根据任务和资源的特性采用不同的算法将任务映 的多个网格用户竞争同一资源的博弈问题，提出了 射到相应的资源上执行的过程.围绕着网格中的资 以预算为约束的优化作业执行时间的资源分配策 源调度，国内外已做了许多研究工作，先后提出了多 略：文献[21-22]提出了基于Nash均衡的拍卖可划 种调度算法.从博弈经济学的角度出发，对供需状 分资源的优化用户费用的资源分配策略，然而，他们 态始终处于动态变化中的计算网格资源进行调度是 的分配策略都是基于历史的CPU负载信息进行用 一种良好的思维方式.文献[4]在基于经济学原理 户决策，没有考虑未来资源负载的变化，不能得到合 的资源调度实验中，由于资源价格是根据资源的重 理的资源价格，因而也就无法有效地实现资源优化 要性事先指定，因此很雅保证其资源配置分布决策 分配；文献[23]提出一种支持并行任务执行的多A- 的最优性；文献[5]提出分布调价WALRAS算法，并 gent系统，Spawn、Agent要求在给定预算的条件下完 讨论了其适用的条件：文献[6]对集中式调价算法 成计算任务，Spawn的关键是Agent如何把资金分 和分布调价WALRAS算法的性能进行了比较：文献 配到不同的子任务中，即控制并发计算；文献[24] [7]结合集中式同步调价算法速度快和分布调价 提出一个D'Agent系统，其关键是通过限制贪心用 WALRAS算法可扩展性的优点，提出一种分布分组 户的请求达到系统内部的稳定，实现用户之间资源 调价算法；Buyya和Abramson等人[8-2]讨论了各种 分配的均衡.上述研究工作主要应用经济学原理研 有代表性的基于经济网格资源管理原理，如拍卖模 究了网格资源框架结构、定价策略、交易算法等问 型、多商品交换模型、合同模型、议价模型等，提出了 题，没有涉及网格资源性质分析及相关市场模型的 一种基于经济理论的以服务为中心、可扩展的网格 研究，尤其这些调度方法都没有足够地考虑消费者 体系结构(grid architecture for computational econo- 被动地得到资源分配（这种调度通常通过集中式计 my,GRACE),并给出了基于现有网格技术的实现方 算而实现)，而且在竞争使用有限的网格资源过程 法，介绍了资源调度的物品交易模型和拍卖模型，以 中，消费者不合理的背离行为使得资源调度问题的 及物品经济模型在计算网格和数据网格的资源管理 研究更为复杂 和调度中的应用；文献[13]应用微观经济学理论提 Agent技术是近年发展起来的分布式人工智能 出了一种基于日用品市场的网格资源定价算法，使 的最新的前沿研究成果，具有自主性、反应性、社会 供求曲线快速收敛，很快达到均衡价格；文献[14] 性和自适应性等诸多特点，为大规模复杂任务求解 以一般均衡理论为基础，依靠市场机制，提出了一种 提供了一种新的途径256.博弈计算方法是资源配 基于市场机制的资源调度方法，实现的计算网格资 置任务求解的有效方法之一，是解决多个自利个体 源的优化调度是一种分布式资源调价方法；Wols 间资源调度问题的有效机制.同时，市场博弈理论也 k「5]从计算经济的角度研究网格资源的分配问题， 为多Agent系统(MAS)动态协作问题的研究提供了 研究了商品市场模型和拍卖模型的资源分配效率； 坚实的数学基础.多Agent技术与演化博弈理论的 Chun等人[i6]采用拍卖一投标(auction-biding)模 有机结合，可为复杂网格计算资源的动态调度开启 型，其目标是在资源交换的市场竞争中买卖资源，匹 一种新的理念和思路.本文运用MAS市场博弈机制 配请求的资源和可用的资源，最大化资源的聚合效 规范消费者在资源调度中的贪婪行为，并以Nash均 用；Feldman等人[]假定消费者预先描述了对资源 衡理论为基础，建立一种分布式的资源优化调度机 的偏好，采用最佳响应(best response)算法获取更多 制和任务求解方法，在该机制下，消费者的资源申请 的效用；Abramson[8]给出了一个网格资源代理，利 和调度具有较高的合理性和有效性 用经济模型动态选择资源.但是，这些方法在很多情 1MAS博奔协作任务求解模型 况下是理想化的，因为只考虑了资源和用户之间的 关系，没有考虑用户和用户之间的相互影响.这样确 在动态开放的计算网格环境中，理性的Agent 定的资源均衡价格即使能达到帕累托(Pareto)最 代表了用户的意志，其目标是使自身利益最大化.网 优，也难以满足实际网格环境的需要.Kwok[9提出 格资源的提供与使用通过市场买卖的方式来实现， 了一个层次化网格的博弈论模型，考虑了资源的自 市场参与者分为2种角色：任务代理（资源买方）和
第2期 蒋伟进，等：MAS动态协作任务求解模型与算法 ·163· 资源代理（资源卖方），双方的目的是最大化各自收 基于相应约束的Nash均衡点求解，即满足 益.在计算网格框架中，构建了2类Agent:资源提供 U(s,s)≥U(s,s) (4) 者Agent(资源Agent)负责管理网格资源，网格资源 式中：s∈S,s=(s,…,s1,s,…,sm),i=1, 的拥有者通过此Agent给资源定价及进行资源调 …, 度；消费者Agent(任务Agent)负责管理用户的计算 定义2设消费者的竞价集合为S={s:|s:= 任务，网格用户（消费者）通过此Agent将所需完成 (p,9:),i=1,…,N},其中，P:为消费者i愿意为使 的任务分配到合适的资源上.2类Agent通过交互协 用资源而出的资源单价，9：为消费者i要使用的资 商资源价格及相应资源量，根据资源市场的供需情 源数量，且消费者的竞价满足P1≥P2≥…≥Pw,假设 况调整价格，最后达到供需平衡的资源分配.这种分 消费者的报价集合中，申请的网格资源数量满足： 配是在满足用户QS的基础上，最大化全体用户的 效用和，即满意度，且保持全局负载均衡 g≤口Q时， 一个任务序列构成，作业的执行时间为所有任务的 出价最高消费者的资源请求不能被满足，此时可以 执行时间之和 定义1资源调度非合作博弈模型为一个三元 以≤QQ也成立，依 组G=(N,S,S),其中： 次类推，调度资源给满足定义2条件的消费者 1)N为非合作的消费者（任务Agent)集，记为 定义3定义1的模型中有N个网格消费者竞 N={Ji,J2,…,Jn},消费者（任务Agent)J:包含JN: 争一个有限的计算资源，假设有K个类型的资源， 个子任务（序列），记O,为任务Agent J:的第j个子 每个用户在一个特定类型的资源上只能完成一个任 任务，则J={0,1,0,2,…,0, 务，定义如下参数： 2)S:为消费者（任务Agent)J,的竞价可选资 {9}=1:网格消费者的任务序列，任务必须按 源集，同时设面向任务Agent集N的所有可选资源 顺序执行（即任务之间有数据依赖），其中是第i 的集合为M,则M={f,方，…，fn,共m个资源，故 个网格用户的第k个类型任务的大小 可得出：SCM,从而有M=S=S1×S2×…×Sn c:第i个网格消费者为了完成k类型任务而选 3)U:为Agent J:的收益函数，在给出收益函数 择资源的能力. 的表达式前，给出如下定义：①设pt(f)为任务 :第i个网格消费者为使用k类型资源每秒的 Agent J:的子任务O,使用资源f的时间，这里f∈ 出价： S.②设tt,(东f-i)为任务Agent J:在2个资源间 A:网格消费者集合. 的传输时间.③设st,(f)为任务Agent J:的子任 B:类型斥的网格资源从A,中接收的总的消费 务O占用资源f众的开始时间， 者出价。 基于以上定义，可得出Agent J:的收益函数U: B::除第个消费者以外所有网格消费者对第 U,(s）=)+p4) (1) k个类型资源的出价集合，即B:=∑jewn:从： 因为第i个网格消费者分到的资源数量与整个 式中：s=(s1,…,s,…,sn),:∈S,并受如下约束： 资源的比例等于它的出价相对于所有消费者出价的 st（f)-ttff-)≥st-(f-1）+pt-1(f-i）, 比例，所以，第i个网格消费者分到的资源数量是 (2) (6) st(f)≥st,y(f), (3) \B: 式中：i,x=1,2,…,n;j=1,2,…,JW；y=1,2,…, 假定网格消费者具有各种资源价格状态的完美 JN,. 信息，即B。已知.既然不依赖于B。,（B+b) 根据上述非合作博弈模型，资源调度问题即为 可以替代B:,那么，第个网格消费者为完成k类型
·164 智能系统学报 第5卷 任务所需的时间就是 用为0.为了使出价为P:的消费者能衡量因为其竞 车、生 =9(+B) 价达不到资源价格而导致申请不到资源的风险，对 (7) Cibe 此取T:=e,来衡量竞价风险，即出价为P:的消费 且费用是 者，不能获得资源使用的概率，所以(1-)代表消 =·=9i(+B) (8) 费者在出价P:时能够竞得资源使用的概率，这样定 c 义4定义的消费者i的效用函数为 1.2模型分析 U.(S)△U,(S,S)=(1-e)·q(Q-q:). 从上面的定价机制知道网格系统的资源申请可 (10) 以得到满足，消费者可以通过提高竞价获得资源的 式中：U,(S)是一个值域为[0，∞)的连续单调增函 使用.消费者对这个资源的使用都有一定支付能力 数，且二阶连续可微，U:(·)=0.同时，U”:(·)> m:和最低数量要求q:,因此消费者所承受的最高资 0,即U:(S)是连续递增单调函数， 源价格为P:ms=m:m/q:,高于这个价格消费者将 下面，根据式(10)的效用函数来讨论资源调度 无法承担使用该资源的支付. 博弈中Nash均衡点的定义、存在性和惟一性， 资源的价格不是由单一消费者的出价决定，而 定义5如果在非合作资源调度博弈中，U:(s:, 是由多个消费者竞价决定（博弈决定），因而需要围 s-)为消费者i的效用函数，那么(s1,…,s,… 绕以下问题研究资源调度的博弈模型：按照博弈理 sw)构成一个Nash均衡点，当且仅当Hi∈N,Hs:∈ 论公平定价；资源的价格不会被恶性竞争抬的过高 S,U(s,s)≤U(s,s),其中，S为消费者i 或过低；资源的价格能恰当地反映大多数参与竞价 所有竞价向量的空间。 消费者的理性需求.。 由上可知，系统达到Nash均衡点，系统的任何 在资源调度博弈中，消费者也是以自己效用最 偏离Nash均衡点的竞价向量S',其效用将不大于 大为目标进行竞价的，此外，消费者的资源占用对其 在S*(s,…,sN)时的效用.而且Nash均衡点的充 他消费者效用的潜在影响也是需要考虑的问题.例 要条件表明按照资源调度向量s:对资源竞价是消 如，用户传输数据对其他用户传输产生的“外部效 费者的占优策略，同时，也说明了资源调度博弈中 用”，因此下面研究依据消费者效用最大的竞价标 求解Nash均衡点的方法为消费者选择s:,使得其效 准，在资源调度中，消费者的效用函数应由2部分组 成：1)消费者使用该资源而获得的收入，这部分主 用最大，即maxU,(s,si). e8i 要涉及消费者获得的资源数量和剩余的资源数量； 因为消费者都是以maxU:(s,s)为目标竞价， 2)消费者为使用资源而必须的支出，这部分主要涉 因此消费者i在制定竞价时需要考虑2个方面的内 及资源的价格和消费者申请的资源数量，效用函数 容：资源价格P:和数量q·由于消费者i的最大购买 定义如下： 能力m:m都是确定的，且P:9:≤m:ms,故竞价中价 定义4在资源调度博弈中，使用CES效用函 格和数量是相互矛盾的参数， 数的变形得到消费者i的效用函数： 定理1在资源调度博弈问题中，W个消费者 U(S)4U(S,S-)=(1-r)·9:(Q-9) 竞价获得资源的使用，如果消费者i的效用函数由 (9) 式(10)定义，那么整个博弈系统的Nash均衡点存 式中：S为整个系统的竞价策略向量；S:为系统i的 在且惟一 竞价向量；S-:为除系统i外，其他消费者的竞价向 证明在定理给出的条件下，消费者i制定博 量；i∈W;U:(·)为消费者i使用资源的效用；r:为 弈策略可以用如下优化问题表示： 消费者i的风险系数；q:为消费者i的资源需求量. m,(s),&tA,g≤mm（） 对消费者效用函数的分析如下：9：(Q-9:)为系 对于上述非线性优化问题，可以构造如下的拉 统使用数量为9：资源的效用；(1-T:)为竞得概率， 格郎日函数： 「：为不能竞得资源的风险系数.如果竞价小于P(本 次竞价后，资源的价格)，消费者将无法负担使用该 L(s)=U)-w(p:-m). 资源的支付，不能获得对资源的使用，此时消费者效 (12)
第2期 蒋伟进，等：MAS动态协作任务求解模型与算法 ·165 式(12)的K-T条件为 信息（如出价信息和申请资源的数量等）；网格分析模 0L:(·)/p:=aU:(·)/p:-oq:=0, 块提取分析收集来的信息，根据资源价格判断资源的 aL,(-)/q:=aU(·)/g:-p:=0,(13) 使用状况和其他消费者对资源的需求情况，解析并保 (gPa,-ma）=0,w≤0， 存资源的价格：计算竞价模块根据当前的资源信息计 算竞价，按照资源分配算法，向资源提供者提交竞价 记7：(S)=U:(·)/p:,同时结合式(11)，则K-T 资源提供者主要包括：资源定价模块和资源分 条件式(13)可以化为：如果P:·9:≤m,那么 配模块.其中，资源定价模块按照定义2计算资源的 w=7:(S)/g:如果P:·9:>m,那么0=0. 价格，并广播资源价格；资源分析模块判断哪些消费 另外，由于aU(·)/p>0,a2U(·)/aq<0 者可以获得资源的使用，分配相当数量的资源.此 那么效用函数U,(·)在s:=pq:处的Hessian矩阵 外，资源分配模块将周期性地收回资源，并广播分配 为 指令，开始新一轮竞价过程. 「a2U,() a2U(·)1 图1反映了消费者Agent的3个状态：S(稳定 状态)、B(竞价状态)和A(网格分析状态).初始情 7()= p 8p:0q: (14) a2U(） a2,() 况下，消费者的状态为S,消费者Agent将以某个初 0g:0p: aqi 始策略行动，同时周期性地向网格其他消费者A- 显然，|7(·)<0，即7(·)为负定矩阵， gent发布本系统的竞价信息（即使没有进行策略调 所以效用函数U,(·)是凹函数，式(11)所述的优化 整也需要定时发布本系统的决策信息，以便让新加 问题有惟一的极大值，即博弈的Nash均衡点存在且 入的消费者能够及时地了解各消费者的当前状 惟一，证毕。 态)；当收集到其他消费者Agent的状态信息和网格 下面，通过研究Nash均衡点上竞价，讨论消费 状态信息时，消费者将根据这些信息判断网格运行 的情况，此时进入状态A;在分析后，如无拥塞发生， 者的竞价方法. 定理2在上述资源调度博弈的Nash均衡点， 消费者Agent将记录这些信息以供竞价使用，同时 返回到状态S;当到达某一时刻（该时刻周期性地发 消费者i竞价应在p:q:=m:m=时取得 证明假设在式(11)描述的优化问题中，当 生或诊测到网格拥塞时发生)，消费者将根据收集 P:9:≤mm时U(·)取得最大值，那么有w=0,将 到的其他消费者的信息（各消费者的竞价信息）和 网格状况进行动态地竞价，此时消费者进入状态B; 0代入式(13)，可得： 新的竞价生成后，消费者Agent的状态将回到S,消 ①aU(·)/p:=0,需有P:=0或Q-9:=0; ②8U:(·)/g:=0,需有p:=0或Q-2g:=0; 费者将以新生成的行动工作3] 在基于市场博弈机制的资源分配任务求解算法 将：=0代入式(10)可得U,(·)=0,故P:≠ 中，消费者的核心模块为竞价计算模块.根据定理 0;另外，条件Q-9:=0与Q-24:=0矛盾，所以 2,可以计算消费者在Nash均衡点的竞价，将4：= P9:<m:ma不能取得最大值. m:mP:时，代入式(10)，可得 这样只有在P4:=mmm时，U,(·）取得最大 值，联合式(13)中的方程组，不难求出最大值点 U(-）-Le,(mmQ-m）+ Pi (p,q),即均衡点，证毕. 从上面的讨论可知，消费者的竞价高低反映了 (1-ep,)( 2m题-mQ)=0.(15) 3 PiPi 其对资源需求的迫切程度，而博弈使得资源的价格 式中：P,为资源的价格，这里可以使用上次竞价后 更能够反映消费者的需求和当前网格的状况， 资源的价格指导本次消费者竞价.显然，通过式 1.3算法 (15)很难求出P:的解析解，但是可以求P:在 资源调度任务求解算法实际上就是一个竞价博 [m:ma/Q,m:ms/q:]范围内的近似解（本文将不花 弈的过程， 过多篇幅介绍复杂方程的求解方法).然后，通过求 消费者的功能主要包括：计算竞价、网格分析、信 出价为P:的消费者申请资源数量的近似解q:,这样 息收集模块.其中，信息收集模块收集资源的信息，包 就可以求得消费者的本次竞价. 括：资源信息（如资源价格、分配指令等）和其他消费者
·166· 智能系统学报 第5卷 其中，Ag为协商参与者Agent i,j,它在协商中 表示生产者或消费者；A为协商双方可行行动组合； 8为协商对象类型组合；Te为协商双方的协商最终 期限；S为协商策略；Protocol为协商协议，协商时协 商参与者所遵循的协商规则 协商过程为在协商最终期限内任意Agent i在 时刻t出价，如果Agent j(i≠j)不接受则根据自身的 状态：S稳定)，B(竞价)，A(分析)事什 策略在t+1时刻还价，然后轮到i决定是否接受j 1)发布竞介信总：2)到达竞价周期：3)确定新的策略：4)记录 分析结果：5)收集竞价信息：6)分析网格状态 的还价，然后再到j决定，这样多次交替出价还价. 图1消费者状态变迁 如果j接受i的出价，则行动accept,协商结束，如果 Fig.1 Consumers state transition j选择退出协商，则行动qut,协商结束。 设消费者c向提供者p申请的资源量为R。个基本 在上述模式下的资源调度过程实际上是消费者 单位，预算费用为B。.设提供者p当前可用资源数量是 和提供者间的竞价博弈过程，目的是在为消费者确 P.个基本单位.在进行资源调度时，提供者首先将目前 定合适资源占用量的同时，也为提供者确定合适的 可用资源量与一预设阈值△比较如果P.≥A,则认为 售价，达到Nash均衡下的Pareto最优. 当前可用资源丰富，采用博弈模式分配资源；否则，认 2仿真分析 为当前可用资源短缺，采用竞价模式△值由提供者根 据其资源使用历史纪录确定， 为验证本文方法的有效性，将本文算法与文献 算法1消费者竞价算法。 [8]中针对日用品市场模型提出的费用优先算法进 输入：资源提供者给出的底价、消费者的最大支 行负载平衡比较，实验结果如表1.表1表明，本文 付能力、所需资源数量； 算法在负载平衡方面表现比定价算法要好，这是因 输出：最终成交价 为本文算法在每个作业协商完成后协商双方都对协 1)提供者通告消费者资源销售底价B。· 商策略进行调整.当资源利用不充分时，资源提供者 2)如果R。·B。≤B。,则消费者通告提供者“愿 调整策略在后面的协商中降低成交价格以竞争到作 接受该售价”；反之，通告提供者“不接受该售价”， 业.这样通过竞争使系统中的资源负载较平衡.而定 3)提供者在收到所有消费者响应后，计算愿意 价算法中，由于在一段时间内资源的价格是不变的， 接受当前售价的消费者数量N,如果N4>0,则提 资源代理都选择价格便宜的资源执行作业，这造成 高售价B,=B。+ε(E是提价步长)，并通告消费者 了一些资源负载过大，而另一些资源得不到利用。 资源最新售价，转2)；否则转4). 表1竞价算法和定价算法对比 4)提供者把所有已知的消费者愿接受的最高 Table 1 Comparison of loads balance between the bidding 售价B,B2,…按从高到低顺序排列为：B,B,… algorithms and the pricing algorithm 5)令i=1. 资源号12345678910 6)给接受售价B的消费者分配R。个基本单位 出价2202323141 资源(R。是该消费者申请的资源量). 定价0040505150 7)如果提供者仍有可用资源且还有待分配资 同时，还在P℃机模拟了本文算法和蛛网模型 源的已接受售价的消费者，则i=i+1,转6). 每个资源提供者可为多个用户服务，每个用户有不 8)对于刚性需求的消费者，若其需求未得到满 同的需求.用户总需求资源数量为32个标准任务， 足，则提供者与其协商；若协商失败，则其退出竞价， 图2比较了本文算法和蛛网算法的资源利用率.资 9)根据消费者资源占用量和其接受的最高售 源提供者资源数量小于32时，如果供不应求，资源 价计算其实际付费，结束， 提供者满足部分用户的需求，本文模型资源利用率 上述竞价协商模型定义如下： 高于蛛网模型；供大于求时，蛛网模型经过反复迭 M= 代，达到平衡点，满足部分用户的需求，竞价模型此 时满足所有用户的需求，资源利用率高于蛛网模型
第2期 蒋伟进，等：MAS动态协作任务求解模型与算法 ·167· 1.2 plications,2001,15(3):258281 1.0 [3]SUBRAMONIAM K,MAHESWARAN M,TOULOUSE M. 0.8 Towards a micro economic model for resource allocation in 6 grid computing system[C]//The 2002 IEEE Canadian Conf 0.4 ◆竞价 on Electrical Computer Engineering.Manitoba,Canada, 0.2 ■蛛网 2002:782-785. 0 30 [4]BUYYA R.Economic-based distributed resource manage- 资源数量 ment and scheduling for grid computing D].Melbourne, Australia:Monash University,2002. 图2资源的利用率对比 [5]CHENG J Q,WELLMAN M P.The WALRAS algorithm: Fig.2 Comparison of resource utilization convergent distributed implementation of general equilibrant 图3是蛛网模型和本文模型达到均衡价格的迭 outcomes[J].Computational Economics,1998,12 (1):1- 代次数.从图中可知，本文模型的均衡价格为6，资 24. 源的总供给为35.改变资源的初始报价，蛛网模型 [6]YGGE F.Market-oriented programming and its application 中初始报价离均衡价格越远，迭代次数越多.本文模 power load management[D].Lund,Sweeten:Lund Univer 型每次迭代根据供需差调整：供需差越大，调价幅度 sity,1998. 越大，很快达到均衡状态 [7]WENG C L,LU X D.A double auction method for resource 50 allocation on computational grids[J].Chinese Joumal of ◆蛛网 Computers,2006,43(6):1004-1009, 40 ■竞价 [8]BUYYA R,ABRAMSON D,VENUGOPAL S.The grid e- 30 conomy[J].Special Issue on Grid Computing,2005,93 (3):698-714. [9]BUYYA R,VAZHKUDAI S.Compute power market:To- 10 wards a market-oriented grid C].Washington.CCGRID 00 23 4 5 6 8 2001:574-581 报价 [10]BUYYA R,ABRAMSON D,GIDDY J.A case for econo- 图3迭代次数 my grid architecture for service-oriented grid computing Fig.3 Iterations [C]//Proc of the 10th IEEE Int'1 Heterogeneous Compu- ting Workshop.Washington:IEEE Computer Society, 3结束语 2001:776-790. [11 BUYYA R,MURSHED M.GRIDSIM:a toolkit for model- 本文提出了一种基于博弈经济机制和多Agent ing and simulation of grid resource management and sched- 动态协作的计算网格资源分配任务求解方法.它通 uling[J].Joumal of Concurrency and Computation:Prac- 过效用函数刻画用户需求的异构性，以一般均衡理 tice and Experience,2002,14(13/15):1175-1220. 论为基础，依靠市场机制实现资源的优化分配.采用 [12]ABRAMSON D,BUYYA R,GIDDY J.A computational MAS博奔经济机制进行资源调度和任务求解有着 economy for grid computing and its implementation in the 许多独特的优点，动态的资源配置提高了系统的自 nimrod-G resource broker[J].Future Generation Comput- 适应性，采用博弈经济原则能够鼓励资源拥有者贡 erSy9tems,2002,18(8):1061-1074. 献他们的空闲资源并从中获利，有助于建立大规模 [13]SUBRAMONIAM K.MAHESWARAN M,TOULOUSE M. 的网格应用系统 Towards a microeconomic model for resource allocation in grid computing system[C]//The 2002 IEEE Canadian 参考文献： Conf.on Electrical Computer Engineering.Manitoba, Canada,2002:373-391. [1]BARUAH S K,COHEN N K.Plaxton in resource allocation [14]CAO H Q,XIAO N,LU X C,et al.A market-based ap- [J].Algorithmica,1996,15(6):600-625. proach to allocate resources for computational grids[J]. [2]WOLSKI R,PLANK JS,BREVIK J,et al.Analyzing mar- Joural of Computer Research and Development,2002,39 ket-based resource allocation strategies for the computational (8):913-916 grid[J].Intemational of High Performance Computing Ap- [15]WOLSKI R,PLANK J S,BREVIK J,BRYAN T.Analy-
·168. 智能系统学报 第5卷 zing market-based resource allocation strategies for the [24]BREDIN J,KOTZ D,RUS D.Utility driven mobile Agent computational grid[J].Journal of High Performance Com- scheduling CS-TR98-331 [R].Hanover,NH:Dartmouth puting Applications,2001,15(3):258-281. College,1998:191-206 [16]CHUN B N,NG J,PARKES D C.Computational resource [25 ]ARCHER A,TARDOS E.Truthful mechanisms for one- exchanges for distributed resource allocation[R].Harvard parameter Agents C]//Proceedings of the 42nd IEEE University,2004. Symposium on Foundations of Computer Science.Lasve- [17]FELDMAN M,LAI K,ZHANG L.A price-anticipating gas,USA:IEEE Computer Society Press,2001:482-491. resource allocation mechanism for distributed shared clus- [26 ]JIANG W J,WANG P.Research on distributed solution ters[C]//Proc of the 6th ACM Conf on Electronic Com- and correspond consequence of complex system based on merce.New York:ACM Press,2005:127-136. MAS[J].Journal of Computer Research and Develop- [18]NASH J F.Non-cooperative games[J].Annals of Mathe- ment,2006,43(9）:1615-1623. matics,1951,54(2):286-295. 作者简介： [19]KWOK Y K,SONG S S,HWANG K.Selfish grid compu- 蒋伟进，男，1964年生，教授，CCF ting:game-theoretic modeling and NAS performance results 高级会员，主要研究领域为智能计算、 [C]//Proc of the IEEE Int'1 Symp on Cluster Computing Agent计算、复杂自适应系统.发表学术 and the Grid.Washington:IEEE Computer Society,2005: 论文30余篇.获省市科技奖励10项. 349-356. [20]BREDIN J,KOTZ D,RUS D,MAHESWARAN R T, IMER C,BASAR T.Computational markets to regulate mobile-agent systems[J].Autonomous Agents and Multi- 骆菲，男，1986年生，硕士研究 Agent Sys8tems,2003,6(3):235-263. 生，主要研究方向为Agent计算、智能 21]MAHESWARAN R T,BAAR T.Nash equilibrium and de- 决策与方法、复杂系统建模。 centralized negotiation in auctioning divisible resources J].Group Decision and Negotiation,2003,12(5):361- 395. [22]JIN Y,KESIDIS G.Nash equilibrium of a generic networ- king game with applications to circuit-switched networks 史德嘉，女，1963年生，教授.主要 [C]//Proc of IEEE INFOCOM.San Francisco,USA: 研究方向分布式人工智能、多主体系 IEEE Computer Society Press,2003:1242-1249. 统、智能控制.主持国家科技部、省级重 [23]WAIDSPURGER C,HOGG T.Spawn:a distributed com- 点项目2项.发表学术论文20余篇，被 putational economy[J].IEEE Trans on Softw Eng,1992 EI检紫10篇. 18(2):18-32