楊蘇影，陳世平

（上海理工大學(xué)，光電信息與計算機工程學(xué)院，上海　200093）

0　引言

云計算是當(dāng)前科技領(lǐng)域最熱的研究，是一種商業(yè)服務(wù)模式和計算模型。隨著用戶需求的擴大，云計算規(guī)模的增長，數(shù)據(jù)中心所消耗的電能也隨之劇增。根據(jù)國際數(shù)據(jù)信息公司的研究，全球共有超過300萬個數(shù)據(jù)中心，每小時的總耗電量已經(jīng)超過3000萬千瓦。而數(shù)據(jù)中心每年產(chǎn)生的能耗更是成倍的增長。因此，數(shù)據(jù)中心能耗問題是當(dāng)前甚至以后云計算領(lǐng)域的重要課題。

目前，針對數(shù)據(jù)中心的能耗問題，許多研究者對能耗優(yōu)化的策略進行了討論。文獻[1]針對資源虛擬化環(huán)境中的混合型負載調(diào)度問題，提出了一種基于能耗比例模型的虛擬機調(diào)度算法。文獻[2]利用約束滿足問題對異構(gòu)云數(shù)據(jù)中心的能耗優(yōu)化資源調(diào)度問題建模，在此基礎(chǔ)上提出了能耗優(yōu)化的資源分配算法。文獻[3]公開了一種云計算能耗關(guān)鍵的三維度虛擬資源調(diào)度方法，從CPU、內(nèi)存以及網(wǎng)絡(luò)帶寬三個維度充分考慮了如何有效地降低數(shù)據(jù)中心的能耗。文獻[4]則通過建立系統(tǒng)模型，針對任務(wù)集的物理資源分配問題，提出一種節(jié)能調(diào)度算法。

以上研究方案對降低數(shù)據(jù)中心能耗都有一定的改善，但都是基于傳統(tǒng)數(shù)據(jù)中心資源分配方式的，存在許多局限性。傳統(tǒng)的數(shù)據(jù)中心以虛擬機為中心，資源直接在個體的虛擬機與個體的物理機之間進行映射，非常復(fù)雜的物理機之間進行映射，非常復(fù)雜。在這種情況下考慮降低數(shù)據(jù)中心能耗也更為困難，分散的資源難以集中，工作量成倍增長，能耗降低的效果也受到限制。因此，針對當(dāng)下的能耗問題，本文將在一種全新的資源管理框架即包簇框架下進行研究，提出一個種基于包簇框架的資源分配策略。包簇框架可以大大簡化映射的復(fù)雜性，更易于實現(xiàn)資源的集中管理，有利于提高資源利用率，同時，采用包簇框架下的平衡蟻群算法來進行資源分配，盡可能將包集中分配在簇上，達到降低數(shù)據(jù)中心能耗的目的。最后通過仿真實驗，驗證了該算法的有效性，并通過對比實驗驗證了該算法的先進性。

1　包簇框架

1.1　包簇介紹

通過遞歸的方式來定義抽象的，多層次的包和簇。其中，包可以看做是一組參與資源共享的虛擬機，若干這樣的包可以被抽象成為級別更高的包，最終，這些虛擬機和包就構(gòu)成了具有明顯層次的結(jié)構(gòu)。在實際的云計算應(yīng)用中，包的層次架構(gòu)形式將由具體的用戶需求來確定，比如一個企業(yè)內(nèi)部可以根據(jù)公司分布以及部門劃分來確定該企業(yè)的包的架構(gòu)，如圖1就為某一企業(yè)的包拓撲結(jié)構(gòu)。

圖1　某企業(yè)的包拓撲結(jié)構(gòu)Fig.1　The packet topology of one enterprise

與之相對應(yīng)的簇也是相似的，我們將“簇”定義為數(shù)據(jù)中心拓撲結(jié)構(gòu)中位置相近的服務(wù)器或者更低級別的簇的集合[5]。數(shù)據(jù)中心資源也可以組成由服務(wù)器、簇、簇中簇構(gòu)成的多級別的層次架構(gòu)。如圖2是以肥胖樹形式存在的傳統(tǒng)數(shù)據(jù)中心的服務(wù)器拓撲結(jié)構(gòu)；如圖3則為采用簇層次結(jié)構(gòu)的簡化后的簇拓撲結(jié)構(gòu)，也可以進一步化簡，這樣一個問題規(guī)模巨大的分配問題，就被簡化為多個小問題。

圖2　傳統(tǒng)數(shù)據(jù)中心的服務(wù)器拓撲結(jié)構(gòu)Fig.2　The server topology of a traditional data center

圖3　簡化的簇拓撲結(jié)構(gòu)Fig.3　Simplified cluster topology

1.2　包簇框架下的資源映射問題

在包含數(shù)以千萬計機器的數(shù)據(jù)中心中，采用傳統(tǒng)的分配方式進行資源分配具有極高的計算復(fù)雜性。而與傳統(tǒng)的方式相比，包簇框架下的資源映射問題就簡單的多。包簇采用“樹”的描述方式，層次劃分清晰?？蓪⒋罅侩x散的機器的映射轉(zhuǎn)化為遞歸的層次映射。包簇框架的采用就將虛擬機與服務(wù)器之間的映射問題轉(zhuǎn)換成了另一種更小型的包和簇之間的映射問題。通過上述方法，就對指數(shù)級復(fù)雜讀的問題進行了分解，得到了一系列的小問題，最后，將這些小問題各個擊破。

2　基于包簇框架的能耗模型

2.1　包簇模型

設(shè)簇層次結(jié)構(gòu)中任意一個簇為ρ，該簇具有N個子簇p，則1≤p≤N。并設(shè)已分配給ρ的包由M個子包v組成，則1≤v≤M。這樣問題就轉(zhuǎn)化為了如何最優(yōu)地將這M個子包分配給ρ中的N個子簇。

實際上，用戶需求以及空閑的資源都是實時變化的。若時間可以被劃分成若干離散的時間段，則對每一個子包v而言，在時間t對資源i的需求總量表示為 Rv,i[t]。資源分配將通過矩陣變量x表示：x : = ( xv,p[t])。每個 xv,p[t]實際上是二進制0-1變量：當(dāng)且僅當(dāng)在時間t時包v被分配給簇p，則 xv,p[t] = 1，否則 xv,p[t] = 0。對每一個子簇p而言，在時間t時資源i的可用總量記為 Ap,i[t]。

在進行資源分配時，需要考慮到任意一個簇p的資源用量不能超過資源總量。所以有了以下約束條件，見公式1：

2.2　基于包簇的能耗模型

服務(wù)器能耗中，CPU占據(jù)了絕大多數(shù)的部分，文獻[6-7]驗證了 CPU使用率與能耗呈近似線性關(guān)系，所以本文利用CPU使用率來建立近似的能耗模型，見公式2。

其中，k表示在服務(wù)器沒有負載時的功耗占服務(wù)器滿負載時的功率比例，u代表CPU利用率，maxP代表CPU在使用率為100%時的功率。即公式2是單個服務(wù)器在CPU利用率u下的功率。

而服務(wù)器消耗的總能量一般用服務(wù)器的功率和時間之積表示，則公式3即為單個服務(wù)器消耗的能量。

而在包簇框架中，不僅需要考慮單個虛擬機消耗的能量，還需要考慮到簇消耗的能量，而簇是由簇與服務(wù)器所組成的，因此在包簇框架下單個簇的消耗的能量如公式4。

其中n為簇p的子簇數(shù)量。當(dāng)簇p為底層簇時，只需計算其下服務(wù)器消耗的總和即可；而當(dāng)p為上層簇時，計算該簇的能耗就需要計算該簇所有子簇的能耗之和。同樣，其子簇能耗也能夠通過公式4計算出來，從而計算出每個簇的能耗大小。進一步地，可以計算出在包簇框架下的數(shù)據(jù)中心的總能耗，見公式5：

由于CPU利用率在不同的時間點有所不同，可以使用積分表示某個時間段內(nèi)的數(shù)據(jù)中心的能耗，見公式6和公式7。

所以最終目標(biāo)函數(shù)如下：

3　基于包簇框架的資源分配問題

3.1　資源分配問題與蟻群算法

資源分配問題可以類比為裝箱問題[8-10]，將每個簇p看作是箱子，包v看作是物品。本文將采用裝箱問題的解決思路來處理該資源分配問題。

蟻群算法[11-12]的特點是分布計算、信息正反饋以及啟發(fā)式搜索[13]，所以該算法成為了裝箱問題的經(jīng)典解決算法?；谝陨咸卣?，與其它算法相比，在解決裝箱問題時能更有效地收斂到最優(yōu)解，因此本文將選取蟻群算法處理該資源分配問題。該算法的基本原理為：蟻群在尋找食物時會在其經(jīng)過的路徑上釋放信息素，螞蟻會被吸引著往信息素濃度較高的路徑行走，并且會在路上留下信息素。這樣就形成一種正反饋的機制，使蟻群總能在一段時間后找到最短路徑。

3.2　改進的蟻群算法

3.2.1平衡蟻群算法

蟻群算法也存在一些問題，如蟻群迷失和早熟問題，本文將針對這兩個問題對蟻群算法進行改進，稱為平衡蟻群算法。

1）為使螞蟻能夠在算法的初始階段更快的收斂到最優(yōu)解，我們將在初始時為路徑上的信息素設(shè)置初始值。

2）為信息素濃度設(shè)置最高與最低閾值，使每條路徑上的信息素濃度相對平衡，這樣的設(shè)定可以給予不同的路徑更多地成為最優(yōu)解的機會，從而避免早熟和迷失問題。

因此，將改進后的蟻群算法稱為平衡蟻群算法。

3.2.2包簇框架下的平衡蟻群算法

蟻群算法需要執(zhí)行多次從而得到最優(yōu)解。在包簇框架下，由于包簇并不是單一的一組節(jié)點，而是具有層次的樹形結(jié)構(gòu)體，蟻群算法需要考慮到整個簇層次結(jié)構(gòu)的每一層。因此，在此說明基于包簇框架下蟻群尋找“食物”的規(guī)則。

3、保證國家能源安全。傳統(tǒng)的礦物質(zhì)能源是當(dāng)今社會發(fā)展和進步的發(fā)動機，目前全球總能耗的75%來自煤炭、石油、天然氣等。但是，礦物能源是有限的。預(yù)計2020年能源消費量將達到30億噸標(biāo)準(zhǔn)煤以上，到2050年可能要達到50億噸標(biāo)準(zhǔn)煤以上。因此，開發(fā)利用生物質(zhì)能已成為解決我國能源問題的戰(zhàn)略選擇。

（1）包簇框架下的每一層都有其對應(yīng)的解，而每一層的解又取決于上一層包簇的解；

（2）不同層次的包簇不能夠產(chǎn)生映射關(guān)系；

（3）同一層次的包簇只有在父包和父簇存在映射關(guān)系的前提下，屬于該父包的一組包才能夠分配到屬于該父簇的一組簇上去。

（4）默認最頂層的簇與最頂層的包存在映射關(guān)系，因為最頂層的包簇是1對1的關(guān)系；

（5）除頂層外的余下每一層，在滿足2，3映射條件的前提下，都將遞歸的通過蟻群算法得到每一層的最優(yōu)解；

（6）蟻群算法在尋找最優(yōu)的映射關(guān)系時，必須保證該簇有足夠的資源滿足該包的需求。

3.3　包簇框架下平衡蟻群算法的資源分配策略

3.3.1適宜度函數(shù)

螞蟻在覓食過程中，信息素對于獲得最優(yōu)解有著至關(guān)重要的作用。而裝箱問題的解可以通過適宜度函數(shù)的大小來評判好壞，信息素的變化量與適宜度函數(shù)成正比，即適宜度函數(shù)越大，說明該解的效果越好。

在 3.2節(jié)中我們建立了能耗模型，本文目標(biāo)是為了降低系統(tǒng)能耗，采用能耗的倒數(shù)來定義適宜度函數(shù)，如下：

設(shè)蟻群中螞蟻的數(shù)量為m，在簇上隨機放置每只螞蟻的初始位置。每個螞蟻k需要根據(jù)概率轉(zhuǎn)移函數(shù)從allowedk集合中搜索下一個包v，概率轉(zhuǎn)移見公式9：

式中， a llowedk即為螞蟻k可允許選擇的包集合，每一次迭代過程中，該集合都會減少，直至allowedk為空，本次迭代結(jié)束；ηv,p為啟發(fā)信息函數(shù)，α為信息素啟發(fā)因子，β為能見度啟發(fā)因子，這兩個參數(shù)反映了螞蟻在選擇包的過程中積累的信息素和啟發(fā)信息對螞蟻選擇路徑的重要程度； τv,p(t)為在t時間包v和簇p路徑上的信息素。

在初始時刻，各個信息素的強度均相等，為信息素設(shè)置一個初始值τv,p( 0)= C （C為常數(shù)）。信息素會因為螞蟻的選擇而增加，也會隨著時間而揮發(fā)；當(dāng)螞蟻完成對包的搜索過程或者是完成一次迭代后，要對信息素進行更新操作，更新規(guī)則見公式10和公式11。

其中，信息素揮發(fā)系數(shù)設(shè)為ρ，包v和簇p路徑上的信息素增量可以表示為 Δ τv,p(t)。f為信息素增量函數(shù)，即適宜度函數(shù)，見公式 8。而為避免蟻群早熟問題，將為信息素設(shè)定上下限，將信息素τv,p設(shè)定在一個區(qū)間 [τmin, τmax]中，τmin為信息素τv,p的下限，τmax為上限。另外，設(shè)包集合為Setv，簇集合為 S etp，簇p在t時間時，其上i資源的剩余資源容量為 R estp,i[t]。a l lowedk,p為螞蟻k在其當(dāng)前所在簇p上可允許選擇的包集；當(dāng)螞蟻完成一次選擇時，需要更新 Rv,i[t]，見公式13。

并設(shè)iterator為當(dāng)前累計迭代次數(shù)，cycle為循環(huán)次數(shù)，則算法結(jié)束條件為iteratorcycle＞。

3.3.3算法步驟

某一層中一次包簇映射過程如下，其中包集合與簇集合的關(guān)系需滿足4.3.2中的規(guī)則3。

（1）初始化 S etv及每個包對應(yīng)的 Rv,i[t]， S etp及每個簇對應(yīng)的 Rp,i[t]；將包集合里的所有包加入allowedk中；

（2）設(shè)置螞蟻數(shù)量m，信息素啟發(fā)因子α，能見度啟發(fā)因子β，信息素揮發(fā)系數(shù)ρ；

（3） 將每只螞蟻隨機放置在簇上，作為初始位置，螞蟻準(zhǔn)備出發(fā)尋找食物即包；

（4）如果 a llowedk為空，則轉(zhuǎn)步驟 6；如果allowedk不為空，則根據(jù)公式10構(gòu)建 a llowedk，并轉(zhuǎn)到下一步；

（5）若 a llowedk,p為空，將螞蟻轉(zhuǎn)移到下一個簇上；若 a llowedk,p不為空，螞蟻根據(jù)概率轉(zhuǎn)移函數(shù)在allowedk,p中選取包v放置進當(dāng)前簇p中，更新p的剩余容量，同時更新 a llowedk，將包v在 a llowedk中刪除；轉(zhuǎn)到步驟4；

（6） 完成本次迭代，判斷是否滿足結(jié)束條件，若不滿足，則初始化信息素，轉(zhuǎn)1繼續(xù)下一次迭代。

在包簇框架下，需要進行多次遞歸這一過程。由于每一層次劃分清晰，在每一層次中可以并行的實施包簇框架下的蟻群算法，這樣，在每一次迭代中只需要執(zhí)行K-1次即可，其中K為包簇的層數(shù)。

4　仿真實驗

4.1　仿真環(huán)境

為了驗證本文算法在包簇框架下對于能耗問題的有效性，在Cloudsim[14]上進行仿真實驗。Cloudsim提供了一個通用的、可擴展的仿真框架，使新興的云計算基礎(chǔ)設(shè)施和應(yīng)用服務(wù)無縫建模、仿真和實驗。以下為仿真實驗相關(guān)環(huán)境。

考慮到真實應(yīng)用中，企業(yè)一般根據(jù)分部與部門劃分為三層，因此本實驗假設(shè)包簇架構(gòu)為三層，并分別設(shè)計二級包40個，三級包500個，二級簇80個，三級簇 700個，設(shè)每個二級簇下的子簇數(shù)量[5,100]間隨機選取，以提高實驗的可靠性。

4.2　算法調(diào)參

本文提出的資源分配算法基于蟻群算法，其參數(shù)的選取對于整個算法的性能有一定的影響。因此為提升本文算法的有效性與準(zhǔn)確性，首先對包簇框架下平衡蟻群算法的幾個關(guān)鍵參數(shù)進行調(diào)試，包括信息素濃度啟發(fā)因子α與信息素揮發(fā)系數(shù)ρ，這兩個參數(shù)都與信息素相關(guān)，對于依靠信息素得到最優(yōu)解的蟻群算法來說至關(guān)重要。

在分析某個特定參數(shù)時，固定其它參數(shù)的取值，從而觀察分析出被調(diào)整參數(shù)取值變化對于目標(biāo)函數(shù)結(jié)果的影響，進而確定最優(yōu)參數(shù)值。本文以能耗為目標(biāo)，即以公式7值最優(yōu)為目標(biāo)進行考察。設(shè)置蟻群算法其他的參數(shù)值：5β=，15m=，10C=，cycle=20。并設(shè)α初始值為1，ρ初始值為0.1。經(jīng)過多次實驗，結(jié)果如圖4和圖5。

圖4　α取值對能耗的影響Fig.4　The effect on energy consumption of α

圖5　ρ取值對能耗的影響Fig.5　The effect on energy consumption of ρ

由圖4可以看出，α=1時能耗并未達到最低值。通過觀察看出隨著α值的增大，能耗也逐漸降低，在α=2時達到最低值，隨后能耗曲線又開始升高。因此信息素濃度啟發(fā)因子α的最優(yōu)值為 2。同樣通過圖5可以看出ρ得最優(yōu)值為0.3。所以最終蟻群算法參數(shù)取值如表1。

4.3　不同算法的實驗結(jié)果對比與分析

為更清晰地描述實驗結(jié)果，本文選取文獻[5]中的基于包簇框架的遺傳算法（IMOPC），以及文獻[15]中在傳統(tǒng)數(shù)據(jù)中心下的遺傳算法（IGA）作為本文算法的對比實驗。在蟻群算法循環(huán)20次后得到實驗結(jié)果如圖6和圖7所示。

表1　參數(shù)設(shè)置Tab.1　Parameter Settings

圖6　CPU使用率隨時間變化曲線圖Fig.6　The graph of CPU utilization over time

圖7　能耗隨時間變化曲線圖Fig.7　Energy consumption curve over time

圖6為三種算法下CPU利用率隨時間變化的對比圖?？梢悦黠@看出，基于包簇框架的 BAAPC與IMOPC算法的CPU利用率遠超于IGA算法，說明包簇框架能有效實現(xiàn)資源共享，提高利用率。而同為包簇框架的BAAPC與IMOPC相比，BAAPC在CPU利用率上則更有優(yōu)勢，說明本文的BAAPC更能減少簇的使用個數(shù)，集中資源，提高資源的利用率。

圖 7為三種算法下數(shù)據(jù)中心的能耗大小對比圖。首先可以看出能耗與CPU利用率是呈正比的，隨著時間的變化兩者都在逐漸增加。其次可以看出CPU利用率最高的BAAPC算法在能耗方面的表現(xiàn)也是最好的，說明本文BAAPC能有效提高利用率，減少簇的個數(shù)，從而有效降低能耗，達到綠色節(jié)能的目的。

5　總結(jié)

本文就當(dāng)前數(shù)據(jù)中心能耗嚴(yán)峻問題提出了一種全新的資源管理框——架包簇框架的資源分配方案。首先針對能耗問題建立了基于包簇框架的能耗模型，然后對于該資源分配問題進行分析，選取蟻群算法作為本文算法，并評估了蟻群算法的優(yōu)劣性，針對性地對蟻群算法進行了改進，得到包簇框架下的平衡蟻群算法，然后基于該算法實現(xiàn)了包資源分配問題。最后通過實驗證明，該算法能有效提高資源利用率，對于降低數(shù)據(jù)中心能耗具有有效性。