王以伍 陳躍輝

(成都醫(yī)學院網(wǎng)絡(luò)中心 四川 成都 610083)

0 引 言

隨著云數(shù)據(jù)中心服務器數(shù)量與規(guī)模的迅猛增加，能耗已經(jīng)成為數(shù)據(jù)中心面臨的主要問題[1]。目前，數(shù)據(jù)中心的能耗已經(jīng)占據(jù)全世界電力供應的1.3%，至2020年將增長至8%[2]。數(shù)據(jù)中心的碳排放為全球總量的0.6%，等同于新西蘭一個國家的碳排放量，至2020年將增長至2.6%，超過德國的碳排放量?；谔摂M化的服務器合并技術(shù)是目前降低數(shù)據(jù)中心能耗的最重要手段，該技術(shù)使得同一服務器上可以運行多重應用，每種應用執(zhí)行于各自的虛擬機上，并將虛擬機映射至服務器。此時，如何在滿足服務質(zhì)量QoS的同時設(shè)計出高能效的虛擬機部署算法對數(shù)據(jù)中心的能效將具有重要影響。

為了解決以上問題，本文在數(shù)據(jù)中心環(huán)境下提出了一種能量與QoS保障的虛擬機部署算法，算法的優(yōu)勢在于：1) 與傳統(tǒng)的服務器資源同質(zhì)不同，算法考慮了異構(gòu)條件下的服務器資源，將從全局考慮QoS保障，將虛擬機部署問題形式化能耗與全局QoS保障間均衡的優(yōu)化問題；2) 通過參數(shù)與進化操作的重定義，提出了一種改進的粒子群算法對虛擬機部署進行求解，并以局部適應度優(yōu)先策略更新粒子位置，使算法可以更快收斂。

1 相關(guān)研究

已有研究中，MBFD算法[3]是云數(shù)據(jù)中心中具有代表性的虛擬機部署能量優(yōu)化算法。該算法首先按當前CPU占用對所有虛擬機進行降低排列，然后將虛擬機分配至帶來功耗增加幅度最小的服務器上，實現(xiàn)能耗優(yōu)化。此外，智能群體算法也廣泛應用于虛擬機部署問題的求解，如遺傳算法GA[4]、模擬退火算法SA[5]、粒子群算法PSO[6]等。然而，以上已有工作均是同質(zhì)的數(shù)據(jù)中心環(huán)境，其方法不適用于異構(gòu)數(shù)據(jù)中心環(huán)境。此外，以最小化能耗為目標的單目標優(yōu)化虛擬機部署也可以利用群體智能算法ACO[7]、PSO[8]、SA[1]和GA[9]等進行求解。但是，盡管此時算法得到的能耗有所降低，但在應用方面并未提供QoS保障，這使得應用負載的執(zhí)行成功率不高。

考慮QoS保障的虛擬機部署問題的相關(guān)研究中，文獻[10]提出了基于GA的多目標虛擬機部署算法，算法可以實現(xiàn)活動主機數(shù)量和通信QoS開銷的最小，均衡數(shù)據(jù)中心中多維度資源的同步利用。文獻[11]提出基于GA的虛擬機部署算法，可以最小化活動數(shù)量和最大化資源利用率。文獻[12]則利用PSO實現(xiàn)了虛擬機部署問題中能耗最小和資源浪費最小。文獻[13]利用一種文化基因算法實現(xiàn)虛擬機部署問題的多目標優(yōu)化，包括最小化能耗、網(wǎng)絡(luò)流量及最大化經(jīng)濟收益。問題在于，以上算法均只考慮了單個維度上的QoS保障，如通信開銷、資源利用率、經(jīng)濟收益等，沒有設(shè)計滿足多維度QoS且從全局角度進行QoS保障的虛擬機部署算法。

比較已有研究，本文將設(shè)計能量與QoS保障的虛擬機部署算法，算法利用改進的粒子群優(yōu)化可以在滿足全局QoS保障的同時最小化數(shù)據(jù)中心的能耗。

2 能量與QoS模型

表1給出本文有關(guān)參數(shù)說明。

表1 符號說明

2.1 能耗模型

數(shù)據(jù)中心的能耗主要集中于服務器主機上，功耗主要由CPU、內(nèi)存、磁盤和網(wǎng)絡(luò)接口組成，且CPU是其功耗的主要組成部分，也可認為，服務器的CPU利用率即為其資源利用率。CPU利用率可根據(jù)執(zhí)行負載的變化建立為時間的函數(shù)，故服務器的能耗也可基于CPU利用率進行建立。將服務器總體定義為：

(1)

式中：En為時間段[t1,t2]間服務器的總能耗，u(t)為變化的CPU利用率，P(u(t))為時間t時服務器的功耗，Pmax為服務器滿載時的最大功耗，c為服務器為空閑狀態(tài)時的能耗比例。

2.2 QoS效用函數(shù)

數(shù)據(jù)密集型服務(簡稱服務)的QoS需求包括多種屬性，如：響應時間、可靠性、吞吐量和可用性等。通常，這些屬性可劃分為兩類：積極型QoS屬性和消極型QoS屬性。積極型QoS屬性(如可靠性和可用性)表明其屬性值越大，服務器運行相關(guān)服務的性能越好。相反，消極型QoS屬性(如響應時間和延時)的屬性值越低，性能越好。本文通過將積極型QoS屬性轉(zhuǎn)換為消極型QoS屬性的方式(乘以-1)而僅考慮消極型QoS屬性。

考慮擁有r種QoS屬性的服務s的QoS需求矢量qs={q1(s),q2(s),…,qr(s)}，其中，qk(s)值(1≤k≤r)代表服務s的第k個屬性值。所有l(wèi)個服務的屬性矢量可表示為QS={q1(S),q2(S),…,qr(S)}，S={s1,s2,…,sm}，其中，qk(S)表示所有服務的第k個屬性值的累加。表2給出了服務的QoS屬性值的累加函數(shù)。

表2 QoS屬性值的累加函數(shù)

每種服務涉及多種QoS屬性，會帶來不同的量化程度，這不利于滿足全局的QoS保障。因此，需要設(shè)計一種QoS效用函數(shù)，將QoS屬性值q(s)矢量映射為單一實數(shù)值?？紤]n臺服務器組成的數(shù)據(jù)中心，PS={ps1,ps2,…,psn}，可部署的m臺虛擬機集合為VM={vm1,vm2…,vmm}。一種服務由部署于一臺主機上一臺虛擬機完成，同時需要滿足其具體資源需求(即CPU和內(nèi)存)和QoS約束。一種服務僅運行一臺虛擬機上，且服務的QoS通常與虛擬機提供相關(guān)。因此，QoS效用函數(shù)需要將所有屬性值在多維度以統(tǒng)一計算的標準化方式將其映射至域[0,1]之間，從而量化全局的QoS保障性能。

定義1QoS效用函數(shù)。假設(shè)有r個QoS屬性，運行于第j臺服務器psj(1≤j≤n)的虛擬機的第i個服務si∈S(1≤i≤l)的QoS效用函數(shù)可表示為：

(2)

那么，所有服務S的QoS效用函數(shù)為：

(3)

同時:

(4)

2.3 能量與QoS保障的虛擬機部署模型

數(shù)據(jù)中心的虛擬機部署問題的優(yōu)化目標是在滿足全局QoS保障的同時最小化能耗。通過重寫式(1)和式(2)，可以將能量與QoS保障的虛擬機部署問題形式化為多目標約束最優(yōu)化問題，即帶有全局QoS效用函數(shù)最大化問題(即全局QoS保障)的全局能耗最小化問題，定義為：

(5)

(6)

約束條件包括QoS約束和資源能力約束，即：

(7)

(8)

(9)

(10)

式中：n表示數(shù)據(jù)中心中服務器的數(shù)量，m表示部署虛擬機的數(shù)量，Ej表示服務器j的能耗，Ck表示QoS約束值，Ck≥qk(S)。

式(5)-式(6)定義的虛擬機部署最優(yōu)化問題為NP問題，該問題需要在滿足所有約束(式(7)-式(10))的前提下實現(xiàn)最小化能耗和最大化全局QoS效用值，得到最優(yōu)虛擬機部署方案。本文將提出一種基于改進粒子群算法的部署策略，在能量與全局QoS保障均衡下實現(xiàn)最優(yōu)虛擬機部署。

3 算法設(shè)計

3.1 PSO算法

粒子群算法PSO是一種基于群體智能的隨機式搜索算法。作為一種進化計算技術(shù)，比較同類方法，PSO執(zhí)行速度更快，效率更高，已經(jīng)廣泛應用于人工智能神經(jīng)網(wǎng)絡(luò)訓練、模糊系統(tǒng)控制等諸多領(lǐng)域。PSO通過迭代式提供侯選解的方式不斷改進解的質(zhì)量，使其最終收斂于最優(yōu)解。

PSO中群體的每個成員即為一個粒子，每個粒子代表搜索問題的一個可行解。每個粒子擁有兩個參數(shù)：速率和位置。粒子位置與適應度值相關(guān)，可用于評估解的質(zhì)量。PSO開始于隨機產(chǎn)生的一個粒子群，并迭代尋找問題最優(yōu)解。以Xlbest表示粒子找到歷史最優(yōu)解，Xgbest表示整個種群找到的歷史最優(yōu)解，在每一次迭代中，粒子的速度和位置通過下式進行更新：

(11)

(12)

為了求解能量與QoS保障的虛擬機部署問題，PSO需作以下改進：1) 傳統(tǒng)PSO僅適用于求解連續(xù)優(yōu)化問題，不適用于求解離散優(yōu)化問題，這表明PSO的相關(guān)參數(shù)和進化操作必須重新定義；2) 必須重新設(shè)計粒子更新策略和解碼策略，以表達虛擬機與服務器間的映射關(guān)系。

3.2 改進PSO

本文對傳統(tǒng)PSO的改進主要針對兩點：1) 重新定義了PSO的參數(shù)和進化操作，使其可以求解能量與QoS保障的虛擬機部署優(yōu)化這類離散最優(yōu)化問題；2) 采用了一種局適應度優(yōu)先策略更新粒子位置信息。

3.2.1相關(guān)定義

傳統(tǒng)PSO僅適用于求解連續(xù)最優(yōu)化問題，無法求解能量與QoS保障的虛擬機部署優(yōu)化這類離散最優(yōu)化問題。為此，需要重新定義PSO的相關(guān)參數(shù)和進化操作。

基于以上五種定義，可將式(11)-式(12)轉(zhuǎn)換為下式：

(13)

(14)

3.2.2局部適應度優(yōu)先策略

傳統(tǒng)的PSO采用隨機選擇策略，可能影響PSO的全局收斂，降低求解效率。為了增強解的質(zhì)量，本文設(shè)計一種局部適應度優(yōu)先策略更新粒子位置。

為了便于表述，將粒子的第一個維度上的每個位值稱為局部位置。在一個最優(yōu)時段[t1,t2]間運行于該服務器的所有虛擬機的CPU利用率被稱為局部能量適應度，定義為：

(15)

式中：uij(t)表示運行于服務器主機j的虛擬機i的CPU利用率，m表示運行于服務器j上的虛擬機的總數(shù)量。

運行于服務器上的所有虛擬機的QoS屬性之和稱為局部QoS適應度，定義為：

(16)

基于式(15)和式(16)，局部適度度定義為：

(17)

對于局部適應度優(yōu)先策略，當PSO需要更新一個粒子的確定局部位置時，服務器上擁有最大適應度的虛擬機將具有更高的概率被選擇去更新局部位置。局部適應度代表服務器的CPU利用率和QoS屬性之和。

3.2.3解碼策略

為了改進解的效率，基于服務器與虛擬機間一對多的映射特點，設(shè)計了一種二維解碼策略，如圖1所示，其中，n為服務器數(shù)量，m為部署于同一服務器上的虛擬機的數(shù)量。

圖1 二維解碼

由圖可知，一個粒子的第一維為n位二進制矢量，矢量中的每一個位即對應于數(shù)據(jù)中心中的一個服務器。這里，“1”代表在當前虛擬機部署方案中對應服務器是活動的，“0”代表服務器為待機狀態(tài)。一個粒子的第二維為部署于服務器上的虛擬機組成的集合。那么，每個虛擬機子集即與一個活動的服務器相關(guān)聯(lián)。例如：粒子的第一維的第一個位值為0，則表明數(shù)據(jù)中心的第一個服務器應被開啟。第一、第二個虛擬機應部署于第一個服務器上。比較傳統(tǒng)的一維粒子解碼方法，二維解碼策略不僅可以有效縮短粒子解碼長度，降低搜索時間，而且能夠反映虛擬機的靜態(tài)優(yōu)化部署特征。

4 仿真實驗

4.1 實驗配置

利用CloudSim[14]對算法進行仿真分析。模擬一個由1 000個異構(gòu)服務器組成的數(shù)據(jù)中心環(huán)境，服務器具體由兩類組成：一類是HP Proliant G4，配置CPU為3 720 MIPS，內(nèi)存為4 GB，峰值功耗為117 W；另一類是HP Proliant G5，配置CPU為5 320 MIPS，內(nèi)存為4 GB，峰值功耗為135 W。服務器具有不同的性能配置和能耗特征[3]。每個服務器運行帶有四種QoS屬性(響應時間、可用性、吞吐量和可靠性)的一個或多個數(shù)據(jù)密集型服務，服務負載產(chǎn)生現(xiàn)實的2 500個Web服務間。

為了更好地反映實際的虛擬機請求，以Amazon EC2的兩類虛擬機實例作為虛擬機請求參數(shù)，包括Micro實例，配置500 MIPS CPU和613 MB內(nèi)存，以及Small實例，配置1 000 MIPS CPU和1 700 MB內(nèi)存。

選取改進最佳適應遞減算法MBFD[3]、最佳適應算法BF[15]、能耗優(yōu)化的粒子群算法EOPSO[12]作為性能比較的基準算法。前兩種算法在裝箱思想對虛擬機部署進行建模，區(qū)別在于對于服務器的資源占用排序分為遞減和遞增排列，兩種算法在優(yōu)化服務器使用數(shù)量、降低服務器閑置能耗上擁有較好效果。EOPSO算法與本文同為粒子群優(yōu)化，但其粒子進化操作及解碼均與本文有所區(qū)別。其他參數(shù)配置如下：能量模型中參數(shù)c設(shè)置為0.6，粒子群的初始種群設(shè)置為20，粒子進化的最大迭代次數(shù)設(shè)置為30，仿真實驗運行10次，實驗結(jié)果取其平均值。

4.2 結(jié)果分析

實驗1觀察數(shù)據(jù)中心所有活動服務器的總體能耗情況，結(jié)果如圖2所示?？梢钥闯觯疚乃惴‥QPSO比較其他算法節(jié)省了更多的能耗，且在虛擬機請求數(shù)量增加時，其能耗增加的敏感度也是最弱的?？傮w上，EQPSO可以節(jié)省30%左右的能耗，原因在于BF和MBFD算法需要全局信息，即數(shù)據(jù)中心中異構(gòu)服務器的能耗信息，而僅僅考慮了多維度的資源約束，未考慮在虛擬機部署過程中不同服務器的能效的不同。PSOVMP算法雖然也利用粒子群的求解思想，但其求解速度更慢，導致很多非最優(yōu)解，能耗更大。本文算法引入了有效的粒子速率與位置更新機制，使其更易找到最優(yōu)部署方案，也更易于實現(xiàn)算法收斂，改進了解的質(zhì)量。最終，本文算法得到的活動服務器也較少，總體能耗更低。

圖2 能耗

實驗2觀察全局QoS保障性能，結(jié)果如圖3所示。由于四種QoS屬性擁有不同的單位，需要根據(jù)QoS效用函數(shù)將QoS矢量值映射為單一實數(shù)值，即進行標準化后均映射至[0,1]之間，如此，全局QoS保障的取值范圍為[0,4]。結(jié)果表明，本文算法EQPSO的全局QoS保障平均為2.74，高于其他算法。原因在于其他算法側(cè)重于局部QoS最優(yōu)化，而局部QoS優(yōu)化無法滿足所有數(shù)據(jù)密集型服務的全局QoS保障。本文算法通過更低的能耗和更高的全局QoS保障獲得了更好的性能。

圖3 全局QoS保障

實驗3觀察服務器空閑的能耗比例變化對算法性能的影響，即式(1)中的c值,結(jié)果如圖4所示。實驗中設(shè)置c=0.1，并以步長0.1遞增至0.9，同時將QoS約束的數(shù)量設(shè)置為1，QoS權(quán)重設(shè)置為0.8。可以看出：1) 當c值遞增時，能耗大幅增加，也反映出本文算法能耗越低時，c值也越小，即空閑的服務器數(shù)量越多；2) 全局QoS保障并未隨c值的變化發(fā)生劇烈波動。

圖4 服務器空閑的能耗比例對性能的影響

實驗4觀察QoS約束數(shù)量對算法性能的影響，結(jié)果如圖5所示。QoS約束數(shù)量代表數(shù)據(jù)中心中用戶對數(shù)據(jù)密集型服務的QoS需求。實驗中設(shè)置QoS約束為1，并以步長1遞增至4，c設(shè)置為0.6，w設(shè)置為0.8，其他屬性權(quán)重隨機產(chǎn)生于[0,0.2]之間。結(jié)果表明，本文算法得到的能耗與QoS保障并未隨著QoS約束數(shù)量的變化發(fā)生過大波動，總體較為平衡，說明算法具有較好的魯棒性，可適應于不同數(shù)量的QoS需求。

圖5 QoS約束數(shù)量對性能的影響

實驗5觀察QoS權(quán)重w對算法性能的影響，結(jié)果如圖6所示。實驗中設(shè)置w=0.1，并以步長0.1遞增至0.9，同時將QoS約束的數(shù)量設(shè)置為1，c設(shè)置為0.6。結(jié)果表明：1) 全局QoS保障在w從0.6遞增至0.9時也是遞增的，即全局QoS保障性能越好，w值越高；2) 算法能耗并未隨著w值的變化發(fā)生劇烈波動，穩(wěn)定性較好；3) 綜合比較，在能耗與QoS均較優(yōu)時，w處于[0.7,0.9]間。

圖6 QoS權(quán)重對性能的影響

實驗6觀察算法計算時間，結(jié)果如圖7所示。實驗中將虛擬機請求數(shù)量從1 000遞增至2 000，c設(shè)置為0.6，w設(shè)置為0.8。結(jié)果表明，當虛擬機請求數(shù)量遞增時，算法的計算時間增速較慢，計算時間與虛擬機請求數(shù)量之間幾乎為線性關(guān)系，算法具體較好的可擴展性，可適應于不同規(guī)模的虛擬機部署請求。

圖7 計算時間

5 結(jié) 語

提出了一種基于能量與多維度QoS保障的虛擬機部署算法。建立了虛擬機部署的QoS模型，設(shè)計了一種通用QoS效用函數(shù)，實現(xiàn)了不同形式QoS的標準量化，并在此基礎(chǔ)上，將虛擬機部署問題形式化為滿足全局QoS保障的同時實現(xiàn)能耗的最小化；設(shè)計了一種改進粒子群算法的虛擬機部署策略對優(yōu)化問題進行求解，該策略通過相關(guān)參數(shù)和進化操作的重新定義，以及局部適應度優(yōu)先的粒子位置更新機制，實現(xiàn)能耗與全局QoS保障的均衡優(yōu)化。實驗結(jié)果表明，算法不僅在能耗與全局QoS保障性能上是優(yōu)于同類算法的，并且在穩(wěn)定性和可擴展性方面也有較好的表現(xiàn)。