考慮低資源損耗的云平臺(tái)虛擬機(jī)放置策略

李少旭，李雷孝+，鄧 丹，林 浩，高 靜，王永生

(1.內(nèi)蒙古工業(yè)大學(xué) 數(shù)據(jù)科學(xué)與應(yīng)用學(xué)院，內(nèi)蒙古 呼和浩特 010080；2.內(nèi)蒙古自治區(qū)科學(xué)技術(shù)廳 內(nèi)蒙古自治區(qū)基于大數(shù)據(jù)的軟件服務(wù)工程技術(shù)研究中心，內(nèi)蒙古 呼和浩特 010080； 3.內(nèi)蒙古農(nóng)業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，內(nèi)蒙古 呼和浩特 010011)

0 引 言

云計(jì)算作為繼分布式計(jì)算、并行計(jì)算、網(wǎng)格計(jì)算以來新的計(jì)算模式，以其成本低廉、安全可靠、可按需分配的資源池機(jī)制的特點(diǎn)，已經(jīng)在全球范圍內(nèi)得到了快速發(fā)展[1]。隨著云數(shù)據(jù)中心的規(guī)模不斷擴(kuò)大，資源損耗嚴(yán)重與低利用率的問題日益突出[2-4]。虛擬機(jī)遷移機(jī)制是云平臺(tái)提高資源利用率、降低能耗的重要手段。虛擬機(jī)放置是虛擬機(jī)遷移的一個(gè)重要環(huán)節(jié)，虛擬機(jī)放置位置的優(yōu)劣影響著數(shù)據(jù)中心的資源分配狀況[5]。如果數(shù)據(jù)中心資源損耗嚴(yán)重，必然需要開啟更多的物理機(jī)來放置虛擬機(jī)。這將會(huì)造成資源浪費(fèi)、增加運(yùn)營成本[6]。

本文以最小化資源損耗為優(yōu)化目標(biāo)，以物理機(jī)上可用的CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和磁盤資源作為約束條件構(gòu)建了虛擬機(jī)放置模型。在模擬放置階段將虛擬機(jī)放置問題轉(zhuǎn)化為多維裝箱問題，結(jié)合粒子群算法(particle swarm optimization，PSO)解決最優(yōu)化問題的思想方法，提出一種基于正余弦擾動(dòng)和反向?qū)W習(xí)的自適應(yīng)粒子群算法(based on sine and cosine perturbation and reverse learning adaptive particle swarm optimization，SCRLPSO)的虛擬機(jī)放置策略。首先對(duì)數(shù)據(jù)中心資源結(jié)構(gòu)進(jìn)行分析，建立最小化資源損耗目標(biāo)的虛擬機(jī)放置模型；然后對(duì)物理機(jī)和虛擬機(jī)的映射關(guān)系進(jìn)行編碼，使用反向?qū)W習(xí)策略進(jìn)行種群初始化。在種群尋優(yōu)的過程中，通過正余弦擾動(dòng)避免種群陷入局部最優(yōu)解，使用開口向下的權(quán)重更新策略增強(qiáng)種群的全局搜索能力。實(shí)驗(yàn)結(jié)果表明，和標(biāo)準(zhǔn)的粒子群算法、傳統(tǒng)的首次適應(yīng)法、最佳適應(yīng)法相比，基于SCRLPSO算法的虛擬機(jī)放置策略更能降低數(shù)據(jù)中心的資源損耗程度。

1 相關(guān)工作

解決虛擬機(jī)放置問題的傳統(tǒng)方案是基于貪婪思想的啟發(fā)式算法，如首次適應(yīng)法(first fit，F(xiàn)F)[7]、最佳適應(yīng)法(best fit，BF)[8]等，目的是盡可能減少數(shù)據(jù)中心處于活動(dòng)狀態(tài)的物理機(jī)的數(shù)量來減少能耗，提高資源利用率。但是這種基于貪婪思想的虛擬機(jī)放置策略在異構(gòu)集群中可能會(huì)導(dǎo)致某些物理機(jī)負(fù)載過高，這會(huì)導(dǎo)致運(yùn)行在其上的虛擬機(jī)服務(wù)質(zhì)量的降低。而有些物理機(jī)可能會(huì)處于低載狀態(tài)，物理機(jī)資源沒有得到充分利用。因此這種基于貪婪思想的虛擬機(jī)放置策略可能會(huì)導(dǎo)致負(fù)載失衡。

近年來，一些基于機(jī)器學(xué)習(xí)的方法被用于求解虛擬機(jī)放置問題。盧海峰等[9]提出了一種強(qiáng)化學(xué)習(xí)下的虛擬機(jī)放置策略，該策略以能耗為優(yōu)化目標(biāo)，從狀態(tài)聚合和時(shí)間信度兩個(gè)方面對(duì)Q-Learning(λ)算法進(jìn)行優(yōu)化，可以有效降低數(shù)據(jù)中心的能耗。郭曙杰等[10]提出一種基于模糊隸屬度的虛擬機(jī)放置策略，借助模糊聚類的思想，計(jì)算虛擬機(jī)與物理機(jī)的隸屬度矩陣，在矩陣中局部搜索得到最優(yōu)的放置方案。

元啟發(fā)式算法也廣泛應(yīng)用于虛擬機(jī)放置問題。何利文等[11]提出了一種基于權(quán)值適應(yīng)度粒子群優(yōu)化算法，以通訊時(shí)延、服務(wù)器負(fù)載以及CPU的處理時(shí)延作為虛擬機(jī)放置的依據(jù)，對(duì)PSO算法的權(quán)重因子ω重新編寫，能更好地降低應(yīng)用的執(zhí)行時(shí)間。Gharehpasha等[12]提出一種混合正弦余弦算法和樽海鞘群算法的虛擬機(jī)放置策略，該策略通過最小化活動(dòng)物理機(jī)的數(shù)量來降低能耗。Ragmani等[13]提出一種用于虛擬機(jī)調(diào)度的混合模糊蟻群優(yōu)化算法，以響應(yīng)時(shí)間、處理時(shí)間和負(fù)載均衡為優(yōu)化目標(biāo)，根據(jù)歷史信息計(jì)算信息素值，為虛擬機(jī)選擇合適的物理機(jī)。

傳統(tǒng)的PSO算法存在容易陷入局部最優(yōu)解、收斂速度慢等缺點(diǎn)。目前國內(nèi)外很多專家學(xué)者在改進(jìn)PSO算法上做了相關(guān)的研究工作。寧維迪[14]針對(duì)粒子群算法容易陷入局部最優(yōu)解的不足，將正弦余弦算法應(yīng)用于粒子群算法的學(xué)習(xí)率更新，使粒子群算法具有較好的全局搜索能力。張繼榮等[15]將正弦余弦策略應(yīng)用于粒子群算法權(quán)重更新中，使算法在運(yùn)行初期具有良好的全局搜索能力，后期快速逼近全局最優(yōu)解。張志宇[16]對(duì)粒子群算法提出改進(jìn)，使用三角函數(shù)來調(diào)整粒子群算法的權(quán)重，使用指數(shù)變化的學(xué)習(xí)因子來調(diào)整粒子向自身學(xué)習(xí)和向種群學(xué)習(xí)的能力，在算法運(yùn)行前期快速搜索到局部最優(yōu)解，在后期加強(qiáng)全局搜索能力，向全局最優(yōu)解靠近。

上述對(duì)虛擬機(jī)放置問題的研究缺乏對(duì)資源損耗和服務(wù)等級(jí)(service level agreement，SLA)的權(quán)衡，同時(shí)考慮上述對(duì)PSO算法改進(jìn)策略，本文提出一種基于正余弦擾動(dòng)和反向?qū)W習(xí)的自適應(yīng)粒子群算法的虛擬機(jī)放置策略。在盡可能降低云平臺(tái)資源損耗的同時(shí)，保障用戶的服務(wù)質(zhì)量。

2 虛擬機(jī)放置的約束優(yōu)化目標(biāo)模型

2.1 數(shù)據(jù)中心模型描述

數(shù)據(jù)中心是支撐云服務(wù)的基礎(chǔ)環(huán)境，其通過對(duì)大量閑置的計(jì)算機(jī)系統(tǒng)資源進(jìn)行虛擬化，構(gòu)成一個(gè)可以按需分配、動(dòng)態(tài)擴(kuò)展的虛擬資源池。虛擬機(jī)是數(shù)據(jù)中心對(duì)用戶進(jìn)行資源分配的基本單位。虛擬機(jī)放置問題[17]，是指按照一定的放置策略，在滿足資源約束的情況下，為虛擬機(jī)選擇一個(gè)合適的物理宿主機(jī)，從而達(dá)到減少資源損耗、節(jié)約運(yùn)營成本、提高運(yùn)行效率等目的。

圖1描述了用戶向數(shù)據(jù)中心提出資源請(qǐng)求，數(shù)據(jù)中心將資源請(qǐng)求分配到物理機(jī)上的工作場(chǎng)景。s個(gè)用戶向數(shù)據(jù)中心請(qǐng)求創(chuàng)建n臺(tái)異構(gòu)的虛擬機(jī) {vmi,i=1,2,…,n}， 數(shù)據(jù)中心現(xiàn)有m臺(tái)物理機(jī) {pmj,j=1,2,…,m}， 要將這些虛擬機(jī)合理地放置在m臺(tái)物理機(jī)上。一臺(tái)物理機(jī)能夠放置多臺(tái)虛擬機(jī)，而一臺(tái)虛擬機(jī)只能被放置在一臺(tái)物理機(jī)上。

數(shù)據(jù)中心提供的物理資源主要包括CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、磁盤。物理機(jī)pmj能形式化描述成式(1)

pmj={idj,cpuj,memj,bwj,diskj,alivej}

(1)

在式(1)中，idj表示第j臺(tái)物理機(jī)在數(shù)據(jù)中心的唯一標(biāo)識(shí)，cpuj表示第j臺(tái)物理機(jī)的CPU核心數(shù)，memj表示第j臺(tái)物理機(jī)的內(nèi)存大小，bwj表示第j臺(tái)物理機(jī)的帶寬大小，diskj表示第j臺(tái)物理機(jī)的磁盤大小，alivej∈{0, 1} 表示第j臺(tái)物理機(jī)是否處于活躍狀態(tài)。

數(shù)據(jù)中心的虛擬機(jī)vmi的資源需求描述可以形式化描述成式(2)

vmi={idi,cpui,memi,bwi,diski}

(2)

其中，idi表示第i臺(tái)虛擬機(jī)在數(shù)據(jù)中心的編號(hào)，cpui表示第i臺(tái)虛擬機(jī)的CPU核心數(shù)，memi表示第i臺(tái)虛擬機(jī)的內(nèi)存大小，bwi表示第i臺(tái)虛擬機(jī)的帶寬大小，diski表示第i臺(tái)虛擬機(jī)的磁盤大小。

2.2 資源損耗模型

由于同一臺(tái)物理機(jī)上往往運(yùn)行著數(shù)臺(tái)異構(gòu)的虛擬機(jī)，不同規(guī)格的虛擬機(jī)對(duì)計(jì)算機(jī)資源的占用率不同，這有可能會(huì)導(dǎo)致物理機(jī)某一維度的資源利用率過高，而其它維度的資源未能充分利用，造成計(jì)算資源的極大損耗。不合理的虛擬機(jī)放置位置，會(huì)導(dǎo)致數(shù)據(jù)中心的負(fù)載失衡。

圖2為在僅考慮CPU、內(nèi)存資源時(shí)數(shù)據(jù)中心的資源損耗案例。某一臺(tái)物理機(jī)上先放置了3臺(tái)異構(gòu)的虛擬機(jī)，剩余可用資源為20%的CPU和30%的內(nèi)存。若此時(shí)用戶請(qǐng)求一臺(tái)資源需求為30%的CPU和30%的內(nèi)存的虛擬機(jī)，數(shù)據(jù)中心將由于這臺(tái)物理機(jī)的CPU資源不足，開啟一臺(tái)新的物理機(jī)來處理該虛擬機(jī)創(chuàng)建請(qǐng)求，造成更大的資源浪費(fèi)和系統(tǒng)能耗。

在考慮數(shù)據(jù)中心資源損耗時(shí)，物理機(jī)具有的資源維度和虛擬機(jī)請(qǐng)求的資源維度是相同的。假設(shè)物理機(jī)pmj上運(yùn)行著k臺(tái)虛擬機(jī)，R={cpu，mem，bw，disk} 為物理機(jī)的資源集合，r∈R，rj表示物理機(jī)pmj的r類資源配置量，ri表示部署在物理機(jī)pmj上的虛擬機(jī)vmi(i=1,2,…,k) 的r類資源配置量。物理機(jī)pmj的r類資源利用率可以表示為式(3)

(3)

將數(shù)據(jù)中心中各類資源的利用率的均值作為數(shù)據(jù)中心的平均資源利用率。用Uavg表示數(shù)據(jù)中心總的平均資源利用率，其計(jì)算方式如式(4)所示

(4)

使用標(biāo)準(zhǔn)差來衡量數(shù)據(jù)中心資源分配的偏離程度Lose，Lose的計(jì)算過程能形式化描述為式(5)

(5)

將Lose作為數(shù)據(jù)中心資源損耗優(yōu)化目標(biāo)函數(shù)，Lose值越小表示數(shù)據(jù)中心負(fù)載越均衡，即資源損耗越少。

2.3 虛擬機(jī)放置的約束優(yōu)化模型

假設(shè)物理機(jī)pmj上放置著k臺(tái)虛擬機(jī)，θ為物理機(jī)在保障用戶服務(wù)質(zhì)量情況下所能提供最大資源的比例。由此得到一個(gè)虛擬機(jī)放置約束優(yōu)化模型，可形式化描述為式(6)

(6)

其中，式(6)中的第一個(gè)約束條件表示部署在一臺(tái)物理機(jī)上所有虛擬機(jī)請(qǐng)求的資源總和不能超過物理機(jī)在保證服務(wù)質(zhì)量情況下所能提供的資源。式(6)中的第二個(gè)約束條件表示數(shù)據(jù)中心中所有虛擬機(jī)請(qǐng)求的資源總和不能超過數(shù)據(jù)中心在保證服務(wù)質(zhì)量情況下所能提供的資源。

3 SCRLPSO算法

在標(biāo)準(zhǔn)PSO算法[18]中，每個(gè)粒子代表一個(gè)解空間的解。種群中的每個(gè)粒子通過速度-位置計(jì)算模型進(jìn)行種群迭代，每次迭代根據(jù)自己的當(dāng)前位置、速度、全局最優(yōu)解和個(gè)體歷史最優(yōu)解來更新自己的位置和速度[19,20]。

虛擬機(jī)放置問題是一個(gè)典型的離散型問題。傳統(tǒng)的PSO算法在解決離散型問題時(shí)，存在編碼解碼復(fù)雜、容易陷入局部最優(yōu)解、收斂速度慢和不能動(dòng)態(tài)調(diào)整全局搜索和局部搜索的關(guān)系等問題。為此，在傳統(tǒng)的PSO算法的基礎(chǔ)上，使用連續(xù)整數(shù)編碼方式替換傳統(tǒng)的二進(jìn)制編碼方式，結(jié)合反向?qū)W習(xí)策略來提高種群的收斂速度，采用開口向下的拋物線的權(quán)重更新策略在運(yùn)行中動(dòng)態(tài)調(diào)整搜索權(quán)重，通過正余弦擾動(dòng)來避免陷入局部最優(yōu)解，提出了一種SCRLPSO算法。

設(shè)種群規(guī)模為N，維度為D，最大迭代次數(shù)為T，第i個(gè)粒子的位置為xi=(xi1,xi2,…,xiD)， (i=1,2,…,N)， 速度為vi=(vi1,vi2,…,viD)， 第i個(gè)粒子迄今為止搜索到的最優(yōu)位置為pi=(pi1,pi2,…,piD)， 種群今為止搜索到的最優(yōu)位置為g=(g1,g2,…,gD)。 標(biāo)準(zhǔn)粒子群算法利用式(7)、式(8)來更新粒子速度和位置

vij(t+1)=ω·vij(t)+c1r1(t)[pij(t)-xij(t)]+c2r2(t)[gj(t)-xij(t)]

(7)

xij(t+1)=xij(t)+vij(t+1)

(8)

其中，t表示當(dāng)前迭代次數(shù)，xij(t) 表示t時(shí)刻粒子i的第j維的位置，vij(t) 表示t時(shí)刻粒子i的第j維的速度，ω為保持原有速度的權(quán)重，c1和c2稱為學(xué)習(xí)因子，r1和r2為[0,1]之間的均勻隨機(jī)數(shù)。

3.1 編 碼

標(biāo)準(zhǔn)PSO算法適合于連續(xù)型問題的尋優(yōu)，針對(duì)離散型問題需要對(duì)問題進(jìn)行編碼。常用的二進(jìn)制編碼方式在對(duì)虛擬機(jī)放置問題進(jìn)行編碼時(shí)，一個(gè)n×m的01矩陣代表一個(gè)解，第i行代表第i臺(tái)虛擬機(jī)的放置位置。由于虛擬機(jī)的不可分割性，每臺(tái)虛擬機(jī)僅能放置在一臺(tái)物理機(jī)上，故每一行僅能有一個(gè)數(shù)字為1。如圖3所示，圖3左側(cè)是一個(gè)4×3 的01矩陣，描述的是將4臺(tái)虛擬機(jī)放置到3臺(tái)物理機(jī)上的一個(gè)放置方案的編碼。圖3右側(cè)表示每一臺(tái)虛擬機(jī)放置的實(shí)際物理機(jī)序號(hào)。計(jì)算編碼所對(duì)應(yīng)的n個(gè)虛擬機(jī)放置位置，需要一個(gè)解碼的時(shí)間。此外，使用二進(jìn)制編碼在位置更新時(shí)，要求考慮每個(gè)虛擬機(jī)僅能放置在一臺(tái)物理機(jī)上的約束。必須在位置-速度計(jì)算模型添加額外的模塊來保證約束的實(shí)現(xiàn)，造成不必要的計(jì)算資源浪費(fèi)。

針對(duì)上述二進(jìn)制編碼的不足，本文采用一種連續(xù)整數(shù)編碼方式。根據(jù)虛擬機(jī)和物理主機(jī)的映射關(guān)系，以虛擬機(jī)為單位，每個(gè)虛擬機(jī)僅能放置到一個(gè)物理主機(jī)，使用一個(gè)m維向量表示解的編碼，向量中的每個(gè)屬性為物理機(jī)編號(hào)，如x={x1,x2,…,xn}，xi∈{1,2,…,m}，i∈{1,2,…,n}。 向量xi的維度為n，每個(gè)維度的取值為[1,m]之間的整數(shù)。例如，xi=q, 表示第i臺(tái)虛擬機(jī)放置在第q臺(tái)物理機(jī)。采用連續(xù)整數(shù)編碼的方式，可以很好地適用于位置-速度計(jì)算模型。并且編碼即位置，編碼和位置保持高度的一致性，節(jié)省了編碼解碼的時(shí)間，提高算法的運(yùn)行效率和求解精度。

3.2 種群初始化策略

種群收斂速度在一定程度上受個(gè)體距離最優(yōu)解的距離的影響。如果種群中每個(gè)個(gè)體都距離最優(yōu)解較近，那一定程度上能提高種群收斂速度?？紤]每個(gè)個(gè)體和它的反向個(gè)體，有更高的幾率接近最優(yōu)解[21]。在初始化種群時(shí)，生成種群的反向種群。將種群中個(gè)體和它的反向個(gè)體進(jìn)行比較，選擇Lose更小的個(gè)體作為種群的初始個(gè)體，構(gòu)成初始種群。

對(duì)于反向解，它的值為解的位置的每一位的反向取值。對(duì)于種群中第i個(gè)個(gè)體xi=(xi1,xi2,…,xiD)， 它的反向解定義為

xi-=(m+1-xi1,m+1-xi2,…,m+1-xiD)

(9)

SCRLPSO算法將初始種群作為反向?qū)W習(xí)個(gè)體，增加了初始解的多樣性，使初始種群更加接近最優(yōu)解。使用式(9)來生成xi的反向解xi-，若Lose(xi)

3.3 自適應(yīng)權(quán)重

PSO算法在尋優(yōu)的過程中，可以分為局部挖掘和全局搜索兩類，也稱為開發(fā)和探索。這兩個(gè)部分相互促進(jìn)又相互矛盾，全局搜索用于快速定位最優(yōu)解的范圍，而局部挖掘用于尋找最優(yōu)解。全局搜索過多的時(shí)候，收斂速度會(huì)變慢，求解精度降低；局部挖掘過多的時(shí)候，就容易陷入局部最優(yōu)解。在種群迭代的過程中必須權(quán)衡二者的關(guān)系。PSO算法使用權(quán)重系數(shù)ω來處理開發(fā)和探索的關(guān)系，常用的慣性權(quán)重策略有線性遞減權(quán)值策略和指數(shù)曲線、開口向下拋物線、開口向上拋物線等非線性權(quán)重策略。

標(biāo)準(zhǔn)PSO算法使用線性遞減權(quán)值策略，ω隨著迭代次數(shù)線性遞減。當(dāng)大量的虛擬機(jī)部署在云平臺(tái)上時(shí)，采用線性遞減權(quán)值策略使算法全局搜索能力強(qiáng)，但后期收斂速度慢，求解精度低。所以本文采用自適應(yīng)權(quán)重開口向下曲線來動(dòng)態(tài)調(diào)節(jié)開發(fā)和探索的能力，如式(10)所示。保證算法在前中期保持較強(qiáng)的全局搜索能力，后期權(quán)重快速下降，具有較強(qiáng)的局部搜索能力。ωmax、ωmin為最大權(quán)重和最小權(quán)重

(10)

3.4 位置更新模型

傳統(tǒng)的粒子群優(yōu)化算法具有較好的全局搜索能力，但是后期局部搜索能力不足，求解精度低。針對(duì)粒子群優(yōu)化算法局部搜索時(shí)的隨機(jī)性，本文以概率rc采用正余弦擾動(dòng)對(duì)粒子進(jìn)行位置更新。采取當(dāng)前可能不好的解，有利于跳出局部最優(yōu)解，增強(qiáng)算法的全局尋優(yōu)能力。正弦余弦算法是一種新型元啟發(fā)式算法[22]，通過非線性方式調(diào)整參數(shù)來提高算法的搜索能力。本文結(jié)合正余弦策略，使用式(11)～式(14)來更新粒子速度和位置。

r為在[0,1]之間均勻隨機(jī)取值，若r>rc

vi(t+1)=ω(t)·vi(t)+c1r1[pi(t)-xi(t)]+c2r2[g(t)-xi(t)]

(11)

(12)

否則

vi(t+1)=vi(t)

(13)

(14)

其中，rc為擾動(dòng)概率，若r>rc，使用PSO算法的位置-速度計(jì)算模型來更新粒子的速度和位置，否則使用正余弦擾動(dòng)來更新粒子。在式(12)～式(14)中，將位置的浮點(diǎn)型數(shù)值轉(zhuǎn)化為整型，并約束在[1,m]之間，表示物理機(jī)的序號(hào)。t表示當(dāng)前迭代次數(shù)，xi(t)表示t時(shí)刻粒子i的位置，vi(t)表示t時(shí)刻粒子i的速度，ω(t)為t時(shí)刻保持原有速度的權(quán)重因子，c1為個(gè)體向自身學(xué)習(xí)能力因子，c2為個(gè)體向種群學(xué)習(xí)能力因子，r1和r2為[0,1]之間的均勻隨機(jī)數(shù)，ω(t)為粒子第t代的慣性因子，r3取值為[0,2π]均勻分布的隨機(jī)數(shù)，r4為[0,2]之間均勻分布的隨機(jī)數(shù)，控制和當(dāng)前全局最優(yōu)解之間的距離，r5為取值為[0,1]的隨機(jī)數(shù)，控制正弦和余弦的轉(zhuǎn)換概率。

最終設(shè)計(jì)出SCRLPSO算法如算法1所示。

算法1：基于正余弦擾動(dòng)和反向?qū)W習(xí)的自適應(yīng)粒子群優(yōu)化算法

輸入?yún)?shù)：pms：數(shù)據(jù)中心物理機(jī)資源列表

vms：數(shù)據(jù)中心虛擬機(jī)請(qǐng)求列表

xbound：粒子位置范圍

vbound：粒子速度范圍

ωbound：權(quán)重范圍

T：終止進(jìn)化的代數(shù)

M：種群規(guī)模

輸出參數(shù)：g：最優(yōu)方案

(1)t←1；

(2)ProcedureSCRLPSO(pms,vms,xbound,vbound,ωbound,T)

(3)foriinM

(4)X(t)[i]←Code(pms,vms,xbound,vbound);

(5)endfor

(6)forxinX(t)do

(7)x-←reverse_learning(x);

(8)ifLose(x-)

(9)x←x-;

(10)endif

(11)endfor

(12)while(t<=T)do

(13)weight=getweight(t);

(14)fori=1toMdo

(15)X(t)[i]←updatexv(wright,t,X(t)[i]);

(16)endfor

(17)X(t+1)←X(t);

(18)t←t+1;

(19)g←updateglobalbest();

(20)fori=1toMdo

(21)p[i]←updatehistorybest(wright,t,p[i]);

(22)endfor

(23)endwhile

(24)endProcedure

其中，X(t) 表示t時(shí)刻種群的所有個(gè)體，包含個(gè)體的位置和速度，第(3)行～第(10)行表示種群初始化操作，第(13)行更新當(dāng)前代數(shù)種群的權(quán)重，第(14)行～第(16)行更新種群中個(gè)體的位置和速度，第(19)行～第(22)行更新種群全局最優(yōu)解和個(gè)體歷史最優(yōu)解。

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本文采用Python語言對(duì)算法進(jìn)行了實(shí)現(xiàn)，通過和標(biāo)準(zhǔn)PSO算法、最佳適應(yīng)法、首次適應(yīng)法進(jìn)行對(duì)比分析來驗(yàn)證SCRLPSO算法在虛擬機(jī)放置問題上降低資源損耗的有效性。實(shí)驗(yàn)?zāi)M了50臺(tái)同構(gòu)的物理機(jī)組成云平臺(tái)，物理機(jī)的配置為36核CPU、95 GB內(nèi)存、10 000 MB帶寬和10 TB磁盤。

實(shí)驗(yàn)中，最佳適應(yīng)算法依次選擇所有處于活躍狀態(tài)的物理機(jī)中能滿足虛擬機(jī)需求的,且剩余資源最小的物理機(jī)來進(jìn)行放置。以內(nèi)存利用率為指標(biāo)對(duì)物理機(jī)升序排序，依次判斷物理機(jī)是否滿足虛擬機(jī)要求，直到某個(gè)物理機(jī)能夠放置虛擬機(jī)，此時(shí)選擇的物理機(jī)就是最優(yōu)選擇。若檢查到最后一臺(tái)物理機(jī)仍不能放置，則要求喚醒新的物理機(jī)進(jìn)行放置。

首次適應(yīng)算法根據(jù)物理機(jī)序號(hào)依次判斷能否放置虛擬機(jī)，若能放置則將虛擬機(jī)放置在這臺(tái)物理機(jī)上，否則判斷下一個(gè)物理機(jī)。直到檢查完所有物理機(jī)，若仍不能放置，則要求喚醒新的物理機(jī)進(jìn)行放置。

根據(jù)OpenStack的flavor套餐提供的虛擬機(jī)參數(shù)規(guī)格，同時(shí)對(duì)虛擬機(jī)進(jìn)行帶寬限制，虛擬機(jī)具體的參數(shù)規(guī)格見表1。

表1 虛擬機(jī)規(guī)格

SCRLPSO算法主要的參數(shù)見表2。 [xmin,xmax] 為粒子位置范圍， [vmin,vmax] 為粒子速度范圍，用來約束粒子，以免越界或速度過快錯(cuò)過最優(yōu)解。rc正余弦策略的擾動(dòng)概率，用來切換位置更新公式，θ為保障服務(wù)質(zhì)量的情況下所能提供的最大資源利用率。

表2 SCRLPSO算法參數(shù)

(1)資源損耗分析

本文以資源損耗為評(píng)價(jià)指標(biāo)，在相同數(shù)量和規(guī)模的虛擬機(jī)請(qǐng)求下，比較各個(gè)放置策略的資源損耗度，根據(jù)式(5)得到每種策略的最優(yōu)放置方案的資源損耗度。由于資源利用率取值區(qū)間為[0,1]，計(jì)算Lose時(shí)得到的數(shù)據(jù)偏小，所以對(duì)資源利用率做去掉百分號(hào)處理，每種策略執(zhí)行20次取其均值作為結(jié)果。

圖4描述的是SCRLPSO算法、PSO算法、BF算法、FF算法在4組虛擬機(jī)請(qǐng)求的資源損耗情況。從圖中可以看出，在相同的虛擬機(jī)請(qǐng)求數(shù)量下，SCRLPSO算法的資源損耗度相較于BF算法、FF算法、PSO算法更小。實(shí)驗(yàn)結(jié)果表明，數(shù)據(jù)中心資源損耗并不隨著虛擬機(jī)數(shù)量而線性變化，而是針對(duì)云平臺(tái)資源分布情況。如果當(dāng)前的數(shù)據(jù)中心資源不足以放置所有的虛擬機(jī)，則數(shù)據(jù)中心需要開啟新的物理機(jī)來承載虛擬機(jī)的資源請(qǐng)求。經(jīng)過本文的優(yōu)化策略后，虛擬機(jī)被均勻分配到各個(gè)物理機(jī)上，使得數(shù)據(jù)中心資源分配相對(duì)均勻，減少了資源損耗。

(2)SLA違背率分析

服務(wù)質(zhì)量是評(píng)價(jià)云服務(wù)的重要指標(biāo)之一，通常SLA和物理機(jī)的資源利用率相關(guān)。當(dāng)物理機(jī)的資源利用率提高時(shí)，服務(wù)質(zhì)量快速下降。本文將數(shù)據(jù)中心的SLA違背率定義為

fSLA=ln(2+Uavg-θ)

(15)

圖5描述的是SCRLPSO算法、PSO算法、FF算法、BF算法隨著虛擬機(jī)請(qǐng)求數(shù)量的增加，數(shù)據(jù)中心的服務(wù)質(zhì)量的變化情況。SCRLPSO算法相對(duì)于傳統(tǒng)的FF算法，SLA違背率平均降低了7%，比BF算法的SLA違背率降低了6%，比標(biāo)準(zhǔn)PSO算法的SLA違背率降低了1%。故SCRLPSO算法更能保證用戶的服務(wù)質(zhì)量。傳統(tǒng)的BF算法、FF算法等基于貪婪策略的啟發(fā)式算法，主要目標(biāo)是盡可能減少處于活躍狀態(tài)的物理機(jī)的數(shù)量來提高資源利用率，與盡可能提高服務(wù)質(zhì)量的目標(biāo)沖突，很可能會(huì)導(dǎo)致服務(wù)質(zhì)量的下降。本文提出的虛擬機(jī)放置策略，能在盡可能減少資源損耗的同時(shí)，保障用戶的服務(wù)質(zhì)量。

(3)收斂速度對(duì)比

圖6描述的是SCRLPSO算法和PSO算法在不同虛擬機(jī)請(qǐng)求下的平均收斂速度。SCRLPSO算法的收斂速度比PSO算法提高了50%。這是因?yàn)镾CRLPSO算法融合了反向?qū)W習(xí)策略，使得初始解更接近最優(yōu)解。在權(quán)重更新策略上采用開口向下拋物線，同時(shí)使用正弦余弦算法來擾動(dòng)粒子更新過程，增強(qiáng)種群的全局搜索能力，提高搜索精度。故SCRLPSO算法相較于標(biāo)準(zhǔn)PSO算法具有更快的收斂速度。

5 結(jié)束語

本文提出了基于SCRLPSO算法的虛擬機(jī)放置策略。該策略考慮CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和磁盤4種計(jì)算機(jī)系統(tǒng)資源，針對(duì)云平臺(tái)中普遍存在的資源損耗進(jìn)行分析，提出了最小化資源損耗的優(yōu)化目標(biāo)函數(shù)模型，在標(biāo)準(zhǔn)的粒子群算法的基礎(chǔ)上對(duì)編碼和權(quán)重進(jìn)行改進(jìn)，使其更適合于求解虛擬機(jī)放置問題?；旌险矣嘞宜惴?，能夠有效地避免陷入局部最優(yōu)解，提升求解精度。同時(shí)結(jié)合基于反向?qū)W習(xí)的種群初始化策略，能夠加快種群收斂速度。仿真實(shí)驗(yàn)的結(jié)果表明，在數(shù)據(jù)中心資源配置和虛擬機(jī)請(qǐng)求一定的情況下，本文方法相對(duì)于標(biāo)準(zhǔn)粒子群算法、最佳適應(yīng)法、首次適應(yīng)法更能減少數(shù)據(jù)中心資源損耗，進(jìn)而降低能耗，減少數(shù)據(jù)中心運(yùn)營成本。下一步將對(duì)虛擬機(jī)調(diào)度問題進(jìn)行多目標(biāo)優(yōu)化，進(jìn)一步提高云平臺(tái)的綜合性能。