基于竞价机制的网格资源分配方法

王维欢林晓娴魏物春

1.西北师范大学数信学院，甘肃 兰州730070

2.兰州市财税学校

基于竞价机制的网格资源分配方法

王维欢1林晓娴1魏物春2

1.西北师范大学数信学院，甘肃 兰州730070

2.兰州市财税学校

针对网格资源分配中的竞争问题，提出一种基于竞价机制的网格资源分配方法，并定义了参与方的效用函数，基于所提出的资源分配模型，设计出一种网格资源分配算法，从而使得整个资源的分配趋于合理，为解决网格资源分配问题提供了一种有效的途径。

Grid; Resource Allocation; Bidding; Utility Function

1 引言

网格资源管理是网格计算的核心问题，而资源分配以及资源分配算法又是资源管理的关键技术和核心问题[1]。提高网格系统的性能，就要提高资源管理的效率和设计好的资源分配算法，从而满足系统的用户需求并为其他服务提供支持。合理地将市场机制引入到网格的资源分配中，可保障资源提供者和使用者的利益，同时也可以激励更多的资源提供者加入到网格系统的建设中。目前已经有很多基于市场机制的经济模型被使用到网格资源的分配中，文献[2]中使用市场经济学中的商品市场和拍卖模型进行动态资源分配。文献[3]中提出一种市场竞拍机制的网格资源管理分配方法，以均衡理论和第二价格竞拍机制为基础，实现了计算网格资源的优化分配。文献[4]中提出一种用投标模型对网格资源进行分配的方法,通过投标算法搜索效用函数获得其期望效用最大化。文献[5]中以一般均衡论为基础，依靠市场机制，提出一种基于市场机制的资源分配方法，实现计算网格资源的优化调度。本文提出的基于竞价机制的资源分配方法，为调节网格资源分配提出了一种算法，系统遵循均衡分配原则，根据用户的竞价均衡地分配网格资源。

2 基于竞价机制的网格资源分配模型

基于竞价机制的网格资源分配模型如图1所示，主要由三个实体组成：资源提供者，网格市场和用户。资源提供者和用户通过网格市场发生作用来实现网格资源的调度和分配。

以下分别介绍此模型中的各个模块及其功能：

（1）网格资源提供者：是市场交易的提供者。通过出售资源，从而追求自身利益的网格节点，由资源管理者将自己相关的信息在市场中发布，从而进入网格市场进行交易。

资源管理者：是资源提供者的软件代理。在用户和网格资源之间，通过中间件来扮演中介者的角色，能够根据资源提供者的意愿，在进行实际交易时，负责向市场发布资源状态信息，协助用户管理者使用资源，并协调网格资源提供者和网格用户之间的交互。

（2）网格用户：是市场交易的竞标者。通过支付金额购买资源，从而获得资源的网格节点。

用户管理者：是网格用户的软件代理，按照特定的策略，根据用户的需求访问网格市场，寻找用户满意的资源，与资源管理者通过协商进行交易。

（3）网格市场：在用户和网格资源之间架起沟通的桥梁。网格市场的主要功能是以市场交易的方式实现网格资源供需双方的匹配。它为交易双方提供了一个代理平台，是交易的协调者，主要组成部分为：市场控制和管理，网格信息服务，网格交易服务和网格银行等。

运用该模型，实现资源分配的大致步骤如下：

①资源提供者通过资源管理者在网格市场中注册资源，网格信息服务动态收集资源信息；

②用户通过用户管理者在网格信息服务中查找资源，获得满足条件的资源集合；

③用户管理者根据网格信息服务提供的信息，在网格交易服务中与资源管理者进行交互，资源管理者访问用户管理者对每个资源提交的竞价，然后根据分配算法由市场控制和管理模块分配资源，并反馈给用户管理者；

④最后资源管理者和用户管理者通过网格银行完成货币支付。

3 基于竞价机制的资源分配

3.1 问题描述

本文网格资源分配定义为同时为多个网格用户分配多个不同类型资源的问题，该分配同时满足用户对资源的具体性能需求。假定本文中的网格环境由m个计算资源和n个非合作的用户组成，n个用户可以同时竞争m个计算资源。这里的计算资源分为两种情况：一种是可以划分的资源，另外一种是不可划分的资源。

定义1：资源集合R为：R={R1，R2，…，Rm｝代表m个异构的计算资源。

定义2：用户集合U为U={U1,U2,…,Un｝，假设集合中用户的各个任务之间是相互独立的，Bi表示用户支付的预算，单位：G$。

定义3：n个用户对m个资源的竞价集合用矩阵B表示为：

3.2 效用函数

在网格资源管理中，效用是衡量网格资源提供者提供给用户服务的满意程度。网格资源的分配方法应当可以根据特定用户的需求及应用特性来选择适合的计算资源执行任务，为此引入效用函数。效用函数是指用户竞争资源时通过竞价所获得的资源效用的函数，它被用以衡量用户从既定的资源组合中所获得的满足程度。资源提供者和用户的目的都是致力于最大化他们各自的效用函数，来获得最大的利润。

在竞争资源时，每个用户都是以自己效用最大为目标进行竞价，在不超过其预算的前提下，通过对资源的不同竞价，期望获取更多的资源满足需求。此外，用户的资源占用对其他用户效用的潜在影响也是需要考虑的问题。用户的效用函数定义如下：

(1)对可划分的网格资源进行竞价的用户的效用函数

图1 基于竞价机制的网格资源分配模型

Wij表示用户i得到资源j的分配比例，Bij表示用户i对资源j的竞价，表示n个用户对资源j的竞价总和，Eij表示用户i对资源j的喜好程度所给出的权重，其中

表示用户i对m个资源的竞价之和，由公式(2)可知，用户出价越高，使用的资源数量越多，当用户获得的资源数越多，效用值越大。对每个资源的竞价越高，用户的效用越大，每个用户的目的就是使自己效用最大化，因此需要选用一种合理的竞价组合，尽可能多的获得更多的资源。

（3）每个用户都想在条件允许的情况下最大化自己的效用。因此，从用户角度出发，使其效用最大化是最终优化目标。用户的目标函数定义为:

约束条件为第i个用户对m个资源的竞价之和不能超出用户总预算Bi。

当一个用户向各个资源竞价，由于在网格中其他用户同时也在出价，因此目前的用户竞价可能还会改变，此时代理就必须根据新的一组竞价来最大化自己效用。但是这种状态不可能一直持续下去，需要基于纳什均衡确定资源分配策略。纳什均衡是指用户所选的竞价策略处于这样一种状态，即在其他用户不改变当前策略的前提下，任何一个用户都无法单方改变自己的策略而实现各自效用最大化。

4 基于效用函数的网格资源分配算法

基于效用函数的资源分配策略其设计目标为：（1）各用户都是以自己的效用最大为目标来竞价，申请资源；（2）通过算法的执行，资源能够获得一个合理的定价，且资源在分配上能够收敛于一个纳什均衡点的资源分配结果；

资源分配算法：

输入：资源的底价，用户的最大预算、竞价；

输出：资源分配结果。

① 获得满足条件的资源集合R；

② 用户i对m个资源提交竞价，资源提供者根据用户提交的竞价分配资源；

③ 用户根据分配到资源的情况和其效用函数公式计算其效用；

④ 由于在网格中多个用户在同时竞价，各个用户竞价很可能发生变化，此时，用户就必须重新提交竞价来最大化自己效用。根据效用函数策略，寻找一组用户竞价使得用户的竞价保持不变，即系统达到均衡状态，则分配结束，否则，返回步骤2。

5 结论

本文提出了一种基于竞价机制的网格资源分配模型，通过效用函数刻画用户对网格服务的满意程度，并给出了基于用户效用函数的资源分配方法，为解决网格资源分配问题提供了一个有效的途径。

[1]K.Czajkowski, I.Foster, N.Karonis,et al.A Resource Management Architecture for Metacomputing Systems.Job Scheduling Strategies for Parallel Processing.1998, 1459(10): 62-82.

[2]R Wolski, JS Plank, J Brevik, T Bryan.G-commerce: Market formulations controlling resource allocation on the computational grid.In Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS’01).IEEE Computer Society, 2001, 1: 1530-2075.

[3]曹鸿强, 俏侬, 卢锡城.一种基于市场机制的计算网格资源分配方法[J].计算机研究与发展.2002, 39(8): 913-916

[4]李春林.基于投标模型的计算网格资源分配的研究[J].武汉理工大学学报.2005, 29(5): 654 - 658

[5]Cao Hongqiang, Xiao Nong, Li Xicheng, et al.A market-based approach to allocate resource for computational grids[J].Journal of Computer Research and Development, 2002, 39(8): 913-916.

An Approach to Allocate Grid Resources Based on Bidding

Wang Wei-huan Lin Xiao-xian
College of Mathematics and Information Science, Northwest Normal University

For the problem of competition in grid Resource Allocation, a bidding mechanism based on the grid resource allocation methods is proposed, and defines the utility function of users.Based on the proposed resource allocation model, designed an algorithm of grid resource allocation, which makes the whole resource allocation more reasonable, to provides an effective way to resolve the problem of the grid resource management.

TP393

甘肃省科技攻关计划项目2GS047-A52-002-04

10.3969/j.issn.1001-8972.2011.04.049

王维欢（1981-），女，甘肃兰州人，硕士研究生，主要研究领域：分布与并行计算；

林晓娴（1983-），女，甘肃兰州人，硕士研究生，主要研究领域：分布与并行计算；

魏物春（1981-），男。甘肃兰州人，教师。

网格；资源分配；竞价；效用函数