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

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

中圖分類號： TN911?34 文獻標識碼： 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 引 言

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

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

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

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

1 相關工作

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

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

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

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

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

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

[maxj=1nxjpj]

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

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

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

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

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

本文提出的DP?VMPA Mechanism決定了獲得虛擬機的Winner用戶集和這個集合中每個用戶的定價。這種組合拍賣機制能有效分配虛擬機資源，為拍賣商帶來更高的收益（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ī)劃求解虛擬機供應與分配機制（DP?VMPA）如上，機制被云提供商階段性的調用，運行該機制需要提供三個輸入參數(shù)：虛擬機資源總量[M，]虛擬機的類型數(shù)量[m]和相應的虛擬機權重[wi，]輸出三個參數(shù)：成功獲得虛擬機資源的用戶集合[W，]用戶支付向量[P]以及提供商對每類虛擬機的供應數(shù)量[ki]。

動態(tài)規(guī)劃機制也分為三個階段。第一階段，拍賣商收集用戶的投標，所有用戶的投標構成集合[BN。]第二階段使用動態(tài)規(guī)劃分配算法（算法3給出CA?DP分配算法）決定獲得資源的Winner集合，求出該集合下產生的最大社會總價值[BestValue]，同時決定出拍賣商的虛擬機供應方案。第三階段，使用VCG機制求出Winner集合每個用戶應當支付的金額，即用戶[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ù)，即所有參與投標的用戶集合[BN]和虛擬機資源總量[M。]運行算法可以得到兩個值，即最優(yōu)分配下的投標成功用戶集合[W]和對應的最大估價之和BestValue。

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

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

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

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

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

命題1 DP?VMPA機制的時間復雜度為[O（nnM）]

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

命題2 DP?VMAP機制是Truthful的

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

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

命題3 DP?VMAP機制滿足個體理性

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

4 應用案例及分析

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

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

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

5 結 論

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

參考文獻

[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.