云計算網絡下虛擬機負載均衡方法仿真

舒曉苓，吳雪琴

(電子科技大學成都學院，四川 成都 611731)

1 引言

隨著互聯網、物聯網以及虛擬現實等技術的興起，云計算需求量劇增[1]。同時，云客戶對云服務質量的要求越來越嚴格，特別是線上交易與海量數據交互對服務質量要求較高。為了提升客戶體驗效果，虛擬機資源調度方式備受人們關注。資源調度[2]是指在云環境的基礎上，分析若干個客戶的多資源需求與云系統的可利用資源，使資源能夠及時傳輸到客戶匹配虛擬機上，并確定虛擬機資源協調的順序。云環境下虛擬機資源協調問題是多資源、多種類型的極難問題，在研究過程中會面臨諸多的挑戰[3]。其中，最主要挑戰就是負載，因為云環境中不同資源性能均不同，實時負載存在較大差異，資源協調極難做到公平、有效。

為此，諸多研究人員對云虛擬機負載均衡進行積極研究。有學者將改進粒子群算法應用在云計算的任務調度中，采用粒子群與雞群融合算法，將粒子的分布根據雞群種類進行區分，并改進粒子的學習因子，有效協調虛擬機的負載，但該過程使用算法較為復雜，增加負載協調的時間；除此之外，羅斯寧等人[4]面對虛擬機負載協調使用時間較長的問題，根據目標函數構建任務匹配模型，并利用改進蟻群算法協調任務匹配時負載的問題，該方法為了縮短負載協調時間，簡化計算流程，但是負載均衡效果和收斂性不佳。

為了解決虛擬機負載協調效率低、負載均衡效果和收斂性不佳的問題，本文采用邏輯分區方式將硬件資源進行分區劃分，可以增強資源的利用效率與靈活性能，并使用遺傳算法完成各分區虛擬機資源負載均衡優化，該流程能夠自適應調節虛擬機負載，縮短虛擬機協調延遲時長，滿足客戶的實時使用需求。

2 云虛擬機負載均衡優化算法

2.1 邏輯分區下云虛擬機負載分析

云是由K個計算設備資源構成[5]，含有CPU、內存以及存儲器材等。這些器材資源都是通過虛擬機向客戶傳輸的，云系統能夠實時支持若干個虛擬機同時調度。

由于邏輯分區可以將物理服務設備的硬件資源進行分割，得出兩個或者兩個以上單個服務器，也就是分區。各個分區上均有各自單獨使用的處理設備、內存以及硬盤等[6]，同時任意一個分區運行不會干擾其他分區運行，進而增加資源的使用效率與靈活性。為此，采用邏輯分區方式將虛擬機分割成V個分區，各分區虛擬機均對應特定個數的資源，也就是運行客戶單位時間內能夠利用的最多資源。設定K=(1，2，…，k)代表資源種類；V={1，2，…，V}代表虛擬機分區的空間；Rvk代表第v種類虛擬機需要的第k種類資源的個數；Ck代表第k種類資源系統容量。而系統能夠支持v種類虛擬機的條件為：

Rvk≤Ck，?k∈K

(1)

根據公式(1)可將虛擬機配置設定如下：

設定一：假設1個系統能夠同時調度N1個種類-1的虛擬機實例、N2個類型-2的虛擬機實例，Nv個類型-v的虛擬機實例，則V分區元素向量[7]N=(N1，N2，…，Nv)是云系統的1個可行的虛擬機配置，整個流程如公式(2)所示。

(2)

2.2 業務形式

需要考慮以下業務形式：虛擬機的發出請求隨機地送達系統，不同分區的虛擬機請求送達速率均不同且互相獨立；對各分區虛擬機送出請求的數量不同且服務相互獨立，并具有相同分布形式(i.i.d分布)，任意一個請求的虛擬機運行時間也需要服從i.i.d分布形式。

若來源于終端客戶的請求，需要明確所請求是哪個分區的虛擬機與運營時間t(以時隙為單位)。一個虛擬機任務被稱為第v′種類任務，則此任務就需要請求第v種類的虛擬機。任務長度為S，則代表此虛擬機請求運營S時隙。為了降低計算難度，只需考慮未占用時隙系統，是指任意任務被調度開始到調度結果使用時長為一個時隙的系統。從各時隙起始階段，虛擬機調度設備經過調度方案確定此時隙，并調度符合要求分區的虛擬機與各分區虛擬機調度幾個虛擬機設備共同執行任務。

(3)

其中，E表示常數。

(4)

(5)

設定Qv(t)代表t時間點，系統等待的第v種類虛擬請求的個數，即：

(6)

設定Wv(t)代表t時間點，系統等待的第v種類虛擬機請求的工作量，即：

(7)

2.3 優化目標

(8)

(9)

則最小優化為：

(10)

約束條件為：

Nv(t)≤Wv(t)，?v∈V

(11)

為了縮短公式(10)-(11)優化問題的計算時間，則用虛擬機配置組數[9]NAt×v=(N(at，v))At×v來代表調度方案的集合，設定如下：

設定二：當行向量Nat=(N(at，v))1×v，at=1，2，…，At表示時間點t的可行虛擬機配置時，N(at，v)被認為是時間點t的虛擬機配置數組，且Nat=(N(at，v))1×v=(N(at，1)，N(at，2)，…，N(at，V))需要符合如下約束條件：

(12)

在加入虛擬機配置數值后，目標優化問題變換成一個判斷問題，也就是選取at∈{1，…At}，t=0，…，∞最佳數值，使平均任務在最短時間內完成。

同時，通過公式(13)能夠獲得在t時隙調度結束的-v種類虛擬機個數為：

(13)

在t時間的-v種類虛擬機的平均任務結束所使用時長為：

(14)

根據公式(14)可知，E[Tv(t)]為Nv(τ)(τ=0，…，t-1)的函數。

設定g({Nat})為序列Nat，t=0，…，∞的函數，代表全部分區的虛擬機完成平均任務所使用時間，則優化問題可以變換成最小化，即：

(15)

約束條件：

Nat?NAt×v，t=0，…，∞，at∈{1，A}

(16)

2.4 負載均衡優化

通過對虛擬機負載分析得出任務形式與優化目標，并采用遺傳算法對虛擬機資源協調進行優化，達到虛擬機負載均衡優化的目的。

2.4.1 染色體的編碼與解碼

利用整數編碼方法對染色體進行編碼，設定n表示染色體長度，1個基因表示1個任務，基因數值表示執行此任務的虛擬機編號。

若m=6，n=20，則表示6個虛擬機，20個不同任務，生成以下長度為20的染色體，即

p0=[2，3，1，4，1，6，1，2，5，3，1，4，2，6，1，6，5，3，5，5]

(17)

對染色體進行解碼，獲得6組虛擬機編碼的任務隊列，解碼過程如下：

v1：{3，5，7，11，15}；x1，3=x1，5=x1，7=x1，11=x1，15=1

v2：{1，8，13}；x2，1=x2，8=x2，13=1

v3：{2，10，18}；x3，2=x3，10=x3，18=1

v4：{4，12}；x4，4=x4，12=1

v5：{9，17，19，20}；x5，9=x5，17=x5，19=x5，20=1

v6：{6，14，16}；x6，6=x6，14=x6，16=1

(18)

2.4.2 初始種群的生成

種群規模的選擇對遺傳算法的收斂性具有較大影響，太大與太小均會影響算法的準確性。為此，種群規模通常在20-150范圍內。設定種群規模為SIZE，根據系統任意生成SIZE個染色體，基因數值為[1，m]區間內任意數值。

2.4.3 遺傳操縱

1)個體選取

個體選取是從種群中篩選適用度[10]最佳染色體進行復制，形成新的種群。其中，個體i被選中的幾率為：

(19)

利用輪盤賭的篩選方法，得出個體i的累計概率，即：

(20)

2)交叉操作

交叉操作生物領域有性繁殖的基因重建流程，與染色體的交叉重建等同，進而產生具備極佳優良基因的染色體，交叉幾率通常在0.4-0.99范圍內。使用順序交叉方式進行交叉操作，得出2個父代個體，即p1和p2。

在父代個體p1根據順序編碼找出tp2中每個基因數值，同時向前移動，使得找出基因順序與tp2等同，以此獲得新的個體，即np1=[1，1，6，2，2，3，5，5，3，4，5，4，3，1，5，6，6，5，3，3]。與此同時，將父代個體p2與交叉因子串tp1做相同的操作，獲得np2=[2，3，5，5，3，1，1，6，2，4，2，1，6，4，3，3，2，4，4，4]。

3)變異操作

變異操作是指編碼受到小概率干擾而發生變化，等同于基因突變。變異概率通常在0.0001-0.1范圍內。利用整數變異，也就是任意取點，并利用基因(排除已選取基因)的數值整數來代替此基因，此基因整數取值為[1，m]。例如，將父代個體p1做變異操作，假設任意投點到第8個基因上，則此點基因數值為1，在[1，6]區間內任意取除了1以外的數值；若任意取數值為2，則p1變異后獲得新個體為np1=[2，3，5，5，3，4，5，2，4，1，3，2，6，1，5，6，6，5，3，3]。

為確保算法的空間查找能力，并提升算法的收斂性能，將自適應變異方法引入，使個體增添1個變異概率屬性：pmk代表個體k的變異概率，若目前最佳個體的適應度是fbest，則個體k的適應度f(k)為：

pm′k=exp(-α×(|fbest-f(k)|/fbest))×pmk(α∈R+)

(21)

通過公式(21)完成自適應協調的變異概率，并能根據客戶任務的需求動態協調資源，使虛擬機負載均衡得到優化。

3 實驗結果分析

3.1 實驗環境

實驗根據現實設備的運行負載記錄數據來檢測本文算法的優劣。實驗選用Intel(R)Pentium(R)處理設備，內存16GB，操作系統為Windows 10，并將基于改進粒子群算法的云計算任務調度方法和基于改進蟻群算法的云計算用戶任務調度算法作為對比方法，分析三種方法得出的負載均衡效果、負載協調時長與收斂性能。

3.2 負載均衡效果對比

實驗選取800條任務記錄，在三種算法最佳的狀況下進行對比，對比結果如圖1所示。

圖1 負載均衡效果對比

從圖1可知，隨著任務數量的增多，三種方法的負載均衡均呈上升趨勢，而本文算法上升坡度均高于傳統方法，因為本文算法使用邏輯分區方式將硬件資源進行合理劃分，并且各分區虛擬機能夠同時調度多個虛擬機設備共同執行任務，增強虛擬機負載均衡能力，為此，本文算法優于傳統方法。

3.3 任務等待時長對比

相同任務不同算法的虛擬機資源負載協調時長也是不同的。下面從負載協調時長進一步證實本文算法的虛擬機負載均衡性能。圖2為等待時長對比結果。

圖2 等待時長對比情況

從圖2中看出，隨著任務數量增多，任務協調時間逐漸增加，基于改進粒子群算法的云計算任務調度方法的任務協調耗時最長，該方法不能根據虛擬機配置數值將虛擬機資源調度問題轉換成單維的虛擬機調度決策問題，增加任務協調時間；而本文算法的等待時長最短，整體上看本文算法優于傳統方法。

3.4 收斂性對比

為了證實本文算法的收斂性能，實驗選擇100次迭代次數，并將本文算法與傳統方法進行對比，對比結果如圖3所示。

圖3 收斂性對比結果

從圖3可以看出，基于改進粒子群算法的云計算任務調度方法隨著任務數量的增多，迭代次數基本不變，表明該方法不能在實驗設置最大迭代次數內收斂，其收斂性較差；基于改進蟻群算法的云計算用戶任務調度算法迭代次數高于本文算法迭代次數，這是因為本文算法使用自適應變異方法，能夠提升空間查找能力，進而提升算法的收斂性能，因此，本文算法收斂性較好。

4 結論

傳統虛擬機負載均衡任務調度是直接將任務調度在主機資源上，這種方式滿足不了客戶任務對云資源的動態需求。為此本文提出基于邏輯分區的云虛擬機負載均衡優化算法。此算法在響應時長與負載均衡效果、收斂性均取得一定成果，但由于對課題研究時間有限，今后可以在成本、吞吐量、穩定性等方面深入研究。