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

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

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

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

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

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

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

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

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

Urj=1Crj ∑vmi∈Vjdri（1）

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

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

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

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

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

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

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

1.2 問題定義

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

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

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

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

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

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

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

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

∑vmi∈Vjdri

其中：第一個約束條件表示一臺虛擬機只能放置在一臺物理主機中;第二個約束表示主機中虛擬機請求的r類資源不能超過物理主機r類資源的總?cè)萘俊?/p>

Pareto 優(yōu)化的目的是找到對一個或幾個目標函數(shù)不可能進一步優(yōu)化而對其他目標不至于劣化的最優(yōu)解的集合。設(shè)xA，xB是多目標優(yōu)化問題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)點提出的一種具有全局優(yōu)化能力的算法。該算法首先初始化一組隨機解，然后通過迭代搜索尋找當前最優(yōu)解，并運用隨機飛行在最優(yōu)解附近尋找局部最優(yōu)新解，提高了算法的局部搜索能力。與粒子群算法和遺傳算法相比，BA結(jié)構(gòu)簡單、參數(shù)少，且在有效性和準確性方面有明顯優(yōu)勢[10]。 BA的隨機飛行機制有助于在最優(yōu)解與可行解之間找到一個平衡，其全局尋優(yōu)能力可實現(xiàn)在整個解空間中搜索到最佳的虛擬機放置方案。針對虛擬機放置問題，本文提出了一種改進的離散蝙蝠算法（Discrete BA， DBA）。

2.1 BA的離散化

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

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

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

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

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

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

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

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

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

其中：行向量vtb，i表示Vtb的第i個分量，行向量xt-1b，i是Xt-1b的第i個分量，即蝙蝠b在第t-1次迭代后虛擬機vmi的部署向量。 xor表示異或操作，由于一臺虛擬機只能放置在一臺物理主機上，為了確保這個約束條件，本文使用異或操作對速度進行更新，并對該操作作了相應(yīng)的改進，假設(shè)S1和S2是兩個p×q的映射矩陣，行向量s1，i和s2，i分別表示S1和S2的第i個分量，則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）的隨機數(shù)，當s1，i和s2，i相同時，則通過xor操作更新為零向量;否則隨機選擇某一個向量作為運算結(jié)果。經(jīng)典BA通過將Vtb和Xt-1b相加得到第t次迭代后蝙蝠b的位置Xtb，本文對Xtb的離散化改進如式（11）所示。

xtb，i=vtb，i， r

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

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

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

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

其中：行向量xnew，i是矩陣Xnew的第i個部署向量;矩陣Xo1和Xo2是最優(yōu)解集合PS中的任意兩個最優(yōu)解，xo1，i和xo2，i分別表示矩陣Xo1和Xo2中虛擬機vmi的部署向量。 Xnew是產(chǎn)生的新解。如果新解優(yōu)于舊解且產(chǎn)生的隨機數(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求解虛擬機放置的過程中，本文引入了蟻群算法的信息素矩陣Τt=（τtij）m×n，保留迭代過程中獲得的歷史經(jīng)驗，讓所有蝙蝠可以共享搜索過程中積累的信息，加快算法的收斂速度。τtij表示第t次迭代中虛擬機vmi放置在hj上積累的信息素。在種群迭代過程中，信息素矩陣的更新如式（15）所示。

τtij=

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

τt-1ij，其他 （15）

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

2.3DBA

本文將種群的迭代過程分為兩部分：隨機迭代搜索和啟發(fā)式迭代搜索。在每次迭代中，蝙蝠b隨機選擇某一種迭代方式來搜索最優(yōu)解。在隨機搜索中，蝙蝠b根據(jù)式（10）來更新自身的速度;在啟發(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中，虛擬機vmi放置在了物理主機hj上，則xt-1b，i， j=1;否則xt-1b，i， j=0。如果矩陣Xt-1b中虛擬機vmi部署積累的信息素值大于矩陣X*中vmi部署積累的信息素值，則對向量vt-1b，i和xt-1b，i進行異或操作。

式（17）表示了在啟發(fā)式搜索中第t次迭代后，主機和虛擬機的映射關(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詳細說明了DBA迭代尋找最優(yōu)解的總體框架。其中，Xt-1表示第t-1次迭代后所有蝙蝠的位置的集合，PS是種群當前的Pareto最優(yōu)解的集合，ran，rand1，rand2∈[0，1）是隨機數(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ù)主機的資源使用情況，數(shù)據(jù)中心的活動物理主機分為低負載、正常以及過載三類[3]。本文使用Ho表示過載物理主機集合，Hn表示正常負載的主機集合，Hu表示低負載主機集合，Hs表示休眠主機集合。

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

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

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

輸入 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 實驗與結(jié)果分析

4.1 評價指標

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

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

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

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

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

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

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

SLAV=SLATAH×PDM（20）

ESV指標如式（21）所示：

ESV=EC×SLAV（21）

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

4.2 實驗配置

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

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

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

4.3.1有效性

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

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

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

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

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

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

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

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

4.3.2高效性

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

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

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

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

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

5 結(jié)語

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

參考文獻 （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)支配的高維多目標優(yōu)化算法[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。

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

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

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