梁建斌

（廣東工業(yè)大學(xué)，廣州510006）

0 引言

云計(jì)算是分布式計(jì)算的一種特殊形式［1］，它可以按需訪問可配置的計(jì)算資源共享池，如網(wǎng)絡(luò)、服務(wù)器、存儲(chǔ)和服務(wù)［2］。它通過最少的管理工作或者與最少的服務(wù)進(jìn)行快速配置和發(fā)布［3］，是網(wǎng)格計(jì)算、并行計(jì)算和分布式計(jì)算的商業(yè)實(shí)現(xiàn)［4］。虛擬化技術(shù)提供云服務(wù)的技術(shù)支持，所有硬件資源經(jīng)過虛擬化成為統(tǒng)一的資源［5］。虛擬機(jī)根據(jù)客戶應(yīng)用和所需硬件資源（如CPU、RAM和ROM等）創(chuàng)建，然后托管到服務(wù)器上運(yùn)行［6］。

隨著客戶對(duì)計(jì)算能力的需求不斷增長(zhǎng)，促使云服務(wù)提供商部署越來越多的數(shù)據(jù)中心。用于服務(wù)器以及冷卻服務(wù)器的設(shè)備能源成本顯著增加，甚至已經(jīng)超過硬件的購(gòu)置成本［7］。云數(shù)據(jù)中心的能源相關(guān)成本達(dá)到運(yùn)營(yíng)總成本的一半［8］。因此，數(shù)據(jù)中心的生命周期成本通常由能耗決定［9］。目前，數(shù)據(jù)中心的資源使用與能源消耗比例并不高。即使服務(wù)器的CPU使用率只有10%，仍消耗服務(wù)器能耗峰值的50%以上的能源［10］。虛擬化技術(shù)允許一臺(tái)服務(wù)器上同時(shí)讓幾個(gè)虛擬機(jī)分享硬件資源，與Xen、VMware和Hyper-V一樣，允許將物理資源作為虛擬機(jī)進(jìn)行共享與調(diào)配［11］，使得虛擬機(jī)整合變得可行。

虛擬機(jī)整合可以降低能源消耗，因此虛擬機(jī)安置問題（Virtual Machine Placement，VMP）被提出，一個(gè)尋求在服務(wù)器上獲得虛擬機(jī)最佳部署的問題［12－13］。有效的分配有助于通過降低運(yùn)行主機(jī)的操作成本來實(shí)現(xiàn)經(jīng)濟(jì)效益的最大化［14］。VMP是NP難問題［15］，計(jì)算難度大，且需要盡可能少的運(yùn)算時(shí)間。過去的研究中，線性規(guī)劃是VMP的最早解決方式［16－17］。線性規(guī)劃簡(jiǎn)單，且確保獲得最優(yōu)解。但是隨著問題規(guī)模增大，計(jì)算時(shí)間將不可接受。啟發(fā)式算法被應(yīng)用解決VMP［18］，然而啟發(fā)式算法方法簡(jiǎn)單，計(jì)算時(shí)間短，但容易陷入局部最優(yōu)。使用群體算法解決VMP，如蟻群系統(tǒng)、遺傳算法（Genetic Algorithm，GA）［19］和 粒 子 群 優(yōu) 化（Particle Swarm Optimization，PSO）［20］，不僅避免陷入局部最優(yōu)，也能在可控時(shí)間內(nèi)得到高質(zhì)量解。然而，目前群體算法的運(yùn)算時(shí)間明顯過長(zhǎng)。雖然啟發(fā)式算法具有陷入局部最優(yōu)的風(fēng)險(xiǎn)，如果克服了這個(gè)缺點(diǎn)，可以在更短的時(shí)間內(nèi)獲得可行解。本文提出一種避免局部最優(yōu)解的啟發(fā)式算法——強(qiáng)插算法。

本文的其余部分如下：第1部分回顧VMP的相關(guān)研究；第2部分概述VMP的模型和強(qiáng)插算法的算法原理；第3部分描述強(qiáng)插算法的具體步驟和流程；第4部分分別使用強(qiáng)插算法，RGGA（Reordering Grouping Genetic Algorithm）［19］和OMEACS（Order Exchange and Migration Ant Colony System）［21］在不同的環(huán)境下實(shí)驗(yàn)并對(duì)數(shù)據(jù)進(jìn)行比較和分析；第5部分給出結(jié)論。

1 相關(guān)工作

線性規(guī)劃是最早用于解決虛擬機(jī)整合問題的算法［22］。FFD（First-Fit Decreasing）是背包問題中簡(jiǎn)單且結(jié)果可靠的算法。BISON（Bin Packing Solution Procedure）算法［23］首先對(duì)所有背包采用FFD策略，然后執(zhí)行分支與綁定的步驟。MBS（Minimal Bin Slack）［24］以背包為主，從物品中找到最適合當(dāng)前背包的組合。Wu等人［25］提出了一種基于模擬退火的局部搜索算法。Murtazaev等人提出了結(jié)合First-Fit和Best Fit算法的SERCON方法，同時(shí)考慮最小化服務(wù)器和發(fā)生遷移的虛擬機(jī)數(shù)量［26］。Zhu等人［27］同時(shí)考慮CPU、內(nèi)存和網(wǎng)絡(luò)帶寬因素，設(shè)計(jì)不同的算法，最大限度地降低能耗。Lago等人［28］同時(shí)考慮了服務(wù)器的硬件和帶寬，提出一種在異構(gòu)環(huán)境下調(diào)度虛擬機(jī)的啟發(fā)式算法。

進(jìn)化算法因?yàn)樵赩MP中的優(yōu)異表現(xiàn)而得到了發(fā)展［29］。VMP可被視作背包問題［19］，David Wilcox等人將FFD應(yīng)用到GGA（Grouping Genetic Algorithm）中，并提供了可靠的交叉算子，從而提出RGGA算法。Ibrahim等人［30］在考慮響應(yīng)時(shí)間的前提下，提出了一種自適應(yīng)遺傳算法。Mi等人［31］使用GA同時(shí)優(yōu)化資源使用率和減少能源消耗問題，多目標(biāo)模型開始出現(xiàn)，一個(gè)改良的GA［32］使用了模糊多目標(biāo)評(píng)價(jià)函數(shù)來優(yōu)化VMP。Wang等人［33］提出了同時(shí)考慮最大化資源使用率，均衡多維資源的使用率和減少應(yīng)用交流成本的優(yōu)化模型，并使用GA進(jìn)行解決。Raju等人［34］提出了EAMOCA（Energy-Aware Multi-Objective Chiropteran Algorithm）算法，其目的是在最大化資源利用率的同時(shí)最小化執(zhí)行時(shí)間和能耗。Li等人［35］考慮了硬盤資源的上限和下限，將改進(jìn)的PSO應(yīng)用到VMP中，避免陷入局部最優(yōu)。Wan等人［36］提出了一種同時(shí)考慮虛擬機(jī)熱／冷啟動(dòng)和熱／冷關(guān)閉的云計(jì)算資源分析模型，得到云平臺(tái)的性能指標(biāo)，并建立了一個(gè)多目標(biāo)優(yōu)化模型對(duì)云平臺(tái)的性能和成本進(jìn)行優(yōu)化。

2 背景

2.1 VMP

VMP目的是使用盡可能少的服務(wù)器容納所有的虛擬機(jī)。理想狀態(tài)下大部分服務(wù)器滿載。問題定義如下：

假設(shè)存在N個(gè)虛擬機(jī)（以下簡(jiǎn)稱虛擬機(jī)）與M個(gè)服務(wù)器（以下簡(jiǎn)稱服務(wù)器）。V＝｛v1，v2，...vi，...，vN｝代表虛擬機(jī)集合，vi＝｛vci，vri｝代表虛擬機(jī)vi需求的CPU與RAM資源。P＝｛p1，p2，...pi，...，pM｝代表服務(wù)器集合。pj＝｛pcj，prj｝代表服務(wù)器pj的CPU與RAM資源上限。B＝｛b1，b2，...，bi，...，bN｝代表安置方案，i∈［1，N］代表虛擬機(jī)編號(hào)，bi∈［1，N］表示將vi放入對(duì)應(yīng)編號(hào)的服務(wù)器中。VMP問題如下描述：

式（2）中yj是服務(wù)器是否空閑的標(biāo)志。如果yj＝0，代表該服務(wù)器空閑。式（3）與（4）分別統(tǒng)計(jì)每臺(tái)服務(wù)器中虛擬機(jī)占用CPU和RAM的總和，并要求各項(xiàng)資源的使用不能超出該服務(wù)器對(duì)應(yīng)資源的上限。

2.2 First-Fit算法

用于VMP的First-Fit算法最早由文獻(xiàn)［5］提出。First-Fit算法難以得到VMP的最優(yōu)解，但是時(shí)間復(fù)雜度低，且步驟簡(jiǎn)單，用作強(qiáng)插算法的評(píng)價(jià)函數(shù)。

2.3 強(qiáng)插算法

在虛擬機(jī)的安置過程中會(huì)出現(xiàn)一個(gè)趨勢(shì)：各項(xiàng)資源需求小的虛擬機(jī)（以下簡(jiǎn)稱小虛擬機(jī)）大量存在于高負(fù)載服務(wù)器中，各項(xiàng)資源需求量大的虛擬機(jī)（以下簡(jiǎn)稱大虛擬機(jī)）大量存在于低負(fù)載服務(wù)器中。這個(gè)趨勢(shì)導(dǎo)致安置方案過早收斂于局部最優(yōu)解。本文提出的強(qiáng)插算法的設(shè)計(jì)思路是避免這種趨勢(shì)的發(fā)生。也就是使用低負(fù)載服務(wù)器中的大虛擬機(jī)交換高負(fù)載服務(wù)器中若干個(gè)小虛擬機(jī)，從而打破安置方案的原有結(jié)構(gòu)，而小虛擬機(jī)也盡可能不交換到低負(fù)載服務(wù)器中，進(jìn)一步降低低負(fù)載服務(wù)器的負(fù)載。當(dāng)存在若干個(gè)服務(wù)器負(fù)載足夠低，可進(jìn)行虛擬機(jī)再安置，減少服務(wù)器數(shù)量。

強(qiáng)插算法需要解決的問題是：已知大虛擬機(jī)和服務(wù)器集合，如何從服務(wù)器集合中找到含有最合適用作交換的小虛擬機(jī)集合的服務(wù)器？該問題可被拆分為兩個(gè)子問題：

（1）交換后，服務(wù)器負(fù)載率的影響是否最低？

（2）交換的小虛擬機(jī)集合對(duì)其他服務(wù)器的提升效果是否最好？

強(qiáng)插算法的解決方案如下：

（1）從各個(gè)服務(wù)器中選出一批與大虛擬機(jī)需求比較接近的小虛擬機(jī)集合，并限制在對(duì)服務(wù)器負(fù)載率影響在不大的范圍里。為此算法使用了強(qiáng)插算子確保選出的小虛擬機(jī)集合的需求總和與大虛擬機(jī)的需求盡可能接近。

（2）從選出的所有集合中選出一個(gè)提升其他服務(wù)器負(fù)載表現(xiàn)最好的集合。為此算法使用了再填充算子，讓所有小虛擬機(jī)集合都嘗試安置到其他高負(fù)載服務(wù)器上。

強(qiáng)插算法每次迭代都需要先對(duì)服務(wù)器篩選。因此強(qiáng)插算法分為三個(gè)部分：選舉算子、變異算子和調(diào)整算子。

3 算法流程

3.1 初始化和參數(shù)設(shè)置

強(qiáng)插算法的參數(shù)會(huì)隨著計(jì)算規(guī)模增大而增大，因此需要對(duì)問題先執(zhí)行一次First-Fit算法，得到初始的安置方案B。B的服務(wù)器數(shù)量與最優(yōu)安置方案所需要的服務(wù)器數(shù)量處于同一數(shù)量級(jí)，用于估計(jì)計(jì)算規(guī)模。根據(jù)Pub計(jì)算：

其中pNum和wNum分別是候選服務(wù)器集合規(guī)模和惡劣服務(wù)器集合的規(guī)模。

3.2 選舉算子

選舉算子分為三步：評(píng)價(jià)，選出惡劣服務(wù)器集合，和選出候選服務(wù)器集合。首先每臺(tái)服務(wù)器統(tǒng)計(jì)各項(xiàng)資源使用情況，然后根據(jù)以下公式得到評(píng)價(jià)值：

其中pcj和prj分別是服務(wù)器的CPU和RAM資源上限，pccj和pcrj分別是服務(wù)器當(dāng)前CPU和RAM的使用情況，ac和ar是服務(wù)器CPU資源上限和RAM資源上限的比值。當(dāng)服務(wù)器CPU資源上限是RAM資源上限兩倍時(shí)，ac＝1，ar＝2。服務(wù)器的負(fù)載率越高，評(píng)價(jià)值越高。選取評(píng)價(jià)值最低的wNum臺(tái)服務(wù)器構(gòu)成惡劣服務(wù)器集合。

候選服務(wù)器集合則由兩部分服務(wù)器構(gòu)成：隨機(jī)服務(wù)器集合和較差服務(wù)器集合。較差服務(wù)器集合是除了惡劣服務(wù)器集合以外，負(fù)載率最差的服務(wù)器集合。由于負(fù)載率較低，在再填充算子中可以被安置入更多小虛擬機(jī)。隨機(jī)服務(wù)器集合是從未被選取的其他服務(wù)器中隨機(jī)選取。其中，較差服務(wù)器集合規(guī)模worsePMsSize

和隨機(jī)服務(wù)器集合規(guī)模randomPMsSize分別如下：

其中，ω是較差服務(wù)器占比。

3.3 變異算子

變異算子由強(qiáng)插算子和再填充算子組成。在一次變異中，需要依次選取惡劣服務(wù)器集合中的每一個(gè)大虛擬機(jī)執(zhí)行強(qiáng)插算子，結(jié)果交由再填充算子進(jìn)一步處理，決定最終的交換方案。

強(qiáng)插算子試圖將惡劣服務(wù)器集合中的所有大虛擬機(jī)都交換到候選服務(wù)器集合中，對(duì)負(fù)載率影響盡可能小的情況下改變候選服務(wù)器中的虛擬機(jī)結(jié)構(gòu)。

為了交換的大虛擬機(jī)和小虛擬機(jī)集合的需求盡可能接近，在強(qiáng)插算子中，選中的大虛擬機(jī)需要對(duì)所有候選服務(wù)器進(jìn)行一次強(qiáng)插算子，得到若干個(gè)候選的小虛擬機(jī)集合。大虛擬機(jī)和所有小虛擬機(jī)集合將通過再填充算子進(jìn)一步處理。強(qiáng)插算子分為4個(gè)步驟：排序、產(chǎn)生計(jì)算序列、評(píng)價(jià)和篩選。

排序是以大虛擬機(jī)為對(duì)照，將候選服務(wù)器中的虛擬機(jī)進(jìn)行分類和排序。排序的順序?yàn)椋篈類虛擬機(jī)、B類虛擬機(jī)、C類虛擬機(jī)和D類虛擬機(jī)。其中，A類虛擬機(jī)的各項(xiàng)資源需求都大于等于大虛擬機(jī)；B類虛擬機(jī)則具有一項(xiàng)資源需求大于大虛擬機(jī)，其余資源需求小于大虛擬機(jī)；C類虛擬機(jī)的資源需求都小于大虛擬機(jī)，但至少一項(xiàng)資源需求不低于大虛擬機(jī)該項(xiàng)資源需求的一半；D類虛擬機(jī)的資源需求都小于大虛擬機(jī)該項(xiàng)資源需求的一半。

產(chǎn)生計(jì)算序列將產(chǎn)生等同于B、C、D類虛擬機(jī)數(shù)量總和的計(jì)算序列。A類虛擬機(jī)不會(huì)產(chǎn)生計(jì)算序列，因?yàn)锳類虛擬機(jī)各項(xiàng)資源需求都大于大虛擬機(jī)，如果發(fā)生交換，只讓服務(wù)器的各項(xiàng)資源使用率下降，且難以再填充到其他服務(wù)器。每個(gè)計(jì)算序列都以P排序的結(jié)果副本為初始序列，選取B、C、D類虛擬機(jī)中的未被選取過的一個(gè)虛擬機(jī)，從原來的位置中取出并放到序列的末尾，最后將大虛擬機(jī)放到序列的首位。形成一條新的計(jì)算序列。

對(duì)每一條計(jì)算序列使用First-Fit算子進(jìn)行計(jì)算并根據(jù)以下公式進(jìn)行評(píng)價(jià)：

其中pccsj和pcrsj分別是大虛擬機(jī)交換到服務(wù)器后，服務(wù)器的CPU和RAM使用情況。適應(yīng)度越少，說明交換方案在強(qiáng)插算子中越合理。如果交換后，服務(wù)器的各項(xiàng)資源使用情況都上升，說明本次交換可以單純地提升服務(wù)器的負(fù)載率，因此適應(yīng)度設(shè)置為0。否則使用服務(wù)器的資源空閑權(quán)重和作為評(píng)價(jià)值。

每條計(jì)算序列在經(jīng)過First-Fit算子后，除了適應(yīng)度外，還獲得了在First-Fit算子中無法被安置入服務(wù)器的虛擬機(jī)，它們構(gòu)成了小虛擬機(jī)集合。小虛擬機(jī)集合將在大虛擬機(jī)對(duì)所有候選服務(wù)器都進(jìn)行強(qiáng)插算子后進(jìn)行匯總，并將交給再填充算子進(jìn)行進(jìn)一步的處理。

變異算子的最后，最終交換方案中剩余的小虛擬機(jī)集合將被安置到惡劣服務(wù)器中。為了更進(jìn)一步降低惡劣服務(wù)器集合的總負(fù)載，再填充算子將盡可能地將虛擬機(jī)保留在候選服務(wù)器集合中。為了找到保留效果最好的小虛擬機(jī)集合，需要對(duì)強(qiáng)插算子得到的所有小虛擬機(jī)集合都執(zhí)行一次再填充算子。再填充算子具有兩個(gè)步驟：排序和再填充與評(píng)價(jià)。

再填充算子通過提升候選服務(wù)器集合的總負(fù)載來降低惡劣服務(wù)器集合的總負(fù)載。一方面，資源需求量更大的虛擬機(jī)更難被安置入服務(wù)器。另一方面，將資源需求量大的虛擬機(jī)安置入候選服務(wù)器集合更符合再填充算子的目標(biāo)。再填充算子需要先從資源需求量大的虛擬機(jī)開始執(zhí)行，因此需要先對(duì)每個(gè)小虛擬機(jī)集合根據(jù)資源需求總量進(jìn)行排序。資源需求總量的公式如下：

資源需求總量越大的虛擬機(jī)在排序后的序列中的位置越靠前。然后，根據(jù)排序后的序列執(zhí)行再填充。首先，獲得除了該小虛擬機(jī)集合對(duì)應(yīng)的服務(wù)器以外的所有候選服務(wù)器當(dāng)前資源使用情況的副本。接著，從序列依次取出虛擬機(jī)，遍歷副本中的每個(gè)服務(wù)器。如果虛擬機(jī)可以被安置到該服務(wù)器中，那么更新副本中該服務(wù)器的資源使用情況，并從序列中去除掉該虛擬機(jī)。最后，計(jì)算序列的適應(yīng)度。序列中可能存在無法被安置的虛擬機(jī)，而序列的適應(yīng)度即序列中剩余虛擬機(jī)的資源需求總量。剩余的虛擬機(jī)集合和適應(yīng)度值是該小虛擬機(jī)集合在再填充算子中的結(jié)果。

選出適應(yīng)度最低的小虛擬機(jī)集合，它以及所對(duì)應(yīng)的服務(wù)器編號(hào)和大虛擬機(jī)就是大虛擬機(jī)最終的交換方案。剩余的虛擬機(jī)集合將被隨機(jī)安置到惡劣服務(wù)器集合中的任意服務(wù)器中，且不會(huì)再參與變異算子。

3.4 調(diào)整算子

變異算子降低了惡劣服務(wù)器集合的總負(fù)載，但同時(shí)也帶來了新的問題：

（1）降低了總負(fù)載，但是不能降低服務(wù)器數(shù)量。

（2）由于變異算子的最后，將虛擬機(jī)隨機(jī)安置到惡劣服務(wù)器，可能會(huì)出現(xiàn)超載的情況。

問題1中，普遍的情況是存在若干低負(fù)載服務(wù)器，可通過重新安置其中的虛擬機(jī)來降低服務(wù)器的使用數(shù)量。問題2中，可以將重新安置超載服務(wù)器和低負(fù)載服務(wù)器中的虛擬機(jī)消除超載現(xiàn)象。因此，問題1和2可以合并為一個(gè)比VMP規(guī)模小的子問題。

子問題的復(fù)雜度低于VMP。由于出現(xiàn)問題的服務(wù)器都是惡劣服務(wù)器，經(jīng)歷了變異算子，惡劣服務(wù)器集合的總負(fù)載很有可能降低了。原有的惡劣服務(wù)器集合安置已經(jīng)是合理的安置方案，再得到一個(gè)合理的安置方案并不困難。另外，變異算子已經(jīng)占用了大量運(yùn)算時(shí)間，算法需要采用時(shí)間更短的調(diào)整算子來調(diào)整惡劣服務(wù)器集合中的虛擬機(jī)。調(diào)整算子分為兩個(gè)步驟：挑選服務(wù)器和remove算子。

首先，根據(jù)負(fù)載情況從所有服務(wù)器中選出符合以下條件的服務(wù)器：

其中，是負(fù)載系數(shù)。當(dāng)一項(xiàng)資源使用率低于μ時(shí)，認(rèn)為服務(wù)器的負(fù)載率過低。負(fù)載率過低的服務(wù)器和超載服務(wù)器將通過remove算子作進(jìn)一步的處理。

在RGGA算法中，變異算子由swap算子，move算子和remove算子組成，swap算子和move算子提供的有效變異最多。但這兩個(gè)算子只能作用于兩個(gè)服務(wù)器之間，不適合多個(gè)服務(wù)器同時(shí)進(jìn)行虛擬機(jī)整合。因此，強(qiáng)插算法采用remove算子作為調(diào)整算子。

為了提高remove算子的效率，調(diào)整算子將重復(fù)執(zhí)行a次，選取服務(wù)器數(shù)量最少的安置方案作為調(diào)整算子的最終方案。

3.5 總流程

算法的總流程如圖1所示，具體步驟如下。

圖1 總體流程圖

（1）使用First-Fit算法，獲得初始安置方案B和Pub，根據(jù)Pub設(shè)置pNum和wNum。設(shè)置t＝0和Tmax。

（2）計(jì)算各個(gè)服務(wù)器的資源使用情況，并根據(jù)資源使用情況對(duì)所有服務(wù)器進(jìn)行排序。

（3）使用選舉算子分別選出候選服務(wù)器集合和惡劣服務(wù)器集合。

（4）逐一選取惡劣服務(wù)器集合中的所有虛擬機(jī)，使用強(qiáng)插算子獲得該虛擬機(jī)對(duì)應(yīng)的交換方案。并執(zhí)行交換方案，更新候選服務(wù)器集合中的虛擬機(jī)構(gòu)成。

（5）選出超載和低負(fù)載服務(wù)器，使用調(diào)整算子獲得一個(gè)合理的再安置方案。

（6）如果t＝Tmax，算法結(jié)束。否則，設(shè)置t＝t＋1并跳到步驟（2）。

4 實(shí)驗(yàn)部分

實(shí)驗(yàn)部分將測(cè)試強(qiáng)插算法的性能。所有算法均使用Java實(shí)現(xiàn)，硬件環(huán)境CPU型號(hào)Intel Core i5－7550，8G內(nèi)存。包含4種不同環(huán)境下的實(shí)驗(yàn)：TestA1和TestA2是同構(gòu)服務(wù)器環(huán)境下不同虛擬機(jī)類型的兩個(gè)測(cè)試，TestB和TestC分別在同構(gòu)服務(wù)器與異構(gòu)服務(wù)器的環(huán)境下瓶頸資源測(cè)試。強(qiáng)插算法的對(duì)比算法是使用遺傳算法的RGGA和使用蟻群系統(tǒng)的OMEACS。強(qiáng)插算法的相關(guān)參數(shù)設(shè)置如下：ω＝0.4，μ＝0.99，a＝50。RGGA和OMEACS的參數(shù)值與原始論文中的一致。TestA1，TestA2和TestB中，最大迭代次數(shù)均為Tmax＝100，TestC由于異構(gòu)環(huán)境更復(fù)雜，最大迭代次數(shù)均為Tmax＝1000。所有算法的最大迭代次數(shù)和FEs如表1所示。所有算法均每個(gè)實(shí)例中都獨(dú)立重復(fù)執(zhí)行100次，F(xiàn)Es和運(yùn)算時(shí)間對(duì)應(yīng)首次得到全局最優(yōu)解所需要的FEs和運(yùn)算時(shí)間。

表1 各個(gè)算法最大迭代次數(shù)和FEs

4.1 TestA大規(guī)模同構(gòu)服務(wù)器測(cè)試

TestA1的實(shí)例生成方法提出于RGGA，與TestA2具有相同的特點(diǎn)：理想安置方案中，服務(wù)器的所有資源都被生成的虛擬機(jī)占滿。TestA1具有9個(gè)實(shí)驗(yàn)用例。所有用例的服務(wù)器都具有500單位CPU和500單位RAM；每個(gè)虛擬機(jī)的CPU需求是位于［1，128］的隨機(jī)整數(shù)，RAM需求是位于［0，100］的隨機(jī)整數(shù)。TestA1的虛擬機(jī)生成方法以服務(wù)器為單位，不斷生成虛擬機(jī)，直到存在虛擬機(jī)生成后，服務(wù)器某項(xiàng)資源不足以負(fù)載該虛擬機(jī)時(shí)，將該虛擬機(jī)的各項(xiàng)資源需求改為服務(wù)器剩余資源量，從而實(shí)現(xiàn)滿載。除最后一個(gè)虛擬機(jī)外，其他虛擬機(jī)都是隨機(jī)生成，因此各個(gè)虛擬機(jī)之間的資源需求差距很大。

續(xù)表

從表2看出，強(qiáng)插算法總能獲得比其他算法更好的結(jié)果，體現(xiàn)了強(qiáng)插算法在TestA1中的穩(wěn)定性。RGGA在實(shí)例A11和A15中獲得與強(qiáng)插算法相同的最優(yōu)解，但是平均值顯示出結(jié)果并不穩(wěn)定。OMEACS則難以獲得與強(qiáng)插算法同等質(zhì)量的解。此外，在所有實(shí)例中，強(qiáng)插算法首次獲得最優(yōu)全局最優(yōu)解的時(shí)間和FEs都遠(yuǎn)低于RGGA和OMEACS。

表2 TestA1在不同虛擬機(jī)規(guī)模下的實(shí)驗(yàn)結(jié)果對(duì)比

TestA2的虛擬機(jī)生成方式與TestA1不同。首先確定服務(wù)器安置的虛擬機(jī)數(shù)量，按照均勻分布的方式生成虛擬機(jī)的各項(xiàng)資源需求。因此，TestA2的所有實(shí)例的理想安置方案中的每個(gè)服務(wù)器的托管虛擬機(jī)之間的資源需求差別不大。對(duì)比表2和表3，TestA2具有相同的服務(wù)器和更少的虛擬機(jī)，但所有算法都需要更多的運(yùn)算時(shí)間和FEs，說明TestA2難度高于TestA1。從表3可見，強(qiáng)插算法穩(wěn)定得到最高質(zhì)量的安置方案。RGGA在TestA2的總體表現(xiàn)弱于TestA1，僅在實(shí)例TestA21獲得與強(qiáng)插算法相同質(zhì)量的安置方案，在其他實(shí)例則無法穩(wěn)定。OMEACS無法獲得與強(qiáng)插算法相同質(zhì)量的安置方案，且在A21、A22、A27中過早收斂于局部最優(yōu)解中。強(qiáng)插算法在時(shí)間復(fù)雜度上依然優(yōu)秀。

表3 TestA2在不同虛擬機(jī)規(guī)模下的實(shí)驗(yàn)結(jié)果對(duì)比

從TestA可以看出，強(qiáng)插算法可以穩(wěn)定得到接近于最優(yōu)安置方案的方案，且首次獲得最優(yōu)全局最優(yōu)解的時(shí)間也遠(yuǎn)低于其他算法，說明強(qiáng)插算法優(yōu)化規(guī)則的合理性。

4.2 TestB大規(guī)模同構(gòu)服務(wù)器測(cè)試

因?yàn)榘l(fā)展趨勢(shì)，RAM的體量比CPU大，往往CPU密集型的任務(wù)導(dǎo)致瓶頸資源問題。TestB設(shè)置了9個(gè)不同規(guī)模的實(shí)例B1～B9測(cè)試三個(gè)算法在瓶頸資源環(huán)境下的性能。所有實(shí)例服務(wù)器均擁有16核CPU和32GB的RAM；虛擬機(jī)的CPU需求是［1，4］中的隨機(jī)整數(shù)，RAM需求是［1，8］中的隨機(jī)整數(shù)，所有隨機(jī)整數(shù)服從均勻分布。每個(gè)虛擬機(jī)有25%幾率需求4內(nèi)核，同時(shí)有25%幾率需求7GB或者8GB的RAM，因此CPU與RAM的使用率接近10∶9，CPU成為了瓶頸資源。TestB的虛擬機(jī)生成方法完全隨機(jī)，不會(huì)提前設(shè)置需求的服務(wù)器數(shù)量，并在生成后使用以下公式對(duì)服務(wù)器數(shù)量進(jìn)行估計(jì)：

其中，pci和pri分別是第i臺(tái)服務(wù)器能提供的CPU和RAM資源上限，分別是該服務(wù)器上所有虛擬機(jī)需求的CPU和RAM總量。推算公式目的是以所有虛擬機(jī)需求總和的最大值來推算至少需要的服務(wù)器數(shù)量，在實(shí)際測(cè)試中，由于虛擬機(jī)需求的隨機(jī)性和復(fù)雜性，需要的服務(wù)器數(shù)量可能大于這個(gè)值。

表4包含了三個(gè)算法在TestB的表現(xiàn)。RGGA僅在B1和B3中獲得最優(yōu)安置方案，OMEACS僅在B1和B2中獲得最優(yōu)安置方案，但是兩個(gè)算法都不穩(wěn)定。一方面，強(qiáng)插算法在所有的實(shí)例都能穩(wěn)定地獲得最優(yōu)安置方案。另一方面，強(qiáng)插算法首次獲得最優(yōu)解所需要的運(yùn)算時(shí)間和FEs遠(yuǎn)低于RGGA和OMEACS。

表4 TestB在不同虛擬機(jī)規(guī)模下的實(shí)驗(yàn)結(jié)果對(duì)比

4.3 TestC異構(gòu)服務(wù)器環(huán)境下瓶頸資源問題

之前的測(cè)試，所有服務(wù)器都是同構(gòu)服務(wù)器。TestC將在異構(gòu)環(huán)境下進(jìn)行測(cè)試。TestC根據(jù)目前兩種主流服務(wù)器型號(hào)設(shè)置實(shí)驗(yàn)：s0（32核CPU和64GB的RAM）和s1（64核CPU和256GB內(nèi)存）。TestC包含5個(gè)實(shí)例，s0和s1服務(wù)器的比例為1∶1。虛擬機(jī)的CPU資源需求是處于區(qū)間［1，8］的隨機(jī)整數(shù)，RAM資源需求是處于［1，32］的隨機(jī)整數(shù)。因此，TestC也是一個(gè)瓶頸資源場(chǎng)景。

表5包含了三種算法在TestC中的性能。平均值顯示強(qiáng)插算法和RGGA的性能相近。RGGA獲得所有實(shí)例中質(zhì)量最好的安置方案，而強(qiáng)插算法在C2和C5中無法獲得與RGGA相同質(zhì)量的安置方案。OMEACS僅在C1中獲得最優(yōu)安置方案。這意味著在異構(gòu)環(huán)境下，VMP問題變得更復(fù)雜，強(qiáng)插算法雖然表現(xiàn)不是最優(yōu)秀，但首次獲得最優(yōu)全局最優(yōu)解的時(shí)間和FEs仍遠(yuǎn)遠(yuǎn)低于RGGA。而RGGA雖然可以獲得最優(yōu)安置方案，但每次的運(yùn)算結(jié)果并不穩(wěn)定，導(dǎo)致運(yùn)算時(shí)間不穩(wěn)定。

表5 TestC在不同虛擬機(jī)規(guī)模下的實(shí)驗(yàn)結(jié)果對(duì)比

4.4 參數(shù)測(cè)試

強(qiáng)插算法包含三個(gè)參數(shù)：較差服務(wù)器占比系數(shù)ω，調(diào)整數(shù)量μ和校驗(yàn)系數(shù)a。為了研究這些參數(shù)對(duì)于安置方案質(zhì)量的影響，使用TestA1對(duì)所有實(shí)例進(jìn)行參數(shù)性能的評(píng)估。

首先測(cè)試較差服務(wù)器占比系數(shù)ω。在其余參數(shù)不變的情況下設(shè)置了從0.1－1.0的11個(gè)參數(shù)實(shí)驗(yàn)。圖2在較差服務(wù)器占比系數(shù)在TestA的所有測(cè)試實(shí)例。隨著ω的增加，F(xiàn)Es不斷下降。但是運(yùn)算時(shí)間經(jīng)歷了下降后上升，曲線大致呈現(xiàn)凹谷的形狀。這說明當(dāng)上升后，強(qiáng)插算子次數(shù)減少，強(qiáng)插算子運(yùn)算時(shí)間上升，整體運(yùn)算時(shí)間上升。當(dāng)時(shí)ω＝0.4，運(yùn)算時(shí)間達(dá)到最小值。所以，算法采用ω＝0.4。

圖2 不同的較差服務(wù)器占比系數(shù)在TestA1各個(gè)實(shí)例的表現(xiàn)

圖3是調(diào)整系數(shù)在TestA的所有測(cè)試實(shí)例。圖3中，F(xiàn)Es大致上隨著調(diào)整系數(shù)的增加而減少，運(yùn)算時(shí)間大致上呈現(xiàn)凹谷形狀。強(qiáng)插算法通過強(qiáng)插算子和調(diào)整算子優(yōu)化結(jié)果，調(diào)整次數(shù)少，會(huì)使算法依賴強(qiáng)插算子優(yōu)化結(jié)果，導(dǎo)致運(yùn)算時(shí)間增長(zhǎng)。調(diào)整次數(shù)多，會(huì)進(jìn)無效的調(diào)整算子。因此，在a＝50時(shí)獲得可接受的FEs和運(yùn)算時(shí)間。

圖3 不同的調(diào)整系數(shù)在TestA1各個(gè)實(shí)例的表現(xiàn)

圖4是校驗(yàn)系數(shù)在TestA的所有測(cè)試實(shí)例。由于μ＝1無法獲得最優(yōu)安置方案，因此不予顯示。大體上，F(xiàn)es一致呈現(xiàn)下降的趨勢(shì)。在TestA11-TestA14時(shí)，運(yùn)算時(shí)間在μ＝0.98時(shí)獲得最小值。而隨著問題規(guī)模不斷增加，μ＝0.99才能獲得最小的運(yùn)算時(shí)間。所以，強(qiáng)插算法采用μ＝0.99。

圖4 不同的校驗(yàn)系數(shù)在TestA1各個(gè)實(shí)例的表現(xiàn)

4.5 收斂速度分析

本部分將評(píng)價(jià)強(qiáng)插算法的收斂性。使用TestA1為測(cè)試實(shí)例，使用強(qiáng)插算法，RGGA進(jìn)行收斂性分析。每個(gè)算法具有100次迭代，獨(dú)立重復(fù)運(yùn)行100次。

圖5是兩個(gè)算法在TestA各個(gè)實(shí)例中的收斂曲線圖。曲線中的每一個(gè)數(shù)值是算法100次運(yùn)行的平均值。盡管RGGA一直在收斂，但是收斂速度過慢，甚至停留在局部最優(yōu)解中，導(dǎo)致整體運(yùn)算時(shí)間的增加。強(qiáng)插算法的初始化與RGGA類似，因此初始階段與RGGA接近，但是收斂速度快于RGGA，因此最早獲得質(zhì)量最高的安置方案。

圖5 強(qiáng)插算法和RGGA的收斂曲線對(duì)比

5 結(jié)語

能源消耗已經(jīng)是數(shù)據(jù)中心的主要運(yùn)營(yíng)成本，已有的VMP算法可以獲得高質(zhì)量的安置方案，但是運(yùn)算時(shí)間長(zhǎng)。這促使我們提出基于啟發(fā)式算法的強(qiáng)插算法，在更短運(yùn)算時(shí)間獲得合理的虛擬機(jī)安置方案，通過關(guān)閉空閑服務(wù)器最小化活動(dòng)服務(wù)器數(shù)量。VMP問題是一個(gè)復(fù)雜的NP難問題，每個(gè)服務(wù)器中的虛擬機(jī)不僅作用于服務(wù)器的負(fù)載情況，更影響著其他服務(wù)器的虛擬機(jī)構(gòu)成。當(dāng)一個(gè)服務(wù)器中小虛擬機(jī)數(shù)量過多時(shí)，其他服務(wù)器由于缺少小虛擬機(jī)，空閑資源無法被利用，相互之間也難以進(jìn)行虛擬機(jī)交換，因而負(fù)載率不高。為了解決這個(gè)現(xiàn)象，本文提出了強(qiáng)插算法。其中，強(qiáng)插算子將大虛擬機(jī)強(qiáng)行到服務(wù)器中，打亂服務(wù)器的虛擬機(jī)原有的虛擬機(jī)結(jié)構(gòu)，釋放其中的小虛擬機(jī)，提高其他服務(wù)器負(fù)載。由于強(qiáng)插算子的強(qiáng)隨機(jī)性和明確的目的性，克服了啟發(fā)式算法的早熟問題。調(diào)整算子則用于調(diào)整強(qiáng)插算子導(dǎo)致的安置方案不合理的問題。

強(qiáng)插算法被用于不同規(guī)模下的同構(gòu)或異構(gòu)服務(wù)器的測(cè)試中。結(jié)果表明強(qiáng)插算法在絕大部分測(cè)試用例中可以穩(wěn)定獲得最高質(zhì)量的安置方案，且運(yùn)算時(shí)間最短。即使不能獲得最高質(zhì)量的安置方案，結(jié)果依然相當(dāng)接近。結(jié)論是，強(qiáng)插算法可以被視作一種高效且高速的VMP算法。