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

曹盟盟++姚文斌

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

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

中圖分類號：TP319

文獻標識碼：A

DOI：10.3969/j.issn.1003-6970.2015.12.021

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

0 引言

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

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

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

l 問題描述

1.1 云資源調度模型

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

1.2 基本定義

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

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

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

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

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

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

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

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

2.2.1 算法設計

1.粒子群算法編碼

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

2.分析與設計慣性權重ω

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

3.確定算法的適應度函數

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

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

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

5.引入分組思想

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

2.2.2 算法步驟

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

Step3：根據適應度函數公式（6）依次計算每個子群中每個粒子的適應值F；

Step4：對于每個粒子，比較個體當前適應值和歷史最優(yōu)位置p_ibest，如果當前適應值較好，則將此粒子當前的位置作為當前最優(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：根據公式（1）和公式（2）更新每個粒子的速度和位置信息；

3 仿真實驗

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

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

3.2 結果與分析

3.2.1 負載不均衡度E的比較

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

3.2.2 資源利用率比較

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

4 結論

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