D0I:10.13374/1.issnl00103.2007.05.0☒ 第29卷第5期 北京科技大学学报 Vol.29 No.5 2007年5月 Journal of University of Science and Technology Beijing y2007 基于反拍卖的计算网格资源分配方法 陈冬娥2)杨扬)刘丽) 1)北京科技大学信息工程学院，北京1000832)河北经贸大学计算机中心，石家庄050091 摘要针对计算网格资源的特点和运用经济机制进行网格资源管理的优势，提出一种基于暗标反拍卖机制的网格资源分 配方法·描述了基于网格服务市场的资源分配框架：针对网格中的服务资源，提出了一种以网格用户为中心，以用户需求驱动 的暗标反拍卖网格资源分配方法，在满足网格用户QoS要求的情况下使系统的总效用最大化：分析了该拍卖机制的Bys均 衡点以及系统在均衡状态的效率、策略和效用：给出了基于用户效用函数的资源分配算法 关键词网格服务：资源分配：反拍卖：QoS;Byes均衡：效用函数 分类号TP393 经济机制作为一种灵活、有效的网格资源管理 网格用户为中心，以用户需求驱动的暗标拍卖的计 方法已经成为网格领域中的研究热点，在不同的应 算网格资源分配方法，并分析了该拍卖机制的Bayes 用领域，研究人员已经开发了用于网格资源管理的 均衡点以及系统在均衡状态的效率、策略和效用，最 不同经济模型：Spawn山是基于分布式计算的调度 后给出了基于用户效用函数的资源分配算法， 系统，采用二级密封价格拍卖机制(Vickrey拍卖)， 1 多个作业竞争一组计算机的处理时间，作业可以根 基于GSM的资源分配框架 据用户偏好制定各种竞标策略.Popcorn!②)是一个 把网格定义为由多个网格服务市场GSM(gid 基于WEB浏览器的系统，Popcorn使用Java语言实 service markets)组成的经济系统，在GSM中，把服 现，用户将分布式的应用分解成一组任务，根据计算 务定义为有价值的经济商品，将网格资源拥有者定 的价值设定每个任务的价格，并进入市场收集资源 义为网格服务提供者GSP(grid service providers), 的出售者，资源出售者出售自己机器上的CPU时 将网格资源消费者定义为网格用户，网格服务提供 间，执行用户的任务.Jaws]与Popcorn类似，也是 者和网格用户都是网格中独立的经济个体，网格服 一个基于WEB浏览器的系统；Jaws中买方与卖方 务提供者和网格用户进入和退出GSM都要通过信 提交定单到匹配器，匹配器一旦匹配到买方与卖方 息服务代理ISA(information service agent)注册登 定单，交易即可完成：定单可以随时更新，这三个系 记，在GSM中，网格用户通过应用服务代理ASB 统都使用了经济机制解决资源分配问题，但系统的 (application server broker)提交任务，并说明自己的 着重点是负载平衡，对服务质量的支持较弱，而且系 QoS要求；ASB根据服务类别将任务分类，然后注 统的结构固定，扩展性和开放性不够好，Nimrod/ 册到ISA,宣布他们要买入的服务及QoS要求，从 G[]网格资源调度器能够在计算网格中管理和调1SA中，网格用户还可以获取关于本地服务资源（与 度应用，系统采用商品市场模型管理分配资源，采用 网格用户同在一个GSM中的服务资源)的有用信 由用户定义的最终期限和预算限制所驱动的应用级 息，若用户想要获得其他GSM中的服务资源信息， 调度策略；Nimrod./G和文献[G9]的研究工作侧重 则必须通过本地ISA与其他ISA联系，以获得服务 于资源分配系统的实现，对拍卖机制本身的效率、策 资源信息列表：而网格服务提供者GSP通过资源服 略和效用未做深入研究 务代理RSA(resource service agent)注册到ISA,注 针对计算网格资源的特点，本文提出了一种以 册信息包括服务资源的名称、位置、硬件参数等，在 收稿日期：2006-10-25修回日期：2006-12-20 多个网格服务市场中，一般一个服务资源只属于一 基金项目：国家自然科学基金重大研究计划重点项目(N0· 个市场，且只在相应的GSM中的ISA进行注册，如 90412012):国家自然科学基金资助项目(N。-60673160) 果一个服务资源同时属于几个不同的GSM,则应当 作者简介：陈冬娘(1964一)，女，副教授，博士研究生：杨扬 在每个GSM中的ISA都进行注册. (1955一)，男，教授，博士生导师
基于反拍卖的计算网格资源分配方法 陈冬娥12） 杨 扬1） 刘 丽1） 1） 北京科技大学信息工程学院北京100083 2） 河北经贸大学计算机中心石家庄050091 摘 要 针对计算网格资源的特点和运用经济机制进行网格资源管理的优势提出一种基于暗标反拍卖机制的网格资源分 配方法．描述了基于网格服务市场的资源分配框架；针对网格中的服务资源提出了一种以网格用户为中心以用户需求驱动 的暗标反拍卖网格资源分配方法在满足网格用户 QoS 要求的情况下使系统的总效用最大化；分析了该拍卖机制的 Bayes 均 衡点以及系统在均衡状态的效率、策略和效用；给出了基于用户效用函数的资源分配算法． 关键词 网格服务；资源分配；反拍卖；QoS；Bayes 均衡；效用函数 分类号 TP393 收稿日期：2006-10-25 修回日期：2006-12-20 基金 项 目：国 家 自 然 科 学 基 金 重 大 研 究 计 划 重 点 项 目 （ No． 90412012）；国家自然科学基金资助项目（No．60673160） 作者 简 介：陈 冬 娥 （1964—）女副 教 授博 士 研 究 生；杨 扬 （1955—）男教授博士生导师 经济机制作为一种灵活、有效的网格资源管理 方法已经成为网格领域中的研究热点在不同的应 用领域研究人员已经开发了用于网格资源管理的 不同经济模型：Spawn ［1］ 是基于分布式计算的调度 系统采用二级密封价格拍卖机制（Vickrey 拍卖） 多个作业竞争一组计算机的处理时间作业可以根 据用户偏好制定各种竞标策略．Popcorn ［2］ 是一个 基于 WEB 浏览器的系统Popcorn 使用 Java 语言实 现用户将分布式的应用分解成一组任务根据计算 的价值设定每个任务的价格并进入市场收集资源 的出售者资源出售者出售自己机器上的 CPU 时 间执行用户的任务．Jaws ［3］与 Popcorn 类似也是 一个基于 WEB 浏览器的系统；Jaws 中买方与卖方 提交定单到匹配器匹配器一旦匹配到买方与卖方 定单交易即可完成；定单可以随时更新．这三个系 统都使用了经济机制解决资源分配问题但系统的 着重点是负载平衡对服务质量的支持较弱而且系 统的结构固定扩展性和开放性不够好．Nimrod／ G ［4—5］网格资源调度器能够在计算网格中管理和调 度应用系统采用商品市场模型管理分配资源采用 由用户定义的最终期限和预算限制所驱动的应用级 调度策略；Nimrod／G 和文献［6—9］的研究工作侧重 于资源分配系统的实现对拍卖机制本身的效率、策 略和效用未做深入研究． 针对计算网格资源的特点本文提出了一种以 网格用户为中心以用户需求驱动的暗标拍卖的计 算网格资源分配方法并分析了该拍卖机制的Bayes 均衡点以及系统在均衡状态的效率、策略和效用最 后给出了基于用户效用函数的资源分配算法． 1 基于 GSM 的资源分配框架 把网格定义为由多个网格服务市场 GSM （grid service markets）组成的经济系统．在 GSM 中把服 务定义为有价值的经济商品将网格资源拥有者定 义为网格服务提供者 GSP （grid service providers） 将网格资源消费者定义为网格用户网格服务提供 者和网格用户都是网格中独立的经济个体．网格服 务提供者和网格用户进入和退出 GSM 都要通过信 息服务代理 ISA（information service agent）注册登 记．在 GSM 中网格用户通过应用服务代理 ASB （application server broker）提交任务并说明自己的 QoS 要求；ASB 根据服务类别将任务分类然后注 册到 ISA宣布他们要买入的服务及 QoS 要求．从 ISA 中网格用户还可以获取关于本地服务资源（与 网格用户同在一个 GSM 中的服务资源）的有用信 息．若用户想要获得其他 GSM 中的服务资源信息 则必须通过本地 ISA 与其他 ISA 联系以获得服务 资源信息列表；而网格服务提供者 GSP 通过资源服 务代理 RSA（resource service agent）注册到 ISA注 册信息包括服务资源的名称、位置、硬件参数等在 多个网格服务市场中一般一个服务资源只属于一 个市场且只在相应的 GSM 中的 ISA 进行注册．如 果一个服务资源同时属于几个不同的 GSM则应当 在每个 GSM 中的 ISA 都进行注册． 第29卷 第5期 2007年 5月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．29No．5 May2007 DOI:10．13374／j．issn1001－053x．2007．05．023
第5期 陈冬娥等：基于反拍卖的计算网格资源分配方法 .549 (4)统一时间开标，标价最低者中标（拍卖成 2拍卖模型 功)，并以此中标价成交，如果出现最低标价相同的 2.1拍卖 情况，由ISA随机抽取中标者：如果出现投标方（卖 拍卖作为经济机制中的一种方式，因其能快速、 方)最低标价高于拍卖方（买方）预算，ISA则终止此 高效地解决网格资源分配问题而受到关注，拍卖是 次招标（拍卖失败）； 通过多个资源需求者以不同的价格竞争资源，最后 (5)如果不是因为ISA中止拍卖，则继续下面 由“拍卖人”依据不同的拍卖方式选定中标人并确定 的步骤，中标的RSA接受任务，执行服务； 资源成交的价格.一个拍卖其实就是一个明显的市 (6)中标的RSA向ASB返回服务结果； 场规则，它依据来自于投标方投标的基础而决定服 (T)ASB按中标成交价向该RSA支付费用 务资源的价格和分配，常用的拍卖方式有英国式拍 2.2.2拍卖模型 卖（增价拍卖）、荷兰式拍卖（减价拍卖）、第一价格密 定义1暗标拍卖是一个不完全信息静态博 封拍卖和第二价格密封拍卖(Vickrey拍卖)等4种， 弈(A,K,C,P,·其中，A={a1≤≤m},是 前两种方式也称为公开拍卖，后两种拍卖方式也称 M个服务资源代理RSA的集合；K=kg1≤g≤ 为密封拍卖].拍卖是简单且容易界定的经济环 l,是ASB任务申请的l个服务类型的集合：C= 境，一方面拍卖模型仅需要比较少的价格信息，另一 {c1≤g≤川，1≤m,是m个服务资源生产 方面拍卖模型可操作性强，相对容易实现，可使资源 成本价格的集合，c是服务资源j完成g类服务的 在短时间内被合理分配，获得系统范围内最优解或 成本价格：P=P1≤g≤l,1≤m{,是各RSA 较优解。衡量拍卖模型的优劣主要有三个标准：效 投标价的集合（投标策略空间），P如是第j个卖方对 用、策略和效率。从效用角度考虑，应保证系统总效 第g类服务需求的投标价 用最大即网格服务提供者（卖方）的效用和网格用户 卖方的投标策略就是如何选择投标价格以得到 (买方)的效用都最大；从策略角度考虑，应是最优或 最大收益，投标价格是服务类型与服务资源成本的 占优策略，应对网格中独立的经济个体的理性要求 函数，Pg=Pi(kgc):U={4|1≤g≤l,1≤≤ 尽可能低；从效率角度考虑，拍卖过程的时间复杂度 m【,是各RSA投标方效用的集合，u是投标方j完 应尽可能低或者拍卖轮次应尽可能少 成第g类服务的效用 2.2暗标拍卖 2.2.3效用分析 反拍卖是由网格用户发起的拍卖，是服务提供 定义2暗标拍卖中，卖方中标者的效用是成 者之间的一种博弈.网格用户作为买方给出自己的 交价格与其代理的服务资源的成本价格之差，未中 服务需求和Q$要求，服务提供者作为服务卖方投 标者的效用为0 标，标价最低者中标、在拍卖模型中有三个关键的 (1)当只有卖方j是一个最低标价时，卖方j 角色：卖方、拍卖人和买方，在暗标反拍卖中，各卖 中标，其效用为： 方根据买方需求密封标书投标，由拍卖人统一时间 开标，标价最低者中标，以最低价格成交，如果出现 ugi-ugi(Pgi'cgj)=min(Paj)-cgi,ugiEU (1) 最低标价相同的情况，由拍卖人随机抽取中标者， (2)当有h(1≤h≤n)个相同的最低标价时， 2.2.1拍卖规则 卖方j中标的概率就是一个最低价时的1/，其效 从拍卖的效率考虑，选择单轮次的暗标拍卖可 用为： 使资源在短时间内被合理分配，该模型中，信息服 ugi=ugj(Pai'cgi)=[min(Paj)-cgi]/h (2) 务代理ISA充当拍卖师的角色，ASB在ISA中预先 (3)卖方j没有中标时， 设置一个保留价格（用户预算），若中标价高于这个 ugiugi(Paicaj)=0 (3) 预算价就不能成交，步骤如下： 显然，卖方中标者的效用除了取决于中标价以 (1)用户提交带QoS的任务申请到应用服务代 外，还取决于服务资源的成本价 理ASB; (4)卖方的总效用为： (2)ASB根据服务类别将任务分类，然后注册 (4) 到ISA,宣布他们的服务需求，如任务大小、最终执 g=1,=1 g=1,=1 行时间、费用预算等，进行拍卖： (5)买方的效用为： (③)各RSA密封标书投标： ugi=ugi(bg'Pai)=bg Pai, (5)
2 拍卖模型 2∙1 拍卖 拍卖作为经济机制中的一种方式因其能快速、 高效地解决网格资源分配问题而受到关注．拍卖是 通过多个资源需求者以不同的价格竞争资源最后 由“拍卖人”依据不同的拍卖方式选定中标人并确定 资源成交的价格．一个拍卖其实就是一个明显的市 场规则它依据来自于投标方投标的基础而决定服 务资源的价格和分配．常用的拍卖方式有英国式拍 卖（增价拍卖）、荷兰式拍卖（减价拍卖）、第一价格密 封拍卖和第二价格密封拍卖（Vickrey 拍卖）等4种 前两种方式也称为公开拍卖后两种拍卖方式也称 为密封拍卖［10］．拍卖是简单且容易界定的经济环 境一方面拍卖模型仅需要比较少的价格信息另一 方面拍卖模型可操作性强相对容易实现可使资源 在短时间内被合理分配获得系统范围内最优解或 较优解．衡量拍卖模型的优劣主要有三个标准：效 用、策略和效率．从效用角度考虑应保证系统总效 用最大即网格服务提供者（卖方）的效用和网格用户 （买方）的效用都最大；从策略角度考虑应是最优或 占优策略应对网格中独立的经济个体的理性要求 尽可能低；从效率角度考虑拍卖过程的时间复杂度 应尽可能低或者拍卖轮次应尽可能少． 2∙2 暗标拍卖 反拍卖是由网格用户发起的拍卖是服务提供 者之间的一种博弈．网格用户作为买方给出自己的 服务需求和 QoS 要求服务提供者作为服务卖方投 标标价最低者中标．在拍卖模型中有三个关键的 角色：卖方、拍卖人和买方．在暗标反拍卖中各卖 方根据买方需求密封标书投标由拍卖人统一时间 开标标价最低者中标以最低价格成交如果出现 最低标价相同的情况由拍卖人随机抽取中标者． 2∙2∙1 拍卖规则 从拍卖的效率考虑选择单轮次的暗标拍卖可 使资源在短时间内被合理分配．该模型中信息服 务代理 ISA 充当拍卖师的角色ASB 在 ISA 中预先 设置一个保留价格（用户预算）若中标价高于这个 预算价就不能成交．步骤如下： （1） 用户提交带 QoS 的任务申请到应用服务代 理 ASB； （2） ASB 根据服务类别将任务分类然后注册 到 ISA宣布他们的服务需求如任务大小、最终执 行时间、费用预算等进行拍卖； （3） 各 RSA 密封标书投标； （4） 统一时间开标标价最低者中标（拍卖成 功）并以此中标价成交．如果出现最低标价相同的 情况由 ISA 随机抽取中标者；如果出现投标方（卖 方）最低标价高于拍卖方（买方）预算ISA 则终止此 次招标（拍卖失败）； （5） 如果不是因为 ISA 中止拍卖则继续下面 的步骤中标的 RSA 接受任务执行服务； （6） 中标的 RSA 向 ASB 返回服务结果； （7） ASB 按中标成交价向该 RSA 支付费用． 2∙2∙2 拍卖模型 定义1 暗标拍卖是一个不完全信息静态博 弈：〈AKCPU〉．其中A＝｛aj｜1≤ j≤ m｝是 M 个服务资源代理 RSA 的集合；K ＝｛kg｜1≤ g≤ l｝是 ASB 任务申请的 l 个服务类型的集合；C＝ ｛cgj｜1≤ g≤ l｜1≤ j≤ m｝是 m 个服务资源生产 成本价格的集合cgj是服务资源 j 完成 g 类服务的 成本价格；P＝｛pgj｜1≤g≤ l1≤ j≤ m｝是各 RSA 投标价的集合（投标策略空间）pgj是第 j 个卖方对 第 g 类服务需求的投标价． 卖方的投标策略就是如何选择投标价格以得到 最大收益投标价格是服务类型与服务资源成本的 函数pgj＝ pgj（ kgcgj）；U＝｛ugj｜1≤ g≤ l1≤ j≤ m｝是各 RSA 投标方效用的集合ugj是投标方 j 完 成第 g 类服务的效用． 2∙2∙3 效用分析 定义2 暗标拍卖中卖方中标者的效用是成 交价格与其代理的服务资源的成本价格之差未中 标者的效用为0． （1） 当只有卖方 j 是一个最低标价时卖方 j 中标其效用为： ugj＝ ugj（ pgjcgj）＝min g （ pgj）—cgjugj∈ U （1） （2） 当有 h（1≤ h≤ n）个相同的最低标价时 卖方 j 中标的概率就是一个最低价时的1／h其效 用为： ugj＝ ugj（ pgjcgj）＝［min g （ pgj）—cgj ］／h （2） （3） 卖方 j 没有中标时 ugj＝ ugj（ pgjcgj）＝0 （3） 显然卖方中标者的效用除了取决于中标价以 外还取决于服务资源的成本价． （4） 卖方的总效用为： U＝ ∑ lm g＝1j＝1 ugj＝ ∑ lm g＝1j＝1 ugj（ pgjcgj） （4） （5）买方的效用为： ugj＝ ugj（ bgpgj）＝bg— pgj （5） 第5期 陈冬娥等： 基于反拍卖的计算网格资源分配方法 ·549·
.550 北京科技大学学报 第29卷 其中，b,是网格用户对第g类服务需求的预算价 用越小；标价越高中标的机会越小，但中标的效用越 格. 大，所以在暗标拍卖博弈中，卖方不存在最大效用. (6)买方的总效用为： 证毕. 之y=为(a,-pg) 定理3在网格资源分配问题的暗标拍卖中， (6) g=1,=1 9=1=1 卖方j(1≤≤m)以投标价p成交，在此策略下， 定义3暗标拍卖中，系统的总效用U,=卖方 系统处于Bayes均衡状态. 的总效用十买方的总效用，即： 证明由于各个博弈方（卖方）构成策略的函数 u.=与pa+之(4，-p0) 关系可以有多种函数形式及种类，因此卖方策略空 g=1,j=1 g=1.j=1 间中的策略是非常多的，Bayes均衡策略组合通常 显然，当买方总效用和卖方总效用都分别最大 也有许多，想要找出暗标拍卖博弈的全部Bayes均 时，系统总效用才最大， 衡是很难的，甚至是不可能的，为了方便分析，假设 在暗标拍卖博弈中，卖方j中标者的收益除了 只有两个卖方（卖方i和卖方j(i,j=1,2;丰j), 取决于中标价以外，还取决于服务成本.卖方的一 那么对某一特定的服务资源，拍卖的策略组合为 个策略是一个函数关系Pg=P(gcg),所有这种 [p1(c1),p2(c2)],每个卖方的成本价S,设c在 函数关系的集合构成卖方j的策略空间. [0,1]上均匀分布，c∈[0,1] 定理1在网格资源分配问题的暗标拍卖中， 设卖方j的最优标价卫防是其对特定服务的生 拍卖以成交结束，此时买方存在唯一的最优策略 产成本G的函数，p=卫j(c),并假设pj(c)是单调 P=P(gcg),使得买方效用最大， 递增函数，实际意义为，卖方的生产成本高，投标价 证明(1)首先证明成交策略是买方的最优策 自然会高一些.于是存在反函数：G=P(9)= 略 ①(p),它表示投标价为p时，卖方j的生产成本， 买方拍卖以成交结束，此时成交价格卫= 卖方j的效用函数为： min(Pg)买方的效用： pi一G,当ppi Pgi)=bg一Pgw≤bg一min(Pg)=bg一pg=ug 其中，i,j=1,2;≠j 由P的任意性可知，成交策略Pw是买方的最 由于c在[0,1]上均匀分布，于是，卖方j的效 优策略， 用是： (2)唯一性 4(p1,p2,c1,cz)= 由证明(1)可知，任意策略p买方所获得的效 (pj-q)Xprob(p<p)+2(p-g)X 用都小于成交策略P下买方所获得的效用，根据拍 卖规则，拍卖中的价格是决定是否拍卖成功的唯一 prob(Pi=p:)+0Xprob(pjpi). 因素，在卖方成本一定的情况下，拍卖策略由拍卖价 式中，prob()是卖方j在不同情况下的概率，c是 格唯一确定，因此p是买方唯一的最优策略.证 卫j(c)的逆函数，又C作为连续型随机变量，故 毕. prob(p:=pi)=prob(Φ(pi)=Φ(pi)=0. 定理2在网格资源分配问题的暗标拍卖中， 由于c在[0,1]上均匀分布，故 卖方j不存在最大效用， prob(pjpi)=prob(pj(cj)pi(ci))= 证明(1)如果在拍卖成交的前提下， prob((pj)(pi))=(pj)c:=D(pj)- Hpg3u(pica)=pg-cg≥ 因此， min(Pai)cai=pai cai=ugi(Pai,caj)- uj(p1,p2,e1,e2)=(pi-cj)Xprob(pipi)= 可见，对于任意的P,成交策略P下的效用 (卫防一c)(p)· ug(P,cg)都不是最大 卖方j的效用最大化问题就可以表示为 (2)如果不成交，卖方j效用为0. mar(4)=max(pj一c)Φ(pi), 从以上分析不难看出，在网格资源分配问题的 对成本c求导得最优化一阶条件 暗标拍卖中，标价越低中标的机会越大，但中标的效 -(pi)十(p5-c)Φ'(pi)=0
其中bg 是网格用户对第 g 类服务需求的预算价 格． （6） 买方的总效用为： ∑ lm g＝1j＝1 ugj＝ ∑ lm g＝1j＝1 （ bg— pgj） （6） 定义3 暗标拍卖中系统的总效用 Us＝卖方 的总效用＋买方的总效用即： Us＝ ∑ lm g＝1j＝1 ugj（ pgjcgj）＋ ∑ lm g＝1j＝1 （ bg— pgj） （7） 显然当买方总效用和卖方总效用都分别最大 时系统总效用才最大． 在暗标拍卖博弈中卖方 j 中标者的收益除了 取决于中标价以外还取决于服务成本．卖方的一 个策略是一个函数关系 pgj＝ pgj（ kgcgj）所有这种 函数关系的集合构成卖方 j 的策略空间． 定理1 在网格资源分配问题的暗标拍卖中 拍卖以成交结束此时买方存在唯一的最优策略 p ∗ gj＝ p ∗ gj（ kgcgj）使得买方效用最大． 证明 （1） 首先证明成交策略是买方的最优策 略． 买方拍卖以成交结束此时成交价格 p ∗ gj ＝ min（ pgj）买方的效用： u ∗ gj＝ ugj（ bgp ∗ gj）＝bg— p ∗ gj＝bg—min（ pgj）． 对∀ p′gj＝ p′gj（ kgcgj）p′gj∈P∃ u′gj＝ ugj（ bg p′gj）＝bg— p′gj≤bg—min（ pgj）＝bg— p ∗ gj＝ u ∗ gj． 由 p′gj的任意性可知成交策略 p ∗ gj 是买方的最 优策略． （2） 唯一性． 由证明（1）可知任意策略 p′gj买方所获得的效 用都小于成交策略 p ∗ gj下买方所获得的效用根据拍 卖规则拍卖中的价格是决定是否拍卖成功的唯一 因素在卖方成本一定的情况下拍卖策略由拍卖价 格唯一确定因此 p ∗ gj 是买方唯一的最优策略．证 毕． 定理2 在网格资源分配问题的暗标拍卖中 卖方 j 不存在最大效用． 证明 （1） 如果在拍卖成交的前提下 ∀ p′gj∃ u′gj（ p′gjcgj）＝ p′gj—cgj≥ min（ pgj）—cgj＝ p ∗ gj—cgj＝ u ∗ gj（ p ∗ gjcgj）． 可见对于任意的 p′gj成交策略 p ∗ gj 下的效用 u ∗ gj（ p ∗ gjcgj）都不是最大． （2） 如果不成交卖方 j 效用为0． 从以上分析不难看出在网格资源分配问题的 暗标拍卖中标价越低中标的机会越大但中标的效 用越小；标价越高中标的机会越小但中标的效用越 大．所以在暗标拍卖博弈中卖方不存在最大效用． 证毕． 定理3 在网格资源分配问题的暗标拍卖中 卖方 j （1≤ j≤ m）以投标价 p ∗ ij 成交在此策略下 系统处于 Bayes 均衡状态． 证明 由于各个博弈方（卖方）构成策略的函数 关系可以有多种函数形式及种类因此卖方策略空 间中的策略是非常多的Bayes 均衡策略组合通常 也有许多想要找出暗标拍卖博弈的全部 Bayes 均 衡是很难的甚至是不可能的．为了方便分析假设 只有两个卖方（卖方 i 和卖方 j（ ij＝12；i≠ j）） 那么对某一特定的服务资源拍卖的策略组合为 ［ p1（ c1）p2（ c2）］每个卖方的成本价 cj设 cj 在 ［01］上均匀分布cj∈［01］． 设卖方 j 的最优标价 pj 是其对特定服务的生 产成本 cj 的函数pj＝ pj（ cj）并假设 pj（ cj）是单调 递增函数．实际意义为卖方的生产成本高投标价 自然会高一些．于是存在反函数：cj ＝ p —1 j （ cj ）＝ Φ（ pj）它表示投标价为 pj 时卖方 j 的生产成本． 卖方 j 的效用函数为： uj＝ uj（ p1p2c1c2）＝ pj—cj当 pj＜ pi （ pj—cj）／2当 pj＝ pi 0当 pj＞ pi 其中ij＝12；i≠ j． 由于 cj 在［01］上均匀分布于是卖方 j 的效 用是： uj（ p1p2c1c2）＝ （ pj—cj）×prob（ pj＜ pi）＋ 1 2 （ pj—cj）× prob（ pj＝ pi）＋0×prob（ pj＞ pi）． 式中prob（·）是卖方 j 在不同情况下的概率cj 是 pj（ cj）的逆函数又 cj 作为连续型随机变量故 prob（ pi＝ pj）＝prob（Φ（ pi）＝Φ（ pj））＝0． 由于 cj 在［01］上均匀分布故 prob（ pj＜ pi）＝prob（ p —1 j （ cj）＜ p —1 i （ ci））＝ prob（Φ（ pj）＜Φ（ pi））＝Φ（ pj）＜ci＝Φ（ pj）． 因此 uj（ p1p2e1e2）＝（ pj—cj）×prob（ pj＜ pi）＝ （ pj—cj）Φ（ pj）． 卖方 j 的效用最大化问题就可以表示为 max p j （ uj）＝max p j （（ pj—cj）Φ（ pj）） 对成本 cj 求导得最优化一阶条件 —Φ（ pj）＋（ pj—cj）Φ′（ pj）＝0 ·550· 北 京 科 技 大 学 学 报 第29卷
第5期 陈冬娥等：基于反拍卖的计算网格资源分配方法 .551. 解此微分方程得 QS要求，采用用户预算与服务完成时间加权的方 Pi=2cj. 法作为效用函数，有下式： 由此可见，策略组合(2c1,2c2)是此拍卖的 u(ta,e)=aln(kta)+Bne (8) Bayes均衡 其中，k为完成用户服务所需要的服务类型向量；α， 可以计算出，卖方的投标价与实际成本之间的 β是由用户给定的系数，且α十B=1,表示用户对服 差距将随着投标人数的增多而递减.如果有m个 务质量的要求，是偏好完成时间更短还是偏好费用 卖方博弈，每个卖方的成本c独立，且在[0,1]上均 更低 匀分布，则卖方j(1≤≤m)的效用函数 基于该效用函数的优化算法： 山=(p一c)-（pi), Step1:由买方给出服务需求，AsB对服务进行 最优化一阶条件为 分类，确定a,B的值 (pi)十(m-1)(p-G)Φ'(p)=0, Step2:由各个卖方进行暗标叫价 解微分方程得到 Step3:确定获胜卖方 Step4:服务交易，按式(8)给出的效用函数计 P-mi 算效用值，再按中标价计算完成服务的费用 可见，当m→o时，p时→G也就是说，投标人 Step5:按效用值u(ta,e)从小到大对资源排 越多，买方需要支付的费用就越少， 序 证毕. Step6:对服务请求集D中的每个服务请求d: 当然，如果没有限定卖方采用单调递增函数的 进行调度，重复执行以下步骤，直到完成所有请求的 策略，Bayes均衡就会发生改变，如果卖方成本的概 服务 率分布，不再是[0,1]的均匀分布，则暗标拍卖博弈 For each t in order u(ta,e) 的Bayes均衡也会发生变化，要根据概率具体分布 if minimum B and ETC(di)<T 情况讨论， do select)while p《e时∥把任务分配给最便宜的 定理4在网格资源分配问题的暗标拍卖中， 资源 当拍卖以标价p;成交时，即系统处于Bayes均衡状 enddo 态时，网格经济系统效用最大，网格资源得到合理配 endif 置 if aB and pijei 证明 由式(7)，当拍卖以标价p成交时，卖 do select,while ETC(d:,t)<Td∥把任务分配给 方总效用 执行时间最短的资源) enddo U= g=1.=1 g=1,=1 endif 由定理3知，在P时，存在策略组合使得系统 endfor 处于Bayes均衡状态，而一定的策略组合下，卖方的 其中，T为用户定义的完成服务d:的最终期限， 效用一定 ETC(d:,t)为服务请求d:在资源r上的预期执行 又由定理1知，此时买方效用最大 时间，e时为完成服务d:用户愿意支付的服务费用， ug =∑(b,-P P为服务d:使用资源的价格. 9=1.=1 g=1,=1 由定义3，系统总效用U。=买方总效用十卖方 4 结语 总效用，因此，此时系统总效用最大，证毕 运用拍卖机制进行网格资源管理是一种非常灵 可见，在拍卖成交时，网格用户在获得了最大效 活有效的方法，本文着重讨论了暗标拍卖在网格资 用的同时，系统也获得了最大的总效用，个体优化 源分配中的应用，以面向服务的思想，构建了一个 与整体优化取得一致，就是最合理的资源分配方案. 基于网格服务市场的资源分配框架，该框架基于 3资源分配算法 OGSA,开放性和可扩充性较好，在此框架下，将资 源分配问题描述为一个暗标拍卖模型，其目标是在 设ta为用户要求的服务完成时间，e为用户代 满足网格用户Qo$要求的情况下，最大化系统的总 理完成该任务的预算费用，为更好的表达用户的 效用，为了更好地表达网格用户的需求，使用了完
解此微分方程得 pj＝2cj． 由此可见策略组合 （2c12c2） 是此拍卖的 Bayes 均衡． 可以计算出卖方的投标价与实际成本之间的 差距将随着投标人数的增多而递减．如果有 m 个 卖方博弈每个卖方的成本 cj 独立且在［01］上均 匀分布则卖方 j（1≤ j≤ m）的效用函数 uj＝（ pj—cj）Φm—1（ pj） 最优化一阶条件为 —Φ（ pj）＋（ m—1）（ pj—cj）Φ′（ pj）＝0 解微分方程得到 pj＝ m m—1 cj． 可见当 m→∞时pj → cj．也就是说投标人 越多买方需要支付的费用就越少． 证毕． 当然如果没有限定卖方采用单调递增函数的 策略Bayes 均衡就会发生改变如果卖方成本的概 率分布不再是［01］的均匀分布则暗标拍卖博弈 的 Bayes 均衡也会发生变化要根据概率具体分布 情况讨论． 定理4 在网格资源分配问题的暗标拍卖中 当拍卖以标价 p ∗ ij 成交时即系统处于 Bayes 均衡状 态时网格经济系统效用最大网格资源得到合理配 置． 证明 由式（7）当拍卖以标价 p ∗ ij 成交时卖 方总效用 U＝ ∑ lm g＝1j＝1 ugj＝ ∑ lm g＝1j＝1 ugj（ pgjcgj）． 由定理3知在 p ∗ ij 时存在策略组合使得系统 处于 Bayes 均衡状态而一定的策略组合下卖方的 效用一定． 又由定理1知此时买方效用最大 ∑ lm g＝1j＝1 ugj＝ ∑ lm g＝1j＝1 （ bg— pgj）． 由定义3系统总效用 Us＝买方总效用＋卖方 总效用因此此时系统总效用最大．证毕． 可见在拍卖成交时网格用户在获得了最大效 用的同时系统也获得了最大的总效用．个体优化 与整体优化取得一致就是最合理的资源分配方案． 3 资源分配算法 设 td 为用户要求的服务完成时间e 为用户代 理完成该任务的预算费用为更好的表达用户的 QoS 要求采用用户预算与服务完成时间加权的方 法作为效用函数有下式： u（ tde）＝ aln（ ktd）＋βln e （8） 其中k 为完成用户服务所需要的服务类型向量；α β是由用户给定的系数且 α＋β＝1表示用户对服 务质量的要求是偏好完成时间更短还是偏好费用 更低． 基于该效用函数的优化算法： Step1：由买方给出服务需求ASB 对服务进行 分类确定 αβ的值． Step2：由各个卖方进行暗标叫价． Step3：确定获胜卖方． Step4：服务交易．按式（8）给出的效用函数计 算效用值再按中标价计算完成服务的费用． Step5：按效用值 u（ tde）从小到大对资源排 序． Step6：对服务请求集 D 中的每个服务请求 di 进行调度重复执行以下步骤直到完成所有请求的 服务． ｛For each t in order u（ tde） if minimum α＜βand ETC（ dit）＜ Tdi do select rj while pij≪eij∥把任务分配给最便宜的 资源 rj enddo endif if α＞βand pij＜eij do select rj while ETC（ dit）≪ Tdi∥把任务分配给 执行时间最短的资源 rj enddo endif endfor｝ 其中Tdi为用户定义的完成服务 di 的最终期限 ETC（ dit）为服务请求 di 在资源 rj 上的预期执行 时间eij为完成服务 di 用户愿意支付的服务费用 pij为服务 di 使用资源 rj 的价格． 4 结语 运用拍卖机制进行网格资源管理是一种非常灵 活有效的方法．本文着重讨论了暗标拍卖在网格资 源分配中的应用．以面向服务的思想构建了一个 基于网格服务市场的资源分配框架．该框架基于 OGSA开放性和可扩充性较好．在此框架下将资 源分配问题描述为一个暗标拍卖模型其目标是在 满足网格用户 QoS 要求的情况下最大化系统的总 效用．为了更好地表达网格用户的需求使用了完 第5期 陈冬娥等： 基于反拍卖的计算网格资源分配方法 ·551·
.552 北京科技大学学报 第29卷 成时间和用户预算相结合的加权效用模型，通过网 in Asia-Pacific Region (HPC Asia 2000).Beijing.2000 格中每个独立的经济个体最大化各自收益，网格服 [5]Buyya R.Murshed M.Abramson D.A deadline and budget con- strained cost time optimization algorithm for scheduling task farm- 务市场达到均衡.市场交易的均衡点即为系统资源 ing applications on global grids//The 2002 International Confer- 的最优配置.该算法的复杂度较低，能够根据用户 ence on Parallel and Distributed Processing Techniques and Appli- 的Q$要求灵活有效地为用户动态的分配网格服 cations.Las Vegas,2002:101 务资源 [6]Wolski R.Brevik J.Plank J,et al.Grid resource allocation and control using computational economies//Berman F.Fox C.Hey 参考文献 T.In Grid Computing:Making the Global Infrastructure a Reali- [1]Waldspurger C.Hogg T.Huberman B.et al.Spawn:a dis" ty.Chichester:John Wiley &.Sons Ltd,2003:747 tributed computational economy.IEEE Trans Software Eng [7]Buyya R.Economie-Based Distributed Resource Management and 1992,18(2):103 Scheduling for Grid Computing Dissertation ]Melbourne: [2]Nisan N.London S,Regev O,et al.Globally distributed compu" Monash University,2002 tation over the internet:the POPCORN project //The Int Conf [8]Buyya R.Abramson D.Venugopal S.The grid economy/ Distributed Computing Systems(ICDCS'98).Amsterdam.1998 Parashar M,Lee C.Special Issue on Grid Computing Proceed- [3]LalisS,Karipidis A.An open market-based framework for dis- ings of the IEEE.New York:IEEE Press.2005,93(3):698 tributed computing over the internet //The Ist IEEE/ACM Int [9]Wolski R.Plank JS.Brevik J.et al.Analyzing market-based re- Workshop Grid Computing (GRID 2000).Bangalore.2000 source allocation strategies for the computational grid.Int J High [4 Moore R,Baru C.Marciano R,et al.Nimrod-G:an architecture Perform Comput Appl.2001.15(3):258 for a resource management and scheduling system in a global com [10]谢识子.经济博弈论.上海：复旦大学出版社，2002 putational grid//The 4th Int Conf High Performance Computing Method of resource allocation for computational grids based on reverse auction CHEN Donge 2),YANG Yang),LIU Li) 1)Information Engineering School.University of Science and Technology Beijing.Beijing 100083.China 2)Computer Center,Hebei University of Economics and Business.Shijiahuang 050091.China ABSTRACI A sealed inverse-auction method of resource allocation for computational grids was proposed con sidering the dynamic,heterogeneous and autonomous characteristics of computing resources in the computational grid environment and the advantages of economics mechanism applied to solve the problem of resource manage- ment.A grid service market framework for resource allocation in the computational grid environment was de- scribed.A sealed inverse-auction mechanism was presented,where centered on users,and driven by user s needs.The aim was to maximize the total system utility while the QoS requirement of users were fulfilled. Bayes equilibrium point and strategy,efficiency and utility in the Bayes equilibrium state were discussed.A utili- ty function-based resource allocation arithmetic was presented. KEY WORDS grid service:resource allocation:inverse auction:QoS:Bayes equilibrium:utility function
成时间和用户预算相结合的加权效用模型通过网 格中每个独立的经济个体最大化各自收益网格服 务市场达到均衡．市场交易的均衡点即为系统资源 的最优配置．该算法的复杂度较低能够根据用户 的 QoS 要求灵活有效地为用户动态的分配网格服 务资源． 参 考 文 献 ［1］ Waldspurger CHogg THuberman Bet al．Spawn：a distributed computational economy．IEEE Trans Software Eng 199218（2）：103 ［2］ Nisan NLondon SRegev Oet al．Globally distributed computation over the internet：the POPCORN project ∥The Int Conf Distributed Computing Systems （ICDCS’98）．Amsterdam1998 ［3］ Lalis SKaripidis A．An open market-based framework for distributed computing over the internet ∥The 1st IEEE／ACM Int Workshop Grid Computing （GRID2000）．Bangalore2000 ［4］ Moore RBaru CMarciano Ret al．Nimrod-G：an architecture for a resource management and scheduling system in a global computational grid∥The4th Int Conf High Performance Computing in Asia-Pacific Region （HPC Asia2000）．Beijing2000 ［5］ Buyya RMurshed MAbramson D．A deadline and budget constrained cost-time optimization algorithm for scheduling task farming applications on global grids∥The2002International Conference on Parallel and Distributed Processing Techniques and Applications．Las Vegas2002：101 ［6］ Wolski RBrevik JPlank Jet al．Grid resource allocation and control using computational economies∥Berman FFox GHey T．In Grid Computing：Making the Global Infrastructure a Reality．Chichester：John Wiley ＆ Sons Ltd2003：747 ［7］ Buyya R．Economic-Based Distributed Resource Management and Scheduling for Grid Computing ［ Dissertation ］． Melbourne： Monash University2002 ［8］ Buyya RAbramson D．Venugopal S．The grid economy ∥ Parashar MLee C．Special Issue on Grid ComputingProceedings of the IEEE．New York：IEEE Press200593（3）：698 ［9］ Wolski RPlank J SBrevik Jet al．Analyzing market-based resource allocation strategies for the computational grid．Int J High Perform Comput Appl200115（3）：258 ［10］ 谢识予．经济博弈论．上海：复旦大学出版社2002 Method of resource allocation for computational grids based on reverse-auction CHEN Donge 12）Y A NG Y ang 1）LIU L i 1） 1） Information Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China 2） Computer CenterHebei University of Economics and BusinessShijiazhuang050091China ABSTRACT A sealed inverse-auction method of resource allocation for computational grids was proposed considering the dynamicheterogeneous and autonomous characteristics of computing resources in the computational grid environment and the advantages of economics mechanism applied to solve the problem of resource management．A grid service market framework for resource allocation in the computational grid environment was described．A sealed inverse-auction mechanism was presentedwhere centered on usersand driven by user’s needs．The aim was to maximize the total system utility while the QoS requirement of users were fulfilled． Bayes equilibrium point and strategyefficiency and utility in the Bayes equilibrium state were discussed．A utility function-based resource allocation arithmetic was presented． KEY WORDS grid service；resource allocation；inverse auction；QoS；Bayes equilibrium；utility function ·552· 北 京 科 技 大 学 学 报 第29卷