摘要：云计算通过使用虚拟机技术提高了数据中心的资源利用率。虚拟机放置算法作为云计算的关键技术，具有重要研究意义。现有虚拟机放置算法往往只关注成本控制和云资源使用率，忽略了负载均衡对系统性能的影响。针对该问题，本文在标准的粒子群优化算法基础上进行改进，首先设计多目标函数时引入负载不均衡度概念，然后通过系统实时负载随机生成初始化种群，并在算法中引入分组思想，通过对初始种群进行随机分组，避免算法陷入早熟现象。通过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）表示，如下所示：
　　2.分析与设计惯性权重ω
　　影响算法搜索结果和收敛速度的关键参数就是ω，经过先前的大量实验研究，ω过大有利于全局寻优，ω过小有利于局部寻优。根据ω取值对搜索结果的影响，可以采用经典的线性递减方式设定ω的值如公式（5）所示。
　　3.确定算法的适应度函数
　　根据1.3提出的算法目标，通过对目标优化要求的不同设定相应的权值，实现多目标优化。本算法的目标是在迭代次数范围内找到使适应度函数值最小的资源分配方案，即最终的虚拟机放置方案。适应度函数可以定义如下公式：
　　4.种群初始化引入按资源需求和实时负载分配的思想
　　根据虚拟机对资源的需求情况选择能够满足其要求的物理机，即所选的物理机一定要满足虚拟机对资源的需求，同时根据1.2的定义4物理机部署虚拟机后不至于过载。
　　5.引入分组思想
　　首先将种群随机分成若干份等量的小粒子群，然后在每一个子群里随机设置参数，进行粒子群优化算法寻优，最后再对全部最优解取最小值为最终最分配方案。
　　2.2.2 算法步骤
　　Stepl：按照初始种群方案生成有M个粒子的种群，每个粒子编号为l到M，将M个粒子随机分成N个独立的子群空间，每个子群的粒子个数为m=M/N：
　　Step3：根据适应度函数公式（6）依次计算每个子群中每个粒子的适应值F；
　　Step4：对于每个粒子，比较个体当前适应值和历史最优位置pibest，如果当前适应值较好，则将此粒子当前的位置作为当前最优的位置并更新pibest，否则保持pibest不变；
　　Step5：对于每个粒子，比较当前最优位置pibest和子群体中整体的最优位置Pqgbest，如果当前最优位置较好，则将其作为当前群体最优位置并更新Pqgbest，否则Pqgbest不变（q=l，2…N）；
　　Step6：根据公式（1）和公式（2）更新每个粒子的速度和位置信息；
　　3 仿真实验
　　3.1 实验环境和参数设置
　　为了验证基于分组的粒子群优化算法GPSO在云环境下虚拟机资源分配问题上的可行性，本文扩展了CloudSim平台进行仿真实验，并与轮询算法Round Robin和标准的PSO算法进行了比较。
　　3.2 结果与分析
　　3.2.1 负载不均衡度E的比较
　　系统的负载不均衡度随着虚拟机数量的增加而减小。图2表示三种算法分别在不同虚拟机规模时系统的负载不均衡度。由图2可知GPSO算法的负载不均衡度E小于其他两个算法，说明GPSO算法在负载平衡方面的性能优于其他两个算法。这是因为PSO算法初始种群是随机生成的，而GPSO算法的初始种群是根据系统的实时负载随机生成，并将负载不均衡度作为目标函数进行搜索。轮询算法没有考虑物理机实时负载，也没有优化目标策略。
　　3.2.2 资源利用率比较
　　GPSO算法比其它两种算法的资源利用率更高，这是因为目标函数包含了对系统资源利用率的优化策略，从而一定程度上避免了系统资源的浪费。
　　4 结论
　　本文针对现有虚拟机资源放置算法只考虑云资源的能耗和使用率，忽略负载均衡对系统性能影响的问题，提出了基于分组的改进粒子群算法（Grouped Particle Swarm Optimization：GPSO），通过最小化云数据中心的负载不均衡度达到系统的负载平衡。与标准粒子群算法中随机生成初始种群的方式不同，本文根据系统的实时负载来随机生成初始种群，在算法中引入分组的思想，将该种群进行随机分组，通过比较各组的全局最优解得到最终分配方案。通过CloudSim平台仿真实验表明，改进算法生成的资源分配方案较原算法能有更好的负载均衡、更高的资源利用率，证实了该算法的有效性。