王 娜，劉春霞，黨偉超，白尚旺

(太原科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，太原 030024)

目前學(xué)術(shù)界針對虛擬機動態(tài)遷移問題進行了大量的研究工作，主要集中在兩個方面，一是單純的虛擬機遷移策略方面，主要考慮負載、網(wǎng)絡(luò)帶寬、SLA違規(guī)、虛擬機遷移次數(shù)等性能指標(biāo)的影響；一是遷移過程中源、目的主機以及虛擬機選擇方面，利用相關(guān)的智能算法來優(yōu)化虛擬機分配與放置，減少能量消耗。為了能有效識別出過載節(jié)點，研究人員進行了深入研究。Hsu等[1]提出一種靜態(tài)閾值(Static Threshold，ST)的方法進行虛擬機遷移，該方法利用CPU利用率設(shè)定一個閾值，當(dāng)主機CPU利用率超過該閾值時判定為過載主機，進行虛擬機遷移，否則不進行遷移，該方法可以有效降低數(shù)據(jù)中心能耗。Jain等[2]提出一種負載均衡方法，通過使用較低和較高CPU利用率閾值來選擇源主機，然后將選定的虛擬機放置到耗電量最低的物理主機上，以最大限度地降低能耗。Jianrong等[3]提出一種基于負載預(yù)測的動態(tài)虛擬機整合算法，通過預(yù)測主機在下一時刻的負載來判斷主機的負載狀態(tài)，進而觸發(fā)虛擬機遷移，該方法有效降低了虛擬機遷移次數(shù)，進而降低了數(shù)據(jù)中心的能耗。上述方法都是通過基于閾值或基于預(yù)測的方法來識別熱點，具有一定的局限性，且在計算各物理主機負載時，僅僅考慮了CPU或內(nèi)存的影響。文獻[4]則證明了虛擬機遷移過程中所產(chǎn)生的能耗大小受可用帶寬的影響。因此，上述方法都沒有全面考慮虛擬機遷移過程中多重因素對能耗的影響。

有效識別出熱點只是虛擬機遷移的基礎(chǔ)，在遷移過程中，還需要找到適合遷移的虛擬機以及適當(dāng)?shù)哪康闹鳈C。Dong等[5]提出一種虛擬機分配方法，通過多目標(biāo)優(yōu)化來提高資源利用率并減少物理節(jié)點的使用數(shù)量，從而達到降低能耗的目標(biāo)。Ghribi等[6]提出了一種虛擬機分配算法和虛擬機整合算法，使用線性整數(shù)規(guī)劃算法來優(yōu)化服務(wù)器數(shù)量，降低了數(shù)據(jù)中心的總能耗。Tseng等[7]提出一種支持向量機的虛擬機遷移方法，在特定的時間完成了虛擬機最大資源利用率。Radhakrishnan等[8]提出一種使用神經(jīng)網(wǎng)絡(luò)和遺傳算法相結(jié)合的方法選擇目的主機，實現(xiàn)了數(shù)據(jù)中心能耗降低。上述方法都著重考慮了虛擬機遷移次數(shù)和能耗問題，但由于追求降低數(shù)據(jù)中心能耗可能導(dǎo)致云計算供應(yīng)商遵守違反與用戶簽訂的服務(wù)等級協(xié)議(Service Lever Agreement，SLA)，從而影響數(shù)據(jù)中心的服務(wù)質(zhì)量。

Kansal等[9]提出一種基于螢火蟲算法的虛擬機遷移技術(shù)，將虛擬機遷移過程看做是螢火蟲的生物行為，利用螢火蟲總是朝亮度最大的螢火蟲移動這一生物現(xiàn)象來實現(xiàn)虛擬機的遷移過程，將物理主機上負載最大的虛擬機遷移到亮度最大的物理節(jié)點上。該方法存在以下不足：(1)僅考慮了CPU和內(nèi)存對能耗的影響；(2)在選擇熱點時可能會陷入局部最優(yōu)解；(3)忽視服務(wù)質(zhì)量的影響。

綜上，為更好實現(xiàn)云端服務(wù)的負載均衡、容錯、優(yōu)化服務(wù)器的電能管理，本文提出一種基于改進螢火蟲算法FA_SA(Firefly algorithm and Simulated Annealing algorithm)的虛擬機遷移策略，利用模擬退火算法在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)的優(yōu)點，有效識別熱點，遷移負載最大的虛擬機到能耗最低的節(jié)點，完成遷移調(diào)度，降低數(shù)據(jù)中心能耗，同時保證云端服務(wù)質(zhì)量。

1 相關(guān)定義

1.1 算法機理

螢火蟲算法(Firefly Algorithm，F(xiàn)A)[10]是群體智能搜索算法的一種，其思想源于模擬螢火蟲晚上群聚覓食，通過散發(fā)熒光素吸引同伴的自然現(xiàn)象。在搜索空間中隨機初始化一群螢火蟲，搜索和迭代過程看作成螢火蟲個體間相互吸引和位移的過程。

在FA算法中存在兩個關(guān)鍵要素：螢火蟲的熒光亮度和個體間的吸引力。熒光亮度反映了螢火蟲位置的優(yōu)劣，亮度越高位置越好，對同伴的吸引力越強。吸引力取決于亮度和距離，故種群中亮度較低的螢火蟲尋找自己鄰域內(nèi)熒光較亮的螢火蟲并向其移動靠攏，其位置在不斷更新中完成迭代，最終聚集在亮度最高的螢火蟲周圍，即搜索空間中最優(yōu)位置附近，從而實現(xiàn)目標(biāo)優(yōu)化。

1.2 遷移過程模擬

虛擬機遷移的過程主要分為三個步驟：過載主機的判定、待遷虛擬機的選擇以及目的主機的選擇。本文將虛擬機遷移過程模擬為螢火蟲覓食的生物行為，把物理機集群看作是螢火蟲的聚集群，使虛擬機與螢火蟲個體進行對應(yīng)，待遷虛擬機看作是新加入覓食的螢火蟲，通過不斷地移動尋找到最優(yōu)位置，此時熒光最亮的螢火蟲位置即為需要選擇的目標(biāo)主機。

具體做如下定義：

(1)將數(shù)據(jù)中心看做一個螢火蟲種群。用x表示螢火蟲，即物理主機；將n表示為螢火蟲的個數(shù)，即數(shù)據(jù)中心中物理主機的個數(shù)，則數(shù)據(jù)中心中各物理主機用向量表示為xi=(x1，x2，…，xn).

(2)物理主機的亮度即為物理主機能耗值的大小。用EC(Energy Consumption)表示能耗，EC值越大，表示能耗值越大，則亮度越小；EC值越小，表示能耗值越小，則亮度越大。

(3)將兩個物理主機之間能耗的差值作為距離，即吸引力，用于判斷該主機是否為為熱點，即是否需要進行虛擬機遷移。

2 改進螢火蟲算法的遷移策略

為解決螢火蟲算法易陷入局部最優(yōu)解從而造成虛擬機無效遷移的問題，本文引入模擬退火機制，將螢火蟲算法的全局搜索和模擬退火算法的隨機搜索能力相結(jié)合，提出一種基于改進螢火蟲算法(FA_SA)的虛擬機遷移調(diào)度方法。

2.1 模擬退火機制

模擬退火算法(Simulated Annealing，SA)[11]是由美國物理學(xué)家Metropolis等人在1953年提出的，是基于蒙特卡羅(Monte Carlo)迭代求解法的一種啟發(fā)式隨機搜索算法，引入物理學(xué)中的固體退火過程，如圖1所示，隨著固體溫度越來越高，固體內(nèi)的各個粒子會變得雜亂無序，內(nèi)能會越來越大；隨著溫度降低，固體內(nèi)的各個粒子會逐漸趨于穩(wěn)定，內(nèi)能會越來越小。模擬退火算法的核心是以一定的概率接受當(dāng)前非優(yōu)解，從而跳出局部最優(yōu)解繼續(xù)搜索，進而得到全局最優(yōu)解。模擬退火算法的一般流程為：

圖1 模擬退火內(nèi)能變化[12]

(1)初始化溫度T、降溫次數(shù)M、衰減因子λ以及每個T值的迭代次數(shù)L，令k=0；

(2)隨機產(chǎn)生初始解狀態(tài)X；

(3)從X的領(lǐng)域中隨機產(chǎn)生新的狀態(tài)X′；

(4)計算目標(biāo)函數(shù)差Δ=f(X′)-f(X)，其中f(X)為優(yōu)化目標(biāo)函數(shù)；

(5)如果Δ<0，使X=X′；如果Δ≥0，且e-ΔEI(kT)≥0，θ∈(0，1)的隨機數(shù)，使X=X′；

(6)如果達到最大降溫次數(shù)M，則輸出模擬退火過程中最好的解Xbest并結(jié)束算法；否則令Tk+1=λTk，k=k+1，返回第(3)步繼續(xù)執(zhí)行。

2.2 源主機的選擇

源主機是由于過載或潛在過載需要進行虛擬機遷移的物理節(jié)點，有效選擇源主機是完成虛擬機遷移過程的關(guān)鍵。判定過程分為五步。

第一步：計算能耗值(Energy Consumption，EC).由于數(shù)據(jù)中心物理主機的能耗大小不僅與CPU和內(nèi)存有關(guān)，而且受網(wǎng)絡(luò)帶寬的影響，因此本文依據(jù)式1對物理主機的能耗進行計算，并存儲在列表中。

(1)

其中，λ表示cpu、內(nèi)存和帶寬對能耗影響的權(quán)值，滿足0<λcpu，λram，λbw<1且λcpu+λram+λbw=1，由于CPU資源是影響數(shù)據(jù)中心能耗的關(guān)鍵因素，因此，本文設(shè)定λcpu=1/2，λram=λbw=1/4；v表示運行在第i個物理節(jié)點上虛擬機的數(shù)量；u表示分配給虛擬機的總?cè)蝿?wù)數(shù)；cpuijk、ramijk和bwijk分別表示第i個物理節(jié)點上j個虛擬機運行k個任務(wù)的CPU利用率、內(nèi)存利用率和帶寬利用率；C、M和B分別表示分配給第i個物理節(jié)點的CPU值、內(nèi)存值和帶寬值。

第二步：計算物理主機的節(jié)點計算時間(Node Computation Time，NCT)。NCT表示運行該物理主機上所有任務(wù)所需要的時間。根據(jù)式(2)[5]獲得NCT值，并存儲在列表中。

④切實加強河道砂石資源費的征收與使用。各區(qū)縣水行政主管部門要嚴格按照相關(guān)規(guī)定，認真抓好砂石資源費足額征收工作，要保證“三江”河流100%、其他河流20%的砂石資源費繳入市級金庫，其他河流80%的砂石資源費繳入?yún)^(qū)縣級金庫。 同時，要切實用好河道砂石資源，將砂石資源費首先用于河道管理。

(2)

其中，NCTijk表示在第i個節(jié)點上第j個虛擬機上運行k個任務(wù)所需要的時間。

第三步：計算吸引力指數(shù)(Attraction Index，AI)。通過計算AI值來模擬螢火蟲的吸引力。AI值的存儲形式為AIi(ECi，NCTi)，其中ECi表示第i個節(jié)點的能耗值；NCTi表示第i個節(jié)點的節(jié)點計算時間。根據(jù)EC值對AI列表進行升序排列，EC值最小的節(jié)點為列表中第一個元素。

第四步：計算距離(Distance).源主機表示需要進行虛擬機遷移的物理主機，其實際是過載主機或潛在過載主機，因此，將EC值大于閾值的物理主機重新組合為新的種群List，并根據(jù)式(3)獲得距離值。

Distance=Avg(Listmin，Listmax)

(3)

其中，Listmin和Listmax分別表示List列表中的中間元素和最大元素值。

第五步：采用模擬退火算法查找源主機。

新種群中存儲的是過載主機或潛在過載主機，即潛在源主機。將List列表中EC值離距離Distance最近的物理主機作為初始解，結(jié)合模擬退火算法依據(jù)式(4)對List列表進行搜索，獲得源主機。

p=

(4)

(5)

其中，p表示接受當(dāng)前解的概率；Y(x)表示目標(biāo)函數(shù)，該函數(shù)值由EC值和該物理主機的下一刻EC值共同決定。

當(dāng)新解當(dāng)前時刻的EC值大于當(dāng)前解的EC值并且新解預(yù)測所得下一時刻的EC值大于新解的EC值時，以概率為1完全接受新解；否則，依據(jù)式(5)計算概率，并以此概率接受較差的新解。對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)值→接受或丟棄”的迭代，并最終獲得近似最優(yōu)解。

2.3 待遷虛擬機的選擇

選擇從源主機上需要遷移的虛擬機。根據(jù)式(6)計算該源主機上每個虛擬機的負載值，然后將其存儲在列表中，查找列表中的最大負載值，具有最大負載值的虛擬機就是需要進行遷移的虛擬機。

(6)

其中，jobj表示在第i個節(jié)點的第j個虛擬機上運行的任務(wù)總數(shù)量；分母表示第i個節(jié)點在Δt時間內(nèi)的能耗值。

2.4 目的主機的選擇

螢火蟲總是向熒光更亮的節(jié)點移動，因此，如果一個節(jié)點的EC值最低，那么這個節(jié)點就是最亮的節(jié)點，即AI列表中的第一個元素是最亮的節(jié)點，也就是說，該節(jié)點為目標(biāo)主機節(jié)點。

2.5 距離更新

每次獲得源主機后需要一次迭代更新以便完成下一次的虛擬機遷移，該更新即為距離的更新。根據(jù)式(7)完成距離的更新。

Distancet+1=Distancet+Loadij+ε

(7)

其中，Distancet+1和Distancet分別表示第t時刻和第t+1時刻的距離值；Loadij表示當(dāng)前虛擬機的負載值；ε表示高斯分布誤差。

融合了模擬退火機制的虛擬機遷移調(diào)度算法的流程圖如圖2所示。

圖2 改進螢火蟲算法的流程圖

3 實驗與結(jié)果分析

使用Cloudsim仿真平臺作為實驗環(huán)境。該實驗?zāi)M構(gòu)造了一個由800臺物理主機組成的數(shù)據(jù)中心，這些物理主機分為兩類：400臺類型為HP ProLiant ML110 G4(Intel Xeon 3040，2 Cores×1 860 MHz，4 GB)的物理主機和400臺類型為HP ProLiant ML110 G5(Intel Xeon 3075，2 Cores×2 660 MHz，4 GB)的物理主機。在這些物理主機上，運行如表1所示的四種類型的虛擬機。為了使運行在該平臺上的物理主機和虛擬機負載更接近現(xiàn)實情況，使用了PlantLab CoMon項目提供的虛擬機監(jiān)測數(shù)據(jù)，該數(shù)據(jù)包含了分布在全球500多個不同地區(qū)的1 000多個虛擬機的監(jiān)測信息。本次實驗從2011年3月到4月中隨機選擇10天的數(shù)據(jù)作為實驗數(shù)據(jù)，配置情況如表1所示。

表1 虛擬機配置

本文使用數(shù)據(jù)中心能耗(Energy Consumption，EC)、服務(wù)等級協(xié)議違例率(SLA Violations，SLAV)、虛擬機遷移次數(shù)(Migrs)以及服務(wù)質(zhì)量和能耗的綜合評價(Energy and SLA Violation，ESV)作為評價指標(biāo)。其中，EC值越低表示節(jié)能效果越好；SLAV用式(8)計算，SLAV值越低表示其服務(wù)質(zhì)量越好；ESV的值通過式(9)獲得，該指標(biāo)值越低表示數(shù)據(jù)中心的能耗和服務(wù)質(zhì)量的綜合表現(xiàn)越好。

(8)

ESV=EC×SLAV

(9)

其中，N和V分別表示物理主機的個數(shù)和虛擬機的數(shù)量；Toi表示該物理主機過載的總時間；Tvi表示該虛擬機完成遷移所花費的時間；Tai表示該物理主機總的活動時間。

首先，在同等條件下分別從單純考慮CPU和內(nèi)存因素以及綜合考慮CPU、內(nèi)存和帶寬因素對能耗、平均遷移時間的影響進行對比實驗，如圖3所示。由圖可知，在虛擬機平均遷移時間方面，綜合考慮CPU、內(nèi)存和帶寬所使用的平均遷移時間更短。當(dāng)考慮帶寬因素時，整個虛擬機遷移過程產(chǎn)生的能耗值有所下降，具有一定的優(yōu)化效果。

利用螢火蟲算法選擇源主機階段，只是選擇離距離值最近的物理主機作為源主機，具有一定的局限性，本文在此階段融入模擬退火算法，避免在源主機的選擇過程中陷入局部最優(yōu)解。

分別使用基本螢火蟲算法和融入模擬退火算法的螢火蟲算法進行實驗，得到遷移時間的標(biāo)準方差值，如圖4所示。由圖可知，使用基本螢火蟲算法獲得的遷移時間標(biāo)準方差值大多數(shù)情況下大于使用融入模擬退火算法的螢火蟲算法獲得的遷移時間標(biāo)準方差值，說明融入模擬退火算法后，虛擬機遷移時間有所下降，即在一定程度上提高了虛擬機的遷移效率。

通過實驗，對文獻[1]提出的ST方法、文獻[13]提出局部加權(quán)回歸(the Local Regression，LR)法、FA方法和FA_SA所產(chǎn)生的能耗以及違例率進行對比，對比結(jié)果如表2和表3所示。其中，F(xiàn)A_SA方法對物理主機負載進行預(yù)測完成虛擬機遷移，在一定程度上降低了數(shù)據(jù)中心能耗，并有效降低了SLA違例率。

由表2和表3可以看出，ST方法在一定程度上有效的降低了數(shù)據(jù)中心的能耗，但該方法的違例率卻明顯的上升；LR方法雖然在數(shù)據(jù)中心的能耗上有所提升，但其違例率卻有明顯的下降；而FA方法以及FA_SA方法在數(shù)據(jù)中心能耗和違例率兩方面均有所提升，既有效地降低了數(shù)據(jù)中心能耗又保證了服務(wù)質(zhì)量，其中，F(xiàn)A_SA方法較FA方法在降低數(shù)據(jù)中心能耗和提高服務(wù)質(zhì)量兩方面均有更明顯的效果。

圖5和圖6分別表示使用各算法時數(shù)據(jù)中心的能耗變化以及SLA違例率變化。由圖5和圖6可知，使用LR算法時數(shù)據(jù)中心產(chǎn)生的能耗最大，但其違例率此時是最小的；當(dāng)使用ST算法時，數(shù)據(jù)中心產(chǎn)生的能耗值最小，但其違例率是最大的；這兩種方法只能單方面保證數(shù)據(jù)中心的能耗值降低或者服務(wù)質(zhì)量提高。使用FA算法雖然產(chǎn)生的能耗值比ST算法高，但其違例率卻較低，在一定程度上既達到了數(shù)據(jù)中心能耗降低由保證了數(shù)據(jù)中心的服務(wù)質(zhì)量。相較FA算法，本文提出的FA_SA算法能耗值又有所下降，效果較好。

圖5 EC變化

圖6 SLAV變化

圖7對比了使用各算法時虛擬機遷移次數(shù)的變化。由圖7可知，使用LR算法時虛擬機遷移次數(shù)最多，所產(chǎn)生的能耗值也最大；使用本文提出的FA_SA算法所產(chǎn)生的虛擬機遷移次數(shù)在大多數(shù)情況下最小，相比FA算法，遷移次數(shù)多可能是因為數(shù)據(jù)集選擇不當(dāng)造成的。

圖8對比了使用各算法時ESV的變化。ESV是評價算法是否適用于數(shù)據(jù)中心虛擬機遷移的綜合指標(biāo)。由圖8可知，使用ST方法時，ESV最大，表示該算法不能很好適用于數(shù)據(jù)中心虛擬機遷移過程，所提供的服務(wù)質(zhì)量較低；而本文提出的FA_SA算法的ESV值最低，表示該算法能較好的適用于該過程，為用戶提供較好的服務(wù)質(zhì)量，優(yōu)化效果更明顯。

圖8 ESV變化

4 結(jié)論

本文綜合考慮CPU、內(nèi)存和帶寬等因素對能耗的影響，結(jié)合模擬退火算法，提出一種基于改進螢火蟲算法的虛擬機調(diào)度策略，利用螢火蟲算法的全局搜索和模擬退火算法局部搜索的優(yōu)點選擇待遷源主機，將源主機上負載最大的虛擬機遷移到能耗最低的目的節(jié)點。通過與ST、LR和FA算法進行對比實驗，結(jié)果表明，提出的FA_SA算法方法不僅有效降低了數(shù)據(jù)中心能耗、虛擬機遷移次數(shù)、SLA違例率，而且保證了服務(wù)質(zhì)量，達到了較明顯的優(yōu)化效果。