王以伍 陈跃辉

(成都医学院网络中心 四川 成都 610083)

0 引 言

随着云数据中心服务器数量与规模的迅猛增加，能耗已经成为数据中心面临的主要问题[1]。目前，数据中心的能耗已经占据全世界电力供应的1.3%，至2020年将增长至8%[2]。数据中心的碳排放为全球总量的0.6%，等同于新西兰一个国家的碳排放量，至2020年将增长至2.6%，超过德国的碳排放量。基于虚拟化的服务器合并技术是目前降低数据中心能耗的最重要手段，该技术使得同一服务器上可以运行多重应用，每种应用执行于各自的虚拟机上，并将虚拟机映射至服务器。此时，如何在满足服务质量QoS的同时设计出高能效的虚拟机部署算法对数据中心的能效将具有重要影响。

为了解决以上问题，本文在数据中心环境下提出了一种能量与QoS保障的虚拟机部署算法，算法的优势在于：1) 与传统的服务器资源同质不同，算法考虑了异构条件下的服务器资源，将从全局考虑QoS保障，将虚拟机部署问题形式化能耗与全局QoS保障间均衡的优化问题；2) 通过参数与进化操作的重定义，提出了一种改进的粒子群算法对虚拟机部署进行求解，并以局部适应度优先策略更新粒子位置，使算法可以更快收敛。

1 相关研究

已有研究中，MBFD算法[3]是云数据中心中具有代表性的虚拟机部署能量优化算法。该算法首先按当前CPU占用对所有虚拟机进行降低排列，然后将虚拟机分配至带来功耗增加幅度最小的服务器上，实现能耗优化。此外，智能群体算法也广泛应用于虚拟机部署问题的求解，如遗传算法GA[4]、模拟退火算法SA[5]、粒子群算法PSO[6]等。然而，以上已有工作均是同质的数据中心环境，其方法不适用于异构数据中心环境。此外，以最小化能耗为目标的单目标优化虚拟机部署也可以利用群体智能算法ACO[7]、PSO[8]、SA[1]和GA[9]等进行求解。但是，尽管此时算法得到的能耗有所降低，但在应用方面并未提供QoS保障，这使得应用负载的执行成功率不高。

考虑QoS保障的虚拟机部署问题的相关研究中，文献[10]提出了基于GA的多目标虚拟机部署算法，算法可以实现活动主机数量和通信QoS开销的最小，均衡数据中心中多维度资源的同步利用。文献[11]提出基于GA的虚拟机部署算法，可以最小化活动数量和最大化资源利用率。文献[12]则利用PSO实现了虚拟机部署问题中能耗最小和资源浪费最小。文献[13]利用一种文化基因算法实现虚拟机部署问题的多目标优化，包括最小化能耗、网络流量及最大化经济收益。问题在于，以上算法均只考虑了单个维度上的QoS保障，如通信开销、资源利用率、经济收益等，没有设计满足多维度QoS且从全局角度进行QoS保障的虚拟机部署算法。

比较已有研究，本文将设计能量与QoS保障的虚拟机部署算法，算法利用改进的粒子群优化可以在满足全局QoS保障的同时最小化数据中心的能耗。

2 能量与QoS模型

表1给出本文有关参数说明。

表1 符号说明

2.1 能耗模型

数据中心的能耗主要集中于服务器主机上，功耗主要由CPU、内存、磁盘和网络接口组成，且CPU是其功耗的主要组成部分，也可认为，服务器的CPU利用率即为其资源利用率。CPU利用率可根据执行负载的变化建立为时间的函数，故服务器的能耗也可基于CPU利用率进行建立。将服务器总体定义为：

(1)

式中：En为时间段[t1,t2]间服务器的总能耗，u(t)为变化的CPU利用率，P(u(t))为时间t时服务器的功耗，Pmax为服务器满载时的最大功耗，c为服务器为空闲状态时的能耗比例。

2.2 QoS效用函数

数据密集型服务(简称服务)的QoS需求包括多种属性，如：响应时间、可靠性、吞吐量和可用性等。通常，这些属性可划分为两类：积极型QoS属性和消极型QoS属性。积极型QoS属性(如可靠性和可用性)表明其属性值越大，服务器运行相关服务的性能越好。相反，消极型QoS属性(如响应时间和延时)的属性值越低，性能越好。本文通过将积极型QoS属性转换为消极型QoS属性的方式(乘以-1)而仅考虑消极型QoS属性。

考虑拥有r种QoS属性的服务s的QoS需求矢量qs={q1(s),q2(s),…,qr(s)}，其中，qk(s)值(1≤k≤r)代表服务s的第k个属性值。所有l个服务的属性矢量可表示为QS={q1(S),q2(S),…,qr(S)}，S={s1,s2,…,sm}，其中，qk(S)表示所有服务的第k个属性值的累加。表2给出了服务的QoS属性值的累加函数。

表2 QoS属性值的累加函数

每种服务涉及多种QoS属性，会带来不同的量化程度，这不利于满足全局的QoS保障。因此，需要设计一种QoS效用函数，将QoS属性值q(s)矢量映射为单一实数值。考虑n台服务器组成的数据中心，PS={ps1,ps2,…,psn}，可部署的m台虚拟机集合为VM={vm1,vm2…,vmm}。一种服务由部署于一台主机上一台虚拟机完成，同时需要满足其具体资源需求(即CPU和内存)和QoS约束。一种服务仅运行一台虚拟机上，且服务的QoS通常与虚拟机提供相关。因此，QoS效用函数需要将所有属性值在多维度以统一计算的标准化方式将其映射至域[0,1]之间，从而量化全局的QoS保障性能。

定义1QoS效用函数。假设有r个QoS属性，运行于第j台服务器psj(1≤j≤n)的虚拟机的第i个服务si∈S(1≤i≤l)的QoS效用函数可表示为：

(2)

那么，所有服务S的QoS效用函数为：

(3)

同时:

(4)

2.3 能量与QoS保障的虚拟机部署模型

数据中心的虚拟机部署问题的优化目标是在满足全局QoS保障的同时最小化能耗。通过重写式(1)和式(2)，可以将能量与QoS保障的虚拟机部署问题形式化为多目标约束最优化问题，即带有全局QoS效用函数最大化问题(即全局QoS保障)的全局能耗最小化问题，定义为：

(5)

(6)

约束条件包括QoS约束和资源能力约束，即：

(7)

(8)

(9)

(10)

式中：n表示数据中心中服务器的数量，m表示部署虚拟机的数量，Ej表示服务器j的能耗，Ck表示QoS约束值，Ck≥qk(S)。

式(5)-式(6)定义的虚拟机部署最优化问题为NP问题，该问题需要在满足所有约束(式(7)-式(10))的前提下实现最小化能耗和最大化全局QoS效用值，得到最优虚拟机部署方案。本文将提出一种基于改进粒子群算法的部署策略，在能量与全局QoS保障均衡下实现最优虚拟机部署。

3 算法设计

3.1 PSO算法

粒子群算法PSO是一种基于群体智能的随机式搜索算法。作为一种进化计算技术，比较同类方法，PSO执行速度更快，效率更高，已经广泛应用于人工智能神经网络训练、模糊系统控制等诸多领域。PSO通过迭代式提供侯选解的方式不断改进解的质量，使其最终收敛于最优解。

PSO中群体的每个成员即为一个粒子，每个粒子代表搜索问题的一个可行解。每个粒子拥有两个参数：速率和位置。粒子位置与适应度值相关，可用于评估解的质量。PSO开始于随机产生的一个粒子群，并迭代寻找问题最优解。以Xlbest表示粒子找到历史最优解，Xgbest表示整个种群找到的历史最优解，在每一次迭代中，粒子的速度和位置通过下式进行更新：

(11)

(12)

为了求解能量与QoS保障的虚拟机部署问题，PSO需作以下改进：1) 传统PSO仅适用于求解连续优化问题，不适用于求解离散优化问题，这表明PSO的相关参数和进化操作必须重新定义；2) 必须重新设计粒子更新策略和解码策略，以表达虚拟机与服务器间的映射关系。

3.2 改进PSO

本文对传统PSO的改进主要针对两点：1) 重新定义了PSO的参数和进化操作，使其可以求解能量与QoS保障的虚拟机部署优化这类离散最优化问题；2) 采用了一种局适应度优先策略更新粒子位置信息。

3.2.1相关定义

传统PSO仅适用于求解连续最优化问题，无法求解能量与QoS保障的虚拟机部署优化这类离散最优化问题。为此，需要重新定义PSO的相关参数和进化操作。

基于以上五种定义，可将式(11)-式(12)转换为下式：

(13)

(14)

3.2.2局部适应度优先策略

传统的PSO采用随机选择策略，可能影响PSO的全局收敛，降低求解效率。为了增强解的质量，本文设计一种局部适应度优先策略更新粒子位置。

为了便于表述，将粒子的第一个维度上的每个位值称为局部位置。在一个最优时段[t1,t2]间运行于该服务器的所有虚拟机的CPU利用率被称为局部能量适应度，定义为：

(15)

式中：uij(t)表示运行于服务器主机j的虚拟机i的CPU利用率，m表示运行于服务器j上的虚拟机的总数量。

运行于服务器上的所有虚拟机的QoS属性之和称为局部QoS适应度，定义为：

(16)

基于式(15)和式(16)，局部适度度定义为：

(17)

对于局部适应度优先策略，当PSO需要更新一个粒子的确定局部位置时，服务器上拥有最大适应度的虚拟机将具有更高的概率被选择去更新局部位置。局部适应度代表服务器的CPU利用率和QoS属性之和。

3.2.3解码策略

为了改进解的效率，基于服务器与虚拟机间一对多的映射特点，设计了一种二维解码策略，如图1所示，其中，n为服务器数量，m为部署于同一服务器上的虚拟机的数量。

图1 二维解码

由图可知，一个粒子的第一维为n位二进制矢量，矢量中的每一个位即对应于数据中心中的一个服务器。这里，“1”代表在当前虚拟机部署方案中对应服务器是活动的，“0”代表服务器为待机状态。一个粒子的第二维为部署于服务器上的虚拟机组成的集合。那么，每个虚拟机子集即与一个活动的服务器相关联。例如：粒子的第一维的第一个位值为0，则表明数据中心的第一个服务器应被开启。第一、第二个虚拟机应部署于第一个服务器上。比较传统的一维粒子解码方法，二维解码策略不仅可以有效缩短粒子解码长度，降低搜索时间，而且能够反映虚拟机的静态优化部署特征。

4 仿真实验

4.1 实验配置

利用CloudSim[14]对算法进行仿真分析。模拟一个由1 000个异构服务器组成的数据中心环境，服务器具体由两类组成：一类是HP Proliant G4，配置CPU为3 720 MIPS，内存为4 GB，峰值功耗为117 W；另一类是HP Proliant G5，配置CPU为5 320 MIPS，内存为4 GB，峰值功耗为135 W。服务器具有不同的性能配置和能耗特征[3]。每个服务器运行带有四种QoS属性(响应时间、可用性、吞吐量和可靠性)的一个或多个数据密集型服务，服务负载产生现实的2 500个Web服务间。

为了更好地反映实际的虚拟机请求，以Amazon EC2的两类虚拟机实例作为虚拟机请求参数，包括Micro实例，配置500 MIPS CPU和613 MB内存，以及Small实例，配置1 000 MIPS CPU和1 700 MB内存。

选取改进最佳适应递减算法MBFD[3]、最佳适应算法BF[15]、能耗优化的粒子群算法EOPSO[12]作为性能比较的基准算法。前两种算法在装箱思想对虚拟机部署进行建模，区别在于对于服务器的资源占用排序分为递减和递增排列，两种算法在优化服务器使用数量、降低服务器闲置能耗上拥有较好效果。EOPSO算法与本文同为粒子群优化，但其粒子进化操作及解码均与本文有所区别。其他参数配置如下：能量模型中参数c设置为0.6，粒子群的初始种群设置为20，粒子进化的最大迭代次数设置为30，仿真实验运行10次，实验结果取其平均值。

4.2 结果分析

实验1观察数据中心所有活动服务器的总体能耗情况，结果如图2所示。可以看出，本文算法EQPSO比较其他算法节省了更多的能耗，且在虚拟机请求数量增加时，其能耗增加的敏感度也是最弱的。总体上，EQPSO可以节省30%左右的能耗，原因在于BF和MBFD算法需要全局信息，即数据中心中异构服务器的能耗信息，而仅仅考虑了多维度的资源约束，未考虑在虚拟机部署过程中不同服务器的能效的不同。PSOVMP算法虽然也利用粒子群的求解思想，但其求解速度更慢，导致很多非最优解，能耗更大。本文算法引入了有效的粒子速率与位置更新机制，使其更易找到最优部署方案，也更易于实现算法收敛，改进了解的质量。最终，本文算法得到的活动服务器也较少，总体能耗更低。

图2 能耗

实验2观察全局QoS保障性能，结果如图3所示。由于四种QoS属性拥有不同的单位，需要根据QoS效用函数将QoS矢量值映射为单一实数值，即进行标准化后均映射至[0,1]之间，如此，全局QoS保障的取值范围为[0,4]。结果表明，本文算法EQPSO的全局QoS保障平均为2.74，高于其他算法。原因在于其他算法侧重于局部QoS最优化，而局部QoS优化无法满足所有数据密集型服务的全局QoS保障。本文算法通过更低的能耗和更高的全局QoS保障获得了更好的性能。

图3 全局QoS保障

实验3观察服务器空闲的能耗比例变化对算法性能的影响，即式(1)中的c值,结果如图4所示。实验中设置c=0.1，并以步长0.1递增至0.9，同时将QoS约束的数量设置为1，QoS权重设置为0.8。可以看出：1) 当c值递增时，能耗大幅增加，也反映出本文算法能耗越低时，c值也越小，即空闲的服务器数量越多；2) 全局QoS保障并未随c值的变化发生剧烈波动。

图4 服务器空闲的能耗比例对性能的影响

实验4观察QoS约束数量对算法性能的影响，结果如图5所示。QoS约束数量代表数据中心中用户对数据密集型服务的QoS需求。实验中设置QoS约束为1，并以步长1递增至4，c设置为0.6，w设置为0.8，其他属性权重随机产生于[0,0.2]之间。结果表明，本文算法得到的能耗与QoS保障并未随着QoS约束数量的变化发生过大波动，总体较为平衡，说明算法具有较好的鲁棒性，可适应于不同数量的QoS需求。

图5 QoS约束数量对性能的影响

实验5观察QoS权重w对算法性能的影响，结果如图6所示。实验中设置w=0.1，并以步长0.1递增至0.9，同时将QoS约束的数量设置为1，c设置为0.6。结果表明：1) 全局QoS保障在w从0.6递增至0.9时也是递增的，即全局QoS保障性能越好，w值越高；2) 算法能耗并未随着w值的变化发生剧烈波动，稳定性较好；3) 综合比较，在能耗与QoS均较优时，w处于[0.7,0.9]间。

图6 QoS权重对性能的影响

实验6观察算法计算时间，结果如图7所示。实验中将虚拟机请求数量从1 000递增至2 000，c设置为0.6，w设置为0.8。结果表明，当虚拟机请求数量递增时，算法的计算时间增速较慢，计算时间与虚拟机请求数量之间几乎为线性关系，算法具体较好的可扩展性，可适应于不同规模的虚拟机部署请求。

图7 计算时间

5 结 语

提出了一种基于能量与多维度QoS保障的虚拟机部署算法。建立了虚拟机部署的QoS模型，设计了一种通用QoS效用函数，实现了不同形式QoS的标准量化，并在此基础上，将虚拟机部署问题形式化为满足全局QoS保障的同时实现能耗的最小化；设计了一种改进粒子群算法的虚拟机部署策略对优化问题进行求解，该策略通过相关参数和进化操作的重新定义，以及局部适应度优先的粒子位置更新机制，实现能耗与全局QoS保障的均衡优化。实验结果表明，算法不仅在能耗与全局QoS保障性能上是优于同类算法的，并且在稳定性和可扩展性方面也有较好的表现。