基于熵權層次分析法的云平臺負載預測

王宗杰，郭 舉,2+

(1.北京科技大學 計算機與通信工程學院，北京 100083；2.北京起重運輸機械設計研究院 研發中心，北京 100007)

0 引 言

通過將底層硬件資源抽象為虛擬機節點[1]，云平臺可持續穩定地處理頻繁且種類多樣的用戶請求，但同時產生了計算節點間負載不均衡的問題。伴隨著云計算技術的迅猛發展[2]，出現了不同種類[3]的負載均衡技術[4]，緩解了云平臺負載不均衡的問題[5]。目前國內外關于云平臺的負載均衡技術理論研究和工程實踐產生了大量的研究成果。文獻[6]利用層次分析法分析4種影響云平臺負載的因素，計算云平臺的負載值。該負載值能較好反映當前平臺的資源利用情況，但使用單一的主觀賦權法所得權值具有主觀片面性。文獻[7]利用熵權法建立了對輸電方案的模糊評價模型，提取了評價指標的有效信息，但使用單一客觀賦權法所得結果不全面。文獻[8]利用指數平滑法預測了云平臺的負載值，預測值由歷史負載值加權平均得到。該模型系統資源占用小，但負載誤差會逐步增大，預測精度較低。文獻[9]提出基于支持向量機的云平臺資源分配策略，實現對云平臺資源的動態分配。文獻[10]利用哈希算法將數據存放到不同的數據節點上，實現各節點的負載均衡。文獻[11]提出了能量感知資源管理算法，動態調整虛擬機資源分配情況。針對前人研究存在的問題，提出了更全面的負載評估模型和負載預測算法，實驗結果驗證了其有效性。

1 云平臺負載評估預測方案

云平臺負載評估預測方案包含負載評估和負載預測兩部分內容。負載評估階段選取4種評價指標，利用層次分析法和熵權法計算出云平臺負載序列值。然后，采用差分整合移動平均自回歸模型 (autoregressive integrated moving average model，ARIMA)和BP(back propagation)模型和BP神經網絡分別處理負載序列的線性部分和非線性部分，最終得出云平臺負載預測值。

1.1 層次分析法

層次分析法(analytic hierarchy process,AHP)是對一些較為復雜模糊的問題作出決策的多準則決策分析方法[12]，主要目標是解決多目標的復雜問題，它本質上是一種建立在對問題定性和定量基礎上的決策分析方法。為了得到被評價屬性的權值，它采用決策者主觀經驗判斷各個屬性之間的相對重要程度，建立評價矩陣，隨后逐步計算得出各個屬性的權值，適用于一些定量方法難以應用的復雜問題。

本文采用AHP法賦權計算主觀權重，主要方法和步驟如下：

步驟1 構建遞階層次結構模型。

步驟2 根據各屬性指標的相對重要程度，建立判斷矩陣

其中，c、m、d、n依次代表計算資源、內存資源、硬盤資源、帶寬資源。Wij表示資源i對資源j的重要程度，其取值依照九分位比例標尺。判斷矩陣完成之后，需依照式(1)、式(2)對其進行完整性檢查

(1)

(2)

步驟3 計算權重向量

采用方根法計算權重向量。將判斷矩陣WA中的元素按照每行相乘得到新向量WT，再將該新向量的每個分量開n次方(此處n為4)得到向量WL，最后將所得向量WL進行歸一化處理即得權重向量W。

步驟4 一致性檢驗

表1 平均隨機一致性指標

步驟5 調整判斷矩陣

若判斷矩陣通過步驟4的一致性檢驗，則歸一化后的權重向量即是各因素的權重系數。否則需對判斷矩陣進行調整，直至滿足一致性檢驗。

1.2 熵權法

熵最早由香農引入信息論，目前已經在金融經濟、制造技術等眾多領域得到了眾多應用。一般來說，信息熵Ej越小的指標，其變異程度越大，包含的信息量也越多，對綜合評價的影響也越大，那么分配的權重也應該越大；反之，該指標分配的權重越小。熵權法(entropy wright method,EWM)的原始數據來源于評價過程中，這一方面可以充分利用歷史數據對權重的影響程度，但另一方面也造成熵權法在確定指標時會隨著樣本的變化而變化，對數據樣本具有依賴性，限制了對其的應用。

本文在建立評價模型時，采用熵權法獲得各指標的客觀權重，具體計算步驟如下：

步驟1 構建初始矩陣并進行標準化處理

對于給定的N個對象，M個指標P1,P2…PM， 其中Pi={p1,p2,…pN}， 構建初始矩陣X

對初始矩陣采用歸一法進行標準化處理，得新的矩陣Y，其中

(3)

步驟2 計算各指標的信息熵

由上面對信息熵的定義，可得一組數據的信息熵為

(4)

其中，pij由式(5)給出，若pij=0,則都定義

(5)

步驟3 計算各指標的權重

根據信息熵的計算公式，可計算出各個指標的信息熵為Ei，利用式(6)可計算出各個指標的權重

(6)

1.3 自回歸積分移動平均模型

基于時間序列的預測技術通過統計分析收集的歷史數據，獲得一般的事物變化趨勢，對數據進行不同程度的處理，減少外界因素對變化規律的影響，最終對事物的發生進行預測。ARIMA是一種較常用的基于時間序列的預測模型[13]。

本文利用ARIMA模型對ARMA(自回歸滑動平均模型)模型進一步優化，解決了ARMA只能分析平穩序列的問題。ARIMA實質是ARMA模型與查分運算的組合形式，首先通過一定階數的差分處理時間序列數據，使不平穩數據成為平穩數據，接下來就可以使用ARMA模型對差分后的數據進行擬合。ARIMA模型在時間序列分析方法中應用的比較廣泛，建模流程如圖1所示。

圖1 ARIMA建模流程

首先對時間序列數據進行平穩性檢測、白噪聲檢驗處理，其后通過自相關函數和偏相關函數PACF確立ARIMA模型的參數范圍，并通過數據擬合確定最終模型參數。最后使用ARIMA模型預測時間序列數據。

1.4 BP神經網絡

BP神經網絡是一種按照誤差逆向傳播算法訓練的多層前饋神經網絡，是目前被廣泛應用在預測領域的模型。BP神經網絡主要依靠自身的訓練，自主訓練某些數據規律，不需要提前給出輸入輸出之間的映射關系。在應用時，只需給出輸入值，即可給出最接近期望輸出值的預測結果。BP神經網絡實現預測的核心是BP算法，其思想利用梯度搜索技術和梯度下降法，最終獲得輸出值和實際值的誤差的均方差最小。BP神經網絡的拓撲結構如圖2所示。

圖2 BP神經網絡拓撲結構

BP神經網絡首先根據業務目標選取樣本數據。之后進行數據預處理操作。對于短期變化劇烈的數據不適合直接作為輸入數據。輸入數據序列越穩定均勻，對于建模預測就越有利。一般建立BP神經網絡之前，首先會對數據進行歸一化處理，得到平滑的數據序列作為網絡的輸入，歸一化處理后，一定程度上降低最終預測結果中的無效噪聲。

其次根據負載特點，設計網絡結構并給出網絡的相關參數，包括網絡層數、輸入輸出節點書、隱含層節點數、激活函數等。正確設計這些參數，對于預測效果至關重要。

模型建立完成之后，開始訓練數據樣本集。當網絡訓練的次數達到上限或輸出的數據誤差滿足要求時，輸出訓練好的模型并對負載值進行預測。其訓練過程如圖3所示。

圖3 BP神經網絡訓練過程

1.5 基于ARIMA-BP的云平臺負載預測模型

對于云平臺的負載值來說，它受到內部因素和外部因素的影響，因此云平臺的負載值中隱含了線性特征和非線性特征，是線性特征影響因素和非線性特征影響因素的綜合反映。

對于負載值的預測可以使用適應處理分析線性時間序列的模型和適應處理分析非線性時間序列的模型組成的組合模型對其分析處理。

本文使用線性擬合能力較好的ARIMA模型和非線性擬合能力較好的BP神經模型構成組合預測模型，對云平臺的負載值進行分析預測。ARIMA模型可以提取出云平臺負載值的線性特性，BP神經網絡可以提取出云平臺負載值的非線性特征，兩者結合構成的組合模型不僅彌補了只采用單一預測模型分析的不足之處，又能夠充分發揮各個預測模型的優勢之處。組合模型的整體流程如圖4所示。

圖4 基于ARIMA-BP的組合模型原理

2 實驗驗證

2.1 建立基于熵權層次分析法的動態評估模型

2.1.1 動態主觀權重

首先構建判斷矩陣，本文選取CPU、內存、磁盤、網絡4個因素作為評價指標，則判斷矩為4行4列的矩陣WA。該矩陣的取值根據當前時刻系統運行負載的變化情況和以往經驗。在判斷矩陣WA中，4列元素從左到右依次代表CPU、內存、外部磁盤、網絡帶寬4種影響云平臺負載變化的評價因素

為了下一步計算，需要對該判斷矩陣的列向量進行歸一化處理，之后得到新的矩陣WB

對WB按行求和，然后再進行歸一化處理，得到權重向量W，該權重向量的每行值對應CPU、內存、磁盤、網絡帶寬4個評價指標對應在該時刻的權重值

為了驗證該權重向量的有效性，需要進行一致性檢驗。按照前面章節所描述的步驟計算拉姆達的值為4.1441。即可得C.I.的值為0.048 06。查表可知R.I.的值取為0.9，則C.R.的值為0.0534，則C.R.<0.1，即權重向量W的值滿足一致性檢驗，每一行的值即為該時刻對應指標因素的權重值。

2.1.2 動態客觀權重

熵權法通過利用指標過去一段時間的變化值，計算該指標的權重，因此被稱為是一種客觀賦權法。熵權法通過利用指標過去一段時間的變化值，計算該指標的權重，因此被稱為是一種客觀賦權法。本文數據來源于yahoo webscope數據集，選取其中4個指標為列向量，過去20分鐘內的使用率作為歷史數據，構建初始數據表。對初始化表進行歸一化處理，之后按照公式計算歸一化后的數據表中數據，即得CPU、內存、磁盤、網絡帶寬得信息熵，見表2。

表2 指標信息熵

按照式(6)所示，即得在該時刻4個指標得權重值，結果值見表3。

表3 指標權重

2.1.3 組合評價模型

隨著時間的推移，用戶不同時刻會用不同的請求，導致云平臺的資源消耗處于一個動態變化的狀態，4個指標的權重是基于當前時刻各自的使用情況來確定，為了使得到的指標權重符合當前平臺的負載情況，則每當資源發生變化時都需要重新計算當前指標的權重值?？紤]云平臺負載的變化情況，本文采用層次分析法和熵權法計算出各個時刻評價指標的權重值后，將得出的主客觀權重值帶入拉格朗日乘子，得出各個時刻對應的CPU、內存、磁盤、網絡帶寬的實時權重。各指標的實時權重與對應的利用率的乘積即是當前時刻云平臺的負載值。按照以上步驟，即可得到某實驗對象云平臺的負載時間序列值，部分結果見表4，該負載值結合了各硬件資源的主客觀因素，能夠較好反映云平臺的實時負載情況。

表4 云平臺負載值

2.1.4 結果分析

本文將熵權層次法分別同單純使用熵權法、層次分析法和固定權重計算得出的負載值對比。采用固定權重的方法雖然考慮了不用資源對負載的影響情況，但其實質是將4種因素的指標和縮小至1/4，不能反映系統資源的真實使用情況。層次分析法反映了CPU是系統關鍵指標的主觀經驗，未充分體現其它3種指標的影響。熵權法計算得出的云平臺負載值較高，是由于云平臺的內存利用率一直處于較高狀態，但從計算機系統的角度來看，內存的使用情況并不能代表系統整體的負載。熵權層次分析法則考慮了CPU在系統運行過程中的關鍵地位的主管經驗，同時也客觀評估了4種指標的影響程度，計算得出的負載值能夠更好反映系統的整體運行狀態，較另外3種方法更加科學合理。4種負載評估方法對比如圖5所示。

圖5 4種負載評估方法對比

2.2 基于ARIMA-BP模型的云平臺負載預測

2.2.1 構建ARIMA模型

對云平臺負載進行平穩性處理和白噪聲檢驗，得到穩定的非白噪聲數據。根據平穩時間序列模型特征系數判斷ARIMA模型的參數，模型參數的確定主要通過觀察自相關函數圖和偏自相關函數圖。

如圖6所示，是負載數據的自相關(ACF)和偏自相關(PACF)函數圖，從圖中可以看出，隨著滯后期數的增加，時間序列的自相關系數從高值降為低值，逐漸趨向零，符合ACF拖尾的特點。同時，偏自相關系數也從高值降為低值，逐漸趨向0，符合PACF拖尾的特點；自相關(ACF)圖和偏自相關(PACF)圖都呈現出拖尾現象，可以初步判斷該時間序列可以使用ARMA(p,q) 模型。

圖6 自相關和偏自相關函數

在對序列進行差分處理，結果表明ARIMA(1,1,1) 模型的AIC、SC、HQ值為最小，此時可以選取p=1,q=1,d=1作為模型的參數值，即ARIMA(1,1,1)。 差分結果見表5。

表5 ARIMA模型對比

在使用ARIMA預測負載并計算出負載殘差后，利用BP神經網絡預測殘差值，其中輸入層節點個數為4，隱藏

層節點個數為3，輸出層節點個數為1，并設置訓練網絡的其它參數。最后利用ARIMA及保存的神經網絡對負載值進行預測。

2.2.2 結果分析

圖7是基于ARIMA模型的云平臺負載預測值和基于ARIMA-BP組合模型的云平臺負載預測值的對比圖，可以看到后者更加接近真實值。圖8是這兩種預測模型的誤差對比圖，同樣可以說明基于ARIMA-BP模型的預測值誤差較小，預測精度更高。

圖7 平臺負載預測對比

圖8 預測誤差對比

3 結束語

本文采用熵權法和層次分析法結合的方式建立云平臺負載評價模型，該模型采用4種元素加權的方式，評估云平臺的負載情況，避免了采用單一元素確定了評價云平臺負載的片面性。在選擇賦權法時，采用主客觀賦權法結合的方式，較使用一種賦權法更加全面合理。

基于ARIMA模型預測了云平臺負載數據序列的線性部分，其后采用基于BP神經網絡模型預測了云平臺負載值的非線性部分。最后將構建基于ARIMA-BP的組合模型，并使用該模型預測云平臺負載，所得預測值與期望值相比，滿足期望誤差，驗證了該模型在預測云平臺負載值的有效性。