龚炳江，冯谦谦，赵晓峰

(1.河北工程大学 信息与电气工程学院，河北 邯郸 056038；2.河北工程大学 管理与工商学院，河北 邯郸 056038)

0 引 言

云数据中心的虚拟机资源异构性和物理机规格的不一致性，导致了服务器内部和云数据中心的资源负载不均衡[1]。因此，如何定义虚拟机和物理节点之间的映射关系对系统的性能产生重要的影响。一些学者采用传统的启发式算法或者改进的启发式算法来进行全局化搜索，解决虚拟机的放置问题[2-4]。尽管传统启发式算法简单易行，但是容易产生局部最优解，无法获得全局最优解。文献[5,6]采用蚁群算法和粒子群算法求解虚拟机部署问题具有较好的效果，但是仍存在收敛速度慢、容易陷入局部最优等缺陷；文献[7]采用基于虚拟机的编码方式，存在编码冗余等缺点，并没有将遗传算法的效率发挥到最大。本文在分组遗传算法的基础上，采用资源利用率多维标准差控制参量，设计适应度函数引导搜索解空间。此外，采用轮盘赌方式选择参与交叉过程的染色体，比较定义的基因评估参数值，确定较优的基因进行交叉，使得子代染色体能够较大可能继承父类染色体的优秀基因。而变异采用随机删除较差基因来改变子代的染色体编码，提高最优解的收敛速度。通过实验分析，提出的虚拟放置算法能够有效减少资源浪费，提高数据中心的整体能效。

1 调度算法模型

1.1 多维资源模型

假设物理机集合P={p1,p2,…,pn}，数据中心的物理机总数为n，物理机提供的资源容量集合Qi={qi,1,qi,2,…,qi,d}(1≤i≤n)，其中qi,d表示物理机i能提供的d类型资源的容量(比如CPU、内存、磁盘和带宽的容量)；虚拟机集合V={v1,v2,…,vm}，需要放置的虚拟机总数为m，虚拟机请求的资源大小集合Ri={ri,1,rj,2,…,rj,d}(1≤j≤m)，其中rj,d表示虚拟机j所需求的d类型资源的大小。本节主要符号定义见表1。

表1 主要的符号定义和含义

虚拟机放置算法为找到一个激活较少的物理机，以获得尽量大的资源利用率的虚拟机到物理机的映射方案。可以做如下描述

(1)

(2)

(3)

其中，目标函数式(2)中数据中心物理机的所有资源平均利用率u，通过式(7)～式(9)推导而来。第一条约束条件表示物理机分配的资源不超过其容量限制，第二条约束条件表示每个虚拟机只能放置到唯一的物理机上，第三条约束条件表示pi，vi,j的取值范围为0或1。

1.2 服务器能耗模型

假设数据中心有n台服务器组建而成，服务器i上的能耗为Ei。服务器作为数据中心能耗的主要来源，服务器的负载受到其所负载的虚拟机数目和虚拟机内负载的影响，所以虚拟机数量越多、负载越大，则服务器的负载越大。根据文献[8]的研究，物理服务器的功率能耗Pmax与服务器利用率u呈现一种线性关系，表示为

P(u)=cPmax+(1-c)Pmax

(4)

式中：Pmax是服务器满负载时的最大功耗，c是服务器空载与满载时的功耗比，一般Pmax取值为175w，c的取值为0.7。则在特定时间T内，服务器i的功耗可以表示为

(5)

数据中心的能耗E，可以表示为

(6)

1.3 负载均衡度量指标

物理机内部资源的不充分利用和物理机配置的差异性，导致物理机内部的负载不均衡和不同物理机间的负载不均衡。这种负载分配不均的情况直接影响云数据中心整体能效，需要合理的虚拟机部署策略和负载均衡度量指标保持物理机的负载均衡。为了得到度量指标，考虑以下参数。

物理机i上l类型资源利用率

(7)

物理机i上资源平均资源利用率

(8)

数据中心资源的综合利用率

(9)

物理机i的资源负载不均衡度

(10)

云数据中心的整体负载不均衡度

(11)

Ni作为单个物理机内部资源负载均衡度量的指标，N作为数据中心的物理机负载均衡度量指标。可见，负载不均衡度的值越小，表示系统负载越均衡，系统的性能越好。

2 算法实现

2.1 染色体编码

装箱问题已经提出3种表示方式：基于箱子的表示，基于物品的表示，基于分组的表示[9]。前面两种编码方式，是面向单个项的，具有高度冗余和重复编码等缺点，不适合这类问题的费用函数优化。本文采用基于分组的表示方式，如图1所示，染色体编码BCDA(B={3,6}，C={5}，D={4,2}，A={1})，表示6台虚拟机映射到4台物理机上。这种的表示方式的特别之处是遗传算子对分组部分进行操作，相较于前两种表示方式，不易造成染色体过长而影响计算的效率。

图1 染色体编码

2.2 选 择

2.3 交 叉

交叉算子尽量使得后代继承父类染色体中较优秀的基因，以此得到更优秀的后代。将单个物理机的资源利用率和资源负载均衡度的比值作为基因的评估参数gi=ui/N。评估参数值的大小取决于物理机上资源的利用率和资源负载情况，资源的利用率越高以及资源负载越均衡，评估参数gi的值越大。根据评估参数gi在父类的整个评估参数和中所占的比重，选择参与交叉的基因。这样，在交叉过程中子代继承到优秀基因即虚拟机放置合理的物理机的可能性越大，有效避免因为随机选择遗传基因而使得算法效率过低的情况。

假设参与交叉的两个父类染色体分别为X、Y，从父类X中选择较优秀的基因即评估参数较高的基因插入到父类Y中的随机交叉点中，而产生新的子代染色体。在交叉的过程中，可能出现在不同的物理机中出现重复虚拟机的情况，这时需要删除出现重复虚拟机的物理机。而由于删除操作所产生的孤立的虚拟机采用FFD算法回填。具体的交叉过程，如图2所示。

图2 交叉过程

2.4 变 异

变异操作是遗传算法中不可或缺的一部分，有利于增加种群多样性。算法的期望目标是激活较少的物理机获得较大的资源利用率进而降低能耗。因此，变异算子采用消除一个已使用的物理机及变异后没有依赖的虚拟机即解中缺少某些虚拟机需要采用FFD算法回填的方式。选择基因评估参数gi作为衡量被消除物理机的标准，基因评估参数gi越大表示该物理机中虚拟机放置越合理，其被删除的可能性越小，使变异向着较优的方向发展。以此增强算法局部的随机搜索能力，逼近最优解。

2.5 适应度函数

适应度函数的选取直接影响到算法的收敛速度和能否找到最优解。适应度函数值是算法衡量种群中个体染色体搜索的标准，也就是算法迭代过程中通过其对个体染色体优劣程度进行评价。所以，当适应度函数值越大，个体染色体基因越优秀被遗传的可能性越大，最终得到的解也最好。为了达到激活最少的物理机以获得最大的资源利用率的目标，适应度函数的设计综合考虑激活物理机的数目和资源的利用情况。因此采用式(12)作为算法的适应度函数

(12)

式中：Z为个体中激活的物理机的总数目，U为个体中物理机的平均资源利用率，N为个体中物理机的资源负载不均衡度。

3 仿真实验结果及分析

本文算法采用Cloudsim云仿真平台[10]作为实验仿真工具，对其进行了扩展，改写了Host类、VMAllocationPolicy类和Datacenter类等相关类，实现虚拟机放置算法。

3.1 实验仿真环境

仿真了500台物理机构成了数据中心，为了方便算法性能的测试，设置了10 000 MIPS的CPU、50 GB的内存、1 TB的存储和10 G的带宽。具体设置的虚拟机参数，见表2。

表2 虚拟机参数信息

为分析算法在不同的虚拟机请求规模时的性能，同时将工作负载规模分别为100、200、300、400、500个虚拟机实例运行10次，将10次实验数据的平均值作为实验评估的最终数据。

3.2 仿真实验结果与分析

为了验证本文所提出的虚拟机放置算法(IGGA)的性能和有效性，与基于降序适应算法(FFD)的虚拟机放置策略和基于传统的遗传算法(GA)的虚拟机放置策略进行了比较。

如图3和图4所示，在同一虚拟机请求规模下，IGGA算法在物理机激活数目和资源的综合利用率方面都明显优于FFD算法和GA算法。而且激活物理机的数目与虚拟机请求规模有着密切联系。随着虚拟机请求规模的增大，激活的物理机数目也随之增加。同时，虚拟机的请求规模也影响着资源的综合利用率，资源的综合利用率在某一区间内波动。

图3 激活物理机数目比较

图4 资源综合利用率比较

如图5所示，IGGA算法在系统能耗方面优于FFD算法和GA算法，其启动的物理机数目最少，资源综合利用率最高，所需系统能耗也最小。因而，系统启动物理机数目越少，资源利用率越高，进而可以降低系统的能耗。

图5 系统能耗比较

如图6所示，反映了3种算法在不同的虚拟机规模下的负载不均衡度波动情况。在同一虚拟机的请求规模下，IGGA算法的负载不均衡度小于FFD算法和GA算法，表明改进的算法在负载均衡方面的性能优于它们。FFD算法性能在负载均衡和能耗方面最差，该算法较大程度的减少激活物理机的数目，使个别主机的负载过高，负载不均衡造成了资源浪费和能源损耗。传统的GA算法具有高度冗余和重复编码的缺点，造成算法性能并不理想。本文改进的算法对各方面进行了的优化，在能耗和负载均衡方面具有更好的性能，能够提高云数据中心的整体能效。

图6 负载不均衡度比较

4 结束语

实现低能耗和负载均衡的云数据中心至关重要，如何提高数据中心的整体能效是值得人们关注的问题。本文通过建立多维资源模型、服务器能耗模型和负载均衡度量指标并结合传统启发式算法对分组遗传算法选择、交叉、变异等方面进行了更好的优化，提出了一种面向云数据中心能效优化虚拟机放置算法。仿真实验表明，改进的算法能够有效降低启用物理机的数目，最小化数据中心的能耗，提高了数据中心整体能效。

[1]Anam Sultana Moheet Khan,Prajakta P Chapke.Cloud computing:Comparison with grid computing,cloud service mo-dels,architecture,components,and virtualization[J].International Journal of Advanced Research in Computer Science and Software Engineering,2015,5(1):1087-1093.

[2]Gao Yongqiang,Guan Haibing,Qi Zhengwei,et al.A multi-objective ant colony system algorithm for virtual machine placement in cloud conmputing[J].Journal of Computer and System Sciences,2013,79(8):1230-1242.

[3]Beloglazoy A,Abawajy J,Buyya R.Energy efficient resource allocation heuristics for efficient management of data centers for cloud computing[J].Future Generation Computer Systems,2012,28(5):755-768.

[4]Xu Bo,Peng Zhiping,Xiao Fangxiong,et al.Dynamic deployment of virtual machine in cloud computing using multi-objective optimization[J].Soft Computing,2015,19(8):2265-2273.

[5]ZHAO Jun,MA Zhong,LIU Chi,et al.Multi-objective ant colony optimization algorithm for virtual machine placement[J].Journal of Xidian University(Natural Science),2015,42(3):191-197(in Chinese).[赵君,马中,刘驰,等.一种修改的多目标蚁群系统虚拟机放置算法[J].西安电子科技大学学报(自然科学版),2015,42(3):191-197.]

[6]YANG Jing,ZHANG Hongjun,ZHAO Shuining,et al.Virtual machine deployment strategy based on particle swarm optimization algorithm[J].Journal of Computer Applications,2016,36(1):117-121(in Chinese).[杨靖,张宏军,赵水宁,等.基于粒子群算法的虚拟机部署策略[J].计算机应用,2016,36(1):117-121.]

[7]HUANG Zhaonian,LI Haishan,ZHAO Jun.Virtual machine placement algorithm based on improved genetic algorithm[J].Scientific Journal of Computer Science,2015,42(11A):406-407(in Chinese).[黄兆年,李海山,赵君.基于双适应度遗传算法的虚拟机放置的研究[J].计算机科学,2015,42(11A):406-407.]

[8]Xiong F,Zhou C.Virtual machine selection and placement for dynamic consolidation in cloud computing environment[J].Frontiers of Computer Science,2015,9(2):322-330.

[9]WANG Yongzhen,CHEN Yan,YU Yingying.Improved grouping genetic algorithm for solving multiple traveling salesman problem[J].Journal of Electronics & Information Technology,2017,39(1):198-205(in Chinese).[王勇臻,陈燕,于莹莹.求解多旅行商问题的改进分组遗传算法[J].电子与信息学报,2017,39(1):198-205.]

[10]WEI Liang,HUANG Tao,CHEN Jianya,et al.Workload prediction-based algorithm for consolidation of virtual machines[J].Journal of Electronics & Information Technology,2013,35(2):1271-1276(in Chinese).[魏亮,黄韬,陈建亚,等.基于工作负载预测的虚拟机整合算法[J].电子与信息学报,2013,35(2):1271-1276.]