藺凱青　李志華　郭曙杰　李雙俐

摘 要：虛擬機(jī)放置（VMP）是虛擬機(jī)整合的核心，是一個(gè)多資源約束的多目標(biāo)優(yōu)化問(wèn)題。高效的VMP算法不僅能顯著地降低云數(shù)據(jù)中心能耗、提高資源利用率，還能保證服務(wù)質(zhì)量（QoS）。針對(duì)數(shù)據(jù)中心能耗高和資源利用率低的問(wèn)題，提出了基于離散蝙蝠算法的虛擬機(jī)放置（DBA-VMP）算法。首先，把最小化能耗和最大化資源利用率作為優(yōu)化目標(biāo)，建立多目標(biāo)約束的VMP優(yōu)化模型;然后，通過(guò)效仿人工蟻群在覓食過(guò)程中共享信息素的機(jī)制，將信息素反饋機(jī)制引入蝙蝠算法，并對(duì)經(jīng)典蝙蝠算法進(jìn)行離散化改進(jìn);最后，用改進(jìn)的離散蝙蝠算法求解模型的Pareto最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，與其他多目標(biāo)優(yōu)化的VMP算法相比，所提算法在使用不同數(shù)據(jù)集的情況下都能有效降低能耗，提高資源利用率，實(shí)現(xiàn)了在保證QoS的前提下的降低能耗和提高資源利用率兩者之間的優(yōu)化平衡。

關(guān)鍵詞：虛擬機(jī)放置;多目標(biāo)優(yōu)化;離散蝙蝠算法;數(shù)據(jù)中心;云計(jì)算

中圖分類號(hào)： TP393.02;TP301.6文獻(xiàn)標(biāo)志碼：A

Multi-objective optimization algorithm for virtual machine

placement under cloud environment

LIN Kaiqing， LI Zhihua*， GUO Shujie， LI Shuangli

（School of IoT Engineering， Jiangnan University， Wuxi Jiangsu 214122， China）

Abstract： Virtual Machine Placement （VMP） is the core of virtual machine consolidation and is a multi-objective optimization problem with multiple resource constraints. Efficient VMP algorithm can significantly reduce energy consumption， improve resource utilization， and guarantee Quality of Service （QoS）. Concerning the problems of high energy consumption and low resource utilization in data center， a Discrete Bat Algorithm-based Virtual Machine Placement （DBA-VMP） algorithm was proposed. Firstly， an optimization model with multi-object constraints was established for VMP， with minimum energy consumption and maximum resource utilization as optimization objectives. Then， the pheromone feedback mechanism was introduced in the bat algorithm by emulating the pheromone sharing mechanism of artificial ant colonies in the foraging process， and the bat algorithm was improved and discretized. Finally， the improved discrete bat algorithm was used to solve the Pareto optimal solutions of the model. The experimental results show that compared with other multi-objective optimization algorithms for VMP， the proposed algorithm can effectively reduce energy consumption and improve resource utilization， and achieves an optimal balance between reducing energy consumption and improving resource utilization under the premise of guaranteeing QoS.

Key words： Virtual Machine Placement （VMP）; multi-objective optimization; discrete bat algorithm; data center; cloud computing

0 引言

云數(shù)據(jù)中心規(guī)模的快速增長(zhǎng)導(dǎo)致其能耗不斷攀升，高能耗成了數(shù)據(jù)中心亟需解決的主要問(wèn)題之一[1]。數(shù)據(jù)中心物理主機(jī)的平均CPU使用率只有15%～20%，大部分處于空閑狀態(tài)[2]。處于空閑狀態(tài)的主機(jī)一般消耗其峰值能耗的70%[3]，因此，關(guān)閉空閑主機(jī)可有效降低能耗，提高資源利用率。另一方面，虛擬機(jī)對(duì)資源的請(qǐng)求是隨機(jī)的，當(dāng)多個(gè)虛擬機(jī)同時(shí)請(qǐng)求資源時(shí)，整個(gè)數(shù)據(jù)中心的資源需求急劇上升，關(guān)閉過(guò)多的主機(jī)又會(huì)導(dǎo)致預(yù)留資源緊張，虛擬機(jī)資源請(qǐng)求得不到滿足，從而違背云服務(wù)供應(yīng)商與用戶簽訂的服務(wù)等級(jí)協(xié)議（Service Level Agreement， SLA）。因此“降低能耗、提高資源利用率和保證服務(wù)質(zhì)量”三者相互制約、互相矛盾，實(shí)現(xiàn)三者之間的優(yōu)化平衡是云數(shù)據(jù)中心資源管理所追求的目標(biāo)。

虛擬機(jī)整合是云數(shù)據(jù)中心資源管理的主要手段。虛擬機(jī)整合包括過(guò)載物理主機(jī)檢測(cè)、虛擬機(jī)選擇、虛擬機(jī)放置和低負(fù)載物理主機(jī)關(guān)閉四個(gè)子過(guò)程[3]，其中虛擬機(jī)放置是虛擬機(jī)整合的核心，旨在解決虛擬機(jī)“從哪里來(lái)到哪里去”的問(wèn)題。傳統(tǒng)的虛擬機(jī)放置算法大多將虛擬機(jī)放置建模為裝箱問(wèn)題[3-4]，并使用降序首次適應(yīng)（First Fit Decreasing， FFD）[3]算法或降序最佳適應(yīng)（Best Fit Decreasing， BFD）[4]算法等啟發(fā)式算法對(duì)其進(jìn)行求解，其主要目的是通過(guò)最小化活動(dòng)物理主機(jī)的數(shù)量來(lái)降低能耗。但大規(guī)模云數(shù)據(jù)中心虛擬機(jī)放置是NP-hard問(wèn)題[4]，傳統(tǒng)算法存在容易陷入局部最優(yōu)的不足[5]。因此文獻(xiàn)[6-8]使用智能算法求解該問(wèn)題：文獻(xiàn)[6]將最小化活動(dòng)物理主機(jī)的數(shù)量和最小化主機(jī)剩余資源作為優(yōu)化目標(biāo)并建立優(yōu)化模型，通過(guò)遺傳算法與首次適應(yīng)算法結(jié)合求解該優(yōu)化模型，但該方法仍把虛擬機(jī)放置看作多維裝箱問(wèn)題，且執(zhí)行放置后會(huì)導(dǎo)致部分主機(jī)負(fù)載過(guò)高反而影響服務(wù)質(zhì)量;文獻(xiàn)[7]使用蟻群算法來(lái)求解該問(wèn)題，將最小化遷移次數(shù)和活動(dòng)主機(jī)的數(shù)量作為優(yōu)化目標(biāo)，目的是優(yōu)先將虛擬機(jī)放置在資源利用率高的物理主機(jī)中，達(dá)到降低能耗的目的，但該方法會(huì)導(dǎo)致剩余活動(dòng)主機(jī)的資源利用率過(guò)高，增加了主機(jī)發(fā)生過(guò)載的風(fēng)險(xiǎn);文獻(xiàn)[8]建立了最小化能耗和最小化主機(jī)剩余資源的優(yōu)化模型，并采用離散螢火蟲(chóng)算法求解該優(yōu)化模型，有效改善了數(shù)據(jù)中心的資源利用率且降低了能耗?？傊墨I(xiàn)[6-8]均采用線性加權(quán)將多目標(biāo)問(wèn)題轉(zhuǎn)換為單目標(biāo)優(yōu)化進(jìn)行求解，但在多目標(biāo)問(wèn)題中，一個(gè)目標(biāo)的優(yōu)化往往會(huì)導(dǎo)致另一個(gè)目標(biāo)的劣化，因此，需要求出一組Pareto最優(yōu)解，即對(duì)一個(gè)或多個(gè)目標(biāo)不可能進(jìn)一步優(yōu)化而對(duì)其他目標(biāo)不至于劣化的最優(yōu)解的集合。

針對(duì)以上研究工作中存在的不足，本文提出了基于離散蝙蝠算法的虛擬機(jī)放置（Discrete-Bat-Algorithm-based Virtual Machine Placement， DBA-VMP）算法。首先，通過(guò)分析云數(shù)據(jù)中心負(fù)載數(shù)據(jù)的特征，建立了以最小化能耗和最小化資源剩余率為優(yōu)化目標(biāo)的多目標(biāo)優(yōu)化模型;同時(shí)，對(duì)經(jīng)典蝙蝠算法進(jìn)行離散化改進(jìn)，用改進(jìn)后的蝙蝠算法求解該模型的Pareto最優(yōu)解，即最佳虛擬機(jī)放置方案;另外，在算法中引入了蟻群算法的全局信息素更新規(guī)則，為整個(gè)種群提供正反饋機(jī)制，加速算法進(jìn)化。實(shí)驗(yàn)結(jié)果表明，DBA-VMP算法在保證服務(wù)質(zhì)量的前提下，在降低能耗和減少資源浪費(fèi)兩者之間取得了理想的平衡。

1 虛擬機(jī)放置優(yōu)化模型

1.1 數(shù)據(jù)中心描述

假設(shè)數(shù)據(jù)中心部署在物理主機(jī)hj（1≤j≤n）中的所有虛擬機(jī)集合為Vj。主機(jī)的資源使用量是該主機(jī)上部署的所有虛擬機(jī)請(qǐng)求量的總和，則hj的某類資源利用率可表示為式（1）：

Urj=1Crj ∑vmi∈Vjdri（1）

其中：r∈RS且RS={cpu，mem，bw}是主機(jī)資源類型（CPU、內(nèi)存和帶寬資源）的集合;Urj是主機(jī)hj的r類資源利用率;Crj為hj的r類資源配置容量;dri表示虛擬機(jī)vmi（1≤i≤m）請(qǐng)求的r類資源。

物理主機(jī)的功率與CPU利用率可近似為線性關(guān)系[4]，且可表示為式（2）：

P（Ucpuj）=（Pfullj-Pidelj）×Ucpuj+Pidelj（2）

其中：Pfullj和Pidelj分別代表主機(jī)hj在滿載和空載時(shí)的功率;Pj（Ucpuj）代表hj在CPU利用率是Ucpuj時(shí)的功率。

整個(gè)數(shù)據(jù)中心的能耗可定義為式（3）：

f1（X）=∑nj=1[∫ t 1t0P（Ucpuj（t）） dt]（3）

其中：矩陣X=（xij）m×n表示虛擬機(jī)與物理主機(jī)之間的映射關(guān)系且xij∈{0，1}，如果虛擬機(jī)vmi放置在物理主機(jī)hj上則xij=1，否則xij=0。 ∫ t 1t0P（Ucpuj（t）） dt表示hj在t0至t1時(shí)間段內(nèi)的能源消耗[4]，Ucpuj（t）表示t時(shí)刻hj的CPU利用率。

1.2 問(wèn)題定義

當(dāng)具有不同資源需求的虛擬機(jī)集合放置在某臺(tái)物理主機(jī)上時(shí)，有可能會(huì)使主機(jī)的某類資源利用率過(guò)高，而其他資源還有大量剩余，導(dǎo)致主機(jī)負(fù)載不均衡，造成資源浪費(fèi)。本文使用Wj表示負(fù)載不均衡造成的主機(jī)資源剩余的代價(jià)函數(shù)，定義為式（4）：

Wj=max Rrj-min{Rcpuj，Rmemj，Rbwj}; r∈RS（4）

其中：Rrj表示hj的r類資源剩余率。使用式（1）和式（4）來(lái)建立資源利用率的目標(biāo)函數(shù)，使得主機(jī)在提高利用率的同時(shí)保證剩余資源的負(fù)載均衡。

式（5）表示整個(gè)數(shù)據(jù)中心資源利用率的優(yōu)化目標(biāo)函數(shù)：

f2（X）=∑nj=1[∑r∈RS（Trj-Urj）-|lg Wj|]（5）

其中： Trj表示主機(jī)hj的r類資源使用率的閾值。由式（4）可知，Wj∈[0，1]，但對(duì)數(shù)函數(shù)在零點(diǎn)未定義，所以本文將Wj的值域定義在[0.001，1]內(nèi)，使得|lg Wj|與∑r∈RS（Trj-Urj）屬于相同值域。則虛擬機(jī)放置的多目標(biāo)優(yōu)化模型可描述為式（6）：

min F（X）=（f1（X）， f2（X））

s.t.∑nj=1xij=1; i=1，2，…，m

∑vmi∈Vjdri

其中：第一個(gè)約束條件表示一臺(tái)虛擬機(jī)只能放置在一臺(tái)物理主機(jī)中;第二個(gè)約束表示主機(jī)中虛擬機(jī)請(qǐng)求的r類資源不能超過(guò)物理主機(jī)r類資源的總?cè)萘俊?/p>

Pareto 優(yōu)化的目的是找到對(duì)一個(gè)或幾個(gè)目標(biāo)函數(shù)不可能進(jìn)一步優(yōu)化而對(duì)其他目標(biāo)不至于劣化的最優(yōu)解的集合。設(shè)xA，xB是多目標(biāo)優(yōu)化問(wèn)題min y=（f1（x）， f2（x），…， fm（x））T的可行解，若i∈{1，2，…，m}， fi（xA）≤fi（xB），且 j∈{1，2，…，m}， fj（xA）

2 離散蝙蝠算法

蝙蝠算法（Bat Algorithm， BA）[10]是根據(jù)微型蝙蝠的回聲定位行為，并結(jié)合一些現(xiàn)有群體智能算法的優(yōu)點(diǎn)提出的一種具有全局優(yōu)化能力的算法。該算法首先初始化一組隨機(jī)解，然后通過(guò)迭代搜索尋找當(dāng)前最優(yōu)解，并運(yùn)用隨機(jī)飛行在最優(yōu)解附近尋找局部最優(yōu)新解，提高了算法的局部搜索能力。與粒子群算法和遺傳算法相比，BA結(jié)構(gòu)簡(jiǎn)單、參數(shù)少，且在有效性和準(zhǔn)確性方面有明顯優(yōu)勢(shì)[10]。 BA的隨機(jī)飛行機(jī)制有助于在最優(yōu)解與可行解之間找到一個(gè)平衡，其全局尋優(yōu)能力可實(shí)現(xiàn)在整個(gè)解空間中搜索到最佳的虛擬機(jī)放置方案。針對(duì)虛擬機(jī)放置問(wèn)題，本文提出了一種改進(jìn)的離散蝙蝠算法（Discrete BA， DBA）。

2.1 BA的離散化

BA的離散化操作包括兩部分：對(duì)種群個(gè)體的離散化操作和對(duì)迭代公式的離散化。

首先，對(duì)每個(gè)個(gè)體進(jìn)行離散化操作。蝙蝠b在第t次迭代后所處的位置Xtb=（xb，i， j）m′×n表示虛擬機(jī)和物理主機(jī)之間的映射關(guān)系，其中，m′表示待遷移虛擬機(jī)隊(duì)列長(zhǎng)度，n是整個(gè)數(shù)據(jù)中心物理主機(jī)的數(shù)量，蝙蝠b通過(guò)迭代不斷調(diào)整自己的位置來(lái)搜索新的解空間，同時(shí)不斷更新整個(gè)群體Xt={Xt1，Xt2，…，XtN}經(jīng)歷過(guò)的最好位置的集合PS。

其次，對(duì)迭代公式進(jìn)行離散化操作。每只蝙蝠b都有其自身的速度Vtb=（vtb，i， j）m'×n，在經(jīng)典BA算法中，蝙蝠b根據(jù)式（7）來(lái)更新第t次迭代后的速度：

Vtb=Vt-1b+（Xt-1b-X*）fb（7）

其中：Xt-1b表示第t-1次迭代中蝙蝠b所處的位置;X*∈PS是蝙蝠種群目前找到的全局最優(yōu)解。初始化時(shí)每只蝙蝠隨機(jī)分配一個(gè)脈沖頻率fb并根據(jù)式（8）來(lái)更新：

fb=fmin+（fmax-fmin）β（8）

其中：β∈[0，1]是服從均勻分布的隨機(jī)變量。本文遵循經(jīng)典BA的迭代更新思想，對(duì)式（7）進(jìn)行了離散化操作如式（9）所示。

vtb，i=xor（vt-1b，i，xt-1b，i）， fb≥rand

xor（vt-1b，i，x*，i），其他 （9）

其中：行向量vtb，i表示Vtb的第i個(gè)分量，行向量xt-1b，i是Xt-1b的第i個(gè)分量，即蝙蝠b在第t-1次迭代后虛擬機(jī)vmi的部署向量。 xor表示異或操作，由于一臺(tái)虛擬機(jī)只能放置在一臺(tái)物理主機(jī)上，為了確保這個(gè)約束條件，本文使用異或操作對(duì)速度進(jìn)行更新，并對(duì)該操作作了相應(yīng)的改進(jìn)，假設(shè)S1和S2是兩個(gè)p×q的映射矩陣，行向量s1，i和s2，i分別表示S1和S2的第i個(gè)分量，則xor操作如式（10）：

xor（s1，i，s2，i）=0， s1，i=s2，i

s1，i，s1，i≠s2，i & r≥rand

s2，i，s1，i≠s2，i & r

其中：r和rand都是區(qū)間[0，1）的隨機(jī)數(shù)，當(dāng)s1，i和s2，i相同時(shí)，則通過(guò)xor操作更新為零向量;否則隨機(jī)選擇某一個(gè)向量作為運(yùn)算結(jié)果。經(jīng)典BA通過(guò)將Vtb和Xt-1b相加得到第t次迭代后蝙蝠b的位置Xtb，本文對(duì)Xtb的離散化改進(jìn)如式（11）所示。

xtb，i=vtb，i， r

xt-1b，i，其他 （11）

其中： 行向量xtb，i表示蝙蝠b在第t次迭代后虛擬機(jī)vmi的部署向量;vtb，i是第t次迭代后的速度向量; r∈[0，1）是隨機(jī)數(shù);R是常數(shù)。

在每次迭代中，都會(huì)產(chǎn)生一個(gè)隨機(jī)數(shù)rand1，如果rand1的值大于脈沖發(fā)射率rb，則進(jìn)行局部搜索，從而加速解空間的搜索過(guò)程，提高最優(yōu)解的質(zhì)量，本文將局部搜索過(guò)程離散化為式（12）：

xnew，i=xor（xo1，i，xo2，i）（12）

其中：行向量xnew，i是矩陣Xnew的第i個(gè)部署向量;矩陣Xo1和Xo2是最優(yōu)解集合PS中的任意兩個(gè)最優(yōu)解，xo1，i和xo2，i分別表示矩陣Xo1和Xo2中虛擬機(jī)vmi的部署向量。 Xnew是產(chǎn)生的新解。如果新解優(yōu)于舊解且產(chǎn)生的隨機(jī)數(shù)rand2的值小于響度值A(chǔ)b，則接受新解，更新響度Ab和脈沖發(fā)射率rb，如式（13）和式（14）。

Atb=αAt-1b（13）

rtb=r0b[1-exp（-γ（t-1））]（14）

其中： α和γ是常數(shù)，0<α<1且γ>0。r0b∈[0，1]是蝙蝠b的初始脈沖速率。

2.2 信息素矩陣

在利用DBA求解虛擬機(jī)放置的過(guò)程中，本文引入了蟻群算法的信息素矩陣Τt=（τtij）m×n，保留迭代過(guò)程中獲得的歷史經(jīng)驗(yàn)，讓所有蝙蝠可以共享搜索過(guò)程中積累的信息，加快算法的收斂速度。τtij表示第t次迭代中虛擬機(jī)vmi放置在hj上積累的信息素。在種群迭代過(guò)程中，信息素矩陣的更新如式（15）所示。

τtij=

φ·τt-1ij+（1-φ）·（Fmaxpower-f1（X*）），x*，i， j=1

τt-1ij，其他 （15）

其中：φ∈[0，1]為權(quán)重參數(shù)，用來(lái)調(diào)節(jié)第t-1次迭代后積累的信息素與第t次迭代后產(chǎn)生的信息素所占的比重;Fmaxpower是整個(gè)數(shù)據(jù)中心的最大能耗值，如果第t次迭代后，在最優(yōu)映射矩陣X*中vmi放置在hj上，即x*，i， j=1，則更新τtij;否則保持第t-1次迭代中的信息素值。

2.3DBA

本文將種群的迭代過(guò)程分為兩部分：隨機(jī)迭代搜索和啟發(fā)式迭代搜索。在每次迭代中，蝙蝠b隨機(jī)選擇某一種迭代方式來(lái)搜索最優(yōu)解。在隨機(jī)搜索中，蝙蝠b根據(jù)式（10）來(lái)更新自身的速度;在啟發(fā)式搜索中，蝙蝠b的速度更新公式如式（16）所示。

vtb，i=

xor（vt-1b，i，xt-1b，i）， ∑nj=1xt-1b，i， j·τt-1ij>∑nj=1x*，i， j·τt-1ij

xor（vt-1b，i，x*，i），其他 （16）

如果在矩陣Xt-1b中，虛擬機(jī)vmi放置在了物理主機(jī)hj上，則xt-1b，i， j=1;否則xt-1b，i， j=0。如果矩陣Xt-1b中虛擬機(jī)vmi部署積累的信息素值大于矩陣X*中vmi部署積累的信息素值，則對(duì)向量vt-1b，i和xt-1b，i進(jìn)行異或操作。

式（17）表示了在啟發(fā)式搜索中第t次迭代后，主機(jī)和虛擬機(jī)的映射關(guān)系矩陣Xtb。

xtb，i=vtb，i， ∑nj=1vtb，i， j·τt-1ij>∑nj=1xt-1b，i， j·τt-1ij

xt-1b，i，其他 （17）

算法1詳細(xì)說(shuō)明了DBA迭代尋找最優(yōu)解的總體框架。其中，Xt-1表示第t-1次迭代后所有蝙蝠的位置的集合，PS是種群當(dāng)前的Pareto最優(yōu)解的集合，ran，rand1，rand2∈[0，1）是隨機(jī)數(shù)。

算法1 DBA。

輸入 Xt-1，PS;

輸出 Xt 程序前

for all Xt-1b∈Xt-1 do

if ran

use equation（9） to update Vtb and equation（11） to generate Xtb

else

use equation（16） to update Vtb and equation（17） to

generate Xtb

end if

if rand1>rt-1b then

random select a solution from PS as Xo1， Xo2

use equation （12） to generate Xnew

end if

if rand2

accept Xnew and use （13） （14） to updatertb， Atb

end if

end for

return Xt程序后

3 基于DBA的虛擬機(jī)放置方法

根據(jù)主機(jī)的資源使用情況，數(shù)據(jù)中心的活動(dòng)物理主機(jī)分為低負(fù)載、正常以及過(guò)載三類[3]。本文使用Ho表示過(guò)載物理主機(jī)集合，Hn表示正常負(fù)載的主機(jī)集合，Hu表示低負(fù)載主機(jī)集合，Hs表示休眠主機(jī)集合。

圖1為基于離散蝙蝠算法的虛擬機(jī)放置（DBA-VMP）算法的流程。算法2是偽代碼描述，其中：X*表示迭代完成后主機(jī)和虛擬機(jī)的最終映射關(guān)系，Vmig表示Ho中需要遷移的虛擬機(jī)集合。DBA-VMP為Vmig集合中的每臺(tái)虛擬機(jī)找到合適的目的主機(jī)hd，且hd∈Hn∨Hu∨Hs，及時(shí)解除Ho中所有主機(jī)的過(guò)載風(fēng)險(xiǎn)。在低負(fù)載物理主機(jī)關(guān)閉過(guò)程中，Vmig表示某臺(tái)低負(fù)載主機(jī)hu∈Hu中部署的全部虛擬機(jī)集合，如果DBA-VMP能為所有的虛擬機(jī)找到目的主機(jī)hd，且hd∈Hn∨Hu，則將hu關(guān)閉;否則不執(zhí)行遷移操作。在迭代過(guò)程中，本文使用了文獻(xiàn)[11]提出的非支配排序和擁擠距離算法來(lái)求解Pareto解集。

在算法2的復(fù)雜度分析方面，因?yàn)樗惴?的時(shí)間復(fù)雜度是O（m·n2），其中m表示種群的數(shù)量，n代表待遷移虛擬機(jī)的長(zhǎng)度;非支配排序和擁擠距離（non-dominated sorting and crowding distance）的時(shí)間復(fù)雜度分別為O（m2）和O（2m log（2m）），迭代次數(shù)為I，所以整個(gè)算法的時(shí)間復(fù)雜度為O（I·m·（n2+m））。

算法2 基于離散蝙蝠算法的虛擬機(jī)放置。

輸入 Vmig ;

輸出 X*。程序前

initialize X0b，PS，V0b （b=1，2，…，N）

initialize objective functions f1（X0b）， f2（X0b）

while t

use Algorithm 1 to generate Xtb

use equation （3）～（4） to update f1（Xtb），f2（Xtb）

use non-dominated sorting and crowding distance to update Pareto

solutions PS

use equation（15） to update Τt

select a solution X* from PS

return X* 程序后

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

4.1 評(píng)價(jià)指標(biāo)

本文采用六種性能評(píng)價(jià)指標(biāo)[4]來(lái)評(píng)價(jià)DBA-VMP算法的性能：服務(wù)等級(jí)協(xié)議違例率（SLA Violations， SLAV）、能源消耗（Energy Consumption， EC）、虛擬機(jī)遷移次數(shù)（Virtual Machine Migrations， VMM）、物理主機(jī)的服務(wù)等級(jí)協(xié)議違例時(shí)間（SLA violation Time per Active Host， SLATAH）、遷移虛擬機(jī)導(dǎo)致的虛擬機(jī)性能下降（Performance Degradation due to Migrations， PDM）、服務(wù)質(zhì)量和能耗的綜合評(píng)價(jià)指標(biāo)（Energy consumption and SLA Violations， ESV）。

SLATAH用來(lái)衡量主機(jī)提供的服務(wù)質(zhì)量，如式（18）所示：

SLATAH=1n∑nj=1TsjTaj（18）

其中： n代表活動(dòng)物理主機(jī)的數(shù)量;Taj代表活動(dòng)主機(jī)hj運(yùn)行的時(shí)長(zhǎng);Tsj表示hj的CPU資源過(guò)載產(chǎn)生的SLA違背的時(shí)長(zhǎng)。PDM表示虛擬機(jī)因遷移導(dǎo)致的性能下降程度，如式（19）所示：

PDM=1m∑mi=1ccpuidcpui（19）

其中： m代表虛擬機(jī)的數(shù)量;dcpui代表虛擬機(jī)vmi請(qǐng)求的CPU資源容量;ccpui代表因遷移導(dǎo)致的vmi未被滿足的CPU資源容量。

SLAV綜合評(píng)價(jià)單日內(nèi)數(shù)據(jù)中心的服務(wù)質(zhì)量，如式（20）所示：

SLAV=SLATAH×PDM（20）

ESV指標(biāo)如式（21）所示：

ESV=EC×SLAV（21）

其中，EC代表整個(gè)數(shù)據(jù)中心一天的能源消耗，EC值越低代表數(shù)據(jù)中心運(yùn)維成本越低。

4.2 實(shí)驗(yàn)配置

CloudSim是一種云環(huán)境的開(kāi)源仿真工具[12]。本文模擬了一個(gè)由800臺(tái)異構(gòu)物理主機(jī)組成的數(shù)據(jù)中心，根據(jù)資源配置的不同分為Hp ProLiant ML110 G4（Intel Xeon 3040 2cores 1860MHz，4GB）和Hp ProLiant ML110 G5（Intel Xeon 3075 2cores 2260MHz，4GB）兩種。此外，該平臺(tái)還創(chuàng)建了四種不同類型的虛擬機(jī)，分別是High-CPU Medium Instance（2500MIPS，0.85GB）、Extra Large Instance（2000MIPS，3.75GB）、Small Instance（1000MIPS，1.7GB）和Micro Instance（500MIPS，613MB）。本文采用的實(shí)驗(yàn)數(shù)據(jù)來(lái)自Bitbrains[13]數(shù)據(jù)集和Alibaba Cluster Data V2018[14]數(shù)據(jù)集。

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

本文將DBA-VMP同F(xiàn)FD[3]、多資源組合排序的首次適應(yīng)遺傳算法（Combinatorial Order First-Fit Genetic Algorithm， COFFGA）[6]、使用蟻群系統(tǒng)的虛擬機(jī)放置（Ant Colony System-based VMP， ACS-VMP）算法[7]和資源使用率預(yù)測(cè)感知的最適降序（Utilization Prediction-aware BFD， UPBFD）算法[15]這四種虛擬機(jī)放置算法進(jìn)行對(duì)比。為了獲得有效的對(duì)比結(jié)果，將5種放置算法結(jié)合四分位距（InterQuartile Range， IQR）[4]、過(guò)載概率估計(jì)（Estimation of Overloaded Probability， EOP） [1]兩種物理主機(jī)過(guò)載檢測(cè)算法和隨機(jī)選擇（Random Selection， RS）[4]、過(guò)載概率下降的遷移選擇（Overloaded Probability Decreasing Migration Selection， OPDMS）[5]兩種虛擬機(jī)選擇算法進(jìn)行實(shí)驗(yàn)，并將過(guò)載檢測(cè)和虛擬機(jī)選擇算法組合成IQR-RS、EOP-OPDMS兩組。每次整合時(shí)首先執(zhí)行EOP（或IQR）算法對(duì)主機(jī)進(jìn)行過(guò)載檢測(cè)，再通過(guò)OPDMS（或RS）算法將過(guò)載主機(jī)中的部分虛擬機(jī)遷出直至主機(jī)不再過(guò)載，再通過(guò)虛擬機(jī)放置算法給這些虛擬機(jī)找到合適的目的主機(jī)，最后將部分低負(fù)載主機(jī)中的全部虛擬機(jī)遷出將其切換至休眠狀態(tài)。實(shí)驗(yàn)參數(shù)的初始化如下：N=10， fmax=1， fmin=0，R=0.7，r0b、A0b、α和γ的值為0.95，φ=0.3，iter=8。

4.3.1有效性

有效性主要是用來(lái)驗(yàn)證算法在六種性能評(píng)價(jià)指標(biāo)中的表現(xiàn)。圖2（a）為不同虛擬機(jī)放置算法運(yùn)行Bitbrains數(shù)據(jù)集得到的能耗值。其中，使用EOP-OPDMS作為過(guò)載檢測(cè)和虛擬機(jī)選擇算法時(shí)，DBA-VMP的能耗值最低，約為ACS-VMP能耗的82%，這是由于該算法將能耗指標(biāo)作為了優(yōu)化目標(biāo)，且算法通過(guò)隨機(jī)迭代可抑制貪心選擇使算法陷入局部最優(yōu)，因此算法有很好的節(jié)能效果;ACS-VMP和COFFGA的目的都是最小化活動(dòng)主機(jī)的數(shù)量，當(dāng)采用不同的過(guò)載檢測(cè)和虛擬機(jī)選擇策略時(shí)，能耗值變化幅度很大，表明這兩種算法有可能陷入了局部極值，導(dǎo)致活動(dòng)主機(jī)數(shù)量增加，能耗增大。

圖2（b）為不同算法運(yùn)行Alibaba Cluster數(shù)據(jù)集得到的能耗值， Alibaba Cluster的資源請(qǐng)求量比Bitbrains大但變化幅度小，所以運(yùn)行時(shí)產(chǎn)生的能耗值大且不同算法得到的能耗值差距小。在使用EOP-OPDMS的前提下，DBA-VMP的平均能耗值比FFD高4%左右，因?yàn)镈BA-VMP在進(jìn)行目的主機(jī)選擇時(shí)偏向資源配置大的主機(jī)，以減小主機(jī)的過(guò)載風(fēng)險(xiǎn)，確保服務(wù)質(zhì)量;在使用IQR-RS的前提下，COFFGA的平均能耗值比FFD高16%，再次證明了算法可能會(huì)陷入局部極值。

圖3為幾種算法運(yùn)行不同數(shù)據(jù)集得到的平均遷移次數(shù)，虛擬機(jī)遷移會(huì)造成短暫的停機(jī)影響服務(wù)質(zhì)量。在使用不同的過(guò)載檢測(cè)和虛擬機(jī)選擇算法的情況下，DBA-VMP的遷移次數(shù)保持穩(wěn)定且遠(yuǎn)遠(yuǎn)低于其他算法，因?yàn)樗惴紤]了不同資源間的負(fù)載均衡，使得主機(jī)有足夠的預(yù)留資源應(yīng)對(duì)虛擬機(jī)請(qǐng)求的急劇增加，避免主機(jī)發(fā)生過(guò)載，減少不必要的虛擬機(jī)遷移;ACS-VMP的遷移次數(shù)變化幅度大，運(yùn)行Bitbrains時(shí)，在選擇EOP-OPDMS的前提下ACS-VMP比DBA-VMP低1%左右，但選擇IQR-RS的前提下ACS-VMP比DBA-VMP高85%左右，再次說(shuō)明了：算法有可能陷入局部極值使活動(dòng)主機(jī)的數(shù)量增加，從而降低遷移次數(shù);而當(dāng)算法找到全局最優(yōu)解時(shí)，又導(dǎo)致主機(jī)負(fù)載過(guò)高造成遷移次數(shù)增加。

圖4（a）為不同算法運(yùn)行Bitbrains數(shù)據(jù)集得到的SLATAH值。在使用EOP-OPDMS的前提下，DBA-VMP算法略高于ACS-VMP和COFFGA，結(jié)合圖3（a）可知，這三種算法的遷移次數(shù)相對(duì)較少，但DBA-VMP比其他算法時(shí)間開(kāi)銷大，從而造成虛擬機(jī)請(qǐng)求的響應(yīng)時(shí)間長(zhǎng)，導(dǎo)致服務(wù)質(zhì)量略低于其他算法。使用IQR-RS的情況下，DBA-VMP的SLATAH值最低，因?yàn)樵撍惴ǖ倪w移次數(shù)遠(yuǎn)低于其他算法。

圖4（b）為不同算法運(yùn)行Alibaba Cluster得到的SLATAH值。在使用不同的過(guò)載檢測(cè)和虛擬機(jī)選擇算法的情況下，算法DBA-VMP和COFFGA的SLATAH值都保持領(lǐng)先，因?yàn)镈BA-VMP算法的遷移次數(shù)少，COFFGA在運(yùn)行該數(shù)據(jù)集時(shí)，時(shí)間開(kāi)銷小，F(xiàn)FD僅次于這兩種算法，因?yàn)樗惴ǖ臅r(shí)間開(kāi)銷小。ACS-VMP略高于FFD，因?yàn)樗惴ㄍㄟ^(guò)迭代來(lái)尋找最優(yōu)解，因此算法的響應(yīng)時(shí)間長(zhǎng)，UPBFD的遷移次數(shù)遠(yuǎn)超于其他算法，因此SLATAH遠(yuǎn)高于其他算法。

圖5為不同算法的PDM值。圖5（a）是Bitbrains的運(yùn)行結(jié)果。其中使用EOP-OPDMS的前提下，DBA-VMP算法的PDM值僅次于算法ACS-VMP和COFFGA，因?yàn)檫@三種算法遷移次數(shù)少，但DBA-VMP算法時(shí)間開(kāi)銷較大，虛擬機(jī)請(qǐng)求的響應(yīng)時(shí)間長(zhǎng)，使服務(wù)質(zhì)量受到影響;FFD算法的遷移次數(shù)多但時(shí)間開(kāi)銷小，所以僅次于DBA-VMP算法。圖5（b）為Alibaba Cluster數(shù)據(jù)集的運(yùn)行結(jié)果，在選擇不同過(guò)載檢測(cè)和虛擬機(jī)選擇算法的情況下，DBA-VMP的PDM值都優(yōu)于其他算法，因?yàn)樵撍惴ㄍㄟ^(guò)合理的虛擬機(jī)放置穩(wěn)定了主機(jī)負(fù)載，使遷移次數(shù)遠(yuǎn)低于其他算法，有效保證了服務(wù)質(zhì)量。

圖6為不同算法的服務(wù)質(zhì)量指標(biāo)值，SLAV受SLATAH和PDM的綜合影響，因此，在使用不同過(guò)載檢測(cè)和虛擬機(jī)選擇算法的情況下，DBA-VMP的SLAV值在不同的數(shù)據(jù)集上都有很好的表現(xiàn)。ESV指標(biāo)受服務(wù)質(zhì)量和能耗的影響，因此，結(jié)合圖2和圖6可知，在選擇EOP-OPDMS情況下，運(yùn)行Bitbrains數(shù)據(jù)集后，DBA-VMP的ESV平均值僅次于ACS-VMP和COFFGA，且比ACS-VMP高36%左右;運(yùn)行Alibaba Cluster數(shù)據(jù)集后， DBA-VMP的ESV平均值比COFFGA高18%左右。在選擇IQR-RS情況下，DBA-VMP運(yùn)行不同的數(shù)據(jù)集得到的ESV值都最低。可見(jiàn)，DBA-VMP的ESV值在不同的數(shù)據(jù)集上都有很好的表現(xiàn)，進(jìn)一步驗(yàn)證了DBA-VMP算法的有效性。

通過(guò)以上分析可知，DBA-VMP算法在處理不同的數(shù)據(jù)集時(shí)都可以有效降低能耗，保證數(shù)據(jù)中心的服務(wù)質(zhì)量。

4.3.2高效性

本節(jié)以IQR-RS作為過(guò)載檢測(cè)和虛擬機(jī)選擇算法，通過(guò)對(duì)比不同算法運(yùn)行Bitbrains數(shù)據(jù)集后，數(shù)據(jù)中心活動(dòng)主機(jī)的資源利用率為例，來(lái)驗(yàn)證DBA-VMP算法的高效性。圖7（a）為不同算法CPU資源的利用率對(duì)比，橫坐標(biāo)表示虛擬機(jī)的整合周期，虛擬機(jī)整合每隔5min進(jìn)行一次，每天整合288次。

由圖7（a）可知，UPBFD的CPU利用率最高且維持在80%左右，這是因?yàn)樗惴▋?yōu)先將虛擬機(jī)放置在綜合負(fù)載高的物理主機(jī)上，導(dǎo)致主機(jī)預(yù)留資源緊張，結(jié)合圖6可知，該算法未考慮數(shù)據(jù)中心的服務(wù)質(zhì)量;CPU利用率過(guò)高會(huì)增加主機(jī)的過(guò)載風(fēng)險(xiǎn)，導(dǎo)致虛擬機(jī)頻繁的遷移，影響服務(wù)質(zhì)量。DBA-VMP算法的CPU使用率維持在70%左右，從而能進(jìn)一步提升服務(wù)質(zhì)量。

圖7（b）為內(nèi)存資源的利用率對(duì)比。UPBFD算法整合前期內(nèi)存利用率低于其他算法，這是因?yàn)樗惴▋?yōu)先考慮綜合負(fù)載高的物理主機(jī)且未考慮主機(jī)的不同資源之間的負(fù)載均衡，造成資源浪費(fèi)，DBA-VMP算法的內(nèi)存使用率維持在70%左右，因?yàn)樗惴ㄔ趦?yōu)化時(shí)考慮了不同主機(jī)內(nèi)的負(fù)載均衡，可有效減少資源的浪費(fèi)。

圖7（c）為不同算法的帶寬資源利用率情況，Bitbrains數(shù)據(jù)集中帶寬資源的請(qǐng)求量低，所以每種算法的帶寬資源使用率相近。

通過(guò)以上分析可知，DBA-VMP算法可有效提高主機(jī)的資源利用率并考慮到了不同資源之間的負(fù)載均衡，還同時(shí)兼顧了數(shù)據(jù)中心的服務(wù)質(zhì)量。

5 結(jié)語(yǔ)

本文建立了能耗和資源利用率的優(yōu)化模型，并提出了DBA-VMP算法來(lái)求解該模型的Pareto最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，DBA-VMP算法在保證服務(wù)質(zhì)量的前提下，有效降低了數(shù)據(jù)中心能耗并提高了資源利用率。然而本文算法沒(méi)有對(duì)服務(wù)質(zhì)量作出改善，改善服務(wù)質(zhì)量可以提高用戶體驗(yàn)，因此，在“降低能耗、提高資源利用率和改善服務(wù)質(zhì)量”三者之間取得優(yōu)化平衡的多目標(biāo)虛擬機(jī)放置算法是我們進(jìn)一步的研究工作。

參考文獻(xiàn) （References）

[1]LI Z， YAN C， YU X， et al. Bayesian network-based virtual machines consolidation method [J]. Future Generation Computer Systems， 2017， 69： 75-87.

[2]BIRKE R， CHEN L Y， SMIRNI E. Data centers in the cloud： a large scale performance study [C]// Proceedings of the IEEE 5th International Conference on Cloud Computing. Piscataway： IEEE， 2012： 336-343.

[3]BELOGLAZOV A， ABAWAJY J， BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing [J]. Future Generation Computer Systems， 2012， 28（5）： 755-768.

[4]BELOGLAZOV A， BUYYA R. Optimal online deterministic algo-rithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers [J]. Concurrency and Computation： Practice and Experience， 2012， 24（13）： 1397-1420.

[5]LI Z， YAN C， YU L， et al. Energy-aware and multi-resource overload probability constraint-based virtual machine dynamic consolidation method [J]. Future Generation Computer Systems， 2018， 80： 139-156.

[6]HALLAWI H， MEHNEN J， HE H. Multi-capacity combinatorial ordering GA in application to cloud resources allocation and efficient virtual machines consolidation [J]. Future Generation Computer Systems， 2017， 69： 1-10.

[7]FARAHNAKIAN F， ASHRAF A， PAHIKKALA T， et al. Using ant colony system to consolidate VMS for green cloud computing [J]. IEEE Transactions on Services Computing， 2015， 8（2）： 187-198.

[8]DING W， GU C， LUO F， et al. DFA-VMP： an efficient and secure virtual machine placement strategy under cloud environment [J]. Peer-to-Peer Networking and Applications， 2018， 11（2）： 318-333.

[9]朱占磊，李征，趙瑞蓮.基于線性權(quán)重最優(yōu)支配的高維多目標(biāo)優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2017，37（10）：2023-2827.（ZHU Z L， LI Z， ZHAO R L. Many-objective optimization algorithm based on linear weighted minimal/maximal dominance [J]. Journal of Computer Applications， 2017， 37（10）： 2023-2827.）

[10]YANG X. A new metaheuristic bat-inspired algorithm [C]// Proceedings of the 2010 Nature Inspired Cooperative Strategies for Optimization， SCI 284. Berlin： Springer， 2010： 65-74.

[11]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[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 and Experience， 2011， 41（1）： 23-50.

[13]SHEN S， VAN BEEK V， IOSUP A. Statistical characterization of business-critical workloads hosted in cloud datacenters [C]// Proceedings of the 15th IEEE/ACM International Symposium on Cluster， Cloud and Grid Computing. Piscataway： IEEE， 2015： 465-474.

[14]CHANG Z H. Alibaba cluster trace program [EB/OL]. [2018-12-25]. http：//github.com/alibaba/clusterdata.

[15]FARAHNAKIAN F， PAHIKKALA T， LILJEBERG P， et al. Utilization prediction aware VM consolidation approach for green cloud computing [C]// Proceedings of the IEEE 8th International Conference on Cloud Computing. Piscataway： IEEE， 2015： 381-388.

This work is partially supported by the Ministry of Industry and Information Technology Intelligent Manufacturing Project （ZH-XZ-180004）， the Production-Study-Research Forecasting Project of Jiangsu Science and Technology Department （BY2013015-23）， the 111 Base Construction Project （B2018）.

LIN Kaiqing， born in 1993， M. S. candidate. Her research interests include cloud computing， distributed computing.

LI Zhihua， born in 1969， Ph. D.， associate professor. His research interests include cloud computing， information safety.

GUO Shujie， born in 1994， M. S. candidate. His research interests include cloud computing， parallel computing.

LI Shuangli， born in 1992， M. S. candidate. Her research interests include cloud computing， distributed computing.

收稿日期：2019-05-13;修回日期：2019-06-03;錄用日期：2019-06-10。

基金項(xiàng)目：工業(yè)和信息化部智能制造項(xiàng)目（ZH-XZ-180004）;江蘇省科技廳產(chǎn)學(xué)研前瞻項(xiàng)目（BY2013015-23）;111基地建設(shè)項(xiàng)目 （B2018）。

作者簡(jiǎn)介：藺凱青（1993—），女，山西呂梁人，碩士研究生，CCF會(huì)員，主要研究方向：云計(jì)算、分布式計(jì)算; 李志華（1969—），男，湖南保靖人，副教授，博士，主要研究方向：云計(jì)算、信息安全; 郭曙杰（1994—），男，江蘇常州人，碩士研究生，主要研究方向：云計(jì)算、并行計(jì)算;李雙俐（1992—），女，河南新鄉(xiāng)人，碩士研究生，CCF會(huì)員，主要研究方向：云計(jì)算、分布式計(jì)算。

文章編號(hào)：1001-9081（2019）12-3597-07DOI：10.11772/j.issn.1001-9081.2019050808