云计算中基于多目标优化的虚拟机整合算法

胡志刚　肖慧　李克勤

摘   要：云数据中心中存在着高能耗和高服务水平协议违约率的问题，为了解决此问题，提出了一种基于多目标优化的虚拟机整合算法. 综合考虑能耗、服务质量和迁移开销等多种因素，将虚拟机整合问题构建为一个具有资源约束的多目标优化问题. 使用蚁群系统算法对该多目标优化问题进行求解，进行虚拟机整合，获得近似最优的虚拟机主机映射关系. 为了减少算法复杂度，利用CPU利用率双阈值来判断主机负载状态，根据主机负载状态分阶段进行整合并使用不同的整合策略. 基于CloudSim平台对多目标优化的虚拟机整合算法和其他6种虚拟机整合算法进行仿真实验，将本文算法与现有虚拟机整合算法实验结果进行比较，结果表明本文提出的算法在能耗和服務水平协议违约方面优化显著，具有较好的综合性能.

关键词：云计算;虚拟机整合;蚁群系统算法;节能;服务质量

中图分类号：TP338.8                    文献标志码：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

近年来，随着云计算商业模式和技术架构的越来越成熟，云用户大幅度增加，为了满足他们的需求而新建的数据中心、新置的服务器和制冷设备也随之大幅度增加，解决数据中心的高能耗问题已经成为一个大的挑战[1]. 同时，云用户对云服务的性能需求也愈加具体严格化，用户在交易前会与云服务商制定服务水平协议（Service Level Agreement，SLA）来规范化质量等级（Quality of Service，QoS）需求，以确保本次服务交易的完美达成[2]. 如果云服务商无法提供事先商定的QoS，违背用户的期望，会给用户造成不可预估的损失. 因此，在减少数据中心能耗的同时，提供用户所期望的QoS是云计算发展迫切需要解决的问题.

虚拟机整合[3]可以根据变化的资源需求周期性地调整当前的虚拟机主机间映射关系，在主机间迁移虚拟机以充分并均衡地利用计算资源. 虚拟机整合技术主要包括启发式贪心算法[4-7]、线性/约束规划技术[8-11]和元启发式算法[12-15]. 贪心算法因其时间复杂度低、实现简单等优点被广泛应用来进行虚拟机动态整合. 贪心算法虽然计算开销低，但却容易陷入局部最优而错过最优解. 线性/约束规划技术可以获得最优解，但受问题规模和复杂性的限制，无法很好地扩展到大型数据中心. 近年来研究人员提出了许多基于生物启发计算的元启发整合算法，例如蚁群算法、基因算法、人工蜂群算法，可以有效帮助解决大规模问题并避免局部最优解. 蚁群系统算法（Ant Colony System，ACS）[16-17]，作为蚁群算法的一种，通过在解空间中进行基于概率式的搜索，可以在多项式时间复杂度里找到近似最优解.

现有的虚拟机整合研究大多只关注了云数据中心的能耗问题. 然而，为了实现云系统交付的QoS，还应该同时考虑SLA违约问题. 虚拟机整合可以通过将虚拟机整合到尽可能少的主机上来降低能耗，然而过分整合可能会降低系统性能并导致SLA违

约[18]. 因此，最优虚拟机整合方法应在能耗和QoS之间取得平衡.

本文将虚拟机整合问题构建为一个多目标组合优化问题，优化目标包括降低能耗、保证QoS要求和减少迁移次数，提出了一种基于多目标优化的虚拟机整合算法（Multi-objective Virtual Machine Consolidation，MOVMC）. 首先使用CPU利用率双阈值[4]来判断主机负载状态，确定整合时机;然后基于ACS假设虚拟机和主机之间的映射关系是食物源，使用人工蚁群同时选择待迁移虚拟机和目标主机，寻找虚拟机和主机之间的最佳映射关系. 通过在CloudSim平台上使用真实工作负载来评估所提出的方法. 实验结果表明，该方法在减少能耗、SLA违约和虚拟机迁移方面具有明显的优势.

4   结   论

本文提出了一种基于多目标组合优化的虚拟机整合算法，通过将虚拟机整合到合适的主机中来解决数据中心中高能耗和QoS降级的问题. 虚拟机整合问题被构建为一个多目标优化问题，基于双阈值决定触发虚拟机整合的条件. 将虚拟机与主机之间的映射关系比作食物源，基于ACS通过多阶段整合来优化映射关系. 通过人工蚂蚁的分布式搜索和协作，获得虚拟机与主机之间的全局最优映射关系. 使用实际工作負载对所提出方法的性能进行评估，仿真结果表明，与其他方法相比，该方法能有效降低数据中心的能耗，并保证高水平QoS.

在未来的工作中，进一步研究在整合时间决策过程中，针对不断变化的工作负载采用自适应阈值，做出更合理的迁移决策. 进行更多的仿真实验来评估所提出的方法在实际工作负载中的性能.

参考文献

[1]    蔡立军，何庭钦，孟涛，等. 基于层次拓扑树的虚拟机节能分配算法[J].湖南大学学报（自然科学版），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]  吳小东，韩建军. 云数据中心基于阈值的虚拟机迁移节能调度算法[J]. 华中科技大学学报（自然科学版），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，FU 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，FONSEKA 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.