基于優(yōu)化AHP的虛擬機部署與調度策略

羅 樹，沈記全

（河南理工大學 計算機科學與技術學院，河南 焦作454000）

0 引 言

為實現(xiàn)虛擬機的高效部署［1－5］，國內外研究者從不同的角度尋找虛擬機部署的最優(yōu)方案。Hirofuchi等通過虛擬機實時遷移方式實現(xiàn)IaaS數(shù)據(jù)中心的動態(tài)整合，在降低能耗的同時保持了任務的連續(xù)性，卻沒有形成具體的調度機制［6］；Goiri等提出了一種低功耗的虛擬機部署感知模型，有效降低了能源消耗，但沒有考慮數(shù)據(jù)中心的負載均衡［7］；Li等提出基于改進分組遺傳算法的虛擬機放置策略，有效地提高了虛擬機放置問題的求解速度，沒有針對動態(tài)負載情況進行研究［8］；Gao等采用蟻群算法進行虛擬機部署，提高了物理服務器的資源利用率，優(yōu)化了能耗問題，卻容易陷入局部最優(yōu)解［9］；Zhuang等提出了一種基于多屬性層次分析的虛擬機部署與調度策略，能夠實現(xiàn)對虛擬機部署與遷移最佳方案的選擇，但沒有考慮虛擬機之間的資源競爭問題［10］。

本文構建了一種基于層次分析 （analytic hierarchy process，AHP）優(yōu)化算法的虛擬機部署與調度策略。它首先通過物理服務器躲避機制對目標物理服務器進行初次篩選，然后采用層次分析模型根據(jù)用戶任務類型對虛擬機部署方案進行預測評估。實驗結果表明，該策略在實現(xiàn)物理服務器負載均衡的基礎上，有效提高了物理資源的利用率，并在資源優(yōu)化配置方面有較好的效果。

1 基于AHP的虛擬機選擇影響因素模型

層次分析法［11］（AHP）是一種針對多目標的層次權重決策分析方法，它將決策問題分解成不同的層次結構，并采用一定的標準對各層次影響因素進行客觀量化，較好地實現(xiàn)了定性與定量分析在各類多方案決策問題方面的廣泛應用［12］。運用AHP選擇虛擬機部署方案的步驟如下：

（1）構建各影響因素層次結構模型。本文層次結構模型主要由目標層、準則層及方案層構成。目標層是最佳虛擬機與目標物理服務器節(jié)點部署方案；根據(jù)用戶對資源的需求特征，虛擬機可分為計算型、存儲型、網(wǎng)絡型以及無特殊需求型，因此準則層以CPU 資源、內存資源及寬帶資源等作為影響因素；方案層是所有滿足要求的部署方案。

（2）構建各影響因素間的對比矩陣，利用虛擬機CPU資源、內存資源以及寬帶資源相對于目標物理服務器選擇的重要程度構建對比矩陣A，如式 （1）所示，并根據(jù)AHP的1～9標度賦值，見表1

在矩陣A 中資源影響因素CPU、內存、帶寬分別記為c、m、b，ai為準則層各影響因素對目標層物理服務器節(jié)點選擇的重要程度，Aij為準則層的第i類影響因素和第j類影響因素相比對于目標層物理服務器節(jié)點選擇的重要程度。

表1 1～9標度含義

（3）一致性檢驗，如果矩陣A 滿足 （2），則矩陣A 具有一致性

（4）權重向量計算，首先計算矩陣A 最大特征值λmax，然后根據(jù)式 （3）計算其特征向量N

對特征向量N 作歸一化處理即得到虛擬機所需資源的權重向量w，各分量體現(xiàn)了CPU、內存、寬帶資源對目標物理服務器節(jié)點選擇的影響權重

依據(jù)虛擬機資源需求權重向量以及目標物理節(jié)點資源使用情況的乘積，計算目標物理服務器節(jié)點部署該虛擬機的承受能力的預估值，預估值越小，則目標節(jié)點對部署虛擬機的承受能力越強，虛擬機的服務質量也就越高。

2 基于AHP優(yōu)化算法的虛擬機部署與調度

本文主要優(yōu)化目標是實現(xiàn)數(shù)據(jù)中心負載均衡度和資源利用率的提高。在虛擬機部署與調度時，通過物理服務器躲避列表，判斷虛擬機資源需求類型與物理服務器類型標志的一致性，對目標物理服務器進行初次選擇，以避免相同資源需求虛擬機對物理資源的競爭；運用層次分析模型對虛擬機資源進行量化分析，并根據(jù)虛擬機資源需求的權重向量與物理服務器節(jié)點的資源使用情況對符合條件的目標物理服務器節(jié)點預測評估，從而選擇最佳虛擬機與目標物理服務器部署方案，并按照虛擬機的資源需求類型設置物理服務器的類型標志。

2.1 基于AHP優(yōu)化算法的虛擬機部署策略

在某一段時間，假設需要將n臺虛擬機部署到數(shù)據(jù)中心的m 臺物理服務器節(jié)點上，其中，Vmi＝｛Vm1，Vm2，…，Vmn｝表示待部署虛擬機集合，Pmj＝｛Pm1，Pm2，…，Pmm｝表示物理服務器集合。

對于集合Vmi中任意Vm，若Vm首次開啟，獲取其它相同資源需求類型虛擬機提供正常服務時對物理資源的平均使用值R1；若Vm重啟，獲取該虛擬機以往對物理資源的平均使用值R2；將平均值作為該虛擬機開啟時資源使用情況的預估值

通過性能監(jiān)控查詢Pmj中所有物理服務器當前資源使用情況Rp及其類型標志M

根據(jù)矩陣A 計算虛擬機CPU、內存以及帶寬資源相對于目標物理服務器選擇的影響權重，并取得相應的權重向量w

判斷當前物理服務器類型標志與虛擬機資源需求的一致性，若一致，說明該物理服務器已部署相同資源需求的虛擬機，將其加入到該虛擬機的物理服務器躲避列表Ki；若不一致，需滿足式 （9），即部署該虛擬機時物理資源使用不能超過該物理服務器資源使用量的上限閥值Rp＿up

根據(jù)式 （10）計算待部署Vm對Pmj中所有物理服務器的預估值，S表示預估值集合

選擇預估值集合S中最小值Smin，其對應的物理服務器即目標物理服務器，然后將虛擬機部署到該物理服務器上并啟動。

每次部署完成時，按照虛擬機資源需求設置目標物理服務器標志，并將物理服務器加入相應Ki。

Algorithm1：虛擬機部署算法 輸入：待部署虛擬機集合Vmi ，可用物理服務器集合Pmj ，各虛擬機資源需求類型M′輸出：各虛擬機Vm 的目標物理服務器節(jié)點P m for every Vmin Vmido 運用AHP評估虛擬機M′的權重向量w； if（Vm 首次啟動）do 獲取與Vm 資源需求類型相同的虛擬機的平均資源使用情況R1 ； else 獲取Vm 以往運行時平均資源使用情況R2 ； end if； for（Pm 屬于Pmj ）do 查詢Pm 當前資源情況Rp 及其類型標志M； if（M 與M′一致）do 將Pm 加入Vm 的物理服務器躲避列表Ki； else while（式 （9）成立）do 根據(jù)式 （10）計算Pm 的預估值信息S； end while； end if； end for； for（Smin 屬于S） 獲取所有物理服務器預估值最小的Smin，其對應的Pm即目標物理服務器； end for； 將Vm 部署到Pm ，并啟動該虛擬機任務； 設置目標物理服務器Pm 的類型標志；end for；

2.2 基于AHP優(yōu)化算法的虛擬機的調度策略

某一時間段，假設數(shù)據(jù)中心存在需要進行動態(tài)負載均衡的物理服務器B 及其它m 臺物理服務器，其中Vmi＝｛Vm1，Vm2，…，Vmn｝表示B上所有虛擬機集合，Pmj＝｛Pm1，Pm2，…，Pmm｝表示其它物理服務器集合，負載均衡就是選擇最佳的虛擬機與目標物理節(jié)點調度方案，并重新啟動該虛擬機任務。

獲取物理服務器B當前的資源使用情況RB與集合Pmj中各物理服務器節(jié)點當前資源使用情況Rm及各自的類型標志M

運用AHP分析評估物理服務器B上所有虛擬機的權向量w，獲取各虛擬機運行過程中對服務器資源的使用情況及資源需求，取平均值R3作為虛擬機重啟后對服務器資源使用情況的預估值

判斷當前物理服務器類型標志與待遷移虛擬機資源需求的一致性，若一致，說明物理服務器已部署相同類型的虛擬機，將其加入躲避列表Ki；若不一致，需滿足式（14），即物理資源使用不能超過物理服務器資源使用量的上限閥值Rp＿up

然后按照式 （10）計算所有滿足條件的物理服務器的預估值信息，選擇物理節(jié)點B 上每一臺虛擬機對Pmj中各物理服務器預估值信息的最小值，記為集合S；根據(jù)式（15）計算虛擬機遷出后，物理節(jié)點B的預估值信息S′

G 表示原物理服務器B 相對于目標物理服務器負載的輕松度，若G 小于1，表示目標物理服務器的負載比物理服務器B要輕松，則方案可行，記錄S信息；若G 大于1，表示目標物理服務器的負載比物理服務器B 的負載要重，則方案不可行

最后，在所有備選方案中選擇預估值信息S最小的方案，將待遷移虛擬機遷移到目標物理服務器，并重新啟動該虛擬機任務。

Algorithm2：虛擬機負載均衡算法 輸入：資源過載物理節(jié)點B及其上運行的虛擬機集合Vmi ，物理節(jié)點集合Pm j 輸出：最佳的遷移方案f 根據(jù)對數(shù)據(jù)中心實時監(jiān)控，獲取B當前資源使用情況信息，記為RB ；for（Vm 屬于Vmi）do獲取虛擬機Vm 的資源使用情況及其資源需求類型M′，并獲取該虛擬機的平均資源使用量R3 ；運用AHP模型對虛擬機Vm 進行分析評估，計算其權重向量w；for（Pm 屬于Pmj ）do 查詢Pmj 中Pm 的當前資源使用情況Rm 及其類型標志M； if（M 與M′一致）do

將Pm 加入Vm 的物理服務器躲避列表Ki；else while（式 （14）成立）do 根據(jù)式 （10）計算Pm 的預估值信息S； end while；end if；end for；獲取Pmj 中所有服務器預估值信息的最小值S；按式 （15）計算B放棄Vm 的預估值信息S′；根據(jù)式 （16）判斷當前方案下物理服務器B 節(jié)點與目標物理服務器的相對輕松度G if（G＜1）do 該方案可行，記錄S相關信息，并將當前虛擬機遷移方案加入到備選方案列表F中；else 該方案不可行，放棄對Vm 的遷出方案；end if；end for；for（f屬于F）do 在F中查詢擁有最小S值的方案f，即最佳虛擬機與目標物理服務器遷移方案。end for；根據(jù)方案f進行虛擬機遷出，重新啟動該虛擬機；

3 實驗與分析

3.1 實驗設計

為評估優(yōu)化策略性能，本文在CloudSim［13］云平臺下進行仿真實驗。通過對CloudSim 的擴展編譯以及相關類和接口的改寫，獲取相應的實驗環(huán)境，并完成虛擬機部署與調度測試。本實驗中所需虛擬機的類型、數(shù)量、CPU 及內存參數(shù)見表2，物理服務器數(shù)量、CPU 及內存參數(shù)見表3。

表2 虛擬機資源需求

表3 物理服務器資源

3.2 實驗分析

為了評估優(yōu)化策略的平衡效果和資源利用率，本文同時采用表4所示的3種策略進行仿真實驗，并對它們的性能進行了比較。由于啟發(fā)式算法結果的隨機性，在相同實驗環(huán)境下對每種部署策略進行5次仿真實驗，統(tǒng)計并分析每種策略下各物理服務器達到平衡狀態(tài)時的動態(tài)遷移總次數(shù)及其資源使用情況，實驗結果如圖1～圖3所示。

表4 實驗策略

圖1 動態(tài)遷移總次數(shù)

圖2 5次測試的CPU 利用率

圖1顯示3種策略達到平衡狀態(tài)時物理服務器動態(tài)遷移的總次數(shù)。其中，策略1在虛擬機部署時的遷移次數(shù)最多，且在多次遷移的過程中占用大量物理服務器資源，因此服務器的物理資源利用率比較低；策略2和策略3能夠有效地降低負載均衡過程中的動態(tài)遷移總次數(shù)，提高物理服務器的資源利用率；策略3通過引入躲避機制，將相同資源需求的虛擬機部署到不同的物理服務器，避免了由于虛擬機對相同資源競爭而產生的動態(tài)遷移，進一步提高了物理資源的利用率。

圖3 5次測試的內存利用率

圖2和圖3顯示了采用3種策略達到平衡時各物理服務器的負載情況。從圖中可看出采用策略1時，物理服務器CPU 利用率以及內存利用率曲線波動較大，各物理服務器節(jié)點的物理資源 負載極不均衡；采用策略2和策略3時CPU 利用率以及內存利用率曲線波動較小，都能有效解決數(shù)據(jù)中心物理服務器負載均衡問題，并保持較好的均衡效果；在策略3下物理服務器間CPU 利用率及內存利用率波動最小，負載均衡效果最佳，物理服務器的資源利用率及虛擬機服務質量最高。

4 結束語

為避免同一臺物理服務器節(jié)點上各虛擬機之間對相同物理資源的競爭，提出了基于層次分析優(yōu)化的虛擬機部署與調度策略。通過物理服務器躲避機制對目標物理服務器進行初次篩選，將不同資源需求的虛擬機部署到同一臺物理服務器，以實現(xiàn)虛擬機互補；根據(jù)層次分析模型對虛擬機進行量化分析，并利用物理服務器資源使用情況選擇最佳虛擬機與物理服務器部署方案。通過CloudSim 云仿真實驗，本文優(yōu)化策略進一步減少了物理服務器達到負載平衡時的動態(tài)遷移次數(shù)，提高了資源利用率，使得整個數(shù)據(jù)中心服務器資源更趨于平衡，保證了物理服務器上虛擬機的服務質量。

［1］Armbrust M，F(xiàn)ox A，Griffith，et al.Above the clonds：A Berkeley view of cloud computing，UCB／EECS－2009－28 ［R］.Springfield，USA：University of Callifomia，Berkeley：Engineer and Computer Science Department，2009.

［2］LIU Peng.Cloud computing ［M］.2rd ed.Beijing：Publishing House of Electronics Industry，2011：1－12（in Chinese）.［劉鵬.云計算［M］.2版.北京：電子工業(yè)出版社，2011：1－12.］

［3］LUO Junzhou，JIN Jiahui，SONG Aibo，et al.Cloud computing：Architecture and key technologies［J］.Journal on Communications，2011，37 （7）：3－21 （in Chinese）. ［羅 軍舟，金嘉暉，宋愛波，等.云計算：體系架構與關鍵技術 ［J］.通信學報，2011，37 （7）：3－21.］

［4］Barham P，Dragovic B，F(xiàn)raser K，et al.Xen and the art of virtualization ［C］／／Proceedings of the 19th ACM SOSP.New York：ACM Press，2003：164－177.

［5］HAN Dezhi，LI Nannan，BI Kun.Study of virtualization technology in cloud environment［J］.Huazhong University of Science＆Technology （Natural Science Edition），2012，40 （S1）：262－265 （in Chinese）.［韓德志，李楠楠，畢坤.云環(huán)境下的虛擬化技術探析 ［J］.華中科技大學學報 （自然科學版），2012，40 （S1）：262－265.］

［6］Hirofuchi T，Nakada H，Itoh S，et al.Reactive consolidation of virtual machines enabled by postcopy live migration ［C］／／Proceedings of the 5th International Workshop on Virtualization Technologies in Distributed Computing.ACM，2011：11－18.

［7］Goiri I，Julia F，Nou R，et al.Energy－aware scheduling in virtualized datacenters ［C］／／IEEE International Conference on Cluster Computing.IEEE，2010：58－67.

［8］LI Jinchao，CHEN Jingyi，WU Jie，et al.Virtual machine placement research based on improved grouping genetic algorithm ［J］.Computer Engineering and Design，2012，33 （5）：2053－2056 （in Chinese）.［李進超，陳靜怡，吳杰，等.基于改進分組遺傳算法的虛擬機放置研究 ［J］.計算機工程與設計，2012，33 （5）：2053－2056.］

［9］Gao Yongqiang，Guan Haibing，Qi Zhengwei，et al.A multiobjective ant colony system algorithm for virtual machine placement in cloud computing ［J］.Journal of Computer and System Sciences，2013，79 （8）：1230－1242.

［10］ZHUANG Wei，GUI Xiaolin，LIN Jiancai，et al.Deployment and scheduling of virtual machines in cloud computing：An“AHP”approach［J］.Journal of Xi’an JiaoTong University，2013，47（2）：28－32（in Chinese）.［莊威，桂小林，林建材，等.云環(huán)境下基于多屬性層次分析的虛擬機部署與調度策略 ［J］.西安交通大學學報，2013，47 （2）：28－32.］

［11］JIAO Bo，HUANG Chengdong，HUANG Fei，et al.An aggregation method for the AHP judgment matrices based on optimum possibility－satisfiability degree ［J］.Control and Decision，2013，28 （8）：1242－1246 （in Chinese）.［焦波，黃赪東，黃飛，等.一種基于最優(yōu)可能滿意度的群AHP 判斷矩陣集結方法 ［J］.控制與決策，2013，28 （8）：1242－1246.］

［12］CHEN Xixiang，QIU Jing，LIU Guanjun.Research on the method of test－equipment selection based on analytic hierarchy process and fuzzy comprehensive assessment［J］.ACTA ArmamentarII，2010，31 （1）：68－73 （in Chinese）. ［陳希祥，邱靜，劉冠軍.基于層次分析法與模糊綜合評判的測試設備選擇方法研究 ［J］.兵工學報，2010，31 （1）：68－73.］

［13］Caltheiros R N，Ranjan R，Cesar AF，et al.CloudSim：A novel framework for modeling and simulation of cloud computing infrastructures and services，GRIDS－TR－2009－1 ［R］.Parkville，VIC：The University of Melbourne Australia，Grid Computing and Distributed Systems Laboratory，2009.