鄭倫川

摘 要： 針對(duì)云計(jì)算機(jī)資源管理過(guò)程中如何減少人工操作，達(dá)到資源自適應(yīng)管理這一問(wèn)題，提出了基于負(fù)載相似度的神經(jīng)網(wǎng)絡(luò)負(fù)載預(yù)測(cè)算法和基于混合分組編碼的多目標(biāo)遺傳算法的資源管理策略。針對(duì)不同神經(jīng)網(wǎng)絡(luò)和不同規(guī)模物理節(jié)點(diǎn)，分別在Matlab和CloudSim環(huán)境下進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，基于負(fù)載相似度的Elman神經(jīng)網(wǎng)絡(luò)負(fù)載預(yù)測(cè)算法適應(yīng)云計(jì)算機(jī)系統(tǒng)的動(dòng)態(tài)特點(diǎn)，可以有效提高資源負(fù)載預(yù)測(cè)的準(zhǔn)確性； 基于混合分組編碼的多目標(biāo)遺傳算法的資源管理策略能在減少虛擬機(jī)遷移次數(shù)的同時(shí)優(yōu)化物理機(jī)使用數(shù)量。

關(guān)鍵詞： 云計(jì)算； 負(fù)載預(yù)測(cè)； 神經(jīng)網(wǎng)絡(luò)； 虛擬機(jī)遷移

中圖分類號(hào)： TN711?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）07?0024?05

Abstract： For the problem of how to reduce the manual operation in the process of cloud computer resources management to achieve resource adaptive management， a resource management strategy of neural network load forecasting algorithm based on load similarity and multi?objective genetic algorithm based on hybrid grouping encoding is proposed. The simulation experiments for physical nodes of different scale and different neural networks were conducted in the environments of Matlab and CloudSim respectively. The experimental results show that the Elman neural network load forecasting algorithm based on load similarity adapts to the dynamic characteristics of cloud computer system， and can effectively improve the accuracy of resource load forecasting. The resource management strategy of multi?objective genetic algorithm based on hybrid grouping encoding can reduce the frequency of the virtual machine migration， and optimize the use quantity of physical machines.

Keywords： cloud computing； load forecasting； neural network； virtual machine migration

0 引 言

云計(jì)算具有復(fù)雜性、大規(guī)模性和動(dòng)態(tài)特性等特點(diǎn)給云計(jì)算機(jī)資源的管理帶來(lái)了很多挑戰(zhàn)性問(wèn)題，其中虛擬機(jī)遷移策略和物理機(jī)使用數(shù)量的優(yōu)化最為關(guān)鍵。目前，國(guó)內(nèi)外學(xué)者對(duì)云計(jì)算資源管理的研究主要包括虛擬資源管理、資源負(fù)載預(yù)測(cè)和資源合理分配三方面。在虛擬資源管理方面，大部分是研究如何對(duì)內(nèi)存、CPU及存儲(chǔ)資源進(jìn)行虛擬間的分配，只有少量研究是基于虛擬機(jī)負(fù)載變化進(jìn)行虛擬機(jī)動(dòng)態(tài)遷移和資源分配的文獻(xiàn)[1?2]；在資源負(fù)載預(yù)測(cè)方面，文獻(xiàn)[3]無(wú)法對(duì)突發(fā)的負(fù)載進(jìn)行預(yù)測(cè)，文獻(xiàn)[4]中沒(méi)有考慮短期歷史記錄中無(wú)相似的就會(huì)影響預(yù)測(cè)效果；在資源合理分配方面，文獻(xiàn)[5]不能進(jìn)行自適應(yīng)的云計(jì)算機(jī)資源管理。

針對(duì)上述問(wèn)題，本文提出了一種基于負(fù)載相似度的神經(jīng)網(wǎng)絡(luò)負(fù)載預(yù)測(cè)算法和基于混合分組編碼的多目標(biāo)遺傳算法進(jìn)行虛擬機(jī)資源的管理，得出虛擬機(jī)最優(yōu)遷移策略，從而達(dá)到資源的自適應(yīng)優(yōu)化配置管理。

1 總體思路

基于混合分組編碼的多目標(biāo)遺傳算法進(jìn)行虛擬機(jī)資源的管理由3個(gè)模塊組成，如圖1所示。

具體來(lái)說(shuō)，該模型首先從云計(jì)算機(jī)資源全局監(jiān)控器模塊獲取資源的負(fù)載情況，然后把這些負(fù)載序列發(fā)送給資源配置策略生成器。策略生成器的負(fù)載預(yù)測(cè)模塊先根據(jù)負(fù)載進(jìn)行負(fù)載預(yù)測(cè)，通過(guò)負(fù)載預(yù)測(cè)器和虛擬資源優(yōu)化器得到優(yōu)化的虛擬機(jī)資源配置策略，最后資源配置器根據(jù)生成的資源配置策略進(jìn)行虛擬機(jī)的遷移和資源的配置工作，從而達(dá)到資源的自適應(yīng)管理。

2 具體實(shí)現(xiàn)方法

2.1 資源負(fù)載的特征聚類

2.1.1 資源負(fù)載特征提取

（1） 負(fù)載數(shù)據(jù)的選取及預(yù)處理

云計(jì)算機(jī)數(shù)據(jù)中心的短期負(fù)載預(yù)測(cè)要求一定的實(shí)時(shí)性，從而適應(yīng)動(dòng)態(tài)變化的負(fù)載。因此歷史數(shù)據(jù)的選取要綜合考慮準(zhǔn)確度和實(shí)時(shí)性，本文選擇過(guò)去3天的負(fù)載數(shù)據(jù)進(jìn)行預(yù)測(cè)，如圖2所示。

受突發(fā)因素和數(shù)據(jù)測(cè)量系統(tǒng)影響，獲得的負(fù)載數(shù)據(jù)存在一定的異常數(shù)據(jù)，需采用水平處理法和垂直處理法對(duì)數(shù)據(jù)進(jìn)行修正[6]。

（2） 云計(jì)算機(jī)資源負(fù)載特征提取

由神經(jīng)網(wǎng)絡(luò)研究可知，每個(gè)神經(jīng)網(wǎng)絡(luò)具有d個(gè)輸入及ε個(gè)輸出，分別記為d維輸入向量X{X1，X2，…，Xd}和ε維輸出向量Y{Y1，Y2，…，Yε}。為了滿足神經(jīng)網(wǎng)絡(luò)對(duì)數(shù)據(jù)的格式要求，本文采用基于滑動(dòng)窗口的資源負(fù)載特征提取方法，如圖3所示。

圖3中給定長(zhǎng)度為L(zhǎng)的云計(jì)算機(jī)資源負(fù)載時(shí)間序列，依次取d（x1，x2，…，xd）個(gè)相鄰的樣本為滑動(dòng)窗，并將它們映射為ε維預(yù)測(cè)值Yi（i=1，2，…，n），這N組數(shù)據(jù)即為負(fù)載特征向量，如表1所示，N組負(fù)載特征，每組前d個(gè)數(shù)據(jù)為輸入的負(fù)載特征數(shù)據(jù)，作為網(wǎng)絡(luò)輸入；后ε個(gè)為當(dāng)前數(shù)據(jù)的輸出負(fù)載特征，作為網(wǎng)絡(luò)訓(xùn)練輸出比較值。

2.2 資源負(fù)載的預(yù)測(cè)算法

在處理歷史數(shù)據(jù)時(shí)，首先對(duì)樣本數(shù)據(jù)進(jìn)行聚類，根據(jù)相似度將樣本分為[C]類。要根據(jù)當(dāng)前提取的[d]個(gè)時(shí)間點(diǎn)負(fù)載預(yù)測(cè)接下來(lái)[ε]個(gè)時(shí)間點(diǎn)的負(fù)載，則將這[d]個(gè)時(shí)間序列值和聚類后[C]個(gè)樣本集進(jìn)行比較，找到相似度最高的聚類作為神經(jīng)網(wǎng)絡(luò)的訓(xùn)練樣本，基于此本文提出了基于負(fù)載相似度的神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)算法，即LSNN（Load Similarity Based Nero Network）算法。

LSNN算法預(yù)測(cè)流程如圖4所示，首先需要獲取歷史負(fù)載數(shù)據(jù)，預(yù)處理后提取負(fù)載特征，然后采用KFCM?2聚類算法對(duì)負(fù)載特征進(jìn)行聚類，得到[C]個(gè)聚類集，由式（4）找到相似度最高聚類集作為訓(xùn)練樣本。然后構(gòu)建合適的神經(jīng)網(wǎng)絡(luò)開(kāi)始進(jìn)行訓(xùn)練。初始化各個(gè)參數(shù)后計(jì)算各層神經(jīng)元的輸入與輸出。當(dāng)精度達(dá)到要求時(shí)，結(jié)束訓(xùn)練，否則根據(jù)誤差值進(jìn)行權(quán)值修正，繼續(xù)迭代。直到最后輸入待預(yù)測(cè)序列得到預(yù)測(cè)結(jié)果，算法結(jié)束。

綜合云計(jì)算機(jī)負(fù)載數(shù)據(jù)選取及預(yù)處理、負(fù)載特征提取、基于KFCM?2均值聚類的負(fù)載特征分類及負(fù)載相似度的計(jì)算等方法，設(shè)計(jì)出云計(jì)算機(jī)負(fù)載預(yù)測(cè)模型，實(shí)現(xiàn)負(fù)載的自動(dòng)預(yù)測(cè)，如圖5所示。

選擇Elman神經(jīng)網(wǎng)絡(luò)作為負(fù)載預(yù)測(cè)網(wǎng)絡(luò)，由圖5可以看出，該模型主要包括5個(gè)模塊：云計(jì)算資源全局監(jiān)控器、歷史數(shù)據(jù)選取和預(yù)處理模塊、歷史負(fù)載特征提取模塊、KFCM?2聚類器以及LSNN預(yù)測(cè)器?；谪?fù)載相似度的Elman云計(jì)算機(jī)資源負(fù)載預(yù)測(cè)模型首先從云計(jì)算機(jī)資源全局監(jiān)控器獲取過(guò)去3天的負(fù)載數(shù)據(jù)，同時(shí)提取出當(dāng)前12個(gè)時(shí)間點(diǎn)的負(fù)載序列[X0]為預(yù)測(cè)基準(zhǔn)值；接著利用滑動(dòng)窗口技術(shù)提取出云計(jì)算機(jī)資源負(fù)載特征；然后使用KFCM?2聚類算法將云計(jì)算機(jī)資源負(fù)載特征分成[C]個(gè)聚類簇；最后基于[X0，]挑選出最優(yōu)聚類簇[C*，]作為Elman神經(jīng)網(wǎng)絡(luò)訓(xùn)練樣本進(jìn)行訓(xùn)練，將[X0]作為輸入，預(yù)測(cè)出接下來(lái)6個(gè)時(shí)間點(diǎn)（1 h）的云計(jì)算機(jī)資源負(fù)載預(yù)測(cè)值。

2.3 資源的配置管理

2.3.1 云計(jì)算機(jī)虛擬機(jī)資源的配置管理

2.3.2 基于混合分組編碼的多目標(biāo)遺傳算法

（1） 多目標(biāo)優(yōu)化方法

云計(jì)算機(jī)中虛擬機(jī)資源管理問(wèn)題實(shí)際是在尋求物理機(jī)使用個(gè)數(shù)最少的同時(shí)使虛擬機(jī)遷移次數(shù)最少，但實(shí)際上這兩個(gè)目標(biāo)是相互矛盾的。此時(shí)需要確定一組均衡解，其數(shù)學(xué)描述如下[7]：

（2） 混合分組編碼的多目標(biāo)遺傳算法的實(shí)現(xiàn)

① 編碼：由于一個(gè)物理機(jī)[pmj]可以虛擬出多個(gè)虛擬機(jī)[vmi，]虛擬機(jī)和物理機(jī)之間具有從屬關(guān)系，這種分組問(wèn)題需采用混合分組編碼[9]方法解決。假設(shè)有編號(hào)分別為ABCD的四個(gè)物理機(jī)，其排列順序?yàn)镃ADB；有12臺(tái)虛擬機(jī)分成四組分別分配到四臺(tái)物理機(jī)上，組成四組基因，四組基因構(gòu)成一個(gè)染色體CADB（C{2，4，7}，A{1，9，6}，D{8，10，11，12}，B{3，5}）。染色體具體表示如圖6所示。

② 譯碼：如圖7所示，3個(gè)坐標(biāo)軸分別表示物理機(jī)的CPU、存儲(chǔ)、內(nèi)存三種資源，將每個(gè)基因所包含的虛擬機(jī)依次放入空間的左下角，直到物理機(jī)沒(méi)有足夠空間或虛擬機(jī)放完為止。

③ 初始染色體種群的生成：首先隨機(jī)地生成[M]個(gè)虛擬機(jī)請(qǐng)求序列，接著對(duì)每一個(gè)虛擬機(jī)請(qǐng)求序列[Mi]進(jìn)行如下操作生成初始染色體種群：

Step1：對(duì)當(dāng)前請(qǐng)求序列[Mi，]依次遍歷[Mi]中的虛擬機(jī)請(qǐng)求[RVj；]

Step2：從當(dāng)前物理機(jī)中尋找下標(biāo)最小且滿足[RVj]所需資源的物理機(jī)PM，將該虛擬機(jī)分配到物理機(jī)PM上；

Step3：檢查此次分配是否滿足約束公式（6），如滿足，將虛擬機(jī)請(qǐng)求[RVj]從請(qǐng)求序列[Mi]中刪除，此次分配成功；

Step4：若[Mi]中虛擬機(jī)請(qǐng)求全部處理完，則處理[Mi+1]虛擬機(jī)請(qǐng)求策略，直到處理完所有虛擬機(jī)請(qǐng)求策略。

通過(guò)以上處理，就生成了[M]個(gè)虛擬機(jī)請(qǐng)求序列配置方案，作為染色體初始種群。

④ 適應(yīng)度：適應(yīng)度函數(shù)是根據(jù)目標(biāo)函數(shù)變換而來(lái)的，F(xiàn)it（X）=Φ（·），其中Φ（·）是從目標(biāo)函數(shù)轉(zhuǎn)換為適應(yīng)度的變換函數(shù)。

⑤ 個(gè)體選擇：本文采用PAES算法的比較策略，從隨機(jī)選擇出來(lái)的兩個(gè)個(gè)體中，擇優(yōu)選擇適應(yīng)度好的作為下一代，重復(fù)選擇直到達(dá)到期望的種群規(guī)模。

⑥ 交叉：每個(gè)分組虛擬機(jī)的個(gè)數(shù)不固定，因此交叉操作要能夠處理不等長(zhǎng)的基因，方法如下：

Step1：在父染色體中隨機(jī)選擇兩個(gè)交叉點(diǎn)，并確定交叉部分，每個(gè)交叉部分即為一個(gè)分組；

Step2：把第一個(gè)父染色體的交叉部分注入到第二個(gè)父染色體的交叉點(diǎn)；

Step3：消除第二個(gè)父染色體中重復(fù)的基因，即刪除重復(fù)的虛擬機(jī)；

Step4：刪除重復(fù)虛擬機(jī)后，如有需要，根據(jù)適應(yīng)度調(diào)整染色體，這樣就可得到一個(gè)后代染色體；

Step5：以同樣的交叉方法應(yīng)用到父染色體中，得到第二個(gè)后代。

⑦ 變異：選擇一個(gè)父?jìng)€(gè)體，從中刪除一個(gè)虛擬機(jī)組，然后將刪除的虛擬機(jī)重新分配到各個(gè)物理機(jī)中，從而得到變異染色體。

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

3.1 資源負(fù)載的特征聚類仿真

試驗(yàn)數(shù)據(jù)來(lái)自NASA數(shù)據(jù)中心，以10 min為間隔進(jìn)行一次資源重新配置，統(tǒng)計(jì)每10 min內(nèi)數(shù)據(jù)中心的負(fù)載請(qǐng)求，并以過(guò)去3天的負(fù)載數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，預(yù)測(cè)接下來(lái)12個(gè)時(shí)間點(diǎn)（2 h）的資源負(fù)載。

數(shù)據(jù)處理后，利用滑動(dòng)窗口方法對(duì)負(fù)載數(shù)據(jù)進(jìn)行負(fù)載特征提取，生成訓(xùn)練樣本。設(shè)窗口大小為1，每個(gè)窗口有12個(gè)數(shù)據(jù)點(diǎn)（2 h），如此3天共計(jì)36組訓(xùn)練樣本，每組包含12個(gè)輸入值和12個(gè)預(yù)測(cè)值。

3.2 資源負(fù)載的預(yù)測(cè)算法仿真

從NASA數(shù)據(jù)中心負(fù)載請(qǐng)求日志中可以統(tǒng)計(jì)出數(shù)據(jù)中心的負(fù)載序列，進(jìn)行試驗(yàn)驗(yàn)證預(yù)測(cè)的有效性。本文以10 min為單位對(duì)數(shù)據(jù)中心的負(fù)載進(jìn)行統(tǒng)計(jì)，并以2 h（即[d=12]個(gè)數(shù)據(jù)點(diǎn)）為一組數(shù)據(jù)，并利用前3天的資源負(fù)載數(shù)據(jù)來(lái)預(yù)測(cè)接下來(lái)1 h（即[ε=6]個(gè)數(shù)據(jù)點(diǎn)）的云計(jì)算機(jī)資源負(fù)載，預(yù)測(cè)結(jié)果為判定節(jié)點(diǎn)低載或過(guò)載提供依據(jù)，從而選出相應(yīng)的虛擬機(jī)遷移序列，為虛擬機(jī)實(shí)時(shí)配置決策提供支持。

對(duì)于Elman神經(jīng)網(wǎng)絡(luò)，d=win*ε，win表示一個(gè)窗口的大小，[ε]為輸出向量的維數(shù)，[d]是輸入向量的維數(shù)，win窗口的大小會(huì)對(duì)預(yù)測(cè)結(jié)果產(chǎn)生影響，因此需合理確定win的大小。根據(jù)試驗(yàn)要求，調(diào)整win的大小，固定其他參數(shù)不變，計(jì)算出不同win值對(duì)應(yīng)的MSE，圖9給出了不同win值的預(yù)測(cè)結(jié)果，表2給出了不同win值預(yù)測(cè)結(jié)果的MSE值。

從圖10中可以得到如下結(jié)論：

（1） 當(dāng)聚類簇為1時(shí)表示沒(méi)有對(duì)負(fù)載特征進(jìn)行聚類，即普通的BP和Elman算法，MSE誤差在5%左右，能達(dá)到較好水平；

（2） 當(dāng)聚類個(gè)數(shù)為2，應(yīng)用基于負(fù)載相似度的預(yù)測(cè)算法，MSE誤差分別為0.7%和0.9%，達(dá)到了預(yù)期效果，證明了基于負(fù)載相似度算法的有效性；

（3） 當(dāng)聚類個(gè)數(shù)為3，預(yù)測(cè)結(jié)果偏差在20%以上，這是因?yàn)檫^(guò)度聚類導(dǎo)致實(shí)際預(yù)測(cè)的樣本不足，從而導(dǎo)致較大偏差的出現(xiàn)；

（4） Elman算法的預(yù)測(cè)性能整體比BP好。

3.3 資源的配置管理仿真

本文選擇CloudSim作為仿真平臺(tái)。仿真實(shí)驗(yàn)中分別模擬了50，100，200個(gè)物理節(jié)點(diǎn)三種規(guī)模進(jìn)行實(shí)驗(yàn)對(duì)比，每個(gè)物理節(jié)點(diǎn)裝備2個(gè)處理器，頻率為3 000 MIPS，1 Gb/s網(wǎng)絡(luò)帶寬，8 GB內(nèi)存，7 200轉(zhuǎn)512 GB硬盤。實(shí)驗(yàn)中使用的虛擬機(jī)是單核的，每個(gè)虛擬機(jī)的配置根據(jù)需要?jiǎng)討B(tài)分配資源。

從中可以得出如下結(jié)論：

（1） 以最少物理機(jī)使用個(gè)數(shù)為目標(biāo)的配置策略可使物理機(jī)使用個(gè)數(shù)最少，但虛擬機(jī)遷移次數(shù)較高。

（2） 以最少遷移次數(shù)為目標(biāo)的配置策略可使虛擬機(jī)遷移次數(shù)最少，但物理機(jī)使用個(gè)數(shù)增多。

（3） 基于混合分組的多目標(biāo)遺傳算法配置策略的虛擬機(jī)遷移次數(shù)和物理機(jī)使用個(gè)數(shù)雖然都不是單個(gè)最優(yōu)，但實(shí)現(xiàn)最優(yōu)權(quán)衡，服務(wù)級(jí)目標(biāo)（SLA）違背率最低，并且使用相對(duì)較少的虛擬機(jī)遷移次數(shù)和較少的物理機(jī)個(gè)數(shù)。

4 結(jié) 論

本文提出了基于負(fù)載相似度的Elman神經(jīng)網(wǎng)絡(luò)負(fù)載預(yù)測(cè)算法和基于混合分組編碼的多目標(biāo)遺傳算法的虛擬機(jī)資源管理策略。并在CloudSim及Matlab環(huán)境下分別完成了仿真實(shí)驗(yàn)，證明了負(fù)載預(yù)測(cè)算法和資源管理策略的有效性。本文所提出的負(fù)載預(yù)測(cè)算法只考慮了過(guò)去3天時(shí)間內(nèi)的負(fù)載情況，屬于短期負(fù)載預(yù)測(cè)，對(duì)周度、月度等中長(zhǎng)期負(fù)載預(yù)測(cè)還無(wú)法進(jìn)行；提出的資源管理策略是以虛擬機(jī)為資源單位進(jìn)行管理的，屬粗粒度資源管理，對(duì)細(xì)粒度資源管理還無(wú)法進(jìn)行，還需進(jìn)一步完善。

參考文獻(xiàn)

[1] SHIN D， AKKAN H. Domain?based virtualized resource ma?nagement in cloud computing [C]// Proceedings of 2010 6th International Conference on Collaborative Computing： Networ?king， Applications and Worksharing. Chicago： IEEE， 2010： 1?6.

[2] KUPFERMAN J， SILVERMAN J， JARA P， et al. Scaling into the cloud [EB/OL]. [2009?08?12] http：//cs.ucsb.edu/jkupferman/docs/scalingintothecloudsPDF.

[3] 李強(qiáng)，郝汾沁，肖利民，等.云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（12）：2253?2264.

[4] CARON E， DESPREZ F， MURESAN A. Forecasting for grid and cloud computing on?demand resources based on pattern matching [C]// Proceedings of 2010 2nd IEEE International Conference on Cloud Computing Technology and Science. Indianapolis： IEEE， 2010： 456?463.

[5] LI M K， CHEN M， XIE J. Cloud computing： a synthesis mo?dels for resource service management [C]// Proceedings of 2010 Second International Conference on Communication Systems， Networks and Applications. [S.l.]： IEEE， 2010： 208?211.

[6] 朱振偉.氣象因素對(duì)電網(wǎng)負(fù)荷特性影響的研究[D].杭州：浙江大學(xué)，2008.

[7] 祁薇熹，李彬.多目標(biāo)演化算法的進(jìn)展研究[J].計(jì)算機(jī)與數(shù)字工程，2008，36（5）：16?18.

[8] 賴紅松，董品杰，祝國(guó)瑞.求解多目標(biāo)規(guī)劃問(wèn)題的Pareto多目標(biāo)遺傳算法[J].系統(tǒng)工程，2003，21（5）：24?28.

[9] FALKENAUER E. A Hybrid grouping genetic alogrithm for bin packing [J]. Journal of heuristics， 1996， 2（1）： 5?30.