一種面向數(shù)據(jù)中心的能耗感知虛擬機(jī)放置策略

楊 傲，馬春苗，伍衛(wèi)國，王思敏，趙 坤

(1.西安交通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710049；2.廣東浪潮大數(shù)據(jù)研究有限公司，廣東 廣州 510000)

隨著云計(jì)算的廣泛使用，數(shù)據(jù)中心的規(guī)模不斷擴(kuò)大，因此帶動(dòng)降低數(shù)據(jù)中心運(yùn)行能耗方面的研究不斷發(fā)展。從IT設(shè)備系統(tǒng)層面來看，主要通過作業(yè)調(diào)度實(shí)現(xiàn)負(fù)載均衡達(dá)到節(jié)能效果；從虛擬機(jī)層面看，能夠通過虛擬機(jī)(Virtual Machine，VM)整合、調(diào)度等方法實(shí)現(xiàn)節(jié)能目的。其中，虛擬機(jī)放置(Virtual Machine Placement，VMP)問題被看成一種可變大小的裝箱問題(Variable Size Bin Packing Problem，VSBPP)[1]，本質(zhì)上來說它是將請求的虛擬機(jī)序列通過各種計(jì)算方式得出需要放置的對應(yīng)物理機(jī)(Physical Machine，PM)，放置位置以能夠?qū)崿F(xiàn)最好的服務(wù)質(zhì)量(Quality of Service，QoS)、最低的能耗開銷等為目標(biāo)。目前主要有兩類虛擬機(jī)放置方法，分別為基于啟發(fā)式算法的虛擬機(jī)放置策略以及基于資源探測的虛擬機(jī)放置策略。

在基于啟發(fā)式算法的虛擬機(jī)放置策略中，文獻(xiàn)[2]綜合考慮負(fù)載均衡、虛擬機(jī)分配性能等因素，在此基礎(chǔ)上提出基于改進(jìn)粒子群的虛擬機(jī)優(yōu)化配置算法，利用此優(yōu)化算法實(shí)現(xiàn)了目標(biāo)問題的優(yōu)化。文獻(xiàn)[3]從目前異構(gòu)數(shù)據(jù)中心的角度出發(fā)，提出了一種基于模擬退火技術(shù)的虛擬機(jī)放置策略，通過棄用物理活動(dòng)的機(jī)器來最大程度地降低功耗，并減少制造周期。文獻(xiàn)[4]提出了一種基于離散版本的粒子蟻群的能耗感知算法，在不違反服務(wù)水平協(xié)議(Service Level Agreement，SLA)的情況下，采用了有效的最小化適應(yīng)度函數(shù)來減少功耗。文獻(xiàn)[5]以優(yōu)化云數(shù)據(jù)中心的可用性和能耗為目標(biāo)，提出了一種改進(jìn)的遺傳算法(Improved Genetic Algorithm，I-GA)來解決虛擬機(jī)放置問題。該算法提出了一個(gè)虛擬層次結(jié)構(gòu)模型，并與遺傳算法相結(jié)合，通過對I-GA初始種群生成步驟的創(chuàng)新，該模型能夠在解決可用性和能源消耗問題方面實(shí)現(xiàn)近最優(yōu)解。文獻(xiàn)[6]基于一種改進(jìn)的基于排列的遺傳算法和多維資源感知的最優(yōu)匹配分配策略，提出了一種混合虛擬機(jī)放置算法。提出的虛擬機(jī)放置算法旨在通過最小化虛擬機(jī)的活動(dòng)服務(wù)器數(shù)量來提高云數(shù)據(jù)中心的能耗率，并試圖實(shí)現(xiàn)活動(dòng)服務(wù)器的多維資源(CPU、RAM和帶寬)的平衡使用，從而減少資源浪費(fèi)。文獻(xiàn)[7]提出一種基于文化基因算法(Memetic Algorithm，MA)的虛擬機(jī)放置方法，該方法針對云數(shù)據(jù)中心運(yùn)營情況建立了最小化能耗、最小化運(yùn)行時(shí)服務(wù)等級協(xié)議違例率以及最大化資源利用率的多目標(biāo)優(yōu)化模型，將虛擬機(jī)按照資源請求情況進(jìn)行分類，并利用該分類方法改進(jìn)了MA，利用改進(jìn)后的MA求解多目標(biāo)優(yōu)化模型，得到虛擬機(jī)放置方案。除此之外，還有利用和諧搜索算法[8]以及磷蝦群算法[9]等。

此外，一些研究也從虛擬機(jī)以及物理機(jī)的資源探測方面入手。文獻(xiàn)[10]兼顧考慮物理機(jī)資源浪費(fèi)和網(wǎng)絡(luò)總流量兩個(gè)方面，將虛擬機(jī)放置建模為多目標(biāo)優(yōu)化問題，同時(shí)最小化物理機(jī)資源浪費(fèi)以提高數(shù)據(jù)中心物理機(jī)使用效率和最小化網(wǎng)絡(luò)總流量以改善數(shù)據(jù)中心網(wǎng)絡(luò)的擴(kuò)展性，設(shè)計(jì)了一種基于多目標(biāo)蟻群優(yōu)化的虛擬機(jī)放置算法來求解該問題。文獻(xiàn)[11]認(rèn)為最佳適應(yīng)算法(Best Fit，BF)能夠很好適用于云數(shù)據(jù)中心環(huán)境，因此采用最佳適應(yīng)算法作為數(shù)據(jù)中心虛擬機(jī)放置算法，能夠有助于節(jié)省未充分利用的物理服務(wù)器，并且虛擬機(jī)映射到數(shù)據(jù)中心中的服務(wù)器時(shí)能有效地做出響應(yīng)。文獻(xiàn)[12]通過考慮虛擬機(jī)的 CPU 和內(nèi)存要求分配時(shí)受限于物理機(jī)的容量，受最佳擬合遞減算法的啟發(fā)，開發(fā)了該精確算法的4種變體以解決多容量約束下的多目標(biāo)問題。文獻(xiàn)[13]研究了如何平衡多種資源的使用，在最大限度提高虛擬機(jī)放置的服務(wù)速率的同時(shí)，緩解資源的碎片化，從而避免物理資源的浪費(fèi)和不良的性能。為了解決這種雙目標(biāo)優(yōu)化問題，提出一種聯(lián)合裝箱啟發(fā)式和遺傳算法，以較低的時(shí)間復(fù)雜度獲得近似最優(yōu)解。文獻(xiàn)[14]提出一種基于最佳適應(yīng)法放置的虛擬機(jī)放置策略，稱為空間感知最佳擬合減少(Space Aware Best Fit Decreasing，SABFD)，首先根據(jù)CPU利用率以降序?qū)Υw移的虛擬機(jī)進(jìn)行排序，具有足夠計(jì)算資源的PM將接收第一個(gè)虛擬機(jī)，而后將選擇具有最少可用計(jì)算資源的PM作為第2個(gè)虛擬機(jī)的目標(biāo)主機(jī)；依此類推，直到完成所有虛擬機(jī)的放置。

從上述研究中，可以看出最佳適應(yīng)法用于平衡多種資源的使用十分有效，而遺傳算法作為經(jīng)典的進(jìn)化算法可以較快地獲得較好的優(yōu)化結(jié)果。然而，目前研究尚未考慮數(shù)據(jù)中心服務(wù)器的環(huán)境溫度，若在高溫區(qū)域位置持續(xù)增加服務(wù)器負(fù)載，則可能導(dǎo)致局部熱點(diǎn)問題，使得制冷設(shè)備處于過度制冷狀態(tài)，導(dǎo)致數(shù)據(jù)中心運(yùn)行能耗整體提高。筆者提出的能耗感知虛擬機(jī)放置策略，通過將最佳適應(yīng)法和遺傳算法結(jié)合并進(jìn)行一定改進(jìn)，在降低數(shù)據(jù)中心運(yùn)行能耗的基礎(chǔ)上避免熱點(diǎn)出現(xiàn)。該方法首先收集當(dāng)前數(shù)據(jù)中心所有物理機(jī)的可用資源信息，然后按照CPU資源可用大小進(jìn)行排序，依照溫度上升最小值確定虛擬機(jī)放置位置，當(dāng)所有位置確定后將目標(biāo)序列二進(jìn)制化，通過遺傳算法最終尋找最優(yōu)解。遺傳算法是以能耗及溫度為目標(biāo)，因此得出的最優(yōu)解在降低能耗的基礎(chǔ)上避免熱點(diǎn)出現(xiàn)，保證數(shù)據(jù)中心安全運(yùn)行。

1 算法概述

目前絕大部分?jǐn)?shù)據(jù)中心都采用虛擬化技術(shù)，將硬件資源例如CPU、內(nèi)存、帶寬等進(jìn)行抽象再轉(zhuǎn)換后交付給用戶使用，虛擬化技術(shù)打破了傳統(tǒng)實(shí)體結(jié)構(gòu)之間的物理隔閡，能夠更方便更高效地完成客戶請求的資源和任務(wù)，因此當(dāng)前數(shù)據(jù)中心主要通過請求虛擬機(jī)方式完成對物理資源的分配[15]。隨著數(shù)據(jù)中心的規(guī)模不斷擴(kuò)大，服務(wù)器運(yùn)行能耗也隨之上升，由于服務(wù)器運(yùn)行功耗及發(fā)熱量與CPU、內(nèi)存等利用率呈正相關(guān)，因此請求虛擬機(jī)放置在不同物理機(jī)，將會產(chǎn)生不同的能耗結(jié)果。虛擬機(jī)放置問題本質(zhì)上來說，是將虛擬機(jī)請求序列通過算法計(jì)算得出最適合物理機(jī)放置位置，物理機(jī)在初始階段能夠看做是一個(gè)空盒子，等待合適的虛擬機(jī)將其放入，若確定某個(gè)虛擬機(jī)的放置位置后，目標(biāo)物理機(jī)可用的CPU、內(nèi)存以及帶寬資源則會相應(yīng)地減少，因此物理機(jī)能夠看做是一個(gè)可變大小的箱子。這樣將問題轉(zhuǎn)化為裝箱問題，能夠?qū)PU、內(nèi)存、帶寬以及溫度等多維問題轉(zhuǎn)化為箱子編號的一維問題，進(jìn)而將物理機(jī)序列二進(jìn)制化，極大地簡化了數(shù)據(jù)處理的復(fù)雜度，更方便進(jìn)行后續(xù)計(jì)算。

上述介紹了目前常見的虛擬機(jī)放置算法，但是暫時(shí)還未有在放置過程中考慮服務(wù)器物理溫度的研究。筆者提出的算法通過將能耗與溫度信息進(jìn)行關(guān)聯(lián)，實(shí)現(xiàn)多目標(biāo)優(yōu)化。算法流程圖如圖1所示。

圖1 算法流程圖

首先收集當(dāng)前所有物理機(jī)的信息，包括可用CPU、內(nèi)存、帶寬資源以及當(dāng)前物理機(jī)的溫度。由于服務(wù)器能耗以及溫度主要是與CPU利用率相關(guān)，因此對物理機(jī)按照CPU可用資源從小到大進(jìn)行排序。對于每一個(gè)虛擬機(jī)，采用最佳適應(yīng)算法確定放置位置，若有多個(gè)物理機(jī)符合要求，則根據(jù)文中提出的溫度迫切值計(jì)算方法從中選擇出溫度迫切值最小的物理機(jī)作為目標(biāo)位置。當(dāng)所有虛擬機(jī)序列都確定好位置后得到目標(biāo)虛擬機(jī)序列，將二進(jìn)制化后的序列作為遺傳算法的初始種群，先對序列進(jìn)行交叉以及變異操作，再根據(jù)筆者提出的適應(yīng)度函數(shù)采用輪盤賭法選擇出下一代種群，通過遺傳算法的多次迭代后得出最優(yōu)解。其中，最佳適應(yīng)法的時(shí)間復(fù)雜度為O(n3)，遺傳算法的時(shí)間復(fù)雜度為O(n2)，則算法整體的時(shí)間復(fù)雜度為O(n3)+O(n2)，也就是O(n3)。

2 最佳適應(yīng)法分析

最佳適應(yīng)算法最初應(yīng)用于計(jì)算機(jī)內(nèi)存分配，算法首先將空閑內(nèi)存分區(qū)按照升序的方式排列，在進(jìn)行內(nèi)存分配時(shí)從排序好的空閑內(nèi)存中從小到大查找，將第一個(gè)符合要求的分區(qū)作為目標(biāo)區(qū)域，因此后續(xù)相對較大的分區(qū)能夠保留。在內(nèi)存分配應(yīng)用中指標(biāo)為一維尺度，同樣也可將其擴(kuò)展至三維尺度，在筆者提出的算法中分別將CPU、內(nèi)存以及帶寬資源作為指標(biāo)進(jìn)行匹配。

首先收集物理機(jī)的可用CPU、內(nèi)存、帶寬資源以及溫度信息，假設(shè)有M個(gè)物理機(jī)，對所有物理機(jī)首先按照CPU可用大小以升序方式排列。對于請求的虛擬機(jī)序列，先后處理的順序?qū)斐刹煌慕Y(jié)果，因此將其隨機(jī)排列模擬不同的到達(dá)次序，假設(shè)有N個(gè)虛擬機(jī)，隨機(jī)生成x個(gè)序列Px，序列Pi中每一個(gè)值代表虛擬機(jī)請求編號。在算法運(yùn)行過程中，所有的物理機(jī)以及虛擬機(jī)應(yīng)該滿足以下條件：

(1)

(2)

(3)

(4)

(5)

tj

(6)

(7)

其中，xij是一個(gè)二進(jìn)制數(shù)組，表示虛擬機(jī)Vi是否分配至物理機(jī)Sj，yj是一個(gè)二進(jìn)制數(shù)組，表示物理機(jī)Sj是否分配虛擬機(jī)，tj表示物理機(jī)Sj分配后溫度，Tth為預(yù)定的溫度閾值，vcpu、vmem及vBW分別代表虛擬機(jī)請求的CPU、內(nèi)存及帶寬資源，pcpu、pmem、pBW分別代表物理機(jī)所擁有的資源，N是虛擬機(jī)總量，M是物理機(jī)總量。

Hj=|bj-tavg|+|tj-tavg|， ?j∈{1，2，…，M} 。

(8)

其中，tavg為物理機(jī)初始平均溫度，計(jì)算公式如下：

(9)

通常物理機(jī)運(yùn)行溫度受多方面因素影響，其中散熱部件包括服務(wù)器風(fēng)扇以及制冷設(shè)備等，主要產(chǎn)熱部件為CPU，實(shí)驗(yàn)過程中綜合考慮了產(chǎn)熱與散熱的相互作用，確定了物理機(jī)溫度與CPU利用率呈正相關(guān)。實(shí)驗(yàn)收集了服務(wù)器運(yùn)行時(shí)溫度信息與負(fù)載信息，采用多項(xiàng)式擬合方法，最終物理機(jī)溫度與CPU利用率關(guān)系如下：

(10)

其中，Uj為物理機(jī)j的CPU利用率。Uj由以下公式獲得：

(11)

對所有符合要求的物理機(jī)計(jì)算溫度迫切值，將最大值的物理機(jī)作為當(dāng)前虛擬機(jī)目標(biāo)放置位置，同時(shí)更新物理機(jī)可用資源信息。最佳適應(yīng)算法篩選物理機(jī)序列的算法描述如算法1所示，主體為3層循環(huán)計(jì)算，時(shí)間復(fù)雜度為O(n3)。

算法1最佳適應(yīng)算法篩選物理機(jī)序列。

輸入：x個(gè)虛擬機(jī)序列p，每個(gè)序列長度為N；有序物理機(jī)序列yk，長度為M。

輸出：目標(biāo)物理機(jī)序列q。

① Function_FF(p){

② FOR(i=0 tox)

③ FOR(j=0 toN)

④ FOR(k=0 toM)

⑤ IF(yk可用資源符合虛擬機(jī)pij)

⑥ calculateHk//使用H參數(shù)記錄當(dāng)前物理機(jī)溫度迫切值

⑦ IF(Hkhas not value)//沒有任何物理機(jī)的可用資源符合虛擬機(jī)請求

⑧ throw error

⑨ select the max value ofHkas target position

⑩ update the rest resource of server//更新包括可用CPU、內(nèi)存以及帶寬資源

3 遺傳算法分析

遺傳算法(Genetic Algorithm，GA)是一種優(yōu)化算法，其靈感來自于大自然中種群發(fā)展規(guī)律，種群在不斷進(jìn)化發(fā)展過程中，具有高適應(yīng)環(huán)境的個(gè)體會不斷延續(xù)優(yōu)質(zhì)基因到下一代個(gè)體中，通過對種群中存在的個(gè)體進(jìn)行遺傳操作的迭代，產(chǎn)生了新的種群。在遺傳算法中，染色體的表示、選擇、交叉、變異以及適應(yīng)度函數(shù)是算法的關(guān)鍵。傳統(tǒng)遺傳算法流程是：隨機(jī)生成含有n個(gè)染色體的種群Y，通過適應(yīng)度函數(shù)計(jì)算Y中每個(gè)染色體的適應(yīng)度值。染色體P1和P2是根據(jù)適應(yīng)度值從Y種群中選擇出來的，在P1和P2中應(yīng)用交叉概率為Cp的單點(diǎn)或者多點(diǎn)交叉法產(chǎn)生新的后代Q，然后在后代Q中應(yīng)用概率為Mp的一致性變異操作產(chǎn)生新的后代Q′，新的后代將會放置在新的種群中。應(yīng)用同樣的方法對種群中所有的染色體重復(fù)進(jìn)行選擇、交叉、變異操作，直到新的種群完成。遺傳算法通過變異率和交叉率能夠動(dòng)態(tài)地改變搜索過程，最終獲得最優(yōu)解。同時(shí)由于遺傳算法可以評估多個(gè)個(gè)體，產(chǎn)生多個(gè)最優(yōu)解，因此具有更好的全局搜索能力。遺傳算法的本質(zhì)為二重迭代，時(shí)間復(fù)雜度為O(n2)。

3.1 交叉、變異以及選擇操作分析

遺傳算法中交叉和變異操作是產(chǎn)生新個(gè)體的關(guān)鍵，也是影響遺傳算法性能和最終結(jié)果的關(guān)鍵。交叉用于結(jié)合兩個(gè)或者多個(gè)父代遺傳信息來產(chǎn)生后代，比較流行的交叉算法有單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、順序交叉等。筆者選擇單點(diǎn)交叉法，在單點(diǎn)交叉中，選擇一個(gè)交叉點(diǎn)，將超過此點(diǎn)位置后方的遺傳信息進(jìn)行相互調(diào)換。圖2展示了調(diào)換過程，它交換了父代交叉點(diǎn)后的信息，產(chǎn)生了新的個(gè)體。

圖2 單點(diǎn)交叉操作

在交叉過程中，如果概率過大或者相互交叉基因量過多，則產(chǎn)生新個(gè)體的速度就會過快，具有高適應(yīng)度的個(gè)體結(jié)構(gòu)更加容易被破壞，導(dǎo)致遺傳算法無法朝著最優(yōu)解的方向發(fā)展。相反，若交叉概率過低或者交叉的基因量過少，則不易產(chǎn)生新的個(gè)體，導(dǎo)致迭代過程過于緩慢，甚至整個(gè)求解過程停滯不前。因此文中算法考慮一種基于迭代次數(shù)的動(dòng)態(tài)交叉計(jì)算方法，在算法初期，生成的種群中個(gè)體的差異度較大，通過交叉、變異操作后到后期，由于優(yōu)勝劣汰規(guī)則，大部分高適應(yīng)度個(gè)體都保留了下來，個(gè)體之間的差異度會隨著遺傳的發(fā)展而減小。因此對于算法中交叉操作率以及交叉的基因數(shù)量，應(yīng)隨著迭代次數(shù)而減小。對于交叉點(diǎn)的選擇如下：

(12)

其中，t為當(dāng)前遺傳代數(shù)，tmax為迭代總次數(shù)。

圖3 替換變異操作

選擇是遺傳算法中的重要步驟，它決定序列是否參與后續(xù)迭代過程；遺傳算法的收斂速度也取決于選擇的高效性。流行的選擇算法有輪盤賭、排名法、競賽法及隨機(jī)抽樣法。文中選用輪盤賭法。輪盤賭法是以輪盤游戲?yàn)樗悸?，首先?jì)算種群中所有個(gè)體的適應(yīng)度值f(xi)，i∈[0，N]，隨后根據(jù)

(13)

計(jì)算個(gè)體選擇概率，再根據(jù)公式

(14)

計(jì)算個(gè)體的累計(jì)概率作為輪盤的選擇概率。在輪盤構(gòu)造完成后生成隨機(jī)數(shù)r，選擇出下一輪迭代個(gè)體。在選擇過程中，適應(yīng)度函數(shù)作為確定選擇概率方法，其高效性顯得尤為重要。

3.2 適應(yīng)度函數(shù)分析

適應(yīng)度函數(shù)在遺傳算法中起著重要的作用。首先適應(yīng)度函數(shù)是用來衡量當(dāng)前種群質(zhì)量的重要方式，函數(shù)有多個(gè)輸入接口，代表當(dāng)前種群評估指標(biāo)；在文中，有兩個(gè)評估指標(biāo)，分別為種群的能耗指標(biāo)以及溫度指標(biāo)。能耗指標(biāo)能夠保證遺傳算法迭代中能夠找出能耗最小的虛擬機(jī)放置位置，數(shù)據(jù)中心服務(wù)器能耗建模的方法主要分為基于組件的能耗模型以及基于系統(tǒng)利用率的模型。文中采用基于系統(tǒng)利用率的能耗模型，模型如下：

Pserver=c0ur+c1u+c2，

(15)

其中，u為CPU利用率，c0、c1和c2為實(shí)驗(yàn)中需要確定的參數(shù)，r為實(shí)驗(yàn)浮動(dòng)參數(shù)，浮動(dòng)范圍為0.5～1.5。

為了避免數(shù)據(jù)中心在運(yùn)行過程中出現(xiàn)熱點(diǎn)問題，請求的虛擬機(jī)應(yīng)該避免放置在溫度過熱的區(qū)域。評估方法如下所示：

(16)

其中，bj為物理機(jī)當(dāng)前溫度，Tth為設(shè)定的溫度閾值，tj為物理機(jī)啟動(dòng)虛擬機(jī)后的預(yù)測溫度，由式(10)計(jì)算可得。

至此，可得遺傳算法中適應(yīng)度函數(shù)為

F=Pserver+αT，

(17)

其中，α為動(dòng)態(tài)可調(diào)參數(shù)，根據(jù)數(shù)據(jù)中心的規(guī)模動(dòng)態(tài)調(diào)整，浮動(dòng)范圍為0.1～0.8。

4 實(shí)驗(yàn)結(jié)果與分析

目前數(shù)據(jù)中心能耗優(yōu)化的實(shí)驗(yàn)多數(shù)都是在仿真平臺上實(shí)驗(yàn)的，這是出于對數(shù)據(jù)中心安全性和穩(wěn)定性的考慮。常用的仿真平臺包括GreenCloud、6sigmaDC、EnergyPlus和CloudSim等。本次實(shí)驗(yàn)通過cloudsim仿真平臺完成。cloudsim是墨爾本大學(xué)中Gridbus項(xiàng)目孵化的云計(jì)算仿真平臺，它能夠模擬數(shù)據(jù)中心各種實(shí)體類，如物理機(jī)、虛擬機(jī)、網(wǎng)關(guān)以及實(shí)體類之間的交互關(guān)系[16]。

為了進(jìn)行實(shí)驗(yàn)對比，設(shè)計(jì)了4組對照實(shí)驗(yàn)，分別為首次適應(yīng)法(First Fit，F(xiàn)F)、正余弦優(yōu)化算法(Sine Cosine Algorithm，SCA)、遺傳算法(Genetic Algorithm，GA)以及隨機(jī)分配法(Random)。在實(shí)驗(yàn)中BF算法以CPU資源作為參考對象，SCA中控制參數(shù)r1從2線性下降至0，遺傳算法迭代次數(shù)為200次。現(xiàn)在假設(shè)數(shù)據(jù)中心有3種不同的物理機(jī)配置，同時(shí)虛擬機(jī)請求資源類型也有3種。物理機(jī)配置如表1所示，虛擬機(jī)請求資源類型如表2所示。

表1 物理機(jī)配置表

表2 虛擬機(jī)配置表

為了檢測本算法是否能夠找到最優(yōu)解，首先使用小樣本進(jìn)行實(shí)驗(yàn)，小樣本實(shí)驗(yàn)?zāi)軌蛄信e所有解決方案，因此存在最優(yōu)解。實(shí)驗(yàn)中，分別使用5、6、7、8、10個(gè)虛擬機(jī)樣本，假設(shè)物理機(jī)的數(shù)量與虛擬機(jī)的數(shù)量相等，由數(shù)學(xué)分析可知，在每個(gè)場景中，放置位置一共有n!種，n為虛擬機(jī)個(gè)數(shù)。通過比較不同算法的能耗結(jié)果來推測該算法是否可以找到n!種可能中的最優(yōu)解。實(shí)驗(yàn)結(jié)果如表3所示。

由表3可知，SCA算法、GA算法與筆者提出的算法都能找到最優(yōu)解，而FF算法與Random算法都未能找出最優(yōu)解，相比于FF算法，Random算法求得的能耗平均值更高，也符合預(yù)期結(jié)果。此外，隨著虛擬機(jī)以及物理機(jī)的數(shù)量增加，運(yùn)行能耗也相應(yīng)地提高，同樣符合預(yù)期結(jié)果。

表3 不同算法的能耗結(jié)果 W

此外，對比了不同規(guī)模數(shù)量的物理機(jī)以及虛擬機(jī)在不同方法下的能耗情況，同樣在表2以及表3隨機(jī)生成物理機(jī)以及虛擬機(jī)，對比方法包括Random、FF、SCA和GA。數(shù)量規(guī)模為5組，分別為data100、data150、data200、data250、data300，代表虛擬機(jī)以及物理機(jī)數(shù)量分別為100、150、200、250、300。其中迭代算法迭代次數(shù)為20x規(guī)模。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同算法的能耗對比圖

由圖4可知，在不同數(shù)量集的條件下，文中算法所得到的能耗均最低，因此驗(yàn)證了筆者提出的算法能夠有效地降低數(shù)據(jù)中心運(yùn)行能耗。此外，在FF以及Random算法中，由于未對放置位置進(jìn)行優(yōu)化，因此，相比其他算法能耗最高。在小樣本數(shù)據(jù)中，由于物理機(jī)數(shù)量較少，因此整體能耗較低，各個(gè)算法之間的能耗差值較小，但隨著物理機(jī)的數(shù)量增多，不同算法間的能耗差別逐漸體現(xiàn)。

筆者提出的算法結(jié)合最佳適應(yīng)算法與遺傳算法，在BF算法階段能夠首先對虛擬機(jī)的請求進(jìn)行資源對比，能夠有效地去除無效個(gè)體。此外，在遺傳算法交叉階段采用動(dòng)態(tài)交叉點(diǎn)選擇，種群在初始階段，個(gè)體的相互差異較大，在迭代末期，差異小，因此交叉點(diǎn)的動(dòng)態(tài)選擇能耗保證高適應(yīng)度值的個(gè)體結(jié)構(gòu)不被破壞。從表4以及表5隨機(jī)生成1 000個(gè)物理機(jī)以及500個(gè)虛擬機(jī)，分別對遺傳算法以及文中算法進(jìn)行5 000次迭代計(jì)算，計(jì)算結(jié)果如圖5所示。

圖5 兩種算法迭代過程

由圖5可知，文中的混合算法在2 500次左右收斂，而傳統(tǒng)遺傳算法在實(shí)驗(yàn)過程中，在5 000次迭代后收斂速度過于緩慢，未在本圖予以展示。因此能夠驗(yàn)證本算法相比于遺傳算法能夠更快地收斂，得到最優(yōu)解。

為了模擬出更加貼近數(shù)據(jù)中心真實(shí)運(yùn)行環(huán)境，使用更加豐富的虛擬機(jī)以及物理機(jī)配置模擬虛擬機(jī)請求情況以及物理機(jī)剩余資源，驗(yàn)證本算法能夠使數(shù)據(jù)中心溫度分布更加均勻，進(jìn)而能夠避免熱點(diǎn)的出現(xiàn)。物理機(jī)配置如表4所示，虛擬機(jī)請求配置如表5所示。

表4 物理機(jī)配置表

表5 虛擬機(jī)配置表

首先從物理機(jī)配置表中隨機(jī)生成800個(gè)物理機(jī)，代表當(dāng)前數(shù)據(jù)中心可用物理機(jī)以及可用資源量，再從虛擬機(jī)配置表中隨機(jī)生成1 000個(gè)虛擬機(jī)以及虛擬機(jī)請求資源量，模擬當(dāng)前數(shù)據(jù)中心某段時(shí)間虛擬機(jī)的請求。同時(shí)設(shè)定本算法中遺傳算法迭代次數(shù)為2 000次，在確定虛擬機(jī)啟動(dòng)的位置后，給各個(gè)虛擬機(jī)分配相同的任務(wù)；執(zhí)行完成任務(wù)后，可得出各類算法執(zhí)行任務(wù)后的能耗以及溫度。通過實(shí)驗(yàn)得出采用FF、SCA以及Random算法最終的能耗分別約為62.32kW·h、54.87kW·h和76.78kW·h，而筆者提出的算法最終能耗約為47.38kW·h，能耗降低比例分別約為23.97%、13.65%和38.29%，因此能夠證明筆者提出的算法能夠降低數(shù)據(jù)中心運(yùn)行能耗。為了驗(yàn)證筆者提出的算法能夠有效地避免數(shù)據(jù)中心熱點(diǎn)問題出現(xiàn)，從800個(gè)物理機(jī)中隨機(jī)挑選出20個(gè)物理機(jī)的運(yùn)行信息，其中物理機(jī)結(jié)束任務(wù)后的溫度如圖6所示，各類算法溫度均差圖如圖7所示。

圖6 物理機(jī)溫度圖

圖7 各類算法溫度均差

由以上結(jié)果可知，F(xiàn)F算法、SCA算法以及Random算法最終溫度分布波動(dòng)較大，而筆者提出的算法溫度波動(dòng)較小。通過圖5，同樣能夠驗(yàn)證此觀點(diǎn)。此外，通過計(jì)算，4種算法任務(wù)執(zhí)行后溫度方差分別為18.5、18.0、9.7、3.1，標(biāo)準(zhǔn)差分別為4.2、4.1、3.1、1.7。因此，根據(jù)實(shí)驗(yàn)結(jié)果可以驗(yàn)證，文中提出的算法能夠有效降低數(shù)據(jù)中心運(yùn)行過程中出現(xiàn)熱點(diǎn)的概率。

5 結(jié)束語

首先對虛擬機(jī)放置方法進(jìn)行闡述，可將虛擬機(jī)放置問題看作是可變裝箱問題。隨后介紹了本算法的兩個(gè)組成部分，分別為最佳適應(yīng)算法以及遺傳算法。最佳適應(yīng)算法以可用CPU資源作為參考對象，按照可用CPU資源大小對物理機(jī)進(jìn)行排序，且筆者提出一種判斷溫度趨勢的迫切值方法，在進(jìn)行虛擬機(jī)放置計(jì)算時(shí)提供有效的參考值。通過最佳適應(yīng)算法生成的目標(biāo)物理機(jī)序列作為遺傳算法的初始種群，在制定好高效的適應(yīng)度函數(shù)之后，對種群進(jìn)行交叉、變異以及選擇操作，使得種群向著最優(yōu)解不斷迭代。最后在仿真計(jì)算平臺cloudsim上進(jìn)行實(shí)驗(yàn)，通過實(shí)驗(yàn)數(shù)據(jù)充分驗(yàn)證了筆者提出的算法能夠降低數(shù)據(jù)中心運(yùn)行能耗以及避免熱點(diǎn)問題出現(xiàn)。