Migration Strategy of Green Cloud Computing Virtual Machine Based on Ant Colony Optimization Algorithm

LÜ Ting-qin; WEI Meng

doi:10.13718/j.cnki.xsxb.2020.12.013

In order to improve the energy efficiency of green cloud computing and reduce its energy consumption, a virtual machine migration strategy based on ant colony optimization algorithm has been proposed. The goal of this strategy is to minimize the energy consumption of cloud computing center while ensuring service quality. Firstly, low-load and overloaded physical machines are identified by presupposing resource utilization threshold; then, energy-saving is achieved by moving out virtual machines on low-load and overloaded server nodes; and finally, according to the virtual machine migration list, ant colony optimization algorithm is used to quickly find the best physical machines for virtual machine migration. The simulation results show that compared with other algorithms, the proposed migration strategy has the least execution time and energy consumption.

HTML

云计算是一种按需付费的模式，根据用户需求为用户提供一个由网络、服务器和存储设备等众多资源组成的共享池.由于网络设备的激增和网络服务需求的日益增长，使得整体网络数据流量和能耗急剧增加，因此，面向可持续发展的低能耗、低成本的绿色云计算模式成为未来发展的方向^[1-2].绿色计算的概念是在2005年提出的，提倡在使用信息技术硬件时考虑到电消耗、热耗散等因素，达到降低能耗、节能环保的目标^[3].绿色云计算是指在云计算环境中，通过进行有效的能效管理，在满足服务质量(Quality of Service，QoS)的同时，解决云计算带来的环境、能耗及运营成本问题.因此，绿色云计算的重点不在于重新研制低能耗的基础设备，而是从现有资源出发，做到高效整合利用^[4].

近年来，绿色云计算领域已经引起全球研究人员的广泛关注.针对云计算的能耗和资源利用问题，国内外学者取得了一系列重要的研究和应用成果.文献[5]算法通过采用多租户方式和虚拟机实时迁移技术，使得程序调度的功耗更低.文献[6]针对绿色云计算中的能耗问题，提出了一种基于任务调度的资源感知负载均衡克隆算法.该算法在负载均衡策略中引入克隆选择原理，解决了节能资源感知调度问题.文献[7]提出了一种用于异构云环境的自适应任务分配算法，该算法通过最小化云系统的完工时间来降低能耗，促进绿色云计算.上述方法从任务调度的方法出发，实现了部分节能的效果，但是没有考虑数据中心的物理结构.数据中心的资源管理是一个具有挑战性的问题，云数据中心接近26%的功耗是由物理机(physical machine，PM)或服务器引起的.而虚拟机(virtual machine，VM)的合理配置和动态管理可以大大降低数据中心的功耗，提高其吞吐量.但是，VM放置过程需要进行VM迁移操作，不正确的VM放置可能会启动大量的VM迁移过程，降低云数据中心的性能.因此，合理有效的虚拟机迁移也是一种实现绿色云计算节能的重要方式^[8].文献[9]提出了一种基于学习自动机的新算法，可以提高资源利用率并减少能耗.所提出的算法考虑了用户需求资源的变化来估计过载现象，通过避免PM过载问题的发生来减少迁移次数，并关闭了空闲PM以减少功耗.但是，它不能检测到利用率较低的PM.

为了降低云计算数据中心的能耗，本文提出了一种虚拟机迁移策略，用于减少数据中心上的能耗，平衡不同物理机之间的负载，实现数据中心的最大效率.该方法首先根据预设阈值判断物理机的负载情况，然后根据负载情况，利用虚拟机迁移技术从指定物理机中迁移虚拟任务，以实现休眠低负载PM和平衡高负载PM的目的.同时，将蚁群优化算法应用到虚拟机迁移过程中，用于快速寻找适合迁移的最佳物理机.

2. 基于蚁群优化算法的迁移技术

2.1. 蚁群优化算法

蚁群优化算法^[11](Ant Colony Optimization，ACO)的灵感来源于自然界，是一种元启发式的全局最优化搜索方法.蚁群在觅食过程中，会留下一种称为信息素的化学物质，在行进时，蚂蚁总会倾向于选择信息素浓度高的路线.假若在食物和蚁巢之间存在多条路径，初始时每条路径上都有蚂蚁爬过，但是经过一段时间的循环，单位时间内最短路径上爬过的蚂蚁数量会增多，释放信息素的量变大，那么后续蚂蚁都会选择信息素多的路径，从而找出最短路径.

蚁群优化算法的寻优过程大致分成移动概率计算、信息素的局部调整和全局更新几个步骤.移动概率是指蚂蚁在运动时，根据每条路径上信息素的量决定转移方向的可能性.蚂蚁在t时刻从节点i移动到节点j的移动概率p_i，j(t)可表示为

其中，τ_i，j(t)表示t时刻节点(i，j)上的信息素数量，η_i，j(t)表示t时刻节点(i，j)上的启发函数，η_i，j(t)=1/d_i，j，d_i，j表示节点(i，j)之间的欧几里得距离，C(t)表示第k只蚂蚁下一步允许选择的目的地集合，α，β表示控制参数.

信息素的局部调整是指每只蚂蚁在建立解的过程中，需要在经过s时刻后，调整节点(i，j)之间的局部信息素：

其中，ξ∈[0, 1]是控制因子，d_min是最近2个节点的距离，n表示节点数量.

信息素的全局更新是指生成全局最优解的蚂蚁对其信息素的更新：

其中，ρ∈[0, 1]是挥发系数，Δτ_i，j^k(t)和Δτ_i，j(t)分别表示一次循环第k只蚂蚁和m个蚂蚁在节点(i，j)处的信息素增量.

2.2. 虚拟机迁移技术

绿色云计算是云计算存储和处理云数据的节能方法.云计算中心的服务对象是随机选择的，导致当前服务器节点的负载状态是随机的，即存在一部分服务器节点负载很高和一部分服务器节点负载较低的现象.本文虚拟机迁移目标是最小化云计算中心能耗的同时保证服务质量：一方面采取让一部分资源利用率低的服务器节点进入休眠状态，达到节能的目的；另一方面为了避免资源过度聚合，根据虚拟机的动态改变情况，采用最小迁移时间的方式进行虚拟机迁移.

数据中心有n台物理机和m台虚拟机，在虚拟机资源总和不超过物理机资源上限的前提下，最小总耗能可以被描述为

其中，h(j)表示虚拟机j所在的物理机，q_i，l表示物理机i的第l个资源，v_j，l表示虚拟机j的第l个资源.p_i是物理机i的能耗量，由于CPU是决定物理机电能能耗的主要因素，因此物理机i的能耗量可由下式计算得到：

其中，u_i表示物理机i的CPU利用率，p_max，p_min分别表示物理机i在u_i最大和空闲状态下的能耗.

虚拟机迁移问题可以分成迁移触发、迁移策略和迁移方向3个子问题.

1) 迁移触发：首先设定资源利用率上限和下限阈值U_up，U_down，当CPU利用率大于U_up时，表示物理机处于过载状态，需要迁出部分虚拟机以避免降低用户体验；当CPU利用率小于U_down时，表示物理机处于低负载状态，为了关闭物理机，降低能耗，需要迁出所有虚拟机. CPU的性能由单字长定点指令平均执行速度(Million Instructions Per Second，MIPS)指标来衡量.

2) 迁移策略：在低负载情况下，由于将虚拟机全部迁出，不需要制定迁移策略；但是过载情况时，主机中的虚拟机采用最小迁移时间(Minimum Migration Time，MMT)策略进行迁移，即将总迁移时间最大的虚拟机留在原物理机上：

其中，mt_j表示迁移时间，u_i，j表示虚拟机j占用的CPU与物理机i的总CPU之间的比值.

对于MMT问题，本文采用贪心算法进行求解，解决步骤为：首先根据迁移时间和MIPS指标的比值，将虚拟机按非降序排列，然后依次选择迁出虚拟机，直到物理机的CPU利用率降到U_up之下.

3) 迁移方向：采用蚁群优化算法来判断虚拟机的迁移方向.首先，将虚拟机的状态信息记录到蚂蚁的内存后，蚂蚁进行移动.蚂蚁在搜索服务器时根据节点信息素浓度来选择下一个移动的节点.在以往的蚁群算法文献中，路径选择的概率大小由信息素决定，但是在本文的虚拟机迁移问题中，假设蚂蚁经过的路径节点已经进行了负载均衡优化操作，为了使蚂蚁可以尽力搜索所有的节点，确保整体负载均衡，在利用蚁群优化算法时认为信息素越大的节点被选择移动的概率越小.因此，式子(1)和(5)修改为

其中，L_j，pm(t)表示t时刻节点j的负载均衡值.

下面给出本文方法的算法伪码：

4. 结论

为了实现绿色云计算，降低数据中心的能耗，提出了一种基于蚁群优化算法的虚拟机迁移策略，该策略的目标是使云计算中心的能耗最小化.基于此思路，一方面将资源利用率低的服务器节点进入休眠状态，达到节能的目的，另一方面以最小迁移时间的方式迁移虚拟机，以避免资源过度聚合时的时间和能量消耗.根据虚拟机迁移列表，采用蚁群优化算法快速寻找虚拟机迁移最佳方式.实验结果表明，本文提出的迁移策略在能耗和执行时间方面明显优于其他算法.

Figure (5) Table (2) Reference (12)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	MORENS, INGLE R.Challenges in Green Computing for Energy Saving Techniques[C]//2017 International Conference on Emerging Trends & Innovation in ICT (ICEI). Beijing, China: IEEE, 2017: 73-76. Google Scholar
[2]	BATALLA J M, VASILAKOS A, GAJEWSKI M.Saving Techniques Secure Smart Homes:Opportunities and Challenges[J].ACM Computing Surveys (CSUR), 2017, 50(5):75. Google Scholar
[3]	ZHOU R T, LI Z P, WU C.A Truthful Online Mechanism for Location-Aware Tasks in Mobile Crowd Sensing[J].IEEE Transactions on Mobile Computing, 2018, 17(8):1737-1749. Google Scholar
[4]	TIAN J, MA Y.Load Balancing Method Based on a Performance and Power Ratio[C]//2018 13th Asia Joint Conference on Information Security (AsiaJCIS).Guilin, China: IEEE, 2018: 75-82. Google Scholar
[5]	王以伍, 陈跃辉.数据中心中能量与QoS保障的虚拟机部署[J].计算机应用与软件, 2019, 36(5):51-57. Google Scholar
[6]	RAO G J, BABU G S.Energy Analysis of Task Scheduling Algorithms in Green Cloud[C]//2017 International Conference on Innovative Mechanisms for Industry Applications (ICIMIA).Bangalore, India: IEEE, 2017: 302-305. Google Scholar
[7]	LU Y, SUN N.An Effective Task Scheduling Algorithm Based on Dynamic Energy Management and Efficient Resource Utilization in Green Cloud Computing Environment[J].Cluster Computing, 2019, 22(1):513-520. Google Scholar
[8]	MISHRA S K, PUTHAL D, SAHOO B, et al. An Adaptive Task Allocation Technique for Green Cloud Computing[J]. The Journal of Supercomputing, 2018, 74(1):370-385. Google Scholar
[9]	RANJBARI M, AKBARIT J.A Learning Automata-based Algorithm for Energy and SLA Efficient Consolidation of Virtual Machines in Cloud Data Centers[J].Journal of Parallel and Distributed Computing, 2018, 113:55-62. Google Scholar
[10]	吴小东, 韩建军.云数据中心基于阈值的虚拟机迁移节能调度算法[J].华中科技大学学报(自然科学版), 2018, 46(9):30-34. Google Scholar
[11]	ZHANG Y, YU Y L, ZHANG S L, et al.Ant Colony Optimization for Cuckoo Search Algorithm for Permutation Flow Shop Scheduling Problem[J].Systems Science & Control Engineering, 2019, 7(1):20-27. Google Scholar
[12]	KARTHIKEYAN K, SUNDER R, SHANKAR K, et al.Energy Consumption Analysis of Virtual Machine Migration in Cloud Using Hybrid Swarm Optimization (ABC-BA)[J].The Journal of Supercomputing, 2020, 76(5):3374-3390. Google Scholar

Message Board

Migration Strategy of Green Cloud Computing Virtual Machine Based on Ant Colony Optimization Algorithm

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors