何懷文，肖 濤，程 東，彭 政，傅 瑜

(1.電子科技大學(xué)中山學(xué)院計(jì)算機(jī)學(xué)院 廣東 中山 528402; 2.中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院 廣州 510275)

近年來，云數(shù)據(jù)中心每年所需的巨額能源費(fèi)用以及產(chǎn)生的溫室氣體排放，已引起了學(xué)術(shù)界和工業(yè)界重要關(guān)注[1-2]。據(jù)統(tǒng)計(jì)，信息和通信技術(shù)(information communication technology, ICT)行業(yè)的碳排放已占到全球碳排放的2%，與航天工業(yè)相當(dāng)，并且預(yù)計(jì)將到2020還要翻倍[3]。而隨著可再生能源技術(shù)的發(fā)展，以及其污染少、用之不竭等特點(diǎn)，已被多個著名IT企業(yè)(如Google[4]、Apple[5]、 Microsoft[6])用于數(shù)據(jù)中心電力供應(yīng)，以降低二氧化碳排放。因此，新能源的利用對構(gòu)建綠色數(shù)據(jù)中心及其可持續(xù)發(fā)展，具有重要意義。

雖然可再生能源比傳統(tǒng)電網(wǎng)能源具有更低的碳排放，但是可再生能源(尤其是風(fēng)能和太陽能)受到當(dāng)?shù)貧夂驐l件影響較大，其能源供應(yīng)具有間歇性和難以預(yù)測，它們的引入給云數(shù)據(jù)中心能源管理和負(fù)載調(diào)度帶來了更大挑戰(zhàn)[7]。同時，由于可再生能源的不穩(wěn)定性，使得其電力成本往往高于傳統(tǒng)電網(wǎng)電力價格。面對負(fù)載的隨機(jī)性、電力價格的波動性和綠色能源的間歇性，需要設(shè)計(jì)在線的資源調(diào)度算法，在多種能源供應(yīng)環(huán)境下以保證SLA和碳排放的約束條件，使得數(shù)據(jù)中心成本最小化是一個頗具挑戰(zhàn)性的問題。

為了解決以上問題，本文從不同類型負(fù)載的特征出發(fā)，首先將數(shù)據(jù)中心能源成本優(yōu)化問題形式化為一個受約束的隨機(jī)優(yōu)化問題，然后利用Lyapunov優(yōu)化理論，設(shè)計(jì)了一個碳感知的能源優(yōu)化在線控制算法，在線決策不同能源購買量以及數(shù)據(jù)中心活動的服務(wù)器數(shù)量。最后，本文基于真實(shí)數(shù)據(jù)進(jìn)行了大量的仿真實(shí)驗(yàn)，驗(yàn)證了算法性能。

1 相關(guān)工作

利用綠色能源和電力價格的時變性來進(jìn)行資源調(diào)度，解決數(shù)據(jù)中心高能耗、高費(fèi)用、高污染等問題，已經(jīng)成為了目前的研究熱點(diǎn)[2,8-9]。文獻(xiàn)[10-11]利用電力價格的時空化特性，將數(shù)據(jù)中心能耗優(yōu)化問題形式化為混合非線性整數(shù)規(guī)劃問題并進(jìn)行求解。文獻(xiàn)[12-13]擴(kuò)展了文獻(xiàn)[10-11]的模型，提出可再生能源下的數(shù)據(jù)中心負(fù)載均衡在線算法。但上述研究僅僅考慮了響應(yīng)式負(fù)載的SLA和數(shù)據(jù)中心成本的關(guān)系，并沒有考慮到數(shù)據(jù)中心碳排放的環(huán)境影響。

文獻(xiàn)[14]關(guān)注了延遲容忍負(fù)載的優(yōu)化調(diào)度問題，基于Lyapunov優(yōu)化提出一種雙尺度的跨地域負(fù)載調(diào)度算法。文獻(xiàn)[15-16]針對批處理作業(yè)的GreenHadoop和GreenSlot調(diào)度系統(tǒng)，通過預(yù)測太陽能的可用量來達(dá)到最大化太陽能利用率的目的，但以上系統(tǒng)并不適用于延遲敏感的應(yīng)用。文獻(xiàn)[17]通過時隙數(shù)區(qū)分不同負(fù)載類型，設(shè)計(jì)了可以同時調(diào)度不同負(fù)載的在線能源算法。文獻(xiàn)[18-20]通過預(yù)測未來一段時期內(nèi)再生能源的發(fā)電量，然后延遲批處理負(fù)載的執(zhí)行以降低數(shù)據(jù)中心的能源成本，但是對于難以預(yù)測的可再生能源而言，算法很難獲得相應(yīng)的性能保證。

與原有工作相比，本文綜合考慮了多種能源供應(yīng)下，數(shù)據(jù)中心性能、成本和碳排放三者之間的相互約束和平衡，提出了一種不需要獲知未來數(shù)據(jù)的最小化數(shù)據(jù)中心能源成本的在線調(diào)度算法。

2 系統(tǒng)模型與優(yōu)化目標(biāo)

本文假設(shè)云數(shù)據(jù)中心能源供應(yīng)包括：褐色能源、太陽能和風(fēng)能。褐色能源以傳統(tǒng)電網(wǎng)供電為主，太陽能和風(fēng)能則從當(dāng)?shù)乜稍偕茉窗l(fā)電公司購買(如Google向Iowa公司購買了20年風(fēng)力電能[21])。數(shù)據(jù)中心系統(tǒng)模型如圖1所示。

圖1 綠色數(shù)據(jù)中心系統(tǒng)模型

2.1 負(fù)載模型

數(shù)據(jù)中心請求通常分為響應(yīng)式請求和延遲容忍請求[22]。響應(yīng)式請求指實(shí)時要求較高、需要在很短時間內(nèi)處理完并返回結(jié)果的用戶請求，如Web頁面訪問、網(wǎng)絡(luò)游戲等，該類負(fù)載往往占到數(shù)據(jù)中心流量的50%以上[13,23]。延遲容忍請求則通常為批處理任務(wù)，需要較長處理時間，如MapReduce[24]和大規(guī)模圖形處理[25]等。

與文獻(xiàn)[26]相似，本文采用離散時隙模型，假設(shè)在每個在時隙到達(dá)數(shù)據(jù)中心響應(yīng)式、延遲容忍負(fù)載分別記為W1(t)和W2(t)，并且滿足約束：

如圖1所示，處理響應(yīng)式和延遲容忍負(fù)載的活動服務(wù)器數(shù)量分別為記為n1(t)和n2(t)，數(shù)據(jù)中心服務(wù)器總數(shù)量記為M，則有：

對于響應(yīng)式負(fù)載，通常采用平均響應(yīng)時間作為SLA[12]。本文采用M/GI/1/PS排隊(duì)模型來模擬響應(yīng)式負(fù)載服務(wù)器群n1(t)，假設(shè)負(fù)載被平均分發(fā)到每臺處理速率為1μ的服務(wù)器進(jìn)行處理。根據(jù)文獻(xiàn)[27]，得到平均響應(yīng)時間為則響應(yīng)式負(fù)載的SLA約束可以表示為：

式中，dmax為云中心需要保證的最大平均響應(yīng)時間。另外，服務(wù)器利用率以保證服務(wù)器的利用率不會過載。

延遲容忍負(fù)載允許推遲若干時隙才開始執(zhí)行，因此可以將延遲容忍負(fù)載推遲到電力價格較低時處理，以節(jié)省能源成本。本文假設(shè)延遲容忍負(fù)載的動態(tài)隊(duì)列為U(t)，該類負(fù)載服務(wù)器處理速率為2μ，則的隊(duì)長變化為：

對于隊(duì)列U(t)，需要保證該隊(duì)列的長期穩(wěn)定性，即保證U(t)時間平均隊(duì)長期望值小于無窮大，有：

2.2 能源模型

本文只考慮風(fēng)能和太陽能兩種最常用的可再生能源。風(fēng)能和太陽能的發(fā)電量受當(dāng)時地域氣候(風(fēng)速和太陽光照輻射)影響較大。假設(shè)在時隙t風(fēng)能和太陽能的發(fā)電量分別為根據(jù)文獻(xiàn)[28-30]的能源模型，可得風(fēng)能和太陽能的發(fā)電量表示如下：

本文假設(shè)數(shù)據(jù)中心中每臺活動服務(wù)器能耗模型相同[12,26]，單位時間能耗為0P，則時隙t數(shù)據(jù)中心總能耗為其中電能使用效率(power usage effectiveness, PUE)為數(shù)據(jù)中心消耗的總能源與IT設(shè)備消耗的能源之比。假設(shè)在時隙t數(shù)據(jù)中心購買的褐色能源、太陽能和風(fēng)能分別為Eb(t)、則有：

另外，風(fēng)能和太陽能的購買量不能超過當(dāng)時的發(fā)電量，因此有：

2.3 碳排放模型

在消耗等量能源的情況下，可再生能源碳排放小于褐色能源碳排放。碳排放速率(carbon emission rate, CER)用于表示不同能源的碳排放速率。假設(shè)褐色能源、風(fēng)能、太陽的CER分別記為eb,ew,es，具體數(shù)值如表1[31]所示。

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

因此，時隙t數(shù)據(jù)中心總碳排放量表示為：

現(xiàn)實(shí)中，數(shù)據(jù)中心需要控制某個時期內(nèi)的碳排放量。類似文獻(xiàn)[31]，本文假設(shè)數(shù)據(jù)中心的時間平均碳排放量滿足以下約束：

式中，H為數(shù)據(jù)中心的時間平均碳排放最大限制。

2.4 問題描述

本文假設(shè)數(shù)據(jù)中心參與了電力批發(fā)市場，電力價格隨著時間動態(tài)波動[1]。時隙t的褐色能源、風(fēng)能、太陽能電力價格分別為Pb(t)、Pw(t)和Ps(t)。因此，時隙t數(shù)據(jù)中心能源成本可表示為：

3 問題求解

3.1 離線問題求解

在離線情況下，如獲知將來每個時隙的系統(tǒng)狀態(tài)數(shù)據(jù)(如負(fù)載、電力價格、風(fēng)速和光照輻射等)后，問題P1屬于一個混合整數(shù)規(guī)劃(mixed-integer linear programming, MILP)問題。而由于問題規(guī)模過大，求解P1時易碰到“維度災(zāi)難”導(dǎo)致算法收斂慢等問題。與文獻(xiàn)[22, 32]類似，本文設(shè)計(jì)了一個向前看K-步的離線求解算法。假設(shè)算法運(yùn)行時間段共J個時隙。將整個周期J分為R個時間幀，每個時間幀包含有K個時隙，則有J=RK。假設(shè)可以提前獲知K個時隙內(nèi)的所有系統(tǒng)信息，因此，優(yōu)化時間段J的平均成本可以轉(zhuǎn)換為求解R個P2優(yōu)化問題，其中P2描述為：

為了保證問題P2存在可行解，本文做了以下假設(shè)：1)邊界假設(shè)：對于假設(shè)負(fù)載到達(dá)速率W1(t)、W2(t)是有限的；2)可行性假設(shè)。假設(shè)對于每一個幀都存在至少一個可行策略，滿足問題P2的所有約束。而問題P2可以松弛為一個線性規(guī)劃問題，可通過相關(guān)算法求解。因此，通過求解問題P2，可以得到第r幀的最小平均值為因此，在J時期內(nèi)，向前看K-步算法得到的最小成本值為

3.2 在線算法設(shè)計(jì)

在現(xiàn)實(shí)生活中，信息往往難以獲得或準(zhǔn)確預(yù)測。負(fù)載、電力價格以及綠色能源供應(yīng)量的隨機(jī)性和動態(tài)性給問題的求解帶來很大挑戰(zhàn)。因此，本文利用最新發(fā)展的Lyapunov優(yōu)化理論[32]，設(shè)計(jì)了一種在無須預(yù)測未來數(shù)據(jù)，僅依靠當(dāng)前系統(tǒng)狀態(tài)而做出決策的在線算法。該算法復(fù)雜性低、易于部署，可獲得接近最優(yōu)解的次優(yōu)解。

首先將長期碳排放約束式(12)轉(zhuǎn)換為隊(duì)列穩(wěn)定性問題。構(gòu)造“碳排放虛擬隊(duì)列”Q(t)，表示數(shù)據(jù)中心碳排放量與長期碳排放約束H的偏移，并初始化Q(t)=0。Q(t)隊(duì)長動態(tài)變化如下：

如果隊(duì)列Q(t)穩(wěn)定，即則意味式(12)可以滿足[31]。定義根據(jù)Lyaponov優(yōu)化框架，定義Lyapunov優(yōu)化函數(shù)和一個時隙的Lyapunov偏移量分別為通過控制來調(diào)整隊(duì)列的擁塞程度。另外，將優(yōu)化目標(biāo)的期望值(懲罰函數(shù))與△(t)相加，可以得到時隙t的Lyapunov偏移加懲罰之和為：

式中，V＞0，為控制參數(shù)，用于調(diào)節(jié)目標(biāo)函數(shù)和約束條件之間的權(quán)重。

證明：根據(jù)不等式：

同樣根據(jù)不等式：

得到：

將式(22)和式(23)相加后，兩邊取期望，則得到引理1，其中表示在某個時隙時數(shù)據(jù)中心的最大碳排放量。證畢。

根據(jù)引理1和式(20)，可得到時隙t的Lyapunov偏移加懲罰之和的上界為：

根據(jù)Lyapunov優(yōu)化理論，最小化每個時隙t的偏移加懲罰之和則可獲得目標(biāo)函數(shù)的最優(yōu)解[32]。而在式(24)中，隊(duì)長Q(t)、H、U(t)和W2(t)在每個時隙t開始可以獲得，因此，問題P1可以轉(zhuǎn)換為最小化每個時隙的上界，即轉(zhuǎn)換為問題P3，表示為：

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

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

輸入：負(fù)載W1(t)、W1(t)；氣候數(shù)據(jù)s(t)、v(t)；電力價格Pb(t)、Pw(t)、Ps(t)

1)在每個時隙t開始時刻，獲取當(dāng)前隊(duì)列U(t)和Q(t)隊(duì)長以及其他系統(tǒng)狀態(tài)信息(負(fù)載、電力價格和氣候數(shù)據(jù))。

2)求解優(yōu)化問題P3，滿足約束條件式(2)～式(5)，式(8)～式(11)，式(13)。

3)根據(jù)式(6)、式(19)分別更新隊(duì)列U(t)和Q(t)的隊(duì)長。

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

P3目標(biāo)函數(shù)中C(t)是一個包含了Eb(t)、Ew(t)、的線性表達(dá)式，同時n1(t)可以由式(5)求得，因此，求解P3即可獲得每個時隙t的決策變量和而問題P3雖然是一個MILP問題，但是數(shù)據(jù)中心中整數(shù)變量n1(t)、n2(t)通常較大，可以將其松弛到實(shí)數(shù)域進(jìn)行求解，即問題P3可轉(zhuǎn)換為一個僅具有5個變量的線性規(guī)劃問題，使用內(nèi)點(diǎn)法在多項(xiàng)式時間內(nèi)獲得有效解，最壞情況下時間復(fù)雜度為其中n=5，L為輸入長度。由此可見，CACM算法能夠在線運(yùn)行。本文使用了IBM CPLEX[33]工具對問題P3進(jìn)行求解。

3.3 在線算法性能分析

定理 1 (CACM算法性能)假設(shè)系統(tǒng)狀態(tài)(W1(t)、W2(t)、s(t)、v(t)、Pb(t)、Pw(t)、Ps(t))在時隙內(nèi)屬于獨(dú)立同分布，則對于控制參數(shù)V＞0，CACM算法可以達(dá)到以下性能保證：

證明：根據(jù)Lyapunov優(yōu)化理論[32]，對于問題P1，至少會存在一個隨機(jī)平穩(wěn)控制策略π(選擇和滿足P1的所有約束并得到以下結(jié)果：

根據(jù)式(20)和式(21)，有：

根據(jù)期望迭代法則，得到：

因?yàn)镋[L(T)]有限，E[L(T)]非負(fù)，取T→∞，可以得到式(27)，定理1得證。

4 實(shí)驗(yàn)仿真

4.1 參數(shù)設(shè)置

本文基于真實(shí)負(fù)載、氣候、電力價格等數(shù)據(jù)，模擬一個常見的互聯(lián)網(wǎng)云數(shù)據(jù)中心。仿真實(shí)驗(yàn)中每個時隙t長度為10分鐘，共模擬為4 464個時隙(31天)，相關(guān)參數(shù)設(shè)置如下：

1)綠色能源數(shù)據(jù)。從美國國家可再生能源實(shí)驗(yàn)室(national renewable energy laboratory, NREL)[33]獲取位于亞利桑那大學(xué)測量站從2015年10月1日～2015年10月31日測得的風(fēng)速v(t)和太陽光照輻射強(qiáng)度s(t)的歷史數(shù)據(jù)。對于綠色能源電力供應(yīng)模型，本文采用與文獻(xiàn)[34-35]相同的參數(shù)設(shè)置，假設(shè)太陽能和風(fēng)能的電力轉(zhuǎn)換效率系數(shù)分別為α=20%，β=30%。太陽能發(fā)電面板總面積A=1 000 m2，風(fēng)力渦輪機(jī)轉(zhuǎn)子總面積B=650 m2?？諝饷芏葹棣?1.225 kg/m3。根據(jù)前面描述的風(fēng)力和太陽能發(fā)電模型，可得數(shù)據(jù)中心綠色能源電力供應(yīng)數(shù)據(jù)。開始一周風(fēng)能和太陽能發(fā)電量如圖2a所示。

2)動態(tài)電力價格數(shù)據(jù)。從紐約獨(dú)立系統(tǒng)調(diào)度機(jī)構(gòu)(new york independent system operator, NYISO)[36]獲取該地區(qū)相應(yīng)時間的實(shí)時分區(qū)邊際電價(locational marginal price, LMP)作為褐色能源電力價格Pb(t)，并將實(shí)時電力價格縮放到1個時隙時間。類似文獻(xiàn)[21]，本文假設(shè)風(fēng)能和太陽能電力價格分別為價美分。開始一周風(fēng)能和太陽能電力價格變化如圖2b所示。

3)負(fù)載數(shù)據(jù)。本文同樣選取從2015年10月1日開始的Wiki Dump[37]訪問流量作為數(shù)據(jù)中心負(fù)載樣本。延遲容忍負(fù)載占總負(fù)載比例為隨機(jī)數(shù)γ，假設(shè)γ服從0.2～0.4的均勻分布，即開始一周負(fù)載流量如圖2c所示。

4)數(shù)據(jù)中心參數(shù)設(shè)置。假設(shè)該數(shù)據(jù)中心擁有服務(wù)器總量M=2 000，服務(wù)器功率為230 W，數(shù)據(jù)中心PUE=1.2。假設(shè)響應(yīng)式負(fù)載平均響應(yīng)時間限制dmax=0.1 s，服務(wù)速率μ1=20，延遲容忍負(fù)載服務(wù)速率

圖2 實(shí)驗(yàn)基本參數(shù)

4.2 基準(zhǔn)參數(shù)

本文使用以下算法作為數(shù)據(jù)中心能源成本和碳排放的基準(zhǔn)算法：1)最小化數(shù)據(jù)中心能源成本Min-Cost算法；2)最小化碳排放Max-Green算法。其中Min-Cost算法假設(shè)只使用價格最低的褐色能源，沒有采用綠色能源；Max-Green則優(yōu)先采用碳排放率低的綠色能源，在能源不足時才使用褐色能源。Min-Cost算法和Max-Green算法獲得數(shù)據(jù)中心平均能源成本和平均碳排放邊界值如表2所示。

表2 數(shù)據(jù)中心平均能源成本和平均碳排放邊界值

4.3 結(jié)果討論

1)控制參數(shù)V的影響

假設(shè)長期碳排放限制為H=60 kg。數(shù)據(jù)中心平均能源成本值C(t)隨著時隙t的變化曲線如圖3所示。由圖3可見，平均能源成本C(t)在開始階段處于不穩(wěn)定狀態(tài)，而隨著時隙增加，C(t)逐漸變得平穩(wěn)，說明本文算法可使平均成本逐漸趨于平穩(wěn)。另外，在圖3中，當(dāng)控制參數(shù)V增大時，數(shù)據(jù)中心平均成本將越小，與定理1相符合。

圖3 V和平均成本關(guān)系

圖4 V和能源使用比例關(guān)系

本文還分析了不同控制參數(shù)V下，數(shù)據(jù)中心各種能源的比例變化情況，如圖4所示，其中碳排放約束H=55 kg。由圖4可見，當(dāng)V增大時，褐色能源的使用比例逐漸增加，而太陽能使用比例則逐漸減少。原因在于V增加將會使式(16)中成本值優(yōu)化比重增加，意味著更大程度降低成本，從而促使選擇價格更低的能源。同時，風(fēng)能使用比例一直高于太陽能，原因在于風(fēng)能比太陽能擁有具有更低的碳排放速率和價格，因而會被優(yōu)先考慮。由此可知，如果不考慮風(fēng)能和太陽能的部署因素，僅從價格和碳排放因素上看，風(fēng)能將具有更好的競爭力。

2)碳排放約束對能源成本的影響

當(dāng)碳排放約束分別50 kg，60 kg，70 kg，80 kg時，碳排放約束和能源成本關(guān)系如圖5所示。由圖5可見，隨著平均碳排放約束的增大，算法將獲得更低的成本，表明當(dāng)放松碳排放約束時，數(shù)據(jù)中心運(yùn)營成本將更低，與現(xiàn)實(shí)相符。但成本降低意味著溫室氣體排放增加，對氣候環(huán)境影響愈加嚴(yán)重。

另外，不同碳排放約束下各種能源的使用比例如圖6所示，其中V= 30 000。由圖6可見，隨著碳排放約束增加，綠色能源使用比例逐漸減少，其中當(dāng)碳排放約束為80 kg時，太陽能使用量已經(jīng)接近為0。原因在于隨著碳排放約束放松，算法將更多從價格上考慮能源選擇，因此會優(yōu)先選擇低價的褐色能源、風(fēng)能，而由于太陽能價格最高，所以用量最低。當(dāng)碳排放約束為85 kg時，已經(jīng)接近碳排放基準(zhǔn)上界89.05 kg，說明此時碳排放對成本影響已經(jīng)非常低。

圖6 碳排放約束和能源使用比例關(guān)系

3)與相關(guān)算法比較

本文算法與Max-Green算法的比較如圖7所示，此時碳排放約束H=50 kg，控制參數(shù)V= 10 000。如前所述，Max-Green算法主要思想是實(shí)現(xiàn)數(shù)據(jù)中心最大綠色化[38]，其獲得的碳排放約束下界為46.73 kg。在圖7中，本文算法獲得平均成本值為5.84，而Max-Green算法獲得成本值為6.89?？梢姡谔寂欧偶s束減少了6.8%的情況下，本文CACM算法可節(jié)省約13.8%的能耗成本，性能良好。同時本文算法可以根據(jù)不同碳排放約束獲得其最優(yōu)成本值，比Max-Green更為靈活。

本文算法與3.1節(jié)的離線最優(yōu)算法比較如圖8所示，此時碳排放約束H=70 kg。由圖8可見，隨著控制參數(shù)V的增加，本文算法獲得成本值會逐漸逼近離線最優(yōu)成本，表示通過調(diào)節(jié)控制參數(shù)V，本文算法可以達(dá)到離線最優(yōu)解。

圖7 本文算法與Max-Green算法對比

圖8 本文算法和離線最優(yōu)算法對比

5 結(jié)束語

本文針對滿足不同類型負(fù)載的SLA和長期碳排放約束下，優(yōu)化數(shù)據(jù)中心的能源成本問題，提出了一個碳感知的在線控制CACM算法。該算法不需要預(yù)測未來信息，僅靠當(dāng)前系統(tǒng)狀態(tài)信息作出決策，并可獲得接近離線最優(yōu)解的近似解。通過基于真實(shí)數(shù)據(jù)的大量仿真實(shí)驗(yàn)驗(yàn)證了本文的CACM算法，結(jié)果表明CACM算法具有良好的性能，可以獲得更優(yōu)的能源成本。下一步工作計(jì)劃將該算法推廣到跨地域云數(shù)據(jù)中心能源成本優(yōu)化研究，以及考慮利用能源存儲的方式來降低數(shù)據(jù)中心的成本。