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

鄧生君　張曉哲　肖立權(quán)　姬琳

摘要：針對云計算中虛擬機(jī)的放置問題，本文通過對量子粒子群算法的分析，提出一種改進(jìn)量子粒子群的放置算法。該算法以優(yōu)化數(shù)據(jù)中心能耗為目標(biāo)函數(shù)，根據(jù)粒子當(dāng)前的位置和全局最優(yōu)位置的關(guān)系，采用自適應(yīng)調(diào)整收縮-擴(kuò)張因子和粒子權(quán)值的方法，對量子粒子群算法的關(guān)鍵參數(shù)指標(biāo)進(jìn)行了改進(jìn)，提高算法的收斂速度及粒子尋找最優(yōu)解的能力。通過云計算仿真平臺CloudSim 的測試，表明改進(jìn)后的算法在保證滿足用戶請求的前提下，既提高了搜索效率，又降低了電源損耗。

關(guān)鍵詞：云計算 虛擬機(jī)放置 量子粒子群優(yōu)化算法

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）08-0152-03

Abstract：For the virtual machine placement problem in Cloud Computing ， an improved quantum particle swarm placement algorithm is proposed by analyzing the quantum particle swarm algorithm. The proposed algorithm models data center power consumption as the objective function. According to the relationship between current position and the global best one， an adaptive adjustment of contraction-dilation factor and particle weights method is adopted to improve the key parameter in quantum particle swarm algorithm，improving the convergence speed and the ability to find the optimal solution particle. Through the tests on CloudSim that is a cloud computing simulation platform， results show that under the premise to satisfy users requests， the proposed algorithm not only improves the search efficiency， but also reduces the power consumption.

Key Words：Cloud Computing； Virtual Machine Placement； Quantum-behaved Particle Swarm Optimization

1 引言

近年來，云計算已經(jīng)融入到計算機(jī)技術(shù)的各個領(lǐng)域，它與5G、物聯(lián)網(wǎng)、移動互聯(lián)網(wǎng)和大數(shù)據(jù)分析等都有相當(dāng)緊密的聯(lián)系，是未來信息產(chǎn)業(yè)的重要支撐和關(guān)鍵性技術(shù)。隨著云計算的不斷發(fā)展和壯大，底層的基礎(chǔ)設(shè)施規(guī)模也日益增大，如何在具有動態(tài)性和異構(gòu)性的復(fù)雜云計算環(huán)境下，保證每個用戶需求的同時，合理有效的分配物理資源給虛擬機(jī)，已成為云計算領(lǐng)域研究的一個重要問題。

云計算資源調(diào)度是一個NP難的問題，現(xiàn)有的云計算資源調(diào)度算法更多的是關(guān)注成本控制或資源使用率，采用動態(tài)的資源調(diào)度策略，實現(xiàn)了SLA（Service-Level Agreement）和運(yùn)營成本兩者之間的平衡；文獻(xiàn)提出一種基于遺傳算法的負(fù)載均衡調(diào)度方法，根據(jù)系統(tǒng)當(dāng)前狀態(tài)預(yù)測出放置后系統(tǒng)的結(jié)果，以此來選出最優(yōu)的放置方案，但這些方法忽略了分配過程中涉及的能耗因素。研究表明物理主機(jī)的電源消耗與CPU的使用率是呈線性關(guān)系的， 當(dāng)物理主機(jī)的CPU利用率增大時，物理主機(jī)節(jié)點(diǎn)的電源消耗呈線性增長。本文將資源分配和能耗結(jié)合在一起考慮，提出一種改進(jìn)量子粒子群的放置算法（Adaptive Quantum-behaved Particle Swarm Optimization-Mapping，AQPSO-M），從而在虛擬機(jī)放置的過程中實現(xiàn)放置效率和節(jié)能。

2 問題描述

2.1 基本定義

定義1：底層的Q臺物理主機(jī)被形式化為集合

，單個主機(jī)host有三個種資源描述（CPU、內(nèi)存和帶寬），表示為；n臺虛擬機(jī)被形式化為集合，其中每臺虛擬機(jī)有三種資源描述（CPU、內(nèi)存和帶寬），表示為。

定義2：映射矩陣，也可以被稱為虛擬機(jī)的放置方案。其中，表示第i個虛擬機(jī)沒能成功映射到物理主機(jī)節(jié)點(diǎn)j上，表示第i個虛擬機(jī)被成功映射到第j臺物理主機(jī)節(jié)點(diǎn)上。

定義3：向量表示物理主機(jī)的資源利用率用。

定義4：定義物理主機(jī)的能耗率為，其中是物理主機(jī)當(dāng)前的能耗，是物理主機(jī)j滿負(fù)載的最大功耗。

2.2 目標(biāo)函數(shù)及約束條件

目標(biāo)函數(shù)為完成虛擬機(jī)放置后

當(dāng)越大，相應(yīng)的電能損耗率也越大，在極限情況下，當(dāng)物理主機(jī)節(jié)點(diǎn)的CPU利用率為100%時，該物理主機(jī)節(jié)點(diǎn)的電能損耗率為1。

3 算法的改進(jìn)思想

3.1 確定粒子權(quán)值

4 基于改進(jìn)算法的虛擬機(jī)放置步驟

AQPSO-M算法的虛擬機(jī)放置步驟為：

步驟1：初始化粒子群規(guī)模、迭代次數(shù)和解空間維數(shù)；

步驟2：對云計算資源進(jìn)行編碼，每一個粒子對應(yīng)著一種資源調(diào)度方案；

步驟3：計算各個粒子的權(quán)值系數(shù)以及目標(biāo)函數(shù)適應(yīng)度值，以及所有粒子的目標(biāo)函數(shù)適應(yīng)度值的平均值；

步驟4：確定粒子個體平均最優(yōu)位置；

步驟5：計算粒子在第t次迭代時的局部最佳位置和粒子種群的全局最優(yōu)位置，并計算收縮擴(kuò)張系數(shù)δ；

步驟6：更新粒子隨機(jī)點(diǎn)的位置和最新位置；

步驟7：根據(jù)約束條件進(jìn)行判斷，當(dāng)前所求的解是否滿足約束條件，若滿足則輸出云計算資源調(diào)度的最優(yōu)解，否則跳到第3步繼續(xù)搜索直到滿足條件的解或達(dá)到最大迭代次數(shù)為止。

5 實驗及結(jié)果分析

5.1 實驗環(huán)境

為了驗證AQPSO-M算法在虛擬機(jī)映射時資源調(diào)度的有效性，本文采用的實驗仿真平臺是Cloudsim，對其進(jìn)行了擴(kuò)展，修改了VirtualMachine 類， VMAllocationPolicy 類和 DataCenterBroker類中相關(guān)方法和屬性，并與LFF（Least Full Fit）算法、PSO算法、QPSO算法進(jìn)行對比。實驗的參數(shù)設(shè)置如下：

仿真的硬件環(huán)境： InterCoreTM i5-2450M@2.50GHz，，8GB內(nèi)存，500G硬盤。軟件環(huán)境：windows 7操作系統(tǒng)，Eclipse8.6和javal.7.0語言開發(fā)工具。

在相同實驗條件下，PSO算法中c1和c2設(shè)為2，PSO、QPSO和AQPSO三種算法的種群規(guī)模設(shè)置為10，迭代次數(shù)設(shè)置為300次。

模擬的物理主機(jī)節(jié)點(diǎn)的參數(shù)配置如表1所示。

當(dāng)物理主機(jī)節(jié)點(diǎn)的CPU利用率為100%時耗電量記為250W；當(dāng)物理主機(jī)節(jié)點(diǎn)的CPU利用率為0%時，損耗的電量是175W。

模擬的虛擬機(jī)的參數(shù)配置如表2所示。

5.2 實驗結(jié)果與分析

5.2.1 任務(wù)完成時間的比較

通過對圖1任務(wù)完成時間的分析，可以看出：LFF算法在放置虛擬機(jī)時花費(fèi)的時間自始至終都最多，PSO、QPSO和AQPSO算法在虛擬機(jī)請求數(shù)量較少時，三種算法完成虛擬機(jī)放置的時間沒有太大差別；隨著虛擬機(jī)請求數(shù)量的增加，三種算法得到最優(yōu)放置方案的時間差距逐步增大。

5.2.2 負(fù)載和能耗的對比

如圖2所示：AQPSO-M算法比其他三種算法選出的放置方案中物理主機(jī)的CPU利用率和耗電率都較優(yōu)，這是因為算法關(guān)鍵參數(shù)的自適應(yīng)的優(yōu)化調(diào)整及目標(biāo)函數(shù)中對能耗的考慮，從而在一定程度上提高了搜索效率，并降低了電源損耗。

6 結(jié)語

本章主要針對云計算虛擬機(jī)放置過程中資源調(diào)度的問題，引入量子粒子群算法，根據(jù)粒子當(dāng)前的位置和全局最優(yōu)位置的關(guān)系，采用自適應(yīng)調(diào)整收縮-擴(kuò)張因子和粒子權(quán)值的方法，對量子粒子群算法的關(guān)鍵參數(shù)指標(biāo)進(jìn)行了改進(jìn)，提出一種改進(jìn)量子粒子群的映射算法AQPSO-M，算法以優(yōu)化數(shù)據(jù)中心能耗為目標(biāo)。通過仿真實驗和分析，驗證了AQPSO-M算法在搜索效率和節(jié)能方面的優(yōu)勢。

參考文獻(xiàn)

[1]唐紅，徐光俠.云計算研究與發(fā)展綜述[J].數(shù)字通信，2010，（6）：23-28.

[2]孫香花.云計算研究現(xiàn)狀與發(fā)展趨勢[J].計算機(jī)測量與控制，2011，19（5）：998-1001.

[3]Armbrust M， Fox A， Griffith R， et al. A view of cloud computing [J].Communications of the ACM， 2010，53（4）： 50-58.

[4]劉鵬.云計算[M].北京：電子工業(yè)出版社，2015.

[5]任崇廣.面向海量數(shù)據(jù)處理領(lǐng)域的云計算及其關(guān)鍵技術(shù)研究[D].南京：南京理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，2013.

[6]Van H N， Tran F D， Menaud J M. Autonomic virtual resource management for service hosting platforms[C]/ICSE Workshop on Software Engineering Challenges of Cloud.2009：1-8.

[7]Hu J， Gu J， Sun G， etal. A scheduling strategy on load balancing of virtual machine resources in cloud computing environment [C]. Parallel Architectures， Algorithms and Programming （PAAP）， 2010 Third International Symposium on. IEEE， 2010： 89-96.

[8]Chen Y， Das A， Qin W， etal. Managing server energy and operational costs in hosting centers [C]. ACM SIGMETRICS Performance Evaluation Review. ACM， 2005， 33（1）： 303-314.

[9]Kusic D， Kephart J O， Hanson J E， etal. Power and performance management of virtualized computing environments via lookahead control [J]. Cluster computing， 2009，12（1）： 1-15.

[10]孫俊，方偉，吳小俊等.量子行為粒子群優(yōu)化；原理及其應(yīng)用[M].北京：清華大學(xué)出版社，2011：31-42.