基于層次拓撲樹的虛擬機節(jié)能分配算法

蔡立軍+何庭欽+孟濤+陳磊

摘 要：為了均衡分布式數(shù)據(jù)中心物理主機多維資源的利用率，減少物理主機使用數(shù)量，節(jié)約能耗，提出了一種基于層次拓撲樹的虛擬機節(jié)能分配算法HTES（hierarchical topology energy saving），此算法可以有效提升虛擬機分配效率.利用Laplacian矩陣，對大規(guī)模網(wǎng)絡(luò)拓撲分割，建立了層次拓撲樹模型.基于層次拓撲模型，根據(jù)虛擬機請求中IP地址與數(shù)據(jù)中心的距離，將虛擬機請求分組，從層次拓撲樹模型中查詢合適的物理主機區(qū)域，按虛擬機請求與物理主機的資源匹配度進行虛擬機的分配.將HTES與其他3種算法進行模擬仿真實驗，從虛擬機分配時間、資源均衡率、能耗和物理主機使用情況等方面驗證了HTES算法能夠有效加快物理主機搜索速度，增加底層占用物理主機的集中度，降低底層物理主機的使用數(shù)量，達到節(jié)約能耗的目的.

關(guān)鍵詞：數(shù)據(jù)中心；虛擬機分配；層次拓撲樹；能源利用率

中圖分類號：TP391 文獻標志碼：A

Energy Saving Allocation Algorithm

of a Virtual Machine Based on Hierarchical Topology Tree

CAI Lijun1，HE Tingqin1，MENG Tao1，CHEN Lei2

（ 1. College of Information Science and Engineering，Hunan University，Changsha 410082，China；

2. College of Electrical and Information Engineering， Hunan University，Changsha 410082，China）

Abstract：In order to balance the utilization of multi-dimensional physical host resources and reduce usage number， a virtual machine allocation energy saving algorithm was proposed based on hierarchical topology tree （HTES） in the environments of distributed data center， which enhances allocation efficiency of the virtual machines. Laplacian matrix was then used to split large-scale network topology and to build hierarchical topology tree model. Furthermore， according to the distance between request IP address and the data center， HTES divided the virtual machines into groups， and searched the appropriate physical host region from hierarchical topology tree for allocation， which is based on the match degree between virtual machine requests and physical hosts. Simulation experiments were performed on HTES algorithms and other three algorithms， considering the virtual machine allocation time， resource balancing rate， energy consumption and physical host usage， and other aspects. The results shows that the HTES is able to balance multi-dimensional resources physical hosts， reduce physical host usage， and save energy consumption.

Key words：data centers；virtual machine allocation；hierarchical topology tree；energy utilization

隨著信息科技的不斷發(fā)展，數(shù)據(jù)中心作為一種基礎(chǔ)設(shè)施，已經(jīng)被各行各業(yè)普遍使用.然而當前數(shù)據(jù)中心的發(fā)展也面臨新的問題，數(shù)據(jù)中心的規(guī)模不斷擴張，地理位置愈趨分散.多個分散的數(shù)據(jù)中心通過高速網(wǎng)絡(luò)互聯(lián)，共同組成了大型的分布式數(shù)據(jù)中心.在分布式數(shù)據(jù)中心內(nèi)，用戶通過按需付費的模式，向數(shù)據(jù)中心提交需求.數(shù)據(jù)中心根據(jù)用戶地理位置，從較近的基礎(chǔ)設(shè)施庫分配資源并構(gòu)建虛擬機為用戶服務(wù).然而，大規(guī)模分布式數(shù)據(jù)中心環(huán)境的虛擬機的分配問題面臨新的挑戰(zhàn)，主要表現(xiàn)為主機地理位置更為分散、底層資源規(guī)模更為龐大、多維異構(gòu)資源、較高的能源消耗等.因此，合理的虛擬機（資源）分配策略是數(shù)據(jù)中心收益的保障，研究虛擬機分配算法具有重要意義.

目前已有很多學者對數(shù)據(jù)中心虛擬機的分配進行研究，取得了較多的優(yōu)秀成果.一些研究成果集中在優(yōu)化分布式數(shù)據(jù)中心的資源分配上[1-6].文獻[1]從服務(wù)供應(yīng)商的角度，研究了分布式數(shù)據(jù)中心的收益最大化問題，提出了一種結(jié)合虛擬機分配的動態(tài)調(diào)價算法.文獻[2-3]同樣著眼于分布式數(shù)據(jù)中心的成本優(yōu)化問題，從數(shù)據(jù)傳輸和資源分配兩個角度設(shè)計了相應(yīng)的數(shù)據(jù)管理系統(tǒng)和資源調(diào)度算法，最小化數(shù)據(jù)、成本低的同時，優(yōu)化了數(shù)據(jù)的傳輸時間、提升了底層物理資源的利用率.文獻[4]提出了一種基于溫度感知的資源管理系統(tǒng)，通過動態(tài)調(diào)整服務(wù)器的功率，實現(xiàn)虛擬機分配和服務(wù)器負載間的優(yōu)化.文獻[5]在分布式數(shù)據(jù)中心內(nèi)，對虛擬機的分配請求建立G/G/1/PS隊列，通過優(yōu)化隊列處理實現(xiàn)服務(wù)器負載和虛擬機分配的均衡，節(jié)約了數(shù)據(jù)中心能耗.文獻[6]為提升高性能數(shù)據(jù)中心資源使用率，設(shè)計了CAE集成平臺架構(gòu)，實現(xiàn)了一種基于Web方式的高性能計算中心資源的解決方案.有些研究工作使用數(shù)據(jù)中心網(wǎng)絡(luò)拓撲來優(yōu)化虛擬機的分配，提升底層物理資源的利用率[7-10].在portland網(wǎng)絡(luò)拓撲上，文獻[7]提出了2種啟發(fā)式算法，通過分配虛擬機到最大鏈路能力和鄰近的物理主機上，降低了網(wǎng)絡(luò)開銷，增加了底層資源利用率.文獻[8]根據(jù)網(wǎng)絡(luò)拓撲建立了MNT指標，優(yōu)化資源分配.文獻[9]在網(wǎng)絡(luò)拓撲的基礎(chǔ)上，通過虛擬機和鏈路的合并，增加了拓撲中空閑網(wǎng)絡(luò)設(shè)備數(shù)量，節(jié)約了能源.同樣，在實際數(shù)據(jù)中心拓撲上，文獻[10]通過對帶寬過載的虛擬機進行合并，優(yōu)化了網(wǎng)絡(luò)傳輸消耗.此外，還有較多學者研究數(shù)據(jù)中心的能耗問題[11-14]，通過各種模型和方法減少數(shù)據(jù)中心的能源消耗.文獻[11]同時考慮了虛擬機的分配和網(wǎng)絡(luò)流的傳輸，通過建立線性規(guī)劃模型，并行處理虛擬機的分配，節(jié)約能源消耗.文獻[12]中將虛擬機的分配問題看做多商品流的成本最小化問題，通過Benders分解算法進行求解，減少了底層物理主機的使用數(shù)量，節(jié)約了能源消耗.文獻[15]分析了云數(shù)據(jù)中心下資源分配和能源消耗問題，設(shè)計了一種節(jié)能框架，在減少成本的同時節(jié)約能耗.文獻[16]研究了分布式數(shù)據(jù)中心內(nèi)的能源節(jié)約問題，建立了最大化整數(shù)規(guī)劃模型，通過虛擬機的合并，減少了物理主機的使用，從而實現(xiàn)能耗的節(jié)約.

以上的研究工作在處理大規(guī)模非樹型隨機網(wǎng)絡(luò)拓撲[17]的虛擬機分配問題上，無法有效減少數(shù)據(jù)中心物理主機的使用數(shù)量，仍面臨能耗較高的缺陷.網(wǎng)絡(luò)拓撲的大規(guī)模性和隨機性導致虛擬機分配時掃描的物理主機范圍更為龐大，使用傳統(tǒng)的算法效率較低，一方面表現(xiàn)在底層物理主機的搜索時間過長，降低了虛擬機的分配效率；另一方面底層物理主機分配后集中度較低，過高的分散性不利于物理主機的管理和維護.如DCEERS算法[18]通過Benders分解進行虛擬機分配，利用最小數(shù)量的物理主機承載虛擬機請求，雖然減少了物理主機的數(shù)量，在一定程度上降低了能耗，但并未考慮資源的均衡率，可能引起局部負載及單位時間功耗過大；ANT算法[19]利用蟻群策略求解多目標虛擬機的分配問題，但卻需要大量的迭代尋找最優(yōu)，分配時間上較差.

因此，本文提出了一種基于層次拓撲樹的虛擬機節(jié)能分配算法.首先，將分布式數(shù)據(jù)中心的大規(guī)模網(wǎng)絡(luò)隨機拓撲進行拓撲分割，建立層次拓撲樹.其次，在考慮底層物理主機多維資源均衡的前提下，掃描層次拓撲樹，將虛擬機集中分配網(wǎng)絡(luò)拓撲中的集中區(qū)域，降低底層物理主機的使用.通過關(guān)閉空閑物理主機達到節(jié)約能源的目的.最后，通過大量實驗驗證了算法的性能.基于層次拓撲樹的虛擬機節(jié)能分配算法優(yōu)化了虛擬機的分配，提高了底層資源利用率，降低了能源消耗.

1 模型建立

1.1 預備知識

1.1.1 分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓撲

網(wǎng)絡(luò)拓撲是數(shù)據(jù)中心整體結(jié)構(gòu)的一種表示和體現(xiàn).數(shù)據(jù)中心所有物理主機、存儲設(shè)備、網(wǎng)絡(luò)設(shè)備通過網(wǎng)絡(luò)鏈路彼此互連，共同組成網(wǎng)絡(luò)拓撲.通常情況下，網(wǎng)絡(luò)拓撲用圖G=V，E表示.其中，V為節(jié)點集合，表示數(shù)據(jù)中心內(nèi)所有的物理設(shè)備；E為邊的集合，表示兩兩物理設(shè)備間的網(wǎng)絡(luò)鏈路能力，即網(wǎng)絡(luò)帶寬.

在虛擬機的分配過程中，網(wǎng)絡(luò)拓撲起著重要的作用.所有的虛擬機必須映射到網(wǎng)絡(luò)拓撲中的物理主機上，占用物理主機的CPU，MEM資源，占用網(wǎng)絡(luò)拓撲中多個物理主機間的鏈路帶寬資源，甚至占用拓撲中存儲節(jié)點的部分存儲資源.一個虛擬機在分配過程中，需要掃描網(wǎng)絡(luò)拓撲中的空閑物理主機，進行最終的資源分配.網(wǎng)絡(luò)拓撲可以輕松反映虛擬機的分配情況和運行情況，能夠方便監(jiān)控物理主機的負載和運行，便于物理主機的資源調(diào)優(yōu)和能源節(jié)約.當網(wǎng)絡(luò)拓撲發(fā)生變化時，說明底層物理設(shè)備出現(xiàn)了故障，需要進行虛擬機的遷移和重新分配.

分布式數(shù)據(jù)中心由多個地理位置分散的小型數(shù)據(jù)中心組成.小型數(shù)據(jù)中心之間通過高速網(wǎng)絡(luò)進行互連.每個小型數(shù)據(jù)中心彼此獨立，可以擁有不同類型的網(wǎng)絡(luò)拓撲和物理主機.通常，分布式數(shù)據(jù)中心的整體網(wǎng)絡(luò)拓撲是隨機的，底層物理主機資源是異構(gòu)的.圖1為分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓撲圖.

在圖1中，分布式數(shù)據(jù)中心由K個小型數(shù)據(jù)中心組成.每個數(shù)據(jù)中心擁有不同的網(wǎng)絡(luò)拓撲和物理主機類型.分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓撲呈現(xiàn)隨機性和大規(guī)模性，物理主機擁有異構(gòu)特性.網(wǎng)絡(luò)拓撲的大規(guī)模性和隨機性導致虛擬機分配時掃描的物理主機范圍龐大，增加了虛擬機的搜索時間，降低了虛擬機的分配效率.此外，網(wǎng)絡(luò)拓撲的大規(guī)模性必然存在大量物理主機和網(wǎng)絡(luò)設(shè)備空閑的情況，帶來龐大的能源開銷，增加數(shù)據(jù)中心的成本；物理主機的異構(gòu)性增加了虛擬機分配后物理主機多維資源間的不均衡分配，造成資源浪費；數(shù)據(jù)中心的分散性增加了額外的網(wǎng)絡(luò)開銷，浪費了網(wǎng)絡(luò)帶寬資源.

1.1.2 單機多維資源的不均衡分配

在數(shù)據(jù)中心網(wǎng)絡(luò)拓撲中，物理主機本身由多種資源組成（CPU，MEM和存儲），可看作多維資源向量.如果某維資源（CPU）過度分配，必然造成其他維資源（MEM和存儲）的浪費.只有均衡利用各維資源，才能更充分地發(fā)揮資源效率，提升底層資源的利用率，減少數(shù)據(jù)中心物理主機的使用數(shù)量，降低能源開銷.在傳統(tǒng)虛擬機分配過程中，虛擬機的隨機分配往往導致單機多維資源的不均衡分配.

圖2（a）為單機多維物理資源的不合理分配情況.由圖2（a）可知，僅考慮了CPU和MEM兩維資源，3個虛擬機分配到了物理主機上，造成了物理主機CPU資源的利用率達到了90%（40%+20%+30%）.然而，物理主機的內(nèi)存資源才使用25%（15%+8%+2%）.當新的虛擬機訪問物理主機時，雖然剩余較多的內(nèi)存資源，但是由于CPU資源的高利用率，導致物理主機無法承載新的虛擬機，從而造成了內(nèi)存資源的大量浪費，出現(xiàn)單機多維資源的不均衡分配.圖2（b）中，描述了物理主機的均衡分配情況.同樣是3個虛擬機，但是物理主機的CPU和MEM資源利用率相對均衡，都達到了90%，不會出現(xiàn)單維資源的空閑浪費，能夠更加充分地利用底層資源.

單機多維資源的均衡分配能夠提升底層物理資源的利用率，降低數(shù)據(jù)中心成本.此外，多維資源的均衡分配，可以在一定程度上減少底層物理主機的使用數(shù)量，達到降低數(shù)據(jù)中心能耗的目的.

1.2 問題描述

分布式數(shù)據(jù)中心內(nèi)虛擬機的調(diào)度過程可描述為：位置各異的多個用戶向數(shù)據(jù)中心提交一批虛擬機請求Vms={vm1，vm2，…}.每個虛擬機擁有4種屬性，用vmi={req_cpui，req_memi，req_bwi，ipi，lifetimei}表示，其中req_cpui，req_memi，req_bwi分別表示CPU，MEM和帶寬請求大小，ipi表示用戶的地理位置信息，lifetimei表示當前虛擬機的生命周期.分布式數(shù)據(jù)中心由網(wǎng)絡(luò)拓撲圖G=V，E表示.其中，V為物理資源的集合，E為物理資源間網(wǎng)絡(luò)鏈路帶寬的集合.在分布式數(shù)據(jù)中心內(nèi)，用戶提交的虛擬機請求將根據(jù)用戶位置分配到較近的物理主機上，占用物理主機資源和網(wǎng)絡(luò)帶寬.每個物理主機hostj={cab_cpuj，cab_memj，cab_bwj，DC}擁有3種資源CPU，MEM和帶寬.DC（Data Center）是物理主機所屬子數(shù)據(jù)中心的標識，代表物理主機的位置信息.

在虛擬機的分配過程中，每個虛擬機vmi只能分配到一臺物理主機上hostj.物理主機hostj的剩余資源能力必須滿足虛擬機的請求.一個用戶可以提交多個虛擬機請求，同一用戶的多個虛擬機應(yīng)該分配在同一地理位置的物理主機上.此外，分布式數(shù)據(jù)中心內(nèi)，多個數(shù)據(jù)中心的物理主機通常為異構(gòu)主機，擁有不同的CPU，MEM大小.在分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓撲中，所有網(wǎng)絡(luò)設(shè)備和存儲設(shè)備不能獨立承載虛擬機，不具備相應(yīng)的計算和處理能力.

1.3 分配模型

根據(jù)分布式數(shù)據(jù)中心的虛擬機分配過程描述，本文的虛擬機分配目標是：均衡物理主機多維資源的分配，減少底層物理主機的使用數(shù)量，提升底層資源的利用率，節(jié)約數(shù)據(jù)中心的能源消耗.

分布式數(shù)據(jù)中心內(nèi)，虛擬機的分配過程是連續(xù)的，分配過程不斷循環(huán)，一次分配過程完成后另一次分配過程準備開始.在多次虛擬機分配過程中，物理主機負載狀態(tài)前后一致.單個物理主機可以在不同輪次的分配過程中承載多個虛擬機請求.為了均衡單個物理主機多維資源的均衡分配，必須在物理主機歷史負載狀態(tài)下考慮本輪分配，實現(xiàn)虛擬機分配后物理主機各維資源的剩余率均衡.

為了更好地描述物理主機多維資源的均衡情況，文中定義了請求匹配度HMatch的概念，描述當前虛擬機分配到物理主機后各維資源的使用情況.

1， （sur_cpu

公式（1）描述了虛擬機vmi分配到物理主機hostj后，物理主機剩余資源的均衡程度.其中，req_cpui，req_memi表示虛擬機vmi對CPU和MEM資源的請求大小.sur_cpuj，sur_memj表示物理主機hostj經(jīng)過多輪虛擬機分配后剩余的CPU和MEM資源大小.cab_cpuj，cab_memj表示物理主機hostj的原始CPU和MEM資源大小.本文僅考慮物理主機的CPU和MEM資源的分配均衡程度，暫未考慮存儲和I/O等資源.

此外，從式（1）可知，請求匹配度0≤HMatchij<2.當虛擬機vmi分配到物理主機hostj后，CPU和MEM的剩余資源占總資源的比值相同，則匹配度為0.否則，匹配度值大于0.剩余資源間越均衡，則匹配度值越小.通過匹配度的計算，可以快速獲取虛擬機分配對物理主機資源使用的影響，越小的資源匹配度，則說明物理主機資源的利用率越高，越能減少底層物理主機的數(shù)量，實現(xiàn)節(jié)約能耗的目的.

在式（2）中，Is_Newj描述了物理主機是否在歷史分配過程中承載了虛擬機.若當前物理主機是空閑物理主機，為承載任何虛擬機，則主機的剩余CPU和MEM能力與總資源能力相同.否則，剩余能力小于總資源能力.為了限制虛擬機隨意分配到新的空閑虛擬機，本文用整數(shù)1和2來分別描述當前物理主機的狀態(tài).

在虛擬機分配過程中，虛擬機請求數(shù)量與底層物理主機數(shù)量不同，本文定義0-1變量xij表示虛擬機vmi與物理主機hostj間的映射關(guān)系，見式（3）.

xij=1 ， vmi is maped to hostj 0 ，vmi is not maped to hostj（3）

在式（3）中，虛擬機vmi分配到物理主機hostj上，則xij為1；否則，xij為0.因此，分布式數(shù)據(jù)中心虛擬機分配的目標函數(shù)可以表示如下：

min ∑j∈Hosts∑i∈Vmsxij×HMatchij （4）

st.

for each vmi： ∑j∈Hostsxij≤1

for each hostj： ∑i∈Vmsxij×req_cpui≤cab_cpuj

∑i∈Vmsxij×req_memi≤cab_memj∑i∈Vmsxij×req_bwi≤cab_bwj

for each vmi ， hostj： 0≤HMatchij<2

在式（4）中，最小的物理主機匹配度表示所有虛擬機分配到物理主機后，物理主機剩余資源的均衡性最好，則其可以承載的虛擬機數(shù)量就越多，分配過程中使用的物理主機數(shù)量將減少，此外，當已使用的物理主機分配完之后，再將虛擬機分配到其他的空閑物理主機上，從而節(jié)約了數(shù)據(jù)中心能耗.表1為分布式數(shù)據(jù)中心虛擬機分配過程中的符號及相關(guān)術(shù)語.

2 基于層次拓撲樹的節(jié)能分配算法

針對分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓撲特點，結(jié)合分配模型，本節(jié)提出了一種基于層次拓撲樹的虛擬機節(jié)能分配算法，簡稱HTES.首先，HTES將分布式數(shù)據(jù)中心的大規(guī)模網(wǎng)絡(luò)拓撲進行分配，建立了層次拓撲樹，詳細描述見2.1節(jié)；其次，在層次拓撲樹的基礎(chǔ)上，根據(jù)用戶的地理位置，將虛擬機分配到網(wǎng)絡(luò)拓撲中的某個區(qū)域，保證占用的物理主機相對集中，均衡物理主機多維資源分配，減少物理主機使用數(shù)量，節(jié)約能耗，詳細的分配算法見2.2節(jié).

2.1 拓撲分割建立層次拓撲樹

分布式數(shù)據(jù)中心由多個地理位置分散的小型數(shù)據(jù)中心組成，整個網(wǎng)絡(luò)拓撲具有明顯的大規(guī)模性和隨機性.在虛擬機的分配過程中，需要為每個虛擬機尋找合適的物理主機，從而必須搜索網(wǎng)絡(luò)拓撲的所有物理主機.網(wǎng)絡(luò)拓撲的大規(guī)模給虛擬機的分配過程帶來了兩個難點：①增加了底層物理主機的搜索時間，降低了虛擬機的分配效率.②擴散了底層物理主機的占用分布.例如，同一用戶的多個虛擬機請求可能分配到不同地理位置的物理主機上，也可能分配到同一地理位置內(nèi)的距離位置較遠的多臺物理主機上.這種分散性給底層物理主機的管理和維護帶來了巨大困難，增加了節(jié)能策略的監(jiān)控難度.

針對以上兩個難點，本文對分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓撲進行逐級分割，建立層次拓撲樹.將整個拓撲轉(zhuǎn)化為層次結(jié)構(gòu)，保證每一層的節(jié)點數(shù)目逐層遞減.當進行虛擬機分配時，根據(jù)虛擬機的分配數(shù)量，找到相應(yīng)層級的拓撲子樹尋找物理主機，不用再掃描整個網(wǎng)絡(luò)拓撲，減少了物理主機的掃描時間，增加了虛擬機占用物理主機的集中度，便于虛擬機的快速分配和能耗節(jié)約.

為了進行網(wǎng)絡(luò)拓撲的分割，本文引入了規(guī)范割Normalized-cut（Ncut）和Laplacian矩陣，證明了Laplacian矩陣的第二特征值是2分Ncut的最優(yōu)解.

定義1 規(guī)范割Normalized-cut（Ncut）是衡量網(wǎng)絡(luò)拓撲中兩個節(jié)點子集間相似度的標準，公式如下：

NcutA，=cut（A，）vol（A，V）+cut（A，）vol（，V）

A∈V and ∈V（5）

cut（A，）=∑i∈A，j∈wij （6）

vol（A，V）=∑i∈A，j∈Vwij （7）

式中：V為網(wǎng)絡(luò)拓撲G中的節(jié)點集合；wij為網(wǎng)絡(luò)拓撲的鄰接矩陣W中的值，表示節(jié)點i與節(jié)點j間的權(quán)值.鄰接矩陣W為對稱矩陣，其中wij=wji0.使用規(guī)范割Ncut進行拓撲分割度量，能夠較好地避免小區(qū)域的產(chǎn)生.

定義2 Laplacian 矩陣是網(wǎng)絡(luò)拓撲圖的一種有效表示方式，一個Laplacian矩陣對應(yīng)一個非負權(quán)重的無向有權(quán)圖.Laplacian矩陣的常用表示如下：

Lsym=D-1/2LD-1/2=I-D-1/2WD-1/2（8）

式中：I為單位矩陣；D為網(wǎng)絡(luò)拓撲中節(jié)點的度矩陣；W為鄰接矩陣.每個節(jié)點的度di=∑njwij，表示與該節(jié)點相連的所有邊的權(quán)值和.

Laplacian矩陣具有如下特性：

1）任意n維向量f∈R，有：fΤLf=12∑ni，j=1wij×（fi-fj）2.

2）L為半正定矩陣.

3）L的最小特征值為0，對應(yīng)的最小特征向量為值1的常向量A.

4）L有n個非負實特征值0=λ1≤λ2≤…≤λn.

5）如果網(wǎng)絡(luò)拓撲G是C的連通部件，那么L有C個等于0的特征值.

根據(jù)Ncut和Laplacian矩陣的定義和性質(zhì)，可得Laplacian矩陣的第二特征值是2分Ncut的最優(yōu)解，證明過程如下：

證明 設(shè)劃分向量f如下：

f（vi）=vol（，V）vol（A，V） ， if vi∈A -vol（A，V）vol（，V） ， if vi∈

根據(jù)L的性質(zhì)1 ，得

fTLf=12∑ni，j=1wij（fi-fj）2=

12∑i∈A，j∈wij（fi-fj）2+12∑i∈A，j∈Awij（fi-fj）2+

12∑i∈，j∈Awij（fi-fj）2+12∑i∈，j∈wij（fi-fj）2=

12∑i∈A，j∈wij（fi-fj）2+12∑i∈，j∈Awij（fi-fj）2=

12cut（A，）vol（，V）vol（A，V） +vol（A，V）vol（，V） 2+

12cut（A，）-vol（，V）vol（A，V） -vol（A，V）vol（，V） 2=

cut（A，）vol（V，V）vol（A，V）+vol（V，V）vol（，V）=

vol（V，V）Ncut（A，）

此外：

fTDf=∑i∈Avol（，V）vol（A，V）divol（，V）vol（A，V）+

∑i∈-vol（A，V）vol（，V）di-vol（A，V）vol（，V）=

vol（，V）vol（A，V）∑i∈Adi+vol（A，V）vol（，V）∑i∈di=

vol（，V）vol（A，V）vol（A，V）+vol（A，V）vol（，V）vol（，V）=

vol（V，V）

將上述兩式結(jié)合，可得：NcutA，=fTLffTDf

根據(jù)L的性質(zhì)3，可得：

DfTA=∑ni=1difi=∑i∈Adivol（，V）vol（A，V）-

∑i∈divol（A，V）vol（，V）=

vol（A，V）vol（，V）vol（A，V）-

vol（，V）vol（A，V）vol（，V）=

vol（A，V）vol（，v）-

vol（，v）vol（A，V）=0

因此，Ncut的最小化：min f fTLffTDf

st.

fi∈vol（，V）vol（A，V），-vol（A，V）vol（，V）

DfTA=0

由于最小化的Ncut是一個廣義Rayleigh商，根據(jù)性質(zhì)可得λ1=0，D1/2A為其最小特征值，可得fTLf/fTDf的第二小特征值是Ncut的最優(yōu)解.

根據(jù)Laplacian矩陣與Ncut間的特性，本文將分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓撲轉(zhuǎn)化為Laplacian矩陣，然后對其求第二特征值，從而將網(wǎng)絡(luò)拓撲分割成耦合度最小的兩個子集.再依次對兩個子集進行拓撲分割，最終形成層次拓撲樹.圖3為網(wǎng)絡(luò)拓撲分割的過程.

從圖中可以看出，網(wǎng)絡(luò)拓撲的分割過程為2分迭代分割，通過多次迭代將網(wǎng)絡(luò)拓撲分割成2個子拓撲.在整個分割過程中，必須保持多個數(shù)據(jù)中心間地位位置的分散特性.因此，分布式數(shù)據(jù)中心的層次拓撲樹的第一層拓撲樹就是多個地理位置分散數(shù)據(jù)中心拓撲，不進行過細的劃分.此外，拓撲分割的目標是加快物理主機的搜索速度，減少分配時間，2分迭代分割必然出現(xiàn)最下層子拓撲中節(jié)點數(shù)量較少的情況.為此，本文設(shè)定了拓撲分割門限SplT和拓撲合并門限MerT.根據(jù)拓撲分割門限SplT判斷是否繼續(xù)進行網(wǎng)絡(luò)拓撲的分割.根據(jù)拓撲合并門限進行節(jié)點數(shù)小于MerT的子拓撲的合并.因此，拓撲分割門限SplT必須大于拓撲合并門限MerT.

因此，分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓撲分割的具體過程如下：①根據(jù)分布式數(shù)據(jù)中心內(nèi)小型數(shù)據(jù)中心的網(wǎng)絡(luò)拓撲，建立第1層子拓撲集，保持分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓撲間地理位置的分散特性；②逐個遍歷第1層子拓撲集，形成L矩陣，根據(jù)公式（8）進行第二特征值求解.根據(jù)求解結(jié)果計算相應(yīng)的特征向量.按照特征向量中得到的節(jié)點列表，將網(wǎng)絡(luò)拓撲分割成兩個子拓撲；③逐層遍歷所有子拓撲，生成下一層子拓撲集.當某個子拓撲中的節(jié)點數(shù)量少于最低分割門限SplT，不再進行下一層拓撲分割；④當所有拓撲分割完成后，遍歷最后一層的子拓撲集，將節(jié)點數(shù)少于MerT的子拓撲與其兄弟節(jié)點進行合并；⑤遍歷所有層的子拓撲，統(tǒng)計每層子拓撲中節(jié)點數(shù)量的范圍，結(jié)合層次號和地理位置（IP），建立索引方便查詢.算法1詳細描述了網(wǎng)絡(luò)拓撲分割建立拓撲樹的詳細過程.

算法1 網(wǎng)絡(luò)拓撲分割過程

輸入：網(wǎng)絡(luò)拓撲G，拓撲分割門限值SplT，拓撲合并門限值MerT.

輸出：層次拓撲樹TT.

Step1 初始化.

1）根據(jù)網(wǎng)絡(luò)拓撲G，生成相應(yīng)的鄰接矩陣W和度矩陣D.

2）初始化待分割的網(wǎng)絡(luò)拓撲集TS和子拓撲集STS為空.

3）初始化層次拓撲樹TT為空，層次序號IN為0.

4）根據(jù)網(wǎng)絡(luò)拓撲G和多個數(shù)據(jù)中心的地理位置分散關(guān)系，生成第1層子拓撲集，填充到STS，計算總節(jié)點數(shù)量VN.更新層次拓撲樹的頂層索引，包括層次序號、節(jié)點總數(shù)、子拓撲集合鏈接等，如下所示.更新完成后進入Step2，開始拓撲分割.insert 〈IN，VN，TS〉 to TTIN.

Step2 更新待分割拓撲集，將STS覆蓋TS，清空STS.更新當前層次拓撲樹的層號IN=IN+1.進入Step3開始拓撲分割.

Step3 判斷TS是否為空.TS為空，則進入Step5合并節(jié)點數(shù)目過小的子拓撲.否則，進入Step4，分割拓撲.

Step4 遍歷待分割拓撲集TS，生成子拓撲集STS.

1）計算子拓撲中節(jié)點數(shù)量VN.比較VN與分割門限SplT的大小.若大于，進入2）進行拓撲分割.若小于，則不進行拓撲分割.進行下一個子拓撲的計算.如果TS遍歷完成，進入Step2更新待分割拓撲集.

2）根據(jù)子拓撲G、鄰接矩陣W和度矩陣D，按照公式（8）生成L矩陣Lsym=I-D-1/2WD-1/2，其中I是單位矩陣.進入3）計算第二特征值.

3）根據(jù)L矩陣特性，計算（D-W）x=λDx的第二小特征值.根據(jù)特征值求得想要的特征向量f.按照特性向量中的節(jié)點，將子拓撲分割成兩個子集，加入STS中.進入4）更新層次拓撲樹.

4）計算中STS總節(jié)點數(shù)量VN，更新層次拓撲樹，如下所示.更新完成后重新進行1），分割下一個子拓撲.

insert 〈IN，VN，TS〉 to TTIN.

Step5 遍歷IN層子拓撲，判斷每個子拓撲中節(jié)點數(shù)量.若節(jié)點數(shù)量小于MerT，刪除當前子拓撲集和同一父節(jié)點的兄弟拓撲集.

2.2 區(qū)域性節(jié)能分配算法

根據(jù)分布式數(shù)據(jù)中心的網(wǎng)絡(luò)拓撲特性，在構(gòu)建層次拓撲樹的基礎(chǔ)上，本節(jié)提出了一種區(qū)域性虛擬機節(jié)能分配算法HTES.HTES的核心節(jié)能策略是減少底層物理主機的使用，通過關(guān)閉空閑物理主機實現(xiàn)節(jié)能.較傳統(tǒng)的相同策略節(jié)能算法[12]而言，HTES關(guān)注于分布式數(shù)據(jù)中心環(huán)境；根據(jù)用戶IP分組虛擬機請求，就近提供物理主機資源；分割網(wǎng)絡(luò)拓撲建立層次拓撲樹，快速尋找合適的物理主機；區(qū)域性分配虛擬機到底層集中的物理主機上，緩解了傳統(tǒng)零散分配帶來的難管理、難節(jié)能、難糾錯等缺點；考慮物理主機多維資源的均衡分配，提高底層物理主機的資源利用率.

本文采用區(qū)域性分配，將虛擬機分配到底層集中的物理主機上，緩解了物理主機分散帶來的節(jié)能和管理困難.區(qū)域性虛擬機節(jié)能算法的主要流程分為：虛擬機請求分組，物理主機搜索和區(qū)域性虛擬機均衡分配3個步驟.

虛擬機請求分組：①請求分組，根據(jù)虛擬機請求中IP地址屬性，按照層次拓撲中頂層節(jié)點的地理位置（IP），將虛擬機請求進行分組.分組完成后，所有虛擬機請求都在距離自己最近的數(shù)據(jù)中心隊列中.②并發(fā)分配，并發(fā)對多個虛擬機請求分組進行相應(yīng)的物理資源分配.

區(qū)域性物理主機搜索：①鎖定搜索層次.根據(jù)分組完成后的虛擬機請求個數(shù)V_size，查詢拓撲層次樹中空閑節(jié)點數(shù)量（物理主機）充足的子拓撲，保證子拓撲的空閑數(shù)量大于虛擬機請求數(shù)量α倍，更加均衡地分配虛擬機，均衡物理主機的多維資源.②比較資源能力.比較虛擬機請求大小與空閑物理主機的剩余能力，選擇剩余能力大于請求大小的物理主機.若物理主機搜索成功，數(shù)量等于α×V_size，則進行虛擬機分配.否則，遍歷當前子拓撲的父親拓撲，再次搜索合適數(shù)量的主機，直到找到α×V_size個物理主機為止.③請求遷移.如果當前頂層拓撲內(nèi)所有空閑物理主機數(shù)量小于V_size，則分配相應(yīng)數(shù)量的虛擬機請求，并將多余的虛擬機請求移動到鄰近的數(shù)據(jù)中心隊列中，等待分配.如果鄰近數(shù)據(jù)中心內(nèi)資源同樣不足，則繼續(xù)遷移到其他數(shù)據(jù)中心.如果整個網(wǎng)絡(luò)拓撲資源不足，則返回最近數(shù)據(jù)中心等待其他虛擬機釋放資源.

均衡分配：根據(jù)虛擬機請求隊列和相應(yīng)的物理主機隊列，進行虛擬機的最終分配.按照公式（1）的定義，將虛擬機分配到請求匹配度最好的物理主機上，完成分配過程.

圖4展示了基于層次拓撲樹的虛擬機節(jié)能分配算法過程.從圖中可以看出，虛擬機的分配過程主要分為虛擬機請求分組、根據(jù)層次拓撲樹搜索物理主機和虛擬機分配3個步驟.分布式數(shù)據(jù)中心由2個地理位置分散的小型數(shù)據(jù)中心A和B組成.4個用戶在不同的位置向數(shù)據(jù)中心提交了7個虛擬機請求.根據(jù)用戶IP和物理中心的位置，V1-V4虛擬機請求分配到了A，V5-V7分配到了B.根據(jù)虛擬機請求的數(shù)量，并發(fā)從A和B中尋找合適數(shù)量的子拓撲，進行虛擬機的分配，正如V1，V3-V7所示.然而，當子拓撲的可用物理主機數(shù)量小于虛擬機請求數(shù)量時，從其父節(jié)點的拓撲中尋找其他物理主機進行分配，如V2所示.在整個虛擬機的分配過程中，根據(jù)虛擬機請求與物理主機的匹配度公式（1），進行物理主機的分配.如圖中V1，V3，V4分配到了原拓撲的物理主機，V2因其匹配度較差從而分配到了原拓撲的父節(jié)點.整個節(jié)能分配算法HTES的分配過程如算法2所示.

算法2 基于層次拓撲樹的虛擬機節(jié)能分配算法

輸入：網(wǎng)絡(luò)拓撲G，虛擬機請求列表Vms

輸出：虛擬機分配結(jié)果.

Step1 初始化.根據(jù)網(wǎng)絡(luò)拓撲G，利用算法1生成層次拓撲樹TT，監(jiān)控數(shù)據(jù)中心所有物理主機的使用情況.

Step2 虛擬機請求分組.

1）根據(jù)虛擬機的IP和數(shù)據(jù)中心位置，將虛擬機分配到位置最近的數(shù)據(jù)中心排隊隊列中.

2）分配完成后，并發(fā)對多個數(shù)據(jù)中心進行虛擬機的分配.

Step3 區(qū)域性搜索物理主機.

1）根據(jù)分組完成后的虛擬機請求個數(shù)V_size，查詢拓撲層次樹中空閑節(jié)點數(shù)量（物理主機）充足的子拓撲，保證子拓撲的空閑數(shù)量大于虛擬機請求數(shù)量α倍.

2）比較虛擬機請求大小與空閑物理主機的剩余能力，選擇剩余能力大于請求大小的物理主機.

3）若物理主機搜素成功，數(shù)量等于α×V_size，進入Step5進行虛擬機分配.否則，遍歷當前子拓撲的父親拓撲，再次搜索合適的數(shù)量主機，直到找到α×V_size個物理主機為止.

4）當遍歷到頂層拓撲，搜索完整個小數(shù)據(jù)中心的所有物理主機，物理主機數(shù)量不滿足V_size時，進入Step4進行虛擬機請求的遷移.

Step4 虛擬機請求的遷移.

1）當頂層拓撲內(nèi)所有空閑物理主機數(shù)量小于V_size，則分配空閑主機數(shù)量的虛擬機請求，并將多余的虛擬機請求遷移到鄰近的數(shù)據(jù)中心隊列中，等待分配.

2）如果整個網(wǎng)絡(luò)拓撲資源不足，則返回最近數(shù)據(jù)中心等待其他虛擬機釋放資源.

Step5 均衡分配虛擬機.按照公式（1）的定義，根據(jù)請求匹配度的大小，將虛擬機分配到最好的物理主機上，均衡物理主機的多維資源，完成分配過程.

3 實驗結(jié)果分析

為了驗證HTES算法的性能，本文使用CloudSim3.5[17]作為仿真平臺，將HTES算法與貪婪算法GRD[18]，蟻群算法ANT[19]和DCEERS[12]算法進行比較，從分配時間、物理主機數(shù)量、物理主機異構(gòu)使用情況等方面進行了性能驗證.

3.1 實驗環(huán)境

在CloudSim平臺上，利用brite網(wǎng)絡(luò)拓撲圖生成工具，隨機生成10個地理位置分散的數(shù)據(jù)中心網(wǎng)絡(luò)拓撲，拓撲中包括1 000個物理主機和200個網(wǎng)絡(luò)設(shè)備.表2為物理主機參數(shù)表.

此外，利用Cloudsim平臺中的DataCenter，Host，Vm，DataCenteBoker等多個類，構(gòu)建相應(yīng)的1 000個物理主機屬性信息和模擬對應(yīng)的虛擬機請求信息.仿真了4種類型的物理主機模擬數(shù)據(jù)中心的異構(gòu)特性：[〈4core-8g〉，〈8core-8g〉，〈8core-16g〉，〈16core-24g〉].同樣利用隨機的方式，模擬不同用戶在不同IP下的虛擬機請求，虛擬機請求數(shù)量從10～500隨機波動.每個虛擬機的資源請求大小為CPU[1～4]，內(nèi)存為[1～10]×512 M.

3.2 參數(shù)設(shè)置

本節(jié)對實驗中的參數(shù)值拓撲分割門限值SplT，拓撲合并門限值MerT和虛擬機分配算法中的α參數(shù)進行討論及測試.在網(wǎng)絡(luò)拓撲分割的過程中，本文通過設(shè)定拓撲分割門限SplT和拓撲合并門限MerT來處理2分迭代分割出現(xiàn)的最下層子拓撲中節(jié)點數(shù)量較少的情況.本文通過固定合并門限，變動分割門限，或者固定分割門限，變動合并門限，通過不同的門限取值，觀察不同設(shè)置下平均虛擬機分配時間.在網(wǎng)絡(luò)拓撲中，對物理主機的搜尋速度越快，則相應(yīng)的虛擬機分配時速會更快.因此實驗測試中，測試100個虛擬機請求的分配，設(shè)置拓撲分割門限值SplT（10～20），合并門限值MerT（0～5）時，從表3中可以看出，拓撲分割門限值SplT（15～16），拓撲合并門限值MerT（2～3）時，此時拓撲結(jié)構(gòu)下物理主機的搜尋速度最快，虛擬機平均分配時間最少，顯示出良好的分配性能.

參數(shù)α是從子拓撲空閑物理主機數(shù)與虛擬機請求數(shù)量的比值.如果從子拓撲空閑物理主機中等同于虛擬機請求數(shù)量，則虛擬機的分配情況唯一，這種分配并非最優(yōu).因此從子拓撲空間選擇空閑物理主機數(shù)量是要大于虛擬機的請求數(shù)量.本文在仿真實驗中，設(shè)置固定虛擬機數(shù)為100，變動α取值為1.0～2.0，從網(wǎng)絡(luò)拓撲中，搜尋虛擬機請求數(shù)量α倍的物理主機，表4給出了部分實驗數(shù)據(jù)，可以看出，α取值為1.2～1.5時，物理主機的平均利用率較高，浪費率較低.

通過對表3和表4的分析可知，當拓撲分割門限值SplT（15～16）且拓撲合并門限值MerT（2～3）時，算法擁有較快的物理主機搜尋速度；當α取值為1.2～1.5時，物理主機的平均利用率較高，浪費率較低.

3.3 實驗結(jié)果

本次實驗從虛擬機分配時間、資源均衡度、資源浪費度、能耗和物理主機數(shù)量等5個方面對HTES算法進行驗證.

圖5為4種算法在不同虛擬機數(shù)量下的分配時間對比.從圖4可以看出，隨著虛擬機數(shù)量的不斷增加（10～200），分配時間快速增大.在4種算法中，GRD算法的分配時間最少，其次是HTES算法，ANT算法時間最多.在4種算法中，GRD算法隨機分配虛擬機，將虛擬機分配到空閑資源最大的物理主機上，不考慮其他目標，其分配速度最快.HTES、DCEERS和ANT以節(jié)能和提升底層資源利用率為虛擬機分配的目標，通過不同的分配策略實現(xiàn)節(jié)能，分配時間較GRD算法而言有所增加.HTES算法在3種算法中分配時間最快.因為，HTES算法將分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓撲進行分割，建立層次拓撲樹，生成索引.根據(jù)用戶IP將虛擬機請求分組，快速掃描層次拓撲，查詢物理主機，將虛擬機請求集中的分配到底層物理主機，加快了分配效率，減少了物理主機的使用數(shù)量，節(jié)約了能耗；DCEERS算法將虛擬機分配問題看做最小商品流問題，通過Benders分解進行虛擬機分配，利用最小數(shù)量的物理主機承載虛擬機請求，同樣減少了物理主機的數(shù)量，節(jié)約了能耗；ANT算法利用蟻群策略求解多目標虛擬機的分配問題，同時優(yōu)化底層資源的利用和能耗.然而ANT算法需要大量的迭代尋找最優(yōu)，分配時間上較差.

物理主機內(nèi)CPU和內(nèi)存資源的均衡率對比如圖6所示.從圖6可以看出，隨著虛擬機請求數(shù)量的不斷增加（10～200），4種算法的資源均衡程度不斷變化.其中，HTES算法均衡率最好，ANT和DCEERS較差，GRD最差.當虛擬機請求數(shù)為10～50時，GRD和ANT的資源均衡逐級下降，HTES和DCEERS兩種算法圍繞0.65和0.6兩條水平線上下波動.當虛擬機請求數(shù)超過50時，ANT和GRD的均衡率稍微回升，DCEERS則開始下降，HTES相對平穩(wěn)且有所提升.在各種虛擬機請求數(shù)量下，HTES都擁有較好的資源均衡率.因為，HTES在進行虛擬機分配時，需要根據(jù)公式（1）計算虛擬機與物理主機間的匹配度，將虛擬機分配到合適的物理主機上，均衡物理主機多維資源的利用率；DCEERS和ANT算法在嘗試用最小的物理主機分配最多的虛擬機，隨著虛擬機數(shù)量的增加，造成物理主機間資源的不均衡；GRD算法隨機分配虛擬機，當虛擬機數(shù)量較小時，占用底層高性能的物理主機，造成物理主機內(nèi)的資源分配不均衡.隨著虛擬機數(shù)量增加，高性能物理主機的資源利用率提升，各維資源的均衡度相應(yīng)增加.

圖7展示了4種算法的資源浪費情況.圖中資源的浪費率是指CPU和內(nèi)存浪費率的均值，從圖7可以看出，在不同虛擬機請求數(shù)量下（10～200），4種算法的資源浪費率不斷變化，HTES算法浪費率最小，其次是DCEERS和ANT，GRD算法最大.在虛擬機數(shù)量較小時（10～30），HTES，DCEERS和ANT 3種算法的資源浪費率相近，HTES略差于DCEERS和ANT算法.隨著虛擬機數(shù)量的不斷增加，HTES算法的浪費率明顯優(yōu)于其他3種算法.因為，GRD算法的隨機分配策略，并未考慮任何資源均衡目標，其分配時間快，資源浪費率高.DCEERS和ANT通過蟻群和Benders分解，在優(yōu)化虛擬機分配的同時，提高了資源利用率，節(jié)約了能耗；但是兩者并未考慮物理主機多維資源的均衡分配問題.HTES算法利用公式（1），在區(qū)域性分配虛擬機的同時，均衡地分配物理主機的多維資源（CPU和MEM），在提升底層資源利用率的同時，降低了各維資源的浪費率.

圖8為4種算法在不同數(shù)量虛擬機下占用物理主機的單位時間能耗情況，物理主機單位時間能耗是指虛擬機占用的所有物理主機功耗之和.從圖8可以看出，隨著虛擬機數(shù)據(jù)的不斷增加（10～350），單位時間的功耗快速加大.4種算法中GRD算法功耗增加最快，ANT和DCEERS的功耗比較接近，HTES算法的功耗最小.當虛擬機的數(shù)量為10～150時，其功耗增加速率相對較慢，4條趨勢線的坡度比較緩，HTES算法功耗增加速度最慢.然而，隨著虛擬機數(shù)量的不斷增加，4種算法的功耗急速增加，坡度加大，HTES算法的功耗逐漸接近ANT和DCEERS算法.因為HTES算法、ANT和DCEERS算法都是通過提供資源利用率，減少底層物理主機使用數(shù)量來節(jié)約能耗.HTES算法額外考慮了物理主機多維資源均衡分配問題，進一步提升了物理主機的資源利用率.然而，隨著虛擬機數(shù)量的不斷增加，底層物理主機的空閑數(shù)量不斷減少，單位時間產(chǎn)生的功效必然增加，最終變?yōu)橐恢拢ㄋ形锢碇鳈C都在使用）.

圖9為4種算法對底層異構(gòu)物理主機的使用情況.從圖9可以看出，4種算法在相同虛擬機數(shù)量下占用的物理主機類型和數(shù)量各不相同.在4種算法中，GRD算法偏向于占用高性能物理主機.在虛擬機數(shù)量較小（80～150）時，G4[16c，24g]類型的物理主機被全部占用.隨著虛擬機數(shù)量的增加（150～300），G3[8c，16g]類型的物理主機被快速占用；相反，HTES算法偏向于使用低性能的物理主機.在虛擬機數(shù)量較?。?0～150）時，G1[4c，8g]和G2[8c，8g]類型的物理主機被占用.隨著虛擬機數(shù)量的增加（150～300），G3[8c，16g]和G4[16c，24g]類型的物理主機少量被占用；ANT和DCEERS算法則相對比較均衡，在各種虛擬機數(shù)量下，均衡占用G1[4c，8g]，G2[8c，8g]，G3[8c，16g]和G4[16c，24g]類型的物理主機.HTES算法喜好占用低性能物理主機特性更方便進行分布式數(shù)據(jù)中心的節(jié)能.

4 結(jié) 論

針對虛擬機分配中物理主機多維資源的浪費問題，結(jié)合分布式數(shù)據(jù)中心網(wǎng)絡(luò)拓撲的大規(guī)模性和地理位置的不同，本文提出了一種基于層次拓撲樹的虛擬機節(jié)能分配算法.首先，將大規(guī)模網(wǎng)絡(luò)拓撲按照地理位置的不同，劃分成多個頂層子拓撲.其次，利用Laplacian矩陣和Ncut的特性，進行迭代二分切割，建立層次拓撲樹.然后，根據(jù)虛擬機請求IP地址與數(shù)據(jù)中心位置的遠近，將虛擬機請求分組，根據(jù)分組中虛擬機數(shù)量檢索層次拓撲樹，快速查詢合適的區(qū)域性物理主機集合.最后，根據(jù)虛擬機請求與物理主機間的匹配度均衡分配物理主機的多維資源，提高了資源利用率，減少底層物理主機使用數(shù)量，通過關(guān)閉空閑物理主機實現(xiàn)了數(shù)據(jù)中心的節(jié)能.文中將HTES算法與GRD算法、DCEERS算法和ANT算法進行比較，從虛擬機分配時間、資源均衡率、能耗和物理主機使用情況等方面驗證了HTES算法的性能，表明HTES算法適合于分布式數(shù)據(jù)中心.

參考文獻

[1] ZHAO J， LI H， WU C， et al. Dynamic pricing and profit maximization for the cloud with geo-distributed data centers[C]//Conference on Computer Communications.Toronto： IEEE， 2014： 118-126.

[2] TUDORAN R， COSTAN A， WANG R， et al. Bridging data in the clouds： an environment-aware system for geographically distributed data transfers[C]//Cluster， Cloud and Grid Computing （CCGrid）， 2014 14th IEEE/ACM International Symposium on. Chicago：IEEE，2014： 92-101.

[3] ALICHERRY M， LAKSHMAN T V. Network aware resource allocation in distributed clouds[C]//INFOCOM.Orlando： IEEE，2012： 963-971.

[4] ISLAM M A， REN S， PISSINOU N， et al. Distributed temperature-aware resource management in virtualized data center[J].Sustainable Computing： Informatics and Systems， 2015（6）： 3-16.

[5] KO Y M， CHO Y. A distributed speed scaling and load balancing algorithm for energy efficient data centers[J]. Performance Evaluation， 2014， 79： 120-133.

[6] 鄧子云，章兢，白樹仁，等.基于超級計算的 CAE 集成平臺架構(gòu)設(shè)計[J].湖南大學學報：自然科學版，2013，40（7）： 80-85.

DENG Ziyun， ZHANG Jing， BAI Shuren，et al.Architectural design of CAE integration platform based on super computation[J]. Journal of Hunan University： Natural Sciences，2013， 40（7）： 80-85.（In Chinese）

[7] GEORGIOU S， TSAKALOZOS K， DELIS A. Exploiting network-topology awareness for VM placement in IAAS clouds[C]//Cloud and Green Computing （CGC）， 2013 Third International Conference on. Karlsruhe： IEEE， 2013： 151-158.

[8] PENG Y， YUAN Y， HUANG X， et al. Research on maintainability of network topology for data centers[C]//2014 Sixth International Conference on Ubiquitous and Future Networks （ICUFN）. Shanghai： IEEE， 2014： 317-321.

[9] SHIRAYANAGI H， YAMADA H， KENJI K. Honeyguide： a VM migration-aware network topology for saving energy consumption in data center networks[J]. IEICE Transactions on Information and Systems， 2013， 96（9）： 2055-2064.

[10]JAIN N， MENACHE I， NAOR J S，et al. Topology-aware VM migration in bandwidth oversubscribed datacenter networks[M].Berlin Heidelberg： Springer Berlin Heidelberg，2012：586-597.

[11]JIN H， CHEOCHERNAGNGARN T，LEVY D，et al.Joint host-network optimization for energy-efficient data center networking[C]// Parallel & Distributed Processing （IPDPS）， 2013 IEEE 27th International Symposium on. Boston ： IEEE， 2013： 623-634.

[12]SHUJA J， BILAL K， MADANI S A， et al. Data center energy efficient resource scheduling[J]. Cluster Computing， 2014， 17（4）： 1265-1277.

[13]HAMMADI A， MHAMDI L. A survey on architectures and energy efficiency in data center networks[J]. Computer Communications， 2014， 40： 1-21.

[14]MOGHADDAM F A， LAGO P， GROSSO P. Energy-efficient networking solutions in cloud-based environments： a systematic literature review[J]. ACM Computing Surveys （CSUR）， 2015， 47（4）：1-32.

[15]BELOGLAZOV A， ABAWAJY J， BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future Generation Computer Systems， 2012， 28（5）： 755-768.

[16]GU L， ZENG D， GUO S，et al.Joint optimization of VM placement and request distribution for electricity cost cut in geo-distributed data centers[C]//Computing， Networking and Communications （ICNC）， 2015 International Conference on. Garden Grove： IEEE， 2015： 717-721.

[17]BUYYA R， RANJAN R， CALHEIROS R N. Modeling and simulation of scalable Cloud computing environments and the CloudSim toolkit： challenges and opportunities[C]// High Performance Computing & Simulation，HPCS'09，International Conference on. Leipzig： IEEE， 2009： 1-11.

[18]MILLS K， FILLIBEN J， DABROWSKI C. Comparing VM-placement algorithms for on-demand clouds[C]// Cloud Computing Technology and Science （CloudCom）， IEEE Third International Conference on. Athens ： IEEE， 2011： 91-98.

[19]GAO Y， GUAN H， QI Z， et al. A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[J]. Journal of Computer and System Sciences， 2013， 79（8）： 1230-1242.