面向移动云计算的自适应虚拟机调度算法

韦传讲，庄 毅

(南京航空航天大学 计算机科学与技术学院， 南京 211106)

1 引 言

随着无线网络的快速发展，促使了诸如手机、笔记本和平板电脑之类的智能设备的发明，这样的联网技术和设备使得用户可以移动，并可以随时随地访问资源.因此，移动性已成为现代互联网世界的主要特征.根据中国互联网信息中心发布的报告，截止2018年底，我国网民数量大约为8.29亿，其中大概有98.6%的网民是通过手机访问互联网(1)http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201902/t20190228_70645.htm..随着互联网技术的不断发展，应用服务的种类变得多样化，使得人们对移动设备的计算性能的需求也越来越高[1].

移动设备功能和性能需求的上升需要不断突破本身的资源瓶颈，才能满足人们的需求.然而，硬件的提升需要新材料新技术的突破.目前移动设备存在的难以解决的问题，包括移动设备的存储有限，电池续航能力有限，设备的处理能力有限等，都需要新材料技术的突破，才能够使移动设备的性能达到质的飞跃，而这些突破无法在短期实现[2].而云计算技术的出现，使得移动设备固有的缺点得以弥补.云平台上有近乎无限的计算资源和存储资源，能够满足移动终端的各种高性能计算，并提供给移动终端最优的云服务.

移动云计算技术结合了移动互联网技术与传统云计算技术，改善了移动设备固有的缺点.云平台上的计算资源和存储资源被认为几乎是无限的，可以满足移动设备的多种计算需求，使得移动设备获得更好的云服务[3].移动云计算能够支持多种移动设备执行丰富的移动应用，可以为用户带来丰富的产品体验.同时，移动云计算也为移动网络运营商和云服务提供商带来了商业机会[4].移动云计算相较于传统云计算而言，它是一种先进的移动计算技术，其利用各种云和网络技术的统一弹性资源获得不受限的功能、存储和移动性，它弱化了移动终端硬件设备的限制，通过以太网或互联网渠道随时随地地为大量的移动终端提供各种定制的云服务，而不用管其基于的终端平台[5].此外，移动云计算还继承了传统云计算的一些优势，如可伸缩性、支持多用户以及安全服务[6].

移动云计算的日益普及和云中心数量与规模的不断扩大，使得能源消耗成为云中心的最大的运营成本.关于能耗的数字统计随处可见，根据《中国数据中心白皮书(2018年)》2显示，截止2017年底全球数据中心共计44.4万个，大约安装了493.3万架机架，部署至少5500万台服务器，预计2020年会部署安装更多的机架和服务器，这些服务器消耗着越来越多的能源.因此世界上很多国家或组织已经在关注云数据中心高能耗的问题，并付诸行动.移动云计算在满足云用户不断增长应用需求的同时，需要对工作负载和资源配置进行快速智能化和动态管理，从而实现能耗最小和效益最大化的运行模式.因此，很有必要研究相关算法以支持对移动云中心的资源管理，降低开销，提高效率和可靠性.

本文针对移动云中心高能耗问题，从移动云中心资源调度的角度展开研究，设计目标函数，并建立虚拟机(Virtual Machine，VM)调度模型，最后提出VM调度算法以对模型进行求解.本文的主要研究工作及贡献如下：

1)从CPU、内存、网络带宽和磁盘4个维度，将最小化数据中心能耗、最大化数据中心效用以及最小化服务器数量作为目标，建立了基于多目标优化的VM调度模型VMSM-EUN.该模型具有能耗低、效用高和调度结果优等特点.

2)根据粒子群进化的不同阶段，分别设计了适用于加速因子与惯性因子的动态自适应调整策略，可加速粒子群的求解过程并获得更优解.

3)为验证VM调度模型VMSM-EUN的有效性，设计了基于改进粒子群的自适应参数调整的VM调度算法VMSA-IPSO来求解该模型.并通过仿真实验验证了本文算法与模型的有效性，并通过对比实验验证了算法的优越性.

2 相关研究

在移动云计算的众多研究中，通过对虚拟资源的合理调度来降低数据中心的能耗一直是一个研究热点.国内外研究学者从多个方向提出了提高云数据中心的资源利用率和能源效率的方案，包括新颖的资源调度方案、数据中心服务器散热和控温方案、服务器调压变频方案以及高效负载均衡器等.其中资源调度方案对数据中心的能耗影响尤为突出，但设计更快速、更节能的资源调度算法被认为是一个挑战.

目前，许多解决方案采用的分配方法是通过在任意给定时间将单个VM分配给主机的方式，来解决VM分配问题.这种方法独立地规定了VM的资源需求，以确保每个主机具有足够的容量来执行工作负载.但是，这种方法会降低资源利用效率.此外，许多已有的VM部署方案还采用了一种根据当前的CPU资源需求优化资源使用的部署策略.但应用程序的工作负载总是会随着时间的推移而波动，这对VM的动态调度是一个重大的挑战.最近的一些研究表明，通过分析、预测CPU资源和云网络流量也能为云中心有效管理资源提供帮助，确保资源高效合理的分配.为了解决VM调度问题，已有许多专家学者展开了研究，主要包括以降低能耗为目标和以收益最大化为目标.

以降低能耗为目标，对移动云数据中心的资源进行管理和调度，提高云中心资源的利用率和能源效率.Li xiang等人将数据中心的能耗分为计算能耗和冷却能耗，他们精心设计了热能耗模型来分析数据中心的气流和服务器CPU的温度分布，提出了一种能够最大限度地降低云数据中心总能耗的整体VM调度算法[7].文献[8]提出了一种通过对服务器的状态进行管理来减少能耗的方法.将空闲服务器节电状态与输入作业负载进行映射，考虑了资源动态变化情况、工作服务器不同负载时的功耗和空闲服务器休眠状态及转换时的功耗等情况，设计了启发式调度器来对VM进行调度，以使得VM映射中功耗增量最小.文献[9]提出一种能量感知VM调度方法，该方法考虑了数据中心的物理主机的异构带宽，由功率感知算法和带宽供应算法组成.Yibin Li等人在DVS技术的基础上，提出了一种新的能量感知移动云动态资源调度算法[10]，在满足严格的时间约束和应用的概率约束的前提下，可减少移动设备的总能耗.文献[11]提出了一个混合云框架H(2)http://www.caict.ac.cn/kxyj/qwfb/bps/201810/t20181016_186900.htm.和集成资源管理器，该框架和管理器能够管理具有多种沙箱化和虚拟化技术的云基础设施，可有效地平衡工作负载的能源、性能和成本效益.Jang等人提出了一种新的虚拟CPU调度方案，以提高云应用的I/O性能并减少能耗.该方案设计了一个评估函数，该评估函数通过观察每个虚拟CPU 的的资源消耗量来评估VM的任务特性.基于评价函数，该调度方案自适应地控制VM在处理I/O请求时的优先级，以实现公平分配.实验结果表明，该方案提高了VM的响应速度和I/O带宽，并降低能耗[12].Ting Yang等人提出了一种新颖的工作感知VM布局[13]，以减少数据中心的能耗，并尽可能多地满足网络QoS要求.并通过实验验证了其方案可在节省能源消耗的同时减小通信延迟.文献[14]提出了一种VM整合的自适应节能调度算法，该算法的主要思想是最大限度的利用服务器，将数据中心的VM部署在尽可能少的服务器上，以最小化能耗.该算法通过自组织和概率论方法来阻止过载服务器接受VM请求，以确保良好的QoS，并使用在线迁移来确保迁移过程的顺利进行.实验结果表明，该算法能降低数据中心能耗实现节能目标[14].

以收益最大化为目标，主要有基于机器学习算法、基于拍卖机制和博弈论的方法.文献[15]提出了一种考虑云用户和云服务提供商的双激励VM调度模型，该模型通过最大化VM请求的成功率和最小化组合成本实现对云用户的激励，并通过最小化利润的公平性偏差实现对云服务提供商的激励.上述的策略能使获得更高的用户满意度，但是容易造成资源的浪费.Sharrukh Zaman等人针对现有云资源分配策略无法保证有效的分配和云提供商收入最大化的问题，设计了一种基于拍卖的动态VM分配机制，该机制在进行VM配置决策时考虑了用户对VM的需求.实验表明所提出的机制可以提高资源利用率和分配效率，并为云提供商带来更高收益[16].Liu Xing等人提出了一种基于Stackellberg博弈模型的VM定价和分配方案，该方案考虑服务阻塞对用户效用的影响，通过模型分析推导出最优定价的闭式表达式，并通过粒子群算法对VM静态和动态调度进行最优定价搜索.实验结果证明了该方案可以通过定价策略控制网络阻塞，有效提高移动用户和云提供商的实用性[17].文献[18]对移动云环境下应用任务需求进行分析，设计了基于Stackelberg博弈的动态计算资源调度算法和博弈模型，仿真实验表明该算法和模型能保证移动终端的体验质量并最大化终端效用[18].

综上所述，目前已有的云中心的VM调度方法虽然在一定程度上减少了云中心的能耗，但是仍然存在不足，一方面，当VM调度的数量很大时，现有的算法不能满足调度的性能需求.另一方面，上述的VM调度算法在设计时考虑问题不够全面，如仅考虑CPU能耗而不考虑其他部件的能耗问题.因此，本文在充分考虑了CPU、内存、网络带宽和磁盘4个维度，提出了面向能耗和效用的VM调度模型VMSM-EUN，并设计了VM调度算法VMSA-IPSO来求解该模型.

3 虚拟机调度模型

本节考虑服务器上的各种硬件资源，将VM调度模型看作“Packing Problem”.在VM调度问题中，需要把服务器看作背包，VM看作物品，在将物品放入背包时需要考虑物品的大小和背包的大小.“Packing Problem”需要一个多目标优化算法来进行求解.本文考虑VM调度的3个目标，设计了相应的函数，从而将背包问题转换为带约束的多目标优化问题.因此，我们需要设计目标函数，明确约束条件，建立VM调度模型.

3.1 相关定义

定义1.云中心描述.移动云中心所有的服务器用向量P={P1，…，Pi，…，Pn}表示；移动云中心所有的VM用向量V={V1，…，Vj，…，Vm}表示，其中n为移动云中心服务器数量，m为移动云中心VM数量.Pi={Pcpui，Prami，Phddi，Pneti，Pcosti}分别表示服务器Pi的CPU计算能力Pcpui、内存空间Prami、硬盘空间Phddi、网络带宽Pneti以及成本Pcosti；Vj={Vcpuj，Vramj，Vhddj，Vnetj，Rj}分别表示VM所需的CPU资源Vcpuj、内存空间Vramj、硬盘空间Vhddj、网络带宽Vnetj；VM效用Rj={Rj1，…，Rji，…，Rjn}，Rji表示VMVj分配到服务器Pi产生的效用值.

定义2.服务器的多维度负载度计算.采用加权和法，将服务器中各部件的能耗占比定义为能耗权重，再通过计算加权和得到服务器的多维度负载度.定义服务器Pi的多维度负载度FMDLi为式(1)：

FMDLi=ω1×Ucpui+ω2×Urami+ω3×Uhddi+ω4×Uneti

(1)

(2)

其中：Ucpui，Urami，Uhddi，Uneti分别代表服务器Pi的CPU、内存、硬盘和网络带宽利用率.ω1，ω2，ω3，ω4分别为CPU 能耗占比，内存部件能耗占比，硬盘部件能耗占比，网络部件能耗占比.Pji∈{0，1}，Pji=1表示VMVj被部署到服务器Pi上运行，Pji=0表示VMVj未被部署到服务器Pi上运行.

定义3.虚拟机效用函数.VM的效用函数是一个线性函数，如式(3)所示.

(3)

式(3)中的αi、βi、γi和φi分别表示VM每个单位CPU、内存、网络带宽资源和硬盘资源的价格.Cj、Mj、Bj和Hj表示VMVj的CPU、内存、网络带宽和硬盘的资源配置大小.

定义4.服务器效用函数.一台服务器的效用值为该服务器上所有VM产生的效用与该服务器的成本的差值，因此服务器的效用函数如式(4)所示.

(4)

云中心的效用为所有物理机的效用值之和，因此云中心的效用函数如式(5)所示.

(5)

3.2 约束条件

为找到VM和服务器之间的最佳映射方案，实现云中心的效益最大化和低能耗的目标，在进行VM调度时需要明确约束条件.下面给出VM调度模型需满足的约束条件：

s.t

(6)

式(6)中第一个式子表示对于移动云数据中心中的任意一台VM，在任意时刻它只能运行在某一台服务器上运行；式(6)中其余的不等式表示一台服务器所承载VM占用的资源总和小于等于其所拥有的资源.

3.3 目标函数

为实现移动云数据中心效益最大化和降低运行成本的目标，本小节根据上述定义与调度约束条件，设计了3个VM调度的目标函数，具体如下.

3.3.1 最小能耗

文献[19]提出了一个新的服务器的能耗模型，并证明了服务器的能量消耗与CPU利用率呈线性关系.本文在该文献提出的服务器能耗模型的基础上进行优化，不是仅仅考虑CPU利用率而是将服务器的能耗与服务器的负载相联系，考虑了CPU、内存、网络带宽和磁盘4个维度，提出了改进的服务器能耗模型.首先将服务器Pi的多维度负载度FMDLi进行归一化处理，得到服务器的多维度负载率UMDLi，归一化处理方法如式(7)所示.其中FminMDLi，FmaxMDLi表示优化周期[t1，t2]内服务器Pi的多维负载度的最小值和最大值.

(7)

改进的云服务器能耗模型，如式(8)-式(10)所示.

P(UMDLi(t))=c×Pmaxi+(1-c)×Pmaxi×UMDLi(t)

(8)

(9)

(10)

其中，式(8)将服务器的能耗与服务器的负载相联系，考虑了CPU、内存、网络带宽和磁盘4个维度，而不是仅仅考虑CPU利用率.Pmaxi表示服务器Pi的多维负载率达到最高峰值时的最大功耗；UMDLi(t) 表示服务器Pi在t时刻的多维负载率.式(9)中Ei表示优化周期[t1，t2]内服务器Pi的能耗.式(10)中，E表示移动云中心所有服务器的能耗，单位为瓦特(W)，n表示移动云数据中心的服务器数量；Yi∈{0，1}表示服务器Pi是否处于激活状态.Yi=1，表示服务器Pi处于激活状态.Yi=0，表示服务器Pi处于关闭状态.

3.3.2 最大效用

移动云计算中心的效用为全部VM效用和所有服务器成本的差，计算方法如式(11)所示.

(11)

式(11)中R表示移动云中心的总效用值；n表示移动云中心服务器总数；m表示云中心承载的VM总数；Rji表示在服务器Pi上运行VMVj产生的VM效用；Pcosti表示服务器Pi的使用成本.

3.3.3 最小服务器数

通常在虚拟资源调度的优化阶段，为了进一步降低能耗，需要将资源利用率较低的服务器上的VM迁移到其它服务器上，并将该服务器设为休眠状态，使得云中心可以运行较少的服务器来承载相同的负载，以进一步减少数据中心的能量消耗.服务器数计算方法如式(12)所示.

(12)

综上所述，VM调度模型VMSM-EUN可以描述为：

(13)

(14)

(15)

s.t

(16)

4 基于改进粒子群的虚拟机调度算法

4.1 改进的粒子群优化算法

粒子群优化(Particle Swarm Optimization，PSO)算法是模拟鸟群寻找食物的集体行为而提出的一种基于群体智能的全局优化技术.PSO中成员粒子以一定的速度和加速度向更好的位置移动，每个粒子表示问题空间的解[8].

在PSO中，每一个粒子被认为是潜在的解决方案，每个粒子都与两个向量相关联，它们分别是速度向量v(t)=[v1，v2，…，vD] 和位置向量x(t)=[x1，x2，…，xD]，其中D为解空间的维度.在进化过程中改进的PSO算法的更新方程如式(17)、式(18)[20]所示，在PSO中所有粒子是根据当前局部最优解pbest和当前全局最优解gbest来更新自己的信息.

v(t+1)=ωv(t)+c1r1(pbest-x(t))+c2r2(gbest-x(t))

(17)

x(t+1)=x(t)+v(t+1)

(18)

其中，v为粒子速度，ω为惯性因子，c1、c2为加速因子，r1、r2为(0，1)上一致分布的随机数.每一维上的粒子速度被限制在vmax(vmax>0) 内，如果某一维更新后的速度大于用户给定的vmax，那么就设为vmax，即v(t+1)>vmax时，v(t+1)=vmax.如果某一维更新后的速度小于等于用户给定的-vmax，那么就设为-vmax，即v(t+1)≤-vmax时，v(t+1)=-vmax.目前已有的研究对PSO进行了改进，典型工作有主要3个方面：YH Shi等人将惯性因子引入PSO，并证明了当惯性因子值较大时，全局寻优能力强，局部寻优能力弱；值较小反之[21].除惯性因子外，加速因子c1和c2也是PSO中的重要参数.权重因子包括惯性因子ω和加速因子c1、c2，使粒子保持着原有的运动状态，并具有探索和开发的能力.在Kennedy的两个极端情况下，实验表明“仅社交”模型和“仅认知”模型中，两种加速因子对于PSO的成功至关重要[22].Kennedy和Eberhart建议c1、c2固定值为2.0，这种配置已被许多研究人员采用[23].Suganthan证明了对于不同的问题，使用c1、c2的“ad hoc”值而不是固定值可以产生更好的性能[24].Ratnaweera等人提出了一种具有线性时变加速度系数(HPSO-TVAC)的PSO算法，在开始时设置较大的c1和较小的c2，并且在搜索期间逐渐反转.在对比实验中，HPSO-TVAC显示出最佳的整体性能.这是由于时变c1和c2可以平衡全局搜索能力和局部搜索能力[25].由上所述可见，在粒子群寻优的过程中采用适合的惯性因子ω、加速因子c1和c2，将有助于提高PSO性能.因此我们在4.3小节中，将在粒子群求解过程中确定每一次迭代后粒子群所处的状态，动态自适应的改变惯性因子ω和加速因子c1、c2的取值.

4.2 映射关系与编码方式

为了将PSO算法用于求解VM调度问题，我们需要将粒子的编码与现实问题对应，本文中粒子的位置、速度与现实中VM调度问题的映射关系如下所述.

图1 编码方式Fig.1 Encoding scheme

4.3 自适应参数调整

考虑PSO的特性，我们将粒子群求解过程中状态变化与加速因子c1和c2的取值联系在一起，自适应的调整c1和c2.并且将粒子群的进化因子f与惯性因子ω建立映射关系，使得ω的取值跟随进化状态的变化而变化.具体的自适应参数调整方法如下所述.

4.3.1 加速因子c1和c2的调整

参考文献[26]： 设f为进化因子.将粒子群的状态分类为：探索、开发、收敛和跳出4种状态.在粒子群求解过程中通过计算进化因子f的数值大小来确定每一次迭代后粒子群所处的状态，最后得出进化因子f与粒子群所处的状态的模糊隶属函数.模糊隶属函数有交叉的区域，即存在一个f对应两个函数值.我们称这个区域为过渡期.在过渡期，粒子群可能处于两种状态中的任意一种.对于最终分类，可以使用“单例法”或“质心法”[27]两种常用的去模糊技术中的任一种.本文使用单例法，因为它比质心法更有效，并且与去模糊规则表一起实现起来比较简单.与大多数模糊逻辑方案类似，我们设计的去模糊规则表也涉及状态和“状态变化”变量.探索、开发、收敛和跳出4种状态分别用S1、S2、S3和S4表示.根据参考文献[26]，PSO序列S1⟹S2⟹S3⟹S4⟹S1⟹…反映了PSO过程中状态的变化.模糊隶属函数图像的交叉区域分别为：S1与S2交叉区域、S2与S3交叉区域、S1与S4交叉区域.为了分类的稳定性即不过度的切换状态指示符，设计了如表1所示的去模糊化规则表.表1中，F(f)表示模糊隶属度，St-1表示前一个状态，St表示当前状态的选取结果.

在粒子群优化的状态模糊分类后，我们将根据每一次迭代后粒子群所处的状态，动态的改变加速因子c1和c2的取值.综上所述，我们得到以下调整系数c1和c2的策略：

1)在探索状态下增大c1和减小c2：在探索状态下探索尽可能多的最佳值非常重要，增大c1和减小c2可以帮助粒子单独探索并达到它们自己的历史最佳位置，而不是围绕当前可能与局部最优相关的最佳粒子.

表1 去模糊规则表Table 1 Fuzzy control rules

2)在开发状态下略微增大c1并略微减小c2：在这种状态下，粒子利用局部信息并聚集到每个粒子的历史最佳位置所指示的可能的局部最佳位置.因此，缓慢增加c1并保持相对较大的值可以增强围绕局部最好pbest的搜索和利用.与此同时，全局最佳粒子并不总是在此阶段定位全局最优区域.因此，缓慢减少c2并保持较小值可以避免陷入局部最优.此外，在探索状态之后和收敛状态之前更可能发生开发状态.因此，改变c1和c2的时间应该是从探索状态略微改变到收敛状态.

3)在收敛状态下略微增大c1并略微增大c2：在收敛状态下，群体似乎找到全局最优区域，因此，应增强c2的影响以将其他粒子引导到可能的全局最优区域.因此，应增大c2的值.另一方面，应减小c1的值以使群快速收敛，但是这种策略会过早地将这两个参数饱和到它们的下限和上限.结果是群体将被当前最佳区域强烈吸引，导致过早收敛，如果当前最佳区域是局部最优，则是有害的.为避免这种情况，c1和c2都略有增加.略微增大两个加速因子最终将具有与减小c1和增大c2相同的预期效果，因为它们的值将被限制到大约2.0，因为c1和c2之和的上限为4.0[23].当c1和c2的和大于4.0时，需要对c1和c2进行归一化，归一化处理方法如式(19)所示.

(19)

4)在跳出状态下减小c1和增大c2：当全局最佳粒子跳出局部最佳位置并朝向更好的最佳状态时，它可能远离拥挤群集.一旦这个新区域被一个粒子找到，这颗粒子就会成为(可能是新的)领导者，其他粒子应该跟随它并尽可能快地趋近这个新区域.较大的c2和相对较小的c1有助于实现这一目的.

4.3.2 惯性因子ω的调整

PSO中的惯性因子ω用于平衡全局和本地搜索功能.许多研究人员主张ω的值在探索状态下应该很大而在开发状态下应该很小.然而，纯粹随着时间减少ω并不一定正确.进化因子f与惯性权重ω具有一些特征，其中f在探索状态期间也相对较大并且在收敛状态下变得相对较小.因此，ω的取值应跟随进化状态的变化而变化，即令ω与f存在这样的映射ω(f)：R+→R+.

(20)

在本文中，ω初始化为0.9.由于ω不一定随时间单调变化，而是随f单调变化，因此ω将适应以f为特征的搜索环境.在跳出或探索状态下，较大f和ω将有利于全局搜索.相反，当f很小时，检测到开发或收敛状态，ω减小以有利于局部搜索.设计的自适应参数调整流程图如图2所示.

图2 自适应参数调整流程图Fig.2 Self-adaptive parameter adjustment flow chart

4.4 虚拟机调度算法

基于改进粒子群，我们设计了VM调度算法VMSA-IPSO，算法具体步骤如下：

Step1.定期收集连续到达的VM请求作为算法的输入；

Step2.初始化.

Step2-1.根据VMSM-EUN模型中决策变量的个数，设置种群大小为N，最大迭代次数为Gen.

Step2-2.生成初始粒子群.根据VM请求以及服务器的各种资源约束，随机生成N个可行VM部署方案，每一个解都是一个粒子，每个粒子都是由二维编码方案编码的，这些粒子构成了初始种群.粒子的初始位置由初始种群决定，粒子的初始速度由粒子的第一维状态信息决定.

Step3.计算每个粒子到其他粒子的平均距离和进化因子f根据进化因子f的大小对粒子群的状态进行评估，自适应的调整参数c1、c2和ω.

Step4.粒子群中为一个粒子，根据式(10)、式(11)和式(12)计算其目标函数的值.

Step5.对于每个粒子更新其当前最好位置pbest.

Step6.比较所有粒子的当前最好位置pbest，选出适应值最高的与当前全局最好位置gbest作比较，得出种群的全局最佳位置gbest.

Step7.根据式(17)更新种群中所有粒子的速度.

Step8.更新种群中所有粒子的位置.

Step8-1.根据式(18)更新粒子位置，此位置更新操作可能会丢失VM，将在后续步骤中重新部署丢失的VM.

Step8-2.删除VM.上述位置更新操作可能导致VM部署在两台服务器上.因此，必须删除重复的VM以确保部署方案的可行性.删除方法是将二维编码的本地位置设置为0，并将这些重复的VM一起删除.同样，这些被删除的VM将在下一步重新部署.

Step8-3.重新部署被删除的VM.要获得更新后的可行解决方案，就必须将丢失或意外删除的VM重新部署到服务器上.首先将当前处于激活状态的服务器作为主机服务器，当所有处于激活状态的服务器都无法放置VM时才会启用新服务器.

Step9.根据更新后的粒子群，更新局部最优粒子和全局最优粒子的位置信息.

Step10.判断是否达到最大迭代次数，若达到则输出VM调度方案，否则重复步骤Step 3～Step 9.

图3 基于改进粒子群的虚拟机调度算法伪代码Fig.3 Pseudo code of the VM scheduling algorithm

基于改进粒子群的VM调度算法VMSA-IPSO的伪代码，如图3所示.

5 实验与结果分析

本文基于多目标优化算法建立了VM调度模型VMSM-EUN，将最小化数据中心能耗、最大化数据中心效用以及最小化服务器数作为目标，设计并实现了基于改进粒子群的VM调度算法VMSA-IPSO来求解该模型.

5.1 实验参数设置

为了验证VMSM-EUN模型和VMSA-IPSO算法的有效性，本文使用云计算仿真工具CloudSim进行仿真实验.为验证本文提出的VM资源调度算法的性能，在相同环境和条件下将本文提出的VM调度算法VMSA-IPSO与文献[29]提出的MBFD( Modified Best Fit Decreasing algorithm)算法以及“Packing Problem”问题近似算法FF(First-Fit algorithm)、 BF(Best-Fit algorithm)进行比较.从活动服务器数量、服务器效用和能耗3个方面进行了对比分析.实验模拟包含400个异构服务器的异构虚拟化数据中心，为了反映虚拟化数据中心的异构性，我们根据参考文献[30]，选取了两种类型的服务器，它们具有不同的配置和能耗特征，服务器的参数特征如表2所示.所选服务器在不同负载级别的功耗(瓦特)如表3[31]所示.对比仿真实验的参数设置如表4所示.根据文献[32]，在基于Xeon处理器的服务器中，CPU是能耗最大的部件，其能耗占比高达74%，内存能耗占比为19%，硬盘能耗占比为5%，网络部件能耗占比2%.在表4中ω1，ω2，ω3，ω4分别为CPU 能耗权重，内存能耗权重，硬盘能耗权重，网络带宽能耗权重.表5给出了本次实验的VM实例.

表2 服务器参数特征Table 2 Server configuration

表3 服务器在不同负载级别的功耗(瓦特)Table 3 Power consumption of servers at various load levels(W)

表4 实验参数配置Table 4 Experimental parameter configuration

表5 虚拟机实例Table 5 Virtual machine instances

5.2 活动服务器数量比较

在本文中，活动服务器的数量是处于活动状态的服务器总数，这些服务器运行承载云服务的VM.在此实验中，VM请求的数量为100到1000，我们将激活HP ProLiant G4服务器或HP ProLiant G5服务器来响应其请求.图4给出了与其他方法的对比实验结果.

由图4可见，随着VM请求数量的增加，本文提出的算法总是能激活最小数量的服务器，而FF算法始终激活最大数量的服务器.MBFD算法激活的服务器总数小于BF算法和FF算法，但激活的服务器总数多于本文提出的算法VMSA-IPSO.因此，VMSA-IPSO算法能够使移动云数据中心开启更少的服务器，提高了资源的利用率.

图4 激活服务器总数Fig.4 Total number of active servers

5.3 数据中心效用比较

在本文中，数据中心的全局效用定义为所有VM的效用与所有服务器运营成本的差值.根据式(4)、式(5)可得：

(21)

式(21)中，Rtotal、Rvm和Pcost分别为数据中心的全局效用、所有VM的效用和所有服务器的成本.Yi∈{0，1}表示服务器Pi是否处于激活状态.Yi=1，表示服务器Pi处于激活状态.Yi=0，表示服务器Pi处于关闭状态.根据式(21)，我们可以计算在不同VM请求下，各个VM调度算法产生的全局效用值，计算结果如图5所示.

图5 数据中心效用值比较Fig.5 Data center utility values comparison

如图5所示，与其他算法相比，我们的算法获得了更高的效用值.随着VM请求数量的增长，云中心在这4种算法下的效用值各不相同，但是本文提出方法的效用值总是高于FF、BF和MBFD.对于同一组VM请求，如果虚拟化数据中心中服务器的利用率较高，可激活较少的服务器来承载云服务工作负载，此时虚拟化数据中心的能源消耗将减少，数据中心的效用会大幅度增加.

5.4 能耗比较

在本文中，能耗是指所有处于激活状态的服务器的总能耗，计算方法如式(8)-式(10)所示.在满足不同数量的VM请求下，对比的各个算法的总能耗如图6所示.

图6 总能耗对比图Fig.6 Total energy consumption comparison chart

通过图6我们可以得出，无论VM请求的规模如何，本文提出的方法均可使数据中心运营商能够节省更多能量.与其他3种方法相比，我们的方法可以节省较多能源费用.这是因为FF，BF和MBFD在解决问题的过程中，缺乏虚拟化数据中心中异构服务器的能耗特征等反映全局状态的信息.那些算法只考虑了多维资源约束，且未考虑不同服务器的能量差异.

5.5 VMSA-IPSO算法性能分析

为比较VMSA-IPSO算法的收敛时间，本文将未引入参数自适应调整策略的调度算法与VMSA-IPSO算法进行比较.在对比实验中，粒子群大小为30，迭代次数为100.图7中，VM请求数量为300.图8中，VM请求数量为800.从图7和图8可以看出，VMSA-IPSO开始进化并快速收敛，然后趋向平稳，能达到很好的收敛效果，收敛时间大约为50～60次迭代的时间.而未引入参数自适应调整策略的算法的收敛时间大约为75-85次迭代的时间.

图7 收敛时间对比1(虚拟机请求数量：300)Fig.7 Convergence time comparison 1 (Number of virtual machine requests：300)

综上所述，本文方法引入关键参数自适应调整策略，增强了VMSA-IPSO调度算法的收敛性，加快了算法的求解速度，使其能够更快找到更好的VM调度方案，提高调度方案的质量.

6 结 论

本文以最小化能耗、最大化效用以及最小化服务器数为目标，建立了VM调度模型VMSM-EUN，设计了基于改进粒子群的VM调度算法VMSA-IPSO来求解该模型.本文在综合考虑了云中心效用和能耗的前提下，提出的调度算法能更好的解决移动云计算环境下的VM调度问题.通过与现有算法的对比实验，验证了本文提出的基于改进粒子群的VM调度算法具有使云中心能耗更低，效用更大的优点，能进行更优的VM调度.