碳感知的绿色云数据中心能源优化在线算法

何怀文，肖 涛，程 东，彭 政，傅 瑜

(1.电子科技大学中山学院计算机学院 广东 中山 528402; 2.中山大学数据科学与计算机学院 广州 510275)

近年来，云数据中心每年所需的巨额能源费用以及产生的温室气体排放，已引起了学术界和工业界重要关注[1-2]。据统计，信息和通信技术(information communication technology, ICT)行业的碳排放已占到全球碳排放的2%，与航天工业相当，并且预计将到2020还要翻倍[3]。而随着可再生能源技术的发展，以及其污染少、用之不竭等特点，已被多个著名IT企业(如Google[4]、Apple[5]、 Microsoft[6])用于数据中心电力供应，以降低二氧化碳排放。因此，新能源的利用对构建绿色数据中心及其可持续发展，具有重要意义。

虽然可再生能源比传统电网能源具有更低的碳排放，但是可再生能源(尤其是风能和太阳能)受到当地气候条件影响较大，其能源供应具有间歇性和难以预测，它们的引入给云数据中心能源管理和负载调度带来了更大挑战[7]。同时，由于可再生能源的不稳定性，使得其电力成本往往高于传统电网电力价格。面对负载的随机性、电力价格的波动性和绿色能源的间歇性，需要设计在线的资源调度算法，在多种能源供应环境下以保证SLA和碳排放的约束条件，使得数据中心成本最小化是一个颇具挑战性的问题。

为了解决以上问题，本文从不同类型负载的特征出发，首先将数据中心能源成本优化问题形式化为一个受约束的随机优化问题，然后利用Lyapunov优化理论，设计了一个碳感知的能源优化在线控制算法，在线决策不同能源购买量以及数据中心活动的服务器数量。最后，本文基于真实数据进行了大量的仿真实验，验证了算法性能。

1 相关工作

利用绿色能源和电力价格的时变性来进行资源调度，解决数据中心高能耗、高费用、高污染等问题，已经成为了目前的研究热点[2,8-9]。文献[10-11]利用电力价格的时空化特性，将数据中心能耗优化问题形式化为混合非线性整数规划问题并进行求解。文献[12-13]扩展了文献[10-11]的模型，提出可再生能源下的数据中心负载均衡在线算法。但上述研究仅仅考虑了响应式负载的SLA和数据中心成本的关系，并没有考虑到数据中心碳排放的环境影响。

文献[14]关注了延迟容忍负载的优化调度问题，基于Lyapunov优化提出一种双尺度的跨地域负载调度算法。文献[15-16]针对批处理作业的GreenHadoop和GreenSlot调度系统，通过预测太阳能的可用量来达到最大化太阳能利用率的目的，但以上系统并不适用于延迟敏感的应用。文献[17]通过时隙数区分不同负载类型，设计了可以同时调度不同负载的在线能源算法。文献[18-20]通过预测未来一段时期内再生能源的发电量，然后延迟批处理负载的执行以降低数据中心的能源成本，但是对于难以预测的可再生能源而言，算法很难获得相应的性能保证。

与原有工作相比，本文综合考虑了多种能源供应下，数据中心性能、成本和碳排放三者之间的相互约束和平衡，提出了一种不需要获知未来数据的最小化数据中心能源成本的在线调度算法。

2 系统模型与优化目标

本文假设云数据中心能源供应包括：褐色能源、太阳能和风能。褐色能源以传统电网供电为主，太阳能和风能则从当地可再生能源发电公司购买(如Google向Iowa公司购买了20年风力电能[21])。数据中心系统模型如图1所示。

图1 绿色数据中心系统模型

2.1 负载模型

数据中心请求通常分为响应式请求和延迟容忍请求[22]。响应式请求指实时要求较高、需要在很短时间内处理完并返回结果的用户请求，如Web页面访问、网络游戏等，该类负载往往占到数据中心流量的50%以上[13,23]。延迟容忍请求则通常为批处理任务，需要较长处理时间，如MapReduce[24]和大规模图形处理[25]等。

与文献[26]相似，本文采用离散时隙模型，假设在每个在时隙到达数据中心响应式、延迟容忍负载分别记为W1(t)和W2(t)，并且满足约束：

如图1所示，处理响应式和延迟容忍负载的活动服务器数量分别为记为n1(t)和n2(t)，数据中心服务器总数量记为M，则有：

对于响应式负载，通常采用平均响应时间作为SLA[12]。本文采用M/GI/1/PS排队模型来模拟响应式负载服务器群n1(t)，假设负载被平均分发到每台处理速率为1μ的服务器进行处理。根据文献[27]，得到平均响应时间为则响应式负载的SLA约束可以表示为：

式中，dmax为云中心需要保证的最大平均响应时间。另外，服务器利用率以保证服务器的利用率不会过载。

延迟容忍负载允许推迟若干时隙才开始执行，因此可以将延迟容忍负载推迟到电力价格较低时处理，以节省能源成本。本文假设延迟容忍负载的动态队列为U(t)，该类负载服务器处理速率为2μ，则的队长变化为：

对于队列U(t)，需要保证该队列的长期稳定性，即保证U(t)时间平均队长期望值小于无穷大，有：

2.2 能源模型

本文只考虑风能和太阳能两种最常用的可再生能源。风能和太阳能的发电量受当时地域气候(风速和太阳光照辐射)影响较大。假设在时隙t风能和太阳能的发电量分别为根据文献[28-30]的能源模型，可得风能和太阳能的发电量表示如下：

本文假设数据中心中每台活动服务器能耗模型相同[12,26]，单位时间能耗为0P，则时隙t数据中心总能耗为其中电能使用效率(power usage effectiveness, PUE)为数据中心消耗的总能源与IT设备消耗的能源之比。假设在时隙t数据中心购买的褐色能源、太阳能和风能分别为Eb(t)、则有：

另外，风能和太阳能的购买量不能超过当时的发电量，因此有：

2.3 碳排放模型

在消耗等量能源的情况下，可再生能源碳排放小于褐色能源碳排放。碳排放速率(carbon emission rate, CER)用于表示不同能源的碳排放速率。假设褐色能源、风能、太阳的CER分别记为eb,ew,es，具体数值如表1[31]所示。

表1 不同能源的碳排放速率

因此，时隙t数据中心总碳排放量表示为：

现实中，数据中心需要控制某个时期内的碳排放量。类似文献[31]，本文假设数据中心的时间平均碳排放量满足以下约束：

式中，H为数据中心的时间平均碳排放最大限制。

2.4 问题描述

本文假设数据中心参与了电力批发市场，电力价格随着时间动态波动[1]。时隙t的褐色能源、风能、太阳能电力价格分别为Pb(t)、Pw(t)和Ps(t)。因此，时隙t数据中心能源成本可表示为：

3 问题求解

3.1 离线问题求解

在离线情况下，如获知将来每个时隙的系统状态数据(如负载、电力价格、风速和光照辐射等)后，问题P1属于一个混合整数规划(mixed-integer linear programming, MILP)问题。而由于问题规模过大，求解P1时易碰到“维度灾难”导致算法收敛慢等问题。与文献[22, 32]类似，本文设计了一个向前看K-步的离线求解算法。假设算法运行时间段共J个时隙。将整个周期J分为R个时间帧，每个时间帧包含有K个时隙，则有J=RK。假设可以提前获知K个时隙内的所有系统信息，因此，优化时间段J的平均成本可以转换为求解R个P2优化问题，其中P2描述为：

为了保证问题P2存在可行解，本文做了以下假设：1)边界假设：对于假设负载到达速率W1(t)、W2(t)是有限的；2)可行性假设。假设对于每一个帧都存在至少一个可行策略，满足问题P2的所有约束。而问题P2可以松弛为一个线性规划问题，可通过相关算法求解。因此，通过求解问题P2，可以得到第r帧的最小平均值为因此，在J时期内，向前看K-步算法得到的最小成本值为

3.2 在线算法设计

在现实生活中，信息往往难以获得或准确预测。负载、电力价格以及绿色能源供应量的随机性和动态性给问题的求解带来很大挑战。因此，本文利用最新发展的Lyapunov优化理论[32]，设计了一种在无须预测未来数据，仅依靠当前系统状态而做出决策的在线算法。该算法复杂性低、易于部署，可获得接近最优解的次优解。

首先将长期碳排放约束式(12)转换为队列稳定性问题。构造“碳排放虚拟队列”Q(t)，表示数据中心碳排放量与长期碳排放约束H的偏移，并初始化Q(t)=0。Q(t)队长动态变化如下：

如果队列Q(t)稳定，即则意味式(12)可以满足[31]。定义根据Lyaponov优化框架，定义Lyapunov优化函数和一个时隙的Lyapunov偏移量分别为通过控制来调整队列的拥塞程度。另外，将优化目标的期望值(惩罚函数)与△(t)相加，可以得到时隙t的Lyapunov偏移加惩罚之和为：

式中，V＞0，为控制参数，用于调节目标函数和约束条件之间的权重。

证明：根据不等式：

同样根据不等式：

得到：

将式(22)和式(23)相加后，两边取期望，则得到引理1，其中表示在某个时隙时数据中心的最大碳排放量。证毕。

根据引理1和式(20)，可得到时隙t的Lyapunov偏移加惩罚之和的上界为：

根据Lyapunov优化理论，最小化每个时隙t的偏移加惩罚之和则可获得目标函数的最优解[32]。而在式(24)中，队长Q(t)、H、U(t)和W2(t)在每个时隙t开始可以获得，因此，问题P1可以转换为最小化每个时隙的上界，即转换为问题P3，表示为：

因此，本文提出碳感知成本最小化在线算法(carbon-aware for cost minimization online algorithm,CACM)的具体描述如下：

算法1：碳感知成本最小化在线算法—CACM算法

输入：负载W1(t)、W1(t)；气候数据s(t)、v(t)；电力价格Pb(t)、Pw(t)、Ps(t)

1)在每个时隙t开始时刻，获取当前队列U(t)和Q(t)队长以及其他系统状态信息(负载、电力价格和气候数据)。

2)求解优化问题P3，满足约束条件式(2)～式(5)，式(8)～式(11)，式(13)。

3)根据式(6)、式(19)分别更新队列U(t)和Q(t)的队长。

4)更新时隙t：t←t+1

P3目标函数中C(t)是一个包含了Eb(t)、Ew(t)、的线性表达式，同时n1(t)可以由式(5)求得，因此，求解P3即可获得每个时隙t的决策变量和而问题P3虽然是一个MILP问题，但是数据中心中整数变量n1(t)、n2(t)通常较大，可以将其松弛到实数域进行求解，即问题P3可转换为一个仅具有5个变量的线性规划问题，使用内点法在多项式时间内获得有效解，最坏情况下时间复杂度为其中n=5，L为输入长度。由此可见，CACM算法能够在线运行。本文使用了IBM CPLEX[33]工具对问题P3进行求解。

3.3 在线算法性能分析

定理 1 (CACM算法性能)假设系统状态(W1(t)、W2(t)、s(t)、v(t)、Pb(t)、Pw(t)、Ps(t))在时隙内属于独立同分布，则对于控制参数V＞0，CACM算法可以达到以下性能保证：

证明：根据Lyapunov优化理论[32]，对于问题P1，至少会存在一个随机平稳控制策略π(选择和满足P1的所有约束并得到以下结果：

根据式(20)和式(21)，有：

根据期望迭代法则，得到：

因为E[L(T)]有限，E[L(T)]非负，取T→∞，可以得到式(27)，定理1得证。

4 实验仿真

4.1 参数设置

本文基于真实负载、气候、电力价格等数据，模拟一个常见的互联网云数据中心。仿真实验中每个时隙t长度为10分钟，共模拟为4 464个时隙(31天)，相关参数设置如下：

1)绿色能源数据。从美国国家可再生能源实验室(national renewable energy laboratory, NREL)[33]获取位于亚利桑那大学测量站从2015年10月1日～2015年10月31日测得的风速v(t)和太阳光照辐射强度s(t)的历史数据。对于绿色能源电力供应模型，本文采用与文献[34-35]相同的参数设置，假设太阳能和风能的电力转换效率系数分别为α=20%，β=30%。太阳能发电面板总面积A=1 000 m2，风力涡轮机转子总面积B=650 m2。空气密度为ρ=1.225 kg/m3。根据前面描述的风力和太阳能发电模型，可得数据中心绿色能源电力供应数据。开始一周风能和太阳能发电量如图2a所示。

2)动态电力价格数据。从纽约独立系统调度机构(new york independent system operator, NYISO)[36]获取该地区相应时间的实时分区边际电价(locational marginal price, LMP)作为褐色能源电力价格Pb(t)，并将实时电力价格缩放到1个时隙时间。类似文献[21]，本文假设风能和太阳能电力价格分别为价美分。开始一周风能和太阳能电力价格变化如图2b所示。

3)负载数据。本文同样选取从2015年10月1日开始的Wiki Dump[37]访问流量作为数据中心负载样本。延迟容忍负载占总负载比例为随机数γ，假设γ服从0.2～0.4的均匀分布，即开始一周负载流量如图2c所示。

4)数据中心参数设置。假设该数据中心拥有服务器总量M=2 000，服务器功率为230 W，数据中心PUE=1.2。假设响应式负载平均响应时间限制dmax=0.1 s，服务速率μ1=20，延迟容忍负载服务速率

图2 实验基本参数

4.2 基准参数

本文使用以下算法作为数据中心能源成本和碳排放的基准算法：1)最小化数据中心能源成本Min-Cost算法；2)最小化碳排放Max-Green算法。其中Min-Cost算法假设只使用价格最低的褐色能源，没有采用绿色能源；Max-Green则优先采用碳排放率低的绿色能源，在能源不足时才使用褐色能源。Min-Cost算法和Max-Green算法获得数据中心平均能源成本和平均碳排放边界值如表2所示。

表2 数据中心平均能源成本和平均碳排放边界值

4.3 结果讨论

1)控制参数V的影响

假设长期碳排放限制为H=60 kg。数据中心平均能源成本值C(t)随着时隙t的变化曲线如图3所示。由图3可见，平均能源成本C(t)在开始阶段处于不稳定状态，而随着时隙增加，C(t)逐渐变得平稳，说明本文算法可使平均成本逐渐趋于平稳。另外，在图3中，当控制参数V增大时，数据中心平均成本将越小，与定理1相符合。

图3 V和平均成本关系

图4 V和能源使用比例关系

本文还分析了不同控制参数V下，数据中心各种能源的比例变化情况，如图4所示，其中碳排放约束H=55 kg。由图4可见，当V增大时，褐色能源的使用比例逐渐增加，而太阳能使用比例则逐渐减少。原因在于V增加将会使式(16)中成本值优化比重增加，意味着更大程度降低成本，从而促使选择价格更低的能源。同时，风能使用比例一直高于太阳能，原因在于风能比太阳能拥有具有更低的碳排放速率和价格，因而会被优先考虑。由此可知，如果不考虑风能和太阳能的部署因素，仅从价格和碳排放因素上看，风能将具有更好的竞争力。

2)碳排放约束对能源成本的影响

当碳排放约束分别50 kg，60 kg，70 kg，80 kg时，碳排放约束和能源成本关系如图5所示。由图5可见，随着平均碳排放约束的增大，算法将获得更低的成本，表明当放松碳排放约束时，数据中心运营成本将更低，与现实相符。但成本降低意味着温室气体排放增加，对气候环境影响愈加严重。

另外，不同碳排放约束下各种能源的使用比例如图6所示，其中V= 30 000。由图6可见，随着碳排放约束增加，绿色能源使用比例逐渐减少，其中当碳排放约束为80 kg时，太阳能使用量已经接近为0。原因在于随着碳排放约束放松，算法将更多从价格上考虑能源选择，因此会优先选择低价的褐色能源、风能，而由于太阳能价格最高，所以用量最低。当碳排放约束为85 kg时，已经接近碳排放基准上界89.05 kg，说明此时碳排放对成本影响已经非常低。

图6 碳排放约束和能源使用比例关系

3)与相关算法比较

本文算法与Max-Green算法的比较如图7所示，此时碳排放约束H=50 kg，控制参数V= 10 000。如前所述，Max-Green算法主要思想是实现数据中心最大绿色化[38]，其获得的碳排放约束下界为46.73 kg。在图7中，本文算法获得平均成本值为5.84，而Max-Green算法获得成本值为6.89。可见，在碳排放约束减少了6.8%的情况下，本文CACM算法可节省约13.8%的能耗成本，性能良好。同时本文算法可以根据不同碳排放约束获得其最优成本值，比Max-Green更为灵活。

本文算法与3.1节的离线最优算法比较如图8所示，此时碳排放约束H=70 kg。由图8可见，随着控制参数V的增加，本文算法获得成本值会逐渐逼近离线最优成本，表示通过调节控制参数V，本文算法可以达到离线最优解。

图7 本文算法与Max-Green算法对比

图8 本文算法和离线最优算法对比

5 结束语

本文针对满足不同类型负载的SLA和长期碳排放约束下，优化数据中心的能源成本问题，提出了一个碳感知的在线控制CACM算法。该算法不需要预测未来信息，仅靠当前系统状态信息作出决策，并可获得接近离线最优解的近似解。通过基于真实数据的大量仿真实验验证了本文的CACM算法，结果表明CACM算法具有良好的性能，可以获得更优的能源成本。下一步工作计划将该算法推广到跨地域云数据中心能源成本优化研究，以及考虑利用能源存储的方式来降低数据中心的成本。