采用隨機(jī)規(guī)劃模型的云資源分配算法①

陳俊杰

(南通大學(xué) 電子信息學(xué)院,南通 226019)

近年來,云計算技術(shù)發(fā)展迅速,涌現(xiàn)出了一大批成熟的云計算服務(wù)平臺.基礎(chǔ)設(shè)施即服務(wù)(IaaS)、平臺即服務(wù)(PaaS)和軟件即服務(wù)(SaaS)是云計算的三種主要的服務(wù)模式,其中IaaS應(yīng)用最廣泛.IaaS采用虛擬化技術(shù)將物理服務(wù)器抽象成虛擬機(jī),并且通過互聯(lián)網(wǎng)提供給云消費者使用,云消費者采用按使用付費的方式租用虛擬機(jī).

云提供商(Amazon EC2)向云消費者提供了兩種計費策略,按需實例和預(yù)留實例.對于按需實例,云消費者根據(jù)當(dāng)前的工作負(fù)載動態(tài)獲取,按照實際使用情況付費.對于預(yù)留實例,云消費者需要預(yù)付部分費用,并且在預(yù)留期間不管是否使用都需要付費.通過權(quán)衡按需實例和預(yù)留實例的使用,可以有效降低云消費者的資源使用成本.因此,云資源預(yù)留問題即為: 確定預(yù)留資源的數(shù)量,以最小化云消費者的資源使用成本.

虛擬機(jī)整合問題旨在通過虛擬機(jī)的在線遷移,在滿足云消費者資源需求的前提下,最小化所使用的物理服務(wù)器的數(shù)量,以降低能耗,實現(xiàn)綠色云計算.師雪霖等人借鑒網(wǎng)絡(luò)效用最大化模型,提出了虛擬機(jī)放置的效用最大化模型,并且將原始問題轉(zhuǎn)化為拉格朗日對偶問題,采用次梯度算法進(jìn)行求解[1].趙君等人同時考慮物理資源的浪費和網(wǎng)絡(luò)總流量,將虛擬機(jī)放置問題建模為多目標(biāo)優(yōu)化問題,并且提出了一種基于多目標(biāo)蟻群優(yōu)化的虛擬機(jī)放置算法[2].Xiao等人提出了一種虛擬機(jī)放置的啟發(fā)式算法,引入了偏度的概念度量服務(wù)器中多種資源利用的不均衡性,通過最小化偏度,可以有效整合不同類型的工作負(fù)載,提高服務(wù)器資源的整體利用率[3].Zhang等人考慮了服務(wù)器和負(fù)載的異構(gòu)性,提出了異構(gòu)感知的云資源提供算法[4].

本文從云消費者的角度研究云資源提供問題.Chaisiri等人考慮了需求和價格的不確定性,將云資源提供問題建模為多階段隨機(jī)整數(shù)規(guī)劃問題,并且使用Benders分解算法進(jìn)行求解[5].冉泳屹等人使用大偏差理論在線估計過載概率,根據(jù)過載概率動態(tài)調(diào)整按需實例的數(shù)量,同時采用自回歸模型確定預(yù)留實例的數(shù)量,進(jìn)一步降低云消費者的資源使用成本[6].然而,冉泳屹等人并沒有給出云資源預(yù)留問題的數(shù)學(xué)描述,并且在確定預(yù)留實例的數(shù)量時,僅僅考慮了單一的實例類型.Hwang等人將云資源提供問題分成兩個階段,在資源預(yù)留階段,通過一個啟發(fā)式方法確定資源預(yù)留方案,在按需分配階段,采用卡爾曼濾波器預(yù)測當(dāng)前的資源需求[7].Hwang等人雖然給出了云資源預(yù)留問題的數(shù)學(xué)描述,但是所提出的啟發(fā)式算法僅僅考慮了一種虛擬機(jī)類型,以確定最優(yōu)的虛擬機(jī)預(yù)留數(shù)量的上界和下界.在先前的研究中,我們將云資源提供問題建模為兩階段的隨機(jī)整數(shù)規(guī)劃問題,并轉(zhuǎn)化為確定性的整數(shù)線性規(guī)劃問題,利用CPLEX軟件進(jìn)行求解,但是其計算復(fù)雜度較高,不適用于在線應(yīng)用[8].

本文從云消費者的角度研究云資源提供問題,提出了一種采用隨機(jī)規(guī)劃模型的云資源分配算法.首先,同時考慮按需實例和預(yù)留實例,采用兩階段隨機(jī)整數(shù)規(guī)劃對云資源提供問題進(jìn)行建模.然后,采用抽樣平均近似方法減少資源提供問題的場景數(shù)量,降低計算復(fù)雜度,并且提出了一種基于階段分解的混合進(jìn)化算法求解資源提供問題.在仿真實驗中,基于真實的工作負(fù)載數(shù)據(jù)及Amazon EC2的定價模型評估所提出的云資源分配算法,驗證了所提出算法的有效性.

1 云資源提供問題

1.1 云計算環(huán)境

針對特定的服務(wù),云提供商提供了多種可供選擇虛擬機(jī)類型,令V={V1,V2,···,VN}表示云提供商所提供的一組虛擬機(jī)類型,N為虛擬機(jī)類型的總數(shù).假設(shè)一個Vi類型的虛擬機(jī)的資源配置為Ri=[ri1,ri2,···,riM],M為虛擬機(jī)所擁有的資源類型的總數(shù).令Ci表示一個Vi類型的虛擬機(jī)的服務(wù)容量,定義為在給定的服務(wù)質(zhì)量約束條件下,一個Vi類型的虛擬機(jī)所能支持的最大并發(fā)用戶數(shù)或服務(wù)請求到達(dá)速率.

云提供商(Amazon EC2)提供了兩種計費策略,按需實例和預(yù)留實例.對于按需實例,云消費者根據(jù)當(dāng)前的工作負(fù)載動態(tài)獲取,按照實際使用情況付費.對于預(yù)留實例,云消費者需要預(yù)付部分費用,并且在預(yù)留期間不管是否使用都需要付費.令按需實例的計費周期(短期規(guī)劃周期)為TS,預(yù)留實例的計費周期(長期規(guī)劃周期)為TL,令T=TL/TS.假設(shè)一個Vi類型的預(yù)留實例預(yù)付費用為PRi,令pRi=PRi/T,在預(yù)留期間每時間TS費用為pri,一個Vi類型的按需實例每時間TS費 用為poi,通常假設(shè)poi＞pri+pRi.

1.2 基于隨機(jī)規(guī)劃的云資源提供問題

假設(shè)在第t(1≤t≤T)個短期規(guī)劃周期,云消費者的工作負(fù)載為dt.令R={n1,···,nN}表示長期規(guī)劃周期的資源預(yù)留方案,其中ni為Vi類型的預(yù)留實例的數(shù)量,預(yù)留的服務(wù)容量為預(yù)留實例的使用成本為在短期規(guī)劃周期,若預(yù)留的服務(wù)容量能夠滿足工作負(fù)載需求,則不需要動態(tài)分配按需實例,否則,需要動態(tài)分配按需實例,按需實例的使用成本為

其中,xi表 示Vi類型的按需實例的數(shù)量.問題(1)是短期規(guī)劃周期的按需資源分配問題,即給定資源預(yù)留方案和當(dāng)前的工作負(fù)載,動態(tài)分配按需實例,在滿足工作負(fù)載需求的條件下,最小化按需實例的使用成本.

云資源提供問題可以描述為

其中目標(biāo)函數(shù)為長期規(guī)劃周期中預(yù)留實例和按需實例總的使用成本.問題(2)依賴于長期規(guī)劃周期的工作負(fù)載情況,使用云消費者的工作負(fù)載歷史數(shù)據(jù),可以對工作負(fù)載的概率分布pD(Dk)進(jìn) 行估計,其中Dk,k=1,2,···,K,(D1＜D2＜···＜DK)為工作負(fù)載所有可能的取值.因此,問題(2)可以轉(zhuǎn)化為

其中目標(biāo)函數(shù)為每個短期規(guī)劃周期中預(yù)留實例和按需實例的平均使用成本.問題(3)是一個兩階段的隨機(jī)整數(shù)規(guī)劃問題.在資源預(yù)留階段,需要根據(jù)長期規(guī)劃周期的工作負(fù)載情況,確定預(yù)留實例的類型和數(shù)量,在按需分配階段,需要根據(jù)當(dāng)前的工作負(fù)載,確定動態(tài)分配的按需實例的類型和數(shù)量.

問題(3)可以轉(zhuǎn)化為一個確定性的整數(shù)線性規(guī)劃問題,

問題(4)被稱為問題(3)的確定性等價問題,可以通過CPLEX軟件進(jìn)行求解.

2 云資源分配算法

2.1 抽樣平均近似問題

當(dāng)工作負(fù)載D取值(隨機(jī)規(guī)劃問題的場景)的數(shù)量很大,甚至可能是一個連續(xù)的隨機(jī)變量時,問題(3)中的隨機(jī)規(guī)劃問題將不易求解.為了求解這個復(fù)雜的問題,可以使用抽樣平均近似方法.抽樣平均近似方法對場景進(jìn)行抽樣,減少場景數(shù)量,降低求解復(fù)雜度.常用的抽樣方法包括蒙特卡羅方法、擬蒙特卡羅方法和均勻離散化方法等.因為工作負(fù)載D是一個一維的隨機(jī)變量,所以這里使用均勻離散化方法[9].

在均勻離散化方法中,將整個概率區(qū)間[ 0,1]均勻離散化,生成NS個等間隔的離散概率點pj=(2j-1)/(2NS),j=1,…,NS,對于每一個pj,找到最小的kj(1≤kj≤K),使得則Dkj為工作負(fù)載D的第j個抽樣.由D的NS個抽樣,問題(3)可以近似表示為

上述問題被稱為問題(3)的抽樣平均近似問題,該問題仍然是一個兩階段的隨機(jī)整數(shù)規(guī)劃問題,可以轉(zhuǎn)化為一個確定性的整數(shù)線性規(guī)劃進(jìn)行求解,并且樣本容量NS越大,抽樣平均近似問題的近似精度越高.

2.2 混合進(jìn)化算法

雖然抽樣平均近似方法可以減少場景數(shù)量,有效降低求解復(fù)雜度,但是問題(5)轉(zhuǎn)化為確定性等價的整數(shù)規(guī)劃問題之后,規(guī)模仍然很大,不采用分解算法很難求解.本文提出了一種基于階段分解的混合進(jìn)化算法,使用進(jìn)化算法對第一階段決策變量進(jìn)行搜索,對于第二階段子問題使用整數(shù)規(guī)劃進(jìn)行求解.因此,問題(5)可以分解為:

主問題:

子問題:

在主問題中需要確定預(yù)留實例的類型和數(shù)量,在子問題中需要確定按需實例的類型和數(shù)量,子問題的決策依賴于主問題的決策,并且對于主問題中給定的虛擬機(jī)預(yù)留配置,子問題是NS個小規(guī)模的整數(shù)線性規(guī)劃問題.對于第一階段主問題,使用進(jìn)化算法進(jìn)行求解,對于第二階段子問題,使用標(biāo)準(zhǔn)的整數(shù)線性規(guī)劃求解方法進(jìn)行求解.

接下來重點研究基于遺傳算法的主問題求解方法.遺傳算法的關(guān)鍵是編碼方案、適應(yīng)度函數(shù)及遺傳算子的設(shè)計[10].

(1)染色體編碼

在進(jìn)行遺傳操作之前,首先需要對優(yōu)化問題的可行解進(jìn)行編碼.常用的編碼方法有二進(jìn)制編碼、格雷碼編碼和實數(shù)編碼等,其中二進(jìn)制編碼存在漢明懸崖問題,格雷碼編碼在進(jìn)行交叉操作時會產(chǎn)生更高階的非線性.為了克服這些問題,這里采用實數(shù)編碼方案.對于問題(6)的一個可行解(n1,n2,···,nN),ni∈N0且0≤ni≤nmiax,其中nmiax=「Dmax/Ci?,Dmax為工作負(fù)載需求的最大值,ni可 以用一個實數(shù)變量xi表 示0 ≤xi.因此,可 行 解可以編碼為(x1,x2,···,xN).

(2)適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評價種群中個體對環(huán)境的適應(yīng)程度,也就是可行解的優(yōu)劣,可行解越好,適應(yīng)度函數(shù)值越大.問題(6)是一個最小化問題,以總的資源提供成本最小化為優(yōu)化目標(biāo).對于可行解(n1,n2,···,nN),適應(yīng)度函數(shù)f(n1,···,nN)定義為

其中,T(n1,···,nN)是虛擬機(jī)預(yù)留配置為(n1,···,nN)時總的資源提供成本,Tmin是到目前為止所獲得的目標(biāo)函數(shù)的最小值.為了確定T(n1,···,nN),需要求解NS個子問題(7).

(3)選擇

選擇算子實現(xiàn)種群的優(yōu)勝劣汰,既要保證一定的選擇強(qiáng)度,使得種群向著最優(yōu)解進(jìn)化,又要保持種群的多樣性,防止未成熟收斂.常用的選擇算子有適應(yīng)度比例選擇、錦標(biāo)賽選擇和排序選擇等.根據(jù)Blickle等人[11]的研究,指數(shù)排序選擇算子能夠在相同的選擇強(qiáng)度條件下,保證較好的種群多樣性,避免算法陷入局部最優(yōu)解,因此本文采用指數(shù)排序選擇算子.在指數(shù)排序選擇操作中,首先對種群中所有個體按照適應(yīng)度值升序排列,然后按照個體的順序為其分配相應(yīng)的選擇概率

其中,c=pi/pi+1(0＜c＜1)是相鄰兩個個體選擇概率的比值,c值越小,選擇算子的選擇強(qiáng)度越大.在確定了每個個體的選擇概率之后,使用輪盤賭采樣法選擇個體.

(4)交叉

交叉操作是遺傳算法的關(guān)鍵步驟,決定了遺傳算法的全局搜索能力.本文采用模擬二進(jìn)制交叉算子(SBX)[12],對于大多數(shù)優(yōu)化問題具有良好的全局搜索能力.在SBX操作中,對于兩個父個體βi=(βi1,βi2,···,βiN)和βj=(βj1,βj2,···,βjN),兩個子個體 β′i和 β′j定義為

其中,Bk定義為

其中,u是 [ 0,1]上 均勻分布的隨機(jī)數(shù),η取值為2.

(5)變異

變異算子決定了遺傳算法的局部搜索能力,同時也維持了種群的多樣性.常用的變異算子有均勻變異、高斯變異和Breeder變異等.均勻變異和高斯變異的性能依賴于參數(shù)的自適應(yīng)調(diào)整,Breeder變異的性能稍差,但是更容易實施.在Breeder變異操作中,

其中,正負(fù)號以相等的概率隨機(jī)選擇,rangei是ni的取值范圍,θ定義為

其中,a(m)以 概率1 /M取值為1,以概率1 -1/M取值為0.

遺傳算法的流程為:

參數(shù)設(shè)置: 在遺傳算法中,種群規(guī)模N、交叉概率pc和 變異概率pm與算法的性能密切相關(guān).通常: 種群規(guī)模設(shè)置為大于變量數(shù)的10倍,交叉概率設(shè)置為0.7-0.8之間,變異概率設(shè)置為變量數(shù)的倒數(shù)[10].

步驟1.隨機(jī)生成問題(6)的N個可行解作為初始種群;

步驟2.使用指數(shù)排序選擇法選擇當(dāng)前種群中的個體進(jìn)行復(fù)制,執(zhí)行N次,生成N個個體;

步驟3.將選擇-復(fù)制操作生成的N個個體進(jìn)行隨機(jī)配對,對每一對個體,以交叉概率pc執(zhí)行SBX操作;

步驟4.對交叉操作生成的每一個個體,以變異概率pm執(zhí)行Breeder變異操作;

步驟5.判斷是否滿足終止條件,若滿足則終止遺傳算法,否則返回步驟2繼續(xù)執(zhí)行遺傳算法.

3 仿真實驗

使用某網(wǎng)站一個月的工作負(fù)載歷史數(shù)據(jù)作為實驗數(shù)據(jù),如圖1所示.根據(jù)工作負(fù)載歷史數(shù)據(jù),可以對工作負(fù)載的概率分布進(jìn)行估計,結(jié)果如圖2所示.針對Web服務(wù),云提供商(Amazon EC2)提供了4種類型的虛擬機(jī): Small(m1.small),Medium(m1.medium),Large(m1.large),Extra Large(m1.xlarge),它們的計費策略和服務(wù)能力[7]如表1所示.

圖1 工作負(fù)載

圖2 工作負(fù)載的概率分布

表1 每種虛擬機(jī)類型的計費策略和服務(wù)能力

3.1 資源預(yù)留方案對運營成本的影響

首先分析資源預(yù)留對云消費者的資源使用成本的影響.研究不同的資源預(yù)留方案下云消費者的資源使用成本,結(jié)果如圖3所示.從圖中可以看出,最優(yōu)的資源預(yù)留方案為{n1=0,n2=0,n3=4,n4=0},預(yù)留的服務(wù)容量為260請求/秒,資源使用成本為5694美元.隨著預(yù)留資源的增加,預(yù)留實例的使用成本逐漸增大,按需實例的使用成本逐漸減小,在預(yù)留資源太多或者太少時資源使用成本均比較高,這是因為在預(yù)留資源太多時,預(yù)留實例得不到充分使用,造成資源浪費,在預(yù)留資源太少時,需要使用更多的按需實例.

圖3 資源預(yù)留方案對運營成本的影響

3.2 抽樣平均近似方法

接下來分析抽樣平均近似方法的性能,比較均勻離散化方法與蒙特卡羅方法及擬蒙特卡羅方法的近似精度,并討論抽樣點數(shù)對近似精度的影響,結(jié)果如圖4所示.從圖中可以看出,抽樣點數(shù)越大,抽樣平均近似方法的近似精度越高,在相同的抽樣點數(shù)下,均勻離散化方法比蒙特卡羅方法及擬蒙特卡羅方法的近似精度更高,當(dāng)抽樣點數(shù)NS=10時,均勻離散化方法的近似精度達(dá)到99%.因此,選擇均勻離散化方法,并且選取抽樣點數(shù)NS=10.

圖4 抽樣平均近似方法的性能

3.3 混合進(jìn)化算法

最后分析混合進(jìn)化算法的性能.從圖5可以看出,隨著進(jìn)化代數(shù)的增加,所獲得的資源預(yù)留方案逐漸趨向于最優(yōu)的資源預(yù)留方案,當(dāng)進(jìn)化代數(shù)G≥7時,所獲得的資源預(yù)留方案即為最優(yōu)的資源預(yù)留方案.因此,混合進(jìn)化算法的終止條件選為G=20.比較本文所提出的混合進(jìn)化算法和Hwang等人所提出的啟發(fā)式算法的性能,二者均可獲得最優(yōu)的資源預(yù)留方案,節(jié)省了超過25%的運營成本,但是Hwang等人的方法需要針對搜索范圍內(nèi)的每個資源預(yù)留方案,確定總的運營成本,所以求解過程所消耗的時間更長,并且當(dāng)最優(yōu)解不在搜索范圍內(nèi)時不能獲得最優(yōu)的資源預(yù)留方案.

圖5 混合進(jìn)化算法的進(jìn)化過程

4 總結(jié)

本文針對云資源提供問題,提出了一種采用隨機(jī)規(guī)劃模型的云資源分配算法,在滿足云消費者資源需求的條件下,最小化其資源使用成本.首先,同時考慮按需實例和預(yù)留實例,采用兩階段隨機(jī)整數(shù)規(guī)劃對云資源提供問題進(jìn)行建模.然后,采用抽樣平均近似方法和基于階段分解的混合進(jìn)化算法求解云資源提供問題.基于真實的工作負(fù)載數(shù)據(jù)及Amazon EC2的定價模型驗證所提出的云資源分配算法.仿真實驗結(jié)果表明,所提出的云資源分配算法能夠在較短時間內(nèi)獲得近似最優(yōu)的云資源預(yù)留方案,有效降低了云消費者的資源使用成本.