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

楊蘇影，陳世平

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

0　引言

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

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

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

1　包簇框架

1.1　包簇介紹

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

圖1　某企業(yè)的包拓?fù)浣Y(jié)構(gòu)Fig.1　The packet topology of one enterprise

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

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

圖3　簡(jiǎn)化的簇拓?fù)浣Y(jié)構(gòu)Fig.3　Simplified cluster topology

1.2　包簇框架下的資源映射問(wèn)題

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

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

2.1　包簇模型

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

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

在進(jìn)行資源分配時(shí)，需要考慮到任意一個(gè)簇p的資源用量不能超過(guò)資源總量。所以有了以下約束條件，見(jiàn)公式1：

2.2　基于包簇的能耗模型

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

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

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

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

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

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

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

3　基于包簇框架的資源分配問(wèn)題

3.1　資源分配問(wèn)題與蟻群算法

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

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

3.2　改進(jìn)的蟻群算法

3.2.1平衡蟻群算法

蟻群算法也存在一些問(wèn)題，如蟻群迷失和早熟問(wèn)題，本文將針對(duì)這兩個(gè)問(wèn)題對(duì)蟻群算法進(jìn)行改進(jìn)，稱為平衡蟻群算法。

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

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

因此，將改進(jìn)后的蟻群算法稱為平衡蟻群算法。

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

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

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

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

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

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

（4）默認(rèn)最頂層的簇與最頂層的包存在映射關(guān)系，因?yàn)樽铐攲拥陌厥?對(duì)1的關(guān)系；

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

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

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

3.3.1適宜度函數(shù)

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

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

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

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

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

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

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

3.3.3算法步驟

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

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

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

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

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

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

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

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

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

4.1　仿真環(huán)境

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

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

4.2　算法調(diào)參

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

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

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

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

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

4.3　不同算法的實(shí)驗(yàn)結(jié)果對(duì)比與分析

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

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

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

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

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

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

5　總結(jié)

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