基于多步優(yōu)化GM（1，1）模型的云計算資源負荷短期預測

張 磊，徐達宇

ZHANG Lei1,XU Dayu2

1.安徽工商職業(yè)學院 網(wǎng)絡中心，合肥 230009

2.合肥工業(yè)大學 過程優(yōu)化與智能決策教育部重點實驗室，合肥 230009

1.Network Centre,Anhui Business Vocational College,Hefei 230009,China

2.Optimization and Intelligent Decision Making,Ministry of Education Key Laboratory of Process,Hefei University of Technology,Hefei 230009,China

1 引言

云計算以承諾向用戶提供具有高可擴展性、靈活性和成本效益的計算、存儲及其他各類應用服務而受到業(yè)界的廣泛關注。為了實現(xiàn)這些承諾，云計算服務提供商不僅需要通過構建完善的基礎設施、采取迅速有效的管理機制對資源進行規(guī)劃以提供高質(zhì)量服務來滿足用戶需求，同時還需要控制成本、提高利潤來謀求自身的長期發(fā)展，而云計算數(shù)據(jù)中心能源消耗所產(chǎn)生的費用是運營成本中一個主要的構成部分。

云計算環(huán)境下的資源負荷預測是實現(xiàn)云計算海量異構資源有效管理以應對動態(tài)且不確定的多元化用戶需求，保證及時、可靠地將各種資源提供給使用者的同時降低運營商、服務供應商自身的成本，以及減少數(shù)據(jù)中心能源消耗過程中重要的一步[1]。利用歷史數(shù)據(jù)對未來一段時間內(nèi)資源負荷進行準確的預測，就可以運用服務器運行機制（例如服務器開/關、休眠/掛起）、虛擬化技術（例如虛擬機遷移）和相應的負載均衡策略來實現(xiàn)整個云計算系統(tǒng)資源的合理配置，并為云計算運營商和服務供應商提供有力的決策支持。在先前的云計算資源負荷預測研究中，相關學者使用了如自回歸模型（Auto-Regression，AR）[2]、模式匹配[3]、神經(jīng)網(wǎng)絡[4-5]、貝葉斯模型[6]等預測方法。然而，云計算系統(tǒng)是受多種因素影響的復雜非線性系統(tǒng)，其資源負荷也相應地表現(xiàn)出強烈的動態(tài)性，以上文獻中所提的預測方法都只是簡單地使用了傳統(tǒng)預測模型展開實驗，并未在對云計算資源負荷特征分析的基礎上進行對應的預測模型選擇和構建；并且單一的預測模型難以準確描述云計算資源負荷復雜的內(nèi)部變化規(guī)律，不能及時調(diào)整模型參數(shù)以反映外部環(huán)境因素發(fā)生的變化。文獻[7-9]分析了云計算資源負荷的特征，并在資源使用率、任務執(zhí)行時間、資源請求內(nèi)容等幾個方面與網(wǎng)格計算（Grid Computing）及其他高性能計算（High Performance Computing，HPC）系統(tǒng)進行了全面地比較。本文在這些研究的基礎上總結了云計算資源負荷的幾個主要特點：（1）大部分云計算中的任務具有較短的執(zhí)行時間。75%至80%的任務執(zhí)行時間在3分鐘左右；（2）云計算中的每個任務對資源的需求是少量的。大部分單個任務使用的資源約占一臺機器總資源量的2.5%。（3）相比于網(wǎng)格計算和其他HPC系統(tǒng)，云計算資源負荷表現(xiàn)出較高的噪聲，具有短期內(nèi)頻繁變化的特點。以上這些云計算資源負荷特點決定了其預測模型需要有較強的非線性擬合能力和自適應的模型參數(shù)調(diào)整能力來不斷適應負荷的動態(tài)性。

基于以上論述，本文將重點放于云計算資源負荷的短期預測研究中，短期負荷要求模型能夠盡可能使用較少的數(shù)據(jù)量、較短的預測時間去獲得準確的預測結果，從而能夠及時地為云計算的資源合理配置和調(diào)度提供可靠的決策支持，目的是為了能夠更有效地對云計算資源進行實時控制和管理，保障云計算系統(tǒng)的穩(wěn)定運行及其資源的高效供應，保證對云計算用戶提供可靠的服務。本文結合云計算資源負荷特點，闡述了GM（1，1）灰色模型在預測性能上的優(yōu)劣，提出基于多項式回歸模型、馬爾科夫鏈和布谷鳥搜索算法多步優(yōu)化的GM（1，1）預測模型，并將該模型用于云計算環(huán)境下資源負荷的短期預測應用中去，也是對GM（1，1）灰色模型的應用范圍作進一步的推廣。實驗結果表明，相比于其他傳統(tǒng)時間序列預測模型，本文所建模型具有更高的預測精度，體現(xiàn)出良好的預測性能，適合對具有較強動態(tài)性和非線性的云計算資源負荷進行短期預測。

2 基于多步優(yōu)化的GM（1，1）預測模型

自20世紀80年代我國學者鄧聚龍教授[10]創(chuàng)立灰色系統(tǒng)理論以來，灰色系統(tǒng)預測方法得到了國內(nèi)外學者的廣泛關注。其中GM（1，1）模型因其計算簡便、應用廣泛而在灰色預測中占有重要地位，是運用最早也是迄今為止應用最為廣泛的灰色模型，它以部分信息已知、部分信息未知的不確定性系統(tǒng)為研究對象，通過對已知信息的生成、開發(fā)，提取有價值的信息，實現(xiàn)對系統(tǒng)運行行為、演化規(guī)律的正確描述和有效監(jiān)控。其建模不依賴于原始數(shù)據(jù)的分布信息，而是運用累加生成的方法使得序列呈現(xiàn)出整體的灰指數(shù)規(guī)律，在此基礎上構建灰色微分方程并求解?；疑Ｐ筒恍枰髽颖緮?shù)據(jù)就能建模預測，且建模過程簡單、算法復雜度低，并被證明在短期預測中具有獨特的優(yōu)勢[11]。因而，GM（1，1）模型被廣泛地用于國民經(jīng)濟的各個領域[12-14]。但是，和其他預測方法一樣，GM（1，1）模型也存在一定的局限性，它對非負光滑單調(diào)序列的預測精度較高，而對非線性動態(tài)振蕩序列的預測效果并不理想[15]。因此，為了GM（1，1）模型能更好地應對云計算資源負荷時間序列的預測問題，本文將在闡述GM（1，1）預測模型建模機理的基礎上，構建基于多步優(yōu)化的GM（1，1）灰色預測模型。

2.1 GM（1，1）灰色模型介紹

GM（1，1）灰色預測模型的建模機理如下：設原始序列 為，其 中，。對原始序列進行一次累加得到一組新序列，其中模型的白化微分方程式為：

GM（1，1）模型的差分形式（灰微分方程）為：

從而得出灰色預測公式為：

2.2 P-GM（1，1）模型

其中 βi(i=0，1，2，3)為多項式系數(shù)，可由最小二乘法計算出各系數(shù)值：

其中，

在確定各系數(shù)值后，就可用所建的P-GM（1，1）模型計算得到一組新的預測序列來代替原有的預測序列，并且該組新預測序列會比GM（1，1）預測得到的值更接近實際值。

2.3 MP-GM（1，1）模型

經(jīng)過三次多項式回歸優(yōu)化后的GM（1，1）模型P-GM（1，1）在預測精度上有了一定的提高，但與實際值依然存在一定的誤差，從而形成一個殘差序列。因此，在P-GM（1，1）模型擬合結果的基礎上，本文利用適合于預測具有較強隨機性和波動性數(shù)據(jù)的馬爾科夫鏈（Markov chain）對P-GM（1，1）模型進行再次改進以進一步提升本文所建模型對于動態(tài)云計算負荷時間序列的擬合能力，構建MP-GM（1，1）模型，再次提高云計算資源負荷的預測精度。運用馬爾科夫預測法進行預測，主要工作原理是利用初始狀態(tài)的概率向量和狀態(tài)轉(zhuǎn)移矩陣來推測預測對象未來某一時間所處的狀態(tài)。由實際序列及P-GM（1，1）擬合結果可以得到一組殘差序列e(i)。其中，

根據(jù)殘差序列值e(i)的最大、最小值，將殘差序列分為S種狀態(tài)，每種狀態(tài)代表相應的誤差區(qū)間（每個區(qū)間的誤差長度相同），這樣就可以獲得一個S×S的馬爾科夫狀態(tài)轉(zhuǎn)移概率矩陣，而每個預測誤差都可定位在相應的狀態(tài)中。用表示預測對象從狀態(tài)i經(jīng)過m步轉(zhuǎn)移至狀態(tài) j的概率，則m步轉(zhuǎn)移概率為：

用as(t)表示第t個時期預測對象處于狀態(tài)s的概率，則{as(t)，s=1，2，…，S}稱為第 t個時期的狀態(tài)轉(zhuǎn)移向量。設初始的狀態(tài)轉(zhuǎn)移概率向量為as(0)，利用初始的狀態(tài)轉(zhuǎn)移概率向量as(0)和一步狀態(tài)轉(zhuǎn)移矩陣P(1)，可以求出預測對象在任一時間處于任一狀態(tài)的概率向量。從而得到基于馬爾科夫鏈優(yōu)化的P-GM（1，1）預測模型：

其中，as(t)=[a1(t)，a2(t)，…，as(t)]=as(t-1)P(1)，為處于特定誤差區(qū)間范圍內(nèi)的一個灰數(shù)，即，ls和us分別為狀態(tài)s所對應誤差區(qū)間的下限和上限。

2.4 CMP-GM（1，1）模型

在等式（12）中，若要獲得基于MP-GM（1，1）模型的預測結果，就需要確定灰數(shù)的值，即需要將灰數(shù)白化。根據(jù)文獻[14]所述，灰數(shù)的白化方法為：

其中λs∈[0，1]。從而可將等式（12）改寫為：

由等式（14）可知，只要確定向量 [λ1，λ2，…，λS]的值，就可以利用MP-GM（1，1）模型來進行云計算資源負荷短期預測。因此，本文利用布谷鳥搜索算法（Cuckoo Search，CS）來確定向量 [λ1，λ2，…，λS]的最優(yōu)值，提出基于布谷鳥搜索算法的MP-GM（1，1）預測模型—CMPGM（1，1）預測模型。接下來首先介紹布谷鳥搜索算法的基本原理與算法流程。

2.4.1 布谷鳥搜索算法

2009年，Yang和Deb模擬布谷鳥的尋窩產(chǎn)卵行為，提出一種新的智能優(yōu)化算法——布谷鳥搜索算法[16]。這種算法主要基于布谷鳥的巢寄生繁殖機理和萊維飛行（Levy flights）搜索原理兩個方面，它模擬了布谷鳥尋找鳥窩的隨機搜索方式，并模擬出布谷鳥的卵被鳥窩主人發(fā)現(xiàn)后的進一步隨機搜索過程[17]。在文獻[18]中，將布谷鳥搜索算法與粒子群算法、差分進化算法和人工蜂群算法進行了全面的比較，論證了布谷鳥搜索算法在獲取全局優(yōu)化值方面具有優(yōu)良的性能。把布谷鳥尋窩的方式形成理論，需假定以下3個理想狀態(tài)：（1）布谷鳥一次只產(chǎn)一個卵，并隨機選擇鳥窩來孵化它；（2）在隨機選擇的一組鳥窩中，最好的鳥窩將會被保留到下一代；（3）可利用的鳥窩數(shù)量是固定的，一個鳥窩的主人能發(fā)現(xiàn)一個外來鳥蛋的概率為 pα∈[0，1]。在這三個理想狀態(tài)下，布谷鳥算法的基本步驟為：

步驟1 隨機產(chǎn)生 S 維向量λ=(λ1，λ2，…，λS)，設定目標函數(shù) f(E)，生成 n個鳥窩位置λi（i=1，2，…，n），設置算法參數(shù)。

步驟2計算每個鳥窩的目標函數(shù)值，并記錄當前的最優(yōu)解。

步驟3保留上代最優(yōu)鳥窩位置，并按位置更新公式對其他鳥窩位置進行更新。其中位置更新方式遵循萊維飛行，公式為：

其中，α為步長控制量，α＞0;⊙為點對點乘法；Levy(ε)為隨機搜索路徑，服從Levy分布：

步驟4產(chǎn)生服從均勻分布的隨機數(shù)r∈[0，1]，與布谷鳥的卵被鳥窩主人發(fā)現(xiàn)的概率 pα對比，若 r＞pα，則對進行隨機改變，反之不變。再對改變后的鳥窩進行測試，與上一步得到的一組鳥窩位置比較取對應測試值較好的鳥窩位置，并選出當代的全局最優(yōu)位置。

步驟5判斷是否滿足結束要求。若滿足，輸出結果；若未滿足，則返回步驟2。

2.4.2 基于CS算法優(yōu)化的MP-GM（1，1）模型

在闡述了CS算法基本原理與算法流程的基礎上，針對本文云計算資源負荷短期預測的實際應用情況，構建基于CS算法優(yōu)化的MP-GM（1，1）模型—CMP-GM（1，1）預測模型，即通過CS算法不斷搜索最優(yōu)的參數(shù)設置來使得本文所提模型對動態(tài)的云計算負荷具有良好的自適應能力，下面給出算法流程。

步驟2 利用布谷鳥搜索算法更新向量[λ1,λ2,…，λS]的值，使得目標函數(shù) f(E)不斷逼近其全局最小值。

步驟3檢測算法停止條件，若不滿足，返回步驟2；若滿足，則輸出最優(yōu)的λs值，s=1，2，…，S 。

步驟4 運用等式（14），計算出基于CMP-GM（1，1）模型的最優(yōu)云計算資源負荷短期預測序列。

在上文論述了基于布谷鳥搜索優(yōu)化的MP-GM（1，1）算法流程的基礎上，下面給出本文所建的基于多步優(yōu)化GM（1，1）灰色預測模型CMP-GM（1，1）算法的偽代碼：

至此，基于多步優(yōu)化的GM（1，1）灰色預測模型CMP-GM（1，1）已構建完畢。

3 實驗及結果分析

本文所用實驗數(shù)據(jù)來自NASA和Clarknet[19]，該數(shù)據(jù)詳細記錄了每秒鐘兩個數(shù)據(jù)中心接收到的服務請求內(nèi)容，其資源負荷如引言中所述具有很強的動態(tài)非線性性，在[5，20，21]等文獻中已被多次用于云計算負荷預測及其性能分析研究。在云計算實際的資源管理過程中，每5至10分鐘會實施一次資源重新調(diào)度和配置的過程[4，22]。因此，本文中將對兩個數(shù)據(jù)中心提取的數(shù)據(jù)以10分鐘為最小單位進行統(tǒng)計，即每天記錄的數(shù)據(jù)點為144個，以此獲得相應的歷史資源負荷時間序列數(shù)據(jù)，并利用前三天的資源負荷數(shù)據(jù)對未來六小時（36個數(shù)據(jù)點）的云計算資源負荷進行短期預測，使預測結果能夠為云計算資源實現(xiàn)有效的實時配置和調(diào)度起到?jīng)Q策支持作用。為了對所建模型在預測性能進行客觀的評價和比較，本文選擇以絕對平均百分比誤差（AMPE）、均方根誤差（RMSE）和平均絕對誤差（MAE）這三個指標作為衡量預測性能是否優(yōu)良的評價指標。它們的計算公式為：

在實驗過程中，首先利用GM（1，1）模型對歷史數(shù)據(jù)進行第一步擬合，然后再通過P-GM（1，1）模型對獲得的數(shù)據(jù)擬合結果進行優(yōu)化，結果如圖1所示。

圖1（a） 基于P-GM(1,1)模型的NASA數(shù)據(jù)擬合結果

圖1（b） 基于P-GM（1，1）模型的Clarknet數(shù)據(jù)擬合結果

由圖1可以看出，云計算環(huán)境下的資源負荷時間序列具有極強的動態(tài)性，雖然P-GM（1，1）模型能夠擬合出數(shù)據(jù)整體的發(fā)展趨勢，但對于單個數(shù)據(jù)點的擬合結果并不是很理想。因而，在獲得P-GM（1，1）模型擬合結果的基礎上，下一步將結合馬爾科夫鏈來對P-GM（1，1）模型的擬合能力進行進一步提升。根據(jù)P-GM（1，1）模型的擬合誤差的最大值（Maximum error）和最小值（Minimum error），將誤差狀態(tài)分為五個狀態(tài)，每個狀態(tài)的誤差區(qū)間占區(qū)間[Minimum error，Maximum error]的 20%。該五個狀態(tài)所對應的誤差區(qū)間如下所示：

在確定了各個狀態(tài)所對應的誤差區(qū)間后，就可根據(jù)公式（10）分別計算獲得兩組數(shù)據(jù)的馬爾科夫一步狀態(tài)轉(zhuǎn)移概率矩陣和：

求得最優(yōu)的λs值后，運用公式（14）分別計算出基于CMP-GM（1，1）模型的兩組數(shù)據(jù)預測值，結果如圖2所示。

為了驗證所提CMP-GM（1，1）預測模型的有效性，本文選取GM（1，1）、自回歸移動平均（Auto Regressive moving average，ARMA）、BP神經(jīng)網(wǎng)絡及指數(shù)平滑（Exponential Smoothing，ES）四個模型作為對比，并且使各個模型在該實驗數(shù)據(jù)環(huán)境下預測性能表現(xiàn)最優(yōu)的模型參數(shù)設置。其中ARMA模型的自回歸項數(shù) p和模型的移動平均項數(shù)q分別設為 p=2和q=1；BP神經(jīng)網(wǎng)絡的輸入層、隱含層和輸出層神經(jīng)元的最優(yōu)個數(shù)設置為36∶15∶36；指數(shù)平滑采用二次平滑，選取前12個點的平均值作為平滑初值，平滑參數(shù)α經(jīng)過識別、比較后，確定為 α=0.36，此時方差最??；CMP-GM（1，1）模型中布谷鳥算法的終止條件為最大循環(huán)次數(shù)200。圖3給出了CMP-GM（1，1）模型與各模型預測結果的相對誤差比較結果。表1給出了CMP-GM（1，1）模型與各預測模型的預測模型綜合比較結果。

圖2（a） 基于CMP-GM（1，1）模型的NASA數(shù)據(jù)預測結果

圖2（b） 基于CMP-GM（1，1）模型的Clarknet數(shù)據(jù)預測結果

圖3 各模型預測結果的相對誤差比較

表1 各模型的預測結果比較

從預測結果比較中可以看出，本文所提的基于多步優(yōu)化的GM（1，1）模型CMP-GM（1，1）預測模型的預測值與實際值在整體上最為貼近。對于未經(jīng)改進的GM（1，1）模型，CMP-GM（1，1）模型的預測誤差只有其20%～30%，證明了本文所建的多步優(yōu)化模型是有效的，能明顯提升GM（1，1）模型對于動態(tài)、非線性數(shù)據(jù)的預測能力。而相比于ARMA、BP神經(jīng)網(wǎng)絡和ES等在先前云計算資源負荷預測中被用到的模型，CMP-GM（1，1）模型也在預測精度上體現(xiàn)出了一定的優(yōu)勢。綜上所述，CMP-GM（1，1）模型不僅在直觀上反映出該模型良好的預測性能，而且在各評價指標上也體現(xiàn)出了優(yōu)勢，對具有較強非線性性和動態(tài)性的云計算短期資源負荷時間序列展現(xiàn)了優(yōu)良的預測性能。

4 結論

本文首先介紹了云計算資源負荷特征，論述了資源負荷預測在實現(xiàn)云計算資源高效管理中的作用，并強調(diào)了資源負荷短期預測在實現(xiàn)對云系統(tǒng)實時控制和使其穩(wěn)定運行中的效用。繼而闡述了GM（1，1）灰色模型在預測性能上的優(yōu)劣，提出基于多項式回歸模型、馬爾科夫鏈和布谷鳥搜索算法多步優(yōu)化的GM（1，1）預測模型，并將該模型用于云計算環(huán)境下資源負荷的短期預測應用中去。實驗結果表明，相比于其他傳統(tǒng)時間序列預測模型，本文所建模型具有更高的預測精度，體現(xiàn)出良好的預測性能，適合對具有較強動態(tài)性和非線性性的云計算資源負荷進行短期預測。

[1]Ardagna D.Dual time-scale distributed capacity allocation and load redirect algorithms for cloud systems[J].Journal of Parallel and Distributed Computing，2012，72（6）：796-808.

[2]Ching C T M，Dusit N，Tham C K.Evolutionary optimal virtual machine placement and demand forecaster for cloud computing[C]//2011 International Conference on Advanced Information Networking and Applications，2011：348-355.

[3]Caron E，Desprez F，Muresan A.Forecasting for grid and cloud computing on-demand resources based on pattern matching[C]//2nd IEEE International Conference on Cloud Computing Technology and Science，2010：456-463.

[4]Islam S，Keung J，Lee K，et al.Empirical prediction models for adaptive resource provisioning in the cloud[J].Future Generation Computer Systems，2011，28（1）：155-162.

[5]Duy T V T，Sato Y，Inoguchi Y.Performance evaluation of a green scheduling algorithm for energy savings in cloud computing[C]//International Symposium on Parallel Distributed Processing Workshops and Phd Forum IPDPSW，2010：1-8.

[6]Di S，Kondo D，Cirne W.Host load prediction in a Google compute cloud with a Bayesian model[C]//Proceedings oftheInternationalConferenceon High Performance Computing，Networking，Storage and Analysis.[S.l.]：IEEE Computer Society Press，2012：1-11.

[7]Mishra A K.Towards characterizing cloud backend workloads：insights from google compute clusters[J].ACM SIGMETRICS Performance Evaluation Review，2010，37（4）：34-41.

[8]Benson T，Akella A，Maltz D A.Network traffic characteristics of data centers in the wild[C]//Proceedings of the 10th ACM SIGCOMM Conference on Internet Mea-Surement.[S.l.]：ACM，2010：267-280.

[9]Di S，Kondo D，Cirne W.Characterization and comparison of cloud versus grid workloads[C]//International Conference on Cluster Computing（CLUSTER）.[S.l.]：IEEE，2012：230-238.

[10]鄧聚龍.灰理論基礎[M].武漢：華中科技大學出版社，2002.

[11]王正新，黨耀國，練鄭偉.無偏GM（1，1）冪模型其及應用[J].中國管理科學，2011，19（4）：144-151.

[12]王宇熹，汪泓，肖峻.基于灰色GM（1，1）模型的上海城鎮(zhèn)養(yǎng)老保險人口分布預測[J].系統(tǒng)工程理論與實踐，2010（12）：2244-2253.

[13]Li G D.The hybrid grey-based model for cumulative curve prediction in manufacturing system[J].The International Journal of Advanced Manufacturing Technology，2010，47（1/4）：337-349.

[14]王曉佳，楊善林，徐達宇.基于改進粒子群算法的數(shù)據(jù)預測挖掘應用研究[J].情報學報，2011，30（8）：840-845.

[15]錢吳永，黨耀國.基于振蕩序列的GM（1，1）模型[J].系統(tǒng)工程理論與實踐，2009，29（3）：149-154.

[16]Yang X S，Deb S.Cuckoo search via Lévy flights[C]//World Congress on Nature&Biologically Inspired Computing（NaBIC 2009）.[S.l.]：IEEE，2009：210-214.

[17]李煜，馬良.新型元啟發(fā)式布谷鳥搜索算法[J].系統(tǒng)工程，2012，30（8）：64-69.

[18]Civicioglu P，Besdok E.A conceptual comparison of the Cuckoo-search，particle swarm optimization，differential evolution and artificial bee colony algorithms[J].Artificial Intelligence Review，2013，39（4）：1-32.

[19]Traces in the Internet Traffic Archive[EB/OL].[2013-06-20].http：//ita.ee.lbl.gov/html/traces.html.

[20]Mehta A.Envergy conservation in cloud infrastructures[C]//5th Annual IEEE International Systems Conference，2011：456-460.

[21]Prevost J J.Prediction of cloud data center networks loads using stochastic and neural models[C]//6th International Conference on System of Systems Engineering，2011：27-30.

[22]Ardagna D.Dual time-scale distributed capacity allocation and load redirect algorithms for cloud systems[J].Journal of Parallel and Distributed Computing，2012，72（6）：796-808.