一種面向綠色云計算的任務調度算法

秦 軍，孫 蒙，馮亮亮

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

一種面向綠色云計算的任務調度算法

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

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

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

綠色云計算；節能；任務調度；GCA

0 引 言

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

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

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

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

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

1 算法實現

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

1.1 遺傳算法的相關設定

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

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

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

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

Step1：創建一個數組int chromosome[n]，存儲編碼后的染色體；

Step2：for(i=0;i

Step3：for(j=0;j

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

Step5：chromosome[i]=j，將任務i分配給計算節點j；

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

如有任務數n=7，計算節點數m=4的云計算任務調度，現隨機生成一個任務分配矩陣G，如下：

(1)

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

(2)適應度函數。

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

融合算法的任務調度目標是降低能耗，即考慮任務的執行時間和執行費用。為了在縮短任務完成時間的同時降低計算節點的能源消耗，因此，將第k個染色體的適應度函數定義為：

(2)

(3)遺傳操作。

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

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

(3)

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

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

交叉概率函數為：

(4)

變異概率函數為：

(5)

其中，取k1=0.4，k2=0.06，k3=1，k4=0.2；f為變異個體的適應度值；faverage為種群平均適應度值；fmax為種群中個體的最大適應值；f'為交叉個體中較大的適應度值。

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

1.2 加入蟻群優化算法的GA

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

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

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

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

(1)信息素初始化。

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

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

(6)

其中，τCj表示計算節點j固有的最大處理能力；τTj(0)表示根據GA獲得的最優解轉換成的信息素值，反映了節點j的能耗狀態。

(2)轉移概率。

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

(7)

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

(3)信息素更新。

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

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

(8)

(9)

其中，S為常數；Lj表示計算節點j的實時負載。

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

1.3 遺傳-ACO的任務調度

GCA的任務調度步驟如下:

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

Step2：根據待調度任務的規模進行染色體間接編碼，定義適應度函數，隨機生成初始種群；

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

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

Step5：計算交叉概率Pc、變異概率Pm，對選出的較優個體進行交叉、變異操作，經過選擇、交叉、變異操作后產生下一代群體；

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

Step7：根據GA的終止條件進行判定，若滿足則執行Step8，否則跳轉至Step4；

Step8：將GA得到的擁有最大適應度染色體作為最優解集轉化為ACO的初始信息素；

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

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

Step12：更新被選擇節點上的信息素；

Step13：判斷ACO是否滿足終止條件，若滿足，輸出任務調度方案結果，否則跳轉步驟Step11。

2 仿真結果

采用云計算仿真軟件CloudSim進行仿真實驗，用于模擬云環境下的任務調度和資源分配。

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

表1 算法的主要參數

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

三種算法不同任務數執行時間對比見圖2。

從圖2可以看出，在仿真初期，任務量較少，數目為30～90的范圍內各算法的執行時間相差不大。隨著任務數量的增加，任務數大于90的時候，GCA的調度優勢明顯體現出來。這是因為在算法后期轉化為ACO，加快了算法的收斂速度，GCA的執行時間明顯少于GA和ACO。仿真結果證明了GCA可以有效減少調度任務的執行時間。

不同任務數能源消耗對比見圖3。

圖2 不同任務數執行時間對比

圖3 不同任務數的能源消耗對比

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

3 結束語

為了降低云計算系統的能耗，實現能耗優化的綠色云計算，提出了一種基于GA和ACO動態融合的任務調度算法。該算法利用遺傳算法全局搜索能力和蟻群算法的信息交流和正反饋機制尋找任務調度問題的最優解。將云計算運行時間和總能耗作為評判標準，將該算法與GA和ACO進行了對比仿真分析。結果表明，該算法能夠實現云計算總能耗的優化控制。

[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] 王永貴,張 偉,韓瑞蓮.云環境下綠色任務調度策略[J].計算機工程與應用,2012,48(34):81-87.

[6] 李建峰,彭 艦.云計算環境下基于改進遺傳算法的任務調度算法[J].計算機應用,2011,31(1):184-186.

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

[8] 劉萬軍，張孟華，郭文越.基于MPSO算法的云計算資源調度策略[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] 王小平,曹立明.遺傳算法:理論、應用及軟件實現[M].西安:西安交通大學出版社,2002:34-70.

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

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

[13] 劉 永,王新華,邢長明,等.云計算環境下基于蟻群優化算法的資源調度策略[J].計算機技術與發展,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 網絡出版時間：2017-06-05

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

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

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