云計(jì)算中基于多目標(biāo)優(yōu)化的虛擬機(jī)整合算法

胡志剛　肖慧　李克勤

摘? ?要：云數(shù)據(jù)中心中存在著高能耗和高服務(wù)水平協(xié)議違約率的問題，為了解決此問題，提出了一種基于多目標(biāo)優(yōu)化的虛擬機(jī)整合算法. 綜合考慮能耗、服務(wù)質(zhì)量和遷移開銷等多種因素，將虛擬機(jī)整合問題構(gòu)建為一個(gè)具有資源約束的多目標(biāo)優(yōu)化問題. 使用蟻群系統(tǒng)算法對(duì)該多目標(biāo)優(yōu)化問題進(jìn)行求解，進(jìn)行虛擬機(jī)整合，獲得近似最優(yōu)的虛擬機(jī)主機(jī)映射關(guān)系. 為了減少算法復(fù)雜度，利用CPU利用率雙閾值來判斷主機(jī)負(fù)載狀態(tài)，根據(jù)主機(jī)負(fù)載狀態(tài)分階段進(jìn)行整合并使用不同的整合策略. 基于CloudSim平臺(tái)對(duì)多目標(biāo)優(yōu)化的虛擬機(jī)整合算法和其他6種虛擬機(jī)整合算法進(jìn)行仿真實(shí)驗(yàn)，將本文算法與現(xiàn)有虛擬機(jī)整合算法實(shí)驗(yàn)結(jié)果進(jìn)行比較，結(jié)果表明本文提出的算法在能耗和服務(wù)水平協(xié)議違約方面優(yōu)化顯著，具有較好的綜合性能.

關(guān)鍵詞：云計(jì)算;虛擬機(jī)整合;蟻群系統(tǒng)算法;節(jié)能;服務(wù)質(zhì)量

中圖分類號(hào)：TP338.8? ? ? ??? ? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A

Abstract：There exist problems of high energy consumption and high Service Level Agreement （SLA） violation rates in cloud data centers，which urgently need to be resolved. In order to solve the above problems，a Multi-objective Virtual Machine Consolidation Algorithm （MOVMC） was proposed to reduce energy consumption and SLA violation. Taking into account multiple factors including energy consumption，service quality and migration overhead，the virtual machine consolidation problem was constructed as a resource-constrained multi-objective optimization problem. Ant colony system algorithm was employed to perform virtual machine consolidation and obtain the near-optimal mapping relation between virtual machines and hosts as the solution to the multi-objective optimization problem. In order to reduce the algorithm complexity，the double thresholds of CPU utilization were leveraged to judge the host load status and a multi-stage consolidation was performed according to the host load status，in which different consolidation strategies were used. Simulation experiments were conducted on CloudSim platform for MOVMC algorithm and six other virtual machine consolidation algorithms. The experimental results show that，compared with the existing virtual machine consolidation algorithm，the proposed algorithm has significant optimization in terms of energy consumption and SLA violation，and an excellent comprehensive performance.

Key words：cloud computing;virtual machine consolidation;ant colony system;energy saving;quality of service

近年來，隨著云計(jì)算商業(yè)模式和技術(shù)架構(gòu)的越來越成熟，云用戶大幅度增加，為了滿足他們的需求而新建的數(shù)據(jù)中心、新置的服務(wù)器和制冷設(shè)備也隨之大幅度增加，解決數(shù)據(jù)中心的高能耗問題已經(jīng)成為一個(gè)大的挑戰(zhàn)[1]. 同時(shí)，云用戶對(duì)云服務(wù)的性能需求也愈加具體嚴(yán)格化，用戶在交易前會(huì)與云服務(wù)商制定服務(wù)水平協(xié)議（Service Level Agreement，SLA）來規(guī)范化質(zhì)量等級(jí)（Quality of Service，QoS）需求，以確保本次服務(wù)交易的完美達(dá)成[2]. 如果云服務(wù)商無法提供事先商定的QoS，違背用戶的期望，會(huì)給用戶造成不可預(yù)估的損失. 因此，在減少數(shù)據(jù)中心能耗的同時(shí)，提供用戶所期望的QoS是云計(jì)算發(fā)展迫切需要解決的問題.

虛擬機(jī)整合[3]可以根據(jù)變化的資源需求周期性地調(diào)整當(dāng)前的虛擬機(jī)主機(jī)間映射關(guān)系，在主機(jī)間遷移虛擬機(jī)以充分并均衡地利用計(jì)算資源. 虛擬機(jī)整合技術(shù)主要包括啟發(fā)式貪心算法[4-7]、線性/約束規(guī)劃技術(shù)[8-11]和元啟發(fā)式算法[12-15]. 貪心算法因其時(shí)間復(fù)雜度低、實(shí)現(xiàn)簡(jiǎn)單等優(yōu)點(diǎn)被廣泛應(yīng)用來進(jìn)行虛擬機(jī)動(dòng)態(tài)整合. 貪心算法雖然計(jì)算開銷低，但卻容易陷入局部最優(yōu)而錯(cuò)過最優(yōu)解. 線性/約束規(guī)劃技術(shù)可以獲得最優(yōu)解，但受問題規(guī)模和復(fù)雜性的限制，無法很好地?cái)U(kuò)展到大型數(shù)據(jù)中心. 近年來研究人員提出了許多基于生物啟發(fā)計(jì)算的元啟發(fā)整合算法，例如蟻群算法、基因算法、人工蜂群算法，可以有效幫助解決大規(guī)模問題并避免局部最優(yōu)解. 蟻群系統(tǒng)算法（Ant Colony System，ACS）[16-17]，作為蟻群算法的一種，通過在解空間中進(jìn)行基于概率式的搜索，可以在多項(xiàng)式時(shí)間復(fù)雜度里找到近似最優(yōu)解.

現(xiàn)有的虛擬機(jī)整合研究大多只關(guān)注了云數(shù)據(jù)中心的能耗問題. 然而，為了實(shí)現(xiàn)云系統(tǒng)交付的QoS，還應(yīng)該同時(shí)考慮SLA違約問題. 虛擬機(jī)整合可以通過將虛擬機(jī)整合到盡可能少的主機(jī)上來降低能耗，然而過分整合可能會(huì)降低系統(tǒng)性能并導(dǎo)致SLA違

約[18]. 因此，最優(yōu)虛擬機(jī)整合方法應(yīng)在能耗和QoS之間取得平衡.

本文將虛擬機(jī)整合問題構(gòu)建為一個(gè)多目標(biāo)組合優(yōu)化問題，優(yōu)化目標(biāo)包括降低能耗、保證QoS要求和減少遷移次數(shù)，提出了一種基于多目標(biāo)優(yōu)化的虛擬機(jī)整合算法（Multi-objective Virtual Machine Consolidation，MOVMC）. 首先使用CPU利用率雙閾值[4]來判斷主機(jī)負(fù)載狀態(tài)，確定整合時(shí)機(jī);然后基于ACS假設(shè)虛擬機(jī)和主機(jī)之間的映射關(guān)系是食物源，使用人工蟻群同時(shí)選擇待遷移虛擬機(jī)和目標(biāo)主機(jī)，尋找虛擬機(jī)和主機(jī)之間的最佳映射關(guān)系. 通過在CloudSim平臺(tái)上使用真實(shí)工作負(fù)載來評(píng)估所提出的方法. 實(shí)驗(yàn)結(jié)果表明，該方法在減少能耗、SLA違約和虛擬機(jī)遷移方面具有明顯的優(yōu)勢(shì).

4? ?結(jié)? ?論

本文提出了一種基于多目標(biāo)組合優(yōu)化的虛擬機(jī)整合算法，通過將虛擬機(jī)整合到合適的主機(jī)中來解決數(shù)據(jù)中心中高能耗和QoS降級(jí)的問題. 虛擬機(jī)整合問題被構(gòu)建為一個(gè)多目標(biāo)優(yōu)化問題，基于雙閾值決定觸發(fā)虛擬機(jī)整合的條件. 將虛擬機(jī)與主機(jī)之間的映射關(guān)系比作食物源，基于ACS通過多階段整合來優(yōu)化映射關(guān)系. 通過人工螞蟻的分布式搜索和協(xié)作，獲得虛擬機(jī)與主機(jī)之間的全局最優(yōu)映射關(guān)系. 使用實(shí)際工作負(fù)載對(duì)所提出方法的性能進(jìn)行評(píng)估，仿真結(jié)果表明，與其他方法相比，該方法能有效降低數(shù)據(jù)中心的能耗，并保證高水平QoS.

在未來的工作中，進(jìn)一步研究在整合時(shí)間決策過程中，針對(duì)不斷變化的工作負(fù)載采用自適應(yīng)閾值，做出更合理的遷移決策. 進(jìn)行更多的仿真實(shí)驗(yàn)來評(píng)估所提出的方法在實(shí)際工作負(fù)載中的性能.

參考文獻(xiàn)

[1]? ? 蔡立軍，何庭欽，孟濤，等. 基于層次拓?fù)錁涞奶摂M機(jī)節(jié)能分配算法[J].湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，44（2）：137—148.

CAI L J，HE T Q，MENG T，et al. A network-aware two-phase virtual machine allocation algorithm[J]. Journal of Hunan University（Natural Sciences），2017，44（2）：137—148.（In Chinese）

[2]? ? ARDAGNA D，CASALE G，CIAVOTTA M，et al. Quality-of-service in cloud computing：modeling techniques and their applications[J]. Journal of Internet Services & Applications，2014，5（1）：11—17.

[3]? ?FILHO M C S，MONTEIRO C C，IN?CIO P R M，et al. Approaches for optimizing virtual machine placement and migration in cloud environments：A survey[J]. Journal of Parallel & Distributed Computing，2017，111：222—250.

[4]? ?BELOGLAZOV A，ABAWAJY J，BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future Generation Computer Systems，2012，28（5）：755—768.

[5] BELOGLAZOV A，BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computation：Practice and Experience，2012，24（13）：1397—1420.

[6]? ? ZHOU Z，ABAWAJY J，CHOWDHURY M，et al. Minimizing SLA violation and power consumption in cloud data centers using adaptive energy-aware algorithms[J]. Future Generation Computer Systems，2018，86：836—850.

[7]? ?LI M F，BI J P，LI Z C. Improving consolidation of virtual machine based on virtual switching overhead estimation[J]. Journal of Network and Computer Applications，2016，59：158—167.

[8]? ?CHEN X，TANG J R，ZHANG Y. Towards a virtual machine migration algorithm based on multi-objective optimization[J]. International Journal of Mobile Computing & Multimedia Communications，2017，8（3）：79—89.

[9]? ?CHEN L H，SHEN H Y，PLATT S. Cache contention aware virtual machine placement and migration in cloud datacenters[C]// 2016 IEEE 24th International Conference on Network Protocols （ICNP）. Singapore： IEEE，2016：1—10.

[10]? JOO K N，KIM S，KANG D K，et al. A VM vector management scheme for QoS constraint task scheduling in cloud environment[C]// International Conference on Cloud Computing. Korea：Springer International Publishing，2015：39—49.

[11]? HUANG Z，TSANG D H K. M-convex VM Consolidation：Towards a better VM workload consolidation[J]. IEEE Transactions on Cloud Computing，2016，4（4）：415—428.

[12]? LI Z，YAN C，YU L，et al. Energy-aware and multi-resource overload probability constraint-based virtual machine dynamic consolidation method[J]. Future Generation Computer Systems，2018，80：139—156.

[13]? MOSA A，PATON N W. Optimizing virtual machine placement for energy and SLA in clouds using utility functions[J]. Journal of Cloud Computing，2016，5（1）：1—17.

[14]? LI H J，ZHU G F，CUI C Y，et al. Energy-efficient migration and consolidation algorithm of virtual machines in data centers for cloud computing[J]. Computing，2016，98（3）：303—317.

[15]? ARYANIA A，AGHDASI H S，KHANLI L M. Energy-aware virtual machine consolidation algorithm based on ant colony system[J]. Journal of Grid Computing，2018，16（3）：477—491.

[16]? DORIGO M，CARO G D，GAMBARDELLA L M. Ant algorithms for discrete optimization[J]. Artificial Life，1999，5（2）：137—172.

[17] DORIGO M，GAMBARDELLA L M. Ant colony system：A cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation，1997，1（1）：53—56.

[18]? ZHAO H，WANG J，LIU F，et al. Power-aware and performance-guaranteed virtual machine placement in the cloud[J]. IEEE Transactions on Parallel & Distributed Systems，2018，29（6）：1385—1400.

[19]? 吳小東，韓建軍. 云數(shù)據(jù)中心基于閾值的虛擬機(jī)遷移節(jié)能調(diào)度算法[J]. 華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，46（9）：30—34.

WU X D，HAN J J. Threshold-based energy-efficient VM scheduling in cloud datacenters[J]. Journal of Huazhong University of Science and Technology（Natural Sciences），2018，46（9）：30—34. （In Chinese）

[20]? ZHENG Q H，LI R，LI X Q，et al. A multi-objective biogeography-based optimization for virtual machine placement[C]//2015 15th IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing. Shenzhen：IEEE，2015：687—696.

[21]? CHEN Q，CHEN J X，ZHENG B Y，et al. Utilization-based VM consolidation scheme for power efficiency in cloud data centers[C]// IEEE International Conference on Communication Workshop. London：IEEE，2015：1928—1933.

[22]? LI Z H，YAN C Y，YU X R，et al. Bayesian network-based Virtual Machines consolidation method[J]. Future Generation Computer Systems，2018，16（3）：477—491.

[23]? ZHANG F，LIU G，F(xiàn)U X，et al. A survey on virtual machine migration：challenges，techniques and open issues[J]. IEEE Communications Surveys & Tutorials，2018，20（2）：1206—1243.

[24]? CALHEIROS R N，RANJAN R，BELOGLAZOV A，et al. CloudSim：a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software：Practice and Experience，2011，41（1）：23—50.

[25]? DURAO F，CARVALHO J F S，F(xiàn)ONSEKA A，et al. A systematic review on cloud computing[J]. The Journal of Supercomputing，2014，68（3）：1321—1346.

[26]? PARK K S，PAI V S. COMON：A mostly-scalable monitoring system for planetlab[J]. ACM Sigops Operating Systems Review，2006，40（1）：65—74.