基于优化AHP的虚拟机部署与调度策略

罗 树，沈记全

（河南理工大学 计算机科学与技术学院，河南 焦作454000）

0 引 言

为实现虚拟机的高效部署［1－5］，国内外研究者从不同的角度寻找虚拟机部署的最优方案。Hirofuchi等通过虚拟机实时迁移方式实现IaaS数据中心的动态整合，在降低能耗的同时保持了任务的连续性，却没有形成具体的调度机制［6］；Goiri等提出了一种低功耗的虚拟机部署感知模型，有效降低了能源消耗，但没有考虑数据中心的负载均衡［7］；Li等提出基于改进分组遗传算法的虚拟机放置策略，有效地提高了虚拟机放置问题的求解速度，没有针对动态负载情况进行研究［8］；Gao等采用蚁群算法进行虚拟机部署，提高了物理服务器的资源利用率，优化了能耗问题，却容易陷入局部最优解［9］；Zhuang等提出了一种基于多属性层次分析的虚拟机部署与调度策略，能够实现对虚拟机部署与迁移最佳方案的选择，但没有考虑虚拟机之间的资源竞争问题［10］。

本文构建了一种基于层次分析 （analytic hierarchy process，AHP）优化算法的虚拟机部署与调度策略。它首先通过物理服务器躲避机制对目标物理服务器进行初次筛选，然后采用层次分析模型根据用户任务类型对虚拟机部署方案进行预测评估。实验结果表明，该策略在实现物理服务器负载均衡的基础上，有效提高了物理资源的利用率，并在资源优化配置方面有较好的效果。

1 基于AHP的虚拟机选择影响因素模型

层次分析法［11］（AHP）是一种针对多目标的层次权重决策分析方法，它将决策问题分解成不同的层次结构，并采用一定的标准对各层次影响因素进行客观量化，较好地实现了定性与定量分析在各类多方案决策问题方面的广泛应用［12］。运用AHP选择虚拟机部署方案的步骤如下：

（1）构建各影响因素层次结构模型。本文层次结构模型主要由目标层、准则层及方案层构成。目标层是最佳虚拟机与目标物理服务器节点部署方案；根据用户对资源的需求特征，虚拟机可分为计算型、存储型、网络型以及无特殊需求型，因此准则层以CPU 资源、内存资源及宽带资源等作为影响因素；方案层是所有满足要求的部署方案。

（2）构建各影响因素间的对比矩阵，利用虚拟机CPU资源、内存资源以及宽带资源相对于目标物理服务器选择的重要程度构建对比矩阵A，如式 （1）所示，并根据AHP的1～9标度赋值，见表1

在矩阵A 中资源影响因素CPU、内存、带宽分别记为c、m、b，ai为准则层各影响因素对目标层物理服务器节点选择的重要程度，Aij为准则层的第i类影响因素和第j类影响因素相比对于目标层物理服务器节点选择的重要程度。

表1 1～9标度含义

（3）一致性检验，如果矩阵A 满足 （2），则矩阵A 具有一致性

（4）权重向量计算，首先计算矩阵A 最大特征值λmax，然后根据式 （3）计算其特征向量N

对特征向量N 作归一化处理即得到虚拟机所需资源的权重向量w，各分量体现了CPU、内存、宽带资源对目标物理服务器节点选择的影响权重

依据虚拟机资源需求权重向量以及目标物理节点资源使用情况的乘积，计算目标物理服务器节点部署该虚拟机的承受能力的预估值，预估值越小，则目标节点对部署虚拟机的承受能力越强，虚拟机的服务质量也就越高。

2 基于AHP优化算法的虚拟机部署与调度

本文主要优化目标是实现数据中心负载均衡度和资源利用率的提高。在虚拟机部署与调度时，通过物理服务器躲避列表，判断虚拟机资源需求类型与物理服务器类型标志的一致性，对目标物理服务器进行初次选择，以避免相同资源需求虚拟机对物理资源的竞争；运用层次分析模型对虚拟机资源进行量化分析，并根据虚拟机资源需求的权重向量与物理服务器节点的资源使用情况对符合条件的目标物理服务器节点预测评估，从而选择最佳虚拟机与目标物理服务器部署方案，并按照虚拟机的资源需求类型设置物理服务器的类型标志。

2.1 基于AHP优化算法的虚拟机部署策略

在某一段时间，假设需要将n台虚拟机部署到数据中心的m 台物理服务器节点上，其中，Vmi＝｛Vm1，Vm2，…，Vmn｝表示待部署虚拟机集合，Pmj＝｛Pm1，Pm2，…，Pmm｝表示物理服务器集合。

对于集合Vmi中任意Vm，若Vm首次开启，获取其它相同资源需求类型虚拟机提供正常服务时对物理资源的平均使用值R1；若Vm重启，获取该虚拟机以往对物理资源的平均使用值R2；将平均值作为该虚拟机开启时资源使用情况的预估值

通过性能监控查询Pmj中所有物理服务器当前资源使用情况Rp及其类型标志M

根据矩阵A 计算虚拟机CPU、内存以及带宽资源相对于目标物理服务器选择的影响权重，并取得相应的权重向量w

判断当前物理服务器类型标志与虚拟机资源需求的一致性，若一致，说明该物理服务器已部署相同资源需求的虚拟机，将其加入到该虚拟机的物理服务器躲避列表Ki；若不一致，需满足式 （9），即部署该虚拟机时物理资源使用不能超过该物理服务器资源使用量的上限阀值Rp＿up

根据式 （10）计算待部署Vm对Pmj中所有物理服务器的预估值，S表示预估值集合

选择预估值集合S中最小值Smin，其对应的物理服务器即目标物理服务器，然后将虚拟机部署到该物理服务器上并启动。

每次部署完成时，按照虚拟机资源需求设置目标物理服务器标志，并将物理服务器加入相应Ki。

Algorithm1：虚拟机部署算法 输入：待部署虚拟机集合Vmi ，可用物理服务器集合Pmj ，各虚拟机资源需求类型M′输出：各虚拟机Vm 的目标物理服务器节点P m for every Vmin Vmido 运用AHP评估虚拟机M′的权重向量w； if（Vm 首次启动）do 获取与Vm 资源需求类型相同的虚拟机的平均资源使用情况R1 ； else 获取Vm 以往运行时平均资源使用情况R2 ； end if； for（Pm 属于Pmj ）do 查询Pm 当前资源情况Rp 及其类型标志M； if（M 与M′一致）do 将Pm 加入Vm 的物理服务器躲避列表Ki； else while（式 （9）成立）do 根据式 （10）计算Pm 的预估值信息S； end while； end if； end for； for（Smin 属于S） 获取所有物理服务器预估值最小的Smin，其对应的Pm即目标物理服务器； end for； 将Vm 部署到Pm ，并启动该虚拟机任务； 设置目标物理服务器Pm 的类型标志；end for；

2.2 基于AHP优化算法的虚拟机的调度策略

某一时间段，假设数据中心存在需要进行动态负载均衡的物理服务器B 及其它m 台物理服务器，其中Vmi＝｛Vm1，Vm2，…，Vmn｝表示B上所有虚拟机集合，Pmj＝｛Pm1，Pm2，…，Pmm｝表示其它物理服务器集合，负载均衡就是选择最佳的虚拟机与目标物理节点调度方案，并重新启动该虚拟机任务。

获取物理服务器B当前的资源使用情况RB与集合Pmj中各物理服务器节点当前资源使用情况Rm及各自的类型标志M

运用AHP分析评估物理服务器B上所有虚拟机的权向量w，获取各虚拟机运行过程中对服务器资源的使用情况及资源需求，取平均值R3作为虚拟机重启后对服务器资源使用情况的预估值

判断当前物理服务器类型标志与待迁移虚拟机资源需求的一致性，若一致，说明物理服务器已部署相同类型的虚拟机，将其加入躲避列表Ki；若不一致，需满足式（14），即物理资源使用不能超过物理服务器资源使用量的上限阀值Rp＿up

然后按照式 （10）计算所有满足条件的物理服务器的预估值信息，选择物理节点B 上每一台虚拟机对Pmj中各物理服务器预估值信息的最小值，记为集合S；根据式（15）计算虚拟机迁出后，物理节点B的预估值信息S′

G 表示原物理服务器B 相对于目标物理服务器负载的轻松度，若G 小于1，表示目标物理服务器的负载比物理服务器B要轻松，则方案可行，记录S信息；若G 大于1，表示目标物理服务器的负载比物理服务器B 的负载要重，则方案不可行

最后，在所有备选方案中选择预估值信息S最小的方案，将待迁移虚拟机迁移到目标物理服务器，并重新启动该虚拟机任务。

Algorithm2：虚拟机负载均衡算法 输入：资源过载物理节点B及其上运行的虚拟机集合Vmi ，物理节点集合Pm j 输出：最佳的迁移方案f 根据对数据中心实时监控，获取B当前资源使用情况信息，记为RB ；for（Vm 属于Vmi）do获取虚拟机Vm 的资源使用情况及其资源需求类型M′，并获取该虚拟机的平均资源使用量R3 ；运用AHP模型对虚拟机Vm 进行分析评估，计算其权重向量w；for（Pm 属于Pmj ）do 查询Pmj 中Pm 的当前资源使用情况Rm 及其类型标志M； if（M 与M′一致）do

将Pm 加入Vm 的物理服务器躲避列表Ki；else while（式 （14）成立）do 根据式 （10）计算Pm 的预估值信息S； end while；end if；end for；获取Pmj 中所有服务器预估值信息的最小值S；按式 （15）计算B放弃Vm 的预估值信息S′；根据式 （16）判断当前方案下物理服务器B 节点与目标物理服务器的相对轻松度G if（G＜1）do 该方案可行，记录S相关信息，并将当前虚拟机迁移方案加入到备选方案列表F中；else 该方案不可行，放弃对Vm 的迁出方案；end if；end for；for（f属于F）do 在F中查询拥有最小S值的方案f，即最佳虚拟机与目标物理服务器迁移方案。end for；根据方案f进行虚拟机迁出，重新启动该虚拟机；

3 实验与分析

3.1 实验设计

为评估优化策略性能，本文在CloudSim［13］云平台下进行仿真实验。通过对CloudSim 的扩展编译以及相关类和接口的改写，获取相应的实验环境，并完成虚拟机部署与调度测试。本实验中所需虚拟机的类型、数量、CPU 及内存参数见表2，物理服务器数量、CPU 及内存参数见表3。

表2 虚拟机资源需求

表3 物理服务器资源

3.2 实验分析

为了评估优化策略的平衡效果和资源利用率，本文同时采用表4所示的3种策略进行仿真实验，并对它们的性能进行了比较。由于启发式算法结果的随机性，在相同实验环境下对每种部署策略进行5次仿真实验，统计并分析每种策略下各物理服务器达到平衡状态时的动态迁移总次数及其资源使用情况，实验结果如图1～图3所示。

表4 实验策略

图1 动态迁移总次数

图2 5次测试的CPU 利用率

图1显示3种策略达到平衡状态时物理服务器动态迁移的总次数。其中，策略1在虚拟机部署时的迁移次数最多，且在多次迁移的过程中占用大量物理服务器资源，因此服务器的物理资源利用率比较低；策略2和策略3能够有效地降低负载均衡过程中的动态迁移总次数，提高物理服务器的资源利用率；策略3通过引入躲避机制，将相同资源需求的虚拟机部署到不同的物理服务器，避免了由于虚拟机对相同资源竞争而产生的动态迁移，进一步提高了物理资源的利用率。

图3 5次测试的内存利用率

图2和图3显示了采用3种策略达到平衡时各物理服务器的负载情况。从图中可看出采用策略1时，物理服务器CPU 利用率以及内存利用率曲线波动较大，各物理服务器节点的物理资源 负载极不均衡；采用策略2和策略3时CPU 利用率以及内存利用率曲线波动较小，都能有效解决数据中心物理服务器负载均衡问题，并保持较好的均衡效果；在策略3下物理服务器间CPU 利用率及内存利用率波动最小，负载均衡效果最佳，物理服务器的资源利用率及虚拟机服务质量最高。

4 结束语

为避免同一台物理服务器节点上各虚拟机之间对相同物理资源的竞争，提出了基于层次分析优化的虚拟机部署与调度策略。通过物理服务器躲避机制对目标物理服务器进行初次筛选，将不同资源需求的虚拟机部署到同一台物理服务器，以实现虚拟机互补；根据层次分析模型对虚拟机进行量化分析，并利用物理服务器资源使用情况选择最佳虚拟机与物理服务器部署方案。通过CloudSim 云仿真实验，本文优化策略进一步减少了物理服务器达到负载平衡时的动态迁移次数，提高了资源利用率，使得整个数据中心服务器资源更趋于平衡，保证了物理服务器上虚拟机的服务质量。

［1］Armbrust M，Fox A，Griffith，et al.Above the clonds：A Berkeley view of cloud computing，UCB／EECS－2009－28 ［R］.Springfield，USA：University of Callifomia，Berkeley：Engineer and Computer Science Department，2009.

［2］LIU Peng.Cloud computing ［M］.2rd ed.Beijing：Publishing House of Electronics Industry，2011：1－12（in Chinese）.［刘鹏.云计算［M］.2版.北京：电子工业出版社，2011：1－12.］

［3］LUO Junzhou，JIN Jiahui，SONG Aibo，et al.Cloud computing：Architecture and key technologies［J］.Journal on Communications，2011，37 （7）：3－21 （in Chinese）. ［罗 军舟，金嘉晖，宋爱波，等.云计算：体系架构与关键技术 ［J］.通信学报，2011，37 （7）：3－21.］

［4］Barham P，Dragovic B，Fraser K，et al.Xen and the art of virtualization ［C］／／Proceedings of the 19th ACM SOSP.New York：ACM Press，2003：164－177.

［5］HAN Dezhi，LI Nannan，BI Kun.Study of virtualization technology in cloud environment［J］.Huazhong University of Science＆Technology （Natural Science Edition），2012，40 （S1）：262－265 （in Chinese）.［韩德志，李楠楠，毕坤.云环境下的虚拟化技术探析 ［J］.华中科技大学学报 （自然科学版），2012，40 （S1）：262－265.］

［6］Hirofuchi T，Nakada H，Itoh S，et al.Reactive consolidation of virtual machines enabled by postcopy live migration ［C］／／Proceedings of the 5th International Workshop on Virtualization Technologies in Distributed Computing.ACM，2011：11－18.

［7］Goiri I，Julia F，Nou R，et al.Energy－aware scheduling in virtualized datacenters ［C］／／IEEE International Conference on Cluster Computing.IEEE，2010：58－67.

［8］LI Jinchao，CHEN Jingyi，WU Jie，et al.Virtual machine placement research based on improved grouping genetic algorithm ［J］.Computer Engineering and Design，2012，33 （5）：2053－2056 （in Chinese）.［李进超，陈静怡，吴杰，等.基于改进分组遗传算法的虚拟机放置研究 ［J］.计算机工程与设计，2012，33 （5）：2053－2056.］

［9］Gao Yongqiang，Guan Haibing，Qi Zhengwei，et al.A multiobjective ant colony system algorithm for virtual machine placement in cloud computing ［J］.Journal of Computer and System Sciences，2013，79 （8）：1230－1242.

［10］ZHUANG Wei，GUI Xiaolin，LIN Jiancai，et al.Deployment and scheduling of virtual machines in cloud computing：An“AHP”approach［J］.Journal of Xi’an JiaoTong University，2013，47（2）：28－32（in Chinese）.［庄威，桂小林，林建材，等.云环境下基于多属性层次分析的虚拟机部署与调度策略 ［J］.西安交通大学学报，2013，47 （2）：28－32.］

［11］JIAO Bo，HUANG Chengdong，HUANG Fei，et al.An aggregation method for the AHP judgment matrices based on optimum possibility－satisfiability degree ［J］.Control and Decision，2013，28 （8）：1242－1246 （in Chinese）.［焦波，黄赪东，黄飞，等.一种基于最优可能满意度的群AHP 判断矩阵集结方法 ［J］.控制与决策，2013，28 （8）：1242－1246.］

［12］CHEN Xixiang，QIU Jing，LIU Guanjun.Research on the method of test－equipment selection based on analytic hierarchy process and fuzzy comprehensive assessment［J］.ACTA ArmamentarII，2010，31 （1）：68－73 （in Chinese）. ［陈希祥，邱静，刘冠军.基于层次分析法与模糊综合评判的测试设备选择方法研究 ［J］.兵工学报，2010，31 （1）：68－73.］

［13］Caltheiros R N，Ranjan R，Cesar AF，et al.CloudSim：A novel framework for modeling and simulation of cloud computing infrastructures and services，GRIDS－TR－2009－1 ［R］.Parkville，VIC：The University of Melbourne Australia，Grid Computing and Distributed Systems Laboratory，2009.