服务延迟保障的混合绿色云数据中心成本最小化方法

黄晓冬，端木帅飞，毕 敬+，苑海涛

(1.海军航空大学，山东 烟台 264001；2.北京工业大学 信息学部软件学院，北京 100124；3.北京航空航天大学 自动化科学与电气工程学院，北京 100191)

0 引言

随着云计算技术的快速发展，工业界已将云计算视为提升经济发展的新途径[1-3]，云计算正在成为许多组织和数据中心的主导技术，这些组织和数据中心在很大程度上适应了私有和混合云计算模式[4]。随着基础设施即服务(Infrastructure as a Service, IaaS)和软件即服务(Software as a Service, SaaS)的不断商业化，目前云计算服务的定价多采用按需付费的定价策略[5]。与此同时，越来越多的互联网公司将基础设施和应用程序放在云端执行和访问，用户按需付费。例如，IBM、微软、谷歌和亚马逊等互联网企业已经为用户提供了不同的云服务[6]。而私有云服务提供商的目标是以最低的成本按需为用户提供服务，并保证服务质量(Quality of Service, QoS)。因此，最小化私有云服务提供商的成本是一项极具挑战的工作[7]。

在云+物联网时代，云数据中心对能源需求的日益增长使能源储备逐渐减少，能耗问题成为制约私有云提供商发展的关键[8]。云数据中心消耗能源的主要是服务器、存储设备、网络设备和冷却IT负载所需的电力设备，其在运行成本较高的同时排放出更多的二氧化碳[9]，由此引发云服务提供商的关注，尝试开发和利用新绿色能源(如太阳能和风能)成为降低云服务提供商成本的一个重要途径[10]。

混合云中应用复杂、类型多样、任务量大，每个应用通常有严格的服务延迟要求，使得私有云和公有云中的许多因素随时间不断变化[11]，如收益、电价、太阳能和风能，以及公有云虚拟机或容器的运行价格等，最小化任务的执行成本非常困难。另外，由于现实场景中存在多个公有云数据中心，每个公有云的资源使用价格不同且所提供的虚拟机类型多样，导致私有云的能耗成本很难准确估算。综上，在混合云中最小化任务的执行成本并满足其用户的响应时间约束，是一项非常艰巨的任务。本文提出基于成本最小化算法(Cost Minimization Algorithm, CMA)的任务调度方法，从而最小化私有云的总成本。进一步，为了确保云数据中心任务的服务延迟要求，本文给出基于遗传学习机制的混合粒子群优化(Genetic Learning Particle Swarm Optimization, GLPSO)算法，该算法结合了粒子群优化(Particle Swarm Optimization, PSO)算法和遗传算法(Genetic Algorithm, GA)。PSO属于群体智能的范畴，其中的社会学习机制有助于提高集体学习的效率，因此被广泛应用于寻找各种优化问题的全局极小值[12]；GA是基于自然选择和自然遗传机制的随机搜索技术，其中的搜索策略和遗传算子使其具有强大的全局搜索能力[13]。因此，将PSO和GA结合有助于找到问题的最优解，大幅降低私有云服务提供商的成本。

综上所述，本文工作主要有3方面贡献，具体如下：

(1)建立了一个混合云中的任务调度模型，该模型能够严格满足任务的服务延迟约束要求，并将任务智能地调度到私有云或公有云中执行。

(2)给出了私有云服务提供商成本最小化问题的表达式，通过罚函数进一步将其转化为无约束的混合整数非线性规划问题。

(3)提出GLPSO算法求解该问题，得到每个时间间隔的最终解，并根据每个解给出一种新的CMA，该算法在能耗上优先使用绿色能源，相比常规优化算法可以大幅降低私有云服务提供商的成本。

1 相关工作

1.1 数据中心资源分配

WANG等[14]基于蚁群算法提出负载均衡技术，通过检测服务器负载实现了对数据中心的负载均衡操作；WANG等[15]针对IaaS提出一种智能的动态资源分配方法，使竞价在每一轮拍卖中都具有合理性，从而确定供应商和消费者之间的交易关系，并提出一种基于反向传播神经网络的价格预测算法和价格匹配算法的形成机制，可以将不诚实的参与者排除在云市场之外；CHEN[16]提出一种支持突发和紧急需求的云资源分配方法，能够及时、优化地分配各种资源，以应对紧急的应用资源需求，该方法重建了资源分配的新优先级，能够为紧急的应用请求分配更早的虚拟机资源；WU等[17]提出高效的准入控制和资源调度算法，其目标是允许分析即服务(Analysis as a Service, AaaS)提供商在服务等级协议保证下交付AaaS，以增加市场份额、声誉和用户满意度，并提高其利润。以上研究主要针对资源分配问题，并未考虑私有云服务提供商的成本最小化问题，本文则通过将任务智能调度到公有云中执行，最小化私有云服务提供商的总成本。

1.2 数据中心绿色节能

YEGANEH等[18]针对不同的节能降耗因素，提出动态定价算法的容量规划，解决了权衡操作成本和服务延迟的问题；FARAHNAKIAN等[19]提出一个分布式系统架构来合并动态虚拟机，以减少云数据中心的能耗，同时保持所需的QoS，最后采用一种蚁群系统的在线优化元启发式算法解决虚拟机合并问题；CHIANG等[20]在性能保证范围内控制服务速率并优化操作成本，同时考虑功耗、系统拥塞和服务器启动成本，提出一种高效的绿色控制算法，用于解决不同节能策略下的系统约束优化问题。然而，以上研究不能有效利用绿色能源降低能耗，本文设计的模型优先使用绿色能源，绿色能源不足时才考虑使用电能，该模型在治理日益突出的环境污染问题方面具有重要的意义。

1.3 分布式数据中心能耗优化

LI等[21]通过Lyapunov优化框架设计了一个在线动态供应算法，解决了现实世界中没有公有云租赁价格的先验信息和用户请求未来概率未知的问题；XU等[22]提出一种能源感知的资源分配方法——EnReal，同时结合部署在多个云计算平台的应用，提出一个能耗模型及其相应的能量感知资源分配算法，用于虚拟机调度，从而在跨云平台甚至云平台内部以能源感知的方式执行科学的工作流；LUO等[23]利用电力价格的空间和时间变化最小化电力市场管制下分布式云数据中心的能源成本；YAO等[24]提出一种大规模地理分布式数据中心的作业调度和服务器管理的随机优化方法，在处理延迟容忍型工作负载时有效降低了能耗。然而以上研究没有综合考虑能量成本、绿色能源和虚拟机资源价格在时间上的多样性，本文的任务调度方法考虑了私有云电价、绿色能源和公有云价格在时间上的多样性，并严格满足服务延迟要求，通过将所有到达的任务智能地调度到私有云和公有云中执行来最小化私有云服务提供商的成本。

2 混合云中任务调度的体系结构

数据中心提供商通常拥有私有云和执行一些额外任务的公有云，当私有云中资源有限或在公有云的虚拟机中执行任务更经济时，会将一些任务调度到公有云中执行。本文提出了混合云中的任务调度架构，如图1所示。该架构由私有云和公有云两部分组成。私有云中包含了大量的虚拟资源，如CPU、内存和存储等，用户到达的任务首先依次加入一个先进先出(First Come First Served, FCFS)队列中，架构的主要组件是任务调度器，FCFS队列的所有信息(如到达任务数量)会发送给任务调度器。私有云获得的电能主要有网格能量(h)、太阳能(s)和风能(w)3种来源，任务调度器会定期收集电网的价格、风速、太阳辐射强度和现场空气密度，根据收集的信息调度组件执行任务调度，其中CMA确保每个任务在服务延迟约束下定期调度任务到私有云或公有云中，并确定每个时间间隔内分别在私有云和公有云中调度执行的任务数量。

3 系统模型和构造成本最小化问题

本文重点是延迟容忍类型应用的任务，包括大规模数据分析、科学计算、图像处理等任务。随着部署在数据中心的计算机越来越多，越来越多的云数据中心支持多核计算并趋向于并行化，本文将每个任务分解为功能相当的小任务，每个小任务都可以在一个时间间隔内执行完毕。另外，所有到达的任务都有严格的服务延迟约束(B)，即t时刻到达的任务必须在t～t+B时间间隔内被调度执行。为了有效构造模型，本文给出以下假设：

(1)任意t时刻内到达的任务数量已知。

(2)任务调度器组件可以收集到任意t时刻私有云的电价、公有云的执行价格、太阳能和风能的能量、带宽费用和任务的执行时间等信息。

(3)公有云处理任务的能力是无限的，每个时间间隔内任意任务都可以在公有云中被调度执行。

3.1 绿色能源模型

(1)

(2)

具体参数设置如表1所示。

表1 绿色能源计算的相关参数

3.2 成本最小化问题

为了解模型的功能，现对成本最小化问题中资源、任务、约束等参数和决定变量进行详细描述，如表2和表3所示。

表2 问题参数

续表2

表3 决策变量参数

本文工作的最终目标是最小化私有云提供商的成本，该目标函数定义为P1，包括私有云和公有云成本两部分，即

Cost=Costprivate+Costpublic。

(3)

式中：Costprivate为私有云的成本；Costpublic为公有云的成本。

在任意t时刻，到达的任务会先进入一个FCFS队列，然后通过任务调度器被分别调度到私有云或公有云中执行。令Δt为t时刻累积到达的任务数量，Dt为t时刻累积调度的任务数量，即

(4)

私有云中从t～t+m时间内的成本包括执行任务消耗的能源成本和带宽费用两部分，即

(5)

对于私有云中的能耗，私有云会首先使用绿色能源，以最大程度降低对环境的污染，当绿色能源不足时，将使用电网的能量。

公有云中在t～t+m时间内的成本包括虚拟机的执行价格和耗费的带宽费用两部分，即

(6)

由式(3)、式(5)和式(6)概括最终的成本最小化问题P1如下：

(7)

dtmemt≤memCap；

(8)

(9)

(10)

φdt≤ϖ；

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

式中：augCost和Penalty分别为新的增广函数和惩罚函数；σ是一个比较大的整数，主要表现为对augCost和Penalty的影响。

对于P2问题，每个等式或不等式约束对应的惩罚均被添加到原始目标函数Cost，其中惩罚函数

(23)

4 求解算法

算法1CMA算法伪代码。

1: 初始化λt(0≤t≤B)为0

2: 初始化Δ0和DB为0

3: t←B+1

4: while t≤Length do

5: 用GLPSO算法解决P2

7: Δt-B←Δt-B-1+λt-B

8: Dt←Dt-1+dt

9: for c←1 to C do

11::end for

12::t←t+1

13::end for

算法2GLPSO算法伪代码。

1: 初始化每个粒子的位置和速度

2: dN←(2*C+1)*(B+1)

3: Position←zeros(numParticles,dN+1)

4: w←wmax-(wmax-wmin)/numIters*iterIndex

5: for i←1 to numParticles do

6: Position(i, dN+1)←augProfit(t, Position(i, 1∶dN, Δt-B, Dt))

7: end for

8: 计算Positionlocal和Positionglobal

9: While iterIndex≤numIters do

10:for i←1 to numParticles do

11: 通过GA的交叉(Positionlocal，Positionglobal)、变异、选择得到精英粒子Exemplar(E(i, 1∶dN))

12: if f(E(i, 1∶dN))在sg代后停止更新

13:通过锦标赛策略从20%粒子中选择最好的粒子E(j, 1∶dN)

14: E(i, 1∶dN)=E(i,1∶dN)

15:end if

16: Velocity(i,:)=w*Velocity(i,:)+c*rand*(E(i,1∶dN)-Position(i,1∶dN))

17:更新粒子i

18:i=i+1

19:end for

20: w=wmax-(wmax-wmin)/totalIterations*iterationIndex

21:end while

求解P2问题通常采用典型的元启发式算法，如PSO算法和GA，这些算法不需要优化问题数学结构的任何辅助信息，并具有鲁棒性和易于实现等特点，然而作为仿生优化领域两个著名分支，两种算法都有各自的优缺点。典型GA由选择、交叉和突变3个基本算子组成。选择算子复制高质量的染色体，以提高种群的平均适应度值，也被称为进化；交叉和突变是生殖操作，能够为进化中的种群提供质量更高的遗传物质；PSO算法不使用选择运算符，而是通过将粒子更新到历史最佳位置来表示进化，其中粒子的飞行轨迹与遗传物质的变化相对应。

GA和PSO算法因机制不同导致性能存在差异。标准GA随机选取两条染色体，采用交叉操作交换染色体相同位置的基因，使染色体中的一些基因通过突变获得随机变异，因此GA的复制过程在一定程度上是全方位的。PSO算法是一种基于种群的优化算法，具有实现简单、收敛速度快等特点，在标准PSO算法中，粒子由粒子之前的最佳位置(pbests)和群体发现的全局最佳位置(gbest)引导，搜索比GA更有方向性。因此，本文期望GA具有比PSO算法更好的寻优能力，PSO算法具有比GA更快的收敛速度。

为了进一步提高PSO算法性能，本文提出GLPSO算法，如图2所示。在GLPSO算法中，GA和PSO算法以级联方式杂交，该算法的主循环由两个级联层组成，一个通过GA生成范例，一个按照标准的PSO算法进行粒子更新。该方法使PSO算法中的粒子不再简单地用gbest和pbests，而是用GA构造的样本来指导。因此，GA和PSO算法以一种高内聚的方式进行杂交，

在GLPSO算法中，通过学习GA构建样本，使粒子搜索更加多样化，可以避免PSO算法过早收敛，而且由于GA选择算子的作用，使幸存的样本质量较高，能够对粒子进行有效引导，从而提高PSO算法的搜索效率。反之，粒子的搜索经验(pbests和gbest)将更优秀的遗传物质传播回GA，帮助GA复制改进的样本。因此，在该级联结构中，PSO算法与GA之间的相互作用效果明显，而且在优化过程中不断迭代又进一步增强了PSO算法与GA之间的相互作用。

5性能评估

5.1 实验环境及参数设置

为了评估所提CMA的性能，本文采用真实云计算中心的负载，如图3所示。图中数据集为2011年5月某天的1 440 min内，谷歌数据中心集群中3种类型任务到达的数量，其中采集时间间隔为5 min，共产生288个数据点。本文采用类型3的任务来评估所提算法的性能。

CMA的不同参数设置如下：

(3)GLPSO算法的迭代次数numIters=1 000，粒子数numParticles=100，wmax=0.95，wmin=0.4，c1=2，c2=2，c=1.496 18，pm=0.1，vmax=500。

5.2 实验结果

实验假设公有云数据中心的处理能力是无限的，其中图4、图5分别为每个时间间隔内私有云数据中心和公有云数据中心调度的任务数量。由图5可知，每个时间间隔内只有一个公有云数据中心在运行使用，其他公有云数据中心接受的任务数量为0。每个时间间隔内私有云提供商的成本和罚函数的惩罚值如图6所示，可见罚函数的惩罚值在每个时间间隔内接近于0。因此，本文提出的混合云任务调度在每个时间间隔内都能找到有效的解决方案，而且能够降低私有云服务提供商的成本。图7所示为每个时间间隔内的累积到达任务和累积调度任务，实验中设置服务延迟为3个时间间隔，可见到达的任务在服务延迟要求内可以被有效地调度。因此，CMA可以满足任务服务延迟的要求。

私有云和公有云的累积调度任务数量如图8所示。可见，私有云中调度的任务数量远大于任意一个公有云调度的任务数量。私有云提供商总是以最经济的方式在其中或公有云中智能地调度到达的任务，以保证成本最小化。当其将任务调度给公有云时，需要向公有云支付费用，公有云提供商同样会选择成本最小的公有云来执行到达的任务。每个到达的任务都尽可能在私有云中执行，有两种情况可能将任务调度到公有云中：①私有云的能力有限，不足以调度到达的任务；②公有云执行任务的成本足够低。

5.3 对比实验结果

为了验证算法的有效性，本文将所提GLPSO算法与两种典型算法——模拟退火粒子群优化(Simulated Annealing Particle Swarm Optimization, SAPSO)算法[10]和GA[11]进行对比。其中，SAPSO算法适用于求解局部最优解，算法中的每个粒子均基于模拟退火(Simulated Annealing, SA)算法中的Metropolis准则来更新自己的位置。在每个迭代中，比较当前解决方案和新生成解决方案的目标函数值，改进解被直接接受，同时接受一些较差的解，以摆脱局部最优而获得全局最优。

图9所示为GLPSO算法和两种基线算法的成本对比。明显可见，在大部分时间间隔内，结合了PSO算法和GA的GLPSO算法在求成本最小化的问题上表现良好，在3种算法中成本最低。与SAPSO算法相比，GLPSO算法的成本在89%的时间间隔内大于SAPSO算法，最大成本差达到231.4 $；与GA相比，GLPSO算法的成本在93%的时间间隔内大于GA，最大成本差达到301 $。

图10所示为GLPSO算法和两种基线算法的平均演化曲线，取自第10个时间间隔，即t=10。与SAPSO相比，GLPSO算法虽然收敛速度较慢(经历100次迭代才找到收敛的最终解)，但是所产生的成本比SAPSO低79.51%，其能够将私有云提供商的成本减少150 $。相比之下，GA表现最差，该算法在收敛过程中一直在震荡，始终不能收敛到最优解。

图11和图12所示分别为GLPSO算法和两种基线算法的CPU与内存利用率的对比。可知，GLPSO算法的CPU和内存利用率比较稳定，在0.35附近波动，而且在81%时间间隔内高于SAPSO算法和GA。

6 结束语

越来越多的互联网公司将应用程序部署到云数据中心，任务的不断增长显著增加了私有云服务提供商的能耗成本，现阶段的云数据中心普遍采用混合云方案处理到达的任务，然而混合云中的私有云电网价格、太阳辐射强度、风速和公有云虚拟机执行价格的变化对混合云中的任务调度带来了挑战。为了尽可能减少私有云服务提供商的成本并满足任务的服务延迟约束，本文提出一个成本最小化模型来调度到达的任务，该模型可以根据私有云成本和公有云中多因素的时间变化特性，智能地将所有任务调度到私有云或公有云中执行。CMA采用混合启发式优化算法——GLPSO算法最小化成本，该混合算法采用遗传算子，即交叉、变异和选择构造样本，其中交叉利用粒子的历史信息，包括之前的最佳位置和群体的全局最佳位置产生高质量的后代，变异则通过向后代注入多样化信息来加强全局搜索。基于真实数据的仿真实验证明，所提算法在满足服务延迟约束的同时，能够显著降低私有云服务提供商的运营成本。未来拟将该模型应用到实际的云数据中心，进一步改进和完善任务调度的性能与执行效率。