基于云計(jì)算平臺(tái)的資源調(diào)度優(yōu)化研究

田玉靖　郭芳郁　張慶余

摘要：云計(jì)算平臺(tái)資源調(diào)度既是云計(jì)算系統(tǒng)的關(guān)鍵，又直接影響著系統(tǒng)的工作性能。為了提高云計(jì)算資源調(diào)度的效率，在深入分析粒子群算法和模擬退火算法的基礎(chǔ)上，提出了改進(jìn)粒子群的虛擬機(jī)部署算法及任務(wù)調(diào)度算法。一方面提高了虛擬機(jī)到物理機(jī)的資源利用率，另一方面在保證任務(wù)運(yùn)行時(shí)間最短的前提下優(yōu)化了負(fù)載不均衡問題。最后通過仿真工具CloudSim進(jìn)行了仿真，驗(yàn)證了算法的有效性。

關(guān)鍵詞：云計(jì)算；資源調(diào)度；粒子群算法；資源利用率；CloudSim

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）30-0187-04

隨著互聯(lián)網(wǎng)商業(yè)競(jìng)爭(zhēng)的日益加劇及虛擬化技術(shù)的發(fā)展，云計(jì)算已然徹底改變了信息技術(shù)的獲取及處理方式。而云平臺(tái)資源調(diào)度既是云計(jì)算的關(guān)鍵，又對(duì)云計(jì)算系統(tǒng)的工作性能有著直接的影響，因此研究獲取一款高效的計(jì)算資源調(diào)度模型至關(guān)重要。

針對(duì)云計(jì)算集群的異構(gòu)及不穩(wěn)定問題，文獻(xiàn)[1]提出了一種基于統(tǒng)計(jì)分析的Hadoop任務(wù)槽分配機(jī)制算法RSSO，并在一定程度上提高了集群的性能[1]。為了解決服務(wù)器的吞吐量問題，文獻(xiàn)[2]通過研究蜂群算法，提出了基于負(fù)載分發(fā)的蜂群算法的負(fù)載平衡機(jī)制[2]。此外基于蛙跳算法、免疫進(jìn)化算法等研究出的資源調(diào)度模型，雖均在提高云計(jì)算資源效率上做出了貢獻(xiàn)，但卻存在著易陷入局部最優(yōu)解、收斂速度慢的缺陷。

為了研究獲取更優(yōu)的云計(jì)算調(diào)度方案，提高云計(jì)算的資源利用率，本研究對(duì)粒子群算法的原理進(jìn)行了研究，并結(jié)合實(shí)際針對(duì)性的對(duì)算法進(jìn)行了改進(jìn)，提出了基于改進(jìn)粒子群算法的虛擬機(jī)部署算法（simulated annealing-particle swarm optimization，SA-PSO）及基于改進(jìn)粒子群算法的雙適應(yīng)度任務(wù)調(diào)度算法（double fitness- particle swarm optimization， DF-PSO）。之后通過仿真證明了提出算法的有效性。

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

云計(jì)算資源調(diào)度通常分為兩步，第一步在虛擬資源層分配任務(wù)至虛擬機(jī)上，第二步在物理資源層部署虛擬機(jī)至物理機(jī)上。

研究發(fā)現(xiàn)，一方面云平臺(tái)往往使用簡(jiǎn)單的虛擬機(jī)資源，以犧牲平臺(tái)負(fù)載均衡為代價(jià)來提高云平臺(tái)部署的效率。另一方面云平臺(tái)所提供的物理資源，是通過放置在物理機(jī)上的虛擬機(jī)而實(shí)現(xiàn)。又由于虛擬機(jī)對(duì)不同類型的資源需求不同，且物理機(jī)的配置也不盡相同，因此需要研究一種在保證部署效率的同時(shí)將虛擬資源均衡的調(diào)度到物理資源中的辦法。

2 基于改進(jìn)粒子群的虛擬機(jī)部署算法

2.1 改進(jìn)的粒子群算法

傳統(tǒng)的粒子群算法（particle swarm optimization，PSO）具有并行處理、魯棒性好等特點(diǎn)，目前已廣泛并成功應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)、信號(hào)處理等領(lǐng)域。在PSO中當(dāng)判斷得到計(jì)算出的適應(yīng)度優(yōu)于最優(yōu)解時(shí)，便會(huì)將該粒子作為最優(yōu)解，因此容易出現(xiàn)誤將局部最優(yōu)解定為全局最優(yōu)解的情況。

模擬退火算法源自固體退火原理，其理念為在退火過程中隨著溫度的降低，算法自身的概率突跳特性能夠促使其在解空間中獲得全局最優(yōu)解，即在溫度較高時(shí)可以舍棄局部最優(yōu)解而尋求全局最優(yōu)解[5]。算法核心為退火概率，計(jì)算公式如（1）所示。

[p=e（-△E（kT））] （1）

其中P表示溫度T時(shí)刻趨于平衡的概率，[△E]表示內(nèi)能的變化量，T表示溫度，K表示Boltzmann常數(shù)。

因此為了優(yōu)化傳統(tǒng)粒子群算法的收斂性，選擇在其過程中引入了模擬退火算法。當(dāng)有粒子的適應(yīng)度劣于最優(yōu)解時(shí)，便通過Metropolis進(jìn)行二次判斷，進(jìn)而決定舍棄與否。如此便實(shí)現(xiàn)了獲得局部最優(yōu)解后能夠概率性的跳出，并最終得到全局最優(yōu)解。如圖2所示為改進(jìn)粒子群算法的流程圖。

根據(jù)公式（2）并結(jié)合改進(jìn)算法，研究出的適應(yīng)度淘汰公式如（2）所示。

其中p表示接受適應(yīng)度的概率，F(xiàn)表示當(dāng)前適應(yīng)度，[Fg]表示最優(yōu)適應(yīng)度，T表示溫度（隨迭代次數(shù)的增加而減小）。[T=T?k]，k表示變化系數(shù)（k=0～1，k越大表示溫度降低的越慢）。

得到粒子群的適應(yīng)度函數(shù)值后，根據(jù)公式（2）計(jì)算其概率并進(jìn)行取舍。T的初值為第一次迭代時(shí)的最優(yōu)解，當(dāng)T較大而[F-Fg]較小時(shí)，P值較大，這時(shí)得到的解會(huì)劣于全局最優(yōu)解，同時(shí)也使得有了跳出局部最優(yōu)解的可能。隨著迭代次數(shù)的增加，系數(shù)k逐漸降低，，當(dāng)溫度低于最小值時(shí)，便跳出退火算法，重新根據(jù)粒子群算法直至得到全局最優(yōu)解。

2.2 基于改進(jìn)粒子群的虛擬機(jī)部署算法

對(duì)于研究提出的改進(jìn)粒子群算法，適應(yīng)度函數(shù)是判斷粒子優(yōu)劣性的唯一標(biāo)準(zhǔn)，但其并不唯一，需要具體問題具體分析。因此在對(duì)虛擬機(jī)的內(nèi)存、帶寬以及計(jì)算能力等因素進(jìn)行綜合分析研究后，所得出的負(fù)載不均衡度判斷適應(yīng)度函數(shù)如公式（3）、（4）、（5）所示。

[F1（x）=1ni=1n（mi-mavg）] （3）

[F2（x）=1ni=1n（bwi-bwavg）] （4）

[F3（x）=1ni=1n（ci-cavg）] （5）

其中[mi]表示i號(hào)物理機(jī)的內(nèi)存利用率，[mavg]表示所有物理機(jī)內(nèi)存利用率的平均值；[bwi]表示i號(hào)物理機(jī)的帶寬利用率，[bwavg]表示所有物理機(jī)帶寬利用率的平均值；其中[ci]表示i號(hào)物理機(jī)的計(jì)算能力利用率，[cavg]表示所有物理機(jī)計(jì)算能力利用率的平均值。

公式（6）為結(jié)合三個(gè)不平衡度得到的加權(quán)平均值，并以其作為判斷粒子優(yōu)劣性的標(biāo)準(zhǔn)。

[F（x）=1ni=1nαiFi（x）] （6）

其中[αi]表示第i個(gè)適應(yīng)度的影響因子。

將虛擬機(jī)分配到物理機(jī)上后，各個(gè)物理機(jī)所耗費(fèi)資源的平衡度稱為資源的負(fù)載均衡度。當(dāng)單臺(tái)物理機(jī)資源占用率過高，而其他某臺(tái)資源占用率過低的現(xiàn)象發(fā)生時(shí)，便會(huì)出現(xiàn)前一臺(tái)物理機(jī)運(yùn)行效率大大降低，而另一臺(tái)則處于閑置狀態(tài)的情況。加上物理機(jī)性能不盡相同的條件，分析得出計(jì)算負(fù)載均衡并不能以物理機(jī)分配資源的多少為標(biāo)準(zhǔn)。因此選取資源占用率為標(biāo)準(zhǔn)，并通過統(tǒng)計(jì)標(biāo)準(zhǔn)差對(duì)差異進(jìn)行比較。標(biāo)準(zhǔn)差小時(shí)表示各資源的占用率數(shù)值更接近，則分配方式均衡。反之則不均衡。

2.3虛擬機(jī)部署算法模型

將虛擬機(jī)分配到物理機(jī)的方式即為虛擬機(jī)的部署方式。結(jié)合粒子群算法，則定義粒子表示部署虛擬機(jī)的方式，粒子位置的變化表示方式的改變，負(fù)載不均衡度為粒子優(yōu)劣性的判斷標(biāo)準(zhǔn)。

定義物理機(jī)集合為[H=h1，h2，h3，…，hn]，n為物理機(jī)總數(shù)。虛擬機(jī)的集合為[VM=vm1，vm2，vm3，…，vml]，l為虛擬機(jī)總數(shù)。虛擬機(jī)到物理機(jī)的部署方案定義為[F?VM×H]，對(duì)于任意[（vmi，hj）∈F]，表示將i號(hào)虛擬機(jī)部署到j(luò)號(hào)物理機(jī)上。且單臺(tái)物理機(jī)上虛擬機(jī)所占資源的總量，不得超過其自身資源總量，即：

[?m∈M，Qij≤Rj，j=1，2，…，n] （7）

[Qij]表示將i號(hào)虛擬機(jī)部署到j(luò)號(hào)物理機(jī)所占用的資源，[Rj]表示i號(hào)物理機(jī)的資源總量。

定義粒子（長(zhǎng)度為l）表示部署方案，如公式（7）所示，其中[ki]表示將i號(hào)虛擬機(jī)部署到[ki]號(hào)物理機(jī)。

[x=k1，k2，…，ki，…kl，ki=1，2，…，n] （8）

定義粒子的速度為v，如公式（8）所示，其中[vi]表示第i位的變化量。

[v=v1，v2，…，vi，…vn，vi∈-n，n] （9）

3 基于改進(jìn)粒子群的雙適應(yīng)度任務(wù)調(diào)度算法

由于虛擬機(jī)數(shù)量遠(yuǎn)小于云平臺(tái)中的任務(wù)數(shù)量，因此需要研究獲取將任務(wù)分配到虛擬機(jī)的最優(yōu)分配方式，即最優(yōu)的任務(wù)調(diào)度策略。傳統(tǒng)的任務(wù)調(diào)度方式將重點(diǎn)放在了任務(wù)的完成時(shí)間上，而忽略了負(fù)載的均衡性，對(duì)此本研究提出了改進(jìn)離子群的任務(wù)調(diào)度算法，來完善這一現(xiàn)象。

3.1 適應(yīng)度函數(shù)

在任務(wù)調(diào)度算法中仍可沿用第2節(jié)所提出的改進(jìn)粒子群算法，但要針對(duì)性的作出改進(jìn)。為了能夠根據(jù)虛擬機(jī)性能、任務(wù)情況等提前預(yù)知負(fù)載均衡度和任務(wù)總耗時(shí)，本研究采用了雙適應(yīng)度方法，即任務(wù)執(zhí)行總時(shí)間和虛擬機(jī)負(fù)載均衡度，如公式（10）和公式（11）所示。

[F1（x）=maxr=1lj=1kTime（r，j）] （10）

其中l(wèi)表示虛擬機(jī)總數(shù)，k表示r號(hào)虛擬機(jī)所執(zhí)行的k號(hào)任務(wù)，[Time（r，j）]表示r號(hào)虛擬機(jī)所執(zhí)行的j號(hào)任務(wù)運(yùn)行耗時(shí)?？紤]到雖然虛擬機(jī)間為并行，但虛擬機(jī)上任務(wù)為串行執(zhí)行，因此可認(rèn)為某一虛擬機(jī)運(yùn)行時(shí)間的最大值即為任務(wù)執(zhí)行的總耗時(shí)。

[F2（x）=1li=1l（mi-mavg）2] （11）

其中l(wèi)表示虛擬機(jī)總數(shù)，[mi]表示i號(hào)虛擬機(jī)所有任務(wù)占據(jù)的內(nèi)存總量，[mavg]表示所有虛擬機(jī)內(nèi)存使用量的平均值。同樣由于虛擬機(jī)上的任務(wù)以串行方式執(zhí)行，因此無需比較內(nèi)存占用率，而是將分配到每一個(gè)虛擬機(jī)上任務(wù)的內(nèi)存總量作為計(jì)算負(fù)載均衡度的標(biāo)準(zhǔn)。

結(jié)合上述兩個(gè)公式，定義粒子的適應(yīng)度函數(shù)為：

[F（x）=1（αF1（x）+βF2（x））] （12）

其中[α]、[β]分別表示任務(wù)執(zhí)行總時(shí)間和虛擬機(jī)負(fù)載均衡度兩個(gè)適應(yīng)度的影響因子，其值視實(shí)際情況而定，根據(jù)需要可以控制其中一項(xiàng)起主導(dǎo)作用。

至此可以得出，通過任務(wù)執(zhí)行總時(shí)間和虛擬機(jī)負(fù)載均衡度兩個(gè)適應(yīng)度所共同得出的粒子優(yōu)劣性，既保證了任務(wù)完成時(shí)間最短，又保證了虛擬機(jī)的負(fù)載均衡。

3.2 任務(wù)調(diào)度算法模型

定義云平臺(tái)中虛擬機(jī)集合為[VM=vm1，vm2，vm3，…，vmn]（n表示虛擬機(jī)總數(shù)），任務(wù)集合為[T=t1，t2，t3，…，tl]（l表示任務(wù)總數(shù)），將任務(wù)分配至虛擬機(jī)的方案定義為[F?T×VM]，對(duì)于任意，表示將i號(hào)任務(wù)調(diào)度到j(luò)號(hào)虛擬機(jī)上。

定義粒子（長(zhǎng)度為l）表示調(diào)度方案，如公式（13）所示，其中[ki]表示將i號(hào)任務(wù)調(diào)度到[ki]號(hào)虛擬機(jī)上。

[x=k1，k2，…，ki，…kl，ki=1，2，…，n] （13）

定義粒子的速度為v，如公式（14）所示，其中vi表示第i位的變化量。

[v=v1，v2，…，vi，…vn，vi∈-n，n] （14）

綜合以上雙適應(yīng)度算法，公式（12）所得出的適應(yīng)度函數(shù)值，即為粒子所對(duì)應(yīng)調(diào)度策略的運(yùn)行總時(shí)間和負(fù)載不均衡度共同作用的結(jié)果，值越小則調(diào)度策略越優(yōu)。

4 資源調(diào)度算法仿真

仿真實(shí)驗(yàn)選取CloudSim工具，實(shí)驗(yàn)首先通過建立虛擬數(shù)據(jù)中心，并根據(jù)虛擬機(jī)部署算法將虛擬機(jī)部署到物理機(jī)上，再根據(jù)公式計(jì)算得出物理機(jī)的負(fù)載均衡度，以此驗(yàn)證算法的有效性。其次在上一實(shí)驗(yàn)的基礎(chǔ)上，通過虛擬任務(wù)大小、指令長(zhǎng)度隨機(jī)的多個(gè)任務(wù)，并根據(jù)任務(wù)調(diào)度策略將任務(wù)分配至相應(yīng)的虛擬機(jī)，最后通過判斷任務(wù)執(zhí)行時(shí)間即虛擬機(jī)的負(fù)載均衡度，來驗(yàn)證算法的有效性。

4.1 算法參數(shù)

4.1.1 虛擬機(jī)部署算法

將粒子的長(zhǎng)度設(shè)為9，粒子位置上的數(shù)表示虛擬機(jī)所分配到的物理機(jī)。將迭代次數(shù)設(shè)為800，并作為算法的結(jié)束條件，當(dāng)?shù)螖?shù)超過該閾值時(shí)，便取此刻的全局最優(yōu)解為虛擬機(jī)部署到物理機(jī)的最優(yōu)方式。

4.1.2 任務(wù)調(diào)度算法

云任務(wù)的創(chuàng)建表如表3所示。

考慮到此次實(shí)驗(yàn)運(yùn)行時(shí)間更為重要，因此定義公式（12）中的參數(shù)α=4，β=1，在保證負(fù)載均衡度的同時(shí)使總運(yùn)行時(shí)間最短。

該實(shí)驗(yàn)的迭代次數(shù)同樣設(shè)為800，當(dāng)?shù)螖?shù)超過該閾值時(shí)，便取此時(shí)的全局最優(yōu)解為任務(wù)調(diào)度的最優(yōu)方式。

4.2 結(jié)果分析

4.2.1 虛擬機(jī)部署算法結(jié)果分析

為了驗(yàn)證模擬退火算法的引入改善了傳統(tǒng)粒子群算法的收斂性，實(shí)驗(yàn)將傳統(tǒng)粒子群算法（PSO）與提出的虛擬機(jī)部署算法（即SA-PSO）相比較，定義F為適應(yīng)度，Y=1-F為負(fù)載均衡度，實(shí)驗(yàn)結(jié)果如圖3所示。

分析圖3可知，傳統(tǒng)粒子群算法在初次得到最優(yōu)解后便認(rèn)定該值為最優(yōu)解，不再調(diào)整。而改進(jìn)粒子算法由于退火模擬算法的作用，會(huì)跳出局部最優(yōu)解并不斷調(diào)整，最終獲得更優(yōu)的最優(yōu)解，證明了引入模擬退火算法的有效性。為了驗(yàn)證改進(jìn)粒子群算法在虛擬機(jī)部署方面的有效性，實(shí)驗(yàn)選取在同等條件下只改變虛擬機(jī)和物理機(jī)的個(gè)數(shù)，所得到的結(jié)果如圖4所示。

分析圖4可知，系統(tǒng)的負(fù)載均衡度會(huì)隨著物理機(jī)和虛擬機(jī)個(gè)數(shù)的增加而降低，但使用改進(jìn)粒子群算法的負(fù)載均衡度要優(yōu)于傳統(tǒng)粒子群算法的負(fù)載均衡度，能達(dá)到更好的部署效果。

4.2.2 任務(wù)調(diào)度算法結(jié)果分析

定義任務(wù)個(gè)數(shù)范圍為50～400，梯度為50。指令長(zhǎng)度范圍為10000-30000MI，任務(wù)長(zhǎng)度范圍為200-400MB，兩者均隨機(jī)生成。通過提出的任務(wù)調(diào)度算法（DF-PSO）和貪心算法（GA）對(duì)任務(wù)進(jìn)行調(diào)度，并比對(duì)任務(wù)完成的總時(shí)間和負(fù)載均衡度，得出的結(jié)果如圖5所示。

分析圖5可知，隨著任務(wù)數(shù)量的增加，任務(wù)的執(zhí)行時(shí)間幾乎相同， GA的調(diào)度方式有時(shí)更優(yōu)。

定義負(fù)載均衡度Y=1-F/10000，實(shí)驗(yàn)得出的任務(wù)調(diào)度算法（DF-PSO）和貪心算法（GA）的負(fù)載均衡度如圖6所示。從圖分析得出所提出的任務(wù)調(diào)度算法在負(fù)載均衡性上明顯優(yōu)于貪心算法。

分析圖5和圖6可知，所提出的基于粒子群雙適應(yīng)度任務(wù)調(diào)度算法，雖然犧牲了一定的任務(wù)執(zhí)行時(shí)間，但卻在負(fù)載均衡上占有很大的優(yōu)勢(shì)，因此對(duì)資源調(diào)度具有一定的價(jià)值。

5 結(jié)束語

在分析云資源調(diào)度方式的基礎(chǔ)上，提出了基于改進(jìn)粒子群的虛擬機(jī)部署算法以及基于改進(jìn)粒子群的雙適應(yīng)度任務(wù)調(diào)度算法，并通過實(shí)驗(yàn)對(duì)資源調(diào)度算法進(jìn)行了仿真，證明了算法在提高云計(jì)算資源利用效率方面的有效性。

參考文獻(xiàn)：

[1] 鄧傳華，范通讓，高峰. Hadoop下基于統(tǒng)計(jì)最優(yōu)的資源調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究，2013（2）：417-419+422.

[2] 姚婧，何聚厚. 基于自適應(yīng)蜂群算法的云計(jì)算負(fù)載平衡機(jī)制[J].計(jì)算機(jī)應(yīng)用，2012（9）：2448-2450+2454.

[3] M. Bist， M. Wariya and A. Agarwal， Comparing delta， open stack and Xen Cloud Platforms： A survey on open source IaaS， Advance Computing Conference （IACC）， 2013 IEEE 3rd International， Ghaziabad， 2013， pp. 96-100.

[4] Q. Li and Y. Guo， Optimization of Resource Scheduling in Cloud Computing， Symbolic and Numeric Algorithms for Scientific Computing （SYNASC）， 2010 12th International Symposium on， Timisoara， 2010， pp. 315-320.

[5] 羅中良，劉強(qiáng)，劉小勇. 一類混合模擬退火與蟻群優(yōu)化算法及其收斂性分析[J].工業(yè)儀表與自動(dòng)化裝置，2008（4）：3-6.

[6] 苗壯. 基于CloudStack的IaaS資源調(diào)度策略研究[D].哈爾濱工業(yè)大學(xué)，2014.

[7] 馬良. IAAS云計(jì)算平臺(tái)中資源管理和調(diào)度技術(shù)的研究[D].北京郵電大學(xué)，2013.

[8] 王炳旭. 基于IaaS云平臺(tái)的Hadoop資源調(diào)度策略研究[D].北京交通大學(xué)，2016.

[9] 張小慶. 基于云計(jì)算環(huán)境的資源提供優(yōu)化方法研究[D].武漢理工大學(xué)，2013.

[10] Y. Wang， J. Wang， C. Wang， J. Sun and X. Song， "Utility optimization strategy of resource scheduling in cloud computing，" 2016 35th Chinese Control Conference （CCC）， Chengdu， 2016， pp. 5235-5238.

[11] 白凱. IaaS平臺(tái)資源管理方案的設(shè)計(jì)與實(shí)現(xiàn)[D].西北大學(xué)，2012.

[12] 高貴升. 基于OpenStack的計(jì)算云的研究與實(shí)現(xiàn)[D].成都理工大學(xué)，2012.

[13] 王波，張曉磊. 基于粒子群遺傳算法的云計(jì)算任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2015（6）：84-88