正在加载图片...
第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·