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

楊蘇影，陳世平

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

0　引言

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

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

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

1　包簇框架

1.1　包簇介紹

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

圖1　某企業的包拓撲結構Fig.1　The packet topology of one enterprise

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

圖2　傳統數據中心的服務器拓撲結構Fig.2　The server topology of a traditional data center

圖3　簡化的簇拓撲結構Fig.3　Simplified cluster topology

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

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

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

2.1　包簇模型

設簇層次結構中任意一個簇為ρ，該簇具有N個子簇p，則1≤p≤N。并設已分配給ρ的包由M個子包v組成，則1≤v≤M。這樣問題就轉化為了如何最優地將這M個子包分配給ρ中的N個子簇。

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

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

2.2　基于包簇的能耗模型

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

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

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

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

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

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

所以最終目標函數如下：

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

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

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

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

3.2　改進的蟻群算法

3.2.1平衡蟻群算法

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

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

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

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

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

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

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

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

（2）不同層次的包簇不能夠產生映射關系；

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

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

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

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

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

3.3.1適宜度函數

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

在 3.2節中我們建立了能耗模型，本文目標是為了降低系統能耗，采用能耗的倒數來定義適宜度函數，如下：

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

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

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

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

并設iterator為當前累計迭代次數，cycle為循環次數，則算法結束條件為iteratorcycle＞。

3.3.3算法步驟

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

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

（2）設置螞蟻數量m，信息素啟發因子α，能見度啟發因子β，信息素揮發系數ρ；

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

（4）如果 a llowedk為空，則轉步驟 6；如果allowedk不為空，則根據公式10構建 a llowedk，并轉到下一步；

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

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

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

4　仿真實驗

4.1　仿真環境

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

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

4.2　算法調參

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

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

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

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

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

4.3　不同算法的實驗結果對比與分析

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

表1　參數設置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算法，說明包簇框架能有效實現資源共享，提高利用率。而同為包簇框架的BAAPC與IMOPC相比，BAAPC在CPU利用率上則更有優勢，說明本文的BAAPC更能減少簇的使用個數，集中資源，提高資源的利用率。

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

5　總結

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