基于優(yōu)化粒子群算法的虛擬機部署策略*

董德坤 張亞欽 徐克祥

（中國石油大學(xué)（華東）計算機科學(xué)與技術(shù)學(xué)院 青島 266580）

1 引言

云計算是一種利用互聯(lián)網(wǎng)實現(xiàn)隨時隨地、按需便捷地訪問共享資源池（如計算設(shè)施、存儲設(shè)備、應(yīng)用程序等）的計算模式，本文關(guān)注的是物理服務(wù)器的虛擬化。由于云基礎(chǔ)設(shè)施依賴于虛擬化技術(shù)，云計算的大規(guī)模使用將增加更多的虛擬機請求，從而增加虛擬化基礎(chǔ)設(shè)施的壓力，因此需要一個有效的虛擬機調(diào)度策略。

本文提出一種改進的粒子群算法，該算法迭代過程初期引入混沌策略，使粒子群分布有著良好的遍歷均勻性；使用隨機分組策略，作為改進粒子群的核心過程，設(shè)置兩個目標(biāo)函數(shù)，利用歐氏距離尋求多目標(biāo)粒子群優(yōu)化算法的最優(yōu)解。將改進后的算法應(yīng)用到云計算虛擬機部署，以物理機資源利用率、虛擬機遷移量為目標(biāo)函數(shù)。

2 相關(guān)工作

虛擬機部署是將虛擬機映射到物理機的過程。由于云基礎(chǔ)設(shè)施是完全虛擬的，虛擬機的部署成為云系統(tǒng)的核心問題。為此，人們進行了大量有關(guān)優(yōu)化虛擬機部署的研究工作，Xu等［1］針對云計算環(huán)境下虛擬機的動態(tài)部署問題，提出了虛擬機動態(tài)部署的多目標(biāo)綜合評價模型和改進的多目標(biāo)粒子群優(yōu)化算法（IMOPSO）。胥小波等［2］提出了一種新的混沌粒子群優(yōu)化算法，不同于已有的混沌粒子群算法的簡單粒子序列替換，該算法將混沌融入到粒子運動過程中，使粒子群在混沌與穩(wěn)定之間交替運動，逐步向最優(yōu)點靠近。朱亞會等［3］提出一種基于資源利用率均衡的虛擬機調(diào)度模型。該模型將虛擬機調(diào)度問題抽象為不定維向量裝箱模型。楊靖等［4］引入多種群進化模式提高算法收斂速度，并在此基礎(chǔ)上加入高斯學(xué)習(xí)策略避免局部最優(yōu)，提出了一種多種群高斯學(xué)習(xí)粒子群優(yōu)化（MGL-PSO）算法。張笑燕［5］等提出了一種虛擬機部署方案，該方案的目的是減少主機上的資源碎片。曹盟盟等［6］在算法中引入分組思想，通過對初始種群進行隨機分組，避免算法陷入早熟現(xiàn)象。經(jīng)典的智能算法有蟻群算法、遺傳算法、微分進化算法等，Garg［7～9］等利用遺傳算法（GA）、蟻群算法、微分進化（DE）相結(jié)合的粒子群優(yōu)化算法，保持了多種算法的優(yōu)點。 Zhao［10］提出了一種基于PSO 的改進算法，根據(jù)云計算環(huán)境中資源的使用成本來解決任務(wù)調(diào)度問題。Dashti等［11］利用粒子群優(yōu)化（PSO）在過載的PMs 中重新分配vm，并合并負(fù)載不足的PMs 以節(jié)省電能。

3 資源浪費模型

3.1 問題描述

本文的研究內(nèi)容是基于粒子群算法提出一種虛擬機部署方案，通過合理地部署虛擬機以減少云系統(tǒng)能耗。在云系統(tǒng)中，虛擬機分為已部署的虛擬機和新請求的虛擬機，系統(tǒng)圖如圖1所示。

圖1 系統(tǒng)圖

本文提出的虛擬機部署方案對物理主機CPU、內(nèi)存和網(wǎng)絡(luò)帶寬三種資源的負(fù)載情況進行監(jiān)控。假設(shè)云環(huán)境中有n 個物理機，物理機閾值表示為。m 個虛擬機，虛擬機需求表示為。虛擬機的部署情況由矩陣Xmxn表示，xij值為1表示第i個虛擬機部署在第j個物理機上。

3.2 目標(biāo)函數(shù)和約束函數(shù)

目標(biāo)函數(shù)如下：

約束函數(shù)如下：

其中，式（1）表示虛擬機利用率。式（2）表示虛擬機的遷移數(shù)量。式（3）表示同一虛擬機只能部署在同一物理機上。式（4）、（5）、（6）分別表示多個虛擬機部署在物理機上時，虛擬機CPU、內(nèi)存、帶寬資源需求量不超過物理機CPU、內(nèi)存、帶寬閾值。

4 改進算法設(shè)計

4.1 傳統(tǒng)粒子群算法

粒子群算法是進化算法的一種，在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。式（7）為粒子速度更新公式，式（8）為粒子位置更新公式。在d 維空間的第i 個粒子，位置表示為Xid=(xi1,xi2,…,xid)，速度表示為Vid=(vi1,vi2,…,vid)。

4.2 改進的多目標(biāo)粒子群算法設(shè)計

Kennedy 認(rèn)為，具有大鄰域的粒子群優(yōu)化算法在處理簡單問題時表現(xiàn)得更好，而具有小鄰域的粒子群優(yōu)化算法在處理復(fù)雜問題時表現(xiàn)得更好［12］。本文對傳統(tǒng)粒子群算法進行改進，首先引入混沌算法對粒子群初始化，迭代過程使用隨機分組策略。

1）混沌映射

利用混沌映射初值敏感性、遍歷性特點，隨機初始化一個粒子，并通過混沌映射得到多個粒子的初始值，改變初始粒子群的提取過程。利用混沌映射擴大初始粒子群，得到尋優(yōu)粒子群，使得種群粒子多樣化。Tent 映射結(jié)構(gòu)簡單，具有很好的遍歷性，公式如下。

2）慣性權(quán)重w

w 是影響算法搜索結(jié)果和收斂速度的關(guān)鍵參數(shù)，w 過大有利于全局尋優(yōu)，w 過小有利于局部尋優(yōu)。根據(jù)w 取值對搜索結(jié)果的影響，本文采用線性遞減方式設(shè)定w值。如下所示。

3）隨機分組

粒子群算法迭代過程通過隨機分組策略更新，3 個粒子組成一個小群體，每隔5 代各小群體間粒子進行隨機重組。群體間兩個粒子不足以構(gòu)成一個良好的群體，而五個粒子具有較好的局部搜索能力和較弱的全局搜索能力。三個粒子實現(xiàn)了它們之間的平衡，群體顯示出更好的全局搜索能力［13］。

4）最優(yōu)解設(shè)計

通過歐氏距離法［1］更新目標(biāo)函數(shù)和粒子群，策略步驟表示如下。

（1）群體內(nèi)粒子利用組內(nèi)信息更新速度和位置。目標(biāo)函數(shù)f1 和f2 單獨更新，從每次迭代結(jié)果中，選擇兩個群體最優(yōu)值f-Opt［1］和f-Opt［2］。

（2）計算兩個群體最優(yōu)間的距離。

（3）個體最優(yōu)值的確定。

如果dl[i]

如果dl[i] >df，取二者平均值作為個體最優(yōu)。

（4）更新至迭代結(jié)束。

5）虛擬機編碼

粒子群算法中，設(shè)共有p 個粒子。云系統(tǒng)中，將粒子的速度和位置維數(shù)設(shè)置為物理機數(shù)目n，并將物理機編號為1到n。粒子的位置向量的每一項表示虛擬機i 在該物理機上，粒子位置向量的值表示虛擬機的一種部署策略。

5 實驗

本文選擇CloudSim仿真平臺進行仿真實驗，用基本CloudSim 類中的繼承類實現(xiàn)EPSO 算法。實驗環(huán)境如下，編譯環(huán)境JDK 1.8，編譯軟件Eclipse 4.6，仿真云計算環(huán)境CloudSim 3.0，物理機的數(shù)量為100，虛擬機的數(shù)量為200。所有服務(wù)器都有相同的資源分配：10個處理單元的CPU、20GB內(nèi)存和100M 帶寬。設(shè)計仿真實驗，與經(jīng)典粒子群算法進行對比。

我們比較了多目標(biāo)粒子群算法與傳統(tǒng)的粒子群算法PSO，分別從資源利用率f1，虛擬機遷移數(shù)f2 兩方面進行對比分析。其中PSO 對兩個目標(biāo)的關(guān)注度一致。在CloudSim平臺上，進行仿真實驗記錄相關(guān)數(shù)據(jù)，將實驗結(jié)果數(shù)據(jù)進行對比分析，最后得出兩種算法的實驗效果分布圖。

圖2 表示了在不同服務(wù)請求下算法的資源利用率，證明我們提出的改進算法是有效的，資源利用率高于其他算法。圖3 表示了虛擬機的遷移次數(shù)，PSO算法下虛擬機遷移了73次，EPSO算法下虛擬機遷移了51 次，所提出的算法在虛擬機遷移次數(shù)上少于PSO算法。

圖2 兩種算法下的資源利用率

圖3 兩種算法下的遷移次數(shù)

實驗結(jié)果表明，由于初期粒子群分布更有遍歷性和均勻性，保持種群多樣性等優(yōu)點，使用小群迭代更新，這些小群被頻繁地重新組合以在群之間交換信息。在不失去穩(wěn)定性的情況下，通過歐式距離方法選擇帕累托最優(yōu)解，帕累托最優(yōu)解有更好的分布性和收斂性。該算法與經(jīng)典算法相比，資源利用率、遷移次數(shù)均取得了更好的結(jié)果。

6 結(jié)語

云計算通過使用虛擬機技術(shù)提高了數(shù)據(jù)中心的資源利用率。虛擬機放置算法作為云計算的關(guān)鍵技術(shù)，具有重要研究意義。本文提出了優(yōu)化的粒子群算法，通過平衡資源利用、虛擬機遷移優(yōu)化數(shù)據(jù)中心性能。EPSO 算法首先混沌初始化粒子群，使群體分布具有遍歷性和均勻性，使用小群迭代更新，這些小群被頻繁地重新組合以在群之間交換信息。設(shè)計仿真實驗，將我們的改進算法與經(jīng)典PSO算法進行比較，驗證了改進后的方法的可行性和有效性。實驗結(jié)果表明，該算法平衡了資源利用、虛擬機遷移，優(yōu)化了數(shù)據(jù)中心性能。