黃曉冬，端木帥飛，畢 敬+，苑海濤

(1.海軍航空大學，山東 煙臺 264001；2.北京工業(yè)大學 信息學部軟件學院，北京 100124；3.北京航空航天大學 自動化科學與電氣工程學院，北京 100191)

0 引言

隨著云計算技術的快速發(fā)展，工業(yè)界已將云計算視為提升經濟發(fā)展的新途徑[1-3]，云計算正在成為許多組織和數(shù)據中心的主導技術，這些組織和數(shù)據中心在很大程度上適應了私有和混合云計算模式[4]。隨著基礎設施即服務(Infrastructure as a Service, IaaS)和軟件即服務(Software as a Service, SaaS)的不斷商業(yè)化，目前云計算服務的定價多采用按需付費的定價策略[5]。與此同時，越來越多的互聯(lián)網公司將基礎設施和應用程序放在云端執(zhí)行和訪問，用戶按需付費。例如，IBM、微軟、谷歌和亞馬遜等互聯(lián)網企業(yè)已經為用戶提供了不同的云服務[6]。而私有云服務提供商的目標是以最低的成本按需為用戶提供服務，并保證服務質量(Quality of Service, QoS)。因此，最小化私有云服務提供商的成本是一項極具挑戰(zhàn)的工作[7]。

在云+物聯(lián)網時代，云數(shù)據中心對能源需求的日益增長使能源儲備逐漸減少，能耗問題成為制約私有云提供商發(fā)展的關鍵[8]。云數(shù)據中心消耗能源的主要是服務器、存儲設備、網絡設備和冷卻IT負載所需的電力設備，其在運行成本較高的同時排放出更多的二氧化碳[9]，由此引發(fā)云服務提供商的關注，嘗試開發(fā)和利用新綠色能源(如太陽能和風能)成為降低云服務提供商成本的一個重要途徑[10]。

混合云中應用復雜、類型多樣、任務量大，每個應用通常有嚴格的服務延遲要求，使得私有云和公有云中的許多因素隨時間不斷變化[11]，如收益、電價、太陽能和風能，以及公有云虛擬機或容器的運行價格等，最小化任務的執(zhí)行成本非常困難。另外，由于現(xiàn)實場景中存在多個公有云數(shù)據中心，每個公有云的資源使用價格不同且所提供的虛擬機類型多樣，導致私有云的能耗成本很難準確估算。綜上，在混合云中最小化任務的執(zhí)行成本并滿足其用戶的響應時間約束，是一項非常艱巨的任務。本文提出基于成本最小化算法(Cost Minimization Algorithm, CMA)的任務調度方法，從而最小化私有云的總成本。進一步，為了確保云數(shù)據中心任務的服務延遲要求，本文給出基于遺傳學習機制的混合粒子群優(yōu)化(Genetic Learning Particle Swarm Optimization, GLPSO)算法，該算法結合了粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法和遺傳算法(Genetic Algorithm, GA)。PSO屬于群體智能的范疇，其中的社會學習機制有助于提高集體學習的效率，因此被廣泛應用于尋找各種優(yōu)化問題的全局極小值[12]；GA是基于自然選擇和自然遺傳機制的隨機搜索技術，其中的搜索策略和遺傳算子使其具有強大的全局搜索能力[13]。因此，將PSO和GA結合有助于找到問題的最優(yōu)解，大幅降低私有云服務提供商的成本。

綜上所述，本文工作主要有3方面貢獻，具體如下：

(1)建立了一個混合云中的任務調度模型，該模型能夠嚴格滿足任務的服務延遲約束要求，并將任務智能地調度到私有云或公有云中執(zhí)行。

(2)給出了私有云服務提供商成本最小化問題的表達式，通過罰函數(shù)進一步將其轉化為無約束的混合整數(shù)非線性規(guī)劃問題。

(3)提出GLPSO算法求解該問題，得到每個時間間隔的最終解，并根據每個解給出一種新的CMA，該算法在能耗上優(yōu)先使用綠色能源，相比常規(guī)優(yōu)化算法可以大幅降低私有云服務提供商的成本。

1 相關工作

1.1 數(shù)據中心資源分配

WANG等[14]基于蟻群算法提出負載均衡技術，通過檢測服務器負載實現(xiàn)了對數(shù)據中心的負載均衡操作；WANG等[15]針對IaaS提出一種智能的動態(tài)資源分配方法，使競價在每一輪拍賣中都具有合理性，從而確定供應商和消費者之間的交易關系，并提出一種基于反向傳播神經網絡的價格預測算法和價格匹配算法的形成機制，可以將不誠實的參與者排除在云市場之外；CHEN[16]提出一種支持突發(fā)和緊急需求的云資源分配方法，能夠及時、優(yōu)化地分配各種資源，以應對緊急的應用資源需求，該方法重建了資源分配的新優(yōu)先級，能夠為緊急的應用請求分配更早的虛擬機資源；WU等[17]提出高效的準入控制和資源調度算法，其目標是允許分析即服務(Analysis as a Service, AaaS)提供商在服務等級協(xié)議保證下交付AaaS，以增加市場份額、聲譽和用戶滿意度，并提高其利潤。以上研究主要針對資源分配問題，并未考慮私有云服務提供商的成本最小化問題，本文則通過將任務智能調度到公有云中執(zhí)行，最小化私有云服務提供商的總成本。

1.2 數(shù)據中心綠色節(jié)能

YEGANEH等[18]針對不同的節(jié)能降耗因素，提出動態(tài)定價算法的容量規(guī)劃，解決了權衡操作成本和服務延遲的問題；FARAHNAKIAN等[19]提出一個分布式系統(tǒng)架構來合并動態(tài)虛擬機，以減少云數(shù)據中心的能耗，同時保持所需的QoS，最后采用一種蟻群系統(tǒng)的在線優(yōu)化元啟發(fā)式算法解決虛擬機合并問題；CHIANG等[20]在性能保證范圍內控制服務速率并優(yōu)化操作成本，同時考慮功耗、系統(tǒng)擁塞和服務器啟動成本，提出一種高效的綠色控制算法，用于解決不同節(jié)能策略下的系統(tǒng)約束優(yōu)化問題。然而，以上研究不能有效利用綠色能源降低能耗，本文設計的模型優(yōu)先使用綠色能源，綠色能源不足時才考慮使用電能，該模型在治理日益突出的環(huán)境污染問題方面具有重要的意義。

1.3 分布式數(shù)據中心能耗優(yōu)化

LI等[21]通過Lyapunov優(yōu)化框架設計了一個在線動態(tài)供應算法，解決了現(xiàn)實世界中沒有公有云租賃價格的先驗信息和用戶請求未來概率未知的問題；XU等[22]提出一種能源感知的資源分配方法——EnReal，同時結合部署在多個云計算平臺的應用，提出一個能耗模型及其相應的能量感知資源分配算法，用于虛擬機調度，從而在跨云平臺甚至云平臺內部以能源感知的方式執(zhí)行科學的工作流；LUO等[23]利用電力價格的空間和時間變化最小化電力市場管制下分布式云數(shù)據中心的能源成本；YAO等[24]提出一種大規(guī)模地理分布式數(shù)據中心的作業(yè)調度和服務器管理的隨機優(yōu)化方法，在處理延遲容忍型工作負載時有效降低了能耗。然而以上研究沒有綜合考慮能量成本、綠色能源和虛擬機資源價格在時間上的多樣性，本文的任務調度方法考慮了私有云電價、綠色能源和公有云價格在時間上的多樣性，并嚴格滿足服務延遲要求，通過將所有到達的任務智能地調度到私有云和公有云中執(zhí)行來最小化私有云服務提供商的成本。

2 混合云中任務調度的體系結構

數(shù)據中心提供商通常擁有私有云和執(zhí)行一些額外任務的公有云，當私有云中資源有限或在公有云的虛擬機中執(zhí)行任務更經濟時，會將一些任務調度到公有云中執(zhí)行。本文提出了混合云中的任務調度架構，如圖1所示。該架構由私有云和公有云兩部分組成。私有云中包含了大量的虛擬資源，如CPU、內存和存儲等，用戶到達的任務首先依次加入一個先進先出(First Come First Served, FCFS)隊列中，架構的主要組件是任務調度器，F(xiàn)CFS隊列的所有信息(如到達任務數(shù)量)會發(fā)送給任務調度器。私有云獲得的電能主要有網格能量(h)、太陽能(s)和風能(w)3種來源，任務調度器會定期收集電網的價格、風速、太陽輻射強度和現(xiàn)場空氣密度，根據收集的信息調度組件執(zhí)行任務調度，其中CMA確保每個任務在服務延遲約束下定期調度任務到私有云或公有云中，并確定每個時間間隔內分別在私有云和公有云中調度執(zhí)行的任務數(shù)量。

3 系統(tǒng)模型和構造成本最小化問題

本文重點是延遲容忍類型應用的任務，包括大規(guī)模數(shù)據分析、科學計算、圖像處理等任務。隨著部署在數(shù)據中心的計算機越來越多，越來越多的云數(shù)據中心支持多核計算并趨向于并行化，本文將每個任務分解為功能相當?shù)男∪蝿?，每個小任務都可以在一個時間間隔內執(zhí)行完畢。另外，所有到達的任務都有嚴格的服務延遲約束(B)，即t時刻到達的任務必須在t～t+B時間間隔內被調度執(zhí)行。為了有效構造模型，本文給出以下假設：

(1)任意t時刻內到達的任務數(shù)量已知。

(2)任務調度器組件可以收集到任意t時刻私有云的電價、公有云的執(zhí)行價格、太陽能和風能的能量、帶寬費用和任務的執(zhí)行時間等信息。

(3)公有云處理任務的能力是無限的，每個時間間隔內任意任務都可以在公有云中被調度執(zhí)行。

3.1 綠色能源模型

(1)

(2)

具體參數(shù)設置如表1所示。

表1 綠色能源計算的相關參數(shù)

3.2 成本最小化問題

為了解模型的功能，現(xiàn)對成本最小化問題中資源、任務、約束等參數(shù)和決定變量進行詳細描述，如表2和表3所示。

表2 問題參數(shù)

續(xù)表2

表3 決策變量參數(shù)

本文工作的最終目標是最小化私有云提供商的成本，該目標函數(shù)定義為P1，包括私有云和公有云成本兩部分，即

Cost=Costprivate+Costpublic。

(3)

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

在任意t時刻，到達的任務會先進入一個FCFS隊列，然后通過任務調度器被分別調度到私有云或公有云中執(zhí)行。令Δt為t時刻累積到達的任務數(shù)量，Dt為t時刻累積調度的任務數(shù)量，即

(4)

私有云中從t～t+m時間內的成本包括執(zhí)行任務消耗的能源成本和帶寬費用兩部分，即

(5)

對于私有云中的能耗，私有云會首先使用綠色能源，以最大程度降低對環(huán)境的污染，當綠色能源不足時，將使用電網的能量。

公有云中在t～t+m時間內的成本包括虛擬機的執(zhí)行價格和耗費的帶寬費用兩部分，即

(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分別為新的增廣函數(shù)和懲罰函數(shù)；σ是一個比較大的整數(shù)，主要表現(xiàn)為對augCost和Penalty的影響。

對于P2問題，每個等式或不等式約束對應的懲罰均被添加到原始目標函數(shù)Cost，其中懲罰函數(shù)

(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問題通常采用典型的元啟發(fā)式算法，如PSO算法和GA，這些算法不需要優(yōu)化問題數(shù)學結構的任何輔助信息，并具有魯棒性和易于實現(xiàn)等特點，然而作為仿生優(yōu)化領域兩個著名分支，兩種算法都有各自的優(yōu)缺點。典型GA由選擇、交叉和突變3個基本算子組成。選擇算子復制高質量的染色體，以提高種群的平均適應度值，也被稱為進化；交叉和突變是生殖操作，能夠為進化中的種群提供質量更高的遺傳物質；PSO算法不使用選擇運算符，而是通過將粒子更新到歷史最佳位置來表示進化，其中粒子的飛行軌跡與遺傳物質的變化相對應。

GA和PSO算法因機制不同導致性能存在差異。標準GA隨機選取兩條染色體，采用交叉操作交換染色體相同位置的基因，使染色體中的一些基因通過突變獲得隨機變異，因此GA的復制過程在一定程度上是全方位的。PSO算法是一種基于種群的優(yōu)化算法，具有實現(xiàn)簡單、收斂速度快等特點，在標準PSO算法中，粒子由粒子之前的最佳位置(pbests)和群體發(fā)現(xiàn)的全局最佳位置(gbest)引導，搜索比GA更有方向性。因此，本文期望GA具有比PSO算法更好的尋優(yōu)能力，PSO算法具有比GA更快的收斂速度。

為了進一步提高PSO算法性能，本文提出GLPSO算法，如圖2所示。在GLPSO算法中，GA和PSO算法以級聯(lián)方式雜交，該算法的主循環(huán)由兩個級聯(lián)層組成，一個通過GA生成范例，一個按照標準的PSO算法進行粒子更新。該方法使PSO算法中的粒子不再簡單地用gbest和pbests，而是用GA構造的樣本來指導。因此，GA和PSO算法以一種高內聚的方式進行雜交，

在GLPSO算法中，通過學習GA構建樣本，使粒子搜索更加多樣化，可以避免PSO算法過早收斂，而且由于GA選擇算子的作用，使幸存的樣本質量較高，能夠對粒子進行有效引導，從而提高PSO算法的搜索效率。反之，粒子的搜索經驗(pbests和gbest)將更優(yōu)秀的遺傳物質傳播回GA，幫助GA復制改進的樣本。因此，在該級聯(lián)結構中，PSO算法與GA之間的相互作用效果明顯，而且在優(yōu)化過程中不斷迭代又進一步增強了PSO算法與GA之間的相互作用。

5性能評估

5.1 實驗環(huán)境及參數(shù)設置

為了評估所提CMA的性能，本文采用真實云計算中心的負載，如圖3所示。圖中數(shù)據集為2011年5月某天的1 440 min內，谷歌數(shù)據中心集群中3種類型任務到達的數(shù)量，其中采集時間間隔為5 min，共產生288個數(shù)據點。本文采用類型3的任務來評估所提算法的性能。

CMA的不同參數(shù)設置如下：

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

5.2 實驗結果

實驗假設公有云數(shù)據中心的處理能力是無限的，其中圖4、圖5分別為每個時間間隔內私有云數(shù)據中心和公有云數(shù)據中心調度的任務數(shù)量。由圖5可知，每個時間間隔內只有一個公有云數(shù)據中心在運行使用，其他公有云數(shù)據中心接受的任務數(shù)量為0。每個時間間隔內私有云提供商的成本和罰函數(shù)的懲罰值如圖6所示，可見罰函數(shù)的懲罰值在每個時間間隔內接近于0。因此，本文提出的混合云任務調度在每個時間間隔內都能找到有效的解決方案，而且能夠降低私有云服務提供商的成本。圖7所示為每個時間間隔內的累積到達任務和累積調度任務，實驗中設置服務延遲為3個時間間隔，可見到達的任務在服務延遲要求內可以被有效地調度。因此，CMA可以滿足任務服務延遲的要求。

私有云和公有云的累積調度任務數(shù)量如圖8所示?？梢?，私有云中調度的任務數(shù)量遠大于任意一個公有云調度的任務數(shù)量。私有云提供商總是以最經濟的方式在其中或公有云中智能地調度到達的任務，以保證成本最小化。當其將任務調度給公有云時，需要向公有云支付費用，公有云提供商同樣會選擇成本最小的公有云來執(zhí)行到達的任務。每個到達的任務都盡可能在私有云中執(zhí)行，有兩種情況可能將任務調度到公有云中：①私有云的能力有限，不足以調度到達的任務；②公有云執(zhí)行任務的成本足夠低。

5.3 對比實驗結果

為了驗證算法的有效性，本文將所提GLPSO算法與兩種典型算法——模擬退火粒子群優(yōu)化(Simulated Annealing Particle Swarm Optimization, SAPSO)算法[10]和GA[11]進行對比。其中，SAPSO算法適用于求解局部最優(yōu)解，算法中的每個粒子均基于模擬退火(Simulated Annealing, SA)算法中的Metropolis準則來更新自己的位置。在每個迭代中，比較當前解決方案和新生成解決方案的目標函數(shù)值，改進解被直接接受，同時接受一些較差的解，以擺脫局部最優(yōu)而獲得全局最優(yōu)。

圖9所示為GLPSO算法和兩種基線算法的成本對比。明顯可見，在大部分時間間隔內，結合了PSO算法和GA的GLPSO算法在求成本最小化的問題上表現(xiàn)良好，在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表現(xiàn)最差，該算法在收斂過程中一直在震蕩，始終不能收斂到最優(yōu)解。

圖11和圖12所示分別為GLPSO算法和兩種基線算法的CPU與內存利用率的對比?？芍?，GLPSO算法的CPU和內存利用率比較穩(wěn)定，在0.35附近波動，而且在81%時間間隔內高于SAPSO算法和GA。

6 結束語

越來越多的互聯(lián)網公司將應用程序部署到云數(shù)據中心，任務的不斷增長顯著增加了私有云服務提供商的能耗成本，現(xiàn)階段的云數(shù)據中心普遍采用混合云方案處理到達的任務，然而混合云中的私有云電網價格、太陽輻射強度、風速和公有云虛擬機執(zhí)行價格的變化對混合云中的任務調度帶來了挑戰(zhàn)。為了盡可能減少私有云服務提供商的成本并滿足任務的服務延遲約束，本文提出一個成本最小化模型來調度到達的任務，該模型可以根據私有云成本和公有云中多因素的時間變化特性，智能地將所有任務調度到私有云或公有云中執(zhí)行。CMA采用混合啟發(fā)式優(yōu)化算法——GLPSO算法最小化成本，該混合算法采用遺傳算子，即交叉、變異和選擇構造樣本，其中交叉利用粒子的歷史信息，包括之前的最佳位置和群體的全局最佳位置產生高質量的后代，變異則通過向后代注入多樣化信息來加強全局搜索?；谡鎸崝?shù)據的仿真實驗證明，所提算法在滿足服務延遲約束的同時，能夠顯著降低私有云服務提供商的運營成本。未來擬將該模型應用到實際的云數(shù)據中心，進一步改進和完善任務調度的性能與執(zhí)行效率。