田玉靖　郭芳郁　張慶余

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2016）30-0187-04

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

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

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

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

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

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

2 基于改進粒子群的虛擬機部署算法

2.1 改進的粒子群算法

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

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

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

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

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

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

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

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

2.2 基于改進粒子群的虛擬機部署算法

對于研究提出的改進粒子群算法，適應(yīng)度函數(shù)是判斷粒子優(yōu)劣性的唯一標準，但其并不唯一，需要具體問題具體分析。因此在對虛擬機的內(nèi)存、帶寬以及計算能力等因素進行綜合分析研究后，所得出的負載不均衡度判斷適應(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號物理機的內(nèi)存利用率，[mavg]表示所有物理機內(nèi)存利用率的平均值；[bwi]表示i號物理機的帶寬利用率，[bwavg]表示所有物理機帶寬利用率的平均值；其中[ci]表示i號物理機的計算能力利用率，[cavg]表示所有物理機計算能力利用率的平均值。

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

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

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

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

2.3虛擬機部署算法模型

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

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

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

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

定義粒子（長度為l）表示部署方案，如公式（7）所示，其中[ki]表示將i號虛擬機部署到[ki]號物理機。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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ù)值，即為粒子所對應(yīng)調(diào)度策略的運行總時間和負載不均衡度共同作用的結(jié)果，值越小則調(diào)度策略越優(yōu)。

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

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

4.1 算法參數(shù)

4.1.1 虛擬機部署算法

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

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

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

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

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

4.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻：

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

[2] 姚婧，何聚厚. 基于自適應(yīng)蜂群算法的云計算負載平衡機制[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] 羅中良，劉強，劉小勇. 一類混合模擬退火與蟻群優(yōu)化算法及其收斂性分析[J].工業(yè)儀表與自動化裝置，2008（4）：3-6.

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

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

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

[9] 張小慶. 基于云計算環(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平臺資源管理方案的設(shè)計與實現(xiàn)[D].西北大學(xué)，2012.

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

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