云計算環境下虛擬機部署策略研究

袁愛平

（長沙民政學院軟件學院 長沙 410004）

1 引言

云計算是從分布式計算、網格計算和并行計算等概念發展而來一種新型的計算模式，它是一種基于互聯網相關服務的增加、使用和交付模式。虛擬機資源是云計算環境中的主要資源，數據中心的各種硬件資源通過使用虛擬化技術形成虛擬資源池，系統動態部署虛擬機，用戶透明使用。隨著用戶數量的持續增加，數據中心規模不斷擴大，如何提高云計算環境中的虛擬機資源利用效率以及用戶響應的等待時間，已成為云計算資源部署的關鍵問題。

虛擬機部署策略的優劣決定了數據中心云計算系統的性能。目前，針對云計算環境中的虛擬機資源部署問題，專家和學者們進行廣泛研究并提出了各種策略。文獻［1］通過計算待部署虛擬機和服務器性能向量的相對距離，獲得待部署虛擬機的匹配向量，將匹配向量與系統負載向量綜合分析得到虛擬機的部署位置；文獻［2］提出了多周期分配策略，建立了多周期分配的虛擬機負載均衡問題的數學模型，利用改進的蟻群算法進行了求解；文獻［3］提出了一種面向多目標優化的虛擬機初始放置方法，基于改進的分組遺傳算法和多目標模糊評估方法計算虛擬機的放置問題。本文在分組遺傳算法的基礎上，提出了一種負載均衡的虛擬機調度算法LBGA，綜合考慮虛擬機資源提供過程中資源容量的限制以及負載均衡的需求，從空間利用率、重量和負載變化三個方面來定義評價函數，并通過加權方法定義適應度函數。另外，對選擇和變異操作進行了優化，以獲得算法的近似最優解。最后通過云仿真計算器CloudSim［4］進行了仿真，仿真結果表明本文的算法均衡了服務器資源的分配，提高了資源的綜合利用率。

2 調度算法模型

我們假設有m臺可用的物理服務器，定義為M={PSi|1≤i≤m}，另有n個虛擬機調度請求，定義為N={VMi|1≤i≤n}。虛擬機需物理服務器上的多維資源來實行運算，定義虛擬機i對資源的請求向量為 qi={qi。1qi。2… qi。k} ，qi。j表示虛擬機 i對 j類型資源的需求量。同樣，定義物理服務器i能提供的資源容量向量為 ci={ci。1ci。2… ci。k} ，ci。j表示服務器i能提供的 j類型資源容量。服務器資源負載等于虛擬機所占各維資源向量的和。

定義1：S={S1。S2。…。Sn}表示虛擬機的映射解集合，Si表示主機i上的一種虛擬機映射方案，令T為負載監測周期，根據主機負載的變化規律，將T劃分為r個時間段為

定義2：假設虛擬機的負載在各個時間段中是穩定的，定義虛擬機VMi在時間段k的負載為VL(i。k)，則周期T 中主機 PSi的總負載 PL(i。T)為

通常虛擬機配置到主機后，資源負載會發生很大的變化，因此，需通過虛擬機的動態遷移來調整資源負載以達到負載均衡，我們把虛擬機配置到物理服務器后在周期T內的負載標準偏差設置為

其中

σ(T)反映了樣本總體相對于平均值的離散程度，即表示了各物理主機負載相對于平均負載的離散程度。

由于云計算環境中虛擬機所需物理服務器的資源具有多維性（如不同的CPU、內存和I/O等），各維資源的請求及性能差異很大，因此可以通過資源使用狀況的負載度量來反映多維資源的利用情況。本文將同時考慮主機的三種資源：CPU、內存和I/O，把虛擬機負載定義為

其中 01。12。131，且 11+12+13=1，表示資源的負載權值。 LICPU、LIMem和 LIIO分別表示為主機中CPU、內存和I/O的利用率。我們算法的目標是啟動最少的物理服務器以獲得最大的資源利用率，同時確保被分配的資源不超過服務器的容量上限。

3 算法實現

如上所述，本文在設計算法時重點考慮多維資源之間的均衡負載，以實現最小化物理服務器啟動數量和最大化資源綜合利用率的目標。基于服務器聚合思想的虛擬機調度屬于組合優化中的裝箱問題，傳統的遺傳算法由于編碼等問題對于分組問題的適應性很差［5］。因此，本文提出了一種改進的分組遺傳算法來求解虛擬機的調度問題。該算法在分組遺傳算法的基礎上，采用負載均衡的資源分配方案，從空間利用率、重量和負載變化三個方面來定義適應度函數。另外算法采用輪盤賭法來選擇個體，并優化了種群中個體之間的交叉及變異，以快速有效地獲取近似最優解。其算法流程如圖1所示。

圖1 算法基本流程

3.1 基因編碼

在給出的分組遺傳算法中，為了避免編碼的長度過長而影響計算的效率，以及后面的交叉和變異等操作不會破壞服務器的硬約束條件，我們用服務器的數量來決定染色體的基因位數。染色體中的每一位基因代表一個物理服務器，基因的值表示該服務器上裝載的虛擬機集合，也就是虛擬機的一個分組，如圖2所示，A、B代表物理服務器，1～5代表虛擬機，染色體的編碼為：AB（A：｛1、3｝，B：｛2、4、5｝）。

圖2 算法中的染色體基因編碼示例

3.2 適應度函數

適應度函數的選取直接影響到分組遺傳算法的收斂速度以及能否找到最優解，為了達到最小化物理服務器啟動數量和最大化資源綜合利用率的目標，適應度函數的設計應綜合考慮物理服務器的使用數量和多維資源的均衡分配。考慮到虛擬機資源提供過程中資源容量的限制以及負載均衡的需求，從空間利用率、重量和負載變化三個方面來定義評價函數，并通過加權方法定義最終的算法適應度函數。

1）空間利用率函數

空間利用率為虛擬機體積占主機體積的比率，定義為

其中，BVi表示放入主機的第i個虛擬機的體積，CV表示主機的體積，n為主機中的虛擬機數量。第i個虛擬機的體積定義為

2）重量函數

虛擬機的重量以其負載VL表示，定義為

其中，VLi表示第i個虛擬機的重量，PL表示主機的最大承載重量，若虛擬機的總重量超過主機的最大載重，則函數的值為0。

3）負載變化函數

σ0表示實現主機負載均衡所允許的負載變化約束值，σ(S。T)表示主機在T時間段內實際的負載變化值，Φ(x)為懲罰函數，當個體滿足負載變化約束時，其值為1，否則為e。

根據懲罰函數和處理多目標優化的加權系數方法，本文定義適應度函數為

其中，A、B和C表示加權因子，0≤A。B。C≤1，且A+B+C=1。

3.3 選擇

選擇操作就是對每次迭代產生的個體進行整體評估，然后選擇適應度值較大的個體作為下一代種群的初始集合。為了避免僅挑選適應度較大的個體而使解陷入局部最優，我們采用輪盤賭法來選擇種群的個體，其基本原理是根據每個染色體適應度的比例來確定該個體的選擇概率。具體步驟如下：

步驟一：根據式（10）定義的適應度函數計算每個個體的適應度值和種群的適應度總和。

步驟二：計算個體的適應度值在總和中所占的比例，作為該個體的選擇概率 ps(ai)。

可以看出，這種選擇算法隨機性較強，適應度值越大的個體被選擇的概率越大，同時具有較小適應度值的個體也有被選擇的機會。

3.4 交叉

交叉操作通過選擇兩個父代個體的部分結構進行交換以生成新的個體，可以極大提升遺傳算法的全局搜索能力。但如隨機選擇交叉位，則會造成全局搜索效率的下降；如每次選擇評估值較高的基因進行交叉，則算法很容易陷入局部最優并出現早熟收斂現象。因此我們引入可調參數的概率函數，既保證了評估值較高的基因被選擇以進行交叉，同時制造了全局搜索的隨機性。我們首先計算染色體中的基因評估值并排序，再定義排在第1位的基因被選擇為交叉位的概率為 p(q)，服從 p(q) ～q-ε的分布函數，其中，ε≥0，且取值為2。可以看出，概率的隨機性保證了全局搜索的性能，同時評估值較高的基因具有較大的概率被選擇為交叉位。選擇基因進行交叉操作之后，去掉含有相同基因值的服務器編碼，同時采用FFD［6］方式回填因消除服務器而失去從屬關系的虛擬機。

3.5 變異

變異算子通過賦予個體以很小的概率產生轉變而形成新的個體，增加了種群的多樣性，使得遺傳算法在交叉算子決定的全局搜索能力的基礎上，還具有局部的隨機搜索能力，以防止出現非成熟收斂。為了保證算法的局部搜索能力，變異率不能過大，如果變異率過大，則算法就退化成隨機搜索，因此設置變異概率函數如下：

式中，f為要變異的個體適應度值，favg為當代種群的平均適應度值，fmax為種群中最大的適應度值。當 f≥favg，表示個體適應度值較大時則應該讓pm較小，防止適應度值較大的個體被破壞；當f＜favg，表示個體適應度值較小時則應該讓 pm較大，以開辟新的搜索區域。在本文中設定k1=0.003，k2=0.0042。通過引入變異概率函數，根據種群適應度值的情況調整變異概率，不僅加快了算法的收斂速度，同時防止出現非成熟收斂而陷入早熟情況。

3.6 終止條件

算法的終止是防止出現迭代次數過多的情況，本文基于最優跨度的適應度函數值標準差來決定算法的終止，如式（12）所示：

其中，f(i)表示第i個個體的適應度值，favg為當代種群的平均適應度值，N為種群的個體數量，ζ為收斂的閾值，在這里取ζ=0.1，當算法的標準差小于這個閾值時終止迭代，否則繼續進行迭代進化。

4 仿真實驗

為了驗證負載均衡調度算法LBGA與傳統算法相比在效率上的提高，本文采用CloudSim工具進行仿真，通過與該領域的服務器聚合算法FFD以及多維資源調度算法DRF［7］進行比較。實驗運行的工作負載規模分為100、300、500、800及1000個虛擬機這五個實例，參數設置參考 Feitelson［8］和Mishra［9］等方法，我們把每個實例中的算法均運行30次，取其平均值作為性能分析的依據。

物理服務器的使用數量是衡量服務器資源均衡調度性能的重要指標［10］。LBGA算法、DRF算法和FFD算法在物理服務器使用數量方面的比較如圖3所示。通過分析可以看到，由于LBGA算法綜合考慮了資源負載的均衡，因此對于實驗運行的各個工作實例都只需要啟動最少的物理服務器，LB?GA算法相比FFD算法、DRF算法分別節省11.2%和4%的服務器使用量。LBGA算法由于在調度中綜合考慮了虛擬機的多維資源需求及服務器的資源容量，通過虛擬機的合理部署使服務器的空余資源達到均衡，為后續虛擬機的資源使用提供了更多的可能性，相應地減少了服務器的使用數量。

圖3 服務器使用數量比較

圖4 系統資源綜合利用率比較

系統資源的綜合利用率也是衡量調度算法性能優劣的重要依據［11］。通過圖4中LBGA算法、DRF算法和FFD算法的比較可以看到，LBGA算法相比DRF算法和FFD算法在資源綜合利用率方面取得了6.5%～12.1%的提高，并且由于LBGA算法具有較小的標準差，算法在穩定性方面也具有一定優勢。由于LBGA算法在虛擬機部署過程中注重物理服務器資源之間的負載均衡，每次虛擬機部署時盡量滿足服務器多維資源之間的互補關系，防止出現因某種資源過早飽和而抑制其它資源使用的現象，因此從整體上提高了服務器資源的綜合利用率。

5 結語

本文針對傳統的遺傳算法在解決裝箱問題上效率的不足進行了改正，并將其應用于云環境中虛擬機的部署問題。該算法在分組遺傳算法的基礎上，從空間利用率、重量和負載變化三個方面來定義適應度函數，并通過加權方法定義適應度函數。同時，算法對選擇和變異操作進行了優化，實現了數據中心服務器資源的高效均衡分配。最后，通過與該領域的聚合調度算法FFD和多維資源調度算法DRF比較，證明了該調度算法的有效性和高效性。