一種基于動(dòng)態(tài)規(guī)劃的虛擬機(jī)分配方法

摘 要： 基于組合拍賣(mài)的動(dòng)態(tài)分配機(jī)制使得云拍賣(mài)商能夠根據(jù)市場(chǎng)需求高效地配置云資源，為拍賣(mài)商帶來(lái)更高的收益?，F(xiàn)有方法是貪婪法分配虛擬機(jī)資源，優(yōu)先為投標(biāo)密度高的用戶分配資源，然而這種局部最優(yōu)選擇并不總能帶來(lái)整體最優(yōu)解。提出一種基于動(dòng)態(tài)規(guī)劃的虛擬機(jī)分配方法DP?VMPA，它以最大社會(huì)福利作為目標(biāo)函數(shù)，使用CA?DP分配算法求出獲得資源的用戶集，最后采用VCG機(jī)制為用戶定價(jià)。應(yīng)用實(shí)例表明，DP?VMPA機(jī)制能夠更有效地分配虛擬機(jī)資源，同時(shí)為拍賣(mài)商帶來(lái)更高的收益。

關(guān)鍵詞： 虛擬機(jī)； 動(dòng)態(tài)規(guī)劃； 分配； 定價(jià)

中圖分類(lèi)號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）21?0159?05

A virtual machine allocation method based on dynamic planning

WANG Yan1， SUN Maosheng2， ZHU Junwu2， 3

（1. Center of Informatization， Xuzhou University of Technology， Xuzhou 221018， China；

2. School of Information Engineering， Yangzhou University， Yangzhou 225009， China；

3. Department of Computer Science and Technology， University of Guelph， Guelph NIG2K8， Canada）

Abstract： The dynamic allocation mechanism based on combination auction makes the cloud auctioneer allocate the cloud resource efficiently according to the market requirement， and brings high benefit for the auctioneer. The existing method uses the greed method to allocate the virtual machine resource， and allocates the resource for the high tender?density users optimally. Ho?wever this local optimal selection can′t bring the global optimal solution. A DP?VMPA （dynamic planning based virtual machine provision allocation） method is proposed， which takes the maximal social welfare as target function， uses CA?DP allocation algorithm to find out the obtained users set of resource. The VCG mechanism is used to price for the users. An application example shows that the DP?VMPA method can allocate the virtue machine resources efficiently， and bring a high benefit for the auctioneer.

Keywords： virtue machine； dynamic planning； allocation； pricing

0 引 言

當(dāng)下云拍賣(mài)商們大都使用基于固定價(jià)格機(jī)制的方法分配和賣(mài)出云資源，例如Windows Azure[1]和Amazon EC2[2]。顯然這種分配和定價(jià)體制有不少缺點(diǎn)，首先它不能保證資源的有效分配，那些對(duì)資源估價(jià)高的用戶并不總能如愿獲得請(qǐng)求資源，其次云拍賣(mài)商的利潤(rùn)偏低[3?4]?；谂馁u(mài)的機(jī)制可以有效地解決如上問(wèn)題，它權(quán)衡用戶請(qǐng)求的資源量及對(duì)資源的估價(jià)，決定對(duì)用戶的分配及定價(jià)。

拍賣(mài)機(jī)制分靜態(tài)拍賣(mài)和動(dòng)態(tài)拍賣(mài)，靜態(tài)機(jī)制需要拍賣(mài)商提前供應(yīng)虛擬機(jī)資源并且不能改變資源量，動(dòng)態(tài)拍賣(mài)下，拍賣(mài)商可以使用虛擬化技術(shù)，根據(jù)用戶需求量動(dòng)態(tài)配置各類(lèi)虛擬資源，并將它們按單位虛擬機(jī)實(shí)例賣(mài)出，保證資源的高效利用?，F(xiàn)有的方法大都使用貪婪算法[3?5]決定用戶的分配。它對(duì)用戶的投標(biāo)價(jià)值密度由高到低排序，在資源容量?jī)?nèi)依次選擇價(jià)值密度高的投標(biāo)，將資源分配給用戶，這種啟發(fā)式的策略并不總能獲得最優(yōu)解。

通常WDP問(wèn)題是個(gè)NP完全問(wèn)題，可以對(duì)虛擬機(jī)供應(yīng)與分配問(wèn)題VMPA進(jìn)行客觀描述，給出目標(biāo)函數(shù)，然后使用基于組合拍賣(mài)的動(dòng)態(tài)規(guī)劃算法（CA?DP Allocation Algorithm）求出分配最優(yōu)解。DP算法是先把問(wèn)題分成多個(gè)子問(wèn)題（一般地，每個(gè)子問(wèn)題是互相關(guān)聯(lián)和影響的），再依次研究逐個(gè)問(wèn)題的決策。動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)算法的主要思路使用最優(yōu)性原理找出遞推關(guān)系， 再找最優(yōu)決策序列。定價(jià)方案上采用基于最優(yōu)分配的VCG（Vickrey?Clarke?Groves）機(jī)制，即用分配給該用戶的資源對(duì)其余用戶的社會(huì)損失給其定價(jià)。

本文根據(jù)虛擬機(jī)分配問(wèn)題的目標(biāo)函數(shù)，提出DP?VMPA Mechanism （Dynamic Programming Mechanism that solves VMPA problem），采用CA?DP allocation algorithm解決分配問(wèn)題，同時(shí)使用VCG定價(jià)機(jī)制決定用戶的支付。這個(gè)機(jī)制能保證資源的有效利用，并為提供商帶來(lái)更高的利潤(rùn)。

1 相關(guān)工作

Zaman等人首先詳細(xì)介紹了基于固定價(jià)格的分配機(jī)制[3]，然后提出兩種基于拍賣(mài)的靜態(tài)虛擬機(jī)分配機(jī)制CA?GREEDY機(jī)制和CA?LP機(jī)制，并將它們與Fixed?Price機(jī)制比較，相比于固定價(jià)格機(jī)制，基于拍賣(mài)的機(jī)制能更有效地分配虛擬機(jī)資源，提高拍賣(mài)商利益。CA?LP機(jī)制在分配資源和增大收益方面表現(xiàn)突出，CA?GREEDY機(jī)制因其快速有效的分配性能被廣泛認(rèn)可。文獻(xiàn)[4]中，拍賣(mài)商結(jié)合虛擬化技術(shù)對(duì)資源實(shí)現(xiàn)動(dòng)態(tài)配置，使用CA?PROVISION機(jī)制分配虛擬機(jī)資源。本文嘗試將此機(jī)制與靜態(tài)分配下的CA?GREEDY機(jī)制比較，實(shí)驗(yàn)表明，動(dòng)態(tài)分配下，拍賣(mài)商根據(jù)市場(chǎng)需求動(dòng)態(tài)供應(yīng)資源，可以保證資源的高效利用，增大拍賣(mài)商的利潤(rùn)。它還通過(guò)設(shè)置保留價(jià)格進(jìn)一步提升拍賣(mài)商的收益。文獻(xiàn)[6]提出一種有效投標(biāo)策略，幫助云計(jì)算用戶生成最佳投標(biāo)（請(qǐng)求的虛擬機(jī)資源組合和對(duì)這組資源的估價(jià)）。這種投標(biāo)策略能夠幫助用戶高效地完成云計(jì)算任務(wù)，提高執(zhí)行效用。資源的有效利用也使得拍賣(mài)商收益增加。Nejad在文獻(xiàn)[5]中提出動(dòng)態(tài)虛擬機(jī)資源的啟發(fā)式貪婪分配算法，它詳細(xì)描述了用戶對(duì)多類(lèi)虛擬機(jī)資源CPU、內(nèi)存和容量的請(qǐng)求數(shù)量，然后根據(jù)各類(lèi)資源稀缺性參數(shù)重新定義價(jià)值密度，按貪婪算法進(jìn)行資源分配。文獻(xiàn)[3?5]均采用貪婪法分配資源，貪婪法一步步的構(gòu)造局部最優(yōu)解，使得最終分配解保持可行性且能產(chǎn)生較大效益。

Garfinkel提出了集分割算法解決組合拍賣(mài)下的分配問(wèn)題[7]；Nisan將Winner集決定問(wèn)題表示成一個(gè)標(biāo)準(zhǔn)的混合整數(shù)規(guī)劃問(wèn)題[8]，提出使用商用軟件和一些簡(jiǎn)單算法求解該問(wèn)題。Sandholm在文獻(xiàn)[9]提出使用軟件CPLEX可以高效地解決WDP問(wèn)題，使資源充分利用。Fujisima推薦CASS軟件來(lái)處理更大規(guī)模的WDP[10]。將組合拍賣(mài)下的分配借助各類(lèi)軟件的整數(shù)規(guī)劃實(shí)現(xiàn)，這是完全可行的，不過(guò)這些軟件無(wú)法用算法描述，另外它們只能給出最優(yōu)分配集合，對(duì)用戶的定價(jià)問(wèn)題卻無(wú)法解決。文獻(xiàn)[11]在眾包分配與定價(jià)問(wèn)題中介紹了4種可行的機(jī)制：OPT，GREEDY，VCG和TruTeam，并通過(guò)實(shí)驗(yàn)比較各個(gè)機(jī)制，得出結(jié)論VCG機(jī)制和TruTeam機(jī)制均能高效利用資源，同時(shí)證明其滿足個(gè)體理性和真實(shí)性。

2 動(dòng)態(tài)虛擬機(jī)供應(yīng)與分配問(wèn)題

通過(guò)虛擬化技術(shù)的應(yīng)用，云計(jì)算提供商可以將計(jì)算資源動(dòng)態(tài)配置成任意類(lèi)型的虛擬機(jī)組合。一個(gè)云拍賣(mài)商向用戶提供[m]類(lèi)虛擬機(jī)實(shí)例資源，[VM1，VM2，…，][VMm。]虛擬機(jī)類(lèi)型[VMi]的計(jì)算能力表示為[wi，]其中[w1]=1，[w1

考慮有[n]個(gè)用戶[u1，u2，…，un]向云提供商請(qǐng)求虛擬機(jī)。用戶[uj]向拍賣(mài)商提交一組投標(biāo)[Bj=（rj1，…，rmj，vj），]其中[rij]是請(qǐng)求的虛擬機(jī)[VMi]的數(shù)量，[vj]是單位時(shí)間內(nèi)用戶[j]得到虛擬機(jī)愿意最大支付的金額。拍賣(mài)商階段性的組織拍賣(mài)分配虛擬機(jī)，一單位時(shí)間即這輪拍賣(mài)的拍賣(mài)商的分配與定價(jià)決策到下輪拍賣(mài)的決策之間的時(shí)間間隔。為了定義云提供商獲得的利益，定義[P={p1，p2，…，pn}，]其中用[pj]表示用戶[j]獲得請(qǐng)求的資源時(shí)需要支付的金額，通常小于[vj]；將分配問(wèn)題的解定義為[x=（x1，x2，…，xn）]，分配向量中的元素[xj∈{0，1}，][xj=1]表示用戶[j]得到虛擬機(jī)組合，反之[xj=0]表示用戶未得到；集合[W=uj1≤j≤n，xj=1]作為投標(biāo)勝利用戶集。[sj=][i=1mwirij]表示用戶[uj]請(qǐng)求的單位計(jì)算資源的數(shù)量，其中單位資源也就是一個(gè)[VM1]類(lèi)型的虛擬機(jī)實(shí)例。

定義1：動(dòng)態(tài)虛擬機(jī)供應(yīng)與分配問(wèn)題可以形式化描述為：

[maxj=1nxjpj]

[s.t. j=1nxjsj≤Mxj∈0，10≤pj≤vj]

式中：約束條件（1） 表明成功投標(biāo)的用戶請(qǐng)求的虛擬機(jī)資源總量不得超過(guò)拍賣(mài)商所擁有的資源量；式（2）表示規(guī)定分配向量[xj]的取值范圍；式（3）表示此不等式保證用戶的支付金額不超過(guò)用戶對(duì)其請(qǐng)求資源的最大估價(jià)，也就是確保用戶的效用[Uj=vj-pj]不為負(fù)。組合拍賣(mài)的最優(yōu)方案應(yīng)該是最大化云拍賣(mài)商的利益，但很難找出一個(gè)客觀函數(shù)描述它，通常尋找最大化社會(huì)總福利（成功獲得虛擬機(jī)資源的用戶投標(biāo)總價(jià)值）作為解決組合拍賣(mài)問(wèn)題的方案。這種分配方案決定了拍賣(mài)商對(duì)每類(lèi)虛擬機(jī)的配置，計(jì)算[ki=j=1nxjrij，]即[VMi]類(lèi)虛擬機(jī)需要供應(yīng)的數(shù)量為[ki]。

定義2：真實(shí)的（Truthful， Incentive Compatible）假定任意用戶[j]其在真實(shí)報(bào)價(jià)情形下獲得的效用為[u1，]任意虛假報(bào)價(jià)下獲得的效用為[u2，]若給定機(jī)制中[u1-u2≥0，]則稱(chēng)該機(jī)制是Truthful的。即用戶只有通過(guò)向機(jī)制提交真實(shí)的估價(jià)，他才能獲得最大效用。真實(shí)性使得用戶在投標(biāo)決策時(shí)不需考慮復(fù)雜的投標(biāo)策略，更不需考慮其他用戶的投標(biāo)方案。

定義3：個(gè)體理性（Individual Rationality），即在一機(jī)制中，對(duì)每個(gè)用戶[j]，用戶的效用[Uj=vj-pj]大于等于0，則稱(chēng)用戶[j]是個(gè)體理性的。

3 基于組合拍賣(mài)的動(dòng)態(tài)虛擬機(jī)供應(yīng)與分配機(jī)制

本文提出的DP?VMPA Mechanism決定了獲得虛擬機(jī)的Winner用戶集和這個(gè)集合中每個(gè)用戶的定價(jià)。這種組合拍賣(mài)機(jī)制能有效分配虛擬機(jī)資源，為拍賣(mài)商帶來(lái)更高的收益（Efficient）。

Algorithm 1：DP?VMPA Mechanism

Input：[M；m；wi：1，…，m；]

Output：[W；P；ki：1，…，m；]

1.{phase： Collect [Bids]}

a.Initialize [BN←Φ]

b.For [j]=[1，2，…，n，]

Collect bid [Bj=（rj1，…，rjm，vj）] from user [uj]

c.[BN←BN?{Bj}]

2.{phase 2： Winner Determination and Provision}

（[W，][BestValue]） = CA?DP（[BN，][M]） //Algorithm 3

For [i=1，…，m，]

[ki←j：uj∈Wrij]

3.{phase 3：[Payment]}

For all [j∈W]

（[W，][BestValue]） = CA?DP（[BN-{uj}，][M]） //Algorithm 3

[pj←BestValue-（BestValue-vj）]

For all [j?W，]

[pj←0]

Return （[W；P；ki：1，…，m]）

動(dòng)態(tài)規(guī)劃求解虛擬機(jī)供應(yīng)與分配機(jī)制（DP?VMPA）如上，機(jī)制被云提供商階段性的調(diào)用，運(yùn)行該機(jī)制需要提供三個(gè)輸入?yún)?shù)：虛擬機(jī)資源總量[M，]虛擬機(jī)的類(lèi)型數(shù)量[m]和相應(yīng)的虛擬機(jī)權(quán)重[wi，]輸出三個(gè)參數(shù)：成功獲得虛擬機(jī)資源的用戶集合[W，]用戶支付向量[P]以及提供商對(duì)每類(lèi)虛擬機(jī)的供應(yīng)數(shù)量[ki]。

動(dòng)態(tài)規(guī)劃?rùn)C(jī)制也分為三個(gè)階段。第一階段，拍賣(mài)商收集用戶的投標(biāo)，所有用戶的投標(biāo)構(gòu)成集合[BN。]第二階段使用動(dòng)態(tài)規(guī)劃分配算法（算法3給出CA?DP分配算法）決定獲得資源的Winner集合，求出該集合下產(chǎn)生的最大社會(huì)總價(jià)值[BestValue]，同時(shí)決定出拍賣(mài)商的虛擬機(jī)供應(yīng)方案。第三階段，使用VCG機(jī)制求出Winner集合每個(gè)用戶應(yīng)當(dāng)支付的金額，即用戶[j]不參與拍賣(mài)所能得到的最大價(jià)值總和減去用戶[j]參與拍賣(mài)并獲得資源時(shí)其他用戶的價(jià)值量總和，未獲得虛擬機(jī)的用戶支付量為0。

Algorithm 2： CA?DP allocation algorithm

Input：[BN，M]

Output：[W，BestValue]

1.Initialize [BN←Φ，n←size（BN），] [bestValues[n+1][M+1]]

2.For [j=0，1，…，n，]

[sj←i=1mwirij]

For [h=0，1，…，M，]

If [h=0j=0] then [bestValues[i][j]←0]

Else

If [sj>h]then [bestValues[j][h]←bestValues[j-1][h]]

Else[bestValues[j][h]←][max{bestValues[j-1][h]，bestValues[j-1]]

[[h-sj]+vj}]

3.[h←M]

4.For [j]=[n，…，1]

If [bestValues[j][h]>bestValues[j-1][h]]

then [W←W?{uj}，][h←h-sj]

5.[BestValue←bestValues[n][M]]

Return （[W，][BestValue]）

基于組合拍賣(mài)的動(dòng)態(tài)規(guī)劃分配算法如上所述，該算法需要提供兩個(gè)參數(shù)，即所有參與投標(biāo)的用戶集合[BN]和虛擬機(jī)資源總量[M。]運(yùn)行算法可以得到兩個(gè)值，即最優(yōu)分配下的投標(biāo)成功用戶集合[W]和對(duì)應(yīng)的最大估價(jià)之和BestValue。

組合拍賣(mài)問(wèn)題的最優(yōu)解結(jié)構(gòu)：可以將組合拍賣(mài)分配問(wèn)題的求解過(guò)程看作是進(jìn)行一系列的決策過(guò)程，即決定哪些用戶應(yīng)該獲得虛擬機(jī)資源，哪些用戶不該獲得請(qǐng)求資源。如果一個(gè)問(wèn)題的最優(yōu)解包含了用戶[n]，即[xn=1，]那么其余[（x1，x2，…，xn-1）]一定構(gòu)成子問(wèn)題1，2，[…]，[n-1]在云提供商擁有虛擬機(jī)資源為[M-sj]時(shí)的最優(yōu)解。如果這個(gè)最優(yōu)解不包含物品[n]，即[xn=0，]那么其余[（x1，x2，…，xn-1）]一定構(gòu)成子問(wèn)題1，2，[…]，[n-1]在資源量為[M]時(shí)的最優(yōu)解。

那么根據(jù)上述分析的最優(yōu)解的結(jié)構(gòu)性質(zhì)，遞歸地定義問(wèn)題最優(yōu)解。[bestValues[j][h]]表示虛擬機(jī)資源量為[h]時(shí)，前[j]個(gè)用戶導(dǎo)致的最優(yōu)解的總價(jià)值，那么總有：

[bestValues[j][h]=bestValues[j-1][h]，sj>hmaxbestValues[j-1][h]， bestValues[j-1][h-sj]+vj，sj≤h]

當(dāng)用戶[j]請(qǐng)求的資源量大于[h]時(shí)，[bestValues[j][h]]由虛擬機(jī)資源量為[h]時(shí)，前[j-1]個(gè)用戶最優(yōu)解的總價(jià)值決定；當(dāng)用戶[j]請(qǐng)求的資源量不大于[h]時(shí)，通過(guò)比較不允許[j]獲得資源的總價(jià)值[bestValues[j-1][h]]和允許[j]獲得請(qǐng)求的資源產(chǎn)生的總價(jià)值[bestValues[j-1][h-sj]+vj]，總價(jià)值高的作為[bestValues[j][h]]的最優(yōu)解價(jià)值。顯然最終要求的是[bestValues[j][h]]。

求出最優(yōu)解下的總價(jià)值后，可以通過(guò)回溯找出所有成功獲得虛擬機(jī)資源的用戶，即通過(guò)比較虛擬機(jī)資源量為[h]時(shí)，前[j-1]個(gè)用戶最優(yōu)解的總價(jià)值[bestValues[j-1][h]]和虛擬機(jī)資源量為[h]時(shí)，前[j]個(gè)用戶最優(yōu)解的總價(jià)值[bestValues[j][h]]，來(lái)得出用戶[j]能否獲得請(qǐng)求資源?；厮菪枰獜腫j=n]，[h=M]處開(kāi)始，直至[j=1]，[h=0，]并將結(jié)果保存在集合[W]中。

命題1 DP?VMPA機(jī)制的時(shí)間復(fù)雜度為[O（nnM）]

證明：CA?DP分配算法中遞歸求最優(yōu)解，使用兩個(gè)for循環(huán)對(duì)[j=0，1，…，n]和[h=0，1，…，M]下每種狀態(tài)求出最優(yōu)解，時(shí)間復(fù)雜度為[O（nM），]回溯法求投標(biāo)成功用戶集合[W]只需遍歷一個(gè)for循環(huán)，其時(shí)間復(fù)雜度為[O（n），]總共時(shí)間復(fù)雜度為[O（nM）]。使用VCG機(jī)制對(duì)Winner集中每個(gè)用戶求支付金額，對(duì)每個(gè)用戶需要調(diào)用CA?DP分配算法，最壞時(shí)間復(fù)雜度為[O（nnM）]。

命題2 DP?VMAP機(jī)制是Truthful的

證明：證明真實(shí)性（Truthful），首先證明其分配單調(diào)性（Monotone），即用戶可以通過(guò)增大對(duì)請(qǐng)求的虛擬機(jī)組合的估價(jià)[vj]，或者減少請(qǐng)求的虛擬機(jī)資源總量[sj]來(lái)增加獲得請(qǐng)求資源的幾率，所以說(shuō)機(jī)制是單調(diào)性的。

其次證明支付金額為臨界價(jià)格（Critical Value），動(dòng)態(tài)規(guī)劃?rùn)C(jī)制求出分配最優(yōu)解的前提下，使用VCG機(jī)制對(duì)投標(biāo)成功的用戶定價(jià)，用戶[j]不參與拍賣(mài)所能得到的最大價(jià)值總和減去用戶[j]參與拍賣(mài)時(shí)其他用戶的價(jià)值量總和，求出的支付金額[pj]是臨界價(jià)值。

命題3 DP?VMAP機(jī)制滿足個(gè)體理性

證明：對(duì)獲得資源的每個(gè)用戶[pj=BestValue-][（BestValue-vj），]因?yàn)閯?dòng)態(tài)規(guī)劃基于最優(yōu)分配，所以公式中[bestValue≤bestValue，]即證[Uj=vj-pj=bestValue-][bestValue≥0]。未獲得虛擬機(jī)的用戶[Uj=0，]所以綜上機(jī)制滿足個(gè)體理性。

4 應(yīng)用案例及分析

假定[n=4，][M=8，]4個(gè)用戶的請(qǐng)求虛擬機(jī)數(shù)量和報(bào)價(jià)：（3，3），（2，4），（4，1），（1，2），[bestValue[j][c]]取值如表1所示（[j=]0或[c=0，][bestValue[j][c]]=0）。

時(shí)間復(fù)雜度：基于組合拍賣(mài)的動(dòng)態(tài)規(guī)劃分配算法中，根據(jù)最優(yōu)解結(jié)構(gòu)性質(zhì)，對(duì)[j∈[0，n]]和[c∈[0，M]]每種狀態(tài)下使用遞歸式求出最優(yōu)解，使用兩個(gè)for循環(huán)，其時(shí)間復(fù)雜度為[O（nM）]?；厮莘ㄇ笸稑?biāo)成功用戶集合[W]只需遍歷一個(gè)for循環(huán)，其時(shí)間復(fù)雜度為[O（n），]總共時(shí)間復(fù)雜度為[O（nM）]。

空間復(fù)雜度：動(dòng)態(tài)規(guī)劃求最優(yōu)解需要構(gòu)造（n+1）×（[M+1]）的二維數(shù)組，用于存儲(chǔ)[（j，c）]下的最大價(jià)值[bestValue[j][c]，]空間復(fù)雜度為[O（nM）]。

5 結(jié) 論

為了解決虛擬機(jī)動(dòng)態(tài)分配問(wèn)題，提出一種基于動(dòng)態(tài)規(guī)劃的虛擬機(jī)分配機(jī)制。這種機(jī)制以最大社會(huì)福利為目標(biāo)函數(shù)，遞歸求解最優(yōu)分配下的用戶集，并使用VCG機(jī)制對(duì)用戶資源定價(jià)。DP?VMPA機(jī)制能夠使更多的用戶完成應(yīng)用，高效利用虛擬機(jī)資源，明顯增大了拍賣(mài)商的收益。這個(gè)機(jī)制時(shí)間復(fù)雜度較高，不建議對(duì)大規(guī)模用戶參與的虛擬機(jī)分配問(wèn)題使用該機(jī)制，后續(xù)工作將圍繞對(duì)CA?DP分配函數(shù)進(jìn)行優(yōu)化處理，并對(duì)VCG機(jī)制進(jìn)行改進(jìn)，使得定價(jià)機(jī)制更加簡(jiǎn)易高效。

參考文獻(xiàn)

[1] Microsoft. Windows azure platform [EB/OL]. [2015?09?11]. http：//www.microsoft.com/windowsazure/.

[2] Amazon. Amazon elastic compute cloud （Amazon EC2） [EB/OL]. [2016?01?17]. http：//aws.amazon.com/ec2/.

[3] ZAMAN S， GROSU D. Combinatorial auction?based allocation of virtual machine instances in clouds [J]. Journal of parallel and distributed computing， 2013， 73（4）： 495?508.

[4] ZAMAN S， GROSU D. Combinatorial auction?based dynamic VM provisioning and allocation in clouds [C]// Proceedings of 2011 Third IEEE International Conference on Cloud Computing Technology and Science. [S.l.]： IEEE， 2011： 107?114.

[5] NEJAD M M， MASHAYEKHY L， GROSU D. Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds [J]. IEEE transactions on parallel distribu?ted systems， 2014， 26（2）： 594?603.

[6] ZAMAN S， GROSU D. Efficient bidding for virtual machine instances in clouds [C]// Proceedings of 2011 IEEE International Conference on Cloud Computing. [S.l.]： IEEE， 2011： 41?48.

[7] GARFINKEL R S， NEMHAUSER G L. The set partitioning problem： set covering with equality constraints [J]. Operations research， 1969， 17（5）： S40?S47.

[8] NISAN N. Bidding and allocation in combinatorial auctions [C]// Proceedings of 2000 2nd ACM Conference on Electronic Commerce. New York： ACM， 2001： 1?12.

[9] SANDHOLM T. Algorithm for optimal winner determination in combinatorial auctions [J]. Artificial intelligence， 2002， 135（1/2）： 1?54.

[10] FUJISIMA YUZO， LEYTON?BROWN K， SHOHAM Y. Ta?ming the computational complexity of combinatorial auctions [C]// Proceedings of 1999 International Joint Conference on Artificial Intelligence. [S.l.： s.n.]， 1999： 548?553.

[11] LIU Q， LUO T， TANG R， et al. An efficient and truthful pricing mechanism for team formation in crowdsourcing markets [C]// Proceedings of 2015 IEEE International Conference on Communications. Singapore： IEEE， 2015： 567?572.