摘要：云计算通过使用虚拟机技术提高了数据中心的资源利用率。虚拟机放置算法作为云计算的关键技术，具有重要研究意义。现有虚拟机放置算法往往只关注成本控制和云资源使用率，忽略了负载均衡对系统性能的影响。针对该问题，本文在标准的粒子群优化算法基础上进行改进，首先设计多目标函数时引入负载不均衡度概念，然后通过系统实时负载随机生成初始化种群，并在算法中引入分组思想，通过对初始种群进行随机分组，避免算法陷入早熟现象。通过CloudSim模拟平台进行仿真实验，表明改进后的算法更利于云数据中心进入负载均衡状态，并有较高的资源利用率。 

　　关键词：云计算；虚拟机放置；负载均衡；多目标优化；粒子优化群算法 

　　引言 

　　云计算概念自2007年提出后产生了巨大的影响，全世界都把云计算作为重点新兴战略产业，为抢占云计算制高点，很多国家都研制并且出台了云计算的战略规划，加快部署并推动国家级的云计算相关应用和云计算基础设施，同时也成为工业界和学术界的研究执占。 

　　云计算的关键技术是资源调度技术，由于虚拟化技术的引入，云资源调度以虚拟机为单位进行，将物理资源分配给用户任务对应的虚拟机。由于系统规模增大导致系统具有复杂性、多样性、异构性和动态性等特征，使得云数据中心基于虚拟机的资源调度充满挑战性，同时也决定了虚拟机放置问题是一个NP-hard问题。在云环境中，虚拟机放置时间比调度算法所需的时间长得多，因此云资源调度需要考虑的主要是虚拟机如何放置的问题。 

　　数据中心服务器的负载是影响系统性能的瓶颈，由于CPU时间分片和网络等影响，服务器负载较高时运行任务具有较长的平均完成时间，因此保证数据中心的负载均衡很重要。现有一些算法往往只关注成本控制和云资源使用率，忽略了负载均衡对系统性能的影响，虽然在一定程度上缓解了云资源与用户需求的矛盾，但云数据中心的资源规模大、资源间差异大、组成复杂等问题直接导致数据中心资源的浪费，现如今还没有很好的虚拟机放置算法快速实现数据中心的负载均衡，因此研究先进的虚拟机放置算法具有重要的现实和学术意义。 

　　l 问题描述 

　　1.1 云资源调度模型 

　　根据云计算的特点，建立云资源调度三层结构二级调度模型如图l所示。三层结构分别为用户层、虚拟层和物理层。二级调度为任务调度和虚拟机调度，任务调度为第一级调度，发生在在用户层和虚拟层之间；虚拟机调度为第二级调度，发生在虚拟层和物理层之间。虚拟资源的调度和分配策略是云计算的核心问题，本文主要研究云环境下二级调度过程中的虚拟机资源分配，即将虚拟机放置到满足条件的服务器上。 

　　1.2 基本定义 

　　定义1：云环境中的虚拟机资源调度是将M个虚拟机部署到N个物理机上，映射模型相当于将M个不同元素放到N个不同元素的集合，共有NM种解决方案，该问题属于装箱问题，即给定集合PM{P1，P2，……，PN}和集合VM{V1，V2，……，VM}，把VM中的M个元素放到PM的N个元素中，保证使用的PM中元素数量最少。 

　　定义2：N为云数据中心物理机的数量，Nuse为数据中心中已经占用的物理机的数量；Uuse为数据中心物理机CPU的平均利用率，Uiuse为物理机i中CPU的利用率；Mnse为数据中心物理机的内存平均利用率，Miuse为物理机i中内存的利用率；Suse为数据中心物理机总存储的平均利用率，Siuse为物理机i中硬盘的利用率。 

　　（3）f3=Min（E），f3表示将虚拟机分配到物理机后数据中心的负载不均衡度函数，其中E即上文1.2定义的负载不均衡度，该函数表示E值越小表示系统越平衡。 

　　2 基于改进粒子群算法的虚拟机放置算法 

　　2.1 粒子群优化算法介绍 

　　1995年由美国博士Kennedy和Eberhart通过研究鸟群觅食行为提出粒子群算法（Particle Swarm Optimization，PSO）。设想场景：一群鸟在随机搜寻食物，区域内仅有一块食物，所有鸟都不知道食物在哪里，但它们知道当前位置离食物多远，那么找到食物最有效的策略就是搜寻目前离食物最近鸟的周围区域。PSO算法是一种基于群体的自适应搜索优化算法。算法中每个优化问题的潜在可能解都称其为“粒子”（Particle），每个粒子都有一个被目标函数所决定的适应值（Fitness Value），还有一个速度决定飞翔的方向和距离。每个粒子均受局部最优信息和全局最优信息影响，以一定速度在整个解空间飞行，飞行速度和位置由个体飞行经验和群体飞行经验动态调整，以便用于信息交换。通过大量实验研究，证实了群体中个体之间的社会协作和信息共享有助于整体进化，用公式表示如下： 

　　虽然标准PSO算法优点很多，但是随机性很大，多样性比较差，很容易陷入局部最优现象，因此需要完善，下面将介绍本文改进的粒子群算法。 

　　2.2 基于改进粒子群算法的虚拟机放置算法 

　　2.2.1 算法设计 

　　1.粒子群算法编码 

　　首先对n个待部署虚拟机进行编码形成队列，然后通过虚拟机放置算法得到虚拟机与数据中心m个物理机的映射关系，最后按照映射关系将虚拟机放置到对应物理机上，从而实现优化目标。种群中的每个粒子的位置和速度分别用公式（3）和公式（4）表示，如下所示：