云计算中虚拟机放置多目标优化

李硕硕+孙红

摘 要：提高云计算系统资源利用率一直是云计算研究的重点内容之一。 基于此，将传统的多目标蚁群算法进行改进，并结合排除法解决虚拟机放置的多目标优化的问题，该算法可以通过信息素的不断更新，最终收敛得到最优解。主要考虑了服务级合约违背率（S）、资源损耗（W）、电源消耗（P）3个因素。 实验结果表明，与传统的启发式方法和遗传算法相比，该算法有利于并行计算，能够在多个相互冲突的目标间实现最优权衡和折衷，在服务级合约违背率较少的情况下，系统资源浪费和电源消耗最少，具有可行性。

关键词关键词：云计算；虚拟机放置；多目标优化；蚁群算法；排除法

DOIDOI：10.11907/rjdk.162036

中图分类号：TP302

文献标识码：A 文章编号文章编号：16727800（2016）011000103

基金项目基金项目：国家自然科学基金项目（61170277；61472256）；上海市教委科研创新重点项目（12zz137）；沪江基金项目（C14002）

作者简介作者简介：李硕硕（1989-），男，山东菏泽人，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为计算机网络通信与云计算；孙红（1964-），女，上海人，博士，上海理工大学光电信息与计算机工程学院副教授、硕士生导师，研究方向为计算机网络通信与云计算、控制科学与工程、模式识别与智能系统。

0 引言

云计算作为一种新技术，近年来成为信息领域的研究热点。如今，云计算已经成为通过互联网提供访问和服务的新型模式。如果资源分布不合理，那么必然会导致资源浪费。实现虚拟机放置的多目标优化具有重要意义。现有研究大多采用传统的启发式方法[1]或者遗传算法[2]等算法进行虚拟机的放置。虽然这些算法都可以在一定程度上解决虚拟机放置问题，但是存在各自的局限性。例如，启发式方法虽然可以在虚拟机放置中解决局部最优解问题，但该方法缺乏全局寻优能力；遗传算法虽然在多目标优化方面有一定优势，但无法充分利用反馈信息，致使搜索具有盲目性，求解到一定范围时求解最优解的效率比较低。

本文引入本地管理层和全局管理层的管理框架，通过这种管理框架有利于对虚拟机的放置和资源的分配作出更好的决策。本文所用方法是对传统蚁群算法进行改进，并且与排除法相结合，有利于并行计算，效率更高。能够在服务级合约违背率（S）、资源损耗（W）、电源消耗（P）3个相互冲突的目标间得到最优的权衡，在服务级合约违背率较少的情况下，系统资源浪费和电源消耗最少。

1 虚拟机放置

1.1 管理框架

云计算中基础设施节点数量非常庞大，使得建立架构非常困难，本文管理框架为两层管理，分别为本地管理和全局管理，如图1所示。本地管理管理主机等云基础设全局管理运行在一个主节点上，其通过监控收集来自本地管理中的各种信息，包括用户服务质量、资源消耗和电源消耗等，然后对虚拟机的放置和资源分配作出决策。

图1 系统管理结构

1.2 虚拟机放置数学模型

虚拟机放置问题一直是云计算研究的重点，其为典型的装箱问题。文献[3]证明了虚拟机放置属于NP-hard问题。根据图1中系统管理框架可知，本文在虚拟机初始化放置问题上实施全局管理需要考虑以下3个因素：服务级合约违背率（S）、资源损耗（R）、电源消耗（P）。其中m、n分别表示物理节点和虚拟机的数量，cj表示第j个物理节点拥有的相应资源容量，ri表示第i个虚拟机请求的资源容量。其数学模型描述如下：

式（1）中的3个目标分别是服务级合约违背率（S）、资源损耗（R）、电源消耗（P）。公式（2）～（4）约束了每个物理节点上分配的CPU、内存和网络带宽等资源不会超过其自身的容量。其中，公式（5）约束了每一个虚拟机只可分配到一台物理节点上。

2 基于蚁群算法的多目标优化虚拟机放置策略

蚁群算法是一种可以用来寻找最优解决方案的技术，该算法在虚拟机放置问题上应用比较广泛，并且在处理组合优化问题上具有一定优势。具体设计步骤和处理过程如下：

2.1 适宜度函数

适应度函数的选取在遗传算法中具有重要意义，本文根据公式（1）分别定义了3个子适宜度函数，取值[0，1]。SLA违背率函数（fSLA）、资源利用函数（fresource）、电源消耗函数（fpower），如公式（6）、（7）：

2.3 概率转移函数

2.4 最优解集的构建

利用排除法[4]构造非支配集在多目标遗传算法中是比较常用的方法，本文利用排除法并对其适当改进来处理蚁群算法搜索过程中得到的解，由此实现对于Paxeto解集的构建过程，过程如下：

3 实验结果与分析

本文实验在C1oudSim[4]上实现完成，cloudsim是澳大利亚墨尔本大学的网格实验室和Gridbus项目宣布推出的云计算仿真软。本文运用蚁群算法对资源分配，和其它一些算法进行了实验对比。

实验设定80个物理节点，每个节点的配置均为10GB的内存、1TB的存储和1Gbps的带宽，而CPU的能力等价为1 000，2 000和3 000MIPS。虚拟机的请求数量为200个，其中对CPU的请求分别为250，500，750和1 000MIPS，内存为4GB，存储为200GB，带宽为200Mbps。物理结点在CPU利用率为0%和100%时所消耗的电源分别为175W和250W。实验结果如图2、图3、图4所示。

4 结语

本文采用的算法是一种改进的分布式多目标优化蚁群算法，该算法是将传统的多目标蚁群算法进行改进，选取了服务级合约违背率（S）、资源损耗（W）、电源消耗（P）3个目标，并结合排除法解决虚拟机放置中这3个目标优化的问题。实验结果表明，与传统的启发式方法和遗传算法相比，本文提出的算法能够在服务级合约违背率较少的情况下，有效减少系统资源浪费和电源消耗，具有可行性。本文已将电源消耗作为管理目标之一，接下来将考虑如何兼顾数据中心网络流量等其它方面，从而使其更加完善。

参考文献：

[1] HYEAR C，MCKEE B， GARDNER R，et al.Autonomic virtual machine placement in the data center[J].Hewlett Packard Laboratories，Tech.Rep，2007：2007189.

[2] 李进超，陈静怡，吴杰，等.基于改进分组遗传算法的虚拟机放置研究[J].计算机工程与设计，2012，33（5）：20532056..

[3] CAREY M R，JOHNSON D S.Computers and lntractability：a guide to NPcompleteness[J].1979.

[4] CALHEIROS R N，RANJAN R，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）：2350.

（责任编辑：陈福时）