基于烏鴉搜索和蜻蜓算法融合與支持向量回歸預測的能效虛擬機遷移

2022-08-10 08:12:02許彪高坤

計算機應用與軟件 2022年7期

許彪高坤

1(湖南科技職業學院人工智能學院湖南長沙 410004) 2(湖南第一師范學院信息科學與工程學院湖南長沙 410205)

0 引言

數字時代的云計算服務正在逐年穩步增加。目前的云計算服務形式包括平臺即服務PaaS、軟件即服務SaaS和基礎設施即服務IaaS，它們以按需即付即用的方式提供給終端用戶[1]。云數據中心基于終端用戶的需求進行建立，數據中心充分利用各種存儲元素、處理器和網絡交換機為用戶提供服務[2]。目前，來自用戶的服務需求的增加已經轉向虛擬機方向[3]。需要注意的一點是，目前美國境內的云數據中心的能源消耗已經達到30億kWh[4-5]。數據中心的能耗在未來幾年仍會以每年10%的速度增加，這不僅產生了使得全球氣候變暖的溫室氣體，還會增加數據中心的運營成本[6-7]。

為了實現云系統高能效的負載均衡，本文將設計一種基于能效的虛擬機遷移算法。算法的主要依據是利用蜻蜓算法和烏鴉算法的融合優化和支持向量回歸SVR模型設計高效的虛擬機遷移決策機制。算法主要考慮兩個主要問題：(1) 系統的負載預測問題；(2) 最優化的虛擬機部署問題。基于蜻蜓算法和烏鴉算法的融合算法用于實現最優的虛擬機遷移決策，支持向量回歸模型則用于預測虛擬機的負載狀況和資源利用狀況。算法的主要過程由三個步驟構成。首先，在考慮不同資源參數類型的情況下，需要計算主機的資源利用率，包括CPU數量、內存、指令執行性能MIPS和虛擬機的負載，這些參數直接決定了資源利用率。其次，利用支持向量回歸SVR模型預測每個主機的資源利用率和負載，預測資源利用率和未來主機負載之后，即需要通過負載均衡算法作出虛擬機遷移決策。此時，虛擬機在超載主機向其他主機間的遷移是一個優化問題，該問題最后通過提出的融合烏鴉和蜻蜓算法的能效虛擬機遷移算法得到。

1 相關研究分析

本節對有關能效的虛擬機部署與遷移問題進行概述性研究，重點分析相關算法的思路和優缺點，最后給出本文算法解決的主要問題。文獻[8]為了建立虛擬機遷移模型，提出了時間感知的需求模型和多組件構成的功耗模型，可以通過擁塞控制方法最小化任務的執行代價，同時降低總體執行能耗。然而，該模型缺乏導致確定調度時間窗口的靈活起始時間。文獻[9]通過修正遺傳算法GA提出了一種混合遺傳算法HGA實現云數據中心的能效虛擬機部署。HGA可以提供更好的開發能力，并改進收斂性能，但是得到的虛擬機部署方案會導致網絡負載的劇增。文獻[10]提出了一種虛擬機分配的優化方法，該方法可以確保多維度資源下無死鎖的資源分配，但在沒有負載均衡策略時其網絡負載依然過高。文獻[11]提出了一種基于預測模型的虛擬機合并方法，可以預測云系統的未知負載，基于預測負載和資源的未來需求可以將虛擬機部署至最優的目標位置。即使該方法有效可行，但其擴展性和網絡資源的利用率方面顯得不足。文獻[12]基于蜂群算法FA設計了能效虛擬機遷移算法FFO-EVMM，該算法集中于虛擬機的動態遷移決策并可降低總體執行功耗。但是，在復雜云環境中算法的魯棒性沒有得到討論。文獻[13]為了實現虛擬機遷移提出了基于虛擬機合并的蟻群算法ACS-VMC。算法通過增加虛擬機遷移次數最小化服務等級協議SLA的違例。但是文中沒有對算法的性能做出量化評估。文獻[14]為了實現高能效虛擬機遷移在混合云環境中，設計了基于QoS感知的部署算法，可同步實現功耗和SLA違例的降低，但算法實施中在不同主機間的虛擬機遷移過程忽略了網絡開銷的優化。文獻[15]結合模糊邏輯策略提出了能效感知的虛擬機遷移算法，算法利用虛擬機部署和超低載主機的識別將虛擬機負載進行了有效合并，通過維持當前SLA實現了功耗的最小化。

實現能效的虛擬機遷移模型的最優化問題所面臨的主要問題包括：

1) 將云系統的空閑主機轉換為節能模式可以改善虛擬機的合并過程，但這會導致超載主機和低載主機的不可靠特征，即執行虛擬機動態遷移也會影響與虛擬機相關的任務執行。

2) 云系統中執行虛擬機遷移，需要考慮到每個虛擬機的資源利用，而為了實現負載均衡，最佳虛擬機的選擇必須在遷移過程中得到優化決策。

3) 如文獻[9]，基于虛擬機遷移的負載均衡策略忽略了云系統的能耗問題，而這是云計算系統效率的一個重要衡量指標。

4) 虛擬機遷移必須全局考慮，它會影響任務的服務質量，可能造成服務等級協議的違例。在超載主機與低載主機間進行虛擬機遷移不應該違背服務等級協議SLA[15]。

針對以上問題，本文設計基于能效的虛擬機遷移算法。算法的出發點是利用蜻蜓算法和烏鴉算法的融合優化和支持向量回歸模型設計虛擬機遷移決策機制，利用支持向量回歸模型預測虛擬機的負載狀況和資源利用狀況，利用蜻蜓算法和烏鴉算法的融合實現最優的虛擬機遷移與部署。算法的主要技術優勢在于：首先，算法綜合考慮不同資源類型的負載問題，包括CPU數量、內存、指令執行性能MIPS和網絡帶寬的負載，這些參數直接決定了資源利用率；其次，算法利用支持向量回歸模型實現了主機資源利用率和負載的預測，對于超載問題可以通過負載均衡模型做出虛擬機遷移；最后，融合烏鴉和蜻蜓算法的能效虛擬機遷移則有效解決了前一步驟中的主機超載問題，實現了更均衡和高能效的虛擬機部署方案。

2 云計算中的虛擬機遷移模型

本節建立實現負載均衡時相關虛擬機遷移的基本云計算模型。如圖1所示為本文所討論的虛擬機遷移模型與框架。云計算模型由解決云用戶需求的不同類型的主機PM構成，主機為了動態地處理用戶任務，可部署虛擬機VM集合。云系統中的虛擬機可以動態創建以減少系統負載的瓶頸問題，同時通過虛擬化操作可以改進系統處理速率。用戶請求以任務形式進入系統，每個用戶任務可根據輪轉方式分配在一個虛擬機上執行。主機控制其虛擬機集合，而云系統可以實現監測系統中主機上的負載。若主機負載超過設定的閾值，即認為該主機為超載主機，負載均衡模塊會選擇遷移該主機上的虛擬機至其他低載的主機上，從而均衡整個系統的負載，實現負載均衡。

圖1 云系統中的虛擬機遷移模型

(1)

3 融合烏鴉搜索算法和蜻蜓算法的能效虛擬機遷移

圖2所示為本文提出的融合烏鴉算法和蜻蜓算法的能效虛擬機遷移算法的整體框架。虛擬機遷移模型利用負載均衡策略持續檢測主機的負載狀況。若主機負載超過用戶設置的閾值，模型將選擇最佳的虛擬機在超載主機與低載主機時進行遷移，從而平衡負載狀況。圖2中的虛擬機遷移模型假設主機PM2是超載主機，因此，需要從中選擇一個最佳的虛擬機遷移至低載的主機PMM上。本文算法模型中，利用支持向量回歸SVR模型進行主機未來負載的預測，并通過負載均衡思想作出虛擬機遷移決策。

圖2 算法整體框架

3.1 虛擬機遷移模型

本文在虛擬機遷移模型中考慮了系統負載、能量和遷移代價三種因素，虛擬機對于主機資源占用的屬性包括CPU數量、內存、網絡帶寬和MIPS數量四種，這些屬性均會影響系統負載狀況。因此，算法需要尋找最佳的遷移虛擬機進行重新部署，從而優化負載、能量、遷移代價。以下對這三種模型分別進行說明與定義。

3.1.1負載模型

系統的負載直接決定于處理來自用戶的任務時虛擬機占用的資源情況，虛擬機利用的資源主要包括CPU、內存、網絡帶寬、MIPS，則可將第n個虛擬機的負載定義為：

(2)

(3)

式中：QA(a)、QB(a)、QC(a)和QD(a)分別表示時間周期a時虛擬機所占用的CPU、內存、網絡帶寬和MIPS資源；R表示資源占用量，可定義為：

R=QA+QB+QC+QD

(4)

資源占用QA(a)、QB(a)、QC(a)和QD(a)可以表示為可變時間周期變量a內的資源利用率，定義為：

(5)

(6)

虛擬機n在內存資源上的資源占用可定義為：

(7)

(8)

同樣的道理，虛擬機n在網絡帶寬資源上的資源占用可定義為：

(9)

(10)

虛擬機n在MIPS資源上的資源占用可定義為：

(11)

式中：a-1和a-2代表過去的時間周期間隔內的資源占用。

(12)

主機包含一個虛擬機集合，因此，主機負載直接取決于資源占用和虛擬機負載。主機負載和主機的資源占用分別表示為：

(13)

(14)

(15)

(16)

3.1.2遷移代價模型

虛擬機的動態遷移允許虛擬機在不同主機之間進行轉移，雖然不存在暫停且只有較短停機時間，但動態遷移本身對于運行在虛擬機上的應用會在性能上帶來負面影響。而性能下降和停機時間均取決于應用執行過程中磁盤讀寫頁面數量。因此，虛擬機的遷移代價可以系統中發生的虛擬機移動次數進行衡量。初始情況下，可將云計算系統的遷移代價考慮為最高，值為1。將整體的虛擬機遷移代價定義為：

(17)

式中：J表示遷移常量；o表示虛擬機的移動次數；N表示虛擬機總量；M表示主機數量。

3.1.3能量模型

系統能耗取決于數據處理和遷移過程中每個虛擬機所利用的功耗，因此，云計算系統的能量直接決定于虛擬機上不同類型資源產生的功耗，而該功耗又由對應資源的負載和資源利用率決定。將云計算系統的能耗定義為：

(18)

式中：Ht表示系統中時間t時虛擬機相關網絡元素的功耗(本文考慮的元素包括CPU、內存、網絡帶寬和MIPS)。該功耗表示為：

(19)

3.2 基于支持向量回歸SVR的負載預測

虛擬機的負載在每個任務到達均可能出現變化，因此，有必要考慮虛擬機上的未來負載值從而選擇合適的虛擬機目標。本文采用一種基于支持向量回歸模型SVR的未來負載預測方法。SVR模型利用一個非線性函數集合用于將已知負載值映射為未知負載值。將主機的負載值作為回歸模型的輸入值，基于該值預測未來負載值。SVR模型需要的訓練集合定義為：

S={(u1,v1),(u2,v2),…,(uN,vN)}

(20)

式中：u屬于輸入集合U；v屬于輸出的預測集合V。模型輸入和輸出間的映射可形式化為以下的最優化問題：

(21)

式中：L表示輸出估算值的代價。最優化問題的約束條件為：

〈〈p,φ(un)〉+q〉-vn≤α+α+

(22)

vn-〈〈p,φ(un)〉+q〉≤α+α-

(23)

式中：α+和α-分別表示預定義的誤差和高維度特征集合G中的p值；φ表示分離超平面的符號函數。SVR利用回歸函數定義輸出估算值的上限和下限，其回歸函數定義為：

f(u)=〈p,φ(u)〉+q

(24)

此外，SVR模型利用拉格朗日對偶最大化問題進行估算值的預測，可將其表示為：

(25)

式中：βn表示拉格朗日乘子,W表示對偶函數。

以上定義的最大化問題的約束條件為：

對于拉格朗日對偶最大化問題的回歸估算可表示為：

(26)

3.3 負載預測算法

本節給出負載均衡算法，通過虛擬機遷移完成均衡的負載分配。算法的主要步驟如下：

步驟1初始化云計算系統，包括M個系統主機PM和N個虛擬機VM。

步驟2初始階段將主機的遷移代價設置為最大值，即遷移代價為1。

步驟3在時間周期t時，根據輪轉方法將到達的任務分配至虛擬機。

步驟5根據以下標準，選擇最佳的虛擬機(基于烏鴉搜索和蜻蜓優化算法的虛擬機最優部署算法中得到)在低載主機和超載主機間進行虛擬機遷移，并更新遷移代價：

(27)

步驟6尋找系統負載值Zt、能耗、資源利用率、系統的遷移代價。

步驟7重復步驟3-步驟6進行算法迭代，直到達到終止迭代條件h。

3.4 基于烏鴉搜索和蜻蜓優化算法的虛擬機最優部署算法

3.4.1解的編碼

考慮以下場景：主機PM1部署3個虛擬機，主機PM2部署2個虛擬機，到達的任務根據輪轉方式分配至每個虛擬機上執行。當主機PM1超載時，PM1上的虛擬機需要遷移至PM2上，算法的目標即是選擇最佳的虛擬機進行遷移。如圖3所示即為解的編碼方式。

圖3 解的編碼

3.4.2適應度評估

適應度函數用于選擇合適的虛擬機在低載主機和超載主機間遷移。本文定義了基于負載、能量和遷移代價的適應度函數，并以適應度值最大化為目標。具體將適應度函數定義為：

(28)

3.4.3算法具體過程

基于烏鴉搜索和蜻蜓優化算法的虛擬機最優部署的目標是選擇最佳的虛擬機進行遷移，具體過程如下：

步驟1種群初始化。首先，隨機初始化種群，生成種群規模為O的解集，并將其表示為：

I={I1,I2,…,Ii,…,IO}

(29)

式中：Ii表示第i個解，1≤i≤O。

步驟2適應度評估。根據式(28)的適應度函數，評估每個解的適應度。由于算法應用的適應度是最大化函數，包括最大適應度值的解被保留，可進入下一輪的迭代更新。

步驟3位置更新。蜻蜓算法DA考慮的種群元素為蜻蜓，在蜻蜓更新位置過程中，其具體屬性包括：分離、隊列、凝聚、食物源、敵人。DA的位置更新模式如下：

I(z+1)=I(z)+(b1X1+b2X2+

b3X3+b4X4+b5X5)+rΔI(z)

(30)

式中：X1、X2、X3、X4和X5分別表示以上5個屬性上解的位置；b1、b2、b3、b4和b5分別對應于5個屬性影響解的質量的權重；r表示解的慣性權重；ΔI(z)表示以上參數的位置變化。

烏鴉搜索算法CSA也是一種類似于DA的智能種群算法，其考慮的種群是烏鴉，每個解的更新取決于烏鴉的行為。CSA中位置更新方式為：

I(z+1)=I(z)+c·l(z)·(e(z)-I(z))

(31)

式中：c表示CSA更新的常量；l(z)表示迭代z時解的飛行長度因子；e(z)表示記憶。

由于DA和CSA兩種算法的位置更新等式均取決于種群特征和隨機初始化的種群位置，可將CSA的位置更新應用于DA的位置更新中。因此，可以尋找CSA中的l(z)值，并用于取代CSA中的位置更新值。修改式(31)得到l(z)的值，可將其表示為：

(32)

將式(32)代入式(31)中，算法得到的位置更新為：

(b1X1+b2X2+b3X3+b4X4+b5X5)+rΔI(z)

(33)

式(34)表示算法的位置更新的最終等式：

(34)

步驟4基于適應度尋找最優解。計算每個更新解的適應度，擁有最高適應度的解保留為算法的最優解。

步驟5算法終止。算法迭代結束，返回最優解。最大迭代限制定義為Y。

算法1給出了基于烏鴉搜索和蜻蜓優化算法的虛擬機最優部署算法的偽代碼，算法目標是在主機到達超載條件時尋找最佳的遷移虛擬機，遷移虛擬機需要從超載主機上遷移至低載主機上。最優化過程利用了基于負載、遷移代價和能耗的適應度來決策遷移虛擬機的選擇。

算法1基于烏鴉搜索和蜻蜓優化算法的虛擬機最優部署

輸入:population I

//輸入初始種群

輸出:best solution

//輸出虛擬機最優部署解

1.begin

2. randomly initialize the population of our algorithm

//對算法的種群進行隨機初始化，得到初始解

3.ifz≤Y

//當前迭代次數未超過最大迭代次數

4. find the fitness value of each solution based on Equ.(28)

//根據式(28)計算每個解的適應度

5. update the position of the solution based on Equ.(34)

//根據式(34)更新解的位置

6. recompute the fitness of each solution

//重新計算每個解的適應度值

7.endif

8.ifz=Y

//到達最大迭代次數

9.returnthe optimal solution

//返回最優部署解

10.endif

11.end

4 仿真實驗評測

4.1 實驗環境與評價指標

通過CloudSim[16]構造仿真環境對算法的可行性和有效性進行驗證，仿真實驗中建立5臺主機和20臺虛擬機的部署環境，用戶到達任務設置為100和500，以此度量算法在不同運行規模下的效率。算法的評價選擇為能耗、遷移代價和負載，三個指標分別由文中式(18)、式(17)和式(15)定義，優化目標是盡可能最小化三個指標值。

選擇的對比算法包括ACO算法[13]、LR算法[11]、MEGSA-VMM算法[17]和DA[18]。ACO算法執行虛擬機的分配是基于螞蟻的搜索行為，LR算法進行虛擬機合并則是通過系統中CPU和內存利用的預測方式實現，MEGSA-VMM算法則利用了指數遷移平均模型EWMA和引力搜索算法GSA進行虛擬機的優化部署過程，DA則是傳統的蜻蜓算法過程。

4.2 實驗結果分析

實驗1測試了100個用戶預測任務到達時算法的性能表現，結果如圖4所示。在首次算法迭代中，ACO、LR、MEGSA-VMM和DA得到的負載指標值分別為0.57、0.29、0.07和0.075。本文算法得到的負載指標值為0.07，是所有算法中最低的。同樣，在能耗方面，本文算法在首次迭代中得到了所有算法中最小的能耗值為0.016。而在遷移代價方面，本文算法同樣是最優的。換言之，負載、能耗、遷移代價三個指標值上，本文算法均得到了最小值，則適應度相應是所有算法中最大的，性能表現是最好的。原因在于：支持向量回歸機制可以利用非線性函數集合將所取樣的已知負載值映射為未知負載值，以主機負載值作為回歸模型的輸入值，可以較為準確地對主機的未來負載作出決策，預防出現熱點而導致性能下降，為優化虛擬機的具體部署打好了基礎。而融合入蜻蜓算法和烏鴉算法的虛擬機部署策略則在超載情況下的虛擬機遷移選擇上作出了最優決策，通過融合兩種算法在局部開發和全局搜索上的優勢可以使得虛擬機遷移在滿足負載均衡的同時得到最小化系統能耗。

(a) 負載狀況

圖5是將任務量增加至500時得到的算法性能表現。可以看出，增大任務規模并沒有對本文算法的執行效率產生反轉式影響，其在負載、能耗和遷移代價三個指標上依然穩定地優于另外四種對比算法，這說明所采用的支持向量回歸的負載預測機制和融合入蜻蜓算法和烏鴉算法的虛擬機部署策略依然是有效可行的，不僅可以對虛擬機遷移選擇做出正確決策，而且能夠使得虛擬機遷移在滿足負載均衡的同時最小化系統能耗，具有全局最優的執行效率。