裴 多

(重慶市綜合經(jīng)濟(jì)研究院 信息化研究中心，重慶 401147)

0 引 言

云計(jì)算的核心技術(shù)包括靈活接入的移動(dòng)終端、硬件技術(shù)、海量存儲(chǔ)技術(shù)、虛擬化技術(shù)以及分布式并行計(jì)算。云平臺(tái)靈活高效地資源配置和管理得益于上述各種技術(shù)的成熟。其中，虛擬化技術(shù)實(shí)現(xiàn)對(duì)數(shù)據(jù)中心存在的零散資源進(jìn)行有效整合，并對(duì)虛擬化后的抽象資源進(jìn)行統(tǒng)一管理、配置和監(jiān)控，一定程度上改善了云服務(wù)提供商資源利用率低和運(yùn)營(yíng)成本高的問(wèn)題。然而，虛擬機(jī)的放置是一個(gè)從虛擬機(jī)到物理主機(jī)映射的過(guò)程，虛擬機(jī)的放置優(yōu)化問(wèn)題，是多個(gè)目標(biāo)相互作用相互影響，復(fù)雜困難的組合優(yōu)化問(wèn)題，因此，解決多目標(biāo)虛擬機(jī)部署策略是云數(shù)據(jù)中心提高資源利用率[1]和節(jié)省能耗[2]的關(guān)鍵。Liu等[3]提出了基于蟻群算法的虛擬機(jī)放置算法，該算法通過(guò)減少物理服務(wù)器的運(yùn)行數(shù)量以及提高物理資源的利用率來(lái)降低系統(tǒng)的能耗問(wèn)題。文獻(xiàn)[4]則采用生物物理學(xué)的優(yōu)化方法來(lái)放置虛擬機(jī)，通過(guò)該方法減少資源的浪費(fèi)以及能耗。文獻(xiàn)[5]提出了基于緩存競(jìng)爭(zhēng)意識(shí)的虛擬機(jī)放置算法。

線性規(guī)劃方法是虛擬機(jī)放置的傳統(tǒng)分析方法。Chen等[6]采用整數(shù)線性規(guī)劃來(lái)對(duì)虛擬機(jī)的放置與遷移進(jìn)行求解，用于解決云中虛擬機(jī)整合時(shí)帶來(lái)的緩存競(jìng)爭(zhēng)問(wèn)題。文獻(xiàn)[7]以提高鏈路利用率為目的，采用線性規(guī)劃來(lái)描述路線分配問(wèn)題，并提出基于多項(xiàng)式時(shí)間的虛擬機(jī)放置的啟發(fā)式算法。此外，文獻(xiàn)[8]也采用整數(shù)線性規(guī)劃來(lái)描述了面向服務(wù)的虛擬機(jī)放置問(wèn)題，并使用樹(shù)算法來(lái)得到虛擬機(jī)的放置方案，從而降低通信成本以及建設(shè)成本。

遺傳算法是另外一種虛擬機(jī)放置優(yōu)化算法。Tang等[9]提出了基于遺傳算法的虛擬機(jī)放置算法，該算法綜合考慮了物理機(jī)器以及通信網(wǎng)絡(luò)帶來(lái)的能源消耗問(wèn)題。同時(shí)，為提高遺傳算法的效率，提出了混合的遺傳算法。文獻(xiàn)[10]研究了動(dòng)態(tài)環(huán)境下面向代理服務(wù)器的虛擬機(jī)放置問(wèn)題，綜合考慮了變化的資源供應(yīng)、提供商的定價(jià)以及租戶的動(dòng)態(tài)需求三方面因素，使用遺傳算法得到高質(zhì)量的可伸縮性強(qiáng)的放置方案。

約束規(guī)劃方法也被用于虛擬機(jī)放置。為提高數(shù)據(jù)的安全性，文獻(xiàn)[11]通過(guò)研究分析數(shù)據(jù)存在的安全隱患來(lái)構(gòu)建信息泄露約束條件，在保證滿足該約束條件下進(jìn)行虛擬機(jī)的放置。由于之前的虛擬機(jī)放置研究沒(méi)有考慮物理機(jī)器擁有多個(gè)處理器的情況，導(dǎo)致單個(gè)物理機(jī)器的調(diào)度變得更加復(fù)雜。因此，文獻(xiàn)[12]采用約束規(guī)劃來(lái)描述物理機(jī)器中多個(gè)處理機(jī)的調(diào)度問(wèn)題，并使用改進(jìn)后的約束規(guī)劃方法求解虛擬機(jī)的放置問(wèn)題。

虛擬機(jī)部署策略經(jīng)常被描述為向量裝箱問(wèn)題的變體問(wèn)題，這是一個(gè)NP-hard問(wèn)題。為了解決這個(gè)問(wèn)題，各種啟發(fā)式算法被提出。Li等[13]在虛擬機(jī)放置問(wèn)題時(shí)，考慮了由網(wǎng)絡(luò)通信量以及物理機(jī)器的利用造成的開(kāi)銷(xiāo)，采用基于二進(jìn)制搜索算法來(lái)確定所需物理機(jī)器的個(gè)數(shù)以及放置問(wèn)題。文獻(xiàn)[14]提出了基于信息改進(jìn)的煙花算法(IEFWA)。作者以降低數(shù)據(jù)中心的能耗問(wèn)題為目的，結(jié)合IEFWA算法與基于生物地理學(xué)的優(yōu)化算法(BBO)來(lái)求解虛擬機(jī)的放置問(wèn)題。

上述研究成果都把虛擬機(jī)部署策略用單一目標(biāo)實(shí)現(xiàn)，然而在云數(shù)據(jù)中心，為了提高資源利用率和降低能耗，需要考慮多個(gè)優(yōu)化目標(biāo)。因此，本文提出了基于蟻群智能的虛擬機(jī)多目標(biāo)優(yōu)化部署策略，首先給出多目標(biāo)優(yōu)化問(wèn)題的描述，然后建立優(yōu)化目標(biāo)函數(shù)，采用蟻群算法對(duì)雙目標(biāo)函數(shù)求解，最后與降序首次適應(yīng)算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。

1 蟻群算法

1.1 基本蟻群系統(tǒng)的機(jī)制原理

基本蟻群算法的優(yōu)化機(jī)理包括兩個(gè)階段：適應(yīng)階段和協(xié)作階段。首先是適應(yīng)階段，每只螞蟻依據(jù)自己對(duì)信息的累積選擇和調(diào)整其認(rèn)為最優(yōu)的路徑，路徑上的信息量越大，說(shuō)明選擇該路徑的螞蟻越多；在協(xié)作階段，螞蟻之間通過(guò)信息素共享信息，以便產(chǎn)生更能優(yōu)化性能的解，與自動(dòng)機(jī)的學(xué)習(xí)機(jī)理一致。

1.2 基本蟻群系統(tǒng)的數(shù)據(jù)模型

螞蟻在探索路徑的過(guò)程中，依據(jù)各條路徑上信息量的多少?zèng)Q定其跳轉(zhuǎn)的方向。禁忌表tabk用于標(biāo)記第k只螞蟻已經(jīng)走過(guò)的元素，隨著螞蟻對(duì)路徑的不斷探索，禁忌表tabk進(jìn)行動(dòng)態(tài)調(diào)整。在向最優(yōu)路徑進(jìn)化的過(guò)程中，螞蟻依據(jù)各條路徑上積累的信息量和路徑的自身的啟發(fā)信息來(lái)權(quán)衡當(dāng)前路徑是最優(yōu)路徑的概率。

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

蟻群系統(tǒng)具有方便和其它算法相結(jié)合，較強(qiáng)的魯棒性等優(yōu)點(diǎn)，但是算法探索時(shí)間長(zhǎng)、容易收斂于局部最優(yōu)解是尤為明顯的缺點(diǎn)。

精英策略的螞蟻系統(tǒng)[15](elitist ant system，EAS)，基于排列的螞蟻系統(tǒng)[16](rank-based AS，ASrank)，最大最小螞蟻系統(tǒng)[17](MAX-MIN ant system，MMAS)都對(duì)AS進(jìn)行了少量的修改而獲得了更好的性能。1997年，螞蟻算法的創(chuàng)始人M.Dorigo又提出了一種具有全新機(jī)制的蟻群算法[18](ant colony system，ACS)，這是蟻群算法發(fā)展史上的又一新突破。

ACS和AS之間存在以下3方面的不同：

(1)采用一種偽隨機(jī)比例規(guī)則確定下一個(gè)要選擇的元素，在開(kāi)發(fā)當(dāng)前路徑與探索新路徑之間權(quán)衡。

(2)信息素全局更新規(guī)則只在當(dāng)前探索的最優(yōu)路徑上消耗與釋放信息素。

(3)螞蟻每次跳轉(zhuǎn)到一個(gè)元素后，按照信息素局部更新規(guī)則，都會(huì)揮發(fā)該邊上一定量的信息素，以此來(lái)增大其它螞蟻探索剩余路徑的概率。

與AS相比，蟻群系統(tǒng)ACS重新定義了狀態(tài)轉(zhuǎn)移規(guī)則，信息素全局更新規(guī)則以及信息素局部更新規(guī)則。

(1)狀態(tài)轉(zhuǎn)移規(guī)則

一只位于元素i的螞蟻要確定下一個(gè)移動(dòng)到的元素，應(yīng)用式(1)和式(2)給出的規(guī)則，即偽隨機(jī)比例規(guī)則

(1)

其中

(2)

式中：η(i,j)為啟發(fā)函數(shù)，代表螞蟻從元素i跳轉(zhuǎn)到元素j的期望程度值。β為期望啟發(fā)式因子，用于調(diào)整啟發(fā)信息在路徑選擇時(shí)的重要性，反映出螞蟻在探索路徑的過(guò)程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，β值越大，表示螞蟻偏向于貪心規(guī)則選擇路徑的可能性越大。集合(C-tabk)是第k只螞蟻下一步可以選擇的元素集合。q為在[0,1]區(qū)間均勻分布的隨機(jī)數(shù)，q0是決定了利用先驗(yàn)知識(shí)與探索新路徑之間的相對(duì)重要性。

(2)信息素全局更新規(guī)則

ACS運(yùn)用了更加大膽的規(guī)則確定路徑上的信息，即只增大全局最優(yōu)路徑上的信息素

τij(t)=(1-ρ)×τij+ρ×Δτb(i,j)

(3)

其中

(4)

式中：ρ是信息素?fù)]發(fā)參數(shù)，取值范圍為：0<ρ<1，Cb為從尋路開(kāi)始到當(dāng)前為止全局最優(yōu)的路徑長(zhǎng)度。

(3)信息素局部更新規(guī)則

ACS引入了負(fù)反饋機(jī)制，每當(dāng)一只螞蟻由一個(gè)元素跳轉(zhuǎn)到另一個(gè)元素時(shí)，該路徑上的信息素將依據(jù)式(5)揮發(fā)掉一部分，實(shí)現(xiàn)信息素的局部更新，以此降低已經(jīng)走過(guò)的路徑再次被選定的幾率

τij=(1-ξ)×τij+ξ×τ0,0<ξ<1

(5)

ACS算法[18]在搜索時(shí)間長(zhǎng)、易陷于局部最優(yōu)解兩個(gè)方面都有明顯改善。

2 雙目標(biāo)優(yōu)化模型的建立

虛擬機(jī)放置優(yōu)化問(wèn)題是一個(gè)多目標(biāo)優(yōu)化問(wèn)題。根據(jù)前面對(duì)多目標(biāo)問(wèn)題描述，我們首先給出兩個(gè)優(yōu)化目標(biāo)：資源模型和能耗模型。

資源模型主要考慮兩種資源CPU和內(nèi)存。物理主機(jī)資源利用率和虛擬機(jī)放置有很大關(guān)系，為了實(shí)現(xiàn)多維資源綜合利用[19]，下面給出計(jì)算資源未利用模型

(6)

式中：wj為第j臺(tái)物理主機(jī)的資源浪費(fèi)率，P表示CPU資源，M表示內(nèi)存資源，l是未利用資源比例，T是主機(jī)最高資源利用率。

目前研究表明能耗和CPU利用率是線性關(guān)系[20]，為了節(jié)省能耗，物理主機(jī)的能耗忽略不計(jì)。第j臺(tái)物理主機(jī)的能耗可以表示為

(7)

式中：u為資源利用率。

上面給出了資源模型和能耗模型，為了提高資源未使用利用率和降低能耗，我們建立如下目標(biāo)優(yōu)化函數(shù)。r表示請(qǐng)求資源，v表示第v臺(tái)虛擬機(jī)，S表示放置在第j臺(tái)主機(jī)上的虛擬機(jī)的集合

(8)

(9)

約束條件：①每臺(tái)虛擬機(jī)只可以放置在一臺(tái)物理主機(jī)上；②各個(gè)虛擬機(jī)請(qǐng)求資源的總和不可以超過(guò)最高資源利用率；③每個(gè)虛擬機(jī)的資源請(qǐng)求不會(huì)超過(guò)最高資源利用率。

3 雙目標(biāo)優(yōu)化模型求解算法描述

該小節(jié)尋找提高資源利用率和節(jié)省能耗的虛擬機(jī)放置方案，提出基于ACS雙目標(biāo)虛擬機(jī)放置(bi-objective VM placement ACS，bi-OVMPACS)算法。

3.1 信息素和啟發(fā)信息定義

設(shè)有m臺(tái)虛擬機(jī)放置到n臺(tái)物理主機(jī)，為了記錄虛擬機(jī)分配到物理主機(jī)的信息素定義一個(gè)m行n列的矩陣τm×n,τij表示虛擬機(jī)i放置到主機(jī)j的信息素。在初始化階段，τm×n的值為

(10)

其中

(11)

定義矩陣ηm×n記錄虛擬機(jī)放置到主機(jī)的啟發(fā)信息，ηij表示虛擬機(jī)i放置到主機(jī)j的啟發(fā)信息。虛擬機(jī)放置到主機(jī)要同時(shí)考慮資源利用率和能耗兩個(gè)優(yōu)化目標(biāo)，因此

(12)

(13)

(14)

3.2 虛擬機(jī)選擇規(guī)則

根據(jù)ACS的偽隨機(jī)比例狀態(tài)轉(zhuǎn)移規(guī)則，定義虛擬機(jī)選擇規(guī)則

(15)

其中

(16)

式中：q為[0,1]之間的隨機(jī)數(shù)，q0是[0,1]之間的一個(gè)常數(shù)，α為信息素和啟發(fā)信息的相對(duì)重要程度，ppej是選擇某個(gè)虛擬機(jī)的概率，Ωj則是待放置虛擬機(jī)可以放置到主機(jī)j的集合。

3.3 信息素更新規(guī)則

信息素更新規(guī)則是影響虛擬機(jī)放置的重要部分，螞蟻經(jīng)過(guò)的路徑信息素增加，同時(shí)信息素隨時(shí)間揮發(fā)，因此信息素可能增加可能減少。信息素的揮發(fā)有利于避免算法快速收斂于局部最優(yōu)，同時(shí)擴(kuò)大搜索空間。該算法信息素更新包括兩部分：信息素局部和信息素全局更新。

式(17)表示虛擬機(jī)i放置到主機(jī)j后信息素局部信息素更新規(guī)則，β表示局部信息素?fù)]發(fā)參數(shù)

τij(t)=(1-β)×τij(t-1)+β×τ0

(17)

當(dāng)所有的螞蟻都找到了一條路徑之后，按照上文介紹的比較規(guī)則，選擇最優(yōu)路徑H進(jìn)行信息素全局更新，更新規(guī)則如下

(18)

4 實(shí)驗(yàn)結(jié)果與分析

4.1 蟻群行為和參數(shù)對(duì)算法性能影響的分析

在蟻群算法中，參數(shù)是影響算法求解性能和效率的關(guān)鍵因素之一。目前，蟻群算法中的參數(shù)設(shè)置暫且沒(méi)有系統(tǒng)的理論依據(jù)和通用的操作方法，一般情況下依據(jù)經(jīng)驗(yàn)和大量實(shí)驗(yàn)數(shù)據(jù)確定參數(shù)值。下面就bi-OVMPACS算法中的參數(shù)α，β，γ，antNum對(duì)性能的影響進(jìn)行簡(jiǎn)要分析。

(1)參數(shù)α。信息素是表示先驗(yàn)信息的載體，而啟發(fā)信息是表示未來(lái)信息的載體[21,22]。參數(shù)α并不用來(lái)影響信息素和啟發(fā)信息，而是用以控制二者之間的相互作用。根據(jù)式(15)、式(16)可知，當(dāng)α=0時(shí)，演變?yōu)闊o(wú)信息素影響的bi-OVMPACS算法；當(dāng)α=1時(shí)，演變?yōu)闊o(wú)啟發(fā)信息影響的bi-OVMPACS算法。

(2)參數(shù)β，γ。在蟻群算法中，各只螞蟻之間通過(guò)信息素進(jìn)行合作，以增大迅速發(fā)現(xiàn)最優(yōu)解的概率。在bi-OVMPACS算法中，參數(shù)β和參數(shù)γ都與信息素更新密切相關(guān)。信息素局部更新規(guī)則運(yùn)用負(fù)反饋機(jī)理，以信息素局部更新因子β，局部調(diào)整信息素，減小再選擇已經(jīng)走過(guò)路徑的概率，增大對(duì)新路徑探索的概率。信息素全局更新規(guī)則運(yùn)用“精英策略”，只對(duì)當(dāng)前狀況下最優(yōu)路徑上的信息素進(jìn)行調(diào)整，而其它路徑上的信息素不變。如果信息素全局更新因子γ過(guò)大，會(huì)造成算法的隨機(jī)性和全局搜索能力，而且已探索過(guò)的路徑再次被選定的幾率太大；如果γ太小，雖然算法的隨機(jī)性和全局探索能力有所增強(qiáng)，但是探索到最優(yōu)路徑的時(shí)間消耗太多。

(3)參數(shù)antNum。螞蟻數(shù)antNum值大，能夠增加算法的全局探索能力和穩(wěn)定性，然而antNum值太大，造成大量的曾經(jīng)被確定的路徑上的信息量趨于均值，算法收斂速度減慢。反之，antNum太小，造成未來(lái)被探索的路徑上的信息量接近于0，減小了全局探索的隨機(jī)性，雖然收斂速度快，但算法的穩(wěn)定性較差。

4.2 實(shí)驗(yàn)參數(shù)

bi-OVMPACS算法實(shí)驗(yàn)參數(shù)取值見(jiàn)表1。

表1 bi-OVMPACS算法實(shí)驗(yàn)參數(shù)值

設(shè)置虛擬機(jī)選擇規(guī)則中的參數(shù)α=0.5，使先驗(yàn)信息素和后驗(yàn)信息素同等重要；信息素更新規(guī)則中的參數(shù)β=γ=0.4；根據(jù)Dorigo M等[18]的研究設(shè)置螞蟻數(shù)antNum與虛擬機(jī)數(shù)之比為2∶3；迭代次數(shù)itNum=20。

4.3 實(shí)驗(yàn)結(jié)果對(duì)比及分析

為了驗(yàn)證bi-OVMPACS算法對(duì)虛擬機(jī)放置目標(biāo)函數(shù)的優(yōu)化效果和當(dāng)云數(shù)據(jù)中心有大規(guī)模虛擬機(jī)請(qǐng)求時(shí)的可擴(kuò)展性，本文共設(shè)計(jì)了兩組實(shí)驗(yàn)方案，分別為虛擬機(jī)放置優(yōu)化目標(biāo)對(duì)比實(shí)驗(yàn)和虛擬機(jī)放置可擴(kuò)展性實(shí)驗(yàn)。虛擬機(jī)放置優(yōu)化目標(biāo)對(duì)比實(shí)驗(yàn)在請(qǐng)求的虛擬機(jī)和負(fù)載主機(jī)情況一致的情況下，與降序首次適應(yīng)算法比較兩個(gè)優(yōu)化目標(biāo)：能耗和資源利用率。bi-OVMPACS算法的可擴(kuò)展性實(shí)驗(yàn)分別在兩種不同類(lèi)型虛擬機(jī)不同請(qǐng)求數(shù)量的情況下，對(duì)比螞蟻搜索到一條可行路徑的時(shí)間。

虛擬機(jī)放置優(yōu)化目標(biāo)實(shí)驗(yàn)，與降序首次適應(yīng)算法進(jìn)行實(shí)驗(yàn)對(duì)比。降序首次適應(yīng)算法放置虛擬機(jī)的主要思想是，先將虛擬機(jī)從大到小排序，然后按照排列順序?qū)⑻摂M機(jī)映射到主機(jī)。按主機(jī)啟用順序，如果能找到放置當(dāng)前虛擬機(jī)而且是最早啟動(dòng)的主機(jī)，則將當(dāng)前虛擬機(jī)放置到該主機(jī)；否則，啟動(dòng)另一臺(tái)主機(jī)放置當(dāng)前虛擬機(jī)。FFD算法的主要的運(yùn)算時(shí)間是用來(lái)對(duì)虛擬機(jī)進(jìn)行排序，故其時(shí)間復(fù)雜度是O(nlogn)。

虛擬機(jī)請(qǐng)求實(shí)例采用3.2小節(jié)介紹的偽隨機(jī)方式產(chǎn)生，總共產(chǎn)生200個(gè)虛擬機(jī)請(qǐng)求。在參數(shù)P，stdCPU，stdMem一定的條件下，F(xiàn)FD算法與bi-OVMPACS算法虛擬機(jī)放置優(yōu)化目標(biāo)對(duì)比實(shí)驗(yàn)，見(jiàn)表2。

表2 FFD算法與bi-OVMPACS算法優(yōu)化目標(biāo)對(duì)比實(shí)驗(yàn)

上述實(shí)驗(yàn)結(jié)果表明：在同等條件下，與FFD放置算法相比，bi-OVMPACS算法對(duì)虛擬機(jī)放置目標(biāo)有明顯改善。當(dāng)虛擬機(jī)請(qǐng)求的CPU和內(nèi)存平均值一定時(shí)，目標(biāo)函數(shù)值隨CPU和內(nèi)存的相關(guān)數(shù)增大而減小，反映出不同虛擬機(jī)類(lèi)型對(duì)目標(biāo)函數(shù)的影響；當(dāng)虛擬機(jī)請(qǐng)求的CPU和內(nèi)存平均值不同時(shí)，目標(biāo)函數(shù)隨虛擬機(jī)請(qǐng)求值的增大而增大。因此，bi-OVMPACS算法能夠在一定程度上實(shí)現(xiàn)云數(shù)據(jù)中心能耗和資源利用率同時(shí)優(yōu)化的虛擬機(jī)放置問(wèn)題。

bi-OVMPACS算法的可擴(kuò)展性實(shí)驗(yàn)，分別對(duì)比了虛擬機(jī)請(qǐng)求類(lèi)型為25%和45%，數(shù)目從200增加到2000，參數(shù)stdP值為0.5的情況下，螞蟻探索到一條可行路徑的時(shí)間，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 bi-OVMPACS算法的可擴(kuò)展性實(shí)驗(yàn)

上述實(shí)驗(yàn)結(jié)果表明：虛擬機(jī)請(qǐng)求平均值為25%的探索時(shí)間少于平均值為45%，因?yàn)槌休d平均值為45%的虛擬機(jī)需要啟動(dòng)更多的主機(jī)。隨著虛擬機(jī)請(qǐng)求數(shù)量的增加，螞蟻探索到一條路徑的時(shí)間可以在1 min內(nèi)完成，在人們可以接受的范圍內(nèi)。因此，bi-OVMPACS算法適合大規(guī)模數(shù)據(jù)中心的虛擬機(jī)放置。

5 結(jié)束語(yǔ)

本文首先對(duì)多目標(biāo)優(yōu)化問(wèn)題進(jìn)行了詳細(xì)描述，并且介紹了現(xiàn)有的幾種虛擬機(jī)放置算法，分析了它們?cè)谔摂M機(jī)放置中存在的問(wèn)題，并在此基礎(chǔ)上綜合考慮需要優(yōu)化的CPU和內(nèi)存兩種資源，提出了基于蟻群智能的優(yōu)化能耗和資源利用率的雙目標(biāo)虛擬機(jī)放置模型。然后簡(jiǎn)要介紹了基礎(chǔ)蟻群系統(tǒng)和改進(jìn)的蟻群系統(tǒng)，詳細(xì)闡述了該算法的實(shí)現(xiàn)過(guò)程。最后，通過(guò)對(duì)比實(shí)驗(yàn)，驗(yàn)證了本文提出的算法在對(duì)虛擬機(jī)放置優(yōu)化目標(biāo)的有效性和該算法的可擴(kuò)展性上具有一定的優(yōu)越性。