基于改進(jìn)多目標(biāo)布谷鳥(niǎo)搜索的資源調(diào)度算法

程 曦 宋鐵成

1(四川文理學(xué)院康養(yǎng)產(chǎn)業(yè)學(xué)院 四川 達(dá)州 635000)2(重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065)

0 引 言

云計(jì)算是一種通過(guò)網(wǎng)絡(luò)為用戶提供軟件、數(shù)據(jù)庫(kù)、計(jì)算、存儲(chǔ)和安全性服務(wù)的范例。資源管理是云計(jì)算中提出的核心問(wèn)題，包括資源分配、資源調(diào)度、資源發(fā)現(xiàn)、資源監(jiān)視、資源可用性和資源定價(jià)等方面[1-2]。資源調(diào)度是從適當(dāng)?shù)奈锢碣Y源中選擇最佳的虛擬化資源，即對(duì)要在其中生成虛擬機(jī)(VM)的物理資源進(jìn)行分類，以分配來(lái)自云設(shè)備的資源[3]。因此，在云計(jì)算環(huán)境中的基礎(chǔ)架構(gòu)即服務(wù)(IaaS)下，資源調(diào)度是一個(gè)多目標(biāo)問(wèn)題[4]。為此，需要一種優(yōu)化算法來(lái)解決多目標(biāo)問(wèn)題，實(shí)現(xiàn)資源合理調(diào)度。

多目標(biāo)優(yōu)化的任務(wù)是針對(duì)一組確定的限制同時(shí)優(yōu)化兩個(gè)或多個(gè)沖突目標(biāo)。但是，在云計(jì)算環(huán)境下，優(yōu)化過(guò)程容易出現(xiàn)改善一個(gè)目標(biāo)會(huì)導(dǎo)致另一個(gè)目標(biāo)降級(jí)的難題。近年來(lái)，研究人員采用元啟發(fā)式優(yōu)化算法來(lái)處理資源調(diào)度的多目標(biāo)問(wèn)題[5]。Gobalakrishnan等[6]提出了一種基于遺傳算法和灰狼優(yōu)化算法相結(jié)合的優(yōu)化技術(shù)，實(shí)現(xiàn)了云計(jì)算環(huán)境下負(fù)荷利用率、能耗、遷移成本和遷移時(shí)間組成的多目標(biāo)函數(shù)的優(yōu)化，實(shí)現(xiàn)了高效的任務(wù)調(diào)度，降低了時(shí)間和遷移成本，但是該算法存在求解精度低和后期收斂速度慢等問(wèn)題。Agarwal 等[7]提出一種基于布谷鳥(niǎo)搜索的任務(wù)調(diào)度方法，該方法在可用的虛擬機(jī)之間有效地分配任務(wù)，并保持總體響應(yīng)時(shí)間最小，使計(jì)算資源得到最佳的利用。Krishnadoss 等[8]提出了一種基于布谷鳥(niǎo)搜索算法和反向?qū)W習(xí)算法的多目標(biāo)任務(wù)調(diào)度策略，該策略采用完成時(shí)間和成本作為優(yōu)化問(wèn)題的重要約束條件來(lái)求解任務(wù)調(diào)度的NP完全問(wèn)題，實(shí)現(xiàn)了高性能、低成本的資源動(dòng)態(tài)分配的目標(biāo)。雖然布谷鳥(niǎo)搜索算法操作簡(jiǎn)單、通用性強(qiáng)，但是存在搜索速度慢、容易陷入局部最優(yōu)的缺點(diǎn)。Srichandan等[9]通過(guò)結(jié)合遺傳算法和細(xì)菌覓食算法兩種生物啟發(fā)式算法從經(jīng)濟(jì)和生態(tài)的角度方面降低了能源消耗。Abdullahi等[10]針對(duì)IaaS云計(jì)算環(huán)境下的多目標(biāo)大規(guī)模任務(wù)調(diào)度優(yōu)化問(wèn)題，提出了一種混沌共生生物搜索算法。采用混沌優(yōu)化策略生成初始種群，并用混沌序列代替基于隨機(jī)序列的SOS相分量，以保證生物多樣性，實(shí)現(xiàn)了全局收斂，但是收斂速度慢。

針對(duì)當(dāng)前用于解決IaaS云計(jì)算的資源調(diào)度多目標(biāo)優(yōu)化算法中存在的諸多問(wèn)題，提出一種基于改進(jìn)多目標(biāo)布谷鳥(niǎo)搜索的資源調(diào)度算法，通過(guò)改進(jìn)隨機(jī)游走策略和丟棄概率策略提高了算法的局部搜索能力和收斂速度，從而實(shí)現(xiàn)以最低的執(zhí)行時(shí)間和成本將任務(wù)分配特定的VM中，滿足云用戶對(duì)云提供商的資源利用需求，減少延遲，提高資源利用率和服務(wù)質(zhì)量。

1 云計(jì)算資源調(diào)度描述

云計(jì)算中的資源調(diào)度是一種多目標(biāo)優(yōu)化過(guò)程[11]，適用于處理器、網(wǎng)絡(luò)、存儲(chǔ)和VM等云資源的分發(fā)，根據(jù)云用戶的需求平均分配資源，實(shí)現(xiàn)云資源的最佳利用，確保云計(jì)算能夠以云提供商所提供的一定質(zhì)量的服務(wù)來(lái)滿足所有云用戶的請(qǐng)求。資源調(diào)度(Resource Scheduling，RS)問(wèn)題可以描述為：

(1)

假設(shè)存在一組任務(wù)Ti=(T1,T2,…,Tn)，云計(jì)算已將其映射到虛擬資源Vj=(V1,V2,…,Vm)上，而后被調(diào)度到物理設(shè)備中執(zhí)行。則任務(wù)與資源之間的對(duì)應(yīng)關(guān)系可以用矩陣表示為：

(2)

式中：xij∈{0,1}表示為第i個(gè)任務(wù)Ti與第j個(gè)資源Vj的對(duì)應(yīng)關(guān)系，當(dāng)xij=1時(shí)，表示任務(wù)Ti占據(jù)資源Vj，反之則沒(méi)有。根據(jù)任務(wù)與資源之間的對(duì)應(yīng)關(guān)系，任務(wù)Ti經(jīng)過(guò)資源傳遞到達(dá)物理設(shè)備上執(zhí)行的預(yù)期完成時(shí)間可以表示為：

(3)

同理，預(yù)期完成成本ECC可以定義為：

(4)

式中：Ci=(C1,C2,…,Cn)表示為任務(wù)成本。

根據(jù)預(yù)期完成時(shí)間ETC和預(yù)期完成成本ECC，云計(jì)算環(huán)境中資源節(jié)點(diǎn)完成子任務(wù)所花費(fèi)的時(shí)間和成本可以計(jì)算為：

(5)

(6)

式中：t(i,j)和res(i,j)分別表示任務(wù)Ti在資源Vj的所需時(shí)間和成本;sumTime(i,j)和sumCost(i,j)分別表示任務(wù)完成的總時(shí)間和總成本。

2 改進(jìn)多目標(biāo)布谷鳥(niǎo)搜索的調(diào)度策略

當(dāng)前大多數(shù)資源調(diào)度算法通過(guò)考慮不同的因素(如完成時(shí)間、執(zhí)行所有用戶任務(wù)的總成本、資源利用率、能耗和容錯(cuò)能力)進(jìn)行優(yōu)化，優(yōu)先約束并行應(yīng)用的求解時(shí)間與能耗之間的折中問(wèn)題是一個(gè)雙目標(biāo)優(yōu)化問(wèn)題。這個(gè)問(wèn)題的解決辦法是一組帕累托點(diǎn)。針對(duì)大多數(shù)情況下IaaS云資源調(diào)度不夠而產(chǎn)生的利用率低的問(wèn)題，本文提出一種基于改進(jìn)多目標(biāo)布谷鳥(niǎo)搜索的資源調(diào)度算法，以完成時(shí)間和成本為優(yōu)化目標(biāo)，用最小的ETC和ECC矩陣將任務(wù)分配到虛擬資源上，提高資源利用率。

2.1 多目標(biāo)布谷鳥(niǎo)搜索算法及改進(jìn)措施

布谷鳥(niǎo)搜索算法(Cuckoo Search Algorithm，CSA)[12]是在2010年由Yang等提出的一種生物啟發(fā)式智能優(yōu)化算法，該算法參考了自然界中布谷鳥(niǎo)的寄宿繁衍行為和果蠅的萊維飛行行為，結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)，具有很好的全局搜索能力。鑒于CSA局限于單目標(biāo)問(wèn)題的優(yōu)化，Yang等在2013年提出了多目標(biāo)布谷鳥(niǎo)搜索優(yōu)化(Multi-Objective Cuckoo Search Optimization，MOCSO)算法[13]，該算法可以直接求解Pareto最優(yōu)解集，應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域。

多目標(biāo)布谷鳥(niǎo)搜索算法的3個(gè)基本假設(shè)是在原來(lái)CSA假設(shè)的基礎(chǔ)上為滿足k個(gè)目標(biāo)的需求而做出一定的修改：

(1) 每只布谷鳥(niǎo)一次可產(chǎn)k個(gè)蛋，并隨機(jī)選擇一個(gè)寄生巢放置，第k個(gè)蛋即是一組解的第k個(gè)目標(biāo)。

(2) 在隨機(jī)選擇的一組寄生巢中，最好的巢將會(huì)保留到下一代繼續(xù)繁殖。

(3) 每個(gè)巢中的宿主鳥(niǎo)丟棄外來(lái)蛋的概率為Pa，被發(fā)現(xiàn)后布谷鳥(niǎo)選擇更換一個(gè)具有k個(gè)蛋的新巢。

布谷鳥(niǎo)蛋的寄生巢表示搜索空間的一個(gè)解，寄生巢位置表示解的適應(yīng)度值，布谷鳥(niǎo)搜索可以通過(guò)萊維飛行來(lái)更新t+1時(shí)刻的位置：

(7)

式中：i=1,2,…,n，Levy為萊維飛行搜索；α為步長(zhǎng)控制量，可以引入不同解之間的差來(lái)增加算法的收斂速度。α的計(jì)算如下：

(8)

式中：α0是個(gè)常數(shù)。

MOCSO中鳥(niǎo)巢位置的更新由解的相似性決定的：

(9)

圖1給出了多目標(biāo)布谷鳥(niǎo)搜索算法的流程。

圖1 多目標(biāo)布谷鳥(niǎo)搜索算法流程示意圖

在多目標(biāo)優(yōu)化過(guò)程中，其理想最優(yōu)解是可以完全支配其他解的解，但在優(yōu)化過(guò)程中往往獲得的是多個(gè)相互妥協(xié)的解，即Pareto解。雖然MOCSO考慮了新解和舊解之間的支配關(guān)系，但是由于該算法是基于單目標(biāo)算法之上的，在優(yōu)化過(guò)程中缺乏對(duì)個(gè)體之間相互支配關(guān)系的考慮。除此之外，MOCSO中的游走策略雖然能夠很好地保持算法的全局搜索能力和解的多樣性，但是由于縮放因子r是一個(gè)隨步長(zhǎng)而改變的隨機(jī)數(shù)，在搜索后期會(huì)因步長(zhǎng)的變小而變小，使得解的多樣性降低，陷入局部最優(yōu)。同時(shí)，發(fā)現(xiàn)概率Pa為一固定值，無(wú)論解的適合度值多高，均會(huì)存在Pa概率被丟棄，這種方式會(huì)忽略較好的解，影響最終優(yōu)化結(jié)果，也不適用于MOCSO。

針對(duì)上述兩點(diǎn)，本文從丟棄頻率和游走策略兩個(gè)方面做適當(dāng)改進(jìn)。首先重新定義丟棄概率：將優(yōu)化過(guò)程中產(chǎn)生的新解與舊解合并，按適應(yīng)度大小排序；修改丟棄概率Pa，將其設(shè)定為一個(gè)區(qū)間Pa∈[Pmin,Pmax]；最后將區(qū)間[Pmin,Pmax]劃分為等間距且長(zhǎng)度與解個(gè)數(shù)相同的子集，即形成一一對(duì)應(yīng)關(guān)系，最高適應(yīng)度的解對(duì)應(yīng)最低丟棄概率，反之對(duì)應(yīng)最高丟棄概率。而丟棄概率的最大值與最小值定義為：

Pmax=max(Pmax)·(1-t/max_iter)

(10)

Pmin=max(Pmin)·(1-t/max_iter)

(11)

式中：max_iter表示最大迭代次數(shù)。

其次，針對(duì)式(9)中存在的搜索后期解空間內(nèi)多樣性降低的問(wèn)題，提出下面的游走策略：

(12)

式中：rand是在均勻分布在[0,1]中的隨機(jī)數(shù)，該策略增加了解更新方向的隨機(jī)性，從而增強(qiáng)了解空間個(gè)體的多樣性。

2.2 多目標(biāo)資源調(diào)度問(wèn)題

本文將完成時(shí)間和成本作為IaaS云計(jì)算環(huán)境中優(yōu)化資源調(diào)度的多目標(biāo)函數(shù)，利用改進(jìn)的MOCSO對(duì)多目標(biāo)函數(shù)進(jìn)行優(yōu)化。云計(jì)算資源調(diào)度的目標(biāo)適應(yīng)度函數(shù)是花費(fèi)時(shí)間和成本的加權(quán)：

F= min(λ·sumTime+μ·sumCost)

(13)

式中：λ和μ表示加權(quán)系數(shù)。基于改進(jìn)的MOCSO的多目標(biāo)資源調(diào)度算法的偽代碼由算法1給出。

算法1基于改進(jìn)MOCSO算法的多目標(biāo)資源調(diào)度算法

輸入：丟棄概率Pa∈[Pmin,Pmax]，游走策略參數(shù)r，種群數(shù)量為n的初始化xi(i=1，2，…，n)，最大迭代Maxitr，目標(biāo)函數(shù)Fi(x)=f(xi)。

輸出：最優(yōu)解Sbest。

While((t

基于萊維飛行隨機(jī)生成一個(gè)解；

評(píng)估解的適合度Fi；

if (Fi是Pareto 最優(yōu))

從n個(gè)巢中隨機(jī)選擇一個(gè)j巢；

評(píng)估j巢的K個(gè)解；

if (Fi>Fj) then

將Fi替換Fj；

end if

end if

丟棄部分適合度低的巢，通過(guò)萊維飛行在新位置建造新巢；保留最好的巢，留給下一代；

對(duì)當(dāng)前解進(jìn)行排序并找到當(dāng)前最佳的Pareto最優(yōu)；

t←t+1；

end while

返回最優(yōu)解Sbest；

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

為了評(píng)價(jià)本文算法的性能，使用CloudSim3.0仿真軟件進(jìn)行測(cè)試實(shí)驗(yàn)，并在相同條件下與基于布谷鳥(niǎo)多目標(biāo)優(yōu)化(MOCSO)、基于簡(jiǎn)化群多目標(biāo)優(yōu)化(MOSSO)[14]、基于粒子群多目標(biāo)優(yōu)化(MOPSO)[15]和基于蟻群多目標(biāo)優(yōu)化算法(MOACO)[16]的任務(wù)調(diào)度方法相比。采用完成時(shí)間、成本和利用率三個(gè)性能評(píng)價(jià)指標(biāo)評(píng)估本文方法的性能。表1給出了仿真實(shí)驗(yàn)運(yùn)行環(huán)境的詳細(xì)信息。

表1 實(shí)驗(yàn)運(yùn)行環(huán)境的詳細(xì)信息

3.1 數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

本文采用HPC2N、NASA Ames iPCS / 860和SDSC三個(gè)工作負(fù)載檔案集[17]進(jìn)行測(cè)試，這些檔案集提供了CloudSim工具認(rèn)可的標(biāo)準(zhǔn)工作負(fù)載格式(.swf)。HPC2N數(shù)據(jù)集包括527 371個(gè)任務(wù)的統(tǒng)計(jì)數(shù)據(jù)，NASA包括14 794個(gè)任務(wù)的統(tǒng)計(jì)數(shù)據(jù)，SDSC包括73 496個(gè)任務(wù)的統(tǒng)計(jì)數(shù)據(jù)。在云計(jì)算環(huán)境中，這些數(shù)據(jù)集用于評(píng)估算法的性能。

為了對(duì)比本文算法與其他啟發(fā)式資源調(diào)度優(yōu)化算法的測(cè)試結(jié)果，采用完成時(shí)間、成本、資源利用率三個(gè)指標(biāo)來(lái)評(píng)進(jìn)行價(jià)。下面給出三個(gè)指標(biāo)的數(shù)學(xué)定義。

資源調(diào)度的完成時(shí)間是通過(guò)VM上所有任務(wù)映射的完成時(shí)間來(lái)確定執(zhí)行的最大完成時(shí)間：

(14)

式中：ti表示任務(wù)Ti的完成時(shí)間。

成本表示針對(duì)資源使用或利用率產(chǎn)生的總金額， VM的成本根據(jù)云提供商所確定的大量時(shí)間和VM的描述而有所不同。下面給出用于計(jì)算完成特定VM任務(wù)的成本：

(15)

式中：Ci表示單位時(shí)間內(nèi)資源i的使用成本；resourcei表示資源i。

利用率是指數(shù)據(jù)中心主映射有效利用的資源量：

(16)

3.2 結(jié)果分析

利用多目標(biāo)資源調(diào)度的完成時(shí)間、成本和資源利用率三個(gè)指標(biāo)評(píng)估提出的改進(jìn)MOCSO在IaaS云計(jì)算環(huán)境中的優(yōu)化性能。圖2給出了不同資源調(diào)度算法在HPC2N、NASA和SDCS三個(gè)工作負(fù)載數(shù)據(jù)集測(cè)試的完成時(shí)間。

圖2 不同資源調(diào)度算法在三個(gè)數(shù)據(jù)集上的完成時(shí)間

測(cè)試過(guò)程中使用200～2 000范圍內(nèi)各種數(shù)量的任務(wù)進(jìn)行仿真。將三種云計(jì)算資源調(diào)度算法用于與提出的改進(jìn)MOCSO進(jìn)行比較。可以看出，隨著任務(wù)數(shù)量的增加，資源調(diào)度算法的完成時(shí)間會(huì)增加。結(jié)果表明，相比于標(biāo)準(zhǔn)MOCSO，改進(jìn)的MOCSO的完成時(shí)間有所降低，同時(shí)還可以看出，本文算法的效果比其他三種對(duì)比算法要好。

圖3給出了不同資源調(diào)度算法在HPC2N、NASA和SDCS三個(gè)工作負(fù)載數(shù)據(jù)集測(cè)試的成本。 可以看出，隨著任務(wù)數(shù)量的增加，資源調(diào)度算法的成本也隨之增加。本文算法計(jì)算出的成本低于其他四種算法， 該結(jié)果表明提出的改進(jìn)MOCSO在云計(jì)算環(huán)境中支持云用戶減少開(kāi)支。

圖3 不同資源調(diào)度算法在三個(gè)數(shù)據(jù)集上的成本

圖4給出了不同資源調(diào)度算法在HPC2N、NASA和SDCS三個(gè)工作負(fù)載數(shù)據(jù)集測(cè)試的資源利用率。 可以明顯看出，隨著任務(wù)數(shù)量的增加，資源調(diào)度算法的資源利用率下降。與其他四種算法相比，本文算法在資源利用率上具有一定的優(yōu)勢(shì)。

圖4 不同資源調(diào)度算法在三個(gè)數(shù)據(jù)集上的利用率

仿真結(jié)果和分析結(jié)果表明，提出的改進(jìn)MOCSO在完成時(shí)間、成本、利用率方面提供了更好的質(zhì)量結(jié)果，相較于標(biāo)準(zhǔn)MOCSO有了不錯(cuò)的提升。進(jìn)一步闡明了改進(jìn)MOCSO非常適合IaaS云計(jì)算環(huán)境中的ETC和ECC矩陣。從性能評(píng)估可以看出，改進(jìn)MOCSO可能是一種強(qiáng)大的搜索和優(yōu)化技術(shù)，足以解決IaaS云計(jì)算環(huán)境中資源調(diào)度的多目標(biāo)問(wèn)題。

4 結(jié) 語(yǔ)

本文提出一種基于改進(jìn)多目標(biāo)布谷鳥(niǎo)搜索的資源調(diào)度算法，用于解決IaaS云計(jì)算環(huán)境中資源調(diào)度的多目標(biāo)問(wèn)題。該算法在多目標(biāo)布谷鳥(niǎo)搜索算法的基礎(chǔ)上，為了提高優(yōu)化算法的局部搜索能力和收斂速度，在隨機(jī)游走和丟棄概率兩個(gè)地方做出了一定的改進(jìn)。本文算法用最小的ETC和ECC矩陣將任務(wù)分配到虛擬資源上，以最大限度地減少完成時(shí)間和成本，解決IaaS云資源因?yàn)檎{(diào)度不夠而導(dǎo)致利用率低的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，與其他算法相比，本文算法在評(píng)估指標(biāo)上提供了更好的質(zhì)量結(jié)果。