基于雙向拍賣的適應(yīng)性云計(jì)算資源分配機(jī)制

丁丁，羅四維，艾麗華

（北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044）

1 引言

隨著網(wǎng)格計(jì)算、普適計(jì)算以及計(jì)算機(jī)通信技術(shù)的快速發(fā)展，人們越來越希望能把資源、軟件及應(yīng)用更好地整合在一起，并以服務(wù)的形式向外提供給用戶，因此云計(jì)算應(yīng)運(yùn)而生[1,2]。云計(jì)算的優(yōu)勢在于平臺(tái)整合了大量資源，并且可以按照用戶的實(shí)際需求提供規(guī)模可變的資源[3]，這給用戶帶來方便的同時(shí)，也對資源分配和調(diào)度技術(shù)提出了更高的要求，使得資源分配和任務(wù)調(diào)度成為云計(jì)算研究中的一個(gè)熱點(diǎn)與難點(diǎn)問題。

經(jīng)濟(jì)學(xué)中的市場機(jī)制能夠充分激勵(lì)和調(diào)動(dòng)個(gè)體的積極性，在商品生產(chǎn)和交換中實(shí)現(xiàn)合理的社會(huì)資源配置，有效提高社會(huì)生產(chǎn)率[4]，而由各個(gè)高異構(gòu)性和動(dòng)態(tài)性節(jié)點(diǎn)構(gòu)成的云計(jì)算環(huán)境與現(xiàn)實(shí)經(jīng)濟(jì)社會(huì)具有極大的相似性，借助經(jīng)濟(jì)學(xué)中相關(guān)概念和方法解決云計(jì)算環(huán)境中的資源管理具有可行性和優(yōu)越性[5,6]。目前，可以通過服務(wù)價(jià)格協(xié)商、出售服務(wù)以實(shí)現(xiàn)資源分配的經(jīng)濟(jì)模型包括商品市場模型、標(biāo)價(jià)模型、議價(jià)模型、投標(biāo)模型、按比例分配資源模型、拍賣模型、壟斷模型等[7～9]。由于拍賣模型對全局信息的需求較少，而且具有分布式的結(jié)構(gòu)并易于實(shí)現(xiàn)，基于拍賣的資源分配引起了極大的關(guān)注。

最早把拍賣機(jī)制應(yīng)用到資源分配中的工作可以追溯到1968年Sutherland針對于PDP-1機(jī)器中的研究[10]，隨后被更多地應(yīng)用于集群和分布式系統(tǒng)的負(fù)載均衡問題。然而，這些研究工作大多側(cè)重于資源分配系統(tǒng)的實(shí)現(xiàn)，因此只采用了基本的拍賣策略，并沒有對拍賣機(jī)制本身進(jìn)行深入的研究。隨著網(wǎng)格經(jīng)濟(jì)的出現(xiàn)，拍賣機(jī)制被廣泛應(yīng)用在網(wǎng)格的資源分配中[11,12]，并很快引起了重視。同以往的資源分配模型相比，基于拍賣機(jī)制的網(wǎng)格資源分配模型具有明顯的優(yōu)勢，為云計(jì)算資源分配中拍賣機(jī)制的應(yīng)用奠定了良好的研究基礎(chǔ)。如今，針對云計(jì)算的特點(diǎn)，廣大研究者也紛紛就基于拍賣機(jī)制的資源分配問題展開了一系列的研究。文獻(xiàn)[13]提出的連續(xù)雙向拍賣框架下基于納什均衡的云資源分配策略以及文獻(xiàn)[14]提出的連續(xù)雙向拍賣框架下基于知識(shí)的云資源分配策略，都能夠滿足云計(jì)算環(huán)境下資源的有效分配。文獻(xiàn)[15]則在連續(xù)雙向拍賣的基礎(chǔ)上提出了連續(xù)逆向拍賣，并將其成功應(yīng)用在云計(jì)算環(huán)境下的資源分配中。文獻(xiàn)[16]和文獻(xiàn)[17]致力于在CloudSim中應(yīng)用不同的拍賣機(jī)制以適應(yīng)云計(jì)算環(huán)境下虛擬化資源的優(yōu)化分配。另外，雙向拍賣還被應(yīng)用到工作流調(diào)度和資源協(xié)同分配中[18]。然而，目前的云計(jì)算資源拍賣策略大多是直接使用經(jīng)濟(jì)學(xué)中已有的拍賣理論，以最大化買賣雙方的經(jīng)濟(jì)效益為目標(biāo)，忽略了資源利用率、資源性能、用戶滿意度等指標(biāo)，具有一定的局限性。本文對基于經(jīng)濟(jì)機(jī)制的云計(jì)算資源分配問題進(jìn)行進(jìn)一步的研究，提出了一種基于雙向拍賣的適應(yīng)性云計(jì)算資源分配機(jī)制，在兼顧經(jīng)濟(jì)效益的同時(shí)提高用戶滿意度及云計(jì)算系統(tǒng)的資源利用率。

2 拍賣市場框架

本文采用的拍賣市場框架如圖1所示。在這個(gè)框架中，3個(gè)主要的角色是云資源提供者CRS（cloud resource seller）、云資源消費(fèi)者（cloud resource buyer）和云資源拍賣師（cloud resource auctioneer），分別采用賣方代理、買方代理和拍賣代理來代表賣方、買方和拍賣師參與市場中的拍賣交易。

圖1 拍賣市場的基本框架

文中的拍賣市場采用離散時(shí)間拍賣模型，由拍賣代理以固定時(shí)間間隔組織雙向拍賣。買方和賣方分別根據(jù)自身的需要通過買方代理和賣方代理向拍賣代理提出自己的交易請求（任何一個(gè)買方代理或者賣方代理都不知道其他代理的交易請求）。在收到來自于買方代理和賣方代理的交易請求后，拍賣代理根據(jù)某種雙向拍賣規(guī)則確定成交的買方和賣方以及成交的商品數(shù)量和成交價(jià)格。最后，成交的買方和賣方分別根據(jù)最終確定的成交商品數(shù)量和成交價(jià)格完成系統(tǒng)的資源配置。

3 適應(yīng)性雙向拍賣機(jī)制

3.1 問題的提出

在上述的雙向拍賣市場中，假設(shè)買方i想要購買的商品數(shù)量記為Di，賣方j(luò)想要出售的商品數(shù)量記為Sj。買方i為購買單位商品所能支付的最高價(jià)格記為rbi，賣方j(luò)為出售單位商品所能接受的最低價(jià)格記為rsj。傳統(tǒng)的多數(shù)量雙向拍賣策略為了最大化整個(gè)市場的收益，即最大化所有成交者的收益之和，把商品需求量按照價(jià)格由高到低的順序排列，把商品供應(yīng)量按照價(jià)格由低到高的順序排列，并嘗試找到能夠使得商品的供應(yīng)數(shù)量和需求數(shù)量相等的競爭平衡CE（competitive equilibrium）價(jià)格p*。一個(gè)典型的例子如圖2所示。

圖2 多數(shù)量雙向拍賣市場中K個(gè)買方和L個(gè)賣方成功交易

從圖2中可以看到競爭平衡價(jià)格p*介于rbK和rsL之間（若二者相交為一線段，則擇取其中點(diǎn)）。那么所有在K之前的買方和在L之前的賣方可以成功交易，并且所有商品的成交價(jià)格定為p*。然而，這種拍賣策略存在以下幾方面的不足。

1) 交易者的收益得不到明確的保證。由于競爭平衡價(jià)格由所有拍賣參與者共同決定，因此，在交易完成之前，無論是買方還是賣方都無法預(yù)測最終的交易價(jià)格，市場無法保證每一個(gè)交易者的收益。

2) 對于不同的賣方來說，它們獲取商品的成本可能會(huì)有所不同，因此所期望的賣價(jià)不同。同理，相同的商品可能會(huì)給不同的買方創(chuàng)造不同的價(jià)值，因此不同的買方所期望的買價(jià)也會(huì)有差異。顯然，傳統(tǒng)拍賣策略的統(tǒng)一定價(jià)機(jī)制無法保證所有交易者對成交價(jià)格的滿意度。

3) 為了最大化交易者的經(jīng)濟(jì)收益，傳統(tǒng)的拍賣策略傾向于使出價(jià)和要價(jià)相差較大的買方和賣方成交，這會(huì)大大降低商品的成交量，導(dǎo)致較低的商品利用率。以圖2為例，盡管存在一些買方的出價(jià)（如rb1、rb2、…、rbK-1）在第L+1個(gè)賣方的要價(jià)rsL+1之上，但是第L+1個(gè)賣方仍然不能成交。

由此可見，傳統(tǒng)的拍賣策略并不適用于以服務(wù)用戶為主要目的的云計(jì)算環(huán)境下的資源分配，為此，提出一種適應(yīng)性雙向拍賣機(jī)制，在保證用戶不同服務(wù)質(zhì)量要求的前提下，盡量滿足更多的云計(jì)算用戶，同時(shí)提高云計(jì)算系統(tǒng)的資源利用率。

3.2 適應(yīng)性雙向拍賣機(jī)制

3.2.1 定價(jià)策略

令Bi=(bpi,bqi)表示買方的購買請求，其中，bpi表示買方i購買單位資源的出價(jià)（bidding price），bqi表示買方i所需求資源的數(shù)量；Sj=(spj,sqj)表示賣方的出售請求，其中，spj表示賣方j(luò)出售單位資源的要價(jià)（asking price），sqj表示賣方j(luò)所出售資源的數(shù)量。在本文提出的適應(yīng)性雙向拍賣機(jī)制ADAM (adaptive double auction mechanism)中，拍賣市場把交易的價(jià)格和交易的數(shù)量看成是市場參與者的服務(wù)質(zhì)量要求，并依據(jù)盡量滿足的原則提供服務(wù)。因此，為保證市場參與者服務(wù)質(zhì)量的要求，采用的定價(jià)策略如下。

買方i的出價(jià)bpi等于買方i使用單位資源所能創(chuàng)造的價(jià)值cvi減去買方i所期望的收益pbi；那么如果買方i能夠成功交易，收益如式(1)所示。

賣方j(luò)的要價(jià)spj等于賣方j(luò)向市場提供單位資源所需的成本hcj加上賣方j(luò)所期望的收益psj。如果賣方j(luò)能夠成功交易，收益如式（2）所示。

這樣，ADAM按照每個(gè)市場參與者請求的價(jià)格和數(shù)量進(jìn)行交易，一方面避免了買方即云計(jì)算用戶對成交價(jià)格的不滿，另一方面，也保證了賣方即資源提供者的收益。

3.2.2 分配策略

為了滿足更多的市場參與者（包括買方和賣方），ADAM根據(jù)資源不同的供求關(guān)系分3種情況應(yīng)用不同的拍賣規(guī)則。

1) 供過于求的情況

供過于求的情況指的是拍賣市場中資源的供應(yīng)量大于需求量。在這種情況下，把買方請求的資源需求量和賣方請求的資源供應(yīng)量按照價(jià)格由高到低的順序排列（為了減少交易的工作量，刪除那些不可能成功交易的賣方請求，即要價(jià)高于所有買方出價(jià)的賣方請求），則供過于求時(shí)的買方賣方曲線如圖3所示。

在圖3中，存在一些買方曲線和賣方曲線的交叉點(diǎn)。將這些交叉點(diǎn)分為2類，稱為上升交叉點(diǎn)UCP（up-crossing point）和下降交叉點(diǎn)DCP（downcrossing point）。

① 上升交叉點(diǎn)：假設(shè)買方請求BK與賣方請求SL相交于某交叉點(diǎn)，當(dāng)不等式(3)和不等式(4)成立時(shí)，該交叉點(diǎn)為上升交叉點(diǎn)

圖3 供過于求的情況

上升交叉點(diǎn)意味著自該點(diǎn)之后，賣方的要價(jià)將高于買方的出價(jià)，因此，稱BK和SL為上升關(guān)鍵請求。

② 下降交叉點(diǎn)：如果上升交叉點(diǎn)已經(jīng)存在，假設(shè)買方請求BE與賣方請求SF也相交于某交叉點(diǎn)，當(dāng)不等式（5）和不等式（6）成立時(shí)，該交叉點(diǎn)為下降交叉點(diǎn)

下降交叉點(diǎn)意味著自該點(diǎn)之后，賣方的要價(jià)將低于買方的出價(jià)，因此，稱BE和SF為下降關(guān)鍵請求。

在供過于求的情況下，采用的拍賣規(guī)則如圖4所示。

在圖4所示的拍賣規(guī)則中，do循環(huán)1)～5)對上升交叉點(diǎn)和下降交叉點(diǎn)同時(shí)存在的情況進(jìn)行處理。上升交叉點(diǎn)和下降交叉點(diǎn)同時(shí)存在即在上升交叉點(diǎn)和下降交叉點(diǎn)之間賣方請求的要價(jià)要高于這一區(qū)間的買方請求的出價(jià)，而這一部分的賣方請求是無法得到滿足的，因此，通過找到第一上升交叉點(diǎn)和第一下降交叉點(diǎn)以及相應(yīng)的關(guān)鍵請求來刪除這些賣方請求。這樣做的依據(jù)是因?yàn)樵诠┻^于求的情況下，資源的供應(yīng)量大于資源的需求量，可以犧牲一些賣方請求來滿足更多的買方請求。循環(huán)這個(gè)過程，直到不再同時(shí)出現(xiàn)上升交叉點(diǎn)和下降交叉點(diǎn)為止。上升交叉點(diǎn)與下降交叉點(diǎn)不同時(shí)存在的情況只有2種，一種是不再存在任何的上升交叉點(diǎn)，當(dāng)然也就沒有任何的下降交叉點(diǎn)；另外一種是只存在上升交叉點(diǎn)而不存在下降交叉點(diǎn)。

圖4 供過于求情況下的拍賣規(guī)則

不存在任何的上升交叉點(diǎn)的情況意味著所有賣方請求的要價(jià)都在所有的買方請求的出價(jià)之下，在第6)～15)步對其進(jìn)行處理。在這種情況下，需要根據(jù)買方請求和賣方請求總體數(shù)量的不同找到可交易的買賣方請求。如果此時(shí)賣方請求出售的總體數(shù)量大于買方請求購買的總體數(shù)量（如圖5（a）所示），則找到出售的總體數(shù)量大于買方請求購買的總體數(shù)量，且與買方請求購買的總體數(shù)量最接近的邊緣賣方請求SM，這之前的所有買賣請求都可以成功交易。但為了避免出現(xiàn)賣方最終出售的總體數(shù)量大于買方最終購買的總體數(shù)量的現(xiàn)象，減少賣方請求出售的數(shù)量，使賣方最終出售的總體數(shù)量與買方最終購買的總體數(shù)量相等。具體采用的策略是讓所有交易的賣方請求按比例承擔(dān)這部分減少的交易數(shù)量。事實(shí)上，當(dāng)成交的賣方請求足夠多時(shí)，對每一個(gè)賣方請求而言這種影響是可以忽略不計(jì)的。對于賣方請求出售的總體數(shù)量小于買方請求購買的總體數(shù)量的情況（如圖5（b）所示），同樣需要找到相應(yīng)的邊緣買方請求BM，這之前的所有買賣請求也都可以成功交易。但是在交易的數(shù)量上，需要考慮的是減少買方請求的購買數(shù)量，具體采用的策略是讓所有交易的買方請求按比例承擔(dān)這部分減少的交易數(shù)量。

圖5 不存在上升交叉點(diǎn)

只存在上升交叉點(diǎn)而不存在下降交叉點(diǎn)的情況表明在上升交叉點(diǎn)之前所有賣方請求的要價(jià)都在所有的買方請求的出價(jià)之下，在上升交叉點(diǎn)之后所有賣方請求的要價(jià)都在所有的買方請求的出價(jià)之上（如圖6所示），顯然，這部分賣方請求也是無法得到滿足的。在第16)～25)步對其進(jìn)行處理。在這種情況下，為了避免出現(xiàn)交易者所請求的交易資源量部分成交的現(xiàn)象，本文只對位于上升交叉點(diǎn)之前的K-1個(gè)買方請求和L-1個(gè)賣方進(jìn)行交易。而如何決定這些成功交易的買賣方請求的價(jià)格和數(shù)量的策略與不存在任何的上升交叉點(diǎn)的情況相同，這里不再贅述。

圖6 只存在上升交叉點(diǎn)不存在下降交叉點(diǎn)

2) 供不應(yīng)求的情況

供不應(yīng)求的情況指的是拍賣市場中資源的供應(yīng)量小于需求量。與供過于求的情況不同，在供不應(yīng)求的情況下，把買方請求的資源需求量和賣方請求的資源供應(yīng)量按照價(jià)格由低到高的順序排列，則供不應(yīng)求時(shí)的買方賣方曲線如圖7所示。

圖7 供不應(yīng)求的情況

在圖7中，同樣存在一些買方曲線和賣方曲線的上升交叉點(diǎn)和下降交叉點(diǎn)。這些上升交叉點(diǎn)與下降交叉點(diǎn)的含義與供過于求的情況相同。

在供不應(yīng)求的情況下，ADAM采用的拍賣規(guī)則與供過于求的情況類似，唯一不同的就是在供不應(yīng)求的情況下，資源的需求量大于資源的供應(yīng)量，因此，可以犧牲一些買方請求來滿足更多的賣方請求，具體的拍賣規(guī)則這里不再詳述。

3) 供求平衡的情況

供求平衡的情況指的是拍賣市場中資源的供應(yīng)量等于需求量。對于這種情況分別采用供過于求和供不應(yīng)求情況下的拍賣規(guī)則，哪種方法產(chǎn)生的交易量更大就采用哪種拍賣規(guī)則。

4 性能分析

一種有效的多數(shù)量雙向拍賣機(jī)制應(yīng)滿足以下幾個(gè)特點(diǎn)[11]：策略性防偽（strategy-proof）、預(yù)算平衡（budget-balanced）和個(gè)人理性（individual rational）?？梢宰C明，即使在買方請求和賣方請求的價(jià)格和數(shù)量均為保密信息的前提下，本文提出的適應(yīng)性雙向拍賣機(jī)制ADAM也滿足這些特點(diǎn)。

性質(zhì)1 適應(yīng)性雙向拍賣機(jī)制ADAM是預(yù)算平衡的。

證明 在ADAM中，無論是供過于求的情況還是供不應(yīng)求的情況，所有成功交易的賣方曲線都位于買方曲線之下。假設(shè)在拍賣中M個(gè)買方和N個(gè)賣方最終成交，可以得到式（7）

即在ADAM下，所有市場參與者的支出和收入總和大于零，因此，適應(yīng)性雙向拍賣機(jī)制ADAM是弱預(yù)算平衡的。事實(shí)上，弱預(yù)算平衡對于拍賣機(jī)制來說更加適用，因?yàn)檫@一部分收益通常被市場經(jīng)營者收取，作為管理市場的費(fèi)用。顯然，非負(fù)的收益恰恰反映了市場的存在。

性質(zhì)2 適應(yīng)性雙向拍賣機(jī)制ADAM是個(gè)人理性的。

證明 在ADAM中，按照每個(gè)市場參與者請求的價(jià)格和數(shù)量進(jìn)行交易，因此，如果能夠成功交易，市場參與者必然能夠獲得自己所期望的收益；如果不能參與交易，則該市場參與者的收益為0。也就是說，所有市場參與者參與市場拍賣的收益為非負(fù)，因此，適應(yīng)性雙向拍賣機(jī)制ADAM是個(gè)人理性的。

性質(zhì)3 適應(yīng)性拍賣機(jī)制ADAM對于每一個(gè)市場參與者的交易價(jià)格和交易數(shù)量都是策略性防偽的。

證明 假設(shè)在供過于求的情況下，賣方請求SL為了獲得更多的收益而謊報(bào)了自己的交易價(jià)格，而其他賣方請求保持交易價(jià)格不變。根據(jù)式（2），如果賣方請求SL把自己的價(jià)格報(bào)高了d，那么它得到的收益為(spL+d-hcL)sqL，獲得了一個(gè)大小為dsqL的額外收益。如果它繼續(xù)提高自己的要價(jià)，最終把價(jià)格報(bào)高了一個(gè)量e，使得spL+e＞bpK（如圖8所示），那么根據(jù)供過于求的拍賣規(guī)則它將被剝奪成功交易的機(jī)會(huì)，實(shí)際的收益為0。因此，盡管通過報(bào)高要價(jià)可能獲得額外的收益，但是在ADAM下對賣方代理來說這種謊報(bào)策略很難實(shí)現(xiàn)。這是由于交易代理之間關(guān)于交易請求是互相透明的，一個(gè)賣方代理根本不知道最終哪些請求會(huì)成功交易，更不用說出價(jià)剛好在自己要價(jià)之上的買方請求。因此一個(gè)賣方無法決定應(yīng)該把價(jià)格謊報(bào)多少，而隨機(jī)地報(bào)高價(jià)格反而會(huì)減少自己的收益。同樣的證明過程也可應(yīng)用于買方故意謊報(bào)自己出價(jià)的情況。因此，適應(yīng)性雙向拍賣機(jī)制ADAM對于每一個(gè)市場參與者的交易價(jià)格是策略性防偽的。

圖8 賣方L報(bào)高了交易價(jià)格，其他賣方保持不變

對于交易數(shù)量，同樣在供過于求的情況下，賣方請求SF為了獲得更多的收益而謊報(bào)了自己的交易數(shù)量，而其他賣方請求保持交易數(shù)量不變。根據(jù)式(2)，如果賣方請求SF把自己的數(shù)量報(bào)高了d’，那么它得到的收益為(spF-hcF)(sqF+d')，獲得了一個(gè)大小為(spF-hcF)d'的額外收益。如果它繼續(xù)提高自己的交易數(shù)量，最終把數(shù)量報(bào)高了一個(gè)量e’，使得（如圖9所示），那么根據(jù)供過于求的拍賣規(guī)則它將被剝奪成功交易的機(jī)會(huì)，實(shí)際的收益為0。因此，盡管通過報(bào)高交易數(shù)量可能獲得額外的收益，但是在ADAM下對賣方代理來說這種謊報(bào)策略也很難實(shí)現(xiàn)（道理與謊報(bào)交易價(jià)格相同）。同樣的證明過程也可應(yīng)用于買方故意謊報(bào)自己交易數(shù)量的情況。因此，適應(yīng)性雙向拍賣機(jī)制ADAM對于每一個(gè)市場參與者的交易數(shù)量也是策略性防偽的。

圖9 賣方F報(bào)高了交易數(shù)量，其他賣方保持不變

5 模擬實(shí)驗(yàn)及結(jié)果分析

5.1 實(shí)驗(yàn)設(shè)置

模擬實(shí)驗(yàn)中用到的主要參數(shù)設(shè)置如下。

1) 買方請求的交易價(jià)格服從均勻分布U(20,60)，賣方請求的交易價(jià)格服從均勻分布U(50, 100)。

2) 買方請求和賣方請求的交易數(shù)量服從均勻分布U(10,100)。

所有的實(shí)驗(yàn)結(jié)果數(shù)據(jù)均取1 000次相同實(shí)驗(yàn)的平均值。

5.2 實(shí)驗(yàn)結(jié)果與分析

參照文獻(xiàn)[12]中的方法，本文設(shè)計(jì)了2組模擬實(shí)驗(yàn)，第一組實(shí)驗(yàn)將本文提出的適應(yīng)性雙向拍賣機(jī)制ADAM與文獻(xiàn)[11]提出的多數(shù)量雙向拍賣機(jī)制（記為MDAM）在市場參與者的滿意度（包括買方滿意度和賣方滿意度）方面進(jìn)行比較，第二組實(shí)驗(yàn)對ADAM本身的經(jīng)濟(jì)效率進(jìn)行分析。

1) 買方滿意度和賣方滿意度

通過設(shè)置m＜n來模擬供過于求的情況；設(shè)置m＞n來模擬供不應(yīng)求的情況。采用的(m,n)值分別為(20,180)、(40,160)、(60,140)、(80,120)、(100,100)、(120,80)、(140,60)、(160,40)、(180,20)。不同買賣方個(gè)數(shù)差別下的買方滿意度和賣方滿意度分別如圖10和圖11所示。

圖10 不同買賣方個(gè)數(shù)差別下的買方滿意度

圖11 不同買賣方個(gè)數(shù)差別下的賣方滿意度

從圖10和圖11中可以看出，隨著(m-n)的值從-160增加到0，2種機(jī)制的買方滿意度和賣方滿意度都在增加，當(dāng)m= n時(shí)達(dá)到最大值，之后，隨著(m-n)的值從0增加到160，2種機(jī)制的買方滿意度和賣方滿意度又都在減少。這是因?yàn)樵谀M實(shí)驗(yàn)中，m= n意味著資源供求平衡的情況，相對于供過于求的情況和供不應(yīng)求的情況，相等的資源供應(yīng)量和資源需求量不會(huì)特別地缺少資源的買方或者資源的賣方，因此能夠促成更多的交易。

但是，比較提出的適應(yīng)性雙向拍賣機(jī)制ADAM和傳統(tǒng)的雙向拍賣機(jī)制MDAM，無論是在(m-n)的值從-160增加到0的過程中應(yīng)用供過于求情況下的拍賣規(guī)則，還是在(m-n)從0增加到160時(shí)應(yīng)用供不應(yīng)求情況下的拍賣規(guī)則，ADAM機(jī)制下的買方滿意度和賣方滿意度都明顯高于MDAM機(jī)制下的買方滿意度和賣方滿意度。這是因?yàn)锳DAM機(jī)制會(huì)根據(jù)市場中商品不同的供求關(guān)系應(yīng)用不同的拍賣規(guī)則，從而能夠滿足更多的買方請求和賣方請求。因此ADAM不但能夠滿足更多的云計(jì)算用戶，而且可以促成更多的資源成交，提高系統(tǒng)的資源利用率。

2) 經(jīng)濟(jì)效率

在ADAM下，每個(gè)市場參與者的收益，即買方收益和賣方收益，分別在買方的出價(jià)和賣方的要價(jià)中得到體現(xiàn)（參見式(1)和式(2)）。假設(shè)在拍賣中M個(gè)買方和N個(gè)賣方最終成交，則所有成功交易市場參與者的整體收益PT（profit of traders）可由式(8)得到。

而市場經(jīng)營者的收益PMM（profit of market maker）是所有成功交易的買賣方收益之間的差值，具體可由式(9)得到。

那么市場的經(jīng)濟(jì)效率EM（efficiency of market）就可以表示為

可見，市場的經(jīng)濟(jì)效率與買方使用單位資源所能創(chuàng)造的價(jià)值cv和賣方向市場提供單位資源所需的成本hc有關(guān)。假設(shè)hc服從均勻分布U(40,80)，圖12給出了當(dāng)cv分別服從均勻分布U(20,60)，U(40,80)和U(60,100)時(shí)，ADAM的經(jīng)濟(jì)效率。

從圖12中可以看出，隨著市場參與者數(shù)量的增加，ADAM的經(jīng)濟(jì)效率逐漸接近100%，因此ADAM是漸進(jìn)有效的（asymptotically efficient），適用于具有大量用戶的云計(jì)算環(huán)境。而且隨著cv由U(20,60)變化到U(40,80)，再變化到U(60,100)，ADAM的經(jīng)濟(jì)效率也在提高。這可以由式(10)來解釋。當(dāng)買方使用單位資源所能創(chuàng)造的價(jià)值cv相對賣方向市場提供單位資源所需的成本hc在升高時(shí)，即式（10）中第二項(xiàng)的分母增大時(shí)，會(huì)減小，因此，相應(yīng)的效率增加，這符合經(jīng)濟(jì)活動(dòng)中的實(shí)際情況。事實(shí)上，從市場參與者的角度來看，所有市場參與者只看重自己能得到的收益，而把市場經(jīng)營者所得到的收益，即式(10)中的第二項(xiàng)看成是一種效率的損失（efficiency loss）。因此，效率的損失越小，拍賣市場的經(jīng)濟(jì)效率越高。

圖12 不同cv下的經(jīng)濟(jì)效率

6 結(jié)束語

云計(jì)算的目的就是實(shí)現(xiàn)協(xié)同工作和資源共享，而云計(jì)算環(huán)境中各式各樣資源體現(xiàn)出來的異構(gòu)性和動(dòng)態(tài)性以及用戶需求的多樣性，使得云計(jì)算環(huán)境下的資源管理變得異常復(fù)雜。經(jīng)濟(jì)機(jī)制作為一種靈活、有效的資源分配方法為云計(jì)算環(huán)境下資源分配問題提供了解決問題的新思路，得到了廣泛的關(guān)注和應(yīng)用，具有巨大的發(fā)展?jié)摿Α?/p>

本文對基于經(jīng)濟(jì)機(jī)制的云計(jì)算資源分配問題進(jìn)行進(jìn)一步的研究，提出一種基于雙向拍賣的適應(yīng)性云計(jì)算資源分配機(jī)制ADAM，ADAM把交易的價(jià)格和交易的數(shù)量看成是市場參與者的服務(wù)質(zhì)量要求，在保證市場參與者收益的基礎(chǔ)上，根據(jù)資源不同的供求關(guān)系應(yīng)用不同的拍賣規(guī)則，盡量滿足更多的市場參與者。模擬實(shí)驗(yàn)表明，ADAM能夠顯著提高用戶滿意度和云計(jì)算系統(tǒng)的資源利用率，并且隨著市場參與者數(shù)量的增加，ADAM的經(jīng)濟(jì)效率也在不斷提高，非常適合于具有大量用戶和資源的云計(jì)算環(huán)境。而且，可以證明，即使在請求價(jià)格和請求數(shù)量均為保密信息的強(qiáng)約束條件下，ADAM也具有策略性防偽、預(yù)算平衡和個(gè)人理性的特點(diǎn)。

[1] FOSTER I, ZHAO Y, RAICU I, etal. Cloud Computing and Grid Computing 360-Degree Compared[M]. New York: IEEE Press, 2008.

[2] ARMBRUST M, FOX A, GRIFFITH R, etal. A view of cloud computing[J]. Communications of the ACM, 2010, 53(4):50-58.

[3] 陳賡, 鄭緯民. 云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[J]. 軟件學(xué)報(bào), 2009,20(5):1337-1348.CHEN K, ZHENG W M. Cloud computing: system instances and current research[J]. Journal of Software, 2009, 20(5):1337-1348.

[4] 平新喬. 平新喬講義系列：微觀經(jīng)濟(jì)學(xué)十八講[M]. 北京：北京大學(xué)出版社, 2001.PING X Q. PING Xinqiao Lecture Series: Eighteen Speak on Microeconomics[M]. Beijing: Peking University Press, 2001.

[5] BUYYA R, YEO C S, VENUGOPAL S. Market-oriented cloud computing: vision, hype, and reality for delivering IT services as computing utilities[A]. The 10th IEEE International Conference on High Performance Computing and Communications(HPCC’08)[C]. Los Alamitos,CA, USA, 2008.5-13.

[6] BUYYA R, YEO C S, VENUGOPAL S, etal. Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems, 2009,25(6):599-616.

[7] BUYYA R, STOCKINGER H, GIDDY J, etal. Economic models for management of resources in peer-to-peer and grid computing[A].Technical Track on Commercial Applications for High-Performance Computing, SPIE International Symposium on The Convergence of Information Technologies and Communications (ITCom’01)[C]. Denver, Colorado, USA, 2001.13-25.

[8] BUYYA R, ABRAMSON D, GIDDY J, etal. Economic models for resource management and scheduling in grid computing[J]. The Journal of Concurrency and Computation: Practice and Experience, 2002,14(13): 1507-1542.

[9] BUYYA R. Economic-Based Distributed Resource Management and Scheduling for Grid Computing[D]. Melbourne: School of Computer Science and Software Engineering, Monash University, 2002.

[10] SUTHERLAND I E. A futures market in computer time[J]. Communications of the ACM, 1968, 11(6): 449-451.

[11] HUANG P, SCHELLER-WOLF A, SYCARE K. Design of a multi-unit double auction e-market[J]. Computational Intelligence,2002, 18(4): 596-617.

[12] 翁楚良, 陸鑫達(dá). 一種基于雙向拍賣機(jī)制的計(jì)算網(wǎng)格資源分配方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2006, 29(6): 1004-1009.WENG C L, LU X D. A double auction method for resource allocation on computational grids[J]. Chinese Journal of Computers, 2006, 29(6):1004-1009.

[13] SUN D W, CHANG G R, WANG C, etal. Efficient Nash equilibrium based cloud resource allocation by using a continuous double auction[A]. 2010 International Conference on Computer Design and Appliations(ICCDA’10)[C]. Qinhuangdao, China, 2010.94-99.

[14] SHANG S F, JIANG J L, WU Y W, etal. A knowledge-based continuous double auction model for cloud market[A]. 6th International Conference on Semantics Knowledge and Grids(SKG’10)[C]. Los Alamitos, CA, USA, 2010.129-134.

[15] ROOVERS J, VANMECHELEN K, BROECKHOVE J. A reverse auction market for cloud resources[A]. The 8th International Conference on Economics of Grids Clouds Systems and Services (GECON’11)[C]. Berlin, Germany, 2012.32-45.

[16] BELALEM G, BOUAMAMA S, SEKHRI L. An effective economic management of resources in cloud computing[J]. Journal of Computers,2011, 6(3):404-411.

[17] BELALEM G, BOUAMAMA S, SEKHRI L. An efficient economic model user-oriented for cloud computing[J]. International Journal of Computer Applications, 2011, 15(2):32-39.

[18] FUJIWARA I, AIDA K, ONO I. Applying double-sided combinational auctions to resource allocation in cloud computing[A]. 10th IEEE/IPSJ International Symposium on Applications and the Internet (SAINT’10)[C].Seoul, Korea, 2010.7-14.