組合雙向拍賣協(xié)同融合的網(wǎng)格資源分配機(jī)制研究

包宋建

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

1 概述

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

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

2 組合拍賣理論

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

2.1 一對(duì)多組合拍賣

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

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

單單元組合拍賣中競(jìng)標(biāo)獲勝者決策過(guò)程可用模型M1[5]描述：

(1)

(2)

(3)

(4)

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

(5)

(6)

(7)

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

2.2 多對(duì)一組合拍賣

(8)

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

(9)

(10)

(11)

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

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

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

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

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

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

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

4.1 問(wèn)題描述

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

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

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

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

(12)

(13)

(14)

(15)

(16)

(17)

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

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

表11 競(jìng)標(biāo)者競(jìng)標(biāo)參數(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}

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

4.3 定價(jià)及資源分配算法

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

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

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

(19)

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

(20)

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

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

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

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

m <-qi中非零量的一個(gè)資源的位置

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é)果存儲(chǔ)到alloci和價(jià)格信息tpi中，判斷第s個(gè)用戶需求是否滿足

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 資源分配及定價(jià)算法

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

(21)

(22)

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

5 仿真分析及性能評(píng)估

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

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

網(wǎng)格用戶序號(hào)服務(wù)提供者序號(hào)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可確定競(jìng)拍結(jié)果，由仿真數(shù)據(jù)繪制表3與表4，分別代表資源提供者和用戶的交易對(duì)象及價(jià)格。

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

賣方交易者序號(hào)78101112131516要價(jià)59110363870937654交易價(jià)56.5109.551.247.861.994.683.463.7支付對(duì)象序號(hào)2,5,62,3,5,61,33 2,62,3,51,3,51,3,5

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

交易用戶序號(hào)競(jìng)拍價(jià)交易價(jià)支付對(duì)象:序號(hào)(數(shù)量+種類,價(jià)格)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可知，同一個(gè)資源提供者可以為不同的用戶提供服務(wù)，比如序號(hào)為8的提供者能同時(shí)為用戶2、3、5、6提供資源，同一種資源也可以提供給不同用戶使用，比如提供者15的第3種資源可以分配給用戶2個(gè)數(shù)量給用戶1，分配1個(gè)資源給用戶3。與此同時(shí)，用戶完成任務(wù)所需要的資源種類及數(shù)量往往來(lái)自不同的提供者，比如表4中為用戶3分配的資源來(lái)自多達(dá)6個(gè)提供者，這在一定程度上體現(xiàn)了多個(gè)提供者多種資源協(xié)同分配的思想。

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

圖3 用戶效益分析圖

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

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

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

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

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

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

圖5 用戶效用

圖6 資源效用

6 結(jié)論

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