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

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

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

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

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

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

与文献[26]相似，本文采用离散时隙模型，假设在每个在时隙$t = (1, 2, \cdots , \tau , \cdots )$，到达数据中心响应式、延迟容忍负载分别记为${W_1}(t)$和${W_2}(t)$，并且${W_1}(t)$、${W_2}(t)$满足约束：

式中，$W_1^{{\rm{max}}}$、$W_2^{{\rm{max}}}$分别为数据中心能处理的响应式和延迟容忍负载的最大容量。

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

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

式中，${d_{{\rm{max}}}}$为云中心需要保证的最大平均响应时间。另外，服务器利用率$\rho = \frac{{{W_{\rm{1}}}(t)}}{{{n_{\rm{1}}}(t){\mu _{\rm{1}}}}} < 1$，以保证服务器的利用率不会过载。

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

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

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

1) 风能发电量：$E_{{\rm{supply}}}^w(t) = \frac{1}{2}\beta B\rho {v^3}(t)l$。其中$v(t)$为时隙t的风速，B为所有风力涡轮机转子总面积，β为风能到电能的转换效率系数，ρ为空气密度，l是时间长度。

2) 太阳能发电量：$E_{{\rm{supply}}}^s(t) = \alpha As(t)l$。其中$s(t)$为时隙t的光照辐射强度，A为太阳能面板总面积，α为太阳能到电能的转换效率系数，l是时间长度。

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

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

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

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

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

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

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

记$\vec E(t) = \{ {E^b}(t), {E^s}(t), {E^w}(t)\} $，$\vec n(t) = \{ {n_1}(t), $ ${n_2}(t)\} $，则本文优化问题描述为：在时变的电力价格和可再生能源供应下，数据中心在每个时隙选择能源购买量$\vec E(t)$和活动服务器数量$\vec n(t)$，在满足不同负载SLA以及长期碳排放约束下，使得长期能源成本最小。该问题为一个随机优化问题，数学表示为：

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

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

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

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

如果队列$Q{\rm{(}}t{\rm{)}}$稳定，即$\mathop {{\rm{limsup}}}\limits_{T \to \infty } \frac{1}{T}\sum\limits_{t = 0}^{T - 1} {{\rm E}[Q{\rm{(}}t{\rm{)}}]} \leqslant \infty $，则意味式(12)可以满足^[31]。定义${\mathit{\boldsymbol{ \boldsymbol{\varTheta}}}} (t) \triangleq \left[ {Q{\rm{(}}t), U(t)} \right]$，根据Lyaponov优化框架，定义Lyapunov优化函数和一个时隙的Lyapunov偏移量分别为$L(t) \triangleq \frac{1}{2}[{Q^2}{\rm{(}}t) + $ ${U^2}(t)]$和$\vartriangle (t) \triangleq {\rm E}[L(t + 1) - L(t)|{\mathit{\boldsymbol{ \boldsymbol{\varTheta}}}} (t)]$^[32]。通过控制$\vartriangle (t)$来调整队列$Q{\rm{(}}t), U(t)$的拥塞程度。另外，将优化目标的期望值(惩罚函数)与$\vartriangle (t)$相加，可以得到时隙t的Lyapunov偏移加惩罚之和为：

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

引理1对于任何可行的控制策略$\vec E(t)$和$\vec n(t)$，一个时隙的Lyapunov偏移值$\vartriangle (t)$的上界表示为：

证明：根据不等式：

$\forall a, b, c \geqslant 0$，可以得到：

同样根据不等式：

得到：

将式(22)和式(23)相加后，两边取期望，则得到引理1，其中$B = \frac{{{{(M{\mu _{\rm{2}}})}^{\rm{2}}} + {{(W_{\rm{2}}^{{\rm{max}}})}^{\rm{2}}}}}{{\rm{2}}} + \frac{{{H^{\rm{2}}} + E_{{\rm{max}}}^{\rm{2}}}}{{\rm{2}}}$，${E_{ \rm max}}$表示在某个时隙时数据中心的最大碳排放量。证毕。

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

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

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

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

输入：负载W₁(t)、W₁(t)；气候数据s(t)、v(t)；电力价格P^b(t)、P^w(t)、P^s(t)

输出：决策变量$\vec E(t)$和$\vec n(t)$

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

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

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

4) 更新时隙t：$t \leftarrow t + 1$

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

定理 1  (CACM算法性能)假设系统状态(W₁(t)、W₂(t)、s(t)、v(t)、P^b(t)、P^w(t)、P^s(t))在时隙内属于独立同分布，则对于控制参数$V > 0$，CACM算法可以达到以下性能保证：

式中，${C^*}$为时间平均能源成本的理论下界。

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

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

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

将$t = 0, 2, \cdots , T - 1$时隙相加求和，并且两边除以T，得到：

因为${\rm E}[L(T)]$有限，${\rm E}[L(T)]$非负，取$T \to \infty $，可以得到式(27)，定理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 m²，风力涡轮机转子总面积B=650 m²。空气密度为ρ=1.225 kg/m³。根据前面描述的风力和太阳能发电模型，可得数据中心绿色能源电力供应数据。开始一周风能和太阳能发电量如图 2a所示。

图  2  实验基本参数

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

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

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

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

1) 控制参数V的影响

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

图  3  V和平均成本关系

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

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

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

当碳排放约束分别50 kg，60 kg，70 kg，80 kg时，碳排放约束和能源成本关系如图 5所示。由图 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更为灵活。

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

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

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

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