基于CSP的能耗高效云計算資源調度模型與算法

林偉偉，劉波，朱良昌，齊德昱

(1. 華南理工大學 計算機科學與工程學院，廣東 廣州 510006；2. 華南師范大學 計算機學院，廣東 廣州 510631)

1 引言

隨著云計算技術的發展和云應用的普及，云計算現在已經被越來越多的企業接受，并同時對其展開了廣泛的研究[1]。最近幾年，隨著計算機系統電能消耗的不斷增加，能源的高效利用已經成為現代計算機系統(如數據中心和云端)的一個非常重要的研究內容[2]。近期，有一些關于云計算的資源提供與云計算資源管理的研究，其中GARG等[3]提出一種接近最優的調度策略，該策略利用橫跨不同數據中心之間的數據為云提供者服務。他們考慮了許多影響能源效率的因素(例如：能源消耗、碳排放速度、工作量、CPU功耗效率)，這些因素依據其位置、結構設計和管理系統的不同而在各個數據中心進行變化。為了解決這一問題，出現了一些基于裝箱問題部署虛擬服務器的優化方法，在一些文獻中有其具體的描述[4～8]，關于虛擬機的部署問題就被建模為裝箱問題。然而，目前提出的面向能耗優化的調度方法大部分是針對同構服務器的調度[7,9～13]，但是，由于現有的數據中心服務器的采購時間不同、使用年限不同及品牌不同等異構性，比如文獻[13]描述的數據中心的服務器往往是異構的，因此，目前提出的大部分同構服務器調度方法不能很好地應用在一般的云計算數據中心的能耗管理中。

為此，本文針對異構物理服務器的能耗優化資源調度問題進行研究，利用約束滿足問題[14]對異構物理服務器的能耗優化資源調度問題建模，并基于Choco[15]約束編程求解建立的能耗優化資源分配模型，能夠減少虛擬化的云數據中心的服務器能源消耗。然后，設計了資源調度算法來實現該優化配置方案。最后，使用Choco模擬實驗進行算法評價，實驗結果表明提出的模型和算法在能耗方面明顯優于已有的資源調度方法。

2 相關研究

減少能源的消耗對于資源供應商減少成本和利潤最大化來說非常重要[16,17]。BELOGLAZOV等[18]提出了一種用于虛擬機化云計算數據中心的有效的資源管理系統，它可以減少運營成本并提供所需的服務質量。節約能源是通過虛擬機不斷地依據當前的資源利用率以及虛擬機和熱狀態下的計算節點之間建立的虛擬拓撲網絡結構來進行整合的。RODERO等[19]為高性能計算和虛擬化計算平臺提出了一種能量感知型的網絡配置方法。能源效率的提高是通過工作量的感知，恰到好處地動態配置機制以及通過關閉主機系統中沒有映射虛擬機的子系統方法來實現的。ABDELSALAM等[20]創建了一個用于云計算環境，主要服務于客戶的如Web服務一樣的交互式應用的電力管理數學模型，這個數學模型計算服務器的最優數量和它們應該運行的頻率。文獻[21]中，作者提出了一個提供高效、綠色、強化的可擴展的云計算架構的新框架。通過使用電力調度技術、可變的資源管理、實時調度和最小化的虛擬機設計等技術，使基于最小化云開銷的數據中心系統的整體功效得到了改善，CHANG等[22]對云資源的優化配置進行了研究。他們制定了關于計算能力和其他資源的多樣性的資源分配問題。他們提出了一個可證明的在多項式時間內得到接近最優解的近似算法。然而現今的方法大都考慮的是給予的每個物理機節點上有著相同的物理參數，如CPU速度、硬盤容量、內存等。

此外，絕大部分方法僅將處理器作為唯一值得考慮的資源，而拋棄了其他一些同樣很重要的資源，例如內存和存儲空間。這樣就導致由于工作量大量聚集在同一個節點而形成瓶頸，導致性能的下降以及能量消耗的增加，這個在文獻[23]中有所提及。在運行時虛擬機實現再分配的能力，可以動態地配制工作量，同時可以使虛擬機實現重新部署，使運行的物理機節點達到最小，而空閑節點則切換為省電模式。然而虛擬機的遷移會導致時間延遲、額外的性能開銷以及功耗，所以需要通過仔細分析和智能技術消除這些因工作量變化而導致的非生產性的遷移[2]。

裝箱問題是一個著名的NP組合難題，已提出許多啟發式和貪心算法來解決這難題[9,24]。一些啟發式算法，例如first-fit decreasing (FFD)[10]、best-fit decreasing(BFD)[10]和modified best fit decreasing(MBFD)[25]都被提出來和應用在數據中心的虛擬機調度中[4～8]。這些方法大部分是針對同構服務器的調度，不能很好地應用在一般的異構云計算數據中心的資源調度和能耗管理中。CSP(約束滿足問題)[26]：由一個變量集合和一個約束集合組成；問題的一個狀態是由對一些或全部變量的一個賦值定義的；問題的解是滿足所有約束的完全賦值，或更進一步，使目標函數最大化。約束滿足問題作為人工智能研究的一個基本問題，在許多實際問題中都得到了廣泛的應用，特別是調度中的資源分配問題。為此，本文主要是針對物理服務器異構的云數據中心的資源調度問題進行研究，給出異構物理服務器環境下的能耗優化的資源調度模型和算法，減少云數據中心的能源消耗。

3 基于CSP的能耗優化資源分配模型

3.1 問題描述

最直觀的節能減排方式就是關閉利用率不高的服務器，在傳統模式中，一個應用運行在一個服務器上，關閉服務器就等于關閉了應用；然而，服務器虛擬化為解除應用與物理服務器的綁定提供了可能，在負載低谷期，管理員可以將原來運行在各個服務器上的應用整合到較少的幾臺服務器上，關閉空閑的服務器，已達到綠色節能的目的。因而，一般能耗中的優化問題就是最小化物理主機數；但是，在考慮物理主機異構的情況，由于每個物理主機都有不同能耗，此時，能耗優化的問題并不是最小物理主機數。下面舉個例子進行具體說明。

物理服務器和虛擬機的資源大小及能耗參數如圖1所示，其中Dy1～3表示當虛擬機VM1～3分配到該物理節點時產生的動態能耗。待部署的虛擬機以及其參數如圖2所示。假設需要將這3臺虛擬機部署在這3個物理節點上。如果采用最小主機數策略，3臺物理機都應該分配到PM1上，這時的總能耗為650 W；若將VM1和VM2部署在PM2上，VM3部署在PM3上，則總能耗為420 W，可見，在物理主機異構的情況下，能耗的優化問題并不是最小物理主機數，而是綜合能耗最小。針對上述問題，本文提出了一個基于CSP的能耗優化的云資源調度框架，該框架的系統架構如圖2所示。

圖1 物理服務器與虛擬機的資源大小及能耗參數

圖2 基于CSP的能耗優化的云資源調度框架

從圖2可以看出，提出的基于CSP的能耗優化的云資源調度框架由應用程序檢測、虛擬機配置和虛擬機部署3個模塊組成。本文將在3.2節～3.4節分別對各模塊進行詳細描述。在詳細描述之前，先對部分符號進行如下說明。

3.2 應用程序監測模塊

該模塊首先測出各應用程序當前的負載，然后根據當前負載和 SLA目標確定分配給各應用程序的資源(CPU、memory、network)。對于應用程序ai，其分配的資源可以定義為當前負載和SLA目標的函數，即：Ri= fi(Li,Si)，其中，Li為應用程序ai的當前負載，Si為應用程序的SLA目標，Ri為分配給應用程序的資源，它是(CPU、memory、network)三元組。對于分配給應用程序ai的資源與其當前負載和SLA目標的函數關系fi，本文沒有做出基于經驗的或基于實驗的假設，它可以由各數據中心的管理者根據相應的管理政策、經驗以及大量實驗數據而確定。

下面以 VAN等人[11]關于自動化虛擬資源管理研究中提到的一個基于實驗數據的經驗主義的性能模型(如圖 3所示)為例，對應用程序監測模塊進行簡單說明。

圖3 性能模型

水平軸表示應用程序每秒的請求量，即工作負載；垂直軸表示響應時間；圖中的斜線表示特定CPU能力下響應時間與每秒請求數的關系。假設應用程序A是一個Web應用程序，其SLA目標是請求的響應時間，假設其值為100 ms，若此刻應用程序A的負載為每秒300次請求，則根據圖3所示的關系可以得出分配給應用程序A的CPU能力至少為10 000 MHz。

當然，上面只是一個可能的簡單示例，不同應用程序的應用程序有著不同的 SLA目標、不同類型的工作負載以及它們之間的不同函數關系。在提出的模型中，沒有對這些性質做任何可能的假設，它們應該由數據中心管理員根據不同類型的應用程序，基于經驗或實驗數據對這些性質進行描述與設定。

3.3 虛擬機配置模塊

該模塊根據應用監測程序模塊輸出的分配給各應用程序的資源向量R=(R1,…, Rj,…, Rc)為各應用程序分配虛擬機，使總的分配代價最小。換句話說，該模塊的目的是給出使目標函數(1)最小化的各應用程序的虛擬機分配向量為

其中，m為應用程序的數目，cost為虛擬機的操作開銷向量，每一項對應于每一類虛擬機的分配開銷，Ni為分配給應用程序i的虛擬機向量，并且Ni=（ni1,…,nij,…, nic），而nij為分配給應用程序 i的第j類虛擬機的數量，cost·Ni則表示分配虛擬機向量Ni給應用程序i的開銷。

根據本文的假設，數據中心中每類虛擬機的數目是有限的，即擁有一個上限閾值，下面定義各類虛擬機的閾值向量為：Nmax=(n1max,…, njmax,…, ncmax），且有如下關系

分配給各應用程序資源量應滿足應用程序監測模塊確定的資源要求，即

同時，部署在物理機上的所有虛擬機的資源總量不能超過所有物理機的資源總量，故有如下關系

采用約束編程的方法對上述模型進行求解，即可獲總花費最小的虛擬機分配向量，每一個虛擬機分配向量對應于各應用程序的虛擬機分配情況，即分配了哪類虛擬機及各類虛擬機分配的數量。

3.4 虛擬機部署模塊

虛擬機部署模塊將虛擬機分配模塊產生的虛擬機分配向量N作為輸入，然后將虛擬機分配向量N整合為表示當前所有需要運行的虛擬機集合的向量VM = (vm1,…,vmi,…,vmp)，其中，vmi= (vmiCPU, vmimemory,vminetwork)。同時數據中心提供每臺物理主機的動態能耗參數。在描述物理資源約束前，先給出虛擬機放置的定義。

位向量Hi的定義為：?pi∈P，Hi= (hi1,…,hij,…, hip)，hij=1當且僅當虛擬機vmj部署在物理機pi上。

對于每臺物理機和其上部署的虛擬機有如下的約束關系

根據文獻[28]可知，物理服務器的能耗為空閑時產生的能耗和其上運行的應用所產生的能耗之和為E = Edynamic+ Estatic，其中 Estatic表示物理機空閑時的能耗（即沒有分配虛擬機時的能耗，物理服務器 pi上的空閑能耗用 Eistatic表示），假設物理機 pi上放置各虛擬機資源時新增能耗的向量為 Eidynamic=(ei1,… ,eik)，而 Edynamic為放置在物理服務器 pi上所有虛擬機新增能耗之和 H ?Edynamic。因此，可以建立異構服務器的

i i能耗最優（小）的資源調度模型為

其中，Ei為物理服務器 pi的能耗。由此可以得出關于能耗的約束條件為

其中， EiM

ax為物理服務器 pi所能承載的最大能耗值，即物理服務器ip的實際能耗大小必須小于等于MaxiE 。

4 算法設計

4.1 虛擬機配置算法

4.1.1 算法描述

虛擬機配置算法的基本思想是為需要部署的應用搜索操作開銷最小的虛擬機，并輸出分配的虛擬機向量。首先將虛擬機配置問題表示成 CSP問題，采用最佳優先和剪枝的策略對其進行搜索求解。對于任一待擴展節點，如果到達該節點的路徑對應的花費大于或等于最小花費值，則停止對該節點的擴展；否則，則繼續擴展該節點，若該節點是最后的葉節點，則更新最小花費的值；最終返回使花費最小的虛擬機分配向量。

4.1.2 算法偽代碼

算法偽代碼如下所示。

1) Input ∶ pmList,vmList, AE,wights

2) Output ∶ allocation vector of VM

3) minCost MAX

4) queue new priority_queue()

5) root new node()

6) queue.push(root)

7) while queue is not empty do

8) parent queue.top()

9) queue.pop()

10) cost estimateCost(root);

11) if cost ＞ = minCost then continue

12) app the next application in AE

13) if app == NULL then

14) minCost cost

15) else

16) foreach vm in vmList do

17) if constraints are satisfied then

18) allocate vm to app

19) child new node(root,app)

20) queue.push(child)

21) return allocation vector of VM that minimizes allocation cost

4.1.3 算法性能分析

在虛擬機配置模塊中，假定應用程序數為m，預定義的虛擬機種類數為 c，對于每一類虛擬機都有一個允許被分配的最大數目，設d是所有這些最大數目中的最大值，則對于每個應用程序，可以分配的虛擬機數量最多為cd；根據式(2)～式(8)可知，一共有3m+c+1個約束條件；根據RIVIN等人關于CSP代數求解的研究[27]，對于一個有n個變量，每個變量取值數為m以及M個約束條件的CSP問題，其算法復雜度為O(nm·2M-n)，故虛擬機配置模塊的算法復雜度為O (cdm·22mfc)。

4.2 虛擬機部署算法

4.2.1 算法描述

虛擬機部署算法的基本思想是為需要創建的虛擬機搜索能耗最小的物理主機分配向量，并輸出分配的物理主機向量。將虛擬機部署模塊也表示成CSP問題，采用最佳優先和剪枝的策略來對其進行求解。在搜索前，首先需要對虛擬機分配向量進行重整，使之成為包含所有待分配虛擬機的簡單向量。在搜索中，對于任一待擴展節點，如果到達該節點的路徑對應的能耗大于或等于最小能耗值，則停止對該節點的擴展；否則，則繼續擴展該節點，若該節點是最后的葉節點，則更新最小能耗的值，最終返回使能耗最小的虛擬機放置向量。

4.2.2 算法偽代碼

算法偽代碼如下所示。

1) Input ∶ pmList, allocation vector N, dyList

2) Output ∶ placement vector of VM

3) VM collapses(N) //collapses N into a single vector VM = (vm1,…, vmp)

4) minPower upperbound(pmList,VM,dyList)

5) queue new priority_queue()

6) root new node()

7) queue.push(root)

8) while queue is not empty do

9) parent queue.top()

10) queue.pop()

11) power = estimatePower(root);

12) if power ＞ = minPower then continue

13) vm the next virtual machine in VM

14) if vm == NULL then

15) minPower power

16) else

17) foreach pm in pmList do

18) if constraints are satisfied then

19) allocate vm to pm 20) child new node(root, pm)21) queue.push(child)

22) return placement vector of VM that minimizes power consumption

4.2.3 算法性能分析

在虛擬機部署模塊中，假定要被分配的虛擬機數為 p，物理機數為 n，則對于每一個物理機，最多只能部署p個要被分配的虛擬機；根據式(9)～式(12)可知，一共有4n個約束條件；根據RIVIN等人關于CSP代數求解的研究[27]，對于一個有n個變量，每個變量取值數為m以及M個約束條件的CSP問題，其算法復雜度為O(nm·2M-n)，故虛擬機部署模塊的算法復雜度為O(pn·8n)。

5 實驗與結果

5.1 算法模擬實現

為了驗證提出的模型和算法，本文進行了模擬實驗。在提出的模型中，虛擬機配置和部署問題均被定義為約束滿足問題，然后使用基于JAVA的約束編程CHOCO對它們進行建模和求解，模擬實驗按如下步驟進行。

1) 在應用程序監測模塊，根據應用程序當前負載和SLA目標，獲得各應用程序所需的資源量，同時設置或調整各應用程序的權重。

2) 根據應用程序監測模塊的輸出，虛擬機配置模塊反復探求所有可能的虛擬機分配方案，找出平均花費最小的分配方案。

3) 根據虛擬機配置模塊的輸出，虛擬機部署模塊以最小化數據中心能耗為目標，將需要被分配的虛擬機部署到物理節點上。

4) 增加應用程序的數量，預定義虛擬機的種類數量以及數據中心物理機的數量，重復步驟 1)～3)的過程。

下面分別列出虛擬機配置模塊和虛擬機部署模塊中模型中約束的實現方法。

(a)虛擬機配置模塊

約束式(2)：addConstraint(Choco.leq(Choco.sum(dualpos[i]),VMMAX[i]));

約束式(3)～式(5)：addConstraint(Choco.geq(ACPU[i],APCPU[i]));addConstraint(Choco.geq(AMEM[i],APRAM[i]));addConstraint(Choco.geq(ABW[i],APBW[i]));

約束式(6)～式(8)：addConstraint(Choco.leq(Choco.sum(ACPU),CPUMAX));addConstraint(Choco.leq(Choco.sum(AMEM),RAMMAX));addConstraint(Choco.leq(Choco.sum(ABW),BWMAX));

(b) 虛擬機部署模塊

約束式(9)～式(12)：addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMCPU),PMCPU[i]));addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMRAM),PMRAM[i]));addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMBW),PMBW[i]));addConstraint(Choco.leq(Choco.plus(DYNAMICPower[i],PMSTAPOWER[i]), PMax[i]));

5.2 實驗環境和實驗數據

為了驗證提出的能耗優化資源分配算法（DY，dynamicpower），在物理主機不同異構性的情況下進行了一些模擬實驗，對提出的算法DY與已有的算法 MinPM[4]、FFD[22]、BFD[22]在性能和能耗兩方面進行了比較。本文在16組不同資源數量的環境下進行算法模擬實驗，每組模擬實驗中的虛擬機數和物理機的數量為：10×實驗組號，即 16組實驗中虛擬機數和物理機的數量分別為：10，20，30，…，160。而且，分別在物理主機的能耗異構性不同的2種情況下進行實驗。其中能耗異構性的大小是根據物理機上的能耗參數決定的，如果一組中各物理主機能耗參數相差越大，則該組物理機的異構性越大。實驗中物理主機的能耗參數數據的生成規則如下。

1) 異構性小的物理主機能耗參數設置

空閑能耗：100～300之間。將其分為100～150,150～200, 200～250, 250～300 4 組，依據物理主機的資源大小，選擇其中一個組，隨機生成數據，選擇原則一般依照：資源大的，能耗較小。以下選擇的原則相同。

最大能耗：1 000～2 000之間。將其分為1 000～1 250, 1 250～1 500, 1 500～1 750, 1 750～2 000 4 組，同樣依據物理機主機的資源大小，選擇其中一組，隨機生成數據。

2) 異構性大的物理主機能耗參數設置

空閑能耗：100～500之間。將其分為100～200,200～300, 300～400, 400～500 4 組，依據物理主機的資源大小，選擇其中一組，隨機生成數據。

最大能耗：800～3 500之間。 將其分為800～1 500,1 500～2 200, 2 200～2 900, 2 900～3 600 4組，依據物理主機的資源大小，選擇其中一組，隨機生成數據。

另外，實驗中物理主機和虛擬機的資源大小參數的設置如下。

1) 物理主機的資源參數設置PMCPU：2 ～32 GHz //CPU；PMRAM：2～32 GB//內存；PMBW：100～500 M//帶寬。

2) 物理主機的資源參數設置VMCPU：256 MHz～10 GHz//CPU；VMRAM：256 MB～10 GB//內存；VMBW：30 ～120 M//帶寬。

5.3 實驗結果

圖4(a)～圖4(d)分別是物理主機能耗異構小與異構大 2種實驗環境下 DynamicPower(DY)、MinPM、FFD、BFD 4個算法資源分配的能耗情況。其中，縱坐標為能耗（單位為Wh），橫坐標為實驗編號。從圖4中可以看出，本文提出的能耗優化資源分配算法DY和MinPM算法，隨著物理主機數和虛擬機數的增加，能耗的節省要優于FFD和BFD算法，這主要是因為FFD和BFD只是尋求一個合理的資源分配解，而不是尋求能耗最優的資源分配解。就DY和MinPM 2種算法而言，DY要優于MinPM，因為DY算法考慮虛擬機動態能耗求得綜合能耗最小的資源分配方式，而 MinPM 僅僅是求物理主機數的最小值，所以DY算法得到的能耗始終是小于MinPM的能耗。將圖4(a)～圖4(d)對比可以看出，當物理機的異構性越大時DY算法的能耗減少得更明顯。

為了更好地分析物理主機的能耗異構性大小對資源分配結果的影響，下面給出2種異構環境下的能耗節能的比例情況，見圖 5(a)和圖 5(b)。其中，圖 5(a)和圖 5(b)分別表示圖4中各組實驗中4種算法的能耗與最大能耗相比所節省的能耗百分比。從圖中可以看出，異構性大的環境下DY算法節省的能耗均在50%左右，而異構性小的環境下DY算法節省的能耗在40%左右，即異構性小環境下節能百分比明顯大于異構性大環境下節能百分比。

(a) 物理主機異構小環境的能耗1

(b) 物理主機異構小環境的能耗2

(c) 物理主機異構大環境的能耗1

圖4 能耗比較

除了能耗優化的考慮外，還需要考慮算法的運行效率的問題。圖6是圖4中各算法在各組實驗中所對應的運行時間。

圖5 節能百分比

圖6 算法運行時間比較

圖6 (a)和圖6(b)分別表示圖4中各組實驗的運行時間，縱坐標為運行時間，單位為毫秒(ms)。從上圖中均可以看出，隨著物理主機和虛擬機數的增加，DY和MinPM算法在運行時間上有比較明顯的增加，而FFD和BFD 2種算法相比之下在運行效率上則具有很明顯的優勢，尤其是在物理機和虛擬機數量增加的情況下，這種優勢越加明顯。DY的運行效率則略優于 MinPM 算法，在物理主機異構性較大的情況，則DY的運行效率的優勢更大，這主要是因為DY算法約束條件相比MinPM算法更多，搜索空間更小，所以求解更快。

6 結束語

本文主要研究在物理服務器異構情況下的能耗優化的資源調度問題。由于物理主機資源和能耗的異構，不同種類的虛擬機分配到同一物理主機上產生的動態能耗也不同。此時，能耗優化的問題并不是最小物理主機數。針對該問題，提出了一個基于CSP的能耗最優的資源調度模型，該模型支持異構應用程序和工作負載，并且同時支持增加資源到單節點的垂直伸縮方式和增加節點數的水平伸縮方式。在該模型中，將虛擬機的資源配置從虛擬機的動態部署中分離出來。虛擬機的資源配置模塊旨在根據用戶 SLA要求確定代價最小化的資源配置方案，虛擬機的動態部署旨在最優化數據中心的能源消耗。本文將這2個問題建模為約束滿足問題，采用約束規劃的方法求解該優化問題。模擬實驗的結果驗證了本文提出的能耗最優模型與算法的有效性。本文提出的模型和算法可以應用到云數據中心，不僅可以減少云數據中心的能耗和經營成外，而且這項工作還具有重要的社會意義，因為它可以減少現代IT基礎設施CO2的釋放量和能源的消耗量。

[1] BUYYA R, YEO C S, VENUGOPAL S. Market oriented cloud computing∶ vision, hype, and reality for delivering IT services as computing utilities[A]. HPCC’08[C]. Dalian, China, 2008. 5-13.

[2] BELOGLAZOY A, BUYYA R, LEE C Y, et al. A taxonomy and survey of energy-efficient data centers and cloud computing systems[J]. Advances in Computers, 2011,(82)∶47-111.

[3] GARG S K, YEO C S, ANANDSIVAM A, et al. Environmentconscious scheduling of HPC applications on distributed cloud-oriented data centers[J]. Journal of Parallel and Distributed Computing, 2011,71(6)∶ 732-749.

[4] BICHLER M, SETZER T, SPEITKAMP B. Capacity planning for virtualized servers[A]. WITS’06[C]. Milwaukee, Wisconsin, USA, 2006.1-6

[5] KHANNA G, BEATY K, KAR G, et al. Application performance management in virtualized server environments[A]. NOMS 2006[C].Vancouver, BC, 2006. 373-381.

[6] VERMA A, AHUJA P, NEOGI A. pMapper∶ power and migration cost aware application placement in virtualized systems[A]. Middleware'08 [C]. New York, NY, USA∶ Springer-Verlag, 2008. 243-264.

[7] HERMENIER F, LORCA X, MENAUD J M, et al. Entropy∶ a consolidation manager for cluster[A]. VEE’09[C]. New York, NY,USA∶ ACM, 2009. 41-50.

[8] RIETZ J, MACEDO R, ALVES C, et al. Efficient lower bounding procedures with application in the allocation of virtual machines to data centers[J]. WSEAS Transactions on Information Science And Applications, 2011, 4(8)∶157-170.

[9] BATU R R T, WHITE P. Fast approximate PCPs for multidimensional bin-packing problem[J]. Lecture Notes in Computer Science, 1999,1671∶245-256.

[10] TIAGO C F, MARCO A S N, RODRIGO N C, et al. Server consolidation with migration control for virtualized data centers[J].Future Generation Comp Syst, 2011, 27(8)∶ 1027-1034.

[11] VAN H N, TRAN F D, MENAUD J M. SLA-aware virtual resource management for cloud infrastructures[A]. CIT’09[C]. Washington DC,USA, 2009.357-362.

[12] VON LAZEWSKI G, WANG L, YOUNGE A J, et al. Power-aware scheduling of virtual machines in DVFS-enabled clusters[A].CLUSTER’09[C]. New Orleans, LA, USA, 2009.1-10.

[13] LIU L, WANG H, LIU X, et al. Greencloud∶ a new architecture for green data center[A]. ICAC-INDST '09[C]. New York, NY, USA,ACM, 2009.29-38.

[14] HARALICK R, ELLIOTT G. Increasing tree search efficiency for constraint satisfaction problems[J]. Artificial Intelligence, 1980, 14(3)∶263-313.

[15] JUSSIEN N, ROCHART G , LORCA X. The CHOCO constraint programming solver[A]. OSSICP’08[C]. Paris, France, 2008.

[16] SRIKANTAIAH S, KANSAL A, ZHAO F. Energy aware consolidation for cloud computing[A]. HotPower'08[C]. Berkeley, CA,USA, 2009. 1-15.

[17] BERL A, GELENBE E, GIROLAMO M, et al. Energy-efficient cloud computing[J]. The Computer Journal, 2010, 53(7)∶ 1045-1051.

[18] BELOGLAZOV A, BUYYA R. Energy efficient resource management in virtualized cloud data centers[A]. CCGRID ‘10[C]. Washington DC,USA, 2010. 826-831.

[19] RODERO I, JARAMILLO J, QUIROZ A. Energy-efficient application-aware online provisioning for virtualized clouds and data centers[A]. GREENCOMP’10[C]. Washington DC, USA, 2010.[20] 3A1B-4D5E.LSALAM H S, MALY K, KAMINSKY D. Analysis of energy efficiency in clouds[A]. Computationworld '09[C]. Washington DC,USA, 2009.416-422.

[21] YOUNGE A J, LASZEWSKI G , WANG L. Efficient resource management for Cloud computing environments[A]. GREENCOMP’10[C].Washington DC, USA, 2010. 357-364.

[22] CHANG F, REN J, VISWANATHAN R. Optimal resource allocation in clouds[A]. CLOUD’10[C]. Washington DC, USA, 2010. 418-425.

[23] LEE Y C, ZOMAYA A Y. Energy efficient utilization of resources in cloud computing systems[J]. The Journal of Supercomputing, 2012,60(2)∶ 268-280.

[24] KARMARKAR N, KARP R M. An efficient approximation scheme for the one-dimensional bin-packing problem[A]. FOCS’82[C].Washington DC, USA, 1982. 312-320.

[25] BELOGLAZOV A, ABAWAJY J H, BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future Generation Comp Syst, 2012, 28(5)∶755-768.

[26] KUMAR V. Algorithms for constraint satisfaction problems∶ a survey[J]. AI Magazine, 1992, 13(1)∶ 32-44.

[27] RIVIN I, ZABIH R. An algebraic approach to constraint satisfaction problem[A]. IJCAI'89[C]. San Francisco, CA, USA, 1989. 284-289.