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

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

中圖分類號： TN911?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 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)下云拍賣商們大都使用基于固定價格機(jī)制的方法分配和賣出云資源，例如Windows Azure[1]和Amazon EC2[2]。顯然這種分配和定價體制有不少缺點，首先它不能保證資源的有效分配，那些對資源估價高的用戶并不總能如愿獲得請求資源，其次云拍賣商的利潤偏低[3?4]。基于拍賣的機(jī)制可以有效地解決如上問題，它權(quán)衡用戶請求的資源量及對資源的估價，決定對用戶的分配及定價。

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

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

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

1 相關(guān)工作

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

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

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

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

考慮有[n]個用戶[u1，u2，…，un]向云提供商請求虛擬機(jī)。用戶[uj]向拍賣商提交一組投標(biāo)[Bj=（rj1，…，rmj，vj），]其中[rij]是請求的虛擬機(jī)[VMi]的數(shù)量，[vj]是單位時間內(nèi)用戶[j]得到虛擬機(jī)愿意最大支付的金額。拍賣商階段性的組織拍賣分配虛擬機(jī)，一單位時間即這輪拍賣的拍賣商的分配與定價決策到下輪拍賣的決策之間的時間間隔。為了定義云提供商獲得的利益，定義[P={p1，p2，…，pn}，]其中用[pj]表示用戶[j]獲得請求的資源時需要支付的金額，通常小于[vj]；將分配問題的解定義為[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]請求的單位計算資源的數(shù)量，其中單位資源也就是一個[VM1]類型的虛擬機(jī)實例。

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

[maxj=1nxjpj]

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

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

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

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

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

本文提出的DP?VMPA Mechanism決定了獲得虛擬機(jī)的Winner用戶集和這個集合中每個用戶的定價。這種組合拍賣機(jī)制能有效分配虛擬機(jī)資源，為拍賣商帶來更高的收益（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]）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

參考文獻(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.