面向成本優化的云計算資源分配方法研究

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

（中國聯合網絡通信有限公司研究院 北京100032）

1 引言

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

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

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

2 相關工作

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

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

3 面向成本優化的虛擬機資源分配問題描述

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

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

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

圖1 云計算資源分配框架

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

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

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

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

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

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

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

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

（1）粒子重定義

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

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

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

（2）慣性權重調整

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

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

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

算法流程如圖2所示。

圖2 算法流程

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

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

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

步驟2迭代控制：判斷算法是否達到最大迭代次數，是則轉到步驟4；否則執行步驟3；

步驟3迭代過程：

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

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

（3）執行步驟2；

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

5 仿真結果

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

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

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

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

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

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

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

圖3 資源總收益對比

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

6 結束語

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

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