云計(jì)算網(wǎng)絡(luò)下虛擬機(jī)負(fù)載均衡方法仿真

舒曉苓，吳雪琴

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

1 引言

隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)以及虛擬現(xiàn)實(shí)等技術(shù)的興起，云計(jì)算需求量劇增[1]。同時(shí)，云客戶(hù)對(duì)云服務(wù)質(zhì)量的要求越來(lái)越嚴(yán)格，特別是線上交易與海量數(shù)據(jù)交互對(duì)服務(wù)質(zhì)量要求較高。為了提升客戶(hù)體驗(yàn)效果，虛擬機(jī)資源調(diào)度方式備受人們關(guān)注。資源調(diào)度[2]是指在云環(huán)境的基礎(chǔ)上，分析若干個(gè)客戶(hù)的多資源需求與云系統(tǒng)的可利用資源，使資源能夠及時(shí)傳輸?shù)娇蛻?hù)匹配虛擬機(jī)上，并確定虛擬機(jī)資源協(xié)調(diào)的順序。云環(huán)境下虛擬機(jī)資源協(xié)調(diào)問(wèn)題是多資源、多種類(lèi)型的極難問(wèn)題，在研究過(guò)程中會(huì)面臨諸多的挑戰(zhàn)[3]。其中，最主要挑戰(zhàn)就是負(fù)載，因?yàn)樵骗h(huán)境中不同資源性能均不同，實(shí)時(shí)負(fù)載存在較大差異，資源協(xié)調(diào)極難做到公平、有效。

為此，諸多研究人員對(duì)云虛擬機(jī)負(fù)載均衡進(jìn)行積極研究。有學(xué)者將改進(jìn)粒子群算法應(yīng)用在云計(jì)算的任務(wù)調(diào)度中，采用粒子群與雞群融合算法，將粒子的分布根據(jù)雞群種類(lèi)進(jìn)行區(qū)分，并改進(jìn)粒子的學(xué)習(xí)因子，有效協(xié)調(diào)虛擬機(jī)的負(fù)載，但該過(guò)程使用算法較為復(fù)雜，增加負(fù)載協(xié)調(diào)的時(shí)間；除此之外，羅斯寧等人[4]面對(duì)虛擬機(jī)負(fù)載協(xié)調(diào)使用時(shí)間較長(zhǎng)的問(wèn)題，根據(jù)目標(biāo)函數(shù)構(gòu)建任務(wù)匹配模型，并利用改進(jìn)蟻群算法協(xié)調(diào)任務(wù)匹配時(shí)負(fù)載的問(wèn)題，該方法為了縮短負(fù)載協(xié)調(diào)時(shí)間，簡(jiǎn)化計(jì)算流程，但是負(fù)載均衡效果和收斂性不佳。

為了解決虛擬機(jī)負(fù)載協(xié)調(diào)效率低、負(fù)載均衡效果和收斂性不佳的問(wèn)題，本文采用邏輯分區(qū)方式將硬件資源進(jìn)行分區(qū)劃分，可以增強(qiáng)資源的利用效率與靈活性能，并使用遺傳算法完成各分區(qū)虛擬機(jī)資源負(fù)載均衡優(yōu)化，該流程能夠自適應(yīng)調(diào)節(jié)虛擬機(jī)負(fù)載，縮短虛擬機(jī)協(xié)調(diào)延遲時(shí)長(zhǎng)，滿足客戶(hù)的實(shí)時(shí)使用需求。

2 云虛擬機(jī)負(fù)載均衡優(yōu)化算法

2.1 邏輯分區(qū)下云虛擬機(jī)負(fù)載分析

云是由K個(gè)計(jì)算設(shè)備資源構(gòu)成[5]，含有CPU、內(nèi)存以及存儲(chǔ)器材等。這些器材資源都是通過(guò)虛擬機(jī)向客戶(hù)傳輸?shù)?，云系統(tǒng)能夠?qū)崟r(shí)支持若干個(gè)虛擬機(jī)同時(shí)調(diào)度。

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

Rvk≤Ck，?k∈K

(1)

根據(jù)公式(1)可將虛擬機(jī)配置設(shè)定如下：

設(shè)定一：假設(shè)1個(gè)系統(tǒng)能夠同時(shí)調(diào)度N1個(gè)種類(lèi)-1的虛擬機(jī)實(shí)例、N2個(gè)類(lèi)型-2的虛擬機(jī)實(shí)例，Nv個(gè)類(lèi)型-v的虛擬機(jī)實(shí)例，則V分區(qū)元素向量[7]N=(N1，N2，…，Nv)是云系統(tǒng)的1個(gè)可行的虛擬機(jī)配置，整個(gè)流程如公式(2)所示。

(2)

2.2 業(yè)務(wù)形式

需要考慮以下業(yè)務(wù)形式：虛擬機(jī)的發(fā)出請(qǐng)求隨機(jī)地送達(dá)系統(tǒng)，不同分區(qū)的虛擬機(jī)請(qǐng)求送達(dá)速率均不同且互相獨(dú)立；對(duì)各分區(qū)虛擬機(jī)送出請(qǐng)求的數(shù)量不同且服務(wù)相互獨(dú)立，并具有相同分布形式(i.i.d分布)，任意一個(gè)請(qǐng)求的虛擬機(jī)運(yùn)行時(shí)間也需要服從i.i.d分布形式。

若來(lái)源于終端客戶(hù)的請(qǐng)求，需要明確所請(qǐng)求是哪個(gè)分區(qū)的虛擬機(jī)與運(yùn)營(yíng)時(shí)間t(以時(shí)隙為單位)。一個(gè)虛擬機(jī)任務(wù)被稱(chēng)為第v′種類(lèi)任務(wù)，則此任務(wù)就需要請(qǐng)求第v種類(lèi)的虛擬機(jī)。任務(wù)長(zhǎng)度為S，則代表此虛擬機(jī)請(qǐng)求運(yùn)營(yíng)S時(shí)隙。為了降低計(jì)算難度，只需考慮未占用時(shí)隙系統(tǒng)，是指任意任務(wù)被調(diào)度開(kāi)始到調(diào)度結(jié)果使用時(shí)長(zhǎng)為一個(gè)時(shí)隙的系統(tǒng)。從各時(shí)隙起始階段，虛擬機(jī)調(diào)度設(shè)備經(jīng)過(guò)調(diào)度方案確定此時(shí)隙，并調(diào)度符合要求分區(qū)的虛擬機(jī)與各分區(qū)虛擬機(jī)調(diào)度幾個(gè)虛擬機(jī)設(shè)備共同執(zhí)行任務(wù)。

(3)

其中，E表示常數(shù)。

(4)

(5)

設(shè)定Qv(t)代表t時(shí)間點(diǎn)，系統(tǒng)等待的第v種類(lèi)虛擬請(qǐng)求的個(gè)數(shù)，即：

(6)

設(shè)定Wv(t)代表t時(shí)間點(diǎn)，系統(tǒng)等待的第v種類(lèi)虛擬機(jī)請(qǐng)求的工作量，即：

(7)

2.3 優(yōu)化目標(biāo)

(8)

(9)

則最小優(yōu)化為：

(10)

約束條件為：

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

(11)

為了縮短公式(10)-(11)優(yōu)化問(wèn)題的計(jì)算時(shí)間，則用虛擬機(jī)配置組數(shù)[9]NAt×v=(N(at，v))At×v來(lái)代表調(diào)度方案的集合，設(shè)定如下：

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

(12)

在加入虛擬機(jī)配置數(shù)值后，目標(biāo)優(yōu)化問(wèn)題變換成一個(gè)判斷問(wèn)題，也就是選取at∈{1，…At}，t=0，…，∞最佳數(shù)值，使平均任務(wù)在最短時(shí)間內(nèi)完成。

同時(shí)，通過(guò)公式(13)能夠獲得在t時(shí)隙調(diào)度結(jié)束的-v種類(lèi)虛擬機(jī)個(gè)數(shù)為：

(13)

在t時(shí)間的-v種類(lèi)虛擬機(jī)的平均任務(wù)結(jié)束所使用時(shí)長(zhǎng)為：

(14)

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

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

(15)

約束條件：

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

(16)

2.4 負(fù)載均衡優(yōu)化

通過(guò)對(duì)虛擬機(jī)負(fù)載分析得出任務(wù)形式與優(yōu)化目標(biāo)，并采用遺傳算法對(duì)虛擬機(jī)資源協(xié)調(diào)進(jìn)行優(yōu)化，達(dá)到虛擬機(jī)負(fù)載均衡優(yōu)化的目的。

2.4.1 染色體的編碼與解碼

利用整數(shù)編碼方法對(duì)染色體進(jìn)行編碼，設(shè)定n表示染色體長(zhǎng)度，1個(gè)基因表示1個(gè)任務(wù)，基因數(shù)值表示執(zhí)行此任務(wù)的虛擬機(jī)編號(hào)。

若m=6，n=20，則表示6個(gè)虛擬機(jī)，20個(gè)不同任務(wù)，生成以下長(zhǎng)度為20的染色體，即

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

(17)

對(duì)染色體進(jìn)行解碼，獲得6組虛擬機(jī)編碼的任務(wù)隊(duì)列，解碼過(guò)程如下：

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 初始種群的生成

種群規(guī)模的選擇對(duì)遺傳算法的收斂性具有較大影響，太大與太小均會(huì)影響算法的準(zhǔn)確性。為此，種群規(guī)模通常在20-150范圍內(nèi)。設(shè)定種群規(guī)模為SIZE，根據(jù)系統(tǒng)任意生成SIZE個(gè)染色體，基因數(shù)值為[1，m]區(qū)間內(nèi)任意數(shù)值。

2.4.3 遺傳操縱

1)個(gè)體選取

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

(19)

利用輪盤(pán)賭的篩選方法，得出個(gè)體i的累計(jì)概率，即：

(20)

2)交叉操作

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

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

3)變異操作

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

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

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

(21)

通過(guò)公式(21)完成自適應(yīng)協(xié)調(diào)的變異概率，并能根據(jù)客戶(hù)任務(wù)的需求動(dòng)態(tài)協(xié)調(diào)資源，使虛擬機(jī)負(fù)載均衡得到優(yōu)化。

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

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)根據(jù)現(xiàn)實(shí)設(shè)備的運(yùn)行負(fù)載記錄數(shù)據(jù)來(lái)檢測(cè)本文算法的優(yōu)劣。實(shí)驗(yàn)選用Intel(R)Pentium(R)處理設(shè)備，內(nèi)存16GB，操作系統(tǒng)為Windows 10，并將基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度方法和基于改進(jìn)蟻群算法的云計(jì)算用戶(hù)任務(wù)調(diào)度算法作為對(duì)比方法，分析三種方法得出的負(fù)載均衡效果、負(fù)載協(xié)調(diào)時(shí)長(zhǎng)與收斂性能。

3.2 負(fù)載均衡效果對(duì)比

實(shí)驗(yàn)選取800條任務(wù)記錄，在三種算法最佳的狀況下進(jìn)行對(duì)比，對(duì)比結(jié)果如圖1所示。

圖1 負(fù)載均衡效果對(duì)比

從圖1可知，隨著任務(wù)數(shù)量的增多，三種方法的負(fù)載均衡均呈上升趨勢(shì)，而本文算法上升坡度均高于傳統(tǒng)方法，因?yàn)楸疚乃惴ㄊ褂眠壿嫹謪^(qū)方式將硬件資源進(jìn)行合理劃分，并且各分區(qū)虛擬機(jī)能夠同時(shí)調(diào)度多個(gè)虛擬機(jī)設(shè)備共同執(zhí)行任務(wù)，增強(qiáng)虛擬機(jī)負(fù)載均衡能力，為此，本文算法優(yōu)于傳統(tǒng)方法。

3.3 任務(wù)等待時(shí)長(zhǎng)對(duì)比

相同任務(wù)不同算法的虛擬機(jī)資源負(fù)載協(xié)調(diào)時(shí)長(zhǎng)也是不同的。下面從負(fù)載協(xié)調(diào)時(shí)長(zhǎng)進(jìn)一步證實(shí)本文算法的虛擬機(jī)負(fù)載均衡性能。圖2為等待時(shí)長(zhǎng)對(duì)比結(jié)果。

圖2 等待時(shí)長(zhǎng)對(duì)比情況

從圖2中看出，隨著任務(wù)數(shù)量增多，任務(wù)協(xié)調(diào)時(shí)間逐漸增加，基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度方法的任務(wù)協(xié)調(diào)耗時(shí)最長(zhǎng)，該方法不能根據(jù)虛擬機(jī)配置數(shù)值將虛擬機(jī)資源調(diào)度問(wèn)題轉(zhuǎn)換成單維的虛擬機(jī)調(diào)度決策問(wèn)題，增加任務(wù)協(xié)調(diào)時(shí)間；而本文算法的等待時(shí)長(zhǎng)最短，整體上看本文算法優(yōu)于傳統(tǒng)方法。

3.4 收斂性對(duì)比

為了證實(shí)本文算法的收斂性能，實(shí)驗(yàn)選擇100次迭代次數(shù)，并將本文算法與傳統(tǒng)方法進(jìn)行對(duì)比，對(duì)比結(jié)果如圖3所示。

圖3 收斂性對(duì)比結(jié)果

從圖3可以看出，基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度方法隨著任務(wù)數(shù)量的增多，迭代次數(shù)基本不變，表明該方法不能在實(shí)驗(yàn)設(shè)置最大迭代次數(shù)內(nèi)收斂，其收斂性較差；基于改進(jìn)蟻群算法的云計(jì)算用戶(hù)任務(wù)調(diào)度算法迭代次數(shù)高于本文算法迭代次數(shù)，這是因?yàn)楸疚乃惴ㄊ褂米赃m應(yīng)變異方法，能夠提升空間查找能力，進(jìn)而提升算法的收斂性能，因此，本文算法收斂性較好。

4 結(jié)論

傳統(tǒng)虛擬機(jī)負(fù)載均衡任務(wù)調(diào)度是直接將任務(wù)調(diào)度在主機(jī)資源上，這種方式滿足不了客戶(hù)任務(wù)對(duì)云資源的動(dòng)態(tài)需求。為此本文提出基于邏輯分區(qū)的云虛擬機(jī)負(fù)載均衡優(yōu)化算法。此算法在響應(yīng)時(shí)長(zhǎng)與負(fù)載均衡效果、收斂性均取得一定成果，但由于對(duì)課題研究時(shí)間有限，今后可以在成本、吞吐量、穩(wěn)定性等方面深入研究。