王亞寧 苑春苗 孫學(xué)梅

(天津工業(yè)大學(xué)計算機科學(xué)與軟件學(xué)院 天津 300387)

?

云計算中基于多種群蟻群算法的虛擬機整合

王亞寧 苑春苗*孫學(xué)梅

(天津工業(yè)大學(xué)計算機科學(xué)與軟件學(xué)院 天津 300387)

在云計算的發(fā)展研究中，數(shù)據(jù)中心的高能耗問題得到了廣泛的關(guān)注，而虛擬機整合是解決數(shù)據(jù)中心高能耗問題的手段之一。其思想是通過將一些物理機上的虛擬機遷移到其他活躍的物理機上使得一些物理機切換到低能耗模式或睡眠模式，從而降低云數(shù)據(jù)中心的能耗。首次將多種群蟻群算法應(yīng)用于虛擬機整合，提出基于多種群蟻群算法的虛擬機整合算法。該算法通過特定的目標函數(shù)尋找一個近似最優(yōu)解。通過仿真實驗驗證了該算法在降低能量消耗和減少虛擬機遷移次數(shù)方面優(yōu)于現(xiàn)存的兩種較優(yōu)的虛擬機整合算法。

數(shù)據(jù)中心 能量消耗 虛擬機整合 多種群蟻群

0 引 言

云計算作為近來計算機工業(yè)領(lǐng)域的一大重要變革，其發(fā)展迅速，為用戶提供幾乎無限的虛擬的計算、存儲和網(wǎng)絡(luò)等資源。為了滿足日益增長的用戶需求，云數(shù)據(jù)中心的大小和能量消耗在不斷增加[1],如美國能源部報告[2]指出，一個典型的數(shù)據(jù)中心的能耗占全美所有能耗的1.5%，并且仍以12%的速度增長。高能耗不僅轉(zhuǎn)化為高的運行成本，還導(dǎo)致高的碳排放。因此，數(shù)據(jù)中心的能量消耗問題已成為一個急需解決的問題。

近年來，已有一些嘗試來減少數(shù)據(jù)中心的能耗[3-4]，一種有效且常用的方法是虛擬機整合。虛擬機整合是指根據(jù)虛擬機的資源需求，通過虛擬機遷移將其放置到更少的服務(wù)器上，進而將部分服務(wù)器關(guān)閉或處于低功耗狀態(tài)，從而減小數(shù)據(jù)中心的能源開銷。目前應(yīng)用于虛擬機整合的算法有基于貪心算法、基于蟻群算法等啟發(fā)式算法。在基于貪心算法的啟發(fā)式算法中，文獻[5]使用貪心算法來確定負載的虛擬機整合到輕載的物理機上的順序，文獻[6]為了保持物理機之間的負載平衡使用了最小負載的負載平衡算法。另外在基于蟻群算法的啟發(fā)式算法中，文獻[7]將虛擬機整合看作多目標組合優(yōu)化問題，提出基于蟻群系統(tǒng)的虛擬機整合算法(ACS-VMC)，應(yīng)用自適應(yīng)在線啟發(fā)式優(yōu)化算法[9]得到一個近似最優(yōu)解，該算法是目前利用蟻群算法解決虛擬機整合問題中較優(yōu)的方法之一。文獻[8]中將蟻群系統(tǒng)與基于向量代數(shù)的服務(wù)器資源利用率捕捉技術(shù)[10]結(jié)合，提出基于向量代數(shù)的虛擬機整合算法(AVVMC)。該算法的主要思想是設(shè)置上下利用率閾值并保持它們之間的一個節(jié)點的總CPU利用率。當利用率超過上閾值時，虛擬機是負載平衡再分配，當利用率低于下閾值時，虛擬機是整合再分配。但是在以上文獻中都是以單種群作為考慮的方向，相比較多種群蟻群算法(MACA)[11]在解的多樣性上會有欠缺,在進行虛擬機整合時容易造成局部最優(yōu)的問題，進而對減少能耗和虛擬機遷移次數(shù)造成一定的影響。

本文中，首次將多種群蟻群算法引入到虛擬機整合問題中，提出基于多種群蟻群算法的虛擬機整合算法(MACA-VMC)。該算法改進了貪心算法和蟻群算法在虛擬機整合過程中的缺陷。MACA-VMC算法利用人造螞蟻整合虛擬機，其思想是根據(jù)當前資源需求來減少活躍的物理機的數(shù)量，這些螞蟻通過特定的目標函數(shù)并行地建立遷移計劃。為了評估算法的可行性，我們通過CloudSim[12]模擬真實工作負載的軌跡，分別與上文提到的ACS-VMC算法和AVVMC算法作比較，仿真結(jié)果表明MACA-VMC在減少能耗和虛擬機遷移次數(shù)方面要勝過ACS-VMC和AVVMC。

1 系統(tǒng)模型

(1) 如果當前CPU利用率超過了環(huán)境中物理機的容量，那么這個物理機就可以定義為超載物理機。

(2) 如果預(yù)測的CPU利用率大于CPU可利用的容量，這個物理機視為預(yù)測超載物理機。

(3) 如果當前CPU利用率的值低于CPU總利用率的閾值，此物理機為輕載物理機。根據(jù)研究分析，一般當閾值達到50%時為最好結(jié)果。

(4) 其他各種運行狀態(tài)的物理機都定義為標準物理機。

每一個物理機都包括一個多核的CPU。CPU的性能可以按照每秒處理的百萬級的機器語言指令數(shù)(MIPS)來定義。在任意一個給定的時間，一個云數(shù)據(jù)中心經(jīng)常同時為很多個用戶提供服務(wù)。用戶提交他們的請求給物理機，然后物理機把任務(wù)分配給N個虛擬機。每一個請求的長度有成千上萬的指令(MI)來劃分。

圖1描述了所提到的系統(tǒng)模型，它包括兩個類型的代理：局部代理和全局代理。在每一個物理機中存在一個局部代理，通過觀察物理機的最近資源利用率來確定物理機的狀態(tài)。全局代理充當一個監(jiān)督者，并且利用基于信息熵的異類多種群蟻群算法的虛擬機整合算法來優(yōu)化虛擬機放置。

圖1 虛擬機整合系統(tǒng)模型

它們的工作流程如下：

(1) 局部代理(LA)監(jiān)視CPU的利用率并且將物理機分類。

(2) 全局代理(GA)收集每一個物理機的狀態(tài)，并且利用基于多種群蟻群算法的虛擬機整合算法建立一個全局最優(yōu)的遷移計劃，將在算法描述部分具體描述。

(3) 全局代理發(fā)送命令給監(jiān)視器(VMMs)來執(zhí)行虛擬機遷移整合任務(wù)，該命令決定了哪些虛擬機需要遷移到哪些目的機上。

(4) 當VMM從GA收到指令后開始執(zhí)行真實的虛擬機遷移計劃。

2 算法描述

2.1 單個種群算法描述

每一個物理機p∈P上可能放置一個或多個虛擬機。在虛擬機遷移計劃中，每一個物理機都是一個潛在的源物理機，因為有可能已有虛擬機寄宿在此物理機上。同樣一個虛擬機可以遷移到所有其他的物理機上，所以所有其他的物理機都是潛在的目的物理機。因此首先創(chuàng)建一套元組T，每一個元組t∈T其中包含三個元素：源物理機Pso，要遷移的虛擬機v，目的物理機Pde，其描述如下：

t=(pso,v,pde)

(1)

虛擬機整合算法的輸出量是一個遷移計劃，得到的結(jié)果是在不降低性能的前提下可以用最少的活躍的物理機來滿足所有虛擬機的要求。此算法的目標函數(shù)描述如下：

(2)

在算法的最后，當選擇的遷移計劃被執(zhí)行時，通過將虛擬機遷移到活躍的物理機上來約束活躍的物理機的數(shù)量。一個物理機當且僅當不可能有虛擬機從此物理機遷移到其他物理機并且此物理機不在寄宿虛擬機時此物理機才會關(guān)閉為睡眠模式。其定義如下：

Ps={?p∈PVp=?}

(3)

其中，Vp是在一個物理機P上的虛擬機集合。

在本文把信息素放置在式(1)定義的元組中。每一個螞蟻nA利用隨機狀態(tài)轉(zhuǎn)移規(guī)則來選擇下一個元組進行尋路。在蟻群系統(tǒng)中狀態(tài)轉(zhuǎn)移規(guī)則叫作偽隨機比例規(guī)則。通過此規(guī)則，一個螞蟻k通過下式選擇元組s進行尋路，其描述如下：

(4)

其中，τ表示信息素的數(shù)量，η特定元組的啟發(fā)式值，β是啟發(fā)式值對信息素數(shù)量的影響因子。Tk∈T是元組T中螞蟻k尋路剩余沒有走過的元組。q∈[0,1]是均勻分布的隨機變量，q0∈[0,1]為參數(shù)。S是通過式(7)給出的概率分布公式選出的隨機變量，一個螞蟻k隨機選擇元組s進行下一個尋路的概率ps定義如下：

(5)

元組s啟發(fā)式值ηs定義如下：

(6)

其中，CPde是目的物理機Pde的總?cè)萘恐担琔Pde是目的物理機Pde的已使用容量值，Uv是元組s中的虛擬機已使用的容量值。啟發(fā)式值η依據(jù)CPde和UPde+Uv之間標量值的不同的乘法逆元素。這會使得虛擬機遷移從而減少利用率低的物理機的數(shù)量。而且，約束UPde+Uv≤CPde避免了目的物理機變?yōu)槌d物理機。

除了隨機狀態(tài)轉(zhuǎn)換規(guī)則以外，在所有螞蟻已完成遷移計劃之后還利用了全局和局部信息素更新規(guī)則，全局信息素更新規(guī)則定義如下：

(7)

(8)

α∈(0,1]是信息素信息素衰變參數(shù)，M+最好的全局遷移計劃。

當一個螞蟻穿過一個元組同時制定遷移計劃時，應(yīng)用局部信息素蹤跡規(guī)則，其定義如下：

τs=(1-ρ)·τs+ρ·τ0

(9)

其中，ρ∈(0,1]類似于α和τ0是最初的信息素標準，τ0定義如下：

(10)

當一個種群完成搜索后，根據(jù)每只螞蟻所求的ps值，來計算該種群的信息熵，具體公式如下：

(11)

其中,n表示該種群的螞蟻數(shù),對于所求得的種群信息熵，將用作種群間信息素的交流所選取種群的依據(jù)。

單個種群算法偽代碼如下：

算法1單個種群算法流程

1:M+=?,MS=?

2:?t∈Tτt=τ0

3: fori∈[1,nI] do

4: fork∈[1,nA] do

6: fort∈Tdo

7: generate a random variable q with a uniform distribution between 0 and 1

8: ifq>q0then

9: computeps?s∈Tby using (5)

10: end if

11: choose a tuplet∈Tkto traverse by using (4)

13: apply local update rule in (9) ont

14: update used capacity vectorsUpsoandUpdeint

17:Mk=Mk∪{t}

18: else

20: end if

21: end for

22:MS=MS∪{Mk}

23: end for

24:M+=arg maxMk∈MS{f(Mk)}

25: apply global update rule in(7)on alls∈T

26: end for

一次迭代后，所有的螞蟻都完成了它們的遷移計劃，把所有的特定遷移計劃Mk加入到遷移計劃集MS中(第22行)；利用目標函數(shù)式(2)計算所有Mk∈MS的目標函數(shù)值，把其中目標函數(shù)值最高的遷移計劃賦給全局最優(yōu)遷移計劃M+(第24行)；同時利用全局信息素更新規(guī)則式(7)、式(8)更新全局最優(yōu)遷移計劃當中的元組。最后，所有的迭代都完成后算法輸入全局最優(yōu)遷移計劃M+。

2.2 種群間信息素的交流

在算法中，種群的交流是以一定的時間間隔來進行的，并且這種時間間隔并非固定不變，而是依據(jù)所有群體的信息熵來進行確定，也就是隨著所有種群的收斂情況而改變。種群交流時間間隔gap滿足：

gap=k1·e

(12)

其中，k1為常數(shù)，h為子群體的個數(shù)，si為第i個子群體的信息熵。

交流群體的選擇是根據(jù)各個群體的信息熵來確定的。設(shè)群體i選擇群體j作為進行信息交流的對象，則j可由式(13)決定。

(13)

其中，si、sj為當前時刻群體i和j的信息熵。由此信息熵大的群體會選擇信息熵小的群體來交流信息，使得信息熵小的群體信息素分布相對集中通過和信息熵大的群體的交流可以平衡自己的信息素分布。而同樣信息熵大的群體分布較分散和信息熵小的群體的交流可以集中自己的信息素分布。

當確定群體j作為群體i的交流對象，我們根據(jù)式(14)進行信息素的更新。

(14)

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

3.1 仿真實驗環(huán)境

本文使用CloudSim工具包搭建實驗環(huán)境，并在Eclipse中運行實驗，通過Eclipse輸出實驗的結(jié)果，其中包括數(shù)據(jù)中心的能耗和虛擬機遷移次數(shù)。實驗?zāi)M了一個涵蓋多個不同物理機的數(shù)據(jù)中心，設(shè)置了50臺主機以及50臺虛擬機來模擬云計算的數(shù)據(jù)中心。選擇了兩個在CloudSim里的服務(wù)器配置：HP ProLiant ML110 G4 (Intel Xeon 3040,2 cores×1 860 MHz,4 GB),HP ProLiant ML110 G5 (Intel Xeon3075,2 cores×2 660 MHz,4 GB)。該環(huán)境足以滿足評估基于多核CPU架構(gòu)的資源管理方法所需的硬件配置。為了評估提出的算法的有效性，我們選取了兩種現(xiàn)存的較優(yōu)的虛擬機整合算法ACS-VMC算法和AVVMC算法作為比較對象，驗證相同實驗配置下的能耗和虛擬機遷移。

3.2 數(shù)據(jù)中心的能耗

計算一個數(shù)據(jù)中心的物理資源的總的能耗需要考慮應(yīng)用程序的工作量。計算單個物理機的能量大小時，主要考慮它的CPU使用效率、內(nèi)存使用狀態(tài)、硬盤占用情況和網(wǎng)卡的使用情況。大量研究表明CPU所消耗的能量比內(nèi)存、存儲器和網(wǎng)絡(luò)接口消耗的多的多。因此，通常用一個物理機的CPU利用率表示該物理機的資源利用率，即該物理機主機的能耗。同樣的本文中也用CPU利用率來代表該物理主機的能耗，其中我們利用基于線性回歸的LiRCUP[13]預(yù)測短期內(nèi)物理機的CPU利用率。

為了更好地表明仿真結(jié)果的真實可靠性，我們分別對仿真實驗進行了8次迭代，如圖2和圖3分別比較了1次迭代到8次迭代下的能量消耗和平均能耗，可以明顯看出MACA-VMC算法的能耗要少于ACS-VMC和AVVMC的能耗。AVVMC算法的能耗高達5.0 kW·sec以上，ACS-VMC算法的耗能量在4.9 kW·sec左右，而MACA-VMC算法的能耗僅僅只有不到4.8 kW·sec，且該算法下的能耗較為穩(wěn)定。由此可見，虛擬機整合耗能量方面上，MACA-VMC算法遠遠優(yōu)于另外兩者。

圖2 每次迭代能耗比較

圖3 各種算法平均能耗

3.3 遷移次數(shù)

動態(tài)虛擬機整合是一個耗費資源的計算過程，它會使源物理主機的部分CPU資源消耗增加，源物理主機與目的主機之間的帶寬資源消耗增加，遷移虛擬機上的服務(wù)暫停，總的整合遷移時間增加。因此，本文算法的目標之一是使遷移次數(shù)盡可能的少。在CloudSim中虛擬機遷移的時長近似于在源物理機和目的物理機網(wǎng)絡(luò)帶寬鏈路之間需要內(nèi)存分配給虛擬機的遷移時間。在仿真實驗中使用1 Gbps的網(wǎng)絡(luò)鏈路。如圖4所示，在每次迭代實驗中，MACA-VMC算法的虛擬機遷移次數(shù)都在4次左右徘徊，比較穩(wěn)定；而ACS-VMC算法的虛擬機遷移次數(shù)最多時能達到30次以上，最少時也有8次，AVVMC算法的虛擬機遷移次數(shù)同樣最多時能達到30次左右，最少時也有10次以上,而且以上兩種算法沒有規(guī)律可尋。顯然MACA-VMC算法的虛擬機遷移次數(shù)明顯少于ACS-VMC算法和AVVMC算法的虛擬機遷移次數(shù)。

圖4 虛擬機遷移次數(shù)

4 結(jié) 語

本文中提出了一個較新的基于多種群蟻群算法的虛擬機整合算法(MACA-VMC)。該算法通過整合虛擬機來減少活躍的物理機數(shù)量進而降低數(shù)據(jù)中心的能耗。相比于基于蟻群系統(tǒng)的虛擬機整合算法和基于向量代數(shù)的虛擬機整合算法，MACA-VMC算法降低了能耗，減少了虛擬機的遷移次數(shù)。

在未來的工作中，我們計劃研究一些其他的啟發(fā)式算法進一步對虛擬機整合算法進行優(yōu)化改進。此外我們還計劃將多種群蟻群算法作為一個延伸的虛擬機管理者，在公開的云平臺上評估真實云環(huán)境下的虛擬機整合算法的性能。

[1] Wang B, Qi Z, Ma R, et al. A survey on data center networking for cloud computing[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2015, 91(C):528-547.

[2] Ye K J, Wu Z H, Jiang X H, et al. Power Management of Virtualized Cloud Computing Platform[J]. Chinese Journal of Computers, 2012, 35(6):1262.

[3] Vogels W. Beyond Server Consolidation[J]. Queue, 2008, 6(1):20-26.

[4] Feller E, Morin C, Esnault A. A Case for Fully Decentralized Dynamic VM Consolidation in Clouds[C]// IEEE, International Conference on Cloud Computing Technology and Science. IEEE, 2012:26-33.

[5] Wood T, Shenoy P, Venkataramani A, et al. Sandpiper: Black-box and gray-box resource management for virtual machines[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2009, 53(17):2923-2938.

[6] Ajiro Y, Tanaka A. Improving Packing Algorithms for Server Consolidation[C]// International Computer Measurement Group Conference, December 2-7, 2007, San Diego, Ca, Usa, Proceedings. 2007:399-406.

[7] Farahnakian F, Pahikkala T, Liljeberg P, et al. Utilization Prediction Aware VM Consolidation Approach for Green Cloud Computing[C]// IEEE, International Conference on Cloud Computing. 2015:381-388.

[8] Ferdaus M H, Murshed M, Calheiros R N, et al. Virtual Machine Consolidation in Cloud Data Centers Using ACO Metaheuristic[C]// European International Conference on Parallel Processing. 2014:162a-167a.

[9] Dorigo M, Gambardella L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1):53-66.

[10] Ashraf A, Porres I. Using Ant Colony System to Consolidate Multiple Web Applications in a Cloud Environment[C]// Euromicro International Conference on Parallel, Distributed and Network-Based Processing. 2014:482-489.

[11] 趙君, 馬中, 劉馳,等. 一種多目標蟻群優(yōu)化的虛擬機放置算法[J]. 西安電子科技大學(xué)學(xué)報(自然科學(xué)版), 2015, 42(3):173-178.

[12] Calheiros R N, Ranjan R, Beloglazov A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software Practice & Experience, 2011, 41(1):23-50.

[13] Farahnakian F, Liljeberg P, Plosila J. LiRCUP: Linear Regression Based CPU Usage Prediction Algorithm for Live Migration of Virtual Machines in Data Centers[C]// Euromicro Conference Series on Software Engineering and Advanced Applications. 2013:357-364.

VIRTUALMACHINEINTEGRATIONBASEDONMULTIPLEANTCOLONIESALGORITHMFORCLOUDCOMPUTING

Wang Yaning Yuan Chunmiao*Sun Xuemei
(CollegeofComputerScienceandSoftwareEngineering,TianjinPolytechnicUniversity,Tianjin300387,China)

In the development of cloud computing, high energy consumption of the data center has been widespread concerned, and the virtual machine integration is one of the means to solve the problem of high energy consumption. Virtual machine migration is a method of the number of virtual machines by the physical machine to migrate to make some of physical machines can sleep or enter low-power mode, which reduces power consumption of the cloud data center. In this paper, we present a multiple ant colonies algorithm to implement virtual machines consolidation. The proposed approach finds a near-optimal solution based on a specified objective function. It verifies through experiment that this algorithm outperforms existing virtual machines consolidation approaches in terms of energy consumption and the number of virtual machines migration.

Data center Energy consumption VM integration Multiple ant colonies

2016-09-12。國家自然科學(xué)基金青年科學(xué)基金項目(61402329)。王亞寧，碩士，主研領(lǐng)域：云計算，智能優(yōu)化算法。苑春苗，副教授。孫學(xué)梅，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.08.005