云環境中多目標優化的虛擬機放置算法

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

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

關鍵詞：虛擬機放置;多目標優化;離散蝙蝠算法;數據中心;云計算

中圖分類號： 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 引言

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

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

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

1 虛擬機放置優化模型

1.1 數據中心描述

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

Urj=1Crj ∑vmi∈Vjdri（1）

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

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

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

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

整個數據中心的能耗可定義為式（3）：

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

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

1.2 問題定義

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

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

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

式（5）表示整個數據中心資源利用率的優化目標函數：

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

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

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

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

∑vmi∈Vjdri

其中：第一個約束條件表示一臺虛擬機只能放置在一臺物理主機中;第二個約束表示主機中虛擬機請求的r類資源不能超過物理主機r類資源的總容量。

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

2.1 BA的離散化

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

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

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

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

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

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

其中：β∈[0，1]是服從均勻分布的隨機變量。本文遵循經典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表示異或操作，由于一臺虛擬機只能放置在一臺物理主機上，為了確保這個約束條件，本文使用異或操作對速度進行更新，并對該操作作了相應的改進，假設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都是區間[0，1）的隨機數，當s1，i和s2，i相同時，則通過xor操作更新為零向量;否則隨機選擇某一個向量作為運算結果。經典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）是隨機數;R是常數。

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

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

其中：行向量xnew，i是矩陣Xnew的第i個部署向量;矩陣Xo1和Xo2是最優解集合PS中的任意兩個最優解，xo1，i和xo2，i分別表示矩陣Xo1和Xo2中虛擬機vmi的部署向量。 Xnew是產生的新解。如果新解優于舊解且產生的隨機數rand2的值小于響度值Ab，則接受新解，更新響度Ab和脈沖發射率rb，如式（13）和式（14）。

Atb=αAt-1b（13）

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

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

2.2 信息素矩陣

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

τtij=

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

τt-1ij，其他 （15）

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

2.3DBA

本文將種群的迭代過程分為兩部分：隨機迭代搜索和啟發式迭代搜索。在每次迭代中，蝙蝠b隨機選擇某一種迭代方式來搜索最優解。在隨機搜索中，蝙蝠b根據式（10）來更新自身的速度;在啟發式搜索中，蝙蝠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）表示了在啟發式搜索中第t次迭代后，主機和虛擬機的映射關系矩陣Xtb。

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

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

算法1詳細說明了DBA迭代尋找最優解的總體框架。其中，Xt-1表示第t-1次迭代后所有蝙蝠的位置的集合，PS是種群當前的Pareto最優解的集合，ran，rand1，rand2∈[0，1）是隨機數。

算法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的虛擬機放置方法

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

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

在算法2的復雜度分析方面，因為算法1的時間復雜度是O（m·n2），其中m表示種群的數量，n代表待遷移虛擬機的長度;非支配排序和擁擠距離（non-dominated sorting and crowding distance）的時間復雜度分別為O（m2）和O（2m log（2m）），迭代次數為I，所以整個算法的時間復雜度為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 實驗與結果分析

4.1 評價指標

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

SLATAH用來衡量主機提供的服務質量，如式（18）所示：

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

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

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

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

SLAV綜合評價單日內數據中心的服務質量，如式（20）所示：

SLAV=SLATAH×PDM（20）

ESV指標如式（21）所示：

ESV=EC×SLAV（21）

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

4.2 實驗配置

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

4.3 實驗結果及分析

本文將DBA-VMP同FFD[3]、多資源組合排序的首次適應遺傳算法（Combinatorial Order First-Fit Genetic Algorithm， COFFGA）[6]、使用蟻群系統的虛擬機放置（Ant Colony System-based VMP， ACS-VMP）算法[7]和資源使用率預測感知的最適降序（Utilization Prediction-aware BFD， UPBFD）算法[15]這四種虛擬機放置算法進行對比。為了獲得有效的對比結果，將5種放置算法結合四分位距（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兩組。每次整合時首先執行EOP（或IQR）算法對主機進行過載檢測，再通過OPDMS（或RS）算法將過載主機中的部分虛擬機遷出直至主機不再過載，再通過虛擬機放置算法給這些虛擬機找到合適的目的主機，最后將部分低負載主機中的全部虛擬機遷出將其切換至休眠狀態。實驗參數的初始化如下：N=10， fmax=1， fmin=0，R=0.7，r0b、A0b、α和γ的值為0.95，φ=0.3，iter=8。

4.3.1有效性

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

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

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

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

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

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

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

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

4.3.2高效性

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

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

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

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

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

5 結語

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

參考文獻 （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]朱占磊，李征，趙瑞蓮.基于線性權重最優支配的高維多目標優化算法[J].計算機應用，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。

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

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

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