鄭倫川

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

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

中圖分類號： TN711?34； TM417 文獻(xiàn)標(biāo)識碼： A 文章編號： 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 引 言

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

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

1 總體思路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 資源的配置管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step2：把第一個父染色體的交叉部分注入到第二個父染色體的交叉點；

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

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

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

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

3 仿真實驗

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

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

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

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

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

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

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

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

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

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

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

3.3 資源的配置管理仿真

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

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

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

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

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

4 結(jié) 論

本文提出了基于負(fù)載相似度的Elman神經(jīng)網(wǎng)絡(luò)負(fù)載預(yù)測算法和基于混合分組編碼的多目標(biāo)遺傳算法的虛擬機(jī)資源管理策略。并在CloudSim及Matlab環(huán)境下分別完成了仿真實驗，證明了負(fù)載預(yù)測算法和資源管理策略的有效性。本文所提出的負(fù)載預(yù)測算法只考慮了過去3天時間內(nèi)的負(fù)載情況，屬于短期負(fù)載預(yù)測，對周度、月度等中長期負(fù)載預(yù)測還無法進(jìn)行；提出的資源管理策略是以虛擬機(jī)為資源單位進(jìn)行管理的，屬粗粒度資源管理，對細(xì)粒度資源管理還無法進(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ī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J].計算機(jī)學(xué)報，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] 朱振偉.氣象因素對電網(wǎng)負(fù)荷特性影響的研究[D].杭州：浙江大學(xué)，2008.

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

[8] 賴紅松，董品杰，祝國瑞.求解多目標(biāo)規(guī)劃問題的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.