陳俊杰

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

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

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

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

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

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

1 云資源提供問(wèn)題

1.1 云計(jì)算環(huán)境

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

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

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

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

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

云資源提供問(wèn)題可以描述為

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

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

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

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

2 云資源分配算法

2.1 抽樣平均近似問(wèn)題

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

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

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

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

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

主問(wèn)題:

子問(wèn)題:

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

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

(1)染色體編碼

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

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

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

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

(3)選擇

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

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

(4)交叉

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

其中,Bk定義為

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

(5)變異

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

其中,正負(fù)號(hào)以相等的概率隨機(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ī)生成問(wèn)題(6)的N個(gè)可行解作為初始種群;

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

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

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

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

3 仿真實(shí)驗(yàn)

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

圖1 工作負(fù)載

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

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

3.1 資源預(yù)留方案對(duì)運(yùn)營(yíng)成本的影響

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

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

3.2 抽樣平均近似方法

接下來(lái)分析抽樣平均近似方法的性能,比較均勻離散化方法與蒙特卡羅方法及擬蒙特卡羅方法的近似精度,并討論抽樣點(diǎn)數(shù)對(duì)近似精度的影響,結(jié)果如圖4所示.從圖中可以看出,抽樣點(diǎn)數(shù)越大,抽樣平均近似方法的近似精度越高,在相同的抽樣點(diǎn)數(shù)下,均勻離散化方法比蒙特卡羅方法及擬蒙特卡羅方法的近似精度更高,當(dāng)抽樣點(diǎn)數(shù)NS=10時(shí),均勻離散化方法的近似精度達(dá)到99%.因此,選擇均勻離散化方法,并且選取抽樣點(diǎn)數(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時(shí),所獲得的資源預(yù)留方案即為最優(yōu)的資源預(yù)留方案.因此,混合進(jìn)化算法的終止條件選為G=20.比較本文所提出的混合進(jìn)化算法和Hwang等人所提出的啟發(fā)式算法的性能,二者均可獲得最優(yōu)的資源預(yù)留方案,節(jié)省了超過(guò)25%的運(yùn)營(yíng)成本,但是Hwang等人的方法需要針對(duì)搜索范圍內(nèi)的每個(gè)資源預(yù)留方案,確定總的運(yùn)營(yíng)成本,所以求解過(guò)程所消耗的時(shí)間更長(zhǎng),并且當(dāng)最優(yōu)解不在搜索范圍內(nèi)時(shí)不能獲得最優(yōu)的資源預(yù)留方案.

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

4 總結(jié)

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