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