基于改进萤火虫算法的虚拟机迁移策略研究

王 娜，刘春霞，党伟超，白尚旺

(太原科技大学 计算机科学与技术学院，太原 030024)

目前学术界针对虚拟机动态迁移问题进行了大量的研究工作，主要集中在两个方面，一是单纯的虚拟机迁移策略方面，主要考虑负载、网络带宽、SLA违规、虚拟机迁移次数等性能指标的影响；一是迁移过程中源、目的主机以及虚拟机选择方面，利用相关的智能算法来优化虚拟机分配与放置，减少能量消耗。为了能有效识别出过载节点，研究人员进行了深入研究。Hsu等[1]提出一种静态阈值(Static Threshold，ST)的方法进行虚拟机迁移，该方法利用CPU利用率设定一个阈值，当主机CPU利用率超过该阈值时判定为过载主机，进行虚拟机迁移，否则不进行迁移，该方法可以有效降低数据中心能耗。Jain等[2]提出一种负载均衡方法，通过使用较低和较高CPU利用率阈值来选择源主机，然后将选定的虚拟机放置到耗电量最低的物理主机上，以最大限度地降低能耗。Jianrong等[3]提出一种基于负载预测的动态虚拟机整合算法，通过预测主机在下一时刻的负载来判断主机的负载状态，进而触发虚拟机迁移，该方法有效降低了虚拟机迁移次数，进而降低了数据中心的能耗。上述方法都是通过基于阈值或基于预测的方法来识别热点，具有一定的局限性，且在计算各物理主机负载时，仅仅考虑了CPU或内存的影响。文献[4]则证明了虚拟机迁移过程中所产生的能耗大小受可用带宽的影响。因此，上述方法都没有全面考虑虚拟机迁移过程中多重因素对能耗的影响。

有效识别出热点只是虚拟机迁移的基础，在迁移过程中，还需要找到适合迁移的虚拟机以及适当的目的主机。Dong等[5]提出一种虚拟机分配方法，通过多目标优化来提高资源利用率并减少物理节点的使用数量，从而达到降低能耗的目标。Ghribi等[6]提出了一种虚拟机分配算法和虚拟机整合算法，使用线性整数规划算法来优化服务器数量，降低了数据中心的总能耗。Tseng等[7]提出一种支持向量机的虚拟机迁移方法，在特定的时间完成了虚拟机最大资源利用率。Radhakrishnan等[8]提出一种使用神经网络和遗传算法相结合的方法选择目的主机，实现了数据中心能耗降低。上述方法都着重考虑了虚拟机迁移次数和能耗问题，但由于追求降低数据中心能耗可能导致云计算供应商遵守违反与用户签订的服务等级协议(Service Lever Agreement，SLA)，从而影响数据中心的服务质量。

Kansal等[9]提出一种基于萤火虫算法的虚拟机迁移技术，将虚拟机迁移过程看做是萤火虫的生物行为，利用萤火虫总是朝亮度最大的萤火虫移动这一生物现象来实现虚拟机的迁移过程，将物理主机上负载最大的虚拟机迁移到亮度最大的物理节点上。该方法存在以下不足：(1)仅考虑了CPU和内存对能耗的影响；(2)在选择热点时可能会陷入局部最优解；(3)忽视服务质量的影响。

综上，为更好实现云端服务的负载均衡、容错、优化服务器的电能管理，本文提出一种基于改进萤火虫算法FA_SA(Firefly algorithm and Simulated Annealing algorithm)的虚拟机迁移策略，利用模拟退火算法在局部最优解能概率性地跳出并最终趋于全局最优的优点，有效识别热点，迁移负载最大的虚拟机到能耗最低的节点，完成迁移调度，降低数据中心能耗，同时保证云端服务质量。

1 相关定义

1.1 算法机理

萤火虫算法(Firefly Algorithm，FA)[10]是群体智能搜索算法的一种，其思想源于模拟萤火虫晚上群聚觅食，通过散发荧光素吸引同伴的自然现象。在搜索空间中随机初始化一群萤火虫，搜索和迭代过程看作成萤火虫个体间相互吸引和位移的过程。

在FA算法中存在两个关键要素：萤火虫的荧光亮度和个体间的吸引力。荧光亮度反映了萤火虫位置的优劣，亮度越高位置越好，对同伴的吸引力越强。吸引力取决于亮度和距离，故种群中亮度较低的萤火虫寻找自己邻域内荧光较亮的萤火虫并向其移动靠拢，其位置在不断更新中完成迭代，最终聚集在亮度最高的萤火虫周围，即搜索空间中最优位置附近，从而实现目标优化。

1.2 迁移过程模拟

虚拟机迁移的过程主要分为三个步骤：过载主机的判定、待迁虚拟机的选择以及目的主机的选择。本文将虚拟机迁移过程模拟为萤火虫觅食的生物行为，把物理机集群看作是萤火虫的聚集群，使虚拟机与萤火虫个体进行对应，待迁虚拟机看作是新加入觅食的萤火虫，通过不断地移动寻找到最优位置，此时荧光最亮的萤火虫位置即为需要选择的目标主机。

具体做如下定义：

(1)将数据中心看做一个萤火虫种群。用x表示萤火虫，即物理主机；将n表示为萤火虫的个数，即数据中心中物理主机的个数，则数据中心中各物理主机用向量表示为xi=(x1，x2，…，xn).

(2)物理主机的亮度即为物理主机能耗值的大小。用EC(Energy Consumption)表示能耗，EC值越大，表示能耗值越大，则亮度越小；EC值越小，表示能耗值越小，则亮度越大。

(3)将两个物理主机之间能耗的差值作为距离，即吸引力，用于判断该主机是否为为热点，即是否需要进行虚拟机迁移。

2 改进萤火虫算法的迁移策略

为解决萤火虫算法易陷入局部最优解从而造成虚拟机无效迁移的问题，本文引入模拟退火机制，将萤火虫算法的全局搜索和模拟退火算法的随机搜索能力相结合，提出一种基于改进萤火虫算法(FA_SA)的虚拟机迁移调度方法。

2.1 模拟退火机制

模拟退火算法(Simulated Annealing，SA)[11]是由美国物理学家Metropolis等人在1953年提出的，是基于蒙特卡罗(Monte Carlo)迭代求解法的一种启发式随机搜索算法，引入物理学中的固体退火过程，如图1所示，随着固体温度越来越高，固体内的各个粒子会变得杂乱无序，内能会越来越大；随着温度降低，固体内的各个粒子会逐渐趋于稳定，内能会越来越小。模拟退火算法的核心是以一定的概率接受当前非优解，从而跳出局部最优解继续搜索，进而得到全局最优解。模拟退火算法的一般流程为：

图1 模拟退火内能变化[12]

(1)初始化温度T、降温次数M、衰减因子λ以及每个T值的迭代次数L，令k=0；

(2)随机产生初始解状态X；

(3)从X的领域中随机产生新的状态X′；

(4)计算目标函数差Δ=f(X′)-f(X)，其中f(X)为优化目标函数；

(5)如果Δ<0，使X=X′；如果Δ≥0，且e-ΔEI(kT)≥0，θ∈(0，1)的随机数，使X=X′；

(6)如果达到最大降温次数M，则输出模拟退火过程中最好的解Xbest并结束算法；否则令Tk+1=λTk，k=k+1，返回第(3)步继续执行。

2.2 源主机的选择

源主机是由于过载或潜在过载需要进行虚拟机迁移的物理节点，有效选择源主机是完成虚拟机迁移过程的关键。判定过程分为五步。

第一步：计算能耗值(Energy Consumption，EC).由于数据中心物理主机的能耗大小不仅与CPU和内存有关，而且受网络带宽的影响，因此本文依据式1对物理主机的能耗进行计算，并存储在列表中。

(1)

其中，λ表示cpu、内存和带宽对能耗影响的权值，满足0<λcpu，λram，λbw<1且λcpu+λram+λbw=1，由于CPU资源是影响数据中心能耗的关键因素，因此，本文设定λcpu=1/2，λram=λbw=1/4；v表示运行在第i个物理节点上虚拟机的数量；u表示分配给虚拟机的总任务数；cpuijk、ramijk和bwijk分别表示第i个物理节点上j个虚拟机运行k个任务的CPU利用率、内存利用率和带宽利用率；C、M和B分别表示分配给第i个物理节点的CPU值、内存值和带宽值。

第二步：计算物理主机的节点计算时间(Node Computation Time，NCT)。NCT表示运行该物理主机上所有任务所需要的时间。根据式(2)[5]获得NCT值，并存储在列表中。

④切实加强河道砂石资源费的征收与使用。各区县水行政主管部门要严格按照相关规定，认真抓好砂石资源费足额征收工作，要保证“三江”河流100%、其他河流20%的砂石资源费缴入市级金库，其他河流80%的砂石资源费缴入区县级金库。 同时，要切实用好河道砂石资源，将砂石资源费首先用于河道管理。

(2)

其中，NCTijk表示在第i个节点上第j个虚拟机上运行k个任务所需要的时间。

第三步：计算吸引力指数(Attraction Index，AI)。通过计算AI值来模拟萤火虫的吸引力。AI值的存储形式为AIi(ECi，NCTi)，其中ECi表示第i个节点的能耗值；NCTi表示第i个节点的节点计算时间。根据EC值对AI列表进行升序排列，EC值最小的节点为列表中第一个元素。

第四步：计算距离(Distance).源主机表示需要进行虚拟机迁移的物理主机，其实际是过载主机或潜在过载主机，因此，将EC值大于阈值的物理主机重新组合为新的种群List，并根据式(3)获得距离值。

Distance=Avg(Listmin，Listmax)

(3)

其中，Listmin和Listmax分别表示List列表中的中间元素和最大元素值。

第五步：采用模拟退火算法查找源主机。

新种群中存储的是过载主机或潜在过载主机，即潜在源主机。将List列表中EC值离距离Distance最近的物理主机作为初始解，结合模拟退火算法依据式(4)对List列表进行搜索，获得源主机。

p=

(4)

(5)

其中，p表示接受当前解的概率；Y(x)表示目标函数，该函数值由EC值和该物理主机的下一刻EC值共同决定。

当新解当前时刻的EC值大于当前解的EC值并且新解预测所得下一时刻的EC值大于新解的EC值时，以概率为1完全接受新解；否则，依据式(5)计算概率，并以此概率接受较差的新解。对当前解重复“产生新解→计算目标函数值→接受或丢弃”的迭代，并最终获得近似最优解。

2.3 待迁虚拟机的选择

选择从源主机上需要迁移的虚拟机。根据式(6)计算该源主机上每个虚拟机的负载值，然后将其存储在列表中，查找列表中的最大负载值，具有最大负载值的虚拟机就是需要进行迁移的虚拟机。

(6)

其中，jobj表示在第i个节点的第j个虚拟机上运行的任务总数量；分母表示第i个节点在Δt时间内的能耗值。

2.4 目的主机的选择

萤火虫总是向荧光更亮的节点移动，因此，如果一个节点的EC值最低，那么这个节点就是最亮的节点，即AI列表中的第一个元素是最亮的节点，也就是说，该节点为目标主机节点。

2.5 距离更新

每次获得源主机后需要一次迭代更新以便完成下一次的虚拟机迁移，该更新即为距离的更新。根据式(7)完成距离的更新。

Distancet+1=Distancet+Loadij+ε

(7)

其中，Distancet+1和Distancet分别表示第t时刻和第t+1时刻的距离值；Loadij表示当前虚拟机的负载值；ε表示高斯分布误差。

融合了模拟退火机制的虚拟机迁移调度算法的流程图如图2所示。

图2 改进萤火虫算法的流程图

3 实验与结果分析

使用Cloudsim仿真平台作为实验环境。该实验模拟构造了一个由800台物理主机组成的数据中心，这些物理主机分为两类：400台类型为HP ProLiant ML110 G4(Intel Xeon 3040，2 Cores×1 860 MHz，4 GB)的物理主机和400台类型为HP ProLiant ML110 G5(Intel Xeon 3075，2 Cores×2 660 MHz，4 GB)的物理主机。在这些物理主机上，运行如表1所示的四种类型的虚拟机。为了使运行在该平台上的物理主机和虚拟机负载更接近现实情况，使用了PlantLab CoMon项目提供的虚拟机监测数据，该数据包含了分布在全球500多个不同地区的1 000多个虚拟机的监测信息。本次实验从2011年3月到4月中随机选择10天的数据作为实验数据，配置情况如表1所示。

表1 虚拟机配置

本文使用数据中心能耗(Energy Consumption，EC)、服务等级协议违例率(SLA Violations，SLAV)、虚拟机迁移次数(Migrs)以及服务质量和能耗的综合评价(Energy and SLA Violation，ESV)作为评价指标。其中，EC值越低表示节能效果越好；SLAV用式(8)计算，SLAV值越低表示其服务质量越好；ESV的值通过式(9)获得，该指标值越低表示数据中心的能耗和服务质量的综合表现越好。

(8)

ESV=EC×SLAV

(9)

其中，N和V分别表示物理主机的个数和虚拟机的数量；Toi表示该物理主机过载的总时间；Tvi表示该虚拟机完成迁移所花费的时间；Tai表示该物理主机总的活动时间。

首先，在同等条件下分别从单纯考虑CPU和内存因素以及综合考虑CPU、内存和带宽因素对能耗、平均迁移时间的影响进行对比实验，如图3所示。由图可知，在虚拟机平均迁移时间方面，综合考虑CPU、内存和带宽所使用的平均迁移时间更短。当考虑带宽因素时，整个虚拟机迁移过程产生的能耗值有所下降，具有一定的优化效果。

利用萤火虫算法选择源主机阶段，只是选择离距离值最近的物理主机作为源主机，具有一定的局限性，本文在此阶段融入模拟退火算法，避免在源主机的选择过程中陷入局部最优解。

分别使用基本萤火虫算法和融入模拟退火算法的萤火虫算法进行实验，得到迁移时间的标准方差值，如图4所示。由图可知，使用基本萤火虫算法获得的迁移时间标准方差值大多数情况下大于使用融入模拟退火算法的萤火虫算法获得的迁移时间标准方差值，说明融入模拟退火算法后，虚拟机迁移时间有所下降，即在一定程度上提高了虚拟机的迁移效率。

通过实验，对文献[1]提出的ST方法、文献[13]提出局部加权回归(the Local Regression，LR)法、FA方法和FA_SA所产生的能耗以及违例率进行对比，对比结果如表2和表3所示。其中，FA_SA方法对物理主机负载进行预测完成虚拟机迁移，在一定程度上降低了数据中心能耗，并有效降低了SLA违例率。

由表2和表3可以看出，ST方法在一定程度上有效的降低了数据中心的能耗，但该方法的违例率却明显的上升；LR方法虽然在数据中心的能耗上有所提升，但其违例率却有明显的下降；而FA方法以及FA_SA方法在数据中心能耗和违例率两方面均有所提升，既有效地降低了数据中心能耗又保证了服务质量，其中，FA_SA方法较FA方法在降低数据中心能耗和提高服务质量两方面均有更明显的效果。

图5和图6分别表示使用各算法时数据中心的能耗变化以及SLA违例率变化。由图5和图6可知，使用LR算法时数据中心产生的能耗最大，但其违例率此时是最小的；当使用ST算法时，数据中心产生的能耗值最小，但其违例率是最大的；这两种方法只能单方面保证数据中心的能耗值降低或者服务质量提高。使用FA算法虽然产生的能耗值比ST算法高，但其违例率却较低，在一定程度上既达到了数据中心能耗降低由保证了数据中心的服务质量。相较FA算法，本文提出的FA_SA算法能耗值又有所下降，效果较好。

图5 EC变化

图6 SLAV变化

图7对比了使用各算法时虚拟机迁移次数的变化。由图7可知，使用LR算法时虚拟机迁移次数最多，所产生的能耗值也最大；使用本文提出的FA_SA算法所产生的虚拟机迁移次数在大多数情况下最小，相比FA算法，迁移次数多可能是因为数据集选择不当造成的。

图8对比了使用各算法时ESV的变化。ESV是评价算法是否适用于数据中心虚拟机迁移的综合指标。由图8可知，使用ST方法时，ESV最大，表示该算法不能很好适用于数据中心虚拟机迁移过程，所提供的服务质量较低；而本文提出的FA_SA算法的ESV值最低，表示该算法能较好的适用于该过程，为用户提供较好的服务质量，优化效果更明显。

图8 ESV变化

4 结论

本文综合考虑CPU、内存和带宽等因素对能耗的影响，结合模拟退火算法，提出一种基于改进萤火虫算法的虚拟机调度策略，利用萤火虫算法的全局搜索和模拟退火算法局部搜索的优点选择待迁源主机，将源主机上负载最大的虚拟机迁移到能耗最低的目的节点。通过与ST、LR和FA算法进行对比实验，结果表明，提出的FA_SA算法方法不仅有效降低了数据中心能耗、虚拟机迁移次数、SLA违例率，而且保证了服务质量，达到了较明显的优化效果。