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

鄧生君　張曉哲　肖立權　姬琳

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

關鍵詞：云計算 虛擬機放置 量子粒子群優化算法

中圖分類號：TP301.6 文獻標識碼：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 引言

近年來，云計算已經融入到計算機技術的各個領域，它與5G、物聯網、移動互聯網和大數據分析等都有相當緊密的聯系，是未來信息產業的重要支撐和關鍵性技術。隨著云計算的不斷發展和壯大，底層的基礎設施規模也日益增大，如何在具有動態性和異構性的復雜云計算環境下，保證每個用戶需求的同時，合理有效的分配物理資源給虛擬機，已成為云計算領域研究的一個重要問題。

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

2 問題描述

2.1 基本定義

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

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

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

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

定義4：定義物理主機的能耗率為，其中是物理主機當前的能耗，是物理主機j滿負載的最大功耗。

2.2 目標函數及約束條件

目標函數為完成虛擬機放置后

當越大，相應的電能損耗率也越大，在極限情況下，當物理主機節點的CPU利用率為100%時，該物理主機節點的電能損耗率為1。

3 算法的改進思想

3.1 確定粒子權值

4 基于改進算法的虛擬機放置步驟

AQPSO-M算法的虛擬機放置步驟為：

步驟1：初始化粒子群規模、迭代次數和解空間維數；

步驟2：對云計算資源進行編碼，每一個粒子對應著一種資源調度方案；

步驟3：計算各個粒子的權值系數以及目標函數適應度值，以及所有粒子的目標函數適應度值的平均值；

步驟4：確定粒子個體平均最優位置；

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

步驟6：更新粒子隨機點的位置和最新位置；

步驟7：根據約束條件進行判斷，當前所求的解是否滿足約束條件，若滿足則輸出云計算資源調度的最優解，否則跳到第3步繼續搜索直到滿足條件的解或達到最大迭代次數為止。

5 實驗及結果分析

5.1 實驗環境

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

仿真的硬件環境： InterCoreTM i5-2450M@2.50GHz，，8GB內存，500G硬盤。軟件環境：windows 7操作系統，Eclipse8.6和javal.7.0語言開發工具。

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

模擬的物理主機節點的參數配置如表1所示。

當物理主機節點的CPU利用率為100%時耗電量記為250W；當物理主機節點的CPU利用率為0%時，損耗的電量是175W。

模擬的虛擬機的參數配置如表2所示。

5.2 實驗結果與分析

5.2.1 任務完成時間的比較

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

5.2.2 負載和能耗的對比

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

6 結語

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

參考文獻

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

[2]孫香花.云計算研究現狀與發展趨勢[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].北京：電子工業出版社，2015.

[5]任崇廣.面向海量數據處理領域的云計算及其關鍵技術研究[D].南京：南京理工大學計算機科學與工程學院，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]孫俊，方偉，吳小俊等.量子行為粒子群優化；原理及其應用[M].北京：清華大學出版社，2011：31-42.