基于改進(jìn)粒子群算法的虛擬機(jī)放置算法

曹盟盟++姚文斌

摘要：云計(jì)算通過使用虛擬機(jī)技術(shù)提高了數(shù)據(jù)中心的資源利用率。虛擬機(jī)放置算法作為云計(jì)算的關(guān)鍵技術(shù)，具有重要研究意義?，F(xiàn)有虛擬機(jī)放置算法往往只關(guān)注成本控制和云資源使用率，忽略了負(fù)載均衡對(duì)系統(tǒng)性能的影響。針對(duì)該問題，本文在標(biāo)準(zhǔn)的粒子群優(yōu)化算法基礎(chǔ)上進(jìn)行改進(jìn)，首先設(shè)計(jì)多目標(biāo)函數(shù)時(shí)引入負(fù)載不均衡度概念，然后通過系統(tǒng)實(shí)時(shí)負(fù)載隨機(jī)生成初始化種群，并在算法中引入分組思想，通過對(duì)初始種群進(jìn)行隨機(jī)分組，避免算法陷入早熟現(xiàn)象。通過CloudSim模擬平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，表明改進(jìn)后的算法更利于云數(shù)據(jù)中心進(jìn)入負(fù)載均衡狀態(tài)，并有較高的資源利用率。

關(guān)鍵詞：云計(jì)算；虛擬機(jī)放置；負(fù)載均衡；多目標(biāo)優(yōu)化；粒子優(yōu)化群算法

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.3969/j.issn.1003-6970.2015.12.021

本文著錄格式：曹盟盟，姚文斌.基于改進(jìn)粒子群算法的虛擬機(jī)放置算法[J].軟件，2015，36（12）：89-92

0 引言

云計(jì)算概念自2007年提出后產(chǎn)生了巨大的影響，全世界都把云計(jì)算作為重點(diǎn)新興戰(zhàn)略產(chǎn)業(yè)，為搶占云計(jì)算制高點(diǎn)，很多國家都研制并且出臺(tái)了云計(jì)算的戰(zhàn)略規(guī)劃，加快部署并推動(dòng)國家級(jí)的云計(jì)算相關(guān)應(yīng)用和云計(jì)算基礎(chǔ)設(shè)施，同時(shí)也成為工業(yè)界和學(xué)術(shù)界的研究執(zhí)占。

云計(jì)算的關(guān)鍵技術(shù)是資源調(diào)度技術(shù)，由于虛擬化技術(shù)的引入，云資源調(diào)度以虛擬機(jī)為單位進(jìn)行，將物理資源分配給用戶任務(wù)對(duì)應(yīng)的虛擬機(jī)。由于系統(tǒng)規(guī)模增大導(dǎo)致系統(tǒng)具有復(fù)雜性、多樣性、異構(gòu)性和動(dòng)態(tài)性等特征，使得云數(shù)據(jù)中心基于虛擬機(jī)的資源調(diào)度充滿挑戰(zhàn)性，同時(shí)也決定了虛擬機(jī)放置問題是一個(gè)NP-hard問題。在云環(huán)境中，虛擬機(jī)放置時(shí)間比調(diào)度算法所需的時(shí)間長得多，因此云資源調(diào)度需要考慮的主要是虛擬機(jī)如何放置的問題。

數(shù)據(jù)中心服務(wù)器的負(fù)載是影響系統(tǒng)性能的瓶頸，由于CPU時(shí)間分片和網(wǎng)絡(luò)等影響，服務(wù)器負(fù)載較高時(shí)運(yùn)行任務(wù)具有較長的平均完成時(shí)間，因此保證數(shù)據(jù)中心的負(fù)載均衡很重要。現(xiàn)有一些算法往往只關(guān)注成本控制和云資源使用率，忽略了負(fù)載均衡對(duì)系統(tǒng)性能的影響，雖然在一定程度上緩解了云資源與用戶需求的矛盾，但云數(shù)據(jù)中心的資源規(guī)模大、資源間差異大、組成復(fù)雜等問題直接導(dǎo)致數(shù)據(jù)中心資源的浪費(fèi)，現(xiàn)如今還沒有很好的虛擬機(jī)放置算法快速實(shí)現(xiàn)數(shù)據(jù)中心的負(fù)載均衡，因此研究先進(jìn)的虛擬機(jī)放置算法具有重要的現(xiàn)實(shí)和學(xué)術(shù)意義。

l 問題描述

1.1 云資源調(diào)度模型

根據(jù)云計(jì)算的特點(diǎn)，建立云資源調(diào)度三層結(jié)構(gòu)二級(jí)調(diào)度模型如圖l所示。三層結(jié)構(gòu)分別為用戶層、虛擬層和物理層。二級(jí)調(diào)度為任務(wù)調(diào)度和虛擬機(jī)調(diào)度，任務(wù)調(diào)度為第一級(jí)調(diào)度，發(fā)生在在用戶層和虛擬層之間；虛擬機(jī)調(diào)度為第二級(jí)調(diào)度，發(fā)生在虛擬層和物理層之間。虛擬資源的調(diào)度和分配策略是云計(jì)算的核心問題，本文主要研究云環(huán)境下二級(jí)調(diào)度過程中的虛擬機(jī)資源分配，即將虛擬機(jī)放置到滿足條件的服務(wù)器上。

1.2 基本定義

定義1：云環(huán)境中的虛擬機(jī)資源調(diào)度是將M個(gè)虛擬機(jī)部署到N個(gè)物理機(jī)上，映射模型相當(dāng)于將M個(gè)不同元素放到N個(gè)不同元素的集合，共有NM種解決方案，該問題屬于裝箱問題，即給定集合PM{P₁，P₂，……，P_N}和集合VM{V₁，V₂，……，V_M}，把VM中的M個(gè)元素放到PM的N個(gè)元素中，保證使用的PM中元素?cái)?shù)量最少。

定義2：N為云數(shù)據(jù)中心物理機(jī)的數(shù)量，N_use為數(shù)據(jù)中心中已經(jīng)占用的物理機(jī)的數(shù)量；U_use為數(shù)據(jù)中心物理機(jī)CPU的平均利用率，U_iuse為物理機(jī)i中CPU的利用率；M_nse為數(shù)據(jù)中心物理機(jī)的內(nèi)存平均利用率，M_iuse為物理機(jī)i中內(nèi)存的利用率；S_use為數(shù)據(jù)中心物理機(jī)總存儲(chǔ)的平均利用率，S_iuse為物理機(jī)i中硬盤的利用率。

（3）f₃=Min（E），f₃表示將虛擬機(jī)分配到物理機(jī)后數(shù)據(jù)中心的負(fù)載不均衡度函數(shù)，其中E即上文1.2定義的負(fù)載不均衡度，該函數(shù)表示E值越小表示系統(tǒng)越平衡。

2 基于改進(jìn)粒子群算法的虛擬機(jī)放置算法

2.1 粒子群優(yōu)化算法介紹

1995年由美國博士Kennedy和Eberhart通過研究鳥群覓食行為提出粒子群算法（Particle Swarm Optimization，PSO）。設(shè)想場景：一群鳥在隨機(jī)搜尋食物，區(qū)域內(nèi)僅有一塊食物，所有鳥都不知道食物在哪里，但它們知道當(dāng)前位置離食物多遠(yuǎn)，那么找到食物最有效的策略就是搜尋目前離食物最近鳥的周圍區(qū)域。PSO算法是一種基于群體的自適應(yīng)搜索優(yōu)化算法。算法中每個(gè)優(yōu)化問題的潛在可能解都稱其為“粒子”（Particle），每個(gè)粒子都有一個(gè)被目標(biāo)函數(shù)所決定的適應(yīng)值（Fitness Value），還有一個(gè)速度決定飛翔的方向和距離。每個(gè)粒子均受局部最優(yōu)信息和全局最優(yōu)信息影響，以一定速度在整個(gè)解空間飛行，飛行速度和位置由個(gè)體飛行經(jīng)驗(yàn)和群體飛行經(jīng)驗(yàn)動(dòng)態(tài)調(diào)整，以便用于信息交換。通過大量實(shí)驗(yàn)研究，證實(shí)了群體中個(gè)體之間的社會(huì)協(xié)作和信息共享有助于整體進(jìn)化，用公式表示如下：

雖然標(biāo)準(zhǔn)PSO算法優(yōu)點(diǎn)很多，但是隨機(jī)性很大，多樣性比較差，很容易陷入局部最優(yōu)現(xiàn)象，因此需要完善，下面將介紹本文改進(jìn)的粒子群算法。

2.2 基于改進(jìn)粒子群算法的虛擬機(jī)放置算法

2.2.1 算法設(shè)計(jì)

1.粒子群算法編碼

首先對(duì)n個(gè)待部署虛擬機(jī)進(jìn)行編碼形成隊(duì)列，然后通過虛擬機(jī)放置算法得到虛擬機(jī)與數(shù)據(jù)中心m個(gè)物理機(jī)的映射關(guān)系，最后按照映射關(guān)系將虛擬機(jī)放置到對(duì)應(yīng)物理機(jī)上，從而實(shí)現(xiàn)優(yōu)化目標(biāo)。種群中的每個(gè)粒子的位置和速度分別用公式（3）和公式（4）表示，如下所示：

2.分析與設(shè)計(jì)慣性權(quán)重ω

影響算法搜索結(jié)果和收斂速度的關(guān)鍵參數(shù)就是ω，經(jīng)過先前的大量實(shí)驗(yàn)研究，ω過大有利于全局尋優(yōu)，ω過小有利于局部尋優(yōu)。根據(jù)ω取值對(duì)搜索結(jié)果的影響，可以采用經(jīng)典的線性遞減方式設(shè)定ω的值如公式（5）所示。

3.確定算法的適應(yīng)度函數(shù)

根據(jù)1.3提出的算法目標(biāo)，通過對(duì)目標(biāo)優(yōu)化要求的不同設(shè)定相應(yīng)的權(quán)值，實(shí)現(xiàn)多目標(biāo)優(yōu)化。本算法的目標(biāo)是在迭代次數(shù)范圍內(nèi)找到使適應(yīng)度函數(shù)值最小的資源分配方案，即最終的虛擬機(jī)放置方案。適應(yīng)度函數(shù)可以定義如下公式：

4.種群初始化引入按資源需求和實(shí)時(shí)負(fù)載分配的思想

根據(jù)虛擬機(jī)對(duì)資源的需求情況選擇能夠滿足其要求的物理機(jī)，即所選的物理機(jī)一定要滿足虛擬機(jī)對(duì)資源的需求，同時(shí)根據(jù)1.2的定義4物理機(jī)部署虛擬機(jī)后不至于過載。

5.引入分組思想

首先將種群隨機(jī)分成若干份等量的小粒子群，然后在每一個(gè)子群里隨機(jī)設(shè)置參數(shù)，進(jìn)行粒子群優(yōu)化算法尋優(yōu)，最后再對(duì)全部最優(yōu)解取最小值為最終最分配方案。

2.2.2 算法步驟

Stepl：按照初始種群方案生成有M個(gè)粒子的種群，每個(gè)粒子編號(hào)為l到M，將M個(gè)粒子隨機(jī)分成N個(gè)獨(dú)立的子群空間，每個(gè)子群的粒子個(gè)數(shù)為m=M/N：

Step3：根據(jù)適應(yīng)度函數(shù)公式（6）依次計(jì)算每個(gè)子群中每個(gè)粒子的適應(yīng)值F；

Step4：對(duì)于每個(gè)粒子，比較個(gè)體當(dāng)前適應(yīng)值和歷史最優(yōu)位置p_ibest，如果當(dāng)前適應(yīng)值較好，則將此粒子當(dāng)前的位置作為當(dāng)前最優(yōu)的位置并更新p_ibest，否則保持p_ibest不變；

Step5：對(duì)于每個(gè)粒子，比較當(dāng)前最優(yōu)位置p_ibest和子群體中整體的最優(yōu)位置P_qgbest，如果當(dāng)前最優(yōu)位置較好，則將其作為當(dāng)前群體最優(yōu)位置并更新P_qgbest，否則P_qgbest不變（q=l，2…N）；

Step6：根據(jù)公式（1）和公式（2）更新每個(gè)粒子的速度和位置信息；

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置

為了驗(yàn)證基于分組的粒子群優(yōu)化算法GPSO在云環(huán)境下虛擬機(jī)資源分配問題上的可行性，本文擴(kuò)展了CloudSim平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，并與輪詢算法Round Robin和標(biāo)準(zhǔn)的PSO算法進(jìn)行了比較。參數(shù)設(shè)置如表l、表2所示。

3.2 結(jié)果與分析

3.2.1 負(fù)載不均衡度E的比較

系統(tǒng)的負(fù)載不均衡度隨著虛擬機(jī)數(shù)量的增加而減小。圖2表示三種算法分別在不同虛擬機(jī)規(guī)模時(shí)系統(tǒng)的負(fù)載不均衡度。由圖2可知GPSO算法的負(fù)載不均衡度E小于其他兩個(gè)算法，說明GPSO算法在負(fù)載平衡方面的性能優(yōu)于其他兩個(gè)算法。這是因?yàn)镻SO算法初始種群是隨機(jī)生成的，而GPSO算法的初始種群是根據(jù)系統(tǒng)的實(shí)時(shí)負(fù)載隨機(jī)生成，并將負(fù)載不均衡度作為目標(biāo)函數(shù)進(jìn)行搜索。輪詢算法沒有考慮物理機(jī)實(shí)時(shí)負(fù)載，也沒有優(yōu)化目標(biāo)策略。

3.2.2 資源利用率比較

如圖3所示，GPSO算法比其它兩種算法的資源利用率更高，這是因?yàn)槟繕?biāo)函數(shù)包含了對(duì)系統(tǒng)資源利用率的優(yōu)化策略，從而一定程度上避免了系統(tǒng)資源的浪費(fèi)。

4 結(jié)論

本文針對(duì)現(xiàn)有虛擬機(jī)資源放置算法只考慮云資源的能耗和使用率，忽略負(fù)載均衡對(duì)系統(tǒng)性能影響的問題，提出了基于分組的改進(jìn)粒子群算法（Grouped Particle Swarm Optimization：GPSO），通過最小化云數(shù)據(jù)中心的負(fù)載不均衡度達(dá)到系統(tǒng)的負(fù)載平衡。與標(biāo)準(zhǔn)粒子群算法中隨機(jī)生成初始種群的方式不同，本文根據(jù)系統(tǒng)的實(shí)時(shí)負(fù)載來隨機(jī)生成初始種群，在算法中引入分組的思想，將該種群進(jìn)行隨機(jī)分組，通過比較各組的全局最優(yōu)解得到最終分配方案。通過CloudSim平臺(tái)仿真實(shí)驗(yàn)表明，改進(jìn)算法生成的資源分配方案較原算法能有更好的負(fù)載均衡、更高的資源利用率，證實(shí)了該算法的有效性。