基于改進粒子群算法的虛擬機放置算法

曹盟盟++姚文斌

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

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

中圖分類號：TP319

文獻標識碼：A

DOI：10.3969/j.issn.1003-6970.2015.12.021

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

0 引言

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

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

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

l 問題描述

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

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

1.2 基本定義

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

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

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

2 基于改進粒子群算法的虛擬機放置算法

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

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

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

2.2 基于改進粒子群算法的虛擬機放置算法

2.2.1 算法設(shè)計

1.粒子群算法編碼

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

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

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

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

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

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

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

5.引入分組思想

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

2.2.2 算法步驟

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

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

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

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

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

3 仿真實驗

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

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

3.2 結(jié)果與分析

3.2.1 負載不均衡度E的比較

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

3.2.2 資源利用率比較

如圖3所示，GPSO算法比其它兩種算法的資源利用率更高，這是因為目標函數(shù)包含了對系統(tǒng)資源利用率的優(yōu)化策略，從而一定程度上避免了系統(tǒng)資源的浪費。

4 結(jié)論

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