舒曉苓，吳雪琴

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

1 引言

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

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

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

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

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

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

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

Rvk≤Ck，?k∈K

(1)

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

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

(2)

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

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

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

(3)

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

(4)

(5)

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

(6)

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

(7)

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

(8)

(9)

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

(10)

約束條件為：

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

(11)

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

設(shè)定二：當(dāng)行向量Nat=(N(at，v))1×v，at=1，2，…，At表示時間點(diǎn)t的可行虛擬機(jī)配置時，N(at，v)被認(rèn)為是時間點(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)化問題變換成一個判斷問題，也就是選取at∈{1，…At}，t=0，…，∞最佳數(shù)值，使平均任務(wù)在最短時間內(nèi)完成。

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

(13)

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

(14)

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

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

(15)

約束條件：

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

(16)

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

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

2.4.1 染色體的編碼與解碼

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

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

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

(17)

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

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

2.4.3 遺傳操縱

1)個體選取

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

(19)

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

(20)

2)交叉操作

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

在父代個體p1根據(jù)順序編碼找出tp2中每個基因數(shù)值，同時向前移動，使得找出基因順序與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)變異操作

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

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

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

(21)

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

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

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

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

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

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

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

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

3.3 任務(wù)等待時長對比

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

圖2 等待時長對比情況

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

3.4 收斂性對比

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

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

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

4 結(jié)論

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