劉耀鴻, 王 勇,2

(1.桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,廣西 桂林 541004;2.桂林電子科技大學(xué) 廣西云計(jì)算與復(fù)雜系統(tǒng)高校重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004)

云計(jì)算已經(jīng)成為信息行業(yè)的主要計(jì)算模式,它可以根據(jù)用戶的需求來提供相關(guān)的計(jì)算資源,用戶不需要關(guān)注基礎(chǔ)設(shè)施內(nèi)部的更新和維護(hù)細(xì)節(jié)[1]。這樣提供資源的云服務(wù)提供商就與需要計(jì)算資源的客戶建立了聯(lián)系,形成了一條供應(yīng)鏈,在虛擬化技術(shù)的基礎(chǔ)上通過虛擬機(jī)和物理機(jī)的映射關(guān)系來滿足用戶的需求[2]。隨著云計(jì)算的發(fā)展,虛擬化技術(shù)成為了人們關(guān)注的重點(diǎn)。通過虛擬化技術(shù),可以把軟件資源和硬件資源結(jié)合起來,在成本開銷相對(duì)較少的情況下滿足用戶的計(jì)算需求[3]。

云數(shù)據(jù)中心的能源問題一直是一個(gè)至關(guān)重要的問題,它對(duì)環(huán)境和成本會(huì)產(chǎn)生直接的影響[4]。能源消耗、二氧化碳等問題在不斷產(chǎn)生,使得云數(shù)據(jù)中心的能源管理面臨更大的挑戰(zhàn)。對(duì)于大型的云數(shù)據(jù)中心,能源消耗不可忽視。物理機(jī)所產(chǎn)生的能源消耗約占總體能源消耗的60%。一臺(tái)物理機(jī)所產(chǎn)生的的能耗主要由其資源上限以及部署在物理機(jī)上的虛擬機(jī)請(qǐng)求資源的總和所決定[5]。在通常情況下,一臺(tái)空閑的物理機(jī)產(chǎn)生的功耗占它最大功耗的70%[6],因此對(duì)云數(shù)據(jù)中心的物理機(jī)功耗進(jìn)行控制,減少空閑物理機(jī)的數(shù)量至關(guān)重要。Beloglazov等[7]指出好的虛擬機(jī)放置策略能有效減少能耗,并且提高QoS。通過優(yōu)化虛擬機(jī)放置策略,可以將虛擬機(jī)更多地放置在資源利用率更高的物理機(jī)上,同時(shí)將空閑虛擬機(jī)關(guān)閉,能夠最大限度地減少活動(dòng)物理機(jī)的數(shù)量,從而降低能耗。除此之外,虛擬機(jī)放置的不合理會(huì)導(dǎo)致剩余資源不均衡,進(jìn)而產(chǎn)生資源碎片,大量資源碎片的產(chǎn)生則會(huì)造成數(shù)據(jù)中心效率的低下[8]。因此,在虛擬機(jī)放置的過程中,充分考慮各臺(tái)物理機(jī)的負(fù)載均衡,有助于減少資源碎片,使得數(shù)據(jù)中心的資源使用更加高效。

Jangiti等[9]提出了一種基于資源比率的PM 選擇算法PMNeAR,該算法會(huì)根據(jù)虛擬機(jī)請(qǐng)求CPU 資源與內(nèi)存資源的比例將該虛擬機(jī)放置在剩余CPU和內(nèi)存比例最接近的物理機(jī)上,在減少資源消耗方面相比其他算法有一定的提升效果。Tarafdar等[10]提出了一種能耗和服務(wù)質(zhì)量感知的虛擬機(jī)整合算法EQC,通過馬爾可夫模型預(yù)測出空閑和過載物理機(jī),并對(duì)它們進(jìn)行遷移,旨在保證服務(wù)質(zhì)量的前提下降低數(shù)據(jù)中心的能耗,該算法在降低能耗、保證服務(wù)質(zhì)量和減少遷移次數(shù)方面有一定的效果。Farahnakian等[11]提出了一種UPBFD 算法,并使用k-近鄰回歸模型對(duì)資源使用率進(jìn)行預(yù)測,將過載物理機(jī)上的虛擬機(jī)進(jìn)行遷移,該算法在減少能耗、遷移次數(shù)和SLA 違反次數(shù)上有一定優(yōu)勢。上述近似算法在求解過程中有時(shí)間開銷小的優(yōu)點(diǎn),但是近似算法通常是根據(jù)當(dāng)前狀態(tài)得到一個(gè)最優(yōu)解,這個(gè)解不一定是全局最優(yōu)解。文獻(xiàn)[12-16]采用智能優(yōu)化算法進(jìn)行求解,智能優(yōu)化算法是通過全局搜索來找到可行解。在多目標(biāo)優(yōu)化過程中,一般是將多個(gè)目標(biāo)通過線性加權(quán)的方式整合成一個(gè)優(yōu)化目標(biāo),再通過智能優(yōu)化算法進(jìn)行求解。Parvizi等[12]針對(duì)能耗、資源利用率、活動(dòng)物理機(jī)數(shù)量進(jìn)行優(yōu)化,在引入非線性凸優(yōu)化解后,提出了一種非支配排序遺傳算法,在與其他基礎(chǔ)算法比較中有一定的提升。藺凱青等[13]提出了一種基于離散蝙蝠算法的虛擬機(jī)放置算法(DBA-VMP),對(duì)經(jīng)典蝙蝠算法進(jìn)行改進(jìn)。相比其他幾種多目標(biāo)優(yōu)化的VMP算法,該算法在保證QoS的前提下在降低能耗和提高資源利用率兩方面取得了一定的效果,但是未對(duì)QoS做出進(jìn)一步優(yōu)化。李雙俐等[14]提出了一種基于Memetic的虛擬機(jī)放置方法,首先對(duì)虛擬機(jī)的請(qǐng)求進(jìn)行分類,然后通過改進(jìn)的Memetic算法進(jìn)行求解,除了在降低能耗、提高資源利用率和保證QoS上有一定的提升效果,計(jì)算時(shí)間開銷相比其他智能算法也有一定程度的減小。馬小晉等[15]在模擬退火算法的基礎(chǔ)上進(jìn)行改進(jìn),提出了一種基于改進(jìn)模擬退火算法的虛擬機(jī)調(diào)度方法,針對(duì)資源利用率、執(zhí)行成本和負(fù)載均衡這3個(gè)目標(biāo)進(jìn)行多目標(biāo)優(yōu)化。為了避免陷入局部最優(yōu),引入了并行的思想,根據(jù)執(zhí)行成本和執(zhí)行性能生成兩組解并進(jìn)行迭代,最終效果有一定提升。Tang等[16]提出了一種混合遺傳算法,它不僅考慮了物理機(jī)的能耗,還考慮了通信網(wǎng)絡(luò)的能耗,相比于普通遺傳算法有著更高的性能和效率。以上這些研究大多是針對(duì)能耗、資源利用率進(jìn)行優(yōu)化。但在虛擬機(jī)放置的過程中,不合理的放置造成大量資源碎片的產(chǎn)生也同樣會(huì)導(dǎo)致能耗較高、資源利用率低下的問題。因此,文獻(xiàn)[17-18]主要將資源的負(fù)載均衡及資源碎片最小化作為優(yōu)化目標(biāo)。Li等[17]提出了一種基于BBO 算法的多目標(biāo)虛擬機(jī)放置算法,針對(duì)CPU、內(nèi)存和帶寬資源的負(fù)載均衡進(jìn)行優(yōu)化,同時(shí)考慮物理機(jī)之間的負(fù)載均衡及單個(gè)物理機(jī)內(nèi)部的負(fù)載均衡,取得了一定的效果。Ghasemi等[18]提出了一種基于負(fù)載均衡的多目標(biāo)虛擬機(jī)放置算法,該算法使用了強(qiáng)化學(xué)習(xí)的方法,除了關(guān)注物理機(jī)內(nèi)部的資源平衡,還關(guān)注物理機(jī)之間的負(fù)載均衡,這樣能使資源分布更加均衡的同時(shí)減少運(yùn)行時(shí)間。

上述研究中存在一些不足,例如在用啟發(fā)式算法進(jìn)行求解時(shí),大多數(shù)只考慮了能耗、資源利用率,很少考慮資源碎片的問題,而資源碎片也是虛擬機(jī)放置中的一個(gè)關(guān)鍵指標(biāo),關(guān)系著虛擬機(jī)整合效果的好壞,且這類算法很容易陷入局部最優(yōu)解。因此,提出一種基于蟻獅算法的虛擬機(jī)放置算法(MALO)。通過對(duì)傳統(tǒng)蟻獅算法進(jìn)行調(diào)整,使得種群的隨機(jī)性和多樣性大大提升,能有效避免陷入局部最優(yōu)解。

1 模型設(shè)計(jì)

1.1 虛擬機(jī)放置問題定義

虛擬機(jī)放置問題實(shí)質(zhì)上可看作一個(gè)多維裝箱問題,也是NP hard問題。假設(shè)云數(shù)據(jù)中心有m臺(tái)虛擬機(jī)、n臺(tái)物理機(jī),虛擬機(jī)放置問題也就是通過合理的調(diào)度策略將m臺(tái)虛擬機(jī)放置在n臺(tái)物理機(jī)上,且滿足一定的約束條件。問題定義如下:

數(shù)據(jù)中心中m臺(tái)虛擬機(jī)組成一個(gè)虛擬機(jī)列表V={V1,V2,…,Vm},n臺(tái)物理機(jī)組成一個(gè)物理機(jī)列表H={h1,h2,…,hn}。規(guī)定每臺(tái)虛擬機(jī)請(qǐng)求的資源及物理機(jī)的資源包括CPU 和內(nèi)存2種。第i臺(tái)虛擬機(jī)請(qǐng)求資源為Ri=(ui,wi),其中:ui表示第i臺(tái)虛擬機(jī)請(qǐng)求的CPU 資源;wi表示第i臺(tái)虛擬機(jī)請(qǐng)求的內(nèi)存資源。數(shù)據(jù)中心物理機(jī)的CPU 資源容量列表為Rcpu={c1,c2,…,cn},其中cj表示第j臺(tái)物理機(jī)的CPU 資源容量。數(shù)據(jù)中心物理機(jī)的內(nèi)存資源容量列表為Rmem={m1,m2,…,mn},其中mj表示第j臺(tái)物理機(jī)的內(nèi)存資源容量。并且還需要滿足以下約束條件:

其中:i=1,2,…;m,j=1,2,…,n;Xij表示虛擬機(jī)Vi是否放在物理機(jī)hj上,它有2種取值1和0,1表示虛擬機(jī)Vi放在物理機(jī)hj上,0表示虛擬機(jī)Vi未放在物理機(jī)hj上。式(1)表示一臺(tái)虛擬機(jī)最多只能放置在一臺(tái)物理機(jī)上,式(2)和式(3)表示所有虛擬機(jī)請(qǐng)求的CPU 和內(nèi)存資源總量不能超過當(dāng)前物理機(jī)CPU 和內(nèi)存資源總量。

1.2 能耗模型

當(dāng)前數(shù)據(jù)中心的高能耗問題已經(jīng)引起了足夠的重視,如何降低能耗已成為研究者研究的重點(diǎn)問題。假設(shè)當(dāng)前數(shù)據(jù)中心有m臺(tái)虛擬機(jī)和n臺(tái)物理機(jī),第i臺(tái)物理機(jī)hi處于滿載狀態(tài)時(shí)的功耗為hfull_poweri,當(dāng)前的CPU 利用率為hcpu_utii。 在通常情況下,可認(rèn)為物理機(jī)的功耗與其CPU 利用率呈正相關(guān)關(guān)系,能耗模型為:

其中:α表示空閑物理機(jī)占滿載物理機(jī)功耗的百分比,α的范圍一般在0.6～0.7,本研究統(tǒng)一取0.7;yi表示第i臺(tái)物理機(jī)是否為活動(dòng)物理機(jī),它的取值為0或者1,1表示活動(dòng)物理機(jī),0表示非活動(dòng)物理機(jī);Etotal表示的是數(shù)據(jù)中心的總能耗,在完成虛擬機(jī)的放置時(shí),默認(rèn)當(dāng)前時(shí)刻的總功耗值為數(shù)據(jù)中心所有物理機(jī)產(chǎn)生的能耗。

1.3 資源使用率模型

假如當(dāng)前數(shù)據(jù)中心有m臺(tái)虛擬機(jī)和n臺(tái)活動(dòng)物理機(jī),資源使用率包括CPU 和內(nèi)存資源的平均資源使用率2種,且在計(jì)算時(shí)只考慮活動(dòng)物理機(jī),而不考慮負(fù)載為0的物理機(jī)。資源使用率模型為

1.4 資源平衡度模型

假設(shè)數(shù)據(jù)中心有m臺(tái)虛擬機(jī)和n臺(tái)物理機(jī),為了使虛擬機(jī)的放置更加均衡,提出了一種基于比值的資源平衡度的模型,當(dāng)一臺(tái)物理機(jī)的CPU 利用率和內(nèi)存利用率的比值越接近于1時(shí),則代表這臺(tái)物理機(jī)的資源利用更加均衡。數(shù)據(jù)中心的資源平衡度模型為

其中:hcpu_utii表示第i臺(tái)物理機(jī)的CPU 利用率;hmem_utii表示第i臺(tái)物理機(jī)的內(nèi)存利用率。

1.5 資源碎片模型

在當(dāng)前數(shù)據(jù)中心,不合理的虛擬機(jī)放置策略可能會(huì)造成資源碎片的產(chǎn)生,資源碎片即物理機(jī)上CPU資源和內(nèi)存資源不平衡,導(dǎo)致剩余資源無法再滿足新的虛擬機(jī)請(qǐng)求,隨著資源碎片的累積,會(huì)造成資源利用率低下及資源的浪費(fèi)。資源碎片定義為

其中:fcpu表示CPU 資源碎片;fmem表示內(nèi)存資源碎片;hcpu_remi表示第i臺(tái)物理機(jī)的CPU 剩余量;hmem_remi表示第i臺(tái)物理機(jī)的內(nèi)存剩余量。yi表示是否滿足式(12)和式(14)資源碎片的條件,如果滿足yi為1,否則為0。

1.6 虛擬機(jī)放置目標(biāo)函數(shù)

一個(gè)數(shù)據(jù)中心的虛擬機(jī)是否高效、合理,關(guān)鍵是能否降低能耗、提升資源利用率,并減少資源碎片的產(chǎn)生。低能耗和高資源利用率能使數(shù)據(jù)中心的成本降低。而虛擬機(jī)放置是否平衡同樣影響著數(shù)據(jù)中心的高效性,如果服務(wù)器上資源放置不平衡,會(huì)導(dǎo)致資源碎片的產(chǎn)生。

根據(jù)上述分析,優(yōu)化目標(biāo)主要是最小化能耗、資源碎片,最大化資源利用率。虛擬機(jī)放置目標(biāo)函數(shù)為

其中:F表示目標(biāo)函數(shù)的適應(yīng)度函數(shù)值,這里先將能耗和資源平衡度進(jìn)行歸一化,再通過加權(quán)的方式將多個(gè)目標(biāo)整合成單目標(biāo);r表示一個(gè)參數(shù),當(dāng)r值越大,表示能耗占的比重更大,主要考慮降低能耗,反之則表示資源平衡度占的比重更大,主要考慮虛擬機(jī)放置更加平衡,減少資源碎片。為了平衡能耗和資源平衡度的影響,將r的值設(shè)為0.5,此時(shí)能取得更好的放置效果。

2 基于改進(jìn)蟻獅算法(MALO)的虛擬機(jī)放置方法

本質(zhì)上來說,虛擬機(jī)放置問題是一個(gè)非線性的優(yōu)化問題,它產(chǎn)生的解是離散式的,因此不適合用一般的數(shù)學(xué)方法求解。在大多數(shù)情況下,虛擬機(jī)放置問題利用啟發(fā)式算法來求解,如蟻群算法、遺傳算法及粒子群算法等。蟻獅優(yōu)化算法(antlion optimization,簡稱ALO)具有簡單、調(diào)節(jié)參數(shù)少、魯棒性比較強(qiáng)等優(yōu)點(diǎn),在求解一些復(fù)雜問題時(shí)有一定優(yōu)勢,但也存在不足,主要是易收斂過快,難以跳出局部最優(yōu)解。因此,為了解決這類問題,需要對(duì)ALO 算法的相關(guān)步驟進(jìn)行改進(jìn)。

蟻獅優(yōu)化算法的步驟如下:

Step1:初始化算法的參數(shù)。種群的大小為N,迭代次數(shù)為T,解的維度為dim,解的上界和下界分別為bu,bl。對(duì)N個(gè)螞蟻和蟻獅的位置進(jìn)行隨機(jī)初始化:

其中:Xi,j表示第i個(gè)種群個(gè)體的第j維進(jìn)行初始化,i=1,2,…,N,j=1,2,…,d。將螞蟻的位置和蟻獅的位置保存在矩陣中,根據(jù)目標(biāo)函數(shù)計(jì)算出每個(gè)個(gè)體的適應(yīng)度,并按適應(yīng)度進(jìn)行排序,適應(yīng)度最優(yōu)的位置即為精英蟻獅的位置。

Step2:通過輪盤賭策略選擇蟻獅,不同位置的蟻獅被選中的概率也不一樣,一般來說適應(yīng)度越好,被選中的概率越大。

Step3:螞蟻圍繞輪盤賭策略選擇的蟻獅和精英蟻獅進(jìn)行隨機(jī)游走,隨機(jī)游走的方向和距離由隨機(jī)函數(shù)控制。隨著迭代次數(shù)的不斷增加,螞蟻隨機(jī)游走的邊界也在不斷縮小,越來越接近最優(yōu)解,邊界變化如式(17)所示。最后對(duì)螞蟻的位置進(jìn)行更新,如式(19)所示。

其中:I隨著迭代次數(shù)的增加而增大;t為當(dāng)前迭代次數(shù);T為總迭代次數(shù);W的值由當(dāng)前迭代次數(shù)決定;Ati表示第i個(gè)螞蟻在第t次迭代中的位置;RtA表示由輪盤賭選擇的蟻獅在第t次迭代中的位置;RtE表示精英蟻獅在第t次迭代中的位置。

Step4:在螞蟻位置更新后會(huì)計(jì)算當(dāng)前螞蟻的適應(yīng)度,若當(dāng)前螞蟻的適應(yīng)度優(yōu)于當(dāng)前蟻獅,則蟻獅會(huì)捕獲螞蟻,并將蟻獅的位置更新為螞蟻的位置。

Step5:迭代次數(shù)遞增,若當(dāng)前迭代次數(shù)達(dá)到最大迭代次數(shù),則輸出精英蟻獅的位置,即為全局最優(yōu)解;否則,重復(fù)Step2到Step5,直到滿足條件為止。

針對(duì)ALO算法容易產(chǎn)生的問題,提出了一種改進(jìn)的蟻獅算法(modified antlion optimization,簡稱MALO)。算法的主要流程如下:

輸入:vmList,pmList

輸出:Pos_Elite

T:最大迭代次數(shù);iter:當(dāng)前迭代次數(shù);N:種群數(shù)量;

Pos_Ant:螞蟻位置;Pos_Antlion:蟻獅位置;

Pos_Elite:精英蟻獅位置;

Step1:按照式(16)初始化N個(gè)螞蟻和蟻獅個(gè)體的位置。

Step2:計(jì)算每個(gè)蟻獅個(gè)體的適應(yīng)度函數(shù)值,并按適應(yīng)度函數(shù)值從小到大排序,適應(yīng)度值最小的個(gè)體位置即為Pos_Elite。

Step3:若iter≤T,進(jìn)行迭代,在迭代過程中邊界的變化如式(20)所示,每個(gè)螞蟻個(gè)體會(huì)圍繞輪盤賭策略選擇出的蟻獅以及Pos_Elite進(jìn)行式(22)所示的隨機(jī)游走。若此時(shí)Pos_Ant＞bu或者Pos_Ant＜bl,則Pos_Ant會(huì)按照式(23)進(jìn)行更新。

Step4:計(jì)算Pos_Ant的適應(yīng)度函數(shù)值,若小于Pos_Antlion的適應(yīng)度函數(shù)值,則將Pos_Antlion更新為Pos_Ant。

Step5:若iter=T,則跳轉(zhuǎn)到Step6,否則,iter++,跳轉(zhuǎn)到Step3繼續(xù)循環(huán)。

Step6:此時(shí)Pos_Elite即為虛擬機(jī)放置的最終方案,輸出結(jié)果。

2.1 邊界自適應(yīng)調(diào)整機(jī)制

在傳統(tǒng)蟻獅算法中,螞蟻跟隨蟻獅隨機(jī)游走的邊界是不斷變化的,隨著迭代次數(shù)的增加,它的上界和下界不斷收縮。但是邊界變化的趨勢是線性的,即所有螞蟻個(gè)體在游走過程中邊界變化趨勢完全一致。這種邊界變化機(jī)制不適用于云環(huán)境編碼,它可能會(huì)破壞種群解的多樣性,且易陷入局部最優(yōu)解,不利于全局尋優(yōu)。因此,提出了一種邊界自適應(yīng)調(diào)整機(jī)制,通過改進(jìn)式(17),使得螞蟻進(jìn)行隨機(jī)游走時(shí)解的多樣性更加豐富。

其中:r表示當(dāng)前迭代次數(shù)待放置的虛擬機(jī)數(shù)量和物理機(jī)數(shù)量的比值;t表示當(dāng)前迭代次數(shù);T表示總迭代次數(shù);w的大小隨著當(dāng)前迭代次數(shù)的變化而變化,當(dāng)前迭代次數(shù)越大,w的值越大;rand表示(0,1)區(qū)間的一個(gè)隨機(jī)數(shù)。螞蟻隨機(jī)游走的邊界主要由I來決定,并且與I值呈反比。I的值是隨著迭代次數(shù)的增加而動(dòng)態(tài)變化的。

2.2 螞蟻位置更新策略

螞蟻隨機(jī)游走的位置根據(jù)輪盤賭策略選擇出的蟻獅及精英蟻獅的位置確定。在傳統(tǒng)蟻獅算法中,螞蟻?zhàn)罱K游走的位置是輪盤賭選擇的蟻獅和精英蟻獅位置的中點(diǎn),這樣會(huì)造成多數(shù)螞蟻游走的趨勢保持一致,破壞了種群的多樣性。對(duì)螞蟻隨機(jī)游走的位置進(jìn)行改進(jìn),使得在迭代的不同時(shí)期,螞蟻游走具有不同的趨勢。當(dāng)?shù)螖?shù)較少時(shí),螞蟻偏向輪盤賭選擇的蟻獅進(jìn)行隨機(jī)游走,而在算法后期,螞蟻更偏向精英蟻獅進(jìn)行隨機(jī)游走。這種策略使螞蟻的游走更具隨機(jī)性,也在一定程度上保證了種群的多樣性。改進(jìn)后的螞蟻位置更新策略為

當(dāng)螞蟻完成隨機(jī)游走后,如果此時(shí)螞蟻的位置大于上界或者小于下界,會(huì)將螞蟻個(gè)體移動(dòng)到邊界上,但這樣顯然不利于種群的多樣性,可能會(huì)造成一些個(gè)體集中在同一位置。因此,對(duì)這種情況進(jìn)行改進(jìn),如果螞蟻個(gè)體越界,位置會(huì)按式(23)進(jìn)行更新,保證隨機(jī)性。

3 仿真實(shí)驗(yàn)及分析

用Python語言開發(fā)了一個(gè)虛擬機(jī)放置的仿真平臺(tái),該仿真平臺(tái)可以讀取數(shù)據(jù)、處理數(shù)據(jù)以及統(tǒng)計(jì)性能指標(biāo)。提出的算法將與FFD 算法[6]、MBFD 算法[6]、BRC算法[19]以及ALO 算法在能耗、資源利用率、資源碎片、活動(dòng)物理機(jī)數(shù)量等幾個(gè)方面進(jìn)行對(duì)比。本實(shí)驗(yàn)的環(huán)境配置:CPU 為2.2 GHz六核Intel Core i7,內(nèi)存為16 GiB,操作系統(tǒng)為Mac OS,Python版本為Python 3.7。實(shí)驗(yàn)所采用的數(shù)據(jù)集是BitBrains數(shù)據(jù)集[20],BitBrains是一家真實(shí)的數(shù)據(jù)中心,并為眾多公司提供云計(jì)算服務(wù)。實(shí)驗(yàn)場景選用的是異構(gòu)的數(shù)據(jù)中心并選取了CPU 和內(nèi)存2種指標(biāo),數(shù)據(jù)集的物理機(jī)配置如表1所示。

表1 數(shù)據(jù)中心的物理機(jī)配置

實(shí)驗(yàn)中,MALO算法的種群數(shù)量設(shè)置為200,迭代次數(shù)為10。待放置的虛擬機(jī)數(shù)量分別為50,60,70,80,90以及100臺(tái)。數(shù)據(jù)中心的物理機(jī)數(shù)量為60臺(tái),且是異構(gòu)的。隨著待放置虛擬機(jī)的數(shù)量不斷增加,使用MALO 算法進(jìn)行求解時(shí)維度也在不斷增加,為了保證算法求解的精度盡可能高,實(shí)驗(yàn)采用分批放置,即以10臺(tái)虛擬機(jī)為一組進(jìn)行放置,以此類推。其他對(duì)比算法的參數(shù)均采用默認(rèn)配置。分別對(duì)比各種算法的能耗、物理機(jī)開機(jī)數(shù)量、CPU 資源利用率、內(nèi)存資源利用率、CPU 資源碎片以及內(nèi)存資源碎片這幾個(gè)指標(biāo)。

3.1 能耗實(shí)驗(yàn)

實(shí)驗(yàn)對(duì)比了MALO、ALO、BRC、FFD、MBFD五種虛擬機(jī)放置算法的能耗情況以及各算法的活躍物理機(jī)數(shù)量。在對(duì)能耗進(jìn)行統(tǒng)計(jì)時(shí),當(dāng)物理機(jī)核心數(shù)為24、32、48、64時(shí),物理機(jī)對(duì)應(yīng)的峰值功耗分別為0.7、1.0、1.4、2.0 kW。

能耗實(shí)驗(yàn)結(jié)果如圖1所示,MALO 算法能耗優(yōu)于另外4種算法。當(dāng)虛擬機(jī)數(shù)量為50～90時(shí)能耗最低,虛擬機(jī)數(shù)量為100時(shí),MALO與ALO能耗相同。這是因?yàn)樵跀?shù)據(jù)中心能耗與物理機(jī)的開機(jī)數(shù)量有很強(qiáng)的相關(guān)性,活躍物理機(jī)的數(shù)量越少,能耗一般也越低。但本實(shí)驗(yàn)是在異構(gòu)的數(shù)據(jù)中心下進(jìn)行的,因此削弱了這種相關(guān)性。MALO 算法在ALO 算法上做了一些改進(jìn),有著更好的跳出局部最優(yōu)解機(jī)制,在范圍內(nèi)能搜索到更多解,這樣也就使得活躍物理機(jī)的數(shù)量減少,能耗相比其他幾種算法有一定優(yōu)勢。

圖1 數(shù)據(jù)中心總功耗對(duì)比

活躍物理機(jī)的數(shù)量能間接反映能耗高低,通常情況下活躍物理機(jī)數(shù)量越少,能耗越低,因此降低活躍物理機(jī)的數(shù)量是解決高能耗問題的關(guān)鍵。圖2為這幾種算法的活躍物理機(jī)數(shù)量,可以看出隨著待放置虛擬機(jī)數(shù)量的增加,MALO 算法的活躍物理機(jī)數(shù)量是最低的,當(dāng)虛擬機(jī)數(shù)量為100 時(shí),MALO 算法和ALO算法活躍物理機(jī)數(shù)量一致。這是因?yàn)镸ALO算法相比ALO 算法有著更好的跳出局部最優(yōu)解機(jī)制,有利于全局尋優(yōu)。而FFD算法的策略是將虛擬機(jī)放置在遍歷過程中第一臺(tái)滿足需求的物理機(jī)上,MBFD算法是將虛擬機(jī)放置在能耗增加最少的物理機(jī)上,BRC算法則是基于資源平衡因子和資源浪費(fèi)得到一個(gè)合理的放置方案,這3種算法未盡可能地將多臺(tái)虛擬機(jī)往同一臺(tái)物理機(jī)上放置,從而減少物理機(jī)的開機(jī)數(shù)量。

圖2 數(shù)據(jù)中心活躍物理機(jī)數(shù)量對(duì)比

3.2 資源利用率實(shí)驗(yàn)

資源利用率是衡量一個(gè)數(shù)據(jù)中心虛擬機(jī)放置策略好壞的關(guān)鍵指標(biāo),資源利用率越高意味著每臺(tái)主機(jī)的資源利用更加充分,虛擬機(jī)放置策略更加合理。圖3、圖4分別為各算法的CPU、內(nèi)存利用率的情況,在CPU 利用率方面,在大多數(shù)虛擬機(jī)規(guī)模下MALO 算法都具有比較明顯的優(yōu)勢。而在內(nèi)存利用率方面,當(dāng)虛擬機(jī)規(guī)模在60～90時(shí),MALO 算法內(nèi)存利用率最高;當(dāng)虛擬機(jī)數(shù)量為50時(shí),內(nèi)存利用率低于MBFD算法,當(dāng)虛擬機(jī)數(shù)量為100時(shí),內(nèi)存利用率略低于ALO算法?？偟膩砜?MALO算法在資源利用率上能取得較好的效果,這是因?yàn)镸ALO算法相比ALO算法具有更好的跳出局部最優(yōu)解機(jī)制,能避免陷入局部最優(yōu)解,而FFD、MBFD 及BRC算法沒有盡可能在一臺(tái)物理機(jī)上放置更多的虛擬機(jī),虛擬機(jī)放置較分散,活動(dòng)物理機(jī)的數(shù)量較多,因此,CPU、內(nèi)存利用率低于MALO算法。

圖3 數(shù)據(jù)中心CPU利用率對(duì)比

圖4 數(shù)據(jù)中心內(nèi)存利用率對(duì)比

3.3 資源碎片實(shí)驗(yàn)

資源碎片是衡量數(shù)據(jù)中心虛擬機(jī)放置是否平衡的一個(gè)重要指標(biāo)。如果一臺(tái)物理機(jī)上的虛擬機(jī)放置不平衡,如CPU 資源用完而內(nèi)存資源還剩很多,就會(huì)導(dǎo)致無法再放置新的虛擬機(jī),資源就會(huì)被浪費(fèi)掉,這也是導(dǎo)致物理機(jī)資源利用率低下的一個(gè)重要原因。因此,通常情況下資源碎片的數(shù)量越少,主機(jī)負(fù)載就越均衡,數(shù)據(jù)中心的資源利用越高效。通過圖5、圖6可看出,在CPU 碎片方面,MALO 算法與ALO 算法效果接近,在大多數(shù)虛擬機(jī)規(guī)模下能產(chǎn)生更少的CPU 資源碎片。而在內(nèi)存碎片方面,MALO 算法在效果上僅次于FFD算法,FFD算法在內(nèi)存碎片上效果比較明顯,主要是因?yàn)镕FD的放置策略就是在遍歷物理機(jī)列表的過程中找到首次滿足虛擬機(jī)資源請(qǐng)求的物理機(jī)就進(jìn)行放置,導(dǎo)致虛擬機(jī)放置相對(duì)比較分散,這樣也就減少了內(nèi)存資源碎片的產(chǎn)生。綜合來看,MALO算法在資源碎片方面總體上能取得一個(gè)較好的效果,這是因?yàn)镸ALO 算法在進(jìn)行放置時(shí)考慮了資源平衡度,使得放置后的資源平衡度盡可能小,從而減少放置不平衡情況的發(fā)生。

圖5 數(shù)據(jù)中心CPU資源碎片對(duì)比

圖6 數(shù)據(jù)中心內(nèi)存資源碎片對(duì)比

4 結(jié)束語

提出了一種基于改進(jìn)蟻獅算法的虛擬機(jī)放置方法,針對(duì)能耗、資源利用率及資源碎片這3個(gè)目標(biāo)進(jìn)行優(yōu)化。在蟻獅算法的基礎(chǔ)上,通過在螞蟻隨機(jī)游走策略上引入自適應(yīng)邊界變化機(jī)制,并且改進(jìn)螞蟻隨機(jī)游走時(shí)位置更新策略,使得種群的多樣性大大增加,改進(jìn)后的蟻獅算法有更好的跳出局部最優(yōu)解機(jī)制。將此方法應(yīng)用在虛擬機(jī)放置的場景下,通過與另外4種算法的對(duì)比實(shí)驗(yàn)可看出,MALO 算法在降低能耗、提高資源利用率的同時(shí),也能在一定程度上減少資源碎片的產(chǎn)生。

在未來的工作中,可考慮結(jié)合蟻群算法、粒子群算法等一些智能優(yōu)化算法的策略,使得算法有更好的跳出局部最優(yōu)解機(jī)制。除此之外,蟻獅算法除了應(yīng)用在虛擬機(jī)放置階段,還可以應(yīng)用在虛擬機(jī)遷移過程中,最后在真實(shí)環(huán)境中進(jìn)一步發(fā)揮蟻獅算法的作用,提高云數(shù)據(jù)中心的效率。