基于粒子群優(yōu)化的云計(jì)算低能耗資源調(diào)度算法

賈嘉, 慕德俊

(西北工業(yè)大學(xué) 自動(dòng)化學(xué)院, 陜西 西安 710072)

隨著對云計(jì)算需求的不斷擴(kuò)大，幾大云計(jì)算服務(wù)提供商，如Amazon等，建立了越來越多的數(shù)據(jù)中心，以滿足云計(jì)算對基礎(chǔ)設(shè)施資源的需要。為了維護(hù)大規(guī)模的數(shù)據(jù)中心運(yùn)行，需要大量能耗。這不僅提高了服務(wù)成本，也給相應(yīng)基礎(chǔ)設(shè)施帶來巨大壓力。有研究表明，數(shù)據(jù)中心的使用率一般在5%～20%[1-2]；而空閑服務(wù)器的電量消耗也超過滿負(fù)荷情況下的50%。能耗是云計(jì)算成本中重要一環(huán)。針對云環(huán)境中數(shù)據(jù)中心的能耗問題，本文研究了面向低能耗的基于粒子群優(yōu)化算法的數(shù)據(jù)中心資源分配算法。采用帕累托最優(yōu)解集合描述所有可行的最優(yōu)解。為了得到帕累托最優(yōu)解集合，采用粒子群優(yōu)化算法，對不同的分配方案迭代尋優(yōu)，并按存活周期隨機(jī)變異分配方案。通過比較不同分配方案下能耗，得到最優(yōu)的資源分配方案。

1 云計(jì)算與粒子群優(yōu)化

1.1 云計(jì)算概述

云計(jì)算作為一種新興的并行計(jì)算技術(shù)，是分布式處理、并行處理、網(wǎng)格計(jì)算的發(fā)展和延伸。它提供了更可靠、更安全的存儲(chǔ)和計(jì)算數(shù)據(jù)能力、簡化計(jì)算交付、降低成本、具有更高的擴(kuò)展性和靈活性。云計(jì)算采用計(jì)時(shí)付費(fèi)的形式，程序員只需關(guān)注應(yīng)用程序本身，關(guān)于集群的處理問題，則交由平臺(tái)處理。云計(jì)算重要特點(diǎn)之一是虛擬化。虛擬化技術(shù)范疇從簡單的硬件抽象逐漸發(fā)展成為虛擬云操作系統(tǒng)，云主機(jī)能夠大量根據(jù)用戶定義的服務(wù)質(zhì)量(quality of service,QoS)規(guī)范執(zhí)行應(yīng)用程序的VMs并行分享。

1.2 粒子群優(yōu)化

粒子群優(yōu)化(particle swarm optimization,PSO)算法[3]是一種模擬鳥群覓食行為的演化計(jì)算算法。因其結(jié)構(gòu)簡單、參數(shù)少、易實(shí)現(xiàn)，所以受到廣泛重視并被應(yīng)用到了許多自然科學(xué)和工程科學(xué)領(lǐng)域。標(biāo)準(zhǔn)的PSO的形式如下

2 云計(jì)算能耗模型

云計(jì)算體系下,數(shù)據(jù)服務(wù)需要滿足很多限制性條件,如相應(yīng)時(shí)間、吞吐量等。對于資源調(diào)度而言,這些指標(biāo)構(gòu)成了調(diào)度算法的約束條件。本節(jié)首先研究了與調(diào)度相關(guān)的能耗模型,得到能耗的代價(jià)函數(shù)及約束條件;并指出,所求問題的解為帕累托最優(yōu)解集合。然后采用粒子群優(yōu)化算法對代價(jià)函數(shù)求取最優(yōu)解集合。

2.1 能耗模型

min∑mj=1∑ni=1fijxij3

(2)

(3)

約束條件為

xij∈{0,1},i=1,2,…,n;j=1,2,…,m

(4)

∑mj=1xij=1, ?i

(5)

(6)

∑ni=1fijxij≤maxFj, ?j

(7)

式中,xij=1表示第i個(gè)虛擬主機(jī)調(diào)度到第j個(gè)服務(wù)器,取0則否;fij表示第i個(gè)虛擬主機(jī)在第j個(gè)服務(wù)器上占用的頻率。

2個(gè)代價(jià)函數(shù)分別對應(yīng)了不同的能耗指標(biāo)。代價(jià)函數(shù)(2)代表了所有虛擬主機(jī)總動(dòng)態(tài)功耗之和最小;代價(jià)函數(shù)(3)表示盡可能提高某一臺(tái)服務(wù)器的利用率。代價(jià)函數(shù)(2)和(3)存在一定的沖突關(guān)系,從而構(gòu)成一個(gè)典型的多目標(biāo)優(yōu)化問題。與之相關(guān),約束條件則反應(yīng)了虛擬主機(jī)與服務(wù)器的硬性關(guān)系。約束條件(4)中,xij=1表示虛擬主機(jī)i分配到服務(wù)器j上,而約束(5)表示虛擬主機(jī)只能被分配到1臺(tái)服務(wù)器;約束(6)指出每個(gè)虛擬主機(jī)占用頻率的上下限;約束(7)表示1臺(tái)服務(wù)器上所有虛擬主機(jī)占用的頻率和不能超過服務(wù)器負(fù)載。

決策變量x={xij}和f={fij}構(gòu)成了最終的解。x決定了虛擬主機(jī)在服務(wù)器上的分配;而f則指出該分配下虛擬主機(jī)使用的頻率大小。如前所述,代價(jià)函數(shù)(2)和(3)計(jì)算決策變量x和f是一個(gè)多目標(biāo)優(yōu)化問題,傳統(tǒng)的最優(yōu)化算法難以求解。本節(jié)剩余部分討論了求解x和f的方法。

2.2 多目標(biāo)優(yōu)化的帕累托最優(yōu)

一般而言,代價(jià)函數(shù)(2)和(3)是相互沖突的,所以不存在使二者同時(shí)達(dá)到最小的惟一解,而是產(chǎn)生一組解的集合。數(shù)學(xué)上,把這種沒有一個(gè)解比其他解更優(yōu)的最優(yōu)解集合稱為帕累托最優(yōu)解集或帕累托最優(yōu)前沿(Pareto optimal front, POF)。此時(shí),對于(2)和(3)對應(yīng)的代價(jià)函數(shù),任意2個(gè)解f1和f2存在2種可能的關(guān)系:一個(gè)解優(yōu)于另一個(gè)解,或者兩者都不比對方優(yōu)。

本文采用帕累托占優(yōu)條件[4]來判斷解之間的關(guān)系。針對(2)和(3)對應(yīng)的代價(jià)函數(shù)的解f1和f2,當(dāng)f1的一個(gè)代價(jià)函數(shù)嚴(yán)格優(yōu)于f2,且另一個(gè)代價(jià)函數(shù)f1不嚴(yán)格劣于f2,則稱f1帕累托占優(yōu)f2,即當(dāng)滿足下式時(shí),f1帕累托占優(yōu)f2。

?i:gi(f1)≤gi(f2)

?j:gj(f1)

(8)

式中,gi,i=1,2是代價(jià)函數(shù)(2)或(3)。在給定了一個(gè)服務(wù)器分配方案x后,由(8)可以評估任意2個(gè)頻率分配方案f1和f2。

3 基于粒子群優(yōu)化的低能耗資源調(diào)度算法

由第2節(jié)可知,待求的決策變量為x和f。由于需要指定一個(gè)服務(wù)器分配方案x后,才可能獲取一個(gè)頻率分配方案f,因此,本文首先隨機(jī)給出一個(gè)分配方案x;在該方案下,使用經(jīng)典的粒子群算法進(jìn)行尋優(yōu),得到該方案對應(yīng)的帕累托最優(yōu)解集合;通過隨機(jī)改變方案,得到不同方案的最優(yōu)解集合,合并成為全局最優(yōu)解集合,并在該集合中尋找最終解。

3.1 頻率分配方案

首先隨機(jī)產(chǎn)生一個(gè)服務(wù)器分配方案xt。在xt下,按照約束條件隨機(jī)生成關(guān)于頻率分配ft的粒子群y={yi}。對于每個(gè)粒子yi,按照式(1)所示的迭代過程,進(jìn)行尋優(yōu)。

1) 粒子群尋優(yōu)。對于每一個(gè)方案,按照經(jīng)典的粒子群算法(1),需要使用粒子的局部最優(yōu)解pi和全局最優(yōu)解pg。多目標(biāo)最優(yōu)情況下,每個(gè)粒子yi存在多個(gè)局部最優(yōu),進(jìn)而合并所有粒子將產(chǎn)生多個(gè)全局最優(yōu)。因此,本文算法中允許每個(gè)粒子最多產(chǎn)生的Nl個(gè)局部最優(yōu),即pi={pi,1,pi,2,…,pi,Nl,},而合并所有局部最優(yōu)得到的全局最優(yōu)集合,最多包含Ng個(gè)元素,即pg={pg,1,pg,2,…,pg,Ng}。對于多余的解,有不同的處理方法。與文獻(xiàn)[5]不同,本文算法采用隨機(jī)拋棄多余解的方法。顯然,這有利于提高算法的實(shí)時(shí)性。

2) 迭代終止條件。為了停止粒子群迭代尋優(yōu),本文設(shè)計(jì)依據(jù)服務(wù)器分配方案存活時(shí)間的服務(wù)器分配方案跳轉(zhuǎn)概率Px。Px具體的構(gòu)造方法在3.2節(jié)討論。發(fā)生跳轉(zhuǎn)時(shí),算法存儲(chǔ)當(dāng)前xt及其對應(yīng)的全局最優(yōu)解ft=pg。取遍所有可能的組合xt及其對應(yīng)的ft,合并所有解得到最終的解集合x={xt}和f={ft}。

3) 3種帕累托最優(yōu)解集合。本文涉及到3種不同的帕累托最優(yōu)解集合,為了避免混淆,在此指明其相互關(guān)系。給定服務(wù)器分配方案xt下,最底層的集合是一個(gè)粒子yi迭代尋優(yōu)過程中產(chǎn)生的局部最優(yōu)解pi;合并局部最優(yōu)解,得到所有粒子y={yi}的全局最優(yōu)解集合ft=pg;對于不同的方案x={xt},所有ft將共同組成最終的解集合f={ft}。

3.2 服務(wù)器分配方案

本文采用服務(wù)器分配方案跳轉(zhuǎn)概率Px來終止3.1節(jié)所述的頻率分配尋優(yōu)。

本文使用分配方案的存活周期為自變量,對跳轉(zhuǎn)概率Px賦值。直觀而言,如果對一個(gè)服務(wù)器分配方案xt已經(jīng)進(jìn)行了多次粒子群迭代尋優(yōu),則可以認(rèn)為此時(shí)的結(jié)果已經(jīng)近似達(dá)到該方案下的最優(yōu)解,從而停止計(jì)算當(dāng)前的xt,轉(zhuǎn)而生成新的分配方案xt+1,重新進(jìn)行尋優(yōu)。出于以上的考慮,令

Px=I/Nt

(9)

式中,I為粒子群迭代次數(shù);Nt為指定的參數(shù)。在3.1節(jié)所述粒子群尋優(yōu)時(shí),每次迭代初始都產(chǎn)生一個(gè)[0,1]內(nèi)均勻分布的隨機(jī)數(shù),與Px進(jìn)行比較,如果小于Px,則發(fā)生跳轉(zhuǎn)。

實(shí)際中,服務(wù)器的個(gè)數(shù)一般在102～103間,本文算法隨機(jī)抽取Nx個(gè)分配方案進(jìn)行尋優(yōu)。遍歷所有Nx個(gè)服務(wù)器方案后,得到1組帕累托最優(yōu)解集合f={ft}。

根據(jù)決策者不同的需要,選擇最終的惟一解的方法也有所不同。本文采用類似文獻(xiàn)[5]的方法,計(jì)算每個(gè)解到理想最優(yōu)點(diǎn)的距離,以距離最小原則選取最終解,如圖1所示。圖1中,最終帕累托最優(yōu)解集合存在5個(gè)解,f1,f2,…,f5。解f1的動(dòng)態(tài)能耗最小,為g1min,解f5的服務(wù)器空閑能量最小,為g2min。于是,理想最優(yōu)點(diǎn)為P點(diǎn),對應(yīng)坐標(biāo)(g1min,g2min)。計(jì)算每個(gè)最優(yōu)解到P點(diǎn)的距離,按照距離最小選取最終的解。圖1中,f2為選取的最優(yōu)解。

圖1 距離評價(jià)方法

4 實(shí)驗(yàn)分析

本文采用Matlab模擬了云計(jì)算下服務(wù)器和虛擬主機(jī)。程序運(yùn)行于1臺(tái)PC機(jī),內(nèi)存1.75 GB,CPU為3.0 GHz。

4.1 參數(shù)設(shè)置

實(shí)驗(yàn)中,本文所提算法使用了如下的參數(shù)。粒子群中,慣性權(quán)重ω=1,學(xué)習(xí)因子c1=c2=1.5;采用20個(gè)粒子進(jìn)行迭代尋優(yōu)。每個(gè)粒子最多保留Nl=5個(gè)局部帕累托最優(yōu),而所有粒子共保留Ng=20個(gè)全局帕累托最優(yōu)。用于生成跳轉(zhuǎn)概率的Nt是關(guān)鍵參數(shù),較小的Nt將使算法更快結(jié)束,而較大的Nt則增加了每個(gè)方案的迭代尋優(yōu)次數(shù),從而提高得到該方案下最優(yōu)解的概率。文中取Nt=20。顯然,當(dāng)?shù)螖?shù)n=20時(shí),按照(9)式所示,算法必然發(fā)生跳轉(zhuǎn),因此,Nt還起到了傳統(tǒng)粒子群算法中迭代次數(shù)最大值的作用。

4.2 不同服務(wù)器資源下對比實(shí)驗(yàn)

通過調(diào)整服務(wù)器數(shù)量m和虛擬主機(jī)數(shù)量n,在不同的任務(wù)類型下進(jìn)行了實(shí)驗(yàn)。對比算法采用工業(yè)界普遍使用的輪詢調(diào)度方法。

首先驗(yàn)證了在m=5個(gè)服務(wù)器和n=10個(gè)虛擬主機(jī)環(huán)境下算法的性能。圖2顯示了所提算法的調(diào)度結(jié)果。其中,圖2a)顯示了某個(gè)帕累托局部最優(yōu)解集合,而圖2b)展示了最終的所有帕累托全局最優(yōu)解。按照3.2節(jié)所述距離評價(jià)方法,算法最終選擇圖2b)中左下點(diǎn)對應(yīng)的決策變量作為最終解,其動(dòng)態(tài)功耗為18.6 W,服務(wù)器空閑能量為1.157 W。在本實(shí)驗(yàn)中,每個(gè)粒子群平均存活了5.4次迭代。算法的實(shí)時(shí)性基本滿足實(shí)際要求。采用輪詢算法,動(dòng)態(tài)功耗為80 W,服務(wù)器空閑能量為20 W。

圖2 少量服務(wù)器/虛擬主機(jī)資源調(diào)度結(jié)果

在中量負(fù)載情況下,取m=100個(gè)服務(wù)器,n=300個(gè)虛擬主機(jī),所提算法得到如圖3所示結(jié)果。此時(shí),動(dòng)態(tài)功耗為1 029 W,服務(wù)器空閑能量為566.3 W。采用輪詢算法,動(dòng)態(tài)功耗為2 400 W,服務(wù)器空閑能量為1 600 W。在大量負(fù)載情況下,取m=1 000個(gè)服務(wù)器,n=2 500個(gè)虛擬主機(jī),所提算法得到如圖4所示結(jié)果。此時(shí),動(dòng)態(tài)功耗為9 038 W,服務(wù)器空閑能量為3 657 W。采用輪詢算法,動(dòng)態(tài)功耗為20 000 W,服務(wù)器空閑能量為10 000 W。

圖3 中量服務(wù)器/虛擬主機(jī)資源調(diào)度結(jié)果

圖4 大量服務(wù)器/虛擬主機(jī)資源調(diào)度結(jié)果

了驗(yàn)證所提算法對變化的服務(wù)其數(shù)量及虛擬主機(jī)數(shù)量的魯棒性,取m={21,22,…,210}個(gè)服務(wù)器,對應(yīng)虛擬主機(jī)數(shù)量n為m的21+(t-1)/10倍,t=1,2,…,10隨序號(hào)依次增多。例如,當(dāng)m=210時(shí),n=3 821。由于在4.1節(jié)參數(shù)設(shè)置中已經(jīng)指明,1臺(tái)服務(wù)器最多可以容納4臺(tái)虛擬主機(jī),此時(shí)n/m=3.73已經(jīng)接近服務(wù)器飽和狀態(tài)。圖5顯示了對比結(jié)果。圖5a)為動(dòng)態(tài)能耗對比圖,圖5b)為服務(wù)器空閑能量對比圖。出于可視化考慮,采用了log坐標(biāo)系。

圖5 不同數(shù)量服務(wù)器下性能對比圖

由圖5可見,所提算法比輪詢調(diào)度算法在動(dòng)態(tài)能耗和服務(wù)器空閑能量2個(gè)指標(biāo)上,均取得更優(yōu)的結(jié)果。在全部10組實(shí)驗(yàn)上,所提算法的動(dòng)態(tài)能耗均小于輪詢調(diào)度的50%。

4.3 能耗優(yōu)先對比實(shí)驗(yàn)

對比算法中,除了4.2節(jié)使用的輪詢調(diào)度外,還采用了文獻(xiàn)[6]中優(yōu)先受限的(precedence-constrained)并行應(yīng)用調(diào)度算法,以及文獻(xiàn)[7]采用的狀態(tài)轉(zhuǎn)移算法。

設(shè)定服務(wù)器數(shù)量m={80, 100, 120},對應(yīng)虛擬主機(jī)數(shù)量n={1,2,3}×m。為了直觀對比各算法的能耗,將輪詢調(diào)度的能耗指定為x,而其余算法的能耗相應(yīng)換算為輪詢調(diào)度的占比[8-9]。

表1展示了不同算法在n/m=1時(shí)的實(shí)驗(yàn)結(jié)果。表2對應(yīng)n/m=2的結(jié)果;表3為n/m=3的結(jié)果。各表中,黑體標(biāo)出了能耗最低的算法。

表1 不同算法能耗對比表,n/m=1 (%)

表2 不同算法能耗對比表,n/m=2 (%)

表3 不同算法能耗對比表,n/m=3 (%)

從表1～表3可見，輪詢調(diào)度的耗能最多，且普遍為智能算法能耗的2倍以上。在3種能耗相關(guān)的智能算法中，狀態(tài)轉(zhuǎn)移算法的表現(xiàn)一般，在不同服務(wù)器/虛擬機(jī)比例下，均沒有獲得最少的能耗。這是由于狀態(tài)轉(zhuǎn)移受限于其固有的模型假設(shè)，而實(shí)際中，轉(zhuǎn)移陣實(shí)時(shí)、動(dòng)態(tài)的變化，往往給該算法帶來極強(qiáng)的擾動(dòng)因素，造成算法性能下降。所提算法在7組實(shí)驗(yàn)中取得最低的能耗。

5 結(jié) 論

針對云計(jì)算中能耗過高的問題，提出一種基于粒子群優(yōu)化的資源調(diào)度算法。首先給出了能耗模型，以虛擬主機(jī)在服務(wù)器上的分配方案和占用的頻率為決策指標(biāo)，進(jìn)行優(yōu)化。指出了該模型為多目標(biāo)優(yōu)化問題，從而存在多個(gè)最優(yōu)解，即帕累托最優(yōu)解集合。采用粒子群優(yōu)化算法對于每個(gè)分配方案進(jìn)行迭代尋優(yōu)，按照從屬關(guān)系逐次構(gòu)造了單粒子帕累托局部最優(yōu)解集合、粒子群帕累托全局最優(yōu)解集合和最終的跨分配方案的帕累托最優(yōu)解集合共3個(gè)集合。在最終的集合上，采用距離評價(jià)標(biāo)準(zhǔn)，自主選擇惟一的解。在不同數(shù)量的服務(wù)器和虛擬主機(jī)環(huán)境下進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明所提算法所需能耗低于輪詢算法的50%。

參考文獻(xiàn)：

[1] Ludwig Siegele. Let it Rise: A Special Report on Corporate IT[M]. Economist Newspaper, 2008

[2] Rangan Kash, Cooke A, Post J, et al. The Cloud Wars: ＄100+billion at stake[R]. Tech Rep, Merrill Lynch, 2008

[3] James Kennedy. Particle Swarm Optimization[M]. Encyclopedia of Machine Learning, Springer, 2010

[4] Abido M A. Multiobjective Particle Swarm Optimization for Environmental/Economic Dispatch Problem[J]. Electric Power Systems Research, 2009, 79(7): 1105-1113

[5] 劉靜,羅先覺. 采用多目標(biāo)隨機(jī)黑洞粒子群優(yōu)化算法的環(huán)境經(jīng)濟(jì)發(fā)電調(diào)度[J]. 中國電機(jī)工程學(xué)報(bào), 2010, 30(34): 105-111

Liu Jing, Luo Xianjue. Environmental Economic Dispatching Adopting Multi-Objective Random Black-Hole Particle Swarm Optimization Algorithm[J]. Proceedings of the CSEE, 2010, 30(34): 105-111 (in Chinese)

[6] Mezmaz M, Melab N, Kessaci Y, et al. A Parallel Bi-Objective Hybrid Metaheuristic for Energy-Aware Scheduling for Cloud Computing Systems[J]. Journal of Parallel and Distributed Computing, 2011, 71(11):1497-1508

[7] Lee Young Choon, Zomaya A Y. A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems[J]. IEEE Trans on Parallel and Distributed Systems, 2008, 19(9): 1215-1223

[8] Li Y, Chen M, Dai W, Qiu M. Energy Optimization with Dynamic Task Scheduling Mobile Cloud Computing[J]. IEEE Systems Journal, 2017, 11(1): 96-105

[9] Rimal B P, Maier M. Workflow Scheduling in Multi-Tenant Cloud Computing Environments[J]. IEEE Trans on Parallel and Distributed Systems, 2017, 28(1): 290-304