組合雙向拍賣協同融合的網格資源分配機制研究

包宋建

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

1 概述

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

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

2 組合拍賣理論

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

2.1 一對多組合拍賣

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

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

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

(1)

(2)

(3)

(4)

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

(5)

(6)

(7)

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

2.2 多對一組合拍賣

(8)

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

(9)

(10)

(11)

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

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

3.1 系統結構模型

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

圖1 雙向拍賣系統組成結構

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

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

4.1 問題描述

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

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

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

4.2 資源分配優化模型

(12)

(13)

(14)

(15)

(16)

(17)

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

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

表11 競標者競標參數表

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

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

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

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

(19)

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

(20)

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

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

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

(2) 查詢資源種類數量矩陣qi(m)，根據平均交易價格矩陣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) 將分配結果存儲到alloci和價格信息tpi中，判斷第s個用戶需求是否滿足

If 資源需求種類和數量都滿足

Goto step(4)

Else

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

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

If bl列表已到底

Exit;

Else

s = s +1; i = 1;

更新tpi,alloci,qi;

Goto step(2);

圖2 資源分配及定價算法

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

(21)

(22)

(4)根據資源分配結果將專業分別傳給相應的GSP，并按照(3)產生的價格信息進行收費。

5 仿真分析及性能評估

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

表12 參與者競拍參數

網格用戶序號服務提供者序號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

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

表13 資源提供者定價結果

賣方交易者序號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 交易用戶定價結果

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

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

圖3 用戶效益分析圖

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

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

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

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

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

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

圖5 用戶效用

圖6 資源效用

6 結論

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