王維歡林曉嫻魏物春

1.西北師范大學(xué)數(shù)信學(xué)院，甘肅 蘭州730070

2.蘭州市財(cái)稅學(xué)校

基于競(jìng)價(jià)機(jī)制的網(wǎng)格資源分配方法

王維歡1林曉嫻1魏物春2

1.西北師范大學(xué)數(shù)信學(xué)院，甘肅 蘭州730070

2.蘭州市財(cái)稅學(xué)校

針對(duì)網(wǎng)格資源分配中的競(jìng)爭(zhēng)問(wèn)題，提出一種基于競(jìng)價(jià)機(jī)制的網(wǎng)格資源分配方法，并定義了參與方的效用函數(shù)，基于所提出的資源分配模型，設(shè)計(jì)出一種網(wǎng)格資源分配算法，從而使得整個(gè)資源的分配趨于合理，為解決網(wǎng)格資源分配問(wèn)題提供了一種有效的途徑。

Grid; Resource Allocation; Bidding; Utility Function

1 引言

網(wǎng)格資源管理是網(wǎng)格計(jì)算的核心問(wèn)題，而資源分配以及資源分配算法又是資源管理的關(guān)鍵技術(shù)和核心問(wèn)題[1]。提高網(wǎng)格系統(tǒng)的性能，就要提高資源管理的效率和設(shè)計(jì)好的資源分配算法，從而滿足系統(tǒng)的用戶需求并為其他服務(wù)提供支持。合理地將市場(chǎng)機(jī)制引入到網(wǎng)格的資源分配中，可保障資源提供者和使用者的利益，同時(shí)也可以激勵(lì)更多的資源提供者加入到網(wǎng)格系統(tǒng)的建設(shè)中。目前已經(jīng)有很多基于市場(chǎng)機(jī)制的經(jīng)濟(jì)模型被使用到網(wǎng)格資源的分配中，文獻(xiàn)[2]中使用市場(chǎng)經(jīng)濟(jì)學(xué)中的商品市場(chǎng)和拍賣(mài)模型進(jìn)行動(dòng)態(tài)資源分配。文獻(xiàn)[3]中提出一種市場(chǎng)競(jìng)拍機(jī)制的網(wǎng)格資源管理分配方法，以均衡理論和第二價(jià)格競(jìng)拍機(jī)制為基礎(chǔ)，實(shí)現(xiàn)了計(jì)算網(wǎng)格資源的優(yōu)化分配。文獻(xiàn)[4]中提出一種用投標(biāo)模型對(duì)網(wǎng)格資源進(jìn)行分配的方法,通過(guò)投標(biāo)算法搜索效用函數(shù)獲得其期望效用最大化。文獻(xiàn)[5]中以一般均衡論為基礎(chǔ)，依靠市場(chǎng)機(jī)制，提出一種基于市場(chǎng)機(jī)制的資源分配方法，實(shí)現(xiàn)計(jì)算網(wǎng)格資源的優(yōu)化調(diào)度。本文提出的基于競(jìng)價(jià)機(jī)制的資源分配方法，為調(diào)節(jié)網(wǎng)格資源分配提出了一種算法，系統(tǒng)遵循均衡分配原則，根據(jù)用戶的競(jìng)價(jià)均衡地分配網(wǎng)格資源。

2 基于競(jìng)價(jià)機(jī)制的網(wǎng)格資源分配模型

基于競(jìng)價(jià)機(jī)制的網(wǎng)格資源分配模型如圖1所示，主要由三個(gè)實(shí)體組成：資源提供者，網(wǎng)格市場(chǎng)和用戶。資源提供者和用戶通過(guò)網(wǎng)格市場(chǎng)發(fā)生作用來(lái)實(shí)現(xiàn)網(wǎng)格資源的調(diào)度和分配。

以下分別介紹此模型中的各個(gè)模塊及其功能：

（1）網(wǎng)格資源提供者：是市場(chǎng)交易的提供者。通過(guò)出售資源，從而追求自身利益的網(wǎng)格節(jié)點(diǎn)，由資源管理者將自己相關(guān)的信息在市場(chǎng)中發(fā)布，從而進(jìn)入網(wǎng)格市場(chǎng)進(jìn)行交易。

資源管理者：是資源提供者的軟件代理。在用戶和網(wǎng)格資源之間，通過(guò)中間件來(lái)扮演中介者的角色，能夠根據(jù)資源提供者的意愿，在進(jìn)行實(shí)際交易時(shí)，負(fù)責(zé)向市場(chǎng)發(fā)布資源狀態(tài)信息，協(xié)助用戶管理者使用資源，并協(xié)調(diào)網(wǎng)格資源提供者和網(wǎng)格用戶之間的交互。

（2）網(wǎng)格用戶：是市場(chǎng)交易的競(jìng)標(biāo)者。通過(guò)支付金額購(gòu)買(mǎi)資源，從而獲得資源的網(wǎng)格節(jié)點(diǎn)。

用戶管理者：是網(wǎng)格用戶的軟件代理，按照特定的策略，根據(jù)用戶的需求訪問(wèn)網(wǎng)格市場(chǎng)，尋找用戶滿意的資源，與資源管理者通過(guò)協(xié)商進(jìn)行交易。

（3）網(wǎng)格市場(chǎng)：在用戶和網(wǎng)格資源之間架起溝通的橋梁。網(wǎng)格市場(chǎng)的主要功能是以市場(chǎng)交易的方式實(shí)現(xiàn)網(wǎng)格資源供需雙方的匹配。它為交易雙方提供了一個(gè)代理平臺(tái)，是交易的協(xié)調(diào)者，主要組成部分為：市場(chǎng)控制和管理，網(wǎng)格信息服務(wù)，網(wǎng)格交易服務(wù)和網(wǎng)格銀行等。

運(yùn)用該模型，實(shí)現(xiàn)資源分配的大致步驟如下：

①資源提供者通過(guò)資源管理者在網(wǎng)格市場(chǎng)中注冊(cè)資源，網(wǎng)格信息服務(wù)動(dòng)態(tài)收集資源信息；

②用戶通過(guò)用戶管理者在網(wǎng)格信息服務(wù)中查找資源，獲得滿足條件的資源集合；

③用戶管理者根據(jù)網(wǎng)格信息服務(wù)提供的信息，在網(wǎng)格交易服務(wù)中與資源管理者進(jìn)行交互，資源管理者訪問(wèn)用戶管理者對(duì)每個(gè)資源提交的競(jìng)價(jià)，然后根據(jù)分配算法由市場(chǎng)控制和管理模塊分配資源，并反饋給用戶管理者；

④最后資源管理者和用戶管理者通過(guò)網(wǎng)格銀行完成貨幣支付。

3 基于競(jìng)價(jià)機(jī)制的資源分配

3.1 問(wèn)題描述

本文網(wǎng)格資源分配定義為同時(shí)為多個(gè)網(wǎng)格用戶分配多個(gè)不同類型資源的問(wèn)題，該分配同時(shí)滿足用戶對(duì)資源的具體性能需求。假定本文中的網(wǎng)格環(huán)境由m個(gè)計(jì)算資源和n個(gè)非合作的用戶組成，n個(gè)用戶可以同時(shí)競(jìng)爭(zhēng)m個(gè)計(jì)算資源。這里的計(jì)算資源分為兩種情況：一種是可以劃分的資源，另外一種是不可劃分的資源。

定義1：資源集合R為：R={R1，R2，…，Rm｝代表m個(gè)異構(gòu)的計(jì)算資源。

定義2：用戶集合U為U={U1,U2,…,Un｝，假設(shè)集合中用戶的各個(gè)任務(wù)之間是相互獨(dú)立的，Bi表示用戶支付的預(yù)算，單位：G$。

定義3：n個(gè)用戶對(duì)m個(gè)資源的競(jìng)價(jià)集合用矩陣B表示為：

3.2 效用函數(shù)

在網(wǎng)格資源管理中，效用是衡量網(wǎng)格資源提供者提供給用戶服務(wù)的滿意程度。網(wǎng)格資源的分配方法應(yīng)當(dāng)可以根據(jù)特定用戶的需求及應(yīng)用特性來(lái)選擇適合的計(jì)算資源執(zhí)行任務(wù)，為此引入效用函數(shù)。效用函數(shù)是指用戶競(jìng)爭(zhēng)資源時(shí)通過(guò)競(jìng)價(jià)所獲得的資源效用的函數(shù)，它被用以衡量用戶從既定的資源組合中所獲得的滿足程度。資源提供者和用戶的目的都是致力于最大化他們各自的效用函數(shù)，來(lái)獲得最大的利潤(rùn)。

在競(jìng)爭(zhēng)資源時(shí)，每個(gè)用戶都是以自己效用最大為目標(biāo)進(jìn)行競(jìng)價(jià)，在不超過(guò)其預(yù)算的前提下，通過(guò)對(duì)資源的不同競(jìng)價(jià)，期望獲取更多的資源滿足需求。此外，用戶的資源占用對(duì)其他用戶效用的潛在影響也是需要考慮的問(wèn)題。用戶的效用函數(shù)定義如下：

(1)對(duì)可劃分的網(wǎng)格資源進(jìn)行競(jìng)價(jià)的用戶的效用函數(shù)

圖1 基于競(jìng)價(jià)機(jī)制的網(wǎng)格資源分配模型

Wij表示用戶i得到資源j的分配比例，Bij表示用戶i對(duì)資源j的競(jìng)價(jià)，表示n個(gè)用戶對(duì)資源j的競(jìng)價(jià)總和，Eij表示用戶i對(duì)資源j的喜好程度所給出的權(quán)重，其中

表示用戶i對(duì)m個(gè)資源的競(jìng)價(jià)之和，由公式(2)可知，用戶出價(jià)越高，使用的資源數(shù)量越多，當(dāng)用戶獲得的資源數(shù)越多，效用值越大。對(duì)每個(gè)資源的競(jìng)價(jià)越高，用戶的效用越大，每個(gè)用戶的目的就是使自己效用最大化，因此需要選用一種合理的競(jìng)價(jià)組合，盡可能多的獲得更多的資源。

（3）每個(gè)用戶都想在條件允許的情況下最大化自己的效用。因此，從用戶角度出發(fā)，使其效用最大化是最終優(yōu)化目標(biāo)。用戶的目標(biāo)函數(shù)定義為:

約束條件為第i個(gè)用戶對(duì)m個(gè)資源的競(jìng)價(jià)之和不能超出用戶總預(yù)算Bi。

當(dāng)一個(gè)用戶向各個(gè)資源競(jìng)價(jià)，由于在網(wǎng)格中其他用戶同時(shí)也在出價(jià)，因此目前的用戶競(jìng)價(jià)可能還會(huì)改變，此時(shí)代理就必須根據(jù)新的一組競(jìng)價(jià)來(lái)最大化自己效用。但是這種狀態(tài)不可能一直持續(xù)下去，需要基于納什均衡確定資源分配策略。納什均衡是指用戶所選的競(jìng)價(jià)策略處于這樣一種狀態(tài)，即在其他用戶不改變當(dāng)前策略的前提下，任何一個(gè)用戶都無(wú)法單方改變自己的策略而實(shí)現(xiàn)各自效用最大化。

4 基于效用函數(shù)的網(wǎng)格資源分配算法

基于效用函數(shù)的資源分配策略其設(shè)計(jì)目標(biāo)為：（1）各用戶都是以自己的效用最大為目標(biāo)來(lái)競(jìng)價(jià)，申請(qǐng)資源；（2）通過(guò)算法的執(zhí)行，資源能夠獲得一個(gè)合理的定價(jià)，且資源在分配上能夠收斂于一個(gè)納什均衡點(diǎn)的資源分配結(jié)果；

資源分配算法：

輸入：資源的底價(jià)，用戶的最大預(yù)算、競(jìng)價(jià)；

輸出：資源分配結(jié)果。

① 獲得滿足條件的資源集合R；

② 用戶i對(duì)m個(gè)資源提交競(jìng)價(jià)，資源提供者根據(jù)用戶提交的競(jìng)價(jià)分配資源；

③ 用戶根據(jù)分配到資源的情況和其效用函數(shù)公式計(jì)算其效用；

④ 由于在網(wǎng)格中多個(gè)用戶在同時(shí)競(jìng)價(jià)，各個(gè)用戶競(jìng)價(jià)很可能發(fā)生變化，此時(shí)，用戶就必須重新提交競(jìng)價(jià)來(lái)最大化自己效用。根據(jù)效用函數(shù)策略，尋找一組用戶競(jìng)價(jià)使得用戶的競(jìng)價(jià)保持不變，即系統(tǒng)達(dá)到均衡狀態(tài)，則分配結(jié)束，否則，返回步驟2。

5 結(jié)論

本文提出了一種基于競(jìng)價(jià)機(jī)制的網(wǎng)格資源分配模型，通過(guò)效用函數(shù)刻畫(huà)用戶對(duì)網(wǎng)格服務(wù)的滿意程度，并給出了基于用戶效用函數(shù)的資源分配方法，為解決網(wǎng)格資源分配問(wèn)題提供了一個(gè)有效的途徑。

[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]曹鴻強(qiáng), 俏儂, 盧錫城.一種基于市場(chǎng)機(jī)制的計(jì)算網(wǎng)格資源分配方法[J].計(jì)算機(jī)研究與發(fā)展.2002, 39(8): 913-916

[4]李春林.基于投標(biāo)模型的計(jì)算網(wǎng)格資源分配的研究[J].武漢理工大學(xué)學(xué)報(bào).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

甘肅省科技攻關(guān)計(jì)劃項(xiàng)目2GS047-A52-002-04

10.3969/j.issn.1001-8972.2011.04.049

王維歡（1981-），女，甘肅蘭州人，碩士研究生，主要研究領(lǐng)域：分布與并行計(jì)算；

林曉嫻（1983-），女，甘肅蘭州人，碩士研究生，主要研究領(lǐng)域：分布與并行計(jì)算；

魏物春（1981-），男。甘肅蘭州人，教師。

網(wǎng)格；資源分配；競(jìng)價(jià)；效用函數(shù)