基于三支決策的虛擬機節能遷移策略

楊 翎，姜春茂

（哈爾濱師范大學計算機科學與信息工程學院，哈爾濱 150025）

0 引言

近年來，云計算［1-2］作為一種按需提供服務的計算模型，其能效問題日益得到關注。云能效問題涉及軟件、硬件、網絡等各種要素［3-4］，其中作為數據中心重要組成成分——主機的負載對于能耗的影響巨大。主機負載的程度與其所耗費的能源是不成正比的，這意味著，負載很輕時，如10%的負載，主機也要耗費60%～70%的正常標定能耗；而負載超過特定閾值如70%時其能耗急劇增加［5］。因此，保持主機在一個合理的范圍內，對于降低數據中心的能耗、平衡負載與均衡多維資源的利用率具有重要的意義。

虛擬機遷移技術［6-7］通過遷移過高負載主機的虛擬機合并到過輕負載的主機，進而整合主機的多維資源，減少數據中心的資源浪費，提高資源利用率，避免主機負載過重導致的能耗急劇增加，從而降低了數據中心的能耗。

本文提出一種基于三支決策的虛擬機節能遷移調度策略（Virtual Machine Migration scheduling strategy based on Three-Way Decision，TWD-VMM），借鑒三支決策的思想，將主機分為高負載主機、中等負載主機和低負載主機，進而作出虛擬機遷移調度的決策，即：1）高負載主機遷出虛擬機；2）低負載主機遷入虛擬機；3）將盡可能多的主機負載收斂至中等負載的區域，從而避免主機負載出現過高或過低的情況，達到主機負載均衡并降低數據中心的能耗開銷。

1 相關工作

近年來，利用虛擬機遷移技術來節省云能耗的調度算法相繼被研究。大體上包括如下幾類：

1）從遷移角度出發。Zhao等［8］研究基于啟發式的虛擬機節能調度算法，提出一種能量感知算法，將遺傳算法與禁忌搜索算法相結合，獲得一種最優的虛擬機遷移方案，以達到節省云能耗、平衡資源負載的作用；Xu等［9］將虛擬機遷移歸結為一種多約束的優化模型，提出了一種啟發式虛擬機整合算法，有效降低了遷移成本和能耗；穆瑞輝［10］提出了一種改進的虛擬機在線遷移算法，依據各主機CPU、內存和帶寬利用率確定虛擬機遷移時機，構建了在線遷移算法模型。

2）通過預測和監測主機負載來確定遷移時機，進而選擇遷移虛擬機和目標主機。吳小東等［11］提出了TVMS（Threshold-based energy-efficient VM Scheduling in cloud datacenters）算法，該算法為云數據中心基于閾值的虛擬機遷移節能調度算法，能夠動態預測虛擬機的計算性能，計算虛擬機需求的性能期望值與方差，同時根據靜態閾值判斷虛擬機遷移的時機，對過載主機采取虛擬機遷移，從而降低云能耗；阮順領等［12］針對遷移時機，提出面向數據中心能效優化的虛擬機遷移調度EEVS（Virtual machine migration Scheduling method optimising Energy-Efficiency of data center）算法，EEVS算法將遷移時機細分為三種緊急度，并選擇遷移的虛擬機，確定目標主機，完成虛擬機遷移前的準備工作，對主機進行動態遷移和整合，減少主機的運行數量，以此最小化云能耗；Tian等［13］提出了一種資源動態調度模型，考慮主機與虛擬機的多維資源，使用方差計算主機的綜合負載均衡值；黎紅友等［14］提出了一種負載感知的技術模型，該模型通過對主機負載均衡值排序與分區，將虛擬機遷移到資源最不均衡的主機；文獻［15］提出了基于虛擬機遷移的云計算中心節能調度REVMS（Virtual Machine migration Scheduling to Reduce Energy consumption in datacenter）算法，針對虛擬機分配與合并問題，提出一種優化的虛擬機分配與整合調度算法，提高主機的資源利用率，并通過關閉空閑主機來節省云能耗。

目前眾多針對虛擬機遷移的研究，基本都是將主機的負載劃分為高負載和低負載，采取的遷移策略如表1所示。

通過從高負載主機遷出虛擬機到低負載主機上來避免主機負載過高，進而保持數據中心的主機負載在一個合理的范圍內，從而降低數據中心的能耗。在選擇低負載目標主機時，通常需要遍歷所有的低負載主機。如果低負載主機數量很多，則虛擬機選擇范圍較廣，影響算法效率。因此，本文試圖給出基于三支決策的調度模型，通過將負載劃分為高負載區域、中等負載區域、低負載區域三個區域，然后針對性地設計不同的策略加以調度，使所有主機的負載都收斂在中等負載的區域內，從而優化數據中心的總能耗。三支決策［16-22］的基本思想契合了本文需要解決的問題。三支決策是一種有效的復雜問題處理策略，自從提出以來，廣泛地被應用于垃圾郵件過濾［23］、面部識別［24］、政府決策［25］、推薦系統［26］等。

表1 主機遷移策略Tab.1 Host migration strategy

隨著云計算理論研究工作的深入，不難發現云計算系統中存在大量三支粒度現象，當前開展了諸多基于三支決策的云計算研究，三支決策的相關算法和模型得以被廣泛研究和使用［27-30］。姜春茂等［31］依據任務的延遲時間特性建立三支隊列模型，提出了面向實時云任務的細粒度合并調度算法；徐曉霞等［32］提出了一種面向延遲容忍型任務的移動云計算節能卸載策略，將卸載分為立即卸載、延遲卸載和不卸載三種決策；吳俊偉等［33］提出了代價敏感的三支聚類評分算法，在任務平均響應時間與資源利用率等方面有顯著效果。

三支決策的核心思想是通過粒度劃分的方式將整體分為互不相交或者弱相交的三個部分或三個子集，并對各個部分或子集采取不同的策略。三支決策理論以三分而治作為基本的理論模型，包括分、治、效三部分。本文借鑒三支決策的基本思想，提出基于三支決策的虛擬機遷移調度模型，把主機按照負載劃分為高、中、低是“分”；針對三種不同類型的主機分別采取不同的遷移決策是“治”；最終達到負載均衡和節省能耗是“效”。

2 基于三支決策的虛擬機遷移調度模型

本章通過一個實例分析基于三支決策模型的動機以及本文提出的模型，即基于三支決策的虛擬機遷移調度策略（Virtual Machine Migration scheduling strategy based on Three-Way Decision，TWD-VMM）。

2.1 模型提出的動機

在虛擬機遷移技術中，往往是二分主機負載，即：當主機負載大于某閾值時判定為高負載，主機負載小于等于某閾值時判定為低負載，這是典型的二支決策。在此基礎上，本文將二支情況拓展到三支情況，主機分為高中低三種類型，即三分主機負載。為研究二分主機與三分主機在虛擬機遷移方面的異同，假設數據中心有10 臺不同負載的主機，對比二分主機與三分主機在虛擬機遷移的不同決策，如圖1所示。

圖1（a）、（b）有相同的數據中心。圖1（a）為二分主機的遷移決策，將主機分為高負載和低負載。第1 臺主機負載為98%，明顯為高負載，其余9 臺主機為低負載。當高負載主機的虛擬機遷出時，目標主機的搜索范圍是9 臺低負載主機。圖1（b）為三分主機的遷移決策，分別將主機分為高負載、中等負載和低負載。第1臺主機為高負載，第4、5、6臺主機負載為2%，明顯為低負載，其余6 臺主機為中等負載。當虛擬機遷出時，目標主機的搜索范圍是3 臺低負載主機，相較于前者極大地縮小了目標主機的搜索范圍。隨著數據中心主機負載情況越復雜，三分主機的虛擬機遷移策略在縮小目標主機搜索范圍的效果上就會越明顯。假設虛擬機遷出后使第1 臺主機負載降低10%，目標主機負載增加10%，分別對基于二分主機和三分主機的虛擬機遷移，統計遷移后10 臺主機的負載情況，并計算遷移后主機負載方差，設第i臺主機負載表示為Loi，主機負載方差如式（1）所示，遷移后負載結果如表2所示。

其中：N為主機數量；load_avg表示為主機負載平均值；load_var表示為主機負載方差。

如表2 所示，二分主機的虛擬機遷移有3 種方式，分別是虛擬機遷移到負載為60%、70%和2%的主機；三分主機的虛擬機遷移只有1 種結果，即虛擬機遷移到負載為2%的主機。分別計算10 臺主機的負載方差，方差越小主機負載越均衡。從表2看出虛擬機遷移到負載為2%的主機時負載方差最小，主機負載最均衡。二分主機的虛擬機遷移決策有3 種結果，可能最終的目標主機不是最優選擇；而三分主機在遷移虛擬機的決策上直接選擇低負載的主機。本文根據負載將主機三分有以下優勢：

1）減少虛擬機遷移時對目標主機的搜索范圍，精確虛擬機選擇目標，提高虛擬機遷移效率。

2）主機負載均衡。從表1 看出，將高負載主機的虛擬機遷移到低負載主機，更有利于主機的負載均衡。

3）本文通過虛擬機遷移，將所有主機的負載收斂到中等區域內，避免主機負載過高導致的能耗急劇增加，避免主機負載過低導致的資源浪費，達到節省能耗的目的。

圖1 二分主機與三分主機的虛擬機遷移決策示意圖Fig.1 Virtual machine migration decisions for two-way hosts and three-way hosts

表2 主機遷移后負載情況Tab.2 Load after host migration

2.2 基于三支決策的虛擬機遷移模型

虛擬機遷移通常有三個方面：遷移時機的確定、遷移虛擬機的選擇，以及目標主機的確定。本文提出的三支決策虛擬機遷移策略，是將主機依據負載情況劃分為高、中、低三種類型，如果存在高負載主機，則立刻從高負載主機列表中選擇虛擬機遷出，從低負載主機列表中選擇主機遷入，如圖2所示。

圖2 遷移總框架Fig.2 Overall framework of migration

從圖2 中可以看出，本文調度策略中需要研究的兩個方面：1）主機三分閾值的確定；2）主機高、中、低的三支治略。從圖2 可知，高負載主機和低負載主機最終通過虛擬機的遷移，都收斂成為中等負載，使所有主機負載均衡，從而降低數據中心能耗。

3 三支閾值的確定方法

本章主要介紹如何確定三支閾值，即確定一對閾值[α，β]，將主機劃分為三個集合，分別為高負載主機、中等負載主機和低負載主機集合。

首先初始化閾值α=0.1，β=0.9，設置閾值浮動值d=0.1。其中閾值的浮動變化有4 種方式：α=α+d、α=α-d、β=β+d和β=β-d，如圖3所示；其次執行數據中心所有任務，初始閾值作為根節點并計算總能耗E，和4 個子節點的總能耗E′，數據中心能耗計算如式（2）；最后比較根節點與子節點的能耗，如果存在E′＜E，選擇E′的閾值作為下一次迭代的根節點，更新閾值[α，β]和總能耗E=E′，重復上述步驟，迭代1 000次，逐漸收斂閾值范圍。

圖3 閾值樹狀圖Fig.3 Threshold tree

計算閾值的中心任務：找到最佳閾值，將主機分為高負載、中等負載和低負載主機。通過不斷改變閾值，搜索所有閾值可能取到的值，形成閾值樹狀圖。如圖3 所示，層次遍歷計算不同閾值下的數據中心能耗，搜索到總能耗最低的閾值，作為該數據中心負載的閾值。式（2）中使用的是文獻［5］的能耗模型：

其中：E表示數據中心在時間[t0，t1]內的總能耗；e(μ(t))表示為主機利用率在t時的能耗［5］。

如圖3所示，在層次遍歷過程中，需要遵循以下4點：

1）閾值用于判斷主機為高負載還是低負載，閾值會影響該主機是否遷移的決策，而不同的遷移決策會影響數據中心總能耗大小，因此通過層次遍歷的方式，遍歷閾值可能出現的值，通過比較每種閾值時的能耗，獲得閾值在何值時，數據中心的能耗最低，且α值不能大于β。

2）每次迭代都會完整執行數據中心的所有任務，在執行任務過程中，主機負載是動態變化的。

3）每次比較根節點與子節點的能耗E與E′，選擇總能耗最小的閾值作為下一次迭代的根節點；如果不存在E′＜E，選擇E′=E的閾值作為下一次迭代的根節點，暫時不更新[α，β]與E，直到出現E′＜E時再更新。

4）數據中心負載與能耗之間的關系：數據中心一定實際存在高負載與低負載的閾值，在該閾值下數據中心能耗最低。設實際閾值為[α′，β′]，如果計算出的[α，β]與實際閾值[α′，β′]不一致，可能出現如圖4的4種情況：

1）若β比實際閾值高，說明存在高負載主機被誤判成中等負載主機，如圖4（a）所示，介于[β′，β]范圍的主機為菱形，菱形主機本身是高負載，但是由于β閾值的不正確，被錯誤判斷成中等負載，因此沒有及時遷出虛擬機，導致數據中心存在高負載主機，增加數據中心總能耗。

2）若β比實際閾值低，說明存在中等負載主機被誤判成高負載主機，如圖4（b）所示，介于[β′，β]范圍的主機為菱形，菱形主機本身是中等負載，卻被錯誤判斷成高負載，并通過虛擬機遷出使該主機負載降低，數據中心主機資源沒有充分利用，很可能導致主機數量的增加。

3）若α比實際閾值高，說明存在中等負載主機被誤判成低負載，如圖4（c）所示，介于[α′，α]范圍的主機為菱形，菱形主機本身是中等負載，但是由于α閾值的不正確，接受了虛擬機的遷入導致負載增加，可能成為高負載主機，增加數據中心總能耗。

4）若α比實際閾值低，說明存在低負載主機被誤判成中等負載主機，如圖4（d）所示，介于[α′，α]范圍的主機為菱形，菱形主機本身是低負載，但是沒有接受虛擬機遷入，仍然是低負載主機，導致數據中心資源浪費，總能耗增加。

圖4 [α，β]與[α′，β′]不一致的4種情況Fig.4 Four cases of[α，β]differing to[α′，β′]

4 不同負載主機的三支遷移策略

本章分別對高、中、低負載的主機采取不同“治”。對于高負載主機，選擇虛擬機遷出的決策；對于低負載主機，采取接受虛擬機遷入的決策；對于中等負載主機，優先采取不遷移，但所有主機最終都會收斂到中等負載區間。因此本章分別闡述三種不同負載的主機的不同遷移治略。

在虛擬機遷移過程中，考慮到主機屬性的多維性，本文考慮用3 維向量來刻畫主機性能，其中包括主機的CPU、內存能力和網絡帶寬能力。定義第i臺主機的多維資源描述為hi=分別表示為第i臺主機的CPU、內存和網絡帶寬傳輸能力。定義虛擬機資源的描述為vr={vrc，vrr，vrb}，同理vrc，vrr，vrb分別表示為虛擬機請求的CPU、內存資源和網絡帶寬傳輸資源，并且虛擬機在分配主機時，目標主機的空閑CPU、內存和網絡帶寬都必須滿足虛擬機的資源請求，遷出虛擬機的原主機和目標主機都需要滿足網絡傳輸的請求資源。

4.1 高負載主機遷移策略

高負載主機的遷移策略是將虛擬機遷出，涉及選擇虛擬機的問題，考慮兩方面因素，分別是主機預遷出后多維資源均衡度和主機負載下降幅度。

4.1.1 主機預遷移后多維資源均衡度

定義1主機預遷移后多維資源均衡度。表示第i臺主機上遷出第j臺虛擬機后，該主機的多維資源均衡度為BUij，公式如下：

4.1.2 主機負載下降幅度

由于虛擬機遷移會導致數據中心能耗變化，為控制主機負載下降的幅度，定義能耗抖動值x；同時在選擇虛擬機進行遷移時需要遵循以下兩點規則：

1）遷移一次即可，不要多次遷移，因為多次遷移可能會造成原主機執行任務數量突然減少，使原主機負載下降過多；

2）遷移后的原主機依然可以保持在中等負載中較高的主機負載。

定義2為保證選擇虛擬機遷移時遵循以上兩點規則，定義能耗抖動值x，該值意義在于控制遷出的虛擬機占主機CPU比率。

表3 為數據中心的主機CPU 性能（Host_MIPS）與虛擬機CPU 請求（Vm_MIPS），其中CPU_Utilization為虛擬機占主機的CPU比率，計算公式如式（4）所示：

表3 虛擬機占主機CPU的比率Tab.3 Ratios of CPU performance of host and virtual machine

從表3 可以看出，數據中心有6 種虛擬機類型、1 種主機類型，不同類型的虛擬機對應的CPU_Utilization值不相同，分別為8%、14%、22%、25%、27%、40%。假設目前有3 種主機負載，分別為98%、96%、94%，明顯為高負載主機，需要遷出虛擬機。如表4 所示，對3 種高負載主機，分別遷移6 種虛擬機后的負載情況。

表4 不同虛擬機遷移后負載情況Tab.4 Load after different virtual machine migrations

從表4 看出：在選擇遷出的虛擬機時，如果把負載為8%、14%的虛擬機遷出，該主機仍然可能是高負載，違背了遷移一次即可的原則；如果把25%、27%的虛擬機遷出，該主機可能會成為中等負載主機，并且負載為69%、67%，可能是中等區域中較高的負載；如果把40%的虛擬機遷出，遷出后主機負載為56%左右，可能導致原主機負載下降過多，違背原主機遷移后仍保持中等負載中較高負載的原則。

隨著數據中心越加復雜，主機負載多樣化，以及主機上虛擬機類型多樣性等各種因素，遷移虛擬機對原主機負載的影響會越來越大。x取值的作用就是控制遷出虛擬機對主機負載的影響程度，選擇CPU_Utilization趨近于x值的虛擬機，就是讓遷出后的主機負載下降幅度控制在x左右，因此x取值并不是越大越好，也不是越小越好，x取值存在以下兩種情況。

1）x取值大：說明主機遷出虛擬機后，該主機負載會大幅度下降，可能違反遷移虛擬機的第2 條規則，即不能保證遷出后的主機仍然是中等負載中較高的負載，導致主機資源浪費，可能會增加數據中心主機數量，總能耗增加。

2）x取值?。赫f明主機遷出虛擬機后，該主機負載下降幅度小，可能會違反遷移虛擬機的第1 條規則，即遷移后主機仍然是高負載主機，數據中心能耗增加。

在選擇遷出的虛擬機時，不僅關注主機多維資源均衡度，還關注虛擬機遷出后對主機負載的影響，因此遷移虛擬機選擇的目標函數計算如式（5）所示：

其中：BUij值越小，說明該主機遷移虛擬機后的多維資源越均衡；|CPU_Utilization-x|表示虛擬機所占主機的CPU 利用率與x的偏移程度大小，該值越小，說明該虛擬機所占主機的CPU利用率越接近x。綜合考慮兩者的因素，將乘積作為目標函數，選擇虛擬機的原則是目標函數最小值的虛擬機作為遷移的虛擬機。其中需要說明的是：由于BUij是根據方差計算的，不同虛擬機的BUij值不同，但是不會出現特別大或者特別小的數值，且|CPU_Utilization-x|的最大范圍在0 到1 之間，不會存在特別大或者特別小的數值，所以不存在兩個變量乘積的結果會因為其中一個變量太大或者太小，造成目標函數的數據偏移現象。

4.2 中等負載主機遷移策略

中等負載主機一般不進行遷移，但是考慮到如果低負載主機中沒有合適的主機遷移，該情況下，可以考慮選擇中等負載主機。雖然低負載和中等負載主機都是目標主機的選擇范圍，但是選擇優先級不同。目標主機選擇總流程如圖5所示。

圖5 目標主機確定流程Fig.5 Target host determination process

選擇目標主機的優先級如下：

1）低負載主機。

優先級最高的是低負載主機，其中可能存在以下3 種情況：①低負載主機列表為空；②低負載主機列表中存在空負載主機，將這類主機添加至空負載主機列表，并且不進行遷移；③存在低負載主機列表，且不包括空負載主機，則遍歷該列表，分別計算虛擬機預放置該主機后多維資源均衡度BHk，選擇最小均衡度值的主機遷移，計算如式（6）所示。

2）中等負載主機。

如果低負載主機列表中沒有合適放置的主機，原因有以下兩種情況：①低負載主機列表為空；②低負載主機列表中都是空負載主機，不進行遷移。優先級為第二的是中等負載主機，需要滿足兩點條件：①中等負載主機的剩余資源能夠滿足虛擬機鏡像請求的資源大??；②虛擬機放置主機后仍然可以滿足該主機是中等負載。如果存在滿足以上兩點條件的主機列表，分別計算式（6）的多維資源均衡度BHk，選擇均衡度值最小的主機進行遷移。如果以上兩點條件有一條不滿足，就不進行遷移。

3）空負載主機列表。

如果以上兩類主機都沒有進行遷移，再遍歷空負載主機，即需要重新開一臺新主機。遍歷空負載主機列表，選擇第一個滿足資源請求的主機進行遷移，遷入后更新主機類型。

4.3 低負載主機遷移治略策略

低負載主機的遷移治略是接受從高負載主機遷出的虛擬機，并通過遷入虛擬機使主機負載增加到中等的區間內，該過程涉及遷移虛擬機的目標主機選擇問題，本節考慮兩方面因素：①主機預放置后多維資源均衡度；②低負載主機資源利用率是否為0，若利用率為0 表示該主機沒有執行任務，處于休眠狀態的主機，定義為空負載主機。

4.3.1 主機預放置后多維資源均衡度

定義3主機預放置后多維資源均衡度，指遷移虛擬機預放置在第k臺主機后，該主機的多維資源均衡度BHk，計算如式（6）所示：

4.3.2 空負載主機

由于低負載主機存在兩種狀態，負載小于閾值α的主機和負載等于0的主機，因此將負載等于0的主機添加至空負載主機列表，在不需要重新開一臺主機的情況下，空負載主機不接受虛擬機的遷入。

4.4 TWD-VMM遷移算法

經過上述研究與討論，針對高、中、低三種不同情況的負載主機，分別設計了不同的主機遷移策略，在本節將提出一種基于三支決策的虛擬機調度算法。

4.4.1 TWD-VMM流程

4.4.2 時間復雜度分析

TWD-VMM 算法時間復雜度集中在虛擬機與主機的遍歷上，設置數據中心有N臺主機，每臺主機上的虛擬機數量為m，在最差情況下，虛擬機在選擇目標主機時需要遍歷所有主機列表，迭代次數為O(n×m)，即時間復雜度為O(N2)。

5 實驗與結果分析

本文使用Cloudsim 模擬器［34］工具，通過模擬云數據中心環境，主要對比虛擬機遷移算法TVMS、EEVS、REVMS，分別比較所有主機負載平均值、主機多維資源利用均衡度、數據中心總能耗方面的異同。實驗模擬數據中心環境的主機與虛擬機參數如表3 所示，分別在4 種數據中心環境進行測試，結果如表5所示。

表5 四種數據中心環境Tab.5 Four data center environments

實驗采用模擬器CloudSim 進行，它因為較好地對于云計算進行了建模而得到廣泛的應用。實驗所使用的計算機操作系統為64 位Windows10，內存16 GB。在此操作系統上使用Java在IDEA開發平臺上進行實驗。

實驗的內容主要包括：計算主機負載閾值，并與其他閾值進行比較；確定x的取值，并比較有無x下的能耗；將TWDVMM 算法與其他三種虛擬機遷移算法進行能耗、主機負載平均值和主機多維資源均衡度方面的比較。

5.1 閾值確定與比較

計算主機負載閾值，分別在4 種數據中心環境下進行實驗。根據第4章所述計算負載閾值的模型，在4種數據中心環境下分別計算閾值，所得負載閾值結果都為［0.3，0.7］，為驗證該閾值下數據中心的能耗最低，分別與閾值［0.3，0.8］、［0.2，0.9］、［0.2，0.8］進行實驗比較，計算在4 種數據中心環境下的總能耗，能耗比較結果如表6所示。

表6 不同閾值下的數據中心能耗 單位：kWTab.6 Data center energy consumption under different thresholds unit：kW

不同閾值下數據中心能耗不同，隨著任務數量的增加，數據中心總能耗也在增加。從表6 可知，當數據中心負載閾值為［0，2，0.8］時，能耗相對最高，原因是上閾值太高，下閾值太低，導致大多數主機判斷不準確，不能作出正確的遷移決策，遷移后的主機仍然存在高負載和低負載的情況，造成數據中心資源浪費，能耗增加，因此合理的主機閾值確實可以降低總能耗。當數據中心負載閾值為［0.3，0.7］時，分別在4 種數據中心環境下，都可以保持最低的能耗，說明［0.3，0.7］作為負載閾值最優。在之后的實驗中，可以不用重新計算數據中心負載閾值，使用［0.3，0.7］即可。

5.2 能耗抖動x值確定

根據5.1節所述，x用于控制遷出虛擬機對主機負載的影響程度，合理的x取值可以遵循虛擬機遷移的兩條規則。為研究x的取值，本節分別取x=0.1，0.2，0.3 時，計算4 種數據中心環境下總能耗如圖6所示。

圖6 x取值比較Fig.6 x value comparison

從圖6 可以看出，隨著x取值的不同，數據中心能耗也在發生變化，通過比較得出，當x取值為0.2時總能耗最低，說明當限制遷移虛擬機后，控制原主機負載降低20%左右時，能保證較低的數據中心總能耗，因此統一設置x取值為0.2。

為證明x取值具有實際意義，分別在4 種數據中心環境下，對比有x約束和無x約束兩種情況的數據中心總能耗，如表7所示，可以看出，在有x約束的情況下，數據中心總能耗比沒有x約束的總能耗低，說明x的約束條件是有存在意義的，能夠有效選取虛擬機，并控制虛擬機遷出后對主機負載的影響。

表7 有無x約束的數據中心總能耗 單位：kWTab.7 Total energy consumption of data center with or without x constraint unit：kW

5.3 能耗比較

將TWD-VMM 算法與TVMS、EEVS、REVMS 三種算法分別在虛擬機遷移時機和遷移調度上進行研究，比較它們與本文算法的數據中心總能耗，結果如表8所示。

表8 四種算法在四種數據中心環境下總能耗 單位：kWTab.8 Comparison of total energy consumption of four algorithms under 4four data center environments unit：kW

從表8 可以看出，REVMS 算法的數據中心能耗最高，該算法尋找負載最小的主機，并將其主機上所有的虛擬機遷出，并對其下電操作，但是對高載主機選擇恰當的虛擬機遷移沒有較好的決策，因此導致能耗較高。TVMS算法在4種數據中心下能耗較高，由于該算法在調度過程中，通過結合靜態閾值和主機動態預測進行虛擬機遷移，計算主機所需的CPU 期望值和標準差，進而估算主機的CPU 需求量可能達到的值，來決定遷移的時機，但是估算的準確性很大程度上影響虛擬機遷移的判斷，說明合理的遷移判斷能夠有效地節省數據中心總能耗。從實驗比較發現，本文TWD-VMM 算法無論在哪種數據中心環境下執行任務，都可以保持最低的數據中心總能耗，說明本文的TWD-VMM算法最優。

5.4 主機負載平均值比較

主機負載平均值是所有主機的CPU 利用率的平均值，代表主機的負載程度，主機負載動態規律如下：1）高負載主機通過虛擬機遷出使得該主機負載降低，負載達到平穩且繼續執行任務；2）主機上任務執行結束的過程中，該主機的負載動態呈現下降的趨勢；3）當主機上所有任務結束完成，該主機的負載為0。收集主機所有時刻的負載情況，計算主機負載平均值如圖7所示。

圖7 主機負載平均值比較Fig.7 Average host load comparison

如果負載平均值太低，意味著主機的CPU 資源沒有充分利用；如果負載平均值太高，說明任務在運行過程中，存在并可能長期存在高負載的狀態，云環境服務水平較低。從圖7得出，REVMS 算法負載平均值在0.9 左右，相較于其他算法負載偏高，存在大量主機都在高負載狀態。EEVS 算法和TWD-VMM 算法的負載平均值在0.75 左右，為觀察TWDVMM 算法在執行過程中負載的動態情況，隨機選取20 臺主機，獲取1 s 到10 s 內主機歷史數據的負載情況，如圖8～9所示。

圖8 前10臺主機負載圖Fig.8 Load diagram of first 10 hosts

圖9 后10臺主機負載圖Fig.9 Load diagram of last 10 hosts

如圖8～9 所示，當主機在1 s 時正在執行任務，該時刻的主機CPU 利用率有以下3種情況：1）主機為高負載；2）主機為中等負載；3）主機為低負載。從圖8～9中可以看出：2 s之后主機的負載開始發生變化，高負載主機通過遷出虛擬機使負載降低，低負載主機通過遷入虛擬機使負載增加。并且在3 s時所有低負載和高負載主機通過虛擬機遷移都收斂到中等負載的區間。同時11 s后，主機還會接收新的任務，導致主機負載增加，因此主機的負載平均值在0.75 左右，意味著單位時間檢測主機負載時，存在中等負載的主機，也存在由于執行新任務而負載增加的主機，但從圖8～9 可以看出TWD-VMM 符合虛擬機遷移的兩條規則，即遷移一次即可，和遷移后仍然保持較高的中等負載。

5.5 主機多維資源均衡度比較

主機多維資源均衡度計算如式（7）所示：

其中：ahi表示該主機的三維資源平均值；vhi表示三維資源方差；VH為計算數據中心的所有主機方差平均值，數值越小說明主機的多維資源越均衡表示第i臺主機已使用的CPU資源同理。如圖10 可以看出，TWD-VMM 算法的主機多維資源均衡較低，雖然與其余算法比較優勢不明顯，但是TWD-VMM 算法具有較高的CPU 利用率，主機多維資源均衡度低，說明主機不但能夠利用充分CPU 資源，而且內存、帶寬資源也能夠充分利用，有利于數據中心資源的多種資源的充分利用。

圖10 主機多維資源均衡度比較Fig.10 Comparison of multidimensional resource balance of host

6 結語

通過引入三支決策的方法，本文提出的虛擬機遷移調度算法TWD-VMM 將主機分為高負載主機、中等負載主機和低負載主機，然后分別對高、中、低負載主機在遷移時采取不同的策略，通過高負載主機的遷出與低負載主機的遷入，將所有主機負載最終收斂到中等負載的區間內，實現負載均衡，節省數據中心能耗。本文對于如何確定不同負載類型的主機，即三支閾值確定方法，作出了詳細的闡述。實驗結果表明，TWD-VMM 算法無論在哪種數據中心環境下，相較于其他三種對比算法，在資源利用充分、總能耗降低等方面有明顯效果。

在未來工作中，可以將三支決策的理論更多地運用在優化云能耗問題上，包括對主機性能的更細粒度劃分，和更細粒度的調度算法優化等方面進一步研究，并在虛擬機遷移技術上追求其他更多指標等。