全 ,

(長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院,長(zhǎng)沙 410114)

0 概述

云計(jì)算是互聯(lián)網(wǎng)計(jì)算發(fā)展的新革命,相比于分布式計(jì)算其具有更突出的優(yōu)勢(shì),它是一種高效率的多功能計(jì)算系統(tǒng)[1],大規(guī)模的計(jì)算資源確保了云服務(wù)的高效性。云計(jì)算中需要處理的任務(wù)被調(diào)度分配到在各個(gè)計(jì)算資源中,用戶(hù)可以通過(guò)云計(jì)算按照需求獲取計(jì)算與信息服務(wù),以及高效的存儲(chǔ)服務(wù)[2]。任務(wù)調(diào)度作為云計(jì)算的核心技術(shù),在云計(jì)算處理任務(wù)的過(guò)程中,任務(wù)調(diào)度是不可避免的重要環(huán)節(jié)之一,因此,優(yōu)化任務(wù)調(diào)度機(jī)制是強(qiáng)化云計(jì)算綜合性能的重要方法。

為了更有效地改善云計(jì)算的服務(wù)性能,有學(xué)者針對(duì)云計(jì)算中的任務(wù)調(diào)度機(jī)制所遇到的問(wèn)題展開(kāi)了研究。文獻(xiàn)[3]以提高云計(jì)算服務(wù)質(zhì)量為基礎(chǔ),通過(guò)對(duì)蜂群算法的改進(jìn),能夠在一定程度上提高算法的全局搜索能力,并且能夠有效地滿(mǎn)足QoS需求;文獻(xiàn)[4]引入局部搜索算子對(duì)蜂群算法進(jìn)行優(yōu)化,能夠有效地縮短任務(wù)的完成時(shí)間;文獻(xiàn)[5]利用蟻群算法對(duì)云計(jì)算任務(wù)調(diào)度系統(tǒng)進(jìn)行改善,能夠較好地在多個(gè)方面提高系統(tǒng)性能;文獻(xiàn)[6]針對(duì)任務(wù)調(diào)度過(guò)程中虛擬機(jī)負(fù)載的問(wèn)題,利用蟻群算法較好的反饋機(jī)制提出蟻群優(yōu)化算法,能夠較好地改善資源利用率;文獻(xiàn)[7]利用遺傳算法較好的搜索能力能夠有效地改善任務(wù)調(diào)度的性能,使虛擬機(jī)達(dá)到負(fù)載均衡;文獻(xiàn)[8]利用遺傳算法前期搜索能力強(qiáng)的優(yōu)勢(shì)與蟻群算法的信息反饋的特點(diǎn),將2種算法相結(jié)合來(lái)彌補(bǔ)各自的問(wèn)題,該算法在改善收斂速度的同時(shí)滿(mǎn)足用戶(hù)所要求的服務(wù)質(zhì)量;文獻(xiàn)[9]對(duì)遺傳算法中的交叉和變異的概率公式進(jìn)行優(yōu)化,提高了全局搜索能力;文獻(xiàn)[10]針對(duì)云計(jì)算中任務(wù)調(diào)度需要多個(gè)目標(biāo)優(yōu)化的問(wèn)題,提出了改進(jìn)的Memetic算法,該算法能夠較快地找到全局最優(yōu)解,提高了計(jì)算效率。

本文針對(duì)蟻群算法收斂速度慢與任務(wù)分配不均的問(wèn)題,結(jié)合調(diào)度機(jī)制的特點(diǎn)對(duì)算法中信息素更新方法進(jìn)行優(yōu)化,通過(guò)對(duì)信息素增量賦予權(quán)值,改進(jìn)算法的計(jì)算效率,并采用揮發(fā)系數(shù)動(dòng)態(tài)調(diào)整的方法,提高算法的搜索能力,在進(jìn)行局部信息素更新時(shí),加入衡量虛擬機(jī)工作負(fù)載的權(quán)重系數(shù),保證虛擬機(jī)的負(fù)載均衡。

1 任務(wù)調(diào)度模型

云計(jì)算在處理任務(wù)時(shí),任務(wù)需要被合理地分配到各個(gè)計(jì)算資源中,其任務(wù)調(diào)度機(jī)制可以表示為:通過(guò)任務(wù)調(diào)度策略將需要處理的任務(wù)分配到異構(gòu)的資源上,使全部任務(wù)在被執(zhí)行完成之后所需時(shí)間最少并滿(mǎn)足負(fù)載均衡。本文考慮的問(wèn)題是將N個(gè)相互獨(dú)立、不同大小的任務(wù)根據(jù)任務(wù)調(diào)度算法分配到M個(gè)性能不同的虛擬機(jī)進(jìn)行并行計(jì)算,根據(jù)虛擬機(jī)處理任務(wù)時(shí)的性能指標(biāo)得出實(shí)驗(yàn)結(jié)果。

在云計(jì)算調(diào)度模型中需要處理的作業(yè)為N個(gè)互不關(guān)聯(lián)的任務(wù),N個(gè)任務(wù)集合表示為:Task={t1,t2,…,tn},MI表示任務(wù)的指令長(zhǎng)度,其中MIi表示任務(wù)ti的指令長(zhǎng)度[11]。處理任務(wù)的異構(gòu)資源為M個(gè)虛擬機(jī),虛擬機(jī)集合表示為VM={v1,v2,…,vm},MIPS表示虛擬機(jī)的執(zhí)行速度,其中MIPSj表示虛擬機(jī)vj的執(zhí)行速度[12]。

為計(jì)算每個(gè)任務(wù)在不同虛擬機(jī)上所需要的處理時(shí)間,定義執(zhí)行時(shí)間矩陣為:

其中,timeij表示表示虛擬機(jī)vj處理任務(wù)ti所需要的執(zhí)行時(shí)間,并且timeij=MIi/MIPSj。

根據(jù)虛擬機(jī)與任務(wù)的匹配關(guān)系建立矩陣x[i][j],表示任務(wù)ti是否分配給虛擬機(jī)vj,定義為:

2 云計(jì)算任務(wù)調(diào)度策略

2.1 基于蟻群算法的調(diào)度模型

蟻群算法作為一種全局優(yōu)化算法,一般被用來(lái)解決路徑優(yōu)化的問(wèn)題,該算法具有分布性、隨機(jī)性、反饋性等特點(diǎn),在云環(huán)境中利用蟻群算法的特點(diǎn)能夠有效地處理任務(wù)調(diào)度機(jī)制所遇到的問(wèn)題。

(3)

在完成一次迭代之后,根據(jù)虛擬機(jī)與任務(wù)的配對(duì)情況,對(duì)信息素τij(t)進(jìn)行更新,表達(dá)式為:

τij(t+1)=ρ·τij(t)+Δτij(t)

(4)

2.2 任務(wù)調(diào)度算法的優(yōu)化

蟻群算法在解決任務(wù)分配的問(wèn)題時(shí),對(duì)任務(wù)的分配采用隨機(jī)選擇的方法,影響了算法的搜索能力,使算法需要更多的迭代才能得到最優(yōu)分配方案,因此,會(huì)出現(xiàn)收斂速度變慢的問(wèn)題,雖然通過(guò)正反饋機(jī)制可以強(qiáng)化較優(yōu)的解,但會(huì)導(dǎo)致停滯現(xiàn)象。針對(duì)這些問(wèn)題,本文通過(guò)對(duì)信息素增量Δτij(t)賦予權(quán)值的方法,改變?nèi)中畔⑺氐母乱?guī)則,并依據(jù)迭代次數(shù)的增加更新?lián)]發(fā)系數(shù)ρ的參數(shù)值,改善了算法的綜合性能。

2.2.1 信息素的更新

為了更好地利用最優(yōu)解的信息,使算法得到較好的性能,在每次迭代完成之后,將每只螞蟻所形成的解按照從小到大排序,表示為F1(t)≤F2(t)≤…≤Fm(t),利用解的大小對(duì)信息素增量賦予不同的權(quán)值,最優(yōu)解的權(quán)值最大。最優(yōu)解的權(quán)值大小為a,當(dāng)全部的螞蟻進(jìn)行完一次迭代之后,利用賦予信息素增量權(quán)值的方法對(duì)信息素做全局更新:

(6)

負(fù)載均衡是衡量任務(wù)調(diào)度算法的重要指標(biāo),針對(duì)負(fù)載均衡的問(wèn)題,在信息素的更新規(guī)則中,通過(guò)加入局部信息素的更新方法來(lái)保障任務(wù)調(diào)度的負(fù)載均衡。局部信息素的更新方法定義為:每完成一次任務(wù)與虛擬機(jī)的配對(duì)之后,將引入局部信息素,并依據(jù)虛擬機(jī)的運(yùn)行時(shí)間對(duì)其進(jìn)行更新,更新規(guī)則為:

2.2.2 自適應(yīng)調(diào)整策略

信息素?fù)]發(fā)系數(shù)ρ的數(shù)值設(shè)定是否合理將會(huì)影響算法選找最優(yōu)分配方案的搜索能力與計(jì)算效率[16],通過(guò)動(dòng)態(tài)地改變?chǔ)训闹?從而能自適應(yīng)地調(diào)整信息素的大小,因此,可以有效地加強(qiáng)算法前期的搜索能力,豐富解的多樣性,并隨著迭代次數(shù)的增加,最優(yōu)分配方案的概率得到提高,保證了算法的綜合性能,揮發(fā)系數(shù)ρ的調(diào)整策略為:

ρa(bǔ)(t)=1-ln(t)/ln(t+c)

(9)

其中,C為常數(shù),揮發(fā)系數(shù)ρ的大小限制在[ρmin,ρmax],使ρ的值不會(huì)因?yàn)檫^(guò)大或過(guò)小,而導(dǎo)致求解效率變慢或者搜索能力變?nèi)?保證了算法的綜合性能。

2.3 算法的實(shí)現(xiàn)過(guò)程

算法實(shí)現(xiàn)過(guò)程如下:

1)初始化啟發(fā)函數(shù)ηij(t)、信息素τij(t)、最大迭代次數(shù)tmax、螞蟻數(shù)量n。

3)更新螞蟻k的任務(wù)禁忌表tabuk,如果螞蟻k將任務(wù)ti分配給虛擬機(jī)vj,則將任務(wù)ti加入禁忌表tabuk,更新任務(wù)集合Ek,如果任務(wù)集合Ek為空,則執(zhí)行下一步,否則將跳轉(zhuǎn)到第2步。

5)全局信息素的更新,根據(jù)式(5)對(duì)全局最優(yōu)解進(jìn)行更新,判斷是否為最大迭代次數(shù),如果t≥tmax,則結(jié)束算法,否則t++、k=1并跳轉(zhuǎn)到第2步。

算法偽代碼如下:

1.initialize ηij(t),τij(t),tmax,n,t←1;

2.while t≤tmax

3.initialize k←1,tabuk,Ek;

5.if k≤n

6.while Ek≠φ

8.update tabuk,Ek;

9.end while

10.update τij(t) by式(7);

11.calculate Fk(t);

13.k++;

14.end if

15.update τij(t) by式(6);

17.update Fbestby式(5);

18.t++;

19.end while

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

實(shí)驗(yàn)選擇云計(jì)算仿真器CloudSim對(duì)任務(wù)調(diào)度實(shí)驗(yàn)進(jìn)行仿真,CloudSim是一種可擴(kuò)展、通用的仿真框架,能夠?qū)υ朴?jì)算任務(wù)調(diào)度實(shí)驗(yàn)進(jìn)行模型建立和仿真模擬。實(shí)驗(yàn)對(duì)本文設(shè)計(jì)的改進(jìn)蟻群算法與Min-Min算法、基本蟻群算法進(jìn)行仿真,并比較3種不同算法的實(shí)驗(yàn)結(jié)果。

1)Min-Min算法

采用Min-Min算法處理任務(wù)調(diào)度的過(guò)程為:通過(guò)計(jì)算每個(gè)虛擬機(jī)處理不同任務(wù)時(shí)所需要的完成時(shí)間,選出每個(gè)任務(wù)所需完成時(shí)間的最小值,根據(jù)最小值的大小將任務(wù)進(jìn)行排序,按照由小到大的順序依次分配任務(wù),因?yàn)镸in-Min算法只考慮任務(wù)被完成的時(shí)間為優(yōu)化目標(biāo),所以會(huì)導(dǎo)致任務(wù)分配不合理的問(wèn)題。

2)蟻群算法

在應(yīng)用蟻群算法解決任務(wù)調(diào)度問(wèn)題的過(guò)程中,首先根據(jù)虛擬機(jī)對(duì)每個(gè)任務(wù)的處理能力,計(jì)算任務(wù)與虛擬機(jī)的配對(duì)概率,由螞蟻根據(jù)配對(duì)概率對(duì)任務(wù)進(jìn)行分配,完成一次迭代之后,更新目標(biāo)解與信息素,在算法完成收斂時(shí)得到目標(biāo)解。由于隨機(jī)選擇的方法與反饋機(jī)制的原因,因此會(huì)導(dǎo)致收斂速度變慢與早熟現(xiàn)象。

參數(shù)設(shè)置:需要處理的任務(wù)個(gè)數(shù)分別設(shè)為40、60、80、100和120,任務(wù)的指令長(zhǎng)度為5 000 MI～50 000 MI,虛擬機(jī)數(shù)量為8,執(zhí)行速度為1 000 MIPS～2 000 MIPS。根據(jù)文獻(xiàn)[6,17],并通過(guò)多次實(shí)驗(yàn)進(jìn)行測(cè)試仿真,對(duì)算法參數(shù)進(jìn)行設(shè)置,算法參數(shù)如表1所示。

表1 任務(wù)調(diào)度算法參數(shù)

為了驗(yàn)證改進(jìn)蟻群算法應(yīng)用于云任務(wù)調(diào)度時(shí)的收斂速度,實(shí)驗(yàn)方案設(shè)置為:對(duì)于不相同的任務(wù)個(gè)數(shù),分別計(jì)算改進(jìn)蟻群算法與基本蟻群算法2種方案,找到最優(yōu)解時(shí)的迭代次數(shù),虛擬機(jī)的個(gè)數(shù)為8。每組數(shù)據(jù)為10次實(shí)驗(yàn)的平均值,實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 算法的迭代次數(shù)

圖1的仿真結(jié)果表明:改進(jìn)蟻群算法完成收斂所需的迭代次數(shù)低于基本蟻群算法,因?yàn)楸疚耐ㄟ^(guò)結(jié)合調(diào)度機(jī)制的特點(diǎn)對(duì)信息素的更新規(guī)則進(jìn)行優(yōu)化,通過(guò)對(duì)信息素增量Δτij(t)賦予權(quán)值的方法,加快算法的求解速度,并對(duì)揮發(fā)系數(shù)的值進(jìn)行動(dòng)態(tài)更新,隨著迭代次數(shù)的增加,提高最優(yōu)目標(biāo)解的概率,進(jìn)一步加快算法的計(jì)算效率,收斂速度得到提高,因此改進(jìn)蟻群算法相比于基本蟻群算法能夠更快地找到最優(yōu)解,算法性能得到較好地改善。

圖2為在任務(wù)個(gè)數(shù)不相同的情況下,基于3種不同調(diào)度算法虛擬機(jī)完成任務(wù)所需要的總執(zhí)行時(shí)間的對(duì)比。

圖2 不同算法的任務(wù)完成時(shí)間

通過(guò)對(duì)3種算法的對(duì)比,改進(jìn)蟻群算法根據(jù)解的大小作為信息素更新時(shí)的權(quán)值,并依據(jù)迭代次數(shù)的大小計(jì)算揮發(fā)系數(shù),使算法的全局搜索能力得到加強(qiáng),豐富解的多樣性,最終解的大小更優(yōu),因此,總執(zhí)行時(shí)間更快,與Min-Min算法、基本蟻群算法相比分別減少了16%～29%、10%～17%。

圖3 不同算法的負(fù)載均衡情況

由于Min-Min算法只把總執(zhí)行時(shí)間作為優(yōu)化目標(biāo),因此負(fù)載均衡度最差,本文設(shè)計(jì)的改進(jìn)蟻群算法根據(jù)虛擬機(jī)的運(yùn)行情況對(duì)局部信息素進(jìn)行更新,優(yōu)化了虛擬機(jī)處理任務(wù)時(shí)的負(fù)載均衡,對(duì)比基本蟻群算法,虛擬機(jī)工作的負(fù)載均衡效果更好。

4 結(jié)束語(yǔ)

通過(guò)蟻群算法處理云計(jì)算中的任務(wù)時(shí),會(huì)遇到求解速度慢和負(fù)載不均衡的問(wèn)題,本文通過(guò)添加權(quán)值的方法對(duì)信息素更新規(guī)則進(jìn)行改進(jìn),利用每只螞蟻所生成的解作為信息素增量的權(quán)重,加快算法在選擇匹配方案時(shí)的求解效率,并采用動(dòng)態(tài)更新?lián)]發(fā)系數(shù)的方法,根據(jù)迭代次數(shù)自適應(yīng)地對(duì)權(quán)值進(jìn)行更新調(diào)整,提高算法的全局搜索能力,豐富解的多樣性,改善了算法的收斂性,保證算法的綜合性能。在對(duì)局部信息素更新時(shí),加入衡量虛擬機(jī)負(fù)載的權(quán)重系數(shù),使任務(wù)得到合理分配。實(shí)驗(yàn)結(jié)果表明,本文設(shè)計(jì)的改進(jìn)算法能夠較快地得到最優(yōu)解,與Min-Min算法和基本蟻群算法相比,任務(wù)的總執(zhí)行時(shí)間與負(fù)載問(wèn)題得到了改善。為了更好地提高調(diào)度機(jī)制的綜合性能,下一步將研究具有關(guān)聯(lián)性的云任務(wù)調(diào)度與能耗優(yōu)化問(wèn)題。