程 曦 宋鐵成

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

0 引 言

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

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

(5)

(6)

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

2 改進多目標布谷鳥搜索的調(diào)度策略

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

2.1 多目標布谷鳥搜索算法及改進措施

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

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

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

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

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

布谷鳥蛋的寄生巢表示搜索空間的一個解，寄生巢位置表示解的適應(yīng)度值，布谷鳥搜索可以通過萊維飛行來更新t+1時刻的位置：

(7)

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

(8)

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

MOCSO中鳥巢位置的更新由解的相似性決定的：

(9)

圖1給出了多目標布谷鳥搜索算法的流程。

圖1 多目標布谷鳥搜索算法流程示意圖

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

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

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

(10)

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

(11)

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

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

(12)

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

2.2 多目標資源調(diào)度問題

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

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

(13)

式中：λ和μ表示加權(quán)系數(shù)?；诟倪M的MOCSO的多目標資源調(diào)度算法的偽代碼由算法1給出。

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

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

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

While((t

基于萊維飛行隨機生成一個解；

評估解的適合度Fi；

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

從n個巢中隨機選擇一個j巢；

評估j巢的K個解；

if (Fi>Fj) then

將Fi替換Fj；

end if

end if

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

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

t←t+1；

end while

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

3 實驗與結(jié)果分析

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

表1 實驗運行環(huán)境的詳細信息

3.1 數(shù)據(jù)集及評價指標

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

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

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

(14)

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

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

(15)

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

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

(16)

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

4 結(jié) 語

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