第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≤口<r (5) 1.1调度模型 那么，定义此时消费者y的价格P,为网格资源的价格。 假设网格中存在N个非合作的消费者，他们竞 对于定义2中，资源申请数量的另外2种情况： 价使用网格资源，这些网格用户需要购买网格资源 ①当4，≤Q时，即现有的网格状况可以满足所有 才能完成作业（一个类型各异的任务序列）.作业由 的资源请求，此时资源的价格P,=0.②当q1>Q时， 一个任务序列构成，作业的执行时间为所有任务的 出价最高消费者的资源请求不能被满足，此时可以 执行时间之和 定义1资源调度非合作博弈模型为一个三元 以≤Q<开始定价，如果>Q也成立，依 组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:,这样 息收集模块.其中，信息收集模块收集资源的信息，包 就可以求得消费者的本次竞价. 括：资源信息（如资源价格、分配指令等）和其他消费者