李俊濤，周其力

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江杭州 310018)

“云計(jì)算”作為近來IT產(chǎn)業(yè)發(fā)展的新熱點(diǎn)，受到廣泛關(guān)注，數(shù)據(jù)中心作為云服務(wù)的最終承載者，為應(yīng)用提供資源和服務(wù)等基礎(chǔ)性支撐，然而這些大規(guī)模計(jì)算的基礎(chǔ)設(shè)施卻消耗著大量的電力資源，并且呈逐年增長(zhǎng)趨勢(shì)。根據(jù)Amazon的估計(jì)［1］，數(shù)據(jù)中心的能源消耗占其維護(hù)成本的42%。此外，不斷增加的能源消耗還導(dǎo)致二氧化碳排放量的大幅增加，如何減少能源消耗是數(shù)據(jù)中心所面臨亟需解決的問題。虛擬化技術(shù)［2］則提供了一個(gè)有效的方法來管理云計(jì)算數(shù)據(jù)中心中的資源，目前數(shù)據(jù)中心廣泛采用虛擬化技術(shù)實(shí)現(xiàn)資源調(diào)度的實(shí)體由粗粒度的服務(wù)器向細(xì)粒度的虛擬機(jī)的轉(zhuǎn)化。虛擬機(jī)的放置問題有兩種情況:虛擬機(jī)的初始化放置和虛擬機(jī)的動(dòng)態(tài)管理。其中初始化放置主要解決在一個(gè)沒有負(fù)載的數(shù)據(jù)中心或物理服務(wù)器中放置若干個(gè)虛擬機(jī)。而動(dòng)態(tài)管理主要解決由于系統(tǒng)條件的改變或客戶應(yīng)用負(fù)載的動(dòng)態(tài)變化所引起的虛擬機(jī)重新分配的問題。因此，如何有效放置虛擬機(jī)資源成為云計(jì)算平臺(tái)的一個(gè)研究重點(diǎn)。

1 相關(guān)研究

如何將云計(jì)算數(shù)據(jù)中心的虛擬機(jī)放置到合適的主機(jī)中這一問題，一般將其建模為裝箱問題，而裝箱問題被證明是NP問題，研究者大多采用啟發(fā)式算法來進(jìn)行全局化搜索［3－5］，解決虛擬機(jī)的初始化放置問題。然而啟發(fā)式方法大多是基于貪心算法，并配合使用一些簡(jiǎn)單規(guī)則，比如，次優(yōu)配合，優(yōu)先配合或最佳配合等。文獻(xiàn)［6］將虛擬機(jī)的放置看成一維裝箱問題，采用改進(jìn)后的FFD算法解決虛擬機(jī)的放置問題。文獻(xiàn)［3］通過對(duì)BF算法的改進(jìn)，將其應(yīng)用在大規(guī)模的云計(jì)算環(huán)境中的虛擬機(jī)放置。文獻(xiàn)［7］使用改進(jìn)的BFD算法對(duì)虛擬機(jī)放置階段進(jìn)行優(yōu)化。啟發(fā)式算法的優(yōu)點(diǎn)是簡(jiǎn)單易實(shí)現(xiàn)，但易陷入局部最優(yōu)解，難以獲取全局優(yōu)化解，且可能完全無法產(chǎn)生任何解。遺傳算法作為解決NP問題的方案之一，一直被學(xué)術(shù)界所關(guān)注，一些研究已實(shí)現(xiàn)利用遺傳算法搜索虛擬機(jī)優(yōu)化放置的最優(yōu)解。文獻(xiàn)［8］提出利用遺傳算法并結(jié)合模糊邏輯解決虛擬機(jī)放置到物理節(jié)點(diǎn)的組合優(yōu)化問題。文獻(xiàn)［9］提出了一種基于遺傳算法的任務(wù)調(diào)度模型，利用迭代的遺傳操作優(yōu)化任務(wù)調(diào)度。盡管如此，由于遺傳算法的可改進(jìn)性，使得遺傳算法效率并沒有發(fā)揮到最大。

本文主要關(guān)注虛擬機(jī)的初始化放置問題。提出了一種改進(jìn)的遺傳算法來解決虛擬機(jī)的初始化放置問題，通過對(duì)其編碼方式、交配過程和突變方式進(jìn)行改進(jìn)，以提升算法的效率。通過實(shí)驗(yàn)性能分析，改進(jìn)后的遺傳算法在能源利用率上比傳統(tǒng)的分配算法有所提高。

2 問題描述及數(shù)學(xué)建模

可以將虛擬機(jī)的初始化放置問題描述如下:數(shù)據(jù)中心擁有多臺(tái)物理主機(jī)可供分配使用，同時(shí)可以根據(jù)用戶的請(qǐng)求產(chǎn)生需要分配的虛擬機(jī)若干，算法所解決的問題及即將這若干虛擬機(jī)分配到數(shù)據(jù)中心的物理主機(jī)中。假設(shè)向量P{p1，p2，…，pj}表示數(shù)據(jù)中心的物理主機(jī)序列，向量V{v1，v2，…，vi}表示需要放置的虛擬機(jī)序列，Vpj表示主機(jī)pj中的所有虛擬機(jī)。本文只考慮CPU和內(nèi)存兩個(gè)方面。具體符號(hào)表示如表1所示。

表1 文中所需符號(hào)的含義

由此，可知物理主機(jī)pj的CPU利用率為uj

圖1 基于分組的染色體編碼方式

進(jìn)而可以定義當(dāng)物理主機(jī)pj的CPU利用率為uj時(shí)，該主機(jī)的能源消耗為E(pj)

其中，kj為物理主機(jī)j空閑時(shí)能源消耗的比例;emaxj表示物流主機(jī)CPU利用率100%時(shí)的能源消耗。物理主機(jī)和虛擬機(jī)的約束條件如下

約束式(3)和式(4)保證每個(gè)虛擬機(jī)放置在唯一的一臺(tái)物理主機(jī)中，約束式(5)和式(6)能夠保證該物理主機(jī)中所有虛擬機(jī)的CPU利用率和內(nèi)存之和不會(huì)超過物理主機(jī)的硬件條件限制。

3 算法設(shè)計(jì)與實(shí)現(xiàn)

3.1 染色體編碼

編碼選擇是影響算法搜索效果和效率的重要因素，編碼實(shí)現(xiàn)從問題的解到染色體的映射，在此表示虛擬機(jī)放置到物理節(jié)點(diǎn)的解。針對(duì)裝箱問題，遺傳算法有3種染色體編碼方式:基于箱子的編碼，基于物品的編碼和基于分組的表示［10］。傳統(tǒng)的遺傳算法一般采用前兩種編碼方式，更多是面向單個(gè)物品的，不利用成本函數(shù)的優(yōu)化。本文采用基于分組的編碼方式，圖1給出了該方法的一個(gè)具體實(shí)例。

假設(shè)數(shù)據(jù)中心含有12個(gè)虛擬機(jī)，若干臺(tái)物理主機(jī)，一種情況下，可將它們劃分為4個(gè)組，每組包含不同數(shù)目的虛擬機(jī)，圖中上半部虛擬機(jī)2、4、7在物理主機(jī)A中，同樣的虛擬機(jī)1、9、6在物理主機(jī)B中，虛擬機(jī)8、10、11、12在物理主機(jī) C 中，虛擬機(jī)3、5在物理主機(jī)D中，但對(duì)應(yīng)的染色體基因只有4個(gè);另一種情況下，虛擬機(jī)被分為3組，每臺(tái)物理主機(jī)包含4個(gè)虛擬機(jī)，可以看到此時(shí)虛擬機(jī)的分配達(dá)到一種理想的狀態(tài)。此外使用這種編碼方式將算法的操作中心從面向單個(gè)的虛擬，轉(zhuǎn)變?yōu)榘摂M機(jī)的組。

3.2 交叉算子

交叉算子所支配的交配過程在遺傳算法中的主要作用是使后代能夠繼承父代雙方的優(yōu)秀基因，產(chǎn)生更優(yōu)秀的后代。分組遺傳算法的交配過程是通過隨機(jī)選擇兩個(gè)父代，假設(shè)為X、Y，采用隨機(jī)法選擇X父代中的一段基因，將其加入到父代Y中，從而產(chǎn)生新的子代編碼。向Y中插入新的基因時(shí)，由于是基于分組的編碼，可能相同的虛擬機(jī)會(huì)出現(xiàn)在不同的物理主機(jī)中，如果出現(xiàn)就將包含相同虛擬機(jī)的物理主機(jī)從染色體編碼中刪除，此時(shí)會(huì)產(chǎn)生由于物理主機(jī)刪除而出現(xiàn)沒有分配的虛擬機(jī)，需要為這些未分配的虛擬機(jī)重新分配編碼中的物理主機(jī)。具體交叉過程如圖2所示。

圖2 交叉產(chǎn)生子代的過程

3.3 變異算子

遺傳算法的基本思想是通過模擬自然界生物的進(jìn)化過程來求解，那么變異對(duì)產(chǎn)生優(yōu)秀個(gè)體具有重要的作用。在本文的分組遺傳算法中，摒棄通過隨機(jī)刪除編碼中的物理主機(jī)來實(shí)現(xiàn)變異過程，而是采用資源效用函數(shù)式(7)來決定刪除哪個(gè)主機(jī)。此函數(shù)能反映該物理主機(jī)資源的綜合使用情況，如果該主機(jī)中的虛擬機(jī)放置越合理，則其資源利用率就越高，函數(shù)值也就越大，刪除的概率就越小

如此，每次變異過程刪除的物理主機(jī)的Fi值都是最小的，保證了每次變異都是向著更優(yōu)化的方向前進(jìn)，對(duì)于由于刪除造成的未分配的虛擬機(jī)采用上述方法將其加入到編碼的物理主機(jī)中。

3.4 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是評(píng)價(jià)群體中個(gè)體好壞的標(biāo)準(zhǔn)，是模擬自然選擇的唯一依據(jù)，適應(yīng)度函數(shù)的選取直接影響到遺傳算法的收斂速度以及是否能夠找到最優(yōu)解。根據(jù)適應(yīng)度的大小，對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰，是驅(qū)動(dòng)遺傳算法的動(dòng)力。本文以實(shí)現(xiàn)資源的高效利用為目標(biāo)，因此采用式(8)作為遺傳算法的適應(yīng)度函數(shù)

其中，Emin為主機(jī)能源消耗的最低值;Emax為主機(jī)能源消耗的最大值;而E(x)代表在演化過程中針對(duì)一種可行性解時(shí)，主機(jī)資源消耗的總和。此適應(yīng)度函數(shù)能夠保證能源消耗越小，適應(yīng)度函數(shù)值越大。

4 仿真實(shí)驗(yàn)與分析

遺傳算法采用Java語(yǔ)言實(shí)現(xiàn)，由于所解決問題為虛擬機(jī)的初始化放置，暫時(shí)還沒有實(shí)際數(shù)據(jù)可用，所以本文使用隨機(jī)產(chǎn)生的數(shù)據(jù)，通過一系列的實(shí)驗(yàn)來評(píng)估算法的性能和穩(wěn)定性。具體的實(shí)驗(yàn)環(huán)境如表2所示，虛擬機(jī)所需的CPU和內(nèi)存的大小為［300，3 000］之間的隨機(jī)數(shù)，而物理主機(jī)的CPU和內(nèi)存的大小則從集合{1 000，1 500，…，55 000}中隨機(jī)選取，反映數(shù)據(jù)中心能源消耗的式(2)中kj值及資源效用函數(shù)式(7)中的β值均取取0.7。對(duì)于每次實(shí)驗(yàn)設(shè)定初始種群的規(guī)模為200，終止條件為連續(xù)進(jìn)行20次迭代沒有產(chǎn)生更好的解。

表2 實(shí)驗(yàn)環(huán)境參數(shù)

為了更好的對(duì)比評(píng)估，本文也實(shí)現(xiàn)了降序首次適應(yīng)算法(FFD)，以及傳統(tǒng)的遺傳算法(GA)作為評(píng)估所提算法(MGA)的基準(zhǔn)。FFD作為最流行的一種啟發(fā)式算法，一般用于解決虛擬機(jī)的放置問題［8］，GA算法是所有改進(jìn)遺傳算法的基礎(chǔ)，經(jīng)常用來評(píng)估改進(jìn)算法的性能優(yōu)劣。因?yàn)槊總€(gè)實(shí)驗(yàn)的數(shù)據(jù)都是隨機(jī)產(chǎn)生的，所以每個(gè)實(shí)驗(yàn)都重復(fù)10次，盡可能減小隨機(jī)數(shù)據(jù)帶來的影響，計(jì)算10次實(shí)驗(yàn)的平均值作為本次實(shí)驗(yàn)的最終數(shù)據(jù)。本文主要考慮能源消耗和花費(fèi)時(shí)間這兩個(gè)方面，具體的實(shí)驗(yàn)結(jié)果如圖3～圖4所示。

圖3 能源消耗對(duì)比

圖4 花費(fèi)時(shí)間對(duì)比

從圖3可以看出，本文的MGA算法對(duì)于傳統(tǒng)的GA算法以及FFD算法在能源消耗方面有明顯的下降，平均下降幅度分別達(dá)到了8.5%和16.8%。說明本文算法在虛擬機(jī)的初始化配置方面實(shí)現(xiàn)了更好的優(yōu)化，從而減少了能源消耗。而對(duì)于花費(fèi)時(shí)間方面，如圖4所示，F(xiàn)FD算法的花費(fèi)時(shí)間均＜1 ms，具體原因可理解為FFD算法具有確定性，針對(duì)每次試驗(yàn)FFD都能在短時(shí)間內(nèi)達(dá)到穩(wěn)定狀態(tài)。而GA和MGA算法的花費(fèi)時(shí)間均超過了1 ms，并且隨著虛擬機(jī)總數(shù)的增加呈線性增大，MGA算法相對(duì)于GA算法的花費(fèi)時(shí)間所增加的時(shí)間相差不大，考慮到MGA算法在能源消耗方面的優(yōu)勢(shì)以及算法運(yùn)用在虛擬機(jī)初始化放置的具體環(huán)境，時(shí)間的增加幅度可以接受。

5 結(jié)束語(yǔ)

本文提出的改進(jìn)的遺傳算法采用分組方式的虛擬機(jī)編碼方式，先以物理主機(jī)為粒度采用資源調(diào)度，然后再對(duì)重復(fù)虛擬機(jī)進(jìn)行個(gè)別插入，使得數(shù)據(jù)中心的資源分配更加細(xì)化，同時(shí)引入效用函數(shù)作為變異算子，通過能源相關(guān)的適應(yīng)度函數(shù)的驅(qū)動(dòng)，仿真實(shí)驗(yàn)結(jié)果顯示，該算法在能源消耗方面比FFD算法和傳統(tǒng)的GA算法具有明顯的優(yōu)越性。在此后的工作中，需在多個(gè)指標(biāo)方面對(duì)算法進(jìn)行優(yōu)化改進(jìn)，進(jìn)一步提高算法的性能和可擴(kuò)展性。

［1］ Kusic D，Kephart J O，Hanson J E，et al．Power and performance management of virtualized computing environments via lookahead control［J］．Cluster Computing，2009，12(1):1 －15．

［2］ Goldberg R P．Survey of virtual machine research［J］．Computer，1974，7(6):34 －45．

［3］ Li B，Li J，Huai J，et al．Enacloud:an energy － saving application live placement approach for cloud computing environments［C］．IEEE International Conference on Cloud Computing，2009:17 －24．

［4］ Ajiro Y，Tanaka A．Improving packing algorithms for server consolidation ［C］．International CMG Conference，2007:399－406．

［5］ Gupta R，Bose S K，Sundarrajan S，et al．A two stage heuristic algorithm for solving the server consolidation problem with item－item and bin－item incompatibility constraints［C］．IEEE International Conference on Services Computing，2008:39－46．

［6］ Verma A，Ahuja P，Neogi A．pMapper:power and migration cost aware application placement in virtualized systems Middleware 2008［M］．Berlin Heidelberg:Springer，2008．

［7］ Beloglazov A，Buyya R．Energy efficient resource management in virtualized cloud data centers［C］．Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster，Cloud and Grid Computing，IEEE Computer Society，2010:826－831．

［8］ Xu J，F(xiàn)ortes J A B．Multi－ objective virtual machine placement in virtualized data center environments［C］．Green Computing and Communications(GreenCom)，2010 IEEE/ACM Int'l Conference on ＆ Int'l Conference on Cyber，Physical and Social Computing(CPSCom)，IEEE，2010:179 －188．

［9］ Jang S H，Kim T Y，Kim J K，et al．The study of genetic algorithm －based task scheduling for cloud computing［J］．International Journal of Control and Automation，2012，5(4):157－162．

［10］ Cecchet E，Chanda A，Elnikety S，et al．Performance comparison of middleware architectures for generating dynamic web content［C］．New York:Proceedings of the ACM/IFIP/USENIX 2003 International Conference on Middleware，Springer－ Verlag，2003:242 －261．