秦 軍，孫 蒙，馮亮亮

(1.南京郵電大學 教育科學與技術(shù)學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210003)

一種面向綠色云計算的任務(wù)調(diào)度算法

秦 軍1，孫 蒙2，馮亮亮2

(1.南京郵電大學 教育科學與技術(shù)學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210003)

任務(wù)調(diào)度時的服務(wù)器能耗是云計算系統(tǒng)動態(tài)能耗的重要組成部分。目前云計算帶來的巨大能耗已經(jīng)成為制約云計算發(fā)展的技術(shù)瓶頸，因此節(jié)約能源和提高能源利用率是實現(xiàn)綠色云計算系統(tǒng)的重要基礎(chǔ)。為實現(xiàn)減少能耗和縮短任務(wù)執(zhí)行時間的綠色云計算目標，將遺傳算法和蟻群算法相結(jié)合，提出了一種動態(tài)融合的任務(wù)調(diào)度算法。該算法利用遺傳算法全局搜索查找能力強的優(yōu)點尋找任務(wù)調(diào)度的較優(yōu)解，并將該較優(yōu)解轉(zhuǎn)化為蟻群的初始信息素值，再通過蟻群算法的蟻群信息交流和正反饋機制尋找任務(wù)調(diào)度問題的最優(yōu)解，以有效降低云計算數(shù)據(jù)中心和計算中心的能耗。仿真實驗結(jié)果表明，所提出的任務(wù)調(diào)度算法顯著降低了云計算系統(tǒng)計算的運行時間和總能耗。

綠色云計算；節(jié)能；任務(wù)調(diào)度；GCA

0 引 言

當今,人們的環(huán)保意識達到了空前高度，新能源、減排、綠色經(jīng)濟這些話題的熱度越來越高。2007年，綠色網(wǎng)格組織(Green Grid)[1]成立，目標是要降低數(shù)據(jù)中心和商業(yè)計算系統(tǒng)的能耗。此外，標準性能評估組織(Standard Performance Evaluation Corporation，SPEC)、事務(wù)處理性能委員會(The Transaction Processing Performance Council，TPC)等國際性能評估標準化組織也都在致力于能耗標準化評價和優(yōu)化問題。隨著云計算規(guī)模越來越大，它對能源與環(huán)境的影響已越來越突出，其本身的能耗越來越不可忽視，能耗問題已成為云計算發(fā)展道路上必須要跨過的障礙[2]。托尼·馬斯泰利奇在《云計算 節(jié)能之路》中提到，目前云計算的耗電量已經(jīng)超過全球總耗電量的1%。云計算服務(wù)商建設(shè)數(shù)據(jù)中心，通常，一個占地500平方米的數(shù)據(jù)中心每天消耗的電量就高達38 000度。在2014年，只有8.5%的數(shù)據(jù)中心負責人預(yù)計在2015年后數(shù)據(jù)中心的容量仍然夠用，到2020年，預(yù)計數(shù)據(jù)中心的建設(shè)規(guī)模幾乎將是目前的兩倍，使得云計算的能耗、對環(huán)境的影響等問題更為突出。

從上述數(shù)字可以看出，為云計算設(shè)計高能效的解決方案已經(jīng)迫在眉睫。綠色云計算主要考慮影響生態(tài)環(huán)境的相關(guān)影響因素，近年來綠色云計算已得到研究者的眾多關(guān)注。文獻[3]提出了云計算技術(shù)中的綠色節(jié)能模式。文獻[4]提出了如何利用虛擬化來降低能耗，通過虛擬化實現(xiàn)綠色云計算。文獻[5]對STF-OS、LTF-OS和RT-OS三種綠色任務(wù)調(diào)度算法進行了相關(guān)的理論分析，并驗證了其能有效地減少能源消耗。

在云環(huán)境下，任務(wù)調(diào)度屬于NP完全問題，啟發(fā)式智能算法普遍被認為是解決NP完全問題的較優(yōu)算法，可以有效得到最優(yōu)解，其搜索過程較復雜，但是有良好的尋優(yōu)性能，相比傳統(tǒng)算法有著不可比擬的優(yōu)越性。啟發(fā)式智能算法已被一些學者運用到解決云計算任務(wù)調(diào)度問題，目前應(yīng)用比較成熟的有基于遺傳算法(Genetic Algorithm，GA)、蟻群算法(Ant Colony Optimization，ACO)、粒子群算法(Particle Swarm Optimization，PSO)等資源調(diào)度策略。文獻[6]提出了一種基于GA的云計算任務(wù)調(diào)度策略，以減少任務(wù)的最大完成時間。文獻[7]提出了一種基于ACO的云計算任務(wù)調(diào)度算法，該算法綜合考慮了計算節(jié)點的性能屬性和該節(jié)點在負載壓力下的任務(wù)響應(yīng)能力。文獻[8]針對云計算服務(wù)集群資源調(diào)度和負載平衡的優(yōu)化問題,提出一種基于改進的粒子群優(yōu)化算法的云計算資源調(diào)度策略。

然而每一種算法都有自身的局限性，GA在查找最優(yōu)解的過程中，雖然具有較強的全局搜索能力，但對解空間的局部搜索能力較弱，容易陷入局部最優(yōu)；且算法的變異操作基本是隨機性的，同時在子代個體的進化過程中，缺乏對求解問題的啟發(fā)信息的利用，因此算法的進化率較低，后期收斂速度較慢。而ACO作為分布式啟發(fā)搜索算法，能夠利用蟻群特有的信息素正反饋機制，通過蟻群的整體協(xié)作，找到問題的最優(yōu)解；但ACO在尋優(yōu)的初期由于缺乏信息素，蟻群中螞蟻的路徑搜索會有很大的隨機性，導致算法的效率較低。粒子群算法搜索速度快，效率高，但容易陷入局部最優(yōu)。近年來許多學者根據(jù)啟發(fā)式智能算法加以改進，在解決云計算任務(wù)調(diào)度問題時，取得了較好的效果。

為此，結(jié)合GA的全局尋優(yōu)能力和ACO的局部尋優(yōu)能力，提出了一種基于GA和ACO的云計算任務(wù)調(diào)度算法(Genetic and ant Colony Algorithm，GCA)，以加快收斂速度，縮短任務(wù)執(zhí)行時間，有效提高任務(wù)調(diào)度效率，從而降低云計算平臺中數(shù)據(jù)中心和計算中心的能源消耗，實現(xiàn)綠色云計算。

1 算法實現(xiàn)

該算法的基本思想是結(jié)合GA的全局尋優(yōu)能力和ACO的局部尋優(yōu)能力，利用GA較強的全局搜索能力，快速生成云任務(wù)調(diào)度問題的較優(yōu)解，并作為ACO的初始化信息素分布，在算法后期主要是利用ACO的局部搜索能力，正反饋、分布式、求解效率高等特性。

1.1 遺傳算法的相關(guān)設(shè)定

(1)染色體編碼和初始種群的生成。

GA是從問題的解空間開始的，在解決實際問題時，種群中的每個個體都使用染色體進行編碼，也就是先需要將所有可能存在的任務(wù)調(diào)度方案進行染色體編碼，用來表示個體和問題的解之間的映射關(guān)系，即一條染色體就表示該算法的一個可行解，算法目標就是找到可行解中的最優(yōu)解，來實現(xiàn)任務(wù)與資源的匹配。染色體的編碼方式有多種，如直接編碼、間接編碼和混合編碼[9-10]。

在解決云計算調(diào)度問題時，根據(jù)任務(wù)調(diào)度的特點，可以直接對任務(wù)的執(zhí)行狀態(tài)編碼，也可以采用間接編碼。為此，結(jié)合云計算任務(wù)調(diào)度特點，采用節(jié)點任務(wù)的間接編碼方式，即對每個任務(wù)分配到的計算節(jié)點進行編碼。染色體的長度n為正在進行調(diào)度的任務(wù)數(shù)量。例如染色體{f1,f2,…,fn}，其中fi表示第i個任務(wù)分配到的節(jié)點。

染色體編碼的操作步驟如下：

Step1：創(chuàng)建一個數(shù)組int chromosome[n]，存儲編碼后的染色體；

Step2：for(i=0;i

Step3：for(j=0;j

Step4：if(G[i][j]=1)，判斷矩陣G中的元素是否為1，如果為1，執(zhí)行Step5；

Step5：chromosome[i]=j，將任務(wù)i分配給計算節(jié)點j；

Step6：return chromosome[n]，返回編碼后的染色體。

如有任務(wù)數(shù)n=7，計算節(jié)點數(shù)m=4的云計算任務(wù)調(diào)度，現(xiàn)隨機生成一個任務(wù)分配矩陣G，如下：

(1)

采用上述編碼算法進行染色體編碼，獲得一條染色體:Chromosome[7] =(4,2,1,3,1,4,2)，即7個任務(wù)對應(yīng)的計算節(jié)點號分別為4,2,1,3,1,4,2。

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

GA在進化搜索的過程中，不善于利用外部啟發(fā)信息，僅僅以適應(yīng)度函數(shù)為依據(jù)。GA中的適應(yīng)度函數(shù)是衡量GA尋找最優(yōu)解的約束條件，適應(yīng)度函數(shù)的設(shè)計決定著遺傳算法的搜索性能。

融合算法的任務(wù)調(diào)度目標是降低能耗，即考慮任務(wù)的執(zhí)行時間和執(zhí)行費用。為了在縮短任務(wù)完成時間的同時降低計算節(jié)點的能源消耗，因此，將第k個染色體的適應(yīng)度函數(shù)定義為：

(2)

(3)遺傳操作。

遺傳操作主要包括選擇操作、交叉和變異操作。

選擇操作：目的是為了使優(yōu)良的染色體個體以較高的概率遺傳到下一代，體現(xiàn)了自然世界中適者生存的進化理論。它是GA中一個很重要的步驟，通過對個體的適應(yīng)性評價，計算種群中每個個體的選擇概率，如式(3)：

(3)

其中，f(k)為個體k的適應(yīng)度值；q為種群數(shù)量。

交叉和變異操作：在GA的迭代過程中，交叉操作負責染色體對之間的基因交叉或基因重組，具體操作是從兩個父代染色體中選取部分基因片段，將這部分基因片段進行替換重組，生成一對新的子代染色體，模擬了自然界中有性繁殖的基因重組現(xiàn)象。將父代的優(yōu)良基因遺傳到下一代個體，交叉操作決定了全局搜索能力。變異操作僅對種群個體中少量染色體進行操作，拓展新的搜索空間，決定了局部搜索能力。變異操作保持了種群的個體多樣性，防止算法陷入局部收斂。交叉和變異操作都是采用文獻[6]中提出的自適應(yīng)方式。

交叉概率函數(shù)為：

(4)

變異概率函數(shù)為：

(5)

其中，取k1=0.4，k2=0.06，k3=1，k4=0.2；f為變異個體的適應(yīng)度值；faverage為種群平均適應(yīng)度值；fmax為種群中個體的最大適應(yīng)值；f'為交叉?zhèn)€體中較大的適應(yīng)度值。

GA在進化后期求解效率不高，并且容易陷入局部最優(yōu)，因此選擇合適的時機進行GA到ACO的過渡，可以解決此問題。

1.2 加入蟻群優(yōu)化算法的GA

執(zhí)行上述GA，最終可以獲得問題的最優(yōu)解或近似最優(yōu)解。但是一般情況下，需要根據(jù)不同的問題迭代幾百次甚至上千次。為了減少算法的執(zhí)行時間，加快算法的收斂速度，采取GA與ACO相融合的方式。GA與ACO的進化率伴隨時間變化趨勢見圖1。

圖1 遺傳算法與ACO的進化率-時間圖

從圖1可看出，在初始時間段t0～ta，GA保持較高的進化率，在tb之后，由于不能有效利用啟發(fā)信息，個體進化率開始大幅下降；相反，ACO在時間段t0～ta由于信息素的缺乏，保持較低的進化率，在tb之后，隨著信息素濃度的提高，進化率開始大幅提升。

因此，在ta點將GA切換到ACO是最優(yōu)方案，能夠顯著提高算法性能。具體操作方法：在t0～ta，利用GA對任務(wù)調(diào)度問題進行求解，選取種群中適應(yīng)度值高的個體組成優(yōu)化解作為ACO的初始信息素[11]，解決ACO對初始信息素的依賴問題，然后利用ACO的正反饋機制對較優(yōu)解做進一步優(yōu)化，最后搜索找到調(diào)度問題的最優(yōu)解。

(1)信息素初始化。

GA迭代結(jié)束時，以一定概率選取任務(wù)調(diào)度問題較優(yōu)解轉(zhuǎn)化為ACO的初始信息素。這里將GA求得的最優(yōu)解的前10%個體作為遺傳優(yōu)化算法的解合集T，各計算節(jié)點的初始信息素值為τj：

τj(0)=τCj-τTj(0)

(6)

其中，τCj表示計算節(jié)點j固有的最大處理能力；τTj(0)表示根據(jù)GA獲得的最優(yōu)解轉(zhuǎn)換成的信息素值，反映了節(jié)點j的能耗狀態(tài)。

(2)轉(zhuǎn)移概率。

信息素初始化后，執(zhí)行ACO，螞蟻根據(jù)GA轉(zhuǎn)化來的信息素分布開始搜索，以一定概率p進行下一跳路徑選擇(即在任務(wù)調(diào)度時將任務(wù)分配到下一個資源節(jié)點)。t時刻任務(wù)i調(diào)度到計算節(jié)點j的概率為：

(7)

其中，τ(t,vj)表示時刻t計算節(jié)點vj上關(guān)于待執(zhí)行任務(wù)i的信息素濃度值；η(vj)表示計算節(jié)點vj的處理能力；α表示信息素的重要程度；β表示計算節(jié)點處理能力的重要程度。

(3)信息素更新。

為了防止陷入局部最優(yōu)，需要對螞蟻所選的線路進行局部信息素更新，以保證每輪搜索中的最優(yōu)方案都在信息素的分布中有所體現(xiàn)，這種反饋方式可以加快ACO的收斂速度[12-13]。隨著任務(wù)的執(zhí)行，將計算節(jié)點的信息素濃度根據(jù)任務(wù)的執(zhí)行情況進行更新，見式(8)：

τ(t1,vj)=ρτ(t,vj)+Δτ(t,vj)

(8)

(9)

其中，S為常數(shù)；Lj表示計算節(jié)點j的實時負載。

ACO的終止條件是設(shè)置最大搜索步數(shù)或當進化進入停滯時算法結(jié)束。另外，在GCA算法中，設(shè)定了禁忌表，已搜索過的節(jié)點加入禁忌表，可以防止搜索陷入局部收斂。

1.3 遺傳-ACO的任務(wù)調(diào)度

GCA的任務(wù)調(diào)度步驟如下:

Step1：根據(jù)用戶提交的作業(yè)，進行初始值設(shè)置，根據(jù)作業(yè)的一些特征設(shè)置GA的相關(guān)參數(shù)：種群大小、交叉概率、變異概率、最小迭代次數(shù)和最大迭代次數(shù)；

Step2：根據(jù)待調(diào)度任務(wù)的規(guī)模進行染色體間接編碼，定義適應(yīng)度函數(shù)，隨機生成初始種群；

Step3：對種群個體進行解碼，然后準備進行遺傳性操作；

Step4：計算個體的適應(yīng)度值，根據(jù)個體適應(yīng)度值進行選擇操作，選擇適應(yīng)度值高的個體進入下一步遺傳操作；

Step5：計算交叉概率Pc、變異概率Pm，對選出的較優(yōu)個體進行交叉、變異操作，經(jīng)過選擇、交叉、變異操作后產(chǎn)生下一代群體；

Step6：比較新個體與父代個體，根據(jù)替換的原則進行優(yōu)劣替換，選擇優(yōu)良的個體作為最終子代個體；

Step7：根據(jù)GA的終止條件進行判定，若滿足則執(zhí)行Step8，否則跳轉(zhuǎn)至Step4；

Step8：將GA得到的擁有最大適應(yīng)度染色體作為最優(yōu)解集轉(zhuǎn)化為ACO的初始信息素；

Step9：將GA得到的最優(yōu)解的前10%轉(zhuǎn)換成ACO的初始信息素，并將螞蟻隨機分布于待分配資源節(jié)點上，進入ACO；

Step11：蟻群中的螞蟻根據(jù)式(7)選擇下一個任務(wù)的可分配節(jié)點，同時將當前節(jié)點加入禁忌表；

Step12：更新被選擇節(jié)點上的信息素；

Step13：判斷ACO是否滿足終止條件，若滿足，輸出任務(wù)調(diào)度方案結(jié)果，否則跳轉(zhuǎn)步驟Step11。

2 仿真結(jié)果

采用云計算仿真軟件CloudSim進行仿真實驗，用于模擬云環(huán)境下的任務(wù)調(diào)度和資源分配。

通過將提出算法與GA、ACO進行比較，驗證該算法的性能。初始參數(shù)的設(shè)置見表1。

表1 算法的主要參數(shù)

在模擬云計算實驗中，為了檢驗GCA能耗優(yōu)化的性能，從算法的任務(wù)調(diào)度時間和能耗方面與GA、ACO進行數(shù)據(jù)對比分析。采取執(zhí)行任務(wù)數(shù)量200個，應(yīng)用三種算法分別進行10次調(diào)度，然后將10次結(jié)果取平均值，采用任務(wù)數(shù)量為30、50、70、90、110、130、150、170、190的平均數(shù)據(jù)，然后進行數(shù)據(jù)對比分析。GCA的參數(shù)和表1保持一致。

三種算法不同任務(wù)數(shù)執(zhí)行時間對比見圖2。

從圖2可以看出，在仿真初期，任務(wù)量較少，數(shù)目為30～90的范圍內(nèi)各算法的執(zhí)行時間相差不大。隨著任務(wù)數(shù)量的增加，任務(wù)數(shù)大于90的時候，GCA的調(diào)度優(yōu)勢明顯體現(xiàn)出來。這是因為在算法后期轉(zhuǎn)化為ACO，加快了算法的收斂速度，GCA的執(zhí)行時間明顯少于GA和ACO。仿真結(jié)果證明了GCA可以有效減少調(diào)度任務(wù)的執(zhí)行時間。

不同任務(wù)數(shù)能源消耗對比見圖3。

圖2 不同任務(wù)數(shù)執(zhí)行時間對比

圖3 不同任務(wù)數(shù)的能源消耗對比

從圖3可以看出，在相同任務(wù)數(shù)的情況下，GCA的能源消耗遠低于GA和ACO，在任務(wù)數(shù)目少于70時，GCA在能耗方面的優(yōu)勢表現(xiàn)不明顯，隨著任務(wù)數(shù)增加，可以明顯看到能耗優(yōu)化的效果。這是因為算法后期加入的ACO進行路徑更新，避免了任務(wù)調(diào)度集中于不理想的資源上，增加了能耗。

3 結(jié)束語

為了降低云計算系統(tǒng)的能耗，實現(xiàn)能耗優(yōu)化的綠色云計算，提出了一種基于GA和ACO動態(tài)融合的任務(wù)調(diào)度算法。該算法利用遺傳算法全局搜索能力和蟻群算法的信息交流和正反饋機制尋找任務(wù)調(diào)度問題的最優(yōu)解。將云計算運行時間和總能耗作為評判標準，將該算法與GA和ACO進行了對比仿真分析。結(jié)果表明，該算法能夠?qū)崿F(xiàn)云計算總能耗的優(yōu)化控制。

[1] The Green Grid Consortium[EB/OL].[2011-08-01].http：//www.thegreengrid.org.

[2] Wang L,von Laszewski G,Dayal J,et al.Towards energy aware scheduling for precedence constrained parallel tasks in a cluster with DVFS[C]//10th IEEE/ACM international conference on cluster,cloud and grid computing.[s.l.]:IEEE,2010:368-377.

[3] Kaur M, Singh P. Energy efficient green cloud:underlying structure[C]//2013 international conference on energy efficient technologies for sustainability.[s.l.]:[s.n.],2013：207-212.

[4] 趙肄江,胡 蓉.基于虛擬化的綠色云計算[J].湖南科技大學學報:自然科學版,2010,25(4):86-89.

[5] 王永貴,張 偉,韓瑞蓮.云環(huán)境下綠色任務(wù)調(diào)度策略[J].計算機工程與應(yīng)用,2012,48(34):81-87.

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

[7] 華夏渝,鄭 駿,胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學學報:自然科學版,2010(1):127-134.

[8] 劉萬軍，張孟華，郭文越.基于MPSO算法的云計算資源調(diào)度策略[J].計算機工程,2011,37(11):43-44.

[9] Madivi R,Kamath S.An hybrid bio-inspired task scheduling algorithm in cloud environment[C]//International conference on computing,communication and networking technologies.[s.l.]:IEEE,2014:1-7.

[10] 王小平,曹立明.遺傳算法:理論、應(yīng)用及軟件實現(xiàn)[M].西安:西安交通大學出版社,2002:34-70.

[11] 何雪海,胡小兵,趙吉東,等.基于自適應(yīng)轉(zhuǎn)移概率的蟻群優(yōu)化算法[J].計算機工程,2010,36(23):165-167.

[12] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學出版社,2005.

[13] 劉 永,王新華,邢長明,等.云計算環(huán)境下基于蟻群優(yōu)化算法的資源調(diào)度策略[J].計算機技術(shù)與發(fā)展,2011,21(9):19-23.

A Task Scheduling Algorithm for Green Cloud Computing

QIN Jun1,SUN Meng2,FENG Liang-liang2

(1.College of Education Science & Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The energy generated by the server during the scheduling system is an important part of the dynamic energy consumption of the cloud computing system and the huge energy consumption of the cloud computing has become the technical bottleneck which restricts the development of cloud computing.Therefore,saving energy and improving energy efficiency is an important foundation to achieve green cloud computing system.To achieve the goal of reducing energy consumption and shortening the task execution time of the green cloud computing,an energy-efficient scheduling algorithm based on genetic algorithm and ant colony algorithm has been proposed,which takes advantage of the strong global search ability of genetic algorithm to find the optimal solution of the scheduling problem,then converts it to the initial pheromone of ant colony optimization algorithm.After information communication and positive feedback,the global optimal solution of the task scheduling problem has been found out to effectively reduce the energy consumption in cloud computing center and calculating center.Simulation results show that the proposed algorithm has significantly reduced the task execution time and the total energy consumption.

green cloud computing;energy saving;task scheduling;GCA

2016-07-20

2016-10-27 網(wǎng)絡(luò)出版時間：2017-06-05

江蘇省自然科學基金項目(BK20130882)

秦 軍(1955-)，女，教授，研究方向為計算機網(wǎng)絡(luò)技術(shù)、多媒體技術(shù)、數(shù)據(jù)庫技術(shù)；孫 蒙(1990-)，女，碩士研究生，研究方向為分布式計算機技術(shù)與應(yīng)用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170605.1505.002.html

TP301.6

A

1673-629X(2017)08-0092-05

10.3969/j.issn.1673-629X.2017.08.019