包宋建

(重慶文理學院 電子電氣工程學院，重慶 402160)

1 概述

網(wǎng)格技術(shù)的發(fā)展，使得網(wǎng)格應(yīng)用的范圍從傳統(tǒng)的高性能計算和數(shù)據(jù)密集型應(yīng)用拓展到更廣泛的領(lǐng)域，在計算網(wǎng)格發(fā)展的同時，也就出現(xiàn)了其他各種類型的網(wǎng)格，比如數(shù)據(jù)網(wǎng)格、信息網(wǎng)格等等，隨著應(yīng)用潛力的挖掘，還會出現(xiàn)更多類型的網(wǎng)格。之所以有如此眾多的網(wǎng)格出現(xiàn)，其原因是網(wǎng)格技術(shù)提供各種資源的普遍共享和分布式協(xié)作。

資源種類繁多給網(wǎng)格中資源分配問題帶來了極大的挑戰(zhàn)，協(xié)同資源分配是極其有效的解決辦法[1]。網(wǎng)格經(jīng)濟的出現(xiàn)為網(wǎng)格的商業(yè)化奠定了基礎(chǔ)，采用基于拍賣的資源分配方法實現(xiàn)了同一種資源的高效分配，組合拍賣[2]實現(xiàn)了多種資源共同分配，體現(xiàn)了協(xié)同分配資源的思想。在此基礎(chǔ)上，本文提出了一種在網(wǎng)格環(huán)境下基于組合雙向拍賣協(xié)同融合的網(wǎng)格資源分配機制，設(shè)計了資源分配算法，并通過仿真驗證了該算法的性能。

2 組合拍賣理論

組合拍賣(Combinatorial auctions)[3-4]是拍賣的一種，與傳統(tǒng)拍賣不同，它是一種競價人可以對多種商品的組合進行競價的拍賣方式。組合拍賣適用于買方對商品價值衡量呈現(xiàn)非加性的情況，在分配多種商品時比傳統(tǒng)拍賣具有更高的效率。在文獻[5]中，作者將組合拍賣分成了一對多和多對一兩種，根據(jù)每種商品交易的數(shù)量又有單單元和多單元組合拍賣之分。

2.1 一對多組合拍賣

一對多組合拍賣有單單元組合拍賣(Single-Unit Combinatorial Auction)和多單元組合拍賣(multi-unit combinatorial auction)[5-6]之分。

在SUCA模式中，僅僅只有一個賣方，他擁有m種待出售的商品，可用集合M={I1,I2,...,Im}表示，每種商品是不可分割的，且數(shù)量只有一個。有n個潛在的買方，每個買方對這m種商品的一種或多種感興趣。B={b1,b2,...,bn}表示買方的競標集合，買方j(luò)的競標bj=，其中S為商品組合且S?M，pj,S是買方j(luò)購買該商品組合的競標價格。

單單元組合拍賣中競標獲勝者決策過程可用模型M1[5]描述：

(1)

(2)

(3)

(4)

其中，xj,S為0-1變量，代表買方競標獲勝與否，獲勝時xj,S=1，否則xj,S=0。δj,S=0表示服務(wù)組合S不包括商品i；δj,S=1表示商品i屬于服務(wù)組合S。限制條件式(2)確保一種商品最多分給一個買方，限制條件式(3)保證同一個商品組合不會同時賣給多個買方。式(1)為目標函數(shù)，其目的是使賣方在出售商品時獲得最大的經(jīng)濟利益。

(5)

(6)

(7)

公式(6)限制了對第k種商品的競標數(shù)量總和需少于提供的數(shù)量。

2.2 多對一組合拍賣

(8)

拍賣模型可用模型M3表示：

(9)

(10)

(11)

公式中變量xj代表競標成功與否，成功為1，否則為0。限制條件(10)保證買方所有的商品需求都能滿足，優(yōu)化目標(9)使購買商品所花的費用最少。

3 多單元雙向拍賣資源分配策略

3.1 系統(tǒng)結(jié)構(gòu)模型

在基于經(jīng)濟機制的網(wǎng)格資源分配過程中，資源提供者首先發(fā)布資源的相關(guān)屬性，比如計算能力、存儲能力、在線時間等，而網(wǎng)格用戶通過資源發(fā)現(xiàn)過程對資源進行篩選，尋找到滿足自身任務(wù)需求的可用資源。在這種情況下，價格是決定資源分配過程的唯一因素[7-8]。在拍賣模型中，價格主要表現(xiàn)在三個方面，用戶的競標價格、資源的要價標價格以及用戶和資源提供者的交易價格，在網(wǎng)格環(huán)境中，這些價格都具有動態(tài)變化性，因此，在拍賣系統(tǒng)結(jié)構(gòu)中，價格存儲功能對競標者是必不可少的，一方面，可用以存儲交易價格，為付費機制提供前提和保障；另一方面，可存儲當前競標價格，作為下一次競標的參考值，從而實現(xiàn)競標參與者的決策競標。同時，文獻[9]強調(diào)價格策略要體現(xiàn)用戶和資源的共同利益，因此，在實現(xiàn)資源分配過程中拍賣商必須具有交易價格確定功能。論文對原有的雙向拍賣模型進行了改進，加入了價格存儲模塊、交易者確定和交易價格確定功能模塊，拍賣系統(tǒng)框圖如圖1所示。

圖1 雙向拍賣系統(tǒng)組成結(jié)構(gòu)

在該模型中，為降低用戶和資源實體與拍賣系統(tǒng)交互的復(fù)雜性，雙方各自都采用軟件代理與系統(tǒng)進行信息交互，通過簡單方便的接口為用戶提供透明的資源視圖。由圖可知，系統(tǒng)中主要存在用戶代理、服務(wù)提供者代理、網(wǎng)格信息服務(wù)中心、網(wǎng)格市場拍賣商四類實體。

4 組合雙向拍賣協(xié)同融合的資源分配機制

4.1 問題描述

在這種情況下，如何同時兼顧用戶和資源提供者共同利益，將這些資源分配給用戶使用是一個值得研究的問題，借鑒雙向拍賣機制和組合拍賣的思想，采用基于組合雙向拍賣的資源協(xié)同分配方法來解決這個問題。該方法具有如下優(yōu)點：

(1)最大化資源提供者的利潤，能激發(fā)他們貢獻閑散的資源，豐富網(wǎng)格中資源的種類和數(shù)量。

(2)最小化用戶的費用，使其能享受網(wǎng)格帶來的便利性和經(jīng)濟性。

4.2 資源分配優(yōu)化模型

(12)

(13)

(14)

(15)

(16)

(17)

目標函數(shù)F使成功交易者競標價格差最大，表示競標價格高的用戶和要價低的資源提供者成為競標獲勝者，限制條件保證成交的用戶所需的各種資源數(shù)量都能由資源提供者提供。

現(xiàn)舉例說明上述模型，假設(shè)有3種資源，分別為r1,r2,r3，有5個競標者，包括3個用戶和2個資源提供者，他們的資源需求和價格如表1所示。

表11 競標者競標參數(shù)表

Bid1Bid2Bid3Bid4Bid5r1585-10-10r2302-10-5r3620-10-3P(G$)603545-40-20

則拍賣模型滿足：

Maximize60y1+35y2+45y3-40y4-20y5

Subject to 5y1+8y2+5y3-10y4-10y5≤0

3y+2y3-10y4-5y5≤0

6y1+2y2-10y4-3y5≤0

y1,y2,y3,y4,y5∈{0,1}

求解交易者過程就是求解模型中的0-1變量組合的過程。

4.3 定價及資源分配算法

在基于組合雙向拍賣的資源協(xié)同分配實施過程中，仍采用改進的雙向拍賣結(jié)構(gòu)框圖，如圖1所示。而資源分配及用戶應(yīng)用執(zhí)行流程為：(1)構(gòu)建競標并提交給網(wǎng)格拍賣商，用戶構(gòu)建競價標，資源提供者構(gòu)建要價標。(2)確定交易者及交易價格。拍賣商接收到用戶的競價標和資源提供者的要價標后按照預(yù)先制定的拍賣準則進行資源分配，并將競標結(jié)果返回給參與拍賣的資源消費者和資源提供者。(3)若競標成功，用戶方提交任務(wù)到資源上處理，資源方接收用戶的任務(wù)進行處理。若競標成功繼續(xù)執(zhí)行步驟(4)，否則轉(zhuǎn)到第(6)步。(4)任務(wù)處理完成后，資源提供者將處理結(jié)果發(fā)送給相應(yīng)的用戶。(5)收到任務(wù)處理結(jié)果后，用戶向資源提供者支付相應(yīng)的費用。(6)競標未成功的用戶或資源提供者提高競標價或降低要價重新組織競標準備參加下一次競標，即重復(fù)步驟(1)。

根據(jù)優(yōu)化模型M4求解出0-1序列yj，確定出后期交易者。這里主要討論定價及資源分配算法，其步驟詳細介紹如下：

(1)首先計算每個交易者的平均報價mpj，見式(19)所示，并將交易者按照買方(UB)和賣方(GSP)進行分類，其中買方按照平均報價由高到低排列得到用戶列表bl，賣方按照平均報價由低到高排列得到資源列表sl，然后再將sl按照資源種類進行分類，得到k個賣方列表sli，i∈{1,...,k}，且每個賣方列表對應(yīng)一個數(shù)量列表qi，其中k為資源種類。

(19)

(2)產(chǎn)生平均交易價格矩陣mtp，其中mtp(s,t)表示bl中第s個買方與sl中第t個賣方進行交易時的平均交易價格，計算公式表示如式(20)。

(20)

(3)按照買方列表bl中的先后順序進行資源分配及定價，直到所有買方交易者處理完畢為止，由此可以得到資源分配的具體情況以及相應(yīng)的價格信息。算法偽代碼表示如圖2所示。

輸入：B,bl,sl,sli,qi, 輸出：tpi,alloci,0

(1) 初始化：s = 1, i =1, tpi = [0], alloci =[0];

(2) 查詢資源種類數(shù)量矩陣qi(m)，根據(jù)平均交易價格矩陣mtp匹配用戶需求

m <-qi中非零量的一個資源的位置

t <-賣方列表sl中銷售者sli(m)的位置

If qi(m)≥atbl(s)

tpi (s,t) = tpi (s,t) + atbl(s) *mtp(s,t);

alloci (s,t) = alloci (s,t) + atbl(s);

qi (m) = qi (m) - atbl(s);

atbl(s) = 0;

goto step(3);

else

tpi (s,t) = tpi (s,t) + qi (m)*mtp(s,t);

alloci (s,t) = alloci (s,t) + qi (m);

atbl(s) = atbl(s) -qi (m);

qi (m) = 0;

repeat step(2);

(3) 將分配結(jié)果存儲到alloci和價格信息tpi中，判斷第s個用戶需求是否滿足

If 資源需求種類和數(shù)量都滿足

Goto step(4)

Else

i = i + 1; Goto step(2);

(4) 判斷是否所有用戶需求都滿足，分配結(jié)束與否

If bl列表已到底

Exit;

Else

s = s +1; i = 1;

更新tpi,alloci,qi;

Goto step(2);

圖2 資源分配及定價算法

其中alloci，tpi分表表示第i種資源的分配矩陣和價格矩陣，均為g行h列，分別對應(yīng)bl以及sl中買方和賣方的個數(shù)，alloci表示sl中第t個賣方提供給bl中第s個買方資源的數(shù)量，tpi(s,t)表示第t個賣方提供這些數(shù)量資源所收取的費用。定價結(jié)束后，得到tpb和tps兩個矢量分別表示各個買方應(yīng)支付以及各個賣方應(yīng)收取的總價格，且有

(21)

(22)

(4)根據(jù)資源分配結(jié)果將專業(yè)分別傳給相應(yīng)的GSP，并按照(3)產(chǎn)生的價格信息進行收費。

5 仿真分析及性能評估

由于GridSim包中僅僅提供對計算資源、存儲資源、網(wǎng)絡(luò)帶寬資源的模擬，因此，在未擴展其他資源建模能力時，本節(jié)仿真驗證過程中只采用這3種資源，為方便描述，假設(shè)其代號分別為R1、R2,和R3。系統(tǒng)中設(shè)置16個拍賣參與者，其中6個網(wǎng)格用戶和10個資源提供者，其參數(shù)設(shè)置如表2所示。

表12 參與者競拍參數(shù)

網(wǎng)格用戶序號服務(wù)提供者序號1 2 3 4 5 67 8 9 10 11 12 13 14 15 16R10 4 3 2 410-3-2 -1 -20-3-20-3R23 3 3 0 35 -2-2-3 -3 -2-1-30-3 -1R33 3 4 1 21 -2-3-1 00 -3-1-3-3 -1Price1041361443312593-59-110-80-36-38-70 -93 -71 -76-54

根據(jù)優(yōu)化模型M4可確定競拍結(jié)果，由仿真數(shù)據(jù)繪制表3與表4，分別代表資源提供者和用戶的交易對象及價格。

表13 資源提供者定價結(jié)果

賣方交易者序號78101112131516要價59110363870937654交易價56.5109.551.247.861.994.683.463.7支付對象序號2,5,62,3,5,61,33 2,62,3,51,3,51,3,5

表14 交易用戶定價結(jié)果

交易用戶序號競拍價交易價支付對象:序號(數(shù)量+種類,價格)110483.610(3R2,39.5)、 16(1R3,14.1)、15(2R3,30)2136139.813(2R1,3R2,67.2) 、8(2R1,27.4) 、7(1R3,14.2) 、12(1R3,14.3)3144127.610(1R1,11.7)、11(2R1,2R2,47.8)、16(1R2,12.6)、15(1R3,13.5)、13(1R3,13.8) 、8(2R3,28.2)5125118.616(3R1,37)、15(3R2,39.8) 、13(1R1,13.6) 、8(1R3,13.8)、7(1R3,14.3)6938(1R1,2R2,40.6)、7(2R2,28)、12(1R2,1R3,30.8)

由表3和表4可知，同一個資源提供者可以為不同的用戶提供服務(wù)，比如序號為8的提供者能同時為用戶2、3、5、6提供資源，同一種資源也可以提供給不同用戶使用，比如提供者15的第3種資源可以分配給用戶2個數(shù)量給用戶1，分配1個資源給用戶3。與此同時，用戶完成任務(wù)所需要的資源種類及數(shù)量往往來自不同的提供者，比如表4中為用戶3分配的資源來自多達6個提供者，這在一定程度上體現(xiàn)了多個提供者多種資源協(xié)同分配的思想。

根據(jù)分配及定價結(jié)果可分析拍賣策略對用戶和資源提供者的效益。不考慮競標者的競標策略，假設(shè)其均按實際估計報價，對于用戶，效益為競標價與交易價之差，對于資源方，效益為交易價格與競標要價之差。圖3為用戶效用估計圖。

圖3 用戶效益分析圖

由圖可知，用戶U1、U3、U5的競標價格低于交易價格，效用為正，說明資源分配及定價算法能夠減少這些用戶的費用；同時，U2和U6雖然能夠成功交易，但其效用為負值，在一定程度上對這些用戶具有不利的一面。之所以會出現(xiàn)這種原因主要是因為算法中按照資源平均價格由高到底進行資源分配，用戶U2和U6的單位資源競標價格分別為13.6和13.3，這在所有成交者中是最低的，因此在分配資源時他們沒有優(yōu)選選擇資源的權(quán)利，只有將所有競標價格高的用戶分配完畢后才能分配資源，而這些剩余資源往往要價比較高。這也說明了算法體現(xiàn)了交易用戶的利益，競標價格越高效用也越高，具有一定的風險補償性。

圖4 資源提供者效益分析圖

圖4為資源提供者效益分析圖，與用戶效益圖類似，資源擁有者也有出現(xiàn)負效用的情況，這是由于資源提供者報價太高而沒有被用戶首先選擇的原因造成的。同時，結(jié)合競標參數(shù)表和圖4可以分析出，資源平均報價越低的資源提供者具有的效益越高，這在一定程度上對資源方的低價出售的行為具有補償性。

雖然資源分配算法會對用戶方或資源擁有者帶來負效益，但具有負效用的用戶和資源提供者都是競標價格低和報價高的競標者，他們往往也是拍賣過程中的淘汰者，在拍賣結(jié)果返回時，他們可以根據(jù)自身效用情況決定是否進行交易。

為分析在資源分配過程中，交易者虧盈具體情況，進一步驗證分配策略的性能，對100個競標者進行分析，其中用戶和資源提供者各占一半，資源種類仍選擇3，競標者參數(shù)隨機產(chǎn)生。一般情況下，拍賣過程中要價比競價低，這里，設(shè)用戶競標價格在0到200之間，資源提供者要價在0到80之間隨機產(chǎn)生。網(wǎng)格中，用戶往往需要處理大量任務(wù)，需要的資源量比單個資源提供者的數(shù)量要多，因此，用戶對資源R1、R2和R3的需求量分別介于5到10，10到15，15到20之間；資源提供者對各種資源的提供數(shù)量分別介于3到6，6到9，9到12之間。各個競標者的競價要價及效益分析如圖5和圖6所示。

在此次模擬中，一共有31個用戶和43個資源提供者進行交易，資源分配成功率為74%。由圖可知，在大多數(shù)情況下，交易者的效益都為正，表明資源分配方法能夠兼顧買賣雙方的共同利益。在用戶方，僅有6個用戶的交易價格略高于競標價格，而在資源方，幾乎所有交易者都具有正效益。同時，也可以看出一般情況下，競標價格高的參與者往往能獲得更大的效用。

圖5 用戶效用

圖6 資源效用

6 結(jié)論

首先分析了組合拍賣的基本原理，然后針對網(wǎng)格應(yīng)用對多種資源協(xié)同分配的應(yīng)用場景需求，將雙向拍賣思想與組合拍賣相結(jié)合，提出了基于組合雙向拍賣的網(wǎng)格資源分配機制，在雙向拍賣系統(tǒng)結(jié)構(gòu)模型基礎(chǔ)上實現(xiàn)了模型優(yōu)化，使系統(tǒng)中買賣方的總收益最大化，將交易者確定過程轉(zhuǎn)化為0-1整數(shù)規(guī)劃問題以便求解。同時，給出了相應(yīng)的定價策略和資源分配策略，該算法考慮競標者競標價格形勢，能同時兼顧用戶和資源提供者的利益，具有補償性質(zhì)。最后，通過仿真驗證了算法的相關(guān)性能，說明了該算法思想具有較高的效率，能提高用戶和資源提供者的共同利益。