羅 寧 李 璐 唐 忠

1(廣西經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院網(wǎng)絡(luò)與現(xiàn)代教育技術(shù)中心 廣西 南寧 530021)2(廣西醫(yī)科大學(xué)信息與管理學(xué)院 廣西 南寧 530021)

0 引 言

云計(jì)算是目前計(jì)算機(jī)領(lǐng)域內(nèi)技術(shù)發(fā)展的焦點(diǎn)之一，它是將傳統(tǒng)的分布式計(jì)算、并行計(jì)算、網(wǎng)格計(jì)算融為一體的數(shù)據(jù)服務(wù)系統(tǒng)[1]。由于云環(huán)境的動(dòng)態(tài)特性，虛擬機(jī)(Virtual Machine，VM)會(huì)出現(xiàn)負(fù)載不平衡的問題[2]。因此，任務(wù)調(diào)度器需要通過將總負(fù)載分配給云系統(tǒng)中的所有可用節(jié)點(diǎn)來平衡負(fù)載。平衡負(fù)載的主要目標(biāo)是最大限度地利用資源，提高服務(wù)質(zhì)量。在云環(huán)境中，計(jì)算資源服務(wù)質(zhì)量的好壞是衡量云計(jì)算效果的一個(gè)重要指標(biāo)，因此，如何有效地降低云計(jì)算中的負(fù)載均衡、提升計(jì)算資源利用率是當(dāng)前研究的熱點(diǎn)問題。

負(fù)載均衡的概念在2001年由Zomaya提出，是指將任務(wù)分?jǐn)偟蕉鄠€(gè)操作單元上執(zhí)行的過程[3]，其避免產(chǎn)生系統(tǒng)瓶頸或者資源浪費(fèi)。迄今為止，國(guó)內(nèi)外研究學(xué)者已經(jīng)開發(fā)出許多傳統(tǒng)算法、啟發(fā)式和元啟發(fā)式算法等用來解決任務(wù)負(fù)載優(yōu)化問題。經(jīng)典的Min-Min與Max-Min算法通過優(yōu)先安排計(jì)算量過小或過大的任務(wù)方式縮短總?cè)蝿?wù)完成時(shí)間，但是這類算法的負(fù)載均衡較差[4]。啟發(fā)式算法[5]包括蟻群算法、遺傳算法、粒子群算法和螢火蟲算法等算法以及相關(guān)的改進(jìn)融合算法。這類方法具備操作簡(jiǎn)單、魯棒性強(qiáng)和擴(kuò)充性好的特點(diǎn)，能夠有效地縮短任務(wù)完成時(shí)間，解決資源負(fù)載均衡的問題。Tseng等[6]提出了一種動(dòng)態(tài)預(yù)測(cè)云數(shù)據(jù)中心資源利用率和能耗的多目標(biāo)遺傳算法，用于云數(shù)據(jù)中心的動(dòng)態(tài)資源預(yù)測(cè)和任務(wù)分配。但是，在遇到用戶請(qǐng)求激增的突發(fā)情況時(shí)，負(fù)載平衡性能較差。Chou等[7]提出了基于粒子群優(yōu)化算法的動(dòng)態(tài)節(jié)能資源分配機(jī)制，利用最小二乘回歸方法對(duì)物理機(jī)資源利用率進(jìn)行預(yù)測(cè)，實(shí)現(xiàn)動(dòng)態(tài)節(jié)電資源分配，但是，該方法沒有考慮云環(huán)境中帶寬、內(nèi)存等其他資源的利用率。Zuo等[8]提出了一種基于蟻群優(yōu)化(mosaco)的面向任務(wù)的多目標(biāo)調(diào)度方法，根據(jù)時(shí)間期限和成本約束，對(duì)混合云計(jì)算環(huán)境中公共和私有計(jì)算資源的有限池進(jìn)行優(yōu)化。Vakilinia[9]提出了基于時(shí)間負(fù)載感知的資源調(diào)度算法，通過服務(wù)器功耗、網(wǎng)絡(luò)通信和遷移成本的聯(lián)合優(yōu)化，減少數(shù)據(jù)中心的資源使用成本，提高利用率。

針對(duì)現(xiàn)有多目標(biāo)調(diào)度方法所需處理時(shí)間較長(zhǎng)以及處理突發(fā)情況時(shí)性能降低的問題，提出一種基于模因優(yōu)化和循環(huán)調(diào)度的多目標(biāo)負(fù)載均衡技術(shù)。本文的主要?jiǎng)?chuàng)新之處在于在考慮云服務(wù)器多目標(biāo)調(diào)度問題時(shí)，將工作狀態(tài)區(qū)分為兩種模式：若工作狀態(tài)為突發(fā)，選擇加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法；若工作負(fù)載狀態(tài)為正常，則采用閾值多目標(biāo)模因優(yōu)化技術(shù)調(diào)度任務(wù)。這樣可以通過選擇不同的負(fù)載平衡算法來提高任務(wù)調(diào)度效率，實(shí)現(xiàn)以更高的效率和最短的時(shí)間來平衡云中虛擬機(jī)之間的工作負(fù)載的目標(biāo)。

1 模因算法

模因算法(Memetic Algorithm，MA)在1989年由Moscato提出[10]，靈感源于達(dá)爾文和拉馬克的基因遺傳理論。該算法是將遺傳算法和局部搜索策略相結(jié)合的智能算法，具有全局優(yōu)化能力和局部?jī)?yōu)化能力。由于MA存在局部搜索機(jī)制，即使初始種群的個(gè)體與最優(yōu)解相差很大，也能在單次迭代過程中達(dá)到個(gè)體局部最優(yōu)，可行解在剔除適應(yīng)度很差個(gè)體的同時(shí)，向最優(yōu)解不斷逼近，從而顯示其較強(qiáng)的尋優(yōu)效率及極高的容錯(cuò)能力。

模因算法可以應(yīng)用于單目標(biāo)優(yōu)化問題，也能夠在多目標(biāo)優(yōu)化問題中取得很好的效果。圖1給出了模因算法在單目標(biāo)、多目標(biāo)優(yōu)化問題中的搜索過程。MA在最優(yōu)解搜索過程中，全局搜索用于在特征空間內(nèi)定位最優(yōu)解的潛在區(qū)域，局部搜索是在潛在區(qū)域內(nèi)進(jìn)行精確定位。

(a) 單目標(biāo)優(yōu)化問題 (b) 多目標(biāo)優(yōu)化問題圖1 模因算法在單/多目標(biāo)優(yōu)化問題的搜索過程

MA的大致流程如算法1所示。

算法1模因算法

Begin

t=0；

種群初始化：隨機(jī)選擇初始種群P(t)；

評(píng)價(jià)種群P(t)中的每個(gè)個(gè)體；

while(中止條件) do

在種群P(t)中的全部/部分個(gè)體進(jìn)行局部搜索；

評(píng)價(jià)種群P(t)中的每個(gè)個(gè)體；

復(fù)制種群P(t)得到臨時(shí)種群P′(t)；

對(duì)種群P′(t)使用重組、變異等隨機(jī)操作；

合并種群R(t)=P(t)∪P′(t)；

從R(t)中選擇個(gè)體產(chǎn)生下一代新種群P(t+1)；

t=t+1；

end while

end

目前，模因算法在單目標(biāo)優(yōu)化問題的搜索性能上表現(xiàn)優(yōu)良，在多目標(biāo)優(yōu)化問題(Multi-Objective Optimization Problems，MOOP)中的應(yīng)用還沒有被廣泛討論。MOOP需要在單目標(biāo)優(yōu)化問題的基礎(chǔ)上，解決局部搜索中最優(yōu)解的排序問題。一般而言，處理這個(gè)問題存在兩種方式：采用聚合函數(shù)或Pareto排序。由于基于聚合函數(shù)的方法在優(yōu)化效果方面明顯高于基于Pareto排序的方法，因此，大多數(shù)學(xué)者采用聚合函數(shù)求解MOOP問題。Chen等[11]給出了模因算法在局部搜索中采用不同聚合函數(shù)時(shí)多目標(biāo)優(yōu)化問題的解，該模型中的Pareto前沿具有良好收斂性和確定性，從而驗(yàn)證了模因算法在MOOP問題上也具備很強(qiáng)的適應(yīng)性。

2 算法設(shè)計(jì)

云數(shù)據(jù)中心由一系列連接到互聯(lián)網(wǎng)的服務(wù)器組成。因此，任務(wù)調(diào)度器需要安排調(diào)度云環(huán)境內(nèi)的任務(wù)執(zhí)行順序。一個(gè)優(yōu)越的調(diào)度器使用較少的資源(如能耗、帶寬、內(nèi)存和時(shí)間)來完成用戶任務(wù)。針對(duì)云資源管理的多目標(biāo)問題，本文采用改進(jìn)的模因算法和循環(huán)調(diào)度方法[12]，將用戶請(qǐng)求任務(wù)調(diào)度到資源最佳的虛擬機(jī)上，在最少的時(shí)間內(nèi)實(shí)現(xiàn)負(fù)載均衡。

圖2給出了本文算法在云環(huán)境中平衡負(fù)載以獲得增強(qiáng)任務(wù)調(diào)度性能的整個(gè)過程。首先利用檢測(cè)器判斷用戶發(fā)送請(qǐng)求數(shù)量。如果在很短的時(shí)間內(nèi)接收到大量的請(qǐng)求，會(huì)導(dǎo)致突發(fā)，并影響負(fù)載平衡性能。本文選擇不同的負(fù)載平衡算法來提高任務(wù)調(diào)度效率，當(dāng)突發(fā)檢測(cè)器(Burst Detector，BD)發(fā)現(xiàn)工作負(fù)載狀態(tài)為突發(fā)時(shí)，選擇加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法，將用戶任務(wù)分配給云中資源最優(yōu)的虛擬機(jī)；如果該工作負(fù)載狀態(tài)為正常，則采用閾值多目標(biāo)模因優(yōu)化技術(shù)調(diào)度任務(wù)，從而實(shí)現(xiàn)以更高的效率和最短的時(shí)間來平衡云中虛擬機(jī)之間的工作負(fù)載的目標(biāo)。

圖2 本文算法的架構(gòu)示意圖

2.1 突發(fā)檢測(cè)器

突發(fā)檢測(cè)器用于識(shí)別云環(huán)境服務(wù)器的工作負(fù)載變化，然后通過預(yù)設(shè)閾值來確定工作負(fù)載的狀態(tài)。當(dāng)用戶請(qǐng)求到達(dá)云服務(wù)器時(shí)，BD將用戶請(qǐng)求的速率與閾值進(jìn)行比較。如果用戶請(qǐng)求數(shù)量在短時(shí)間內(nèi)激增，即任務(wù)到達(dá)時(shí)間t的速率大于閾值，則定義此時(shí)工作負(fù)載狀態(tài)為突發(fā)。否則，工作負(fù)荷狀態(tài)為正常。通過考慮突發(fā)檢測(cè)器的輸出結(jié)果，提出的技術(shù)選擇合適的負(fù)載平衡方法來調(diào)度用戶任務(wù)。

2.2 負(fù)載平衡算法

本文設(shè)計(jì)了兩種負(fù)載平衡算法，即閾值多目標(biāo)模因優(yōu)化算法和加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法，分別應(yīng)用于正常和突發(fā)工作負(fù)載條件下的用戶任務(wù)調(diào)度。

2.2.1閾值多目標(biāo)模因優(yōu)化算法

閾值多目標(biāo)模因優(yōu)化算法是結(jié)合遺傳算法和局部搜索策略的智能算法，根據(jù)適應(yīng)值與基于退火選擇、離散交叉和翻轉(zhuǎn)變異等進(jìn)化運(yùn)算原理來確定有效任務(wù)調(diào)度的最優(yōu)虛擬機(jī)。閾值多目標(biāo)模因優(yōu)化算法的流程如圖3所示。算法首先從云服務(wù)器中的虛擬機(jī)數(shù)量填充種群開始。其次計(jì)算每個(gè)群體的模因適應(yīng)值，以確定分配給用戶任務(wù)的最佳虛擬機(jī)。然后使用退火選擇從群體中挑取好的解決方案，接著將離散交叉應(yīng)用于通過組合選定的解決方案來創(chuàng)建新的解決方案。交叉后，通過隨機(jī)改變解的方式對(duì)解進(jìn)行翻轉(zhuǎn)突變。最后，采用局部搜索算法，獲得當(dāng)前迭代中最佳的云負(fù)載平衡解決方案。通過設(shè)定迭代閾值后，輸出多次迭代的結(jié)果，并作為全局最優(yōu)解。

圖3 閾值多目標(biāo)模因優(yōu)化算法流程

云環(huán)境下的用戶i(i=1,2,…，n)發(fā)送請(qǐng)求到云服務(wù)器(Cloud Server，CS)，CS根據(jù)用戶請(qǐng)求到達(dá)的時(shí)間和數(shù)據(jù)中心中虛擬機(jī)利用率的詳細(xì)信息來向資源利用率較低的終端用戶提供不同的服務(wù)?？紤]一個(gè)數(shù)據(jù)中心，具有n個(gè)虛擬機(jī)VM，通過計(jì)算能耗、任務(wù)完成時(shí)間、帶寬和內(nèi)存消耗等多個(gè)目標(biāo)來衡量虛擬機(jī)VMi的資源利用率。能耗指虛擬機(jī)在云環(huán)境中為用戶提供所需服務(wù)使用的能量，VM的能耗為：

EVM=pow(UR)×t

(1)

式中：EVM表示VM的能量消耗;pow(UR)表示為云用戶提供所需服務(wù)使用的能量；t表示服務(wù)時(shí)間。

虛擬機(jī)任務(wù)完成時(shí)間為：

TVM=ts-te

(2)

式中：ts和te分別表示處理任務(wù)的開始和結(jié)束時(shí)間。

VM的帶寬消耗通過可用帶寬ba和未使用帶寬bu之間的差異計(jì)算：

BVM=ba-bu

(3)

虛擬機(jī)處理用戶任務(wù)所需的存儲(chǔ)空間量可被定義為：

MVM=Ts-us

(4)

式中：MVM表示虛擬機(jī)的內(nèi)存利用率；Ts和us分別表示總空間和未使用空間。

在閾值多目標(biāo)模因優(yōu)化算法中，首先利用VMi(i=1,2,…,n)初始化種群，根據(jù)下面的多目標(biāo)問題計(jì)算所有VM的模因適應(yīng)值FVM：

FVM={EVM,TVM,BVM,MVM}

(5)

利用退火選擇(Annealed Selection，AS)挑取具有模因適合度高的種群(即VM)用于下一代，進(jìn)而找到用于云中任務(wù)調(diào)度和負(fù)載平衡的最佳VM。當(dāng)種群生成出現(xiàn)變化時(shí)，每個(gè)種群的模因適合度值和選擇概率也會(huì)發(fā)生變化。種群選擇的概率在數(shù)學(xué)上被估計(jì)為：

(6)

式中：Fi表示種群的平均適合度；N表示種群數(shù)量。

離散交叉(Discrete Crossover，DC)是使用隨機(jī)實(shí)數(shù)來生成一個(gè)后代，隨機(jī)實(shí)數(shù)決定從哪個(gè)父母那里取出后代的模因。離散交叉過程如圖4所示，DC選擇P和Q作為父母，R是P和Q生成的后代，其模因可從父母中選擇。

圖4 離散交叉過程

翻轉(zhuǎn)突變(Flip Mutation，F(xiàn)M)如圖5所示，通過修改染色體中的0和1達(dá)到翻轉(zhuǎn)突變的目的。對(duì)于突變?nèi)旧w中的1，父染色體中的后續(xù)位被翻轉(zhuǎn)來構(gòu)建子染色體。

圖5 翻轉(zhuǎn)突變過程

在完成突變過程后，應(yīng)用局部搜索，選擇具有較高適合度值的VM作為執(zhí)行用戶任務(wù)的最佳虛擬機(jī)。局部搜索(Local Search，LS)在數(shù)學(xué)上定義為：

(7)

式中：FVM和FT分別表示VM和閾值的模因適度值。

通過使用式(7)，閾值多目標(biāo)模因優(yōu)化算法利用模因適度值的局部尋優(yōu)，在多個(gè)VM之中找到最佳VM用于調(diào)度任務(wù)。閾值多目標(biāo)模因優(yōu)化算法適用于非突發(fā)條件下的云中VM工作負(fù)載平衡問題。

2.2.2加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法

加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法旨在優(yōu)化突發(fā)工作負(fù)載情況下的具有不同處理能力的VM。該算法首先通過計(jì)算當(dāng)前VM的能耗、帶寬、內(nèi)存、任務(wù)完成時(shí)間，以及負(fù)載情況來確定模因適合度，然后根據(jù)適合度為每個(gè)VM分配權(quán)重，最后該算法根據(jù)權(quán)重系數(shù)安排完成用戶任務(wù)VM的順序及響應(yīng)次數(shù)。例如，如果VM1和VM2的權(quán)重是3、5，則該算法采用循環(huán)調(diào)度的方式將3個(gè)用戶請(qǐng)求轉(zhuǎn)發(fā)到VM1上處理，將5個(gè)用戶請(qǐng)求轉(zhuǎn)發(fā)到VM2上。

在加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法中，同樣利用VMi(i=1,2,…，n)初始化種群，根據(jù)多目標(biāo)問題計(jì)算所有VM的模因適應(yīng)值FVM：

(8)

式中：LVM表示VM的當(dāng)前負(fù)載。

(9)

式中：T表示VM的總?cè)萘浚籒t表示在當(dāng)前VM上運(yùn)行的用戶任務(wù)的數(shù)量。

VM的權(quán)重系數(shù)為：

(10)

通過使用式(10)來確定每個(gè)VM的權(quán)重值。然后加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法通過執(zhí)行AS、DC、FM和LC在多個(gè)虛擬機(jī)中選取較高權(quán)重的VM，以便處理用戶請(qǐng)求的任務(wù)。當(dāng)云計(jì)算中遇到突發(fā)性工作負(fù)載情況時(shí)，通過引入權(quán)重值，加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法在每輪中將用戶請(qǐng)求任務(wù)分配給已識(shí)別的最佳VM，以最小的資源利用率在云中平衡突發(fā)性工作負(fù)載。

2.3 帕累托前沿

多目標(biāo)優(yōu)化問題的解決方案在數(shù)學(xué)上以非支配點(diǎn)表示，即只有當(dāng)解決方案在所有標(biāo)準(zhǔn)中具有優(yōu)越性能時(shí)，解決方案才占優(yōu)勢(shì)。如果解決方案不能被搜索空間中可用的任何其他解決方案所支配，則稱該解決方案是帕累托最優(yōu)。所有帕累托最優(yōu)解的集合被稱為帕累托集，其在客觀空間中的圖像稱為帕累托前沿[13]。

云中的工作流調(diào)度可以被視為多目標(biāo)優(yōu)化問題，其目標(biāo)是找到一組良好的權(quán)衡解決方案，使用戶能夠在目標(biāo)之間選擇所需的權(quán)衡。本文算法目的是從初始群體中找出帕累托最優(yōu)集合以調(diào)度用戶請(qǐng)求的任務(wù)，即開始于一群隨機(jī)生成的候選解決方案，并在更多的生成或迭代次數(shù)上向更好的解決方案集(帕累托最優(yōu)解決方案)發(fā)展。圖6給出了本文算法的帕累托前沿。其中：X軸表示種群初始化值(即不同數(shù)量的用戶請(qǐng)求任務(wù))；Y軸表示用于平衡云中工作負(fù)荷的帕累托最優(yōu)集(即為調(diào)度任務(wù)正確選擇的最佳VM的數(shù)量)。

圖6 本文算法的帕累托前沿

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

為了評(píng)價(jià)本文算法的性能，使用Amazon EC2數(shù)據(jù)集通過CloudSim仿真器以Java語(yǔ)言進(jìn)行測(cè)試實(shí)驗(yàn)，它是一項(xiàng)基于Web的服務(wù)，允許用戶在Amazon Web Services(AWS)公共云中運(yùn)行應(yīng)用程序。為了對(duì)比性能，本文算法在相同條件下與多目標(biāo)遺傳算法(MGA)[6]和動(dòng)態(tài)節(jié)能資源分配(DPRA)[7]等現(xiàn)有的負(fù)載平衡方法的測(cè)試結(jié)果進(jìn)行比較。

Amazon EC2數(shù)據(jù)集[14]為發(fā)送請(qǐng)求的用戶提供必需的服務(wù)。Amazon EC2數(shù)據(jù)集包含以下屬性：名稱、API名稱、內(nèi)存、計(jì)算單位、核心、存儲(chǔ)、Arch、網(wǎng)絡(luò)性能、最大帶寬、最大IP、Linux成本和Windows成本。Amazon EC2數(shù)據(jù)集允許開發(fā)人員使用虛擬機(jī)VM，VM為與全球AWS數(shù)據(jù)中心一起運(yùn)行的IT項(xiàng)目和云工作負(fù)載提供計(jì)算能力。測(cè)試數(shù)據(jù)考慮在25～250范圍內(nèi)的不同數(shù)量的用戶請(qǐng)求任務(wù)來執(zhí)行實(shí)驗(yàn)評(píng)估。本文仿真實(shí)驗(yàn)的運(yùn)行環(huán)境為Windows10系統(tǒng)下Intel(R) Core(TM) i7-7700HQ處理器。

采用調(diào)度效率，調(diào)度時(shí)間和能耗三個(gè)性能評(píng)價(jià)指標(biāo)來評(píng)估本文方法的性能。調(diào)度效率是計(jì)算正確調(diào)度到最佳VM的用戶請(qǐng)求任務(wù)數(shù)與用戶請(qǐng)求總數(shù)的比率：

(11)

式中：N表示用戶請(qǐng)求總數(shù)量；NURs表示正確調(diào)度到最佳VM的用戶請(qǐng)求的任務(wù)數(shù)。

調(diào)度時(shí)間是指將用戶請(qǐng)求任務(wù)調(diào)度到最佳VM所需的時(shí)間：

ST=N×t(SSUR)

(12)

式中：t(SSUR)表示調(diào)度單個(gè)用戶請(qǐng)求所用的時(shí)間。

能量消耗是估計(jì)虛擬機(jī)執(zhí)行用戶請(qǐng)求任務(wù)時(shí)所需要的能量：

EC=N×E(SSP)

(13)

式中：E(SSP)指執(zhí)行單個(gè)用戶請(qǐng)求任務(wù)所需的能量。

圖7-圖9給出了三種方法用于平衡云服務(wù)器中的工作負(fù)載時(shí)的調(diào)度效率、調(diào)度時(shí)間和能耗對(duì)比?？梢钥闯觯帽疚募夹g(shù)處理云中的突發(fā)和非突發(fā)工作負(fù)載時(shí)的調(diào)度效率都非常高，調(diào)度時(shí)間和能耗則是隨著用戶請(qǐng)求數(shù)量的增加而遞增。此外，本文算法在調(diào)度效率、調(diào)度時(shí)間和能耗方面的性能明顯優(yōu)于其他算法。

圖7 不同用戶請(qǐng)求時(shí)的調(diào)度效率對(duì)比

圖8 不同用戶請(qǐng)求時(shí)的調(diào)度時(shí)間對(duì)比

圖9 不同用戶請(qǐng)求時(shí)的能耗對(duì)比

4 結(jié) 語(yǔ)

為了在正常和突發(fā)工作負(fù)載條件下提高云中用戶任務(wù)的調(diào)度效率，本文提出一種基于模因優(yōu)化和循環(huán)調(diào)度的多目標(biāo)負(fù)載均衡算法。通過設(shè)計(jì)閾值多目標(biāo)模因優(yōu)化算法和加權(quán)多目標(biāo)模因優(yōu)化循環(huán)調(diào)度算法來應(yīng)對(duì)云計(jì)算中正常負(fù)載和突發(fā)負(fù)載時(shí)的用戶請(qǐng)求任務(wù)的調(diào)度工作。實(shí)驗(yàn)結(jié)果表明，與其他算法相比，本文方法在調(diào)度效率、調(diào)度時(shí)間和能耗方面具有明顯的優(yōu)勢(shì)。