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

唐忠原，何利文，黃 俊，袁 野

(南京郵電大學(xué) 計算機(jī)學(xué)院，江蘇 南京 210046)

0 引 言

云計算[1]是由分布式計算、網(wǎng)格計算及并行計算等技術(shù)發(fā)展而來的，將大量計算、存儲和軟件等資源融合在一起，構(gòu)成超大規(guī)模且高性能、可擴(kuò)充性的虛擬IT資源池，再通過服務(wù)器接口向廣大云用戶提供按需計費(fèi)的獨(dú)特商業(yè)服務(wù)模式[2]。隨著云服務(wù)的發(fā)展，數(shù)據(jù)中心變得異常龐大，巨大的數(shù)據(jù)中心需要消耗大量的能源；而根據(jù)IBM公司的統(tǒng)計表明，能源成本占數(shù)據(jù)中心總運(yùn)營成本的50%，而中國的數(shù)據(jù)中心能耗已達(dá)三峽的年發(fā)電量[3]。耗能問題成為目前數(shù)據(jù)中心最具挑戰(zhàn)性的問題；同時，數(shù)據(jù)中心的通信流量也不斷增大，若不進(jìn)行優(yōu)化，會造成網(wǎng)絡(luò)流量聚集，形成鏈路熱點(diǎn)，甚至導(dǎo)致通信阻塞，嚴(yán)重影響數(shù)據(jù)中心的運(yùn)行效率與云計算服務(wù)的服務(wù)質(zhì)量[4]。

降低數(shù)據(jù)中心的能耗與通信流量的常用策略有虛擬機(jī)初始放置[4-6]和虛擬機(jī)遷移[7-8]。虛擬機(jī)遷移會花費(fèi)一定的時間、消耗大量的資源，并且會影響服務(wù)器上其他虛擬機(jī)的運(yùn)行，導(dǎo)致系統(tǒng)性能下降。另外，實(shí)現(xiàn)遷移還需要額外的網(wǎng)絡(luò)存儲系統(tǒng)和高速通信網(wǎng)絡(luò)的支持。若云計算系統(tǒng)中出現(xiàn)大量的虛擬機(jī)遷移，將導(dǎo)致無法滿足服務(wù)等級協(xié)議(service level agreement，SLA)。因此，降低數(shù)據(jù)中心的能耗與通信量的最簡單最直接的方式就是優(yōu)化虛擬機(jī)的初始放置。

對于虛擬機(jī)放置問題，文獻(xiàn)[9]采用能源感知的粒子群優(yōu)化算法優(yōu)化數(shù)據(jù)中心的能耗問題，該文對粒子群優(yōu)化算法進(jìn)行了改進(jìn)，使用新的編碼策略使其適合解決離散優(yōu)化問題。文獻(xiàn)[10]提出了多資源的能耗模型，在該模型下提出了基于粒子群算法的高效能虛擬機(jī)放置策略，可以有效提高系統(tǒng)資源的利用率。文獻(xiàn)[11]根據(jù)分析不同虛擬機(jī)的負(fù)載特征，提出并實(shí)現(xiàn)了一個基于負(fù)載特征的虛擬機(jī)放置策略，利用各種虛擬機(jī)負(fù)載的互補(bǔ)性，進(jìn)行多次配對，得到由多臺虛擬機(jī)組成的配對組，對配對組統(tǒng)一分配服務(wù)器；同樣文獻(xiàn)[12]以利用虛擬機(jī)負(fù)載的歷史數(shù)據(jù)作為分析的依據(jù)，提出了一種基于虛擬機(jī)負(fù)載高峰特征的虛擬機(jī)放置策略,通過更好地復(fù)用物理主機(jī)資源來實(shí)現(xiàn)資源共享。文獻(xiàn)[13]使用能源感知、流量感知的策略重點(diǎn)對三種常見的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)?Fat-tree，VL2，VL2N-Tree)的通信鏈路的能耗進(jìn)行優(yōu)化，該文首先通過流量感知對虛擬機(jī)進(jìn)行分組，使得通信量較大的虛擬機(jī)成為一組，再通過距離感知策略將各組虛擬機(jī)群放置在合適的服務(wù)器上。

在上述研究的基礎(chǔ)上，文中提出了一種改進(jìn)粒子群算法的虛擬機(jī)放置策略，首先對原始粒子群算法的參數(shù)進(jìn)行相應(yīng)的重定義或修改使其適合解決離散優(yōu)化問題，再通過突變策略增強(qiáng)粒子群的多樣性以避免微粒因早熟而陷于局部最優(yōu)的問題。

1 模型設(shè)計

1.1 場景描述

目前數(shù)據(jù)中心的設(shè)計與操作很少考慮到系統(tǒng)的能耗與網(wǎng)絡(luò)擁塞，容易造成數(shù)據(jù)中心的能耗與全網(wǎng)通信量過大、網(wǎng)絡(luò)擁塞嚴(yán)重等問題。為了應(yīng)對通信鏈路故障與網(wǎng)絡(luò)峰值，通常是使用大量冗余鏈路并擴(kuò)大鏈路的帶寬，但該方式容易導(dǎo)致大量的資源浪費(fèi)。文中重點(diǎn)考慮Fat-tree樹形結(jié)構(gòu)網(wǎng)絡(luò)拓?fù)?，具有較強(qiáng)的網(wǎng)絡(luò)容錯性、較大的吞吐量、便于擴(kuò)展等特點(diǎn)，廣泛應(yīng)用于數(shù)據(jù)中心的構(gòu)建；其交換機(jī)常用普通商用設(shè)備而非高性能交換設(shè)備，可以大幅度降低網(wǎng)絡(luò)通信設(shè)備開銷；該結(jié)構(gòu)主要分為三個層次，即Core層、Aggregation層與Edge層，同一層次的交換機(jī)與相鄰層次的交換機(jī)進(jìn)行鏈接，便于實(shí)現(xiàn)網(wǎng)絡(luò)通信的路徑多樣化。其Aggregation層與Edge層的交換機(jī)構(gòu)成一個Pod，假設(shè)Fat-tree拓?fù)浒腜od數(shù)目為k,每個Pod連接服務(wù)器的數(shù)量為(k/2)2個，每個Pod內(nèi)Edge層交換機(jī)數(shù)目與Aggregation層交換機(jī)數(shù)目都為k/2個，Core交換機(jī)數(shù)目為(k/2)2個，若網(wǎng)絡(luò)中每個交換機(jī)的端口數(shù)目為k,則該數(shù)據(jù)中心可以容納服務(wù)器的總數(shù)為k3/4臺，足夠滿足普通數(shù)據(jù)中心的需求。

1.2 能耗模型

數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)淇梢钥醋饕粋€無向圖G(V,E'),其中V是數(shù)據(jù)中心節(jié)點(diǎn)集合，包括交換機(jī)集合Y與服務(wù)器集合Z，即V=Y∪Z，E'是連接節(jié)點(diǎn)之間的通信鏈路集合。計算能耗時，要分別考慮服務(wù)器與通信設(shè)備的能耗。

服務(wù)器的能耗依賴于服務(wù)器的CPU、內(nèi)存、磁盤與網(wǎng)絡(luò)的利用率，其中CPU是服務(wù)器中最重要的耗能部件。服務(wù)器的能耗與服務(wù)器的CPU的利用率是成比例的線性關(guān)系，即CPU的利用率越高，服務(wù)器的能耗也就越大。同時文中還得出，一個空閑的服務(wù)器消耗的功率大約是服務(wù)器最大功率的70%，由此得出服務(wù)器功率消耗的公式：

(1)

在通信鏈路的能耗方面，很多研究中網(wǎng)絡(luò)設(shè)備(交換機(jī)、路由器等)的能耗往往被忽略，其實(shí)網(wǎng)絡(luò)設(shè)備的能耗占整個數(shù)據(jù)中心能耗的10%～20%[13-14]，網(wǎng)絡(luò)設(shè)備在閑置時的能耗為最大功率的85%。文中僅考慮數(shù)據(jù)中心中網(wǎng)絡(luò)設(shè)備的能耗與網(wǎng)絡(luò)設(shè)備的數(shù)量正相關(guān)。

(2)

(3)

所以，數(shù)據(jù)中心的能耗模型E為：

(4)

其中，Ps為交換機(jī)的額定功率。

1.3 全網(wǎng)流量模型

由云計算系統(tǒng)中的“監(jiān)控模塊”可以得到當(dāng)前數(shù)據(jù)中心中虛擬機(jī)間的通信量，接著由“預(yù)測模塊”預(yù)測將來某段時間的虛擬機(jī)間通信量，由此形成數(shù)據(jù)中心的通信方陣C，如下所示：

(5)

其中，cii=0，n表示虛擬機(jī)的總數(shù)量，cij表示單位時間內(nèi)虛擬機(jī)i向虛擬機(jī)j發(fā)送的數(shù)據(jù)量。

在數(shù)據(jù)中心，服務(wù)期間的物理距離對網(wǎng)絡(luò)傳輸時延的影響是很大的，在同一臺服務(wù)器上的虛擬機(jī)間的通信時延可以忽略，因此實(shí)際測試中將不在同一臺服務(wù)器上的虛擬機(jī)間的距離由通信過程中經(jīng)過的通信設(shè)備(如交換機(jī)、路由器)的數(shù)量與擁堵狀況決定，同一臺服務(wù)器上虛擬機(jī)間的距離設(shè)置為0(如VM1與VM13)，不同服務(wù)器上的虛擬機(jī)間的距離設(shè)置為路過交換機(jī)的個數(shù)，由此構(gòu)成了虛擬機(jī)間的距離方陣Distance，如下所示：

(6)

該方陣為對稱方陣，dii=0，dij表示虛擬機(jī)i與虛擬機(jī)j之間的距離。

數(shù)據(jù)中心的通信總流量就是在單位時間內(nèi)，經(jīng)過通信鏈路的所有通信流量之和，其公式如下所示：

(7)

1.4 約束模型

文中將用所需要的CPU、內(nèi)存與帶寬來描述一個虛擬機(jī)。文中沒有考慮虛擬機(jī)對磁盤資源的需求量，因?yàn)榫W(wǎng)絡(luò)連接存儲(NAS)技術(shù)已經(jīng)廣泛運(yùn)用于服務(wù)器集群，即虛擬機(jī)可以方便地使用其他服務(wù)器的磁盤資源。設(shè)定服務(wù)器中各項資源利用率的閾值為70%，設(shè)定閾值的好處在于：首先，一定的資源剩余可以滿足部分應(yīng)用在特定時刻對資源需求量突然增大的情況；其次，通常虛擬機(jī)在運(yùn)行過程中對資源的需求量是逐步上升的，一定的資源剩余給其提供了上升空間，減少了虛擬機(jī)的遷移。為了使優(yōu)化更好地進(jìn)行，根據(jù)CPU、內(nèi)存與帶寬，給出以下約束函數(shù)：

(8)

1.5 目標(biāo)函數(shù)

文中的優(yōu)化策略就是為了求得目標(biāo)函數(shù)的最小值，目標(biāo)函數(shù)如下所示：

minFitness=min(E,Con)=r*E+(1-r)*Con,r∈[0,1]

(9)

其中，r為調(diào)節(jié)因子，以適應(yīng)優(yōu)化不同的數(shù)據(jù)中心。若重點(diǎn)考慮降低數(shù)據(jù)中心的能耗，則可以適當(dāng)增大r的值；若重點(diǎn)考慮降低全網(wǎng)通信流量，提高通信效率，則可以適當(dāng)降低r的值。

為了平衡能耗與全網(wǎng)通信流量對適應(yīng)度值的影響，使用傳統(tǒng)的容限值法來計算r值，計算方式如下：

(10)

其中，E0為在單目標(biāo)情況下能耗的最優(yōu)值；Con0為在單目標(biāo)情況下全網(wǎng)通信流量的最優(yōu)值。

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

微粒群優(yōu)化算法(particle swarm optimization，PSO)是一種基于群智能的全局優(yōu)化進(jìn)化算法，其概念簡單，并有個體數(shù)目少、計算簡單、魯棒性好等優(yōu)點(diǎn)，在求解復(fù)雜問題時具有較強(qiáng)的優(yōu)越性。然而傳統(tǒng)的PSO算法仍然有很多缺點(diǎn)，并不能很好地解決該虛擬機(jī)放置問題，原因如下：首先，傳統(tǒng)的PSO算法是用來解決連續(xù)性優(yōu)化問題，并不能解決離散優(yōu)化問題，所以必須把粒子群算法的各項參數(shù)進(jìn)行重新定義；其次,粒子群優(yōu)化算法的一個重要問題就是容易陷入局部最優(yōu)解，從而失去了全局最優(yōu)解。為了解決上述問題，必須對傳統(tǒng)的PSO算法進(jìn)行改進(jìn)。

PSO算法根據(jù)微粒對環(huán)境的適應(yīng)度值的不同，種群中的微粒不斷向解空間進(jìn)行搜索并向最優(yōu)解靠攏，最終停留在最優(yōu)解處。對于全局優(yōu)化問題P的多個可行解組成一個集合，這個集合就是一個種群(swarm)，種群中的每個元素(將所有虛擬機(jī)放置到服務(wù)器上的一種可行的解決方案)成為一個微粒(particle)，微粒的總數(shù)量就是種群的大小。種群中的每個微粒都有一個位置矢量和速度矢量，為了可以將粒子群算法用于解決該優(yōu)化問題，文中用以下方法對粒子群算法的各個參數(shù)進(jìn)行修改：

位置定義：用向量Xi=[xi1,xi2,…,xin]表示第i個粒子的位置矢量，xi1表示第i個微粒中虛擬機(jī)1放置的位置，該矢量表示將所有虛擬機(jī)放置到服務(wù)器上的一個可行解。

速度定義：用向量Vi=[vi1,vi2,…,vin]表示第i個微粒的速度矢量，該矢量決定相應(yīng)節(jié)點(diǎn)位置的調(diào)整。

同理，種群中的微粒i在搜索過程中經(jīng)歷的最優(yōu)位置叫做個體最優(yōu)解，記為Pbi=[pi1,pi2,…,pin]，種群中所有微粒經(jīng)過的全局最優(yōu)位置叫做全局最優(yōu)解，記為G=[g1,g2,…,gn]。種群就根據(jù)式11和式12不斷更新自己的位置和速度：

(11)

(12)

其中，i∈[1,m]，m為種群大小，n為虛擬機(jī)總數(shù)；k為迭代次數(shù)；c1,c2為學(xué)習(xí)因子；r1,r2為0～1間的隨機(jī)數(shù)；w為慣性權(quán)重。

學(xué)習(xí)因子c1,c2是增強(qiáng)全局搜索能力避免局部最優(yōu)解的重要指標(biāo)。在搜索前期，要求全局搜索能力很強(qiáng)，可以防止局部最優(yōu)；在搜索后期，要求局部搜索能力加強(qiáng)，加快收斂速度。c1,c2的計算方法如下：

(13)

(14)

其中，i為當(dāng)前迭代次數(shù)；N為最大迭代次數(shù)；c1max,c1min分別為c1的最大值與最小值；c2max,c2min分別為c2的最大值與最小值。

為了使粒子群優(yōu)化算法更好地解決虛擬機(jī)放置問題，文中在原始粒子群優(yōu)化算法的基礎(chǔ)上添加了突變策略：粒子群在根據(jù)式11與式12進(jìn)行迭代時，如果微粒的適應(yīng)度小于粒子群的平均適應(yīng)度，則以一定的概率M進(jìn)行突變，其表達(dá)式為：

(15)

其中，Mmax為最大突變概率；i為迭代次數(shù)；N為最大迭代次數(shù)；b為突變步長隨世代下降的曲線形狀因子；p為突變控制因子，控制轉(zhuǎn)換突變策略的時機(jī)，即在迭代前期突變概率較大，有利于擴(kuò)大粒子群的解空間，避免局部收斂，在迭代后期突變概率變小，使粒子快速收斂。

算法流程描述如下：

Step1:初始化各參數(shù)，包括學(xué)習(xí)因子c1與c2的范圍、目標(biāo)函數(shù)的調(diào)節(jié)因子r、最大迭代次數(shù)N、突變控制因子p、突變曲線形狀因子b、最大突變概率值Mmax。

Step2：計算種群中各個粒子的目標(biāo)函數(shù)值Fitness、個體最優(yōu)解Pb(實(shí)驗(yàn)首次迭代時等于初始種群)以及全局最優(yōu)解G。

Step3:按照式11和式12在約束的條件下進(jìn)行迭代，在迭代過程中，若出現(xiàn)微粒群X中的某個某臺虛擬機(jī)所在的服務(wù)器編號xij≥k+1時，即結(jié)果越界，則將該虛擬機(jī)改為原來的服務(wù)器；若發(fā)現(xiàn)不滿足約束函數(shù)，則將合適的虛擬機(jī)放置到一臺可行的服務(wù)器，并不斷更新各粒子的Fitness、Pb和G。

Step4:計算種群的平均適應(yīng)度值avg_fitness，如果Fitnessi

Step5：如果迭代次數(shù)等于N，轉(zhuǎn)至Step6，否則轉(zhuǎn)Step3。

Step6：輸出最優(yōu)的目標(biāo)函數(shù)值與最優(yōu)的虛擬機(jī)放置方案，算法結(jié)束。

3 實(shí)驗(yàn)及結(jié)果分析

采用澳大利亞墨爾本大學(xué)的網(wǎng)絡(luò)實(shí)驗(yàn)室和Gridbus項目提出的云仿真平臺CloudSim作為實(shí)驗(yàn)仿真工具。仿真時使用交換機(jī)的功率為50 W，服務(wù)器分為普通服務(wù)器(CPU：8核，memory：16 GB，bandwidth：1 000 Mbps，peak energy consumption：330 W)與高性能服務(wù)器(CPU：12核，memory：24 GB，bandwidth：2 000 Mbps，peak energy consumption：500 W),虛擬機(jī)的型號分為CPU密集型(CPU：4核，memory：4 GB，bandwidth：200 Mbps)、內(nèi)存密集型(CPU：2核，memory：8 GB，bandwidth：200 Mbps)、帶寬密集型(CPU：2核，memory：2 GB，bandwidth：500 Mbps)與普通型(CPU：2核，memory：4 GB，bandwidth：200 Mbps)。

為了達(dá)到可信的效果，必須說明以下事實(shí)，數(shù)據(jù)中心的虛擬機(jī)間的流量分布是很不均勻的，虛擬機(jī)間產(chǎn)生的流量各不相同，但是大部分虛擬機(jī)在一段時間內(nèi)產(chǎn)生的流量是相對穩(wěn)定的，大約有80%的虛擬機(jī)間的通信流量少于15 kb/s，然而僅有4%的虛擬機(jī)間的通信流量高達(dá)150 kb/s[13-15]，因此在生成通信方陣時80%的虛擬機(jī)間的通信流量為0～20 kb/s，16%的虛擬機(jī)間的通信流量為20～150 kb/s，4%的虛擬機(jī)間的通信流量為150～500 kb/s。

為了驗(yàn)證MPSO算法在虛擬機(jī)放置問題上的可行性，使用PSO、隨機(jī)算法(random algorithm)與首次適應(yīng)算法(first fit algorithm)進(jìn)行對比。

在CloudSim平臺上按照表1中的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行模擬。實(shí)驗(yàn)時，序號1、2的測試數(shù)據(jù)集的初始種群中粒子個數(shù)為50個，最大迭代次數(shù)為300代；3、4的測試數(shù)據(jù)集的初始種群為100個，最大迭代次數(shù)為500代。其他參數(shù)如下：學(xué)習(xí)因子最大值與最小值分別為3與1；慣性權(quán)重w為0.5；初始速度vij設(shè)為1，最大突變概率Mmax為0.2，突變步長隨世代下降的曲線形狀因子b取2，突變控制因子p一般取最大迭代次數(shù)的一半。為了平衡功率與總流量對適應(yīng)度函數(shù)的影響，調(diào)節(jié)因子r經(jīng)計算取0.02。PSO算法的參數(shù)與改進(jìn)粒子群算法所用的參數(shù)相同。為了減少實(shí)驗(yàn)誤差，每組實(shí)驗(yàn)做三次，取其平均值。

圖1是選取的第一組測試數(shù)據(jù)所得的測試結(jié)果，由PSO算法與MPSO算法通過多次迭代求得的適應(yīng)度值隨迭代次數(shù)變化的曲線。

表1 四種仿真數(shù)據(jù)

圖1 適應(yīng)度值與迭代次數(shù)對比

由圖1可得，未經(jīng)優(yōu)化的PSO算法前期的收斂比較快，但是迭代到90次時，下降速度逐漸減弱，最后趨于水平，說明未經(jīng)優(yōu)化的PSO算法的全局搜索能力有限，容易達(dá)到局部收斂。MPSO算法在前期有較強(qiáng)的突變概率，全局搜索能力比較強(qiáng)，故曲線下降速度較慢；但是迭代后突變概率減弱，該算法以較快的速度收斂于最優(yōu)解，在240代時已基本尋找到良好的部署方案。該實(shí)驗(yàn)說明，帶有突變的粒子群算法達(dá)到了理想的結(jié)果。

圖2～5從多個方面展示了四種優(yōu)化算法在四組實(shí)驗(yàn)數(shù)據(jù)中的優(yōu)化效果圖?？梢钥闯?，在流量優(yōu)化方面，使用MPSO算法的四組實(shí)驗(yàn)數(shù)據(jù)中的全網(wǎng)流量與主干網(wǎng)流量都優(yōu)于其他三種算法；在耗能方面，使用MPSO算法的放置策略中使用的服務(wù)器與網(wǎng)絡(luò)設(shè)備的數(shù)量都不高于其他三種算法，因此數(shù)據(jù)中心總功率的消耗也低于其他三種放置算法。

圖2 多目標(biāo)優(yōu)化的全網(wǎng)通信流量對比

圖3 多目標(biāo)優(yōu)化的主干網(wǎng)流量對比

圖4 多目標(biāo)優(yōu)化的服務(wù)器使用臺數(shù)對比

圖5 多目標(biāo)優(yōu)化的數(shù)據(jù)中心總功率對比

4 結(jié)束語

文中提出了一種改進(jìn)粒子群算法的虛擬機(jī)放置策略，以縮小全網(wǎng)的通信量，降低數(shù)據(jù)中心的能耗。首先對粒子群算法的各個參數(shù)進(jìn)行修改，使其適合解決離散優(yōu)化問題，接著給出了三維空間(CPU、內(nèi)存與帶寬)約束模型來約束服務(wù)器的資源使用情況，最后為粒子群算法添加突變策略并給出了一個突變函數(shù)，提高了粒子群的多樣性。實(shí)驗(yàn)結(jié)果表明，該虛擬機(jī)放置策略很好地解決了云環(huán)境中的虛擬機(jī)放置問題，在云環(huán)境這種大規(guī)模分布式并行計算中有很大的研究價值以及可觀的應(yīng)用前景。