基于多維QoS約束遺傳蟻群算法的云計(jì)算任務(wù)調(diào)度

魏志華，黃 青，況少平

(1.武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430070；2.湖北交通職業(yè)技術(shù)學(xué)院 交通信息學(xué)院，湖北 武漢 430070)

?

基于多維QoS約束遺傳蟻群算法的云計(jì)算任務(wù)調(diào)度

魏志華1，黃 青1，況少平2

(1.武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430070；2.湖北交通職業(yè)技術(shù)學(xué)院 交通信息學(xué)院，湖北 武漢 430070)

利用蟻群算法解決云計(jì)算任務(wù)調(diào)度問(wèn)題時(shí)，啟發(fā)因子、信息素蒸發(fā)系數(shù)、期望啟發(fā)因子等參數(shù)的設(shè)定往往采用經(jīng)驗(yàn)選取的方式，而這些參數(shù)又與算法性能息息相關(guān)，提出一種遺傳蟻群融合算法，對(duì)這些參數(shù)進(jìn)行編碼，在進(jìn)化過(guò)程中找到最優(yōu)組合，充分結(jié)合了蟻群算法的反饋機(jī)制、遺傳算法的全局搜索能力和收斂速度較快的特點(diǎn)，同時(shí)根據(jù)不同用戶的需求提出多維QoS的約束來(lái)進(jìn)行信息素的局部更新和全局更新。改進(jìn)的遺傳蟻群算法(GAACO)在云仿真平臺(tái)CloudSim上與模擬退火算法(SA)、基本蟻群算法(ACO)進(jìn)行了對(duì)比仿真實(shí)驗(yàn)，結(jié)果表明，該算法提高了解的收斂速度和全局搜索能力，同時(shí)在任務(wù)調(diào)度時(shí)間、成本、服務(wù)質(zhì)量及系統(tǒng)負(fù)載方面都有著更好的表現(xiàn)。

云計(jì)算；GAACO；自適應(yīng)；多維約束；仿真

云計(jì)算作為一種新型的商業(yè)服務(wù)模式，一經(jīng)提出便受到了工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注。隨著云計(jì)算相關(guān)研究與應(yīng)用的深入發(fā)展，云計(jì)算系統(tǒng)的規(guī)模越來(lái)越大，拓?fù)浣Y(jié)構(gòu)越來(lái)越復(fù)雜，再加上資源的異構(gòu)性，使得如何有效地進(jìn)行云計(jì)算任務(wù)調(diào)度成為了云計(jì)算領(lǐng)域一個(gè)相當(dāng)重要的研究課題。

已有文獻(xiàn)證明云計(jì)算任務(wù)調(diào)度屬于一個(gè)NP完全問(wèn)題[1-2]，可采用啟發(fā)式算法如遺傳算法[3-4]、蟻群算法[5]、模擬退火算法[6]、粒子群算法[7]等進(jìn)行求解，眾多學(xué)者對(duì)此表現(xiàn)出了極大的興趣和關(guān)注，在商業(yè)領(lǐng)域各大公司也對(duì)此做了一定的研究，以Google的Hadoop[8]為例，總共有3種調(diào)度算法，包括先來(lái)先服務(wù)算法[9]、公平調(diào)度算法[10]和計(jì)算能力調(diào)度算法[11]。目前，關(guān)于云計(jì)算任務(wù)調(diào)度還未形成統(tǒng)一的規(guī)范，但是一個(gè)好的任務(wù)調(diào)度策略應(yīng)該能夠適應(yīng)不同云計(jì)算環(huán)境，以及任務(wù)數(shù)量和性能等方面的差異，同時(shí)能夠根據(jù)用戶需求在成本、時(shí)間、可靠性及系統(tǒng)負(fù)載幾方面達(dá)到均衡。蟻群算法能夠較好地滿足群體性的組合優(yōu)化要求，但在選取啟發(fā)因子、信息素?fù)]發(fā)系數(shù)及期望啟發(fā)因子時(shí)往往依靠經(jīng)驗(yàn)，而這些參數(shù)又與算法性能息息相關(guān)[12]，同時(shí)存在收斂速度過(guò)慢、容易陷入局部最優(yōu)解等問(wèn)題。

針對(duì)以上不足，筆者提出了一種結(jié)合用戶多維QoS(quality of service)約束的遺傳蟻群算法，一方面將用戶需求用數(shù)學(xué)的形式融入到算法當(dāng)中，另一方面利用遺傳算法對(duì)啟發(fā)式因子、期望啟發(fā)因子及信息素?fù)]發(fā)系數(shù)進(jìn)行編碼，在進(jìn)化的過(guò)程中找到最優(yōu)組合，提高了蟻群算法的收斂速度和全局搜索的能力，使虛擬機(jī)資源負(fù)載和用戶綜合代價(jià)得到了優(yōu)化。

1 云計(jì)算任務(wù)調(diào)度問(wèn)題概述

云計(jì)算任務(wù)調(diào)度融合了用戶需求與資源分配的問(wèn)題，使得任務(wù)執(zhí)行時(shí)間跨度短、資源負(fù)載率低，為了深入分析問(wèn)題，建立如下云計(jì)算任務(wù)調(diào)度模型：將n個(gè)任務(wù)分配到m個(gè)資源上，用任務(wù)序列J={J1,J2,…,Ji}(i=1,2,…,n)代表n個(gè)任務(wù)，每個(gè)任務(wù)由任務(wù)長(zhǎng)度length、輸入數(shù)據(jù)文件inputfileSize、輸出文件大小outputfileSize這3部分組成，用虛擬機(jī)資源序列m={Vm1,Vm2,…,Vmj}(j=1,2，…,m)代表m個(gè)資源，每個(gè)資源由每秒處理指令速度mips、存儲(chǔ)大小storage、內(nèi)存ram、帶寬bw組成，則單個(gè)任務(wù)在每個(gè)虛擬機(jī)資源上的期望執(zhí)行時(shí)間Dn×m可表示為：

(1)

2 遺傳蟻群算法

2.1 遺傳蟻群算法求解云計(jì)算任務(wù)調(diào)度

蟻群算法的基本模型是意大利學(xué)者DIRIGO受到了自然界中螞蟻進(jìn)行群體性尋食行為的啟發(fā)而提出的，螞蟻尋食具有一定的自組織性，本質(zhì)上來(lái)講是最短路徑問(wèn)題，因而可以用來(lái)求解TSP等經(jīng)典的NP問(wèn)題。遺傳算法(genetic algorithm,GA)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。故可利用遺傳算法來(lái)優(yōu)化蟻群算法，以提高全局搜索能力和收斂速度。

(2)

螞蟻運(yùn)動(dòng)時(shí)，為避免信息素積累過(guò)多，每完成一次調(diào)度，需要對(duì)信息素進(jìn)行更新，可按如下規(guī)則進(jìn)行更新：

(3)

Δτij(n)=Q/multiQoSp

(4)

式中：Q為信息素強(qiáng)度；multiQoSp為多維QoS約束。

結(jié)合云計(jì)算任務(wù)調(diào)度的特點(diǎn)，遺傳蟻群算法對(duì)普通蟻群算法的改進(jìn)主要體現(xiàn)在以下幾個(gè)方面：①啟發(fā)因子、期望啟發(fā)因子及信息素?fù)]發(fā)系數(shù)經(jīng)過(guò)了遺傳種群的交叉變異，增加了解的可能性，提高了全局搜索能力。②信息素更新方面，進(jìn)行了全局和局部更新，同時(shí)又結(jié)合了云計(jì)算任務(wù)調(diào)度過(guò)程中對(duì)成本、時(shí)間、系統(tǒng)負(fù)載及服務(wù)質(zhì)量的要求，提出了多維QoS約束。

2.2 多維QoS約束函數(shù)的建立

普通蟻群算法在求解問(wèn)題時(shí)并未進(jìn)行多維QoS的約束，而在實(shí)際的云計(jì)算調(diào)度過(guò)程中，卻又有相應(yīng)的要求，因此，筆者增加了成本、時(shí)間、可靠性3個(gè)方面的多維QoS約束，建立了相應(yīng)的約束函數(shù)。

設(shè)Kbest為將當(dāng)前待分配的任務(wù)全部分配給性能最好虛擬機(jī)的任務(wù)集合，Kworst為將當(dāng)前待分配的任務(wù)全部分配給性能最差的虛擬機(jī)的任務(wù)集合，p為當(dāng)前螞蟻的編號(hào)，K為編號(hào)為p的螞蟻任務(wù)分配方案，Kj為第Kj個(gè)任務(wù)所分配的資源序號(hào)，k為當(dāng)前待分配任務(wù)個(gè)數(shù)?；诖耍岢隽巳缦录僭O(shè)。

假設(shè)1 用Tmin表示將當(dāng)前待分配任務(wù)全部分配到性能最好的資源時(shí)的時(shí)間代價(jià)，Tmax表示將當(dāng)前待分配任務(wù)全部分配到性能最差資源時(shí)的時(shí)間代價(jià)，Tc表示采用遺傳蟻群算法進(jìn)行任務(wù)調(diào)度時(shí)的時(shí)間代價(jià)，Tres表示時(shí)間約束，其數(shù)學(xué)定義分別為：

假設(shè)2 用Cmin表示將當(dāng)前待分配任務(wù)全部分配到性能最好資源時(shí)的成本代價(jià)，Cmax表示將當(dāng)前待分配任務(wù)全部分配到性能最差資源時(shí)的成本代價(jià)，Cc表示采用遺傳蟻群算法進(jìn)行任務(wù)調(diào)度時(shí)的成本代價(jià)，Cres表示成本約束，其數(shù)學(xué)定義分別為：

式中：perofmips為單位時(shí)間執(zhí)行指令的成本代價(jià)；perofbw為單位時(shí)間帶寬的成本代價(jià)。

假設(shè)3Res為采用遺傳蟻群算法進(jìn)行任務(wù)調(diào)度時(shí)的可靠性量化值；resRes為可靠性約束，其數(shù)學(xué)定義式分別為：

resResKj=Resp/antSize

其中，antSize為螞蟻種群的大小。

假設(shè)4λ1，λ2，λ3分別為成本、時(shí)間、可靠性的權(quán)重系數(shù)(λ1+λ2+λ3=1)，可根據(jù)用戶要求進(jìn)行調(diào)整，筆者選取3個(gè)系數(shù)分別為0.3,0.4,0.4，最終多維QoS約束函數(shù)定義為：

multiQoSp=λ1·Tresp+λ2·Cresp+λ3·resResp

(5)

2.3 算法流程描述

開(kāi)始；

初始化遺傳算法變異概率Pm、交叉概率Pc、種群規(guī)模大小、進(jìn)化代數(shù)等參數(shù)；

初始化蟻群算法種群螞蟻數(shù)量m、虛擬機(jī)資源集合J、信息素強(qiáng)度Q，以及啟發(fā)因子α、期望啟發(fā)因子β及信息素?fù)]發(fā)系數(shù)γ的最大值；

While(nc<進(jìn)化代數(shù)){

分別對(duì)α,β,γ進(jìn)行二進(jìn)制編碼；

選擇個(gè)體進(jìn)行交叉；

分別α,β,γ進(jìn)行多點(diǎn)變異；

對(duì)α,β,γ進(jìn)行解碼；

While(所有螞蟻是否已完成任務(wù)分配){

將m只螞蟻隨機(jī)分配到虛擬機(jī)序J上；

初始化每只螞蟻的禁忌表及每只螞蟻可能路徑上的信息素；

While(所有任務(wù)是否已分配完){

For 每只螞蟻do

記錄已分配虛擬機(jī)；

利用式(2)和已解碼α,β,γ的初步生成待分配虛擬機(jī)概率；

用輪盤(pán)賭的方式選擇任務(wù)執(zhí)行的虛擬機(jī)；

計(jì)算每個(gè)螞蟻的多維約束函數(shù)值multi-QoSp；

利用式(5)進(jìn)行局部更新；

存儲(chǔ)當(dāng)前螞蟻任務(wù)調(diào)度方案；

記錄當(dāng)前最好的解及α,β,γ的值；}

計(jì)算每只螞蟻約束函數(shù)值；

記錄當(dāng)前最佳調(diào)度方案；

記錄當(dāng)前最好的解及α,β,γ的值；

全局更新；

禁忌表清零；

nc++；}}

結(jié)束；

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

為了測(cè)試筆者算法的性能，實(shí)驗(yàn)采用墨爾本大學(xué)網(wǎng)格實(shí)驗(yàn)室的CloudSim3.0.2云仿真平臺(tái)，同時(shí)與基本蟻群算法(ACO)[13]、模擬退火算法(SA)[14]進(jìn)行了仿真對(duì)比和結(jié)果分析。在云仿真平臺(tái)中首先新建MyAll-ocationTest類進(jìn)行云環(huán)境的初始配置，包括數(shù)據(jù)中心的創(chuàng)建、云計(jì)算任務(wù)的規(guī)模參數(shù)初始化、任務(wù)大小與輸入輸出數(shù)據(jù)文件大小、虛擬機(jī)資源的創(chuàng)建，每個(gè)虛擬機(jī)資源包括cpu個(gè)數(shù)、內(nèi)存大小、帶寬以及指令處理速度等指標(biāo)，創(chuàng)建cloudsim對(duì)象添加云計(jì)算任務(wù)，同時(shí)在DatacenterBroker類中新建GAACO、ACO與SA共3種算法。遺傳蟻群算法相關(guān)參數(shù)如表1所示。

表1 遺傳蟻群算法參數(shù)表

3.2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

筆者從4個(gè)方面來(lái)比較遺傳蟻群算法的性能，即平均時(shí)間花費(fèi)、平均成本、算法服務(wù)質(zhì)量、系統(tǒng)資源負(fù)載率。初始時(shí)，任務(wù)規(guī)模為10個(gè)，云計(jì)算資源為10個(gè)，虛擬機(jī)存儲(chǔ)大小為10 GB，內(nèi)存大小為256 MB，cpu個(gè)數(shù)為1，帶寬為1 000 MB，單位時(shí)間帶寬花費(fèi)為0.01元/s，單位時(shí)間指令花費(fèi)為0.01元/s。任務(wù)大小按10個(gè)遞增進(jìn)行實(shí)驗(yàn)。算法服務(wù)質(zhì)量是通過(guò)multiQoS體現(xiàn)的。定義資源負(fù)載率為：

(6)

式中：usei為第i臺(tái)資源的負(fù)載；useAvg為系統(tǒng)平均負(fù)載；n為資源個(gè)數(shù)。

任務(wù)數(shù)量按10個(gè)遞增時(shí)，計(jì)算各算法平均時(shí)間代價(jià)，結(jié)果如圖1所示?？梢钥吹紾AACO的時(shí)間代價(jià)要優(yōu)于ACO，但時(shí)間花費(fèi)比SA長(zhǎng)，并且隨著任務(wù)數(shù)量的增加，時(shí)間上的差距越來(lái)越大，與ACO相比時(shí)間減少了50.9%，與SA相比相差3%，故從時(shí)間代價(jià)來(lái)說(shuō)筆者算法優(yōu)于ACO，但與SA相差不大。

圖1 各算法平均時(shí)間代價(jià)

各算法在不同任務(wù)數(shù)量條件下的成本代價(jià)如圖2所示，任務(wù)數(shù)量以10的倍數(shù)增加，可以看到各算法的差異并不大，平均成本代價(jià)僅相差1%左右。

圖2 各算法成本代價(jià)

各算法服務(wù)質(zhì)量實(shí)驗(yàn)結(jié)果如圖3所示，可以看出筆者算法與SA的服務(wù)質(zhì)量隨著任務(wù)數(shù)量的增長(zhǎng)在緩慢上升，而ACO卻呈現(xiàn)直線急劇上升的趨勢(shì)，服務(wù)質(zhì)量是成本、時(shí)間、可靠性的一個(gè)綜合指標(biāo)，可以看到GAACO的綜合表現(xiàn)要優(yōu)于ACO和SA ，分別降低了14.4%和76.8%。

圖3 各算法服務(wù)質(zhì)量

圖4 各算法系統(tǒng)負(fù)載

各算法系統(tǒng)負(fù)載實(shí)驗(yàn)結(jié)果如圖4所示，可以看出ACO的系統(tǒng)負(fù)載一直維持在一個(gè)較高的水平，而GAACO的系統(tǒng)負(fù)載高于SA卻明顯優(yōu)于ACO，平均系統(tǒng)負(fù)載GAACO比ACO減少了50.2%。同時(shí)結(jié)合圖1～圖3可知，SA更偏向的是一種平均調(diào)度，即分配到每個(gè)虛擬機(jī)上的任務(wù)個(gè)數(shù)都基本一樣，所以利用式(6)得出的負(fù)載為0，但云計(jì)算任務(wù)調(diào)度往往要求成本、時(shí)間、可靠性在用戶需求的基礎(chǔ)上達(dá)到均衡，這體現(xiàn)在QoS上。綜上所述，筆者所提出的算法在實(shí)際調(diào)度過(guò)程中更能滿足客戶的需求。

4 結(jié)論

在對(duì)云計(jì)算任務(wù)調(diào)度進(jìn)行了深入的研究之后，筆者提出的算法從4個(gè)方面與基本蟻群算法、模擬退火算法進(jìn)行了比較，結(jié)果表明筆者算法的綜合性能要優(yōu)于其他兩個(gè)算法，能夠較好地均衡時(shí)間代價(jià)、成本代價(jià)、可靠性和系統(tǒng)負(fù)載，能較好地滿足用戶多維QoS的要求。

[1] 李建鋒，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2011，31(1):184-186.

[2] BAYATI M，PRABHAKAR B，SHAH D，et al. Iterative scheduling algorithms[C]∥Infocom IEEE International Conference on Computer Communications. [S.l.]:[s.n.],2007:445-453.

[3] 熊聰聰，馮龍，陳麗仙，等.云計(jì)算中基于遺傳算法的任務(wù)調(diào)度算法研究[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012(S1):1-4.

[4] WEI Y , TIAN L. Research on cloud design resources scheduling based on genetic algorithm[C]∥International Conference on Systems and Informatic.[S.l.]:[s.n.],2012:2651-2656.

[5] 王芳，李美安，段衛(wèi)軍.基于動(dòng)態(tài)自適應(yīng)蟻群算法的云計(jì)算任務(wù)調(diào)度[J].計(jì)算機(jī)應(yīng)用，2013，33(11):3160-3162.

[6] 袁曉林，施化吉.基于模擬退火算法的云計(jì)算資源調(diào)度模型[J].軟件導(dǎo)刊，2015(2):68-70.

[7] 張?zhí)眨诰?，楊興耀,等.基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與應(yīng)用，2013,49(19):68-72.

[8] WHITE T. Hadoop: the definitive guide[M].[S.l.]:O’reilly Media Inc, 2010：215-220.

[9] KULKARNI A P, KHANDEWAL M. Survey on hadoop and introduction to YARN[J]. International Journal of Emerging Technology and Advanced Engineering, 2014,4(5):82-87.

[10] WANG J, YAO Y, MAO Y, et al. FRESH: fair and efficient slot configuration and scheduling for hadoop clusters[C]∥IEEE International Conference on Cloud Computing.[S.l.]:[s.n.], 2014:761-768.

[11] ELKHOLY A M, SALLAM E A H. Self-adaptive hadoop scheduler for heterogeneous resources[C]∥International Conference on Computer Engineering and Systems.[S.l.]:[s.n.], 2014:427-432.

[12] 杜衡吉，李勇.蟻群算法中參數(shù)設(shè)置對(duì)其性能影響的研究[J].現(xiàn)代計(jì)算機(jī)(專業(yè)版)，2012(9):3-7.

[13] 段海濱.蟻群算法原理及應(yīng)用[M].北京:科學(xué)出版社,2005:36-37.

[14] 張浩榮，陳平華，熊建斌.基于蟻群模擬退火算法的云環(huán)境任務(wù)調(diào)度[J].廣東工業(yè)大學(xué)學(xué)報(bào)，2014(3):77-82.Cloud Computing Task Scheduling Based on Adaptive and QoS Constraint Genetic Ant Colony Algorithm

WEI Zhihua:Prof.; School of Computer Science and Technology, WUT, Wuhan 430070, China.

WEIZhihua,HUANGQing,KUANGShaoping

When using ant colony algorithm to solve the task scheduling problem in cloud computing, the set of heuristic factor, information element evaporation coefficient, expectations inspired factor tend to use experience to select the way, but these parameters is closely related to the performance of the algorithm,a kind of genetic ant colony mixed algorithm was proposed. The parameters are coded, and the optimal combination is found in the process of evolution. The feedback mechanism of ant colony algorithm and the global searching ability of genetic algorithm and the fast convergence rate are fully integrated. At the same time, according to the needs of different users, the paper puts forward the constraint of multi-dimensional QoS to carry on the local update and global update of the pheromone. A constructive simulation experiments was done in the cloud simulation platform CloudSim between the genetic ant colony algorithm(GAACO), simulated annealing algorithm(SA) and basic ant colony algorithm(ACO). The results showed that the algorithm not only can improve the convergence speed and global search ability, but also has better performance in job scheduling time, cost, and quality of service and system load.

cloud computing; GAACO; Qos; simulation

2095-3852(2016)05-0631-05

A

2016-05-17.

魏志華(1964-)，男，湖北武漢人，武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院教授.

TP338;TP316.4 DOI：10.3963/j.issn.2095-3852.2016.05.024