一種基于改進(jìn)最大最小蟻群算法的虛擬機(jī)放置策略?

劉晉西

（武漢數(shù)字工程研究所 武漢 430074）

1 引言

云計(jì)算［1］是一種新型的商業(yè)模式和服務(wù)模式，這種模式提供了用戶所需的一切，作為一種服務(wù)，它滿足在任意時(shí)間、任意地點(diǎn)交付使用。作為云計(jì)算的服務(wù)最終提供者，數(shù)據(jù)中心［2］有著非常復(fù)雜的計(jì)算設(shè)備和存儲(chǔ)設(shè)備以及大型的電力系統(tǒng)等。隨著云計(jì)算的飛速發(fā)展，數(shù)據(jù)中心的規(guī)模也與日俱增。有研究表明，在數(shù)據(jù)中心的所有開(kāi)銷中，有70%來(lái)自服務(wù)器的采購(gòu)開(kāi)銷以及配電和冷卻的基礎(chǔ)設(shè)施開(kāi)銷，剩下的30%則是提供服務(wù)導(dǎo)致的電力開(kāi)銷和網(wǎng)絡(luò)開(kāi)銷［3］。我們所能做的就是優(yōu)化這后30%的電力開(kāi)銷和網(wǎng)絡(luò)開(kāi)銷。

有研究表明，優(yōu)化數(shù)據(jù)中心的資源管理，能夠有效地提高資源的利用率，降低電力開(kāi)銷和網(wǎng)絡(luò)開(kāi)銷［4～6］。圖1為數(shù)據(jù)中心的資源管理圖。

2 問(wèn)題描述

在進(jìn)行虛擬機(jī)的初始化放置時(shí)，滿足客戶的需求以及最小化電能消耗和網(wǎng)絡(luò)資源消耗是要兼顧的。也就是說(shuō)，需要在滿足客戶需求的同時(shí)也要盡可能使得數(shù)據(jù)中心的電能開(kāi)銷和網(wǎng)絡(luò)開(kāi)銷達(dá)到最小值。

這里需要考慮下面的因素:

電能開(kāi)銷。研究表明，數(shù)據(jù)中心的電能開(kāi)銷主要來(lái)源于服務(wù)器的電能開(kāi)銷，而服務(wù)器的電能開(kāi)銷又與CPU、內(nèi)存等有著不可分割關(guān)系，其中CPU占據(jù)著絕大部分［7～8］。研究發(fā)現(xiàn)，物理節(jié)點(diǎn)的電能消耗和CPU利用率呈正相關(guān)。即當(dāng)CPU由完全空閑的狀態(tài)到滿載的狀態(tài)時(shí)，CPU利用率相應(yīng)的由0上升到100%，物理節(jié)點(diǎn)的電能消耗也隨之呈現(xiàn)上升的趨勢(shì)。有些學(xué)者發(fā)現(xiàn)，當(dāng)物理節(jié)點(diǎn)完全空閑時(shí)，它的電能消耗是滿載時(shí)的70%［9］。這一結(jié)論充分說(shuō)明適當(dāng)?shù)年P(guān)閉空閑的物理節(jié)點(diǎn)有助于降低數(shù)據(jù)中心的電能消耗?？梢杂孟旅娴墓絹?lái)計(jì)算物理節(jié)點(diǎn)的電能消耗:

這里Poweri代表的是物理節(jié)點(diǎn)i的電能消耗，Bi為這臺(tái)物理節(jié)點(diǎn)上已經(jīng)被使用的CPU資源，Pi為這臺(tái)物理節(jié)點(diǎn)上未被使用的CPU資源。這樣一來(lái)就有兩種方法可以降低服務(wù)器的電能消耗。一是減少開(kāi)啟服務(wù)器的數(shù)量，二是開(kāi)啟消耗電能較少的服務(wù)器。所以在虛擬機(jī)初始化放置時(shí)，應(yīng)盡可能地將虛擬機(jī)集中放置在消耗電能較小的服務(wù)器上。

這里data（i，j）是一個(gè) n×n 的方陣，代表所有虛擬機(jī)之間的通信頻率，n為虛擬機(jī)的數(shù)量。cost為是一個(gè)k×k的方陣，代表物理機(jī)之間的通信開(kāi)銷，k為物理機(jī)的數(shù)量。π（i）則代表虛擬機(jī)i放置在物理機(jī)的編號(hào)。

至此虛擬機(jī)的初始化放置問(wèn)題轉(zhuǎn)化為多目標(biāo)的優(yōu)化問(wèn)題。我們的目標(biāo)是在滿足虛擬機(jī)資源請(qǐng)求的前提下，將虛擬機(jī)放置在合適的服務(wù)器上，使得整個(gè)的電能開(kāi)銷和網(wǎng)絡(luò)開(kāi)銷達(dá)到最小。即使得下面的公式在滿足約束條件的前提下成立:

其約束條件如下:

1）任意一臺(tái)物理機(jī)上的所有虛擬機(jī)對(duì)CPU資源的請(qǐng)求的數(shù)量之和不能超過(guò)物理機(jī)本身的CPU資源數(shù)量，即

2）任意一臺(tái)物理機(jī)上的所有虛擬機(jī)對(duì)存儲(chǔ)資源的請(qǐng)求的數(shù)量之和不能超過(guò)物理機(jī)本身的存儲(chǔ)資源數(shù)量:

3）任意一臺(tái)物理機(jī)上的所有虛擬機(jī)對(duì)帶寬資源的請(qǐng)求的數(shù)量之和不能超過(guò)物理機(jī)本身的帶寬資源數(shù)量:

4）同一時(shí)刻一臺(tái)虛擬機(jī)只能位于一臺(tái)物理機(jī)上:

宏觀周期的本質(zhì)是圍繞長(zhǎng)期趨勢(shì)線波動(dòng)的債務(wù)周期，利率則可以加快或推遲宏觀周期的運(yùn)行。油價(jià)既是宏觀周期的一部分，被動(dòng)受到宏觀周期的影響，同時(shí)油價(jià)的自身波動(dòng)又會(huì)影響利率和貨幣政策，進(jìn)而影響宏觀周期。

在上述的約束條件中，V是一個(gè)n×3的矩陣，第i行的每一列分別代表虛擬機(jī)i的CPU資源請(qǐng)求數(shù)量、存儲(chǔ)資源請(qǐng)求數(shù)量和帶寬資源請(qǐng)求數(shù)量。P是一個(gè)k×3的矩陣，第k行的每一列代表物理機(jī)k的CPU資源總數(shù)量、存儲(chǔ)資源總數(shù)量和帶寬資源總數(shù)量。

3 算法實(shí)現(xiàn)

相比于傳統(tǒng)的蟻群算法［13～14］，最大最小蟻群算法［15］設(shè)置了信息算的濃度區(qū)間，也就是說(shuō)最大最小蟻群算法中信息素濃度不能無(wú)限制地增大或減小，這樣一來(lái)不僅使得求解速度大大加快，而且也可以防止算法過(guò)早地停滯。

3.1 信息素的更新

幾乎所有的蟻群算法中，信息素τij的更新都會(huì)遵循這樣的規(guī)則:

這里ρ為揮發(fā)因子。

在改進(jìn)的最大最小蟻群算法中Δτibjest的表達(dá)式如下:

這里的Cbest就是式（9）的最小值，參數(shù)b的選擇可以視情況而定，最終使得信息素濃度的增加不至于過(guò)快的達(dá)到上限或者下限從而導(dǎo)致螞蟻無(wú)法做出選擇。

3.2 概率轉(zhuǎn)移函數(shù)

每只螞蟻會(huì)被隨機(jī)的放置在物理機(jī)上，然后根據(jù)一個(gè)概率轉(zhuǎn)移函數(shù)從可以被放置在該物理機(jī)的虛擬機(jī)中選擇一臺(tái)虛擬機(jī)并放置。為了避免已經(jīng)被放置的虛擬機(jī)再次被放置，會(huì)有一個(gè)數(shù)據(jù)禁忌表用來(lái)存儲(chǔ)已經(jīng)放置的虛擬機(jī)和不能被放置在該物理機(jī)的虛擬機(jī)。直到本次循環(huán)結(jié)束，清空禁忌表，螞蟻才能再次自由選擇。以下是概率選擇函數(shù)的表達(dá)式:

上式中allowedm表示螞蟻m下一次允許選擇的虛擬機(jī)，也就是禁忌表中剔除的部分，τij(t)為t時(shí)刻的信息素濃度，ηij(t)為t時(shí)刻的能見(jiàn)度，α和β分別為信息素啟發(fā)式因子和能見(jiàn)度啟發(fā)式因子。

3.3 最優(yōu)解的構(gòu)建

具體構(gòu)建最優(yōu)解的時(shí)候，在算法的每次循環(huán)中，螞蟻根據(jù)概率轉(zhuǎn)移函數(shù)在所有等待被放置的虛擬機(jī)中選擇，每只螞蟻在完成一次循環(huán)后會(huì)得到一個(gè)局部最優(yōu)解。此時(shí)將這個(gè)局部最優(yōu)解暫時(shí)保存為全局最優(yōu)解，若下一只螞蟻的局部最優(yōu)解優(yōu)于全局最優(yōu)解，則將全局最優(yōu)解更新；否則保留全局最優(yōu)解。在所有的螞蟻完成循環(huán)后就可以得到全局最優(yōu)解。

算法流程如下:

第一步，初始化。初始化虛擬機(jī)請(qǐng)求的資源、物理機(jī)的資源、螞蟻的數(shù)量、信息素?fù)]發(fā)因子、信息素的上下限以及循環(huán)次數(shù)；

第二步，將一只螞蟻任意放在一臺(tái)物理機(jī)i上；

第三步，螞蟻根據(jù)轉(zhuǎn)移概率矩陣對(duì)禁忌表以外的虛擬機(jī)進(jìn)行搜索，搜索到合適的虛擬機(jī)就將其放在物理機(jī)i上，將已放置的虛擬機(jī)數(shù)量加1并且更新禁忌表；

第四步，判斷物理機(jī)是否可以放置更多的虛擬機(jī)，如果是，則轉(zhuǎn)向第三步，如果否，轉(zhuǎn)向第五步；

第五步，螞蟻轉(zhuǎn)向下一臺(tái)物理機(jī)并判斷虛擬機(jī)是否放置完畢，如果是，轉(zhuǎn)向第六步，如果否，轉(zhuǎn)向第三步；

第六步，根據(jù)公式（9）計(jì)算C，清空禁忌表并判斷這個(gè)C是否小于Cbest，如果是，轉(zhuǎn)向第七步，如果否，則忽略這個(gè)C；

第七步，將第六步的C賦值給Cbest，記錄當(dāng)前的虛擬機(jī)放置方案，螞蟻數(shù)量加1，并判斷螞蟻數(shù)量是否到達(dá)上限。如果是，轉(zhuǎn)向第八步，如果否，轉(zhuǎn)向第二步；

第八步，循環(huán)數(shù)量加1，并判斷是否到達(dá)循環(huán)次數(shù)的上限，如果是，則算法結(jié)束，Cbest為最優(yōu)解，相應(yīng)的虛擬機(jī)放置方案則為最佳的方案，如果否，則轉(zhuǎn)向第二步。

4 實(shí)驗(yàn)與分析

數(shù)據(jù)中心的總體開(kāi)銷，包括電能開(kāi)銷和網(wǎng)絡(luò)開(kāi)銷，也就是式（9）的結(jié)果是我們?cè)诒疚淖铌P(guān)心的。因此選擇了最大最小蟻群算法和本文中的算法加以比較，即將兩種算法的總體開(kāi)銷作為比較的對(duì)象。

由于模擬與實(shí)際有一定的差距，因此選擇不同規(guī)模的數(shù)據(jù)集來(lái)進(jìn)行50次模擬，并對(duì)最后的結(jié)果取平均值，以此來(lái)減小誤差。

不同規(guī)模的數(shù)據(jù)集如下:

表1 物理機(jī)和虛擬機(jī)資源配置表

表2 機(jī)器數(shù)量

算法性能的評(píng)估指標(biāo)定義為

由圖2可以看出，相比于最大最小蟻群算法，改進(jìn)的最大最小蟻群算法在系統(tǒng)的總體開(kāi)銷中有大約5%的性能提升。這是因?yàn)樵谶@個(gè)算法中，一方面我們總是選擇將虛擬機(jī)集中放置在消耗電能較小的服務(wù)器上，另一方面我們總是將通信頻率高的虛擬機(jī)放置在通信開(kāi)銷小的服務(wù)器上。既減少了電能開(kāi)銷又減少了網(wǎng)絡(luò)開(kāi)銷。因此改進(jìn)的最大最小蟻群算法在總體開(kāi)銷上才會(huì)有性能的提升。

圖2 性能提升度（百分比）

5 結(jié)語(yǔ)

本文將一種改進(jìn)的最大最小蟻群算法應(yīng)用于虛擬機(jī)的初始化放置問(wèn)題中，在保證服務(wù)質(zhì)量的前提下，可以使得整個(gè)系統(tǒng)的電能開(kāi)銷和網(wǎng)絡(luò)開(kāi)銷達(dá)到最小。實(shí)驗(yàn)結(jié)果表明，相比于最大最小蟻群算法，改進(jìn)的最大最小蟻群算法在系統(tǒng)的總體開(kāi)銷中大約有5%的性能提升。