殷 波，張云勇，房秉毅，馮偉斌

（中國聯(lián)合網(wǎng)絡(luò)通信有限公司研究院 北京100032）

1 引言

云計算具有資源按需提供的特征，為用戶以彈性伸縮的方式分配計算資源。該方式靈活高效地實現(xiàn)了資源的按需分配，提高了資源利用率，降低了運營成本。目前，以虛擬化技術(shù)為基礎(chǔ)的云計算資源分配方法，主要以虛擬機為粒度，為用戶提供服務(wù)，處理用戶的應(yīng)用請求。用戶與云服務(wù)提供商簽訂嚴格的SLA，云服務(wù)提供商（SP）在保證用戶SLA的前提下，根據(jù)用戶應(yīng)用的負載狀況，自動彈性調(diào)整資源分配量。云服務(wù)提供商將服務(wù)部署到云計算環(huán)境中，既節(jié)省了前期基礎(chǔ)設(shè)施投入的成本，又進一步降低了后期軟硬件資源的管理運維成本，為云服務(wù)提供商帶來了直接經(jīng)濟收益。云服務(wù)提供商將服務(wù)部署到云環(huán)境中，云數(shù)據(jù)中心擁有者需要將云服務(wù)提供商的用戶請求分配到各個虛擬機資源中進行處理。云數(shù)據(jù)中心的擁有者在本文中被稱為云資源提供商，云資源提供商擁有數(shù)據(jù)中心，負責將云服務(wù)提供商的用戶請求進行任務(wù)分配。

云計算將服務(wù)提供和資源提供兩個過程解耦合，云資源提供商以特定的方式提供資源，并保證資源的可用性以及可靠性，針對云服務(wù)提供商的用戶請求負責制定合理的虛擬機分配方案進行資源提供，為用戶請求分配合理的虛擬機資源。云服務(wù)提供商需要在保證用戶滿意度的基礎(chǔ)上，為用戶請求分配制定虛擬機資源使用方案，盡可能降低虛擬機資源的使用成本，基于云服務(wù)提供商的角度進行成本優(yōu)化和資源分配是本文需要解決的主要問題。

本文首先分析了現(xiàn)有云計算環(huán)境的資源分配現(xiàn)狀，抽象出面向成本優(yōu)化的云服務(wù)提供商資源分配問題的數(shù)學模型，然后采用改進粒子群算法對問題進行了求解。

2 相關(guān)工作

目前基于云服務(wù)提供商進行保證SLA的資源分配策略的研究有很多。在基于定價機制進行資源分配的研究中，根據(jù)不同的資源購買方式，制定出成本分析模型是資源分配研究的核心。例如，參考文獻[1,2]提出了一種在云計算環(huán)境下針對按需、現(xiàn)貨和預(yù)約3種市場，設(shè)計面向SP收益優(yōu)化的資源分配方法，然而該文獻并未深入研究和探討現(xiàn)貨市場的風險問題。此外，為了提高SP的收益，參考文獻[3]首先建立成本分析模型，并制定SP總成本最小的資源提供方案，以滿足用戶需求，然而，在該文獻中，成本分析模型忽略了市場模型的多樣性以及現(xiàn)貨市場的風險對SP長期收益的影響，導致該文獻方法不能準確度量成本和收益。參考文獻[4]設(shè)計了一種定價機制，通過分析應(yīng)用之間的相關(guān)性，提出了兩種SP收益驅(qū)動的資源提供算法。然而，該文獻同樣沒有考慮現(xiàn)貨市場對資源分配方案的影響，同樣導致成本和收益度量不準確。此外，參考文獻[6]闡述了基于市場的資源提供策略的風險和優(yōu)勢。參考文獻[5]對云計算環(huán)境的盈利模式進行了分析，包括分析服務(wù)收費和商業(yè)成本，并且確定了應(yīng)用特征與云資源提供商資源價格及收益之間的關(guān)系，提出了一種基于應(yīng)用特征的定價模型，綜合考慮應(yīng)用的工作負載環(huán)境、多服務(wù)系統(tǒng)的配置、服務(wù)級別協(xié)議、用戶滿意度、服務(wù)質(zhì)量以及SLA違約懲罰、能耗成本等，制定出云服務(wù)提供商的收益模型，并且將服務(wù)系統(tǒng)看作M/M/m隊列模型，對優(yōu)化問題進行建模和分析。然而，該文獻并未針對目前業(yè)界主流的市場模型進行方案設(shè)計，并且同樣忽視了現(xiàn)貨市場的風險對模型的影響，同樣具有成本度量不準確的問題。

本文針對現(xiàn)有研究的不足，基于目前的市場模型，從按需市場、預(yù)約市場和現(xiàn)貨市場3種情況出發(fā)，設(shè)計了SP的資源分配模型，同時針對現(xiàn)貨市場的不穩(wěn)定性，引入風險控制因子，保證現(xiàn)貨市場的可用性，實現(xiàn)了對市場模式的全面度量，并進一步對資源進行有效利用，提高資源利用率，降低資源分配成本，實現(xiàn)了成本優(yōu)化。

3 面向成本優(yōu)化的虛擬機資源分配問題描述

SP將應(yīng)用服務(wù)部署到云環(huán)境中，向用戶提供服務(wù)，并對使用應(yīng)用的用戶進行收費。用戶向SP提交的工作請求用ri(λi,ti)進行表示，λi表示任務(wù)資源需求大小，ti表示任務(wù)的運行時長。SP在進行資源分配和任務(wù)調(diào)度的過程中，首先，需要對用戶的任務(wù)請求進行度量，用ui表示請求ri所需的計算能力，一般情況下ui=λiti。

以亞馬遜為例，目前的云計算運營商通常將其所擁有的虛擬機資源分為3類：預(yù)約類型、按需類型和現(xiàn)貨類型。云資源提供商通常將云數(shù)據(jù)中心內(nèi)的虛擬機進行上述分類，針對不同用戶的任務(wù)請求，將任務(wù)分配到3種不同的虛擬機實例上去。SP面向3種資源類型，制定面向成本優(yōu)化的虛擬機購買方案，實現(xiàn)SP的收益優(yōu)化。

針對云計算運營市場環(huán)境中的3種角色，整個SP資源分配過程如圖1所示。云資源提供商擁有云數(shù)據(jù)中心，并且通過虛擬機分配決策模塊對用戶請求進行任務(wù)調(diào)度和資源分配。SP根據(jù)用戶請求量設(shè)計資源購買方案，租用云資源提供商的資源為用戶提供服務(wù)，獲取收益。制定SP資源購買方案的模塊是虛擬機分配決策模塊。本文的問題及其解決方法主要是在虛擬機分配決策模塊進行策略制定。虛擬機分配決策模塊通過信息采集模塊對用戶請求的信息進行采集，并通過資源監(jiān)測模塊采集云數(shù)據(jù)中心的各項資源信息。信息采集模塊獲取資源信息后，將數(shù)據(jù)發(fā)送至資源分配模塊，本文所提方法被放置在資源分配模塊，資源分配模塊通過對數(shù)據(jù)進行處理，并使用資源分配方法，制定出滿足SP收益最優(yōu)的資源分配策略，并將該策略發(fā)送至決策執(zhí)行模塊。決策執(zhí)行模塊對云數(shù)據(jù)中心發(fā)送指令，進行虛擬機資源分配。在此過程中，SP資源分配策略的制定原則是成本優(yōu)化、收益最優(yōu)。

圖1 云計算資源分配框架

本文基于云服務(wù)提供商的角度，對用戶請求進行資源分配，在完成用戶請求的描述后，接下來對云數(shù)據(jù)中心的資源進行描述。數(shù)據(jù)中心所能提供的虛擬機資源類型用Ω表示，按需市場環(huán)境下使用虛擬機實例i的單位時間的價格用pio表示；nio表示在此次決策周期內(nèi)從按需類型中選取的用于處理用戶請求的虛擬機實例的數(shù)量，則云資源提供商分配按需類型虛擬機實例的總成本可表示為：

用pid表示預(yù)約類型虛擬機實例i單位時間內(nèi)的價格；nid表示在此次決策周期內(nèi)從預(yù)約類型中選取的虛擬機實例i的數(shù)量，則云資源提供商分配預(yù)約類型虛擬機實例的總成本可表示為：

現(xiàn)貨類型是云資源提供商將按需類型和預(yù)約類型虛擬機分配完成之后，將閑散資源組織在一起，進行資源提供的一種資源分配方式。因此，現(xiàn)貨類型的虛擬機資源具有不穩(wěn)定性、可靠性和可用性較低等特點。但閑散的現(xiàn)貨類型虛擬機資源的優(yōu)勢是其成本消耗極低，使用現(xiàn)貨類型的虛擬機實例能有效降低成本支出，是云資源提供商資源回收利用的一種方法。在使用現(xiàn)貨資源進行虛擬機分配時，需要規(guī)避資源風險。

本文設(shè)定了現(xiàn)貨類型資源的風險規(guī)避因子。具體方法是，用δijs表示云資源提供商以成本支出pis將任務(wù)分配到虛擬機實例i的概率，本文將該因子稱為風險規(guī)避因子。現(xiàn)貨市場中虛擬機實例的價格用pis表示。用nis表示云資源提供商以成本pis在此次決策周期內(nèi)分配給任務(wù)請求的虛擬機實例i的數(shù)量。使用云資源提供商提供的現(xiàn)貨類型虛擬機實例的總成本表示為：

通過上述的問題描述，建立SP面向成本優(yōu)化的虛擬機分配的目標函數(shù)如下：

其中，γ和η表示按需類型和現(xiàn)貨類型虛擬機的分配比例，φ+γ+η=1。ci表示虛擬機實例的處理能力。設(shè)置該參數(shù)的目的是為了控制現(xiàn)貨類型虛擬機資源的分配比例，進一步規(guī)避現(xiàn)貨類型資源的不穩(wěn)定風險。在目標函數(shù)中需求解的未知量為nio和sio，求解該問題為NP問題，采用啟發(fā)式算法對其進行求解。在目前現(xiàn)有的啟發(fā)式算法中，求解方法與本文所提問題的數(shù)學模型較為一致的是粒子群算法，因此使用粒子群算法便于對問題進行映射和求解。在本文中，粒子群算法的每一個粒子表示一種虛擬機實例的購買方案，總體的虛擬機資源提供方案為Λ。

4 基于改進粒子群算法的虛擬機資源分配方法

改進算法的思想是在基本粒子群優(yōu)化算法的基礎(chǔ)上，重定義了算法中粒子的位置與速度，并通過自適應(yīng)慣性權(quán)重調(diào)整操作，這樣便于算法在更大的搜索空間內(nèi)尋求最優(yōu)解；此外，能進一步對算法的收斂性進行優(yōu)化，使得算法在較小的時間內(nèi)收斂求得解空間內(nèi)的全局最優(yōu)解。

（1）粒子重定義

其中，xio表示按需類型中第i類虛擬機資源的分配數(shù)量；xid表示預(yù)約類型中第i類虛擬機資源的分配數(shù)量；xis表示現(xiàn)貨類型中第i類虛擬機資源的分配數(shù)量。相應(yīng)地，粒子的速度重定義為：

其中，vio表示按需類型中的第i類虛擬機資源分配數(shù)量的變化量；vid表示預(yù)約類型中第i類虛擬機資源分配數(shù)量的變化量；vis表示現(xiàn)貨類型中第i類虛擬機資源分配數(shù)量的變化量。

改進PSO算法的速度和位置更新與標準PSO算法類似，通過對速度和位置進行不斷更新獲取解空間的最優(yōu)解。本文接下來對慣性權(quán)重進一步改進，以便于優(yōu)化算法的收斂性。

（2）慣性權(quán)重調(diào)整

PSO算法的缺點是在求解過程中出現(xiàn)早熟收斂現(xiàn)象，出現(xiàn)陷入局部最優(yōu)的情況。本文在算法的不同階段，動態(tài)調(diào)整速度的慣性權(quán)重ω取值：首先在求解的早期階段，通過調(diào)整慣性權(quán)重來盡可能擴大算法的解空間求解范圍，然而在算法求解的后期階段，通過調(diào)整慣性權(quán)重促使算法加速收斂到最優(yōu)解范圍。采用該方法能同時保證搜索效率和搜索精度。

改進方法的輸入變量為當前種群的迭代次數(shù)k和當前的慣性權(quán)重ω(k)∈[0.0,1.0]，輸出變量為當前種群的下一代慣性權(quán)重的值ω(k+1)：

其中，當前迭代次數(shù)表示為k；總的迭代次數(shù)表示為K；將ω(0)=1設(shè)置為慣性權(quán)重的初始值；另外，m為整數(shù)，且m∈[1,10]，在算法開始前選定。通過如式（7）的慣性權(quán)重調(diào)整方法，使種群中的粒子在算法的起始階段保持較大的慣性權(quán)重從而增加其搜索解空間的范圍，提高尋優(yōu)能力；而后隨著算法的迭代，逐漸降低慣性權(quán)重值，使種群中的各粒子以更大的概率向當前的全局最優(yōu)解位置靠攏，因此隨著算法的逐漸迭代，粒子群會逐漸趨向最優(yōu)解，從而在算法執(zhí)行的后期使整個種群的求解收斂，以便使算法的收斂性得到保證。算法通過自適應(yīng)慣性權(quán)重動態(tài)調(diào)整后的形式為：

算法流程如圖2所示。

圖2 算法流程

本文所用PSO算法的具體步驟如下。

算法1基于PSO的虛擬機資源分配方法

步驟1初始化算法參數(shù)：粒子群種群規(guī)模數(shù)首先設(shè)定為N，K為算法執(zhí)行的迭代次數(shù)。隨機生成每個粒子的位置參數(shù)xi和初始速度vi；對于上述初始化值的可行性進行檢查；隨后根據(jù)式（5）～式（8）計算當前各粒子位置所對應(yīng)的適應(yīng)度值cost(xi)，進而可以得到對應(yīng)全局最優(yōu)解的初始位置xgb和每個粒子的局部最優(yōu)解位置xpb。

步驟2迭代控制：判斷算法是否達到最大迭代次數(shù)，是則轉(zhuǎn)到步驟4；否則執(zhí)行步驟3；

步驟3迭代過程：

（1）對于粒子群中的每個粒子，計算其適應(yīng)度cost(xi)，如果優(yōu)于當前局部最優(yōu)解cost(xi)≤cost(xpb)則更新當前局部最優(yōu)解xpb=xi；如果優(yōu)于當前全局最優(yōu)解cost(xpb)≤cost(xgb)，則更新全局最優(yōu)解xgb=xpb；

（2）根據(jù)粒子群算法的速度和位置更新式子，對速度和位置進行更新；

（3）執(zhí)行步驟2；

步驟4輸出結(jié)果：將虛擬機的購買方案Λ和當前購買方案下的適應(yīng)度值cost(xi)進行算法輸出。

5 仿真結(jié)果

本文設(shè)計了仿真實驗，以驗證本文所提方法的效果，評價指標為SP完成相同任務(wù)所需的云資源提供商資源總成本，即處理相同情況下的用戶請求，減去所需的虛擬機資源總成本，獲得的SP總收益。實驗采用8核2 GHz AMD Opteron 2350服務(wù)器和4核2.4 GHz Intel Xeon X3220系統(tǒng)，所有服務(wù)器均安裝Xen 3.3和Linux 2.6.18（64 bit內(nèi)核）版本，實驗采用Microsoft Visual Studio 2005作為開發(fā)工具。實驗中的用戶任務(wù)到達的生成曲線服從正態(tài)分布。

本文中虛擬機實例采用亞馬遜所提供實例的大小和標價，見表1～表5。

表1 Amazon EC2按需類型實例價格和實例的基準測試能力

表2 小型虛擬機類型實例價格

表3 中型虛擬機類型的實例價格

表4 大型虛擬機類型的實例價格

表5 超大型虛擬機類型的實例價格

圖3 資源總收益對比

圖3 為本文方法與傳統(tǒng)單一模式定價模型的云服務(wù)提供商的收益對比。從圖3中可以看出，本文方法在針對按需、預(yù)約和現(xiàn)貨3種市場進行資源分配的基礎(chǔ)上，通過引入風險控制因子規(guī)避現(xiàn)貨市場的風險，有效利用了云市場的資源，提高了資源收益。目前在進行SP收益計算的方法中采用FirstFit Profit算法，基于先來先服務(wù)的原則，按照先后順序為用戶請求分配當前最合適的云資源提供商資源，該方法與本文方法相比，會在一定程度上造成資源的浪費，無法利用現(xiàn)貨資源較為便宜的優(yōu)勢，同時，不能合理分配3種市場的資源，該方法所產(chǎn)生的資源總成本較高。本文所提方法從兩個方面實現(xiàn)了成本優(yōu)化：首先，全面考慮了現(xiàn)貨、預(yù)約、按需3種資源類型的購買模式，有效降低了資源成本；其次，對于具有風險的現(xiàn)貨市場，引入風險控制因子，將SLA可靠性要求不高的用戶請求分配到現(xiàn)貨市場進行處理，有效實現(xiàn)了成本優(yōu)化，提高了資源收益。

6 結(jié)束語

本文基于云服務(wù)提供商的立場，針對按需、預(yù)約和現(xiàn)貨3種購買模式，提出了一種面向成本優(yōu)化的虛擬機資源分配方法。本文在全面考慮3種市場的基礎(chǔ)上，針對現(xiàn)貨市場的資源風險，引入了風險控制因子，有效規(guī)避了現(xiàn)貨市場的風險，抽象出成本優(yōu)化的虛擬機資源分配模型。之后，采用改進的粒子群算法對問題進行了求解。本文所提方法在保證用戶SLA的前提下，實現(xiàn)了云服務(wù)提供商的成本最小化，有效降低了資源購買成本，對增加云服務(wù)提供商的收益具有現(xiàn)實意義。

1 Sharma U,Shenoy P,Sahu S,et al.Kingfisher:cost-aware elasticity in the cloud.Proceedings of IEEE INFOCOM,Shanghai,China,April 2011

2 Sharma U,Shenoy P,Sahu S,et al.Kingfisher:a System for Elastic Cost-aware Provisioning in the Cloud.Dept of CS,UMASS,Tech Rep UM-CS-2010-005,2010

3 Thanakornworakij T,Nassar R,Leangsuksun C B,et al.An economic model for maximizing profit of a cloud service provider.Proceedings of Seventh International Conference on Availability,Reliability and Security(ARES),Prague,Aug 2012

4 Lee Y C,Wang C,Zomaya A Y,et al.Profit-driven service request scheduling in clouds.Proceedings of 10th IEEE/ACM International Conference on Cluster,Cloud and Grid Computing,Melbourne,May 2010

5 Cao J,Hwang K,Li K,et al.Optimal multiserver configuration for profit maximization in cloud computing.IEEE Transactions on Parallel and Distributed Systems,2013,24(6):1087～1096

6 Irwin D E,Grit L E,Chase J S.Balancing risk and reward in a market-based task service.Proceedings of 13th IEEE International Symposium on High Performance Distributed Computing,Durham,June 2004