秦 軍，董倩倩，郝天曙

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

基于蟻群模擬退火的云任務(wù)調(diào)度算法改進

秦 軍1，董倩倩2，郝天曙2

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

隨著云計算的快速發(fā)展，如何高效地進行云任務(wù)調(diào)度逐漸成為云計算研究的重點。任務(wù)調(diào)度問題屬于NP優(yōu)化問題，許多超啟發(fā)式算法被應(yīng)用到任務(wù)調(diào)度問題。針對蟻群算法在任務(wù)調(diào)度中存在收斂速度慢、局部搜索能力差和易于陷入局部最優(yōu)的問題，將蟻群算法和模擬退火算法相結(jié)合，提出了蟻群模擬退火算法，擬解決云計算中的任務(wù)調(diào)度問題。在該算法中，以減少任務(wù)的完成時間和保證資源負(fù)載均衡為目標(biāo)，根據(jù)蟻群算法構(gòu)造局部最優(yōu)解，利用模擬退火算法較強的局部搜索能力，將局部最優(yōu)解作為模擬退火算法的初始解進行局部搜索并以一定的概率接受當(dāng)前搜索結(jié)果，從而避免算法陷入局部最優(yōu)。仿真結(jié)果表明，蟻群模擬退火算法的性能優(yōu)于先來先服務(wù)(First Come First Served，F(xiàn)CFS)和標(biāo)準(zhǔn)蟻群優(yōu)化(Ant Colony Optimization,ACO)算法。

任務(wù)調(diào)度；云計算；蟻群算法；模擬退火算法

1 概 述

云計算[1]是分布式計算、并行計算和網(wǎng)格計算的商業(yè)發(fā)展。云計算通過互聯(lián)網(wǎng)實現(xiàn)計算設(shè)施、存儲設(shè)備、應(yīng)用程序等資源的共享，為不同的用戶提供計算、存儲等各種服務(wù)。在云計算環(huán)境中，用戶通過付費的方式使用云提供商提供的服務(wù)或基礎(chǔ)設(shè)施。根據(jù)用戶提交的作業(yè)請求，云計算調(diào)度中心為其分配資源。然而，如何進行高效的任務(wù)調(diào)度仍然是云計算系統(tǒng)所面臨的一個重大挑戰(zhàn)。

云計算采用Goolge公司提出的MapReduce[2]框架結(jié)構(gòu)。每一個單元是由一個獨立的Master節(jié)點和多個Worker節(jié)點組成[3]。Master節(jié)點負(fù)責(zé)調(diào)度所有的任務(wù)、監(jiān)控任務(wù)的執(zhí)行、重新運行失敗的任務(wù)以及處理異常。Worker節(jié)點只負(fù)責(zé)執(zhí)行Master節(jié)點分配的任務(wù)[4-5]。一旦接收到Master節(jié)點分配的任務(wù)，Worker節(jié)點首先要檢測自身剩余的計算資源，如果Worker節(jié)點的資源可以滿足用戶需求，那么將優(yōu)先分配該節(jié)點的資源。如果資源已經(jīng)無法滿足用戶需求，Master節(jié)點將會尋找其他合適的云計算資源。由此可見，任務(wù)調(diào)度策略的好壞直接影響任務(wù)執(zhí)行效率和資源利用率，云計算的任務(wù)調(diào)度模型如圖1所示。用戶將任務(wù)提交到用戶任務(wù)池中，任務(wù)分配節(jié)點根據(jù)Master節(jié)點分配的任務(wù)從任務(wù)池中取得相應(yīng)的任務(wù)，通過任務(wù)調(diào)度器將不同的任務(wù)分配到不同的虛擬機。

圖1 云計算任務(wù)調(diào)度模型

現(xiàn)有的啟發(fā)式任務(wù)調(diào)度算法中，蟻群最優(yōu)化算法[6]具有魯棒性、正反饋、分布式計算和易于結(jié)合其他算法等特點[7]。因此，蟻群最優(yōu)化算法的出現(xiàn)為各個領(lǐng)域解決復(fù)雜的組合問題提供了強大的工具。近年來，蟻群最優(yōu)化算法在組合優(yōu)化問題方面得到了持續(xù)發(fā)展，但是該算法依然存在易于停滯、早熟和易于陷入局部最優(yōu)的缺點[8]。鑒于此，文中提出將蟻群算法和模擬退火算法相結(jié)合的蟻群模擬退火算法(ACOSA)。該算法以減少任務(wù)完成的時間為目標(biāo)，同時考慮虛擬機資源的負(fù)載均衡[9-10]。

2 形式化描述

假設(shè)用戶所提交的任務(wù)是相互獨立、不可分割的；任務(wù)的執(zhí)行順序沒有先后之分；任務(wù)一旦開始執(zhí)行，除非出現(xiàn)虛擬機故障，在執(zhí)行過程中任務(wù)不能中斷。

定義1：任務(wù)集T={T1,T2,…,Tn}，表示當(dāng)前隊列有n個相互獨立的任務(wù)。任務(wù)Ti由四元組{TID,InputFileSize,TLength,OutputFileSize}表示。其中，TID表示任務(wù)編號；InputFileSize表示任務(wù)執(zhí)行前的長度；TLength表示提交到虛擬機的任務(wù)長度；OutputFileSize表示任務(wù)執(zhí)行完成后的長度。

定義2：虛擬機集V={VM1,VM2,…,VMm}，表示云計算數(shù)據(jù)中心當(dāng)前可用的m個虛擬機資源。虛擬機資源Vi由{VMID,PesNum,MIPS,Band,Size}五元組表示。其中，VMID表示虛擬機編號；PesNum表示虛擬機的CPU數(shù)量，文中規(guī)定每一虛擬機只有一個CPU；MIPS表示虛擬機CPU指令執(zhí)行速度；Band表示虛擬機所允許的最大帶寬；Size表示虛擬機的存儲大小。

3 基于模擬退火算法的蟻群算法

蟻群算法的基本原理是模擬自然界螞蟻覓食過程中在路徑上釋放信息素，后面的蟻群根據(jù)路徑上遺留信息素的濃度選擇下一路徑，遺留信息素的濃度越高，蟻群選擇該路徑的概率就越大，從而逐漸收斂于全局最優(yōu)解的過程[11-12]。單純的蟻群算法具有并行性、協(xié)同性和正反饋性等優(yōu)點，但是在求解任務(wù)調(diào)度這種復(fù)雜的NP問題時，該算法存在局部搜索能力差、易于陷入局部最優(yōu)解和收斂速度慢等問題[13]。

針對蟻群算法的缺點，文中提出ACOSA。該算法首先利用蟻群算法在當(dāng)前溫度下構(gòu)造一個局部最優(yōu)解，其次根據(jù)當(dāng)前局部最優(yōu)解，利用模擬退火算法較強的局部搜索能力[14-15]，構(gòu)造局部最優(yōu)解的一個鄰域，在此鄰域內(nèi)通過置換規(guī)則構(gòu)造一個新解，對此新解將按照一定的概率接受或拒絕，從而避免了蟻群算法陷入局部最優(yōu)解；最后利用信息素更新原則更新全局信息素和退火降溫，在新的溫度下構(gòu)造新的局部最優(yōu)解。

3.1 初始化參數(shù)

根據(jù)任務(wù)規(guī)模的大小設(shè)計合理的初始溫度T0，初始溫度要足夠高，否則算法將會收斂過快。初始化蟻群算法的相關(guān)參數(shù)，根據(jù)式(1)初始化蟻群算法中的虛擬機Vj的信息素。

(1)

其中，MIPSj表示虛擬機Vj的CPU指令執(zhí)行速度；Bandj表示虛擬機Vj允許的最大帶寬。

3.2 狀態(tài)遷移規(guī)則

為了虛擬機資源的負(fù)載均衡，ACOSA算法將虛擬機的負(fù)載均衡情況作為啟發(fā)函數(shù)。根據(jù)式(2)為下一任務(wù)Ti計算選擇虛擬機Vj的概率。

(2)

其中，τj(t)表示虛擬機Vj在t時刻的信息素濃度函數(shù)；ηj(t)表示Vj在t時刻的啟發(fā)函數(shù)；allowedk表示虛擬機集合{V1,V2,…,Vm}-tabuk；參數(shù)α,β分別表示信息素濃度和負(fù)載均衡情況的重要程度。

啟發(fā)函數(shù)的初始值ηj(0)為常數(shù)C，啟發(fā)函數(shù)根據(jù)式(3)計算：

(3)

其中,VMExeTimej表示截止到t時刻在虛擬機Vj上執(zhí)行任務(wù)的總時間；VMAverage表示根據(jù)上次迭代結(jié)束時，在當(dāng)前最優(yōu)解情況下每臺虛擬機平均運行的時間。

根據(jù)式(4)計算虛擬機Vj上任務(wù)運行的總時間。

(4)

其中，T_TotalLength表示在虛擬機j上運行的任務(wù)長度之和。

由于云計算資源池中的資源存在異構(gòu)性和動態(tài)性，有些虛擬機的性能優(yōu)于其他虛擬機。一旦某些虛擬機被分配大量的任務(wù)，將會影響任務(wù)集的完成時間。因此，在ACOSA算法中將虛擬機的負(fù)載平衡情況作為啟發(fā)函數(shù)來提高負(fù)載均衡能力。虛擬機j的啟發(fā)函數(shù)ηj(t)越大，則虛擬機j的綜合實力越強，被選擇的概率就越大。

3.3 信息素更新規(guī)則

根據(jù)抽樣穩(wěn)定原則，若滿足該原則，則根據(jù)式(5)進行信息素的更新。

τj(t+1)=(1-ρ)×τj(t)+Δτj(t)

(5)

其中，ρ表示信息素?fù)]發(fā)系數(shù)，ρ值越大，遺留信息素對當(dāng)前路徑選擇的影響越小；Δτj(t)的定義如下：

一個蟻群分配完所有任務(wù)后，更新所有訪問過的虛擬機上的局部信息素，根據(jù)式(6)計算Δτj(t)。

(6)

其中，TVMj表示第i次迭代時虛擬機j上的任務(wù)完成時間。

當(dāng)所有蟻群都完成任務(wù)分配時，根據(jù)式(7)進行全局信息素更新。

(7)

其中，TVMBestj表示在取得全局最優(yōu)解后，虛擬機j運行完成任務(wù)的時間。

3.4 Metropolis準(zhǔn)則

通過蟻群算法獲得局部最優(yōu)解，利用模擬退火算法的局部搜索能力，通過置換規(guī)則擾動當(dāng)前局部最優(yōu)解即隨機選擇兩個任務(wù)，如果兩個任務(wù)對應(yīng)的虛擬機不同，則進行虛擬機交換。如果交換后任務(wù)的完成時間減少，那么就接受新解，否則根據(jù)模擬退火的Metropolis準(zhǔn)則判斷是否接受新解。根據(jù)式(8)和式(9)得出接受新解的概率p，若p的值小于在當(dāng)前溫度T下產(chǎn)生的隨機值，則不接受新解，否則接受。

ΔTC=TCk-TClocal_best

(8)

(9)

其中，TCk表示在當(dāng)前溫度T下，交換虛擬機后所有任務(wù)運行的時間之和；TClocal_best表示在當(dāng)前溫度T下，蟻群算法取得虛擬機運行完成所有任務(wù)花費的最少時間；ΔTC表示在當(dāng)前溫度T下，交換任務(wù)后，虛擬機的運行時間減少的值；p表示當(dāng)ΔTC大于0時，接受新值的概率。

3.5 終止準(zhǔn)則

抽樣穩(wěn)定準(zhǔn)則對應(yīng)模擬退火過程中的抽樣過程，即在同一溫度下，經(jīng)過連續(xù)M次干擾局部最優(yōu)解均保持不變，則認(rèn)為滿足抽樣穩(wěn)定準(zhǔn)則；算法終止準(zhǔn)則對應(yīng)模擬退火過程中的退火過程，即當(dāng)前溫度T小于Tmin，則認(rèn)為滿足算法終止準(zhǔn)則，終止算法。

3.6 蟻群模擬退火算法的基本流程

步驟1：初始化參數(shù)。初始化T0，α,β,ρ,Q,M和Tmin；根據(jù)式(1)初始化信息素濃度。

步驟2：將蟻群隨機分布在虛擬機上，根據(jù)式(2)構(gòu)造候選解。

步驟3：按照所有任務(wù)完成時間最短的原則計算出局部最優(yōu)解，從而構(gòu)造局部最優(yōu)解的鄰域，根據(jù)式(5)和式(6)進行局部信息素更新。

步驟4：根據(jù)模擬退火算法的置換規(guī)則在鄰域內(nèi)構(gòu)造新解，由式(8)和式(9)判斷是否接受新解。

步驟5：判斷當(dāng)前溫度T下局部最優(yōu)值是否滿足抽樣穩(wěn)定準(zhǔn)則，滿足則轉(zhuǎn)步驟6，否則返回步驟4。

步驟6：根據(jù)式(5)和式(7)更新信息素。

步驟7：T(t+1)=cT(t)，c為一常數(shù)。判斷當(dāng)前溫度T(t+1)是否小于Tmin，若滿足算法終止準(zhǔn)則，則輸出最優(yōu)解，算法結(jié)束；否則返回步驟2。

4 仿真實驗與性能分析

文中將選擇CloudSim3.0進行仿真實驗。通過云計算仿真平臺對調(diào)度策略FCFS、標(biāo)準(zhǔn)蟻群算法(ACO)和ACOSA算法進行性能分析。

4.1 仿真參數(shù)設(shè)置

在CloudSim中設(shè)置5個數(shù)據(jù)中心，50個虛擬機資源和100～1 000個任務(wù)進行仿真實驗。提交到虛擬機上的任務(wù)長度為1 000-20 000MI(Million Instructions)。云仿真實驗中的其他參數(shù)設(shè)置見表1。標(biāo)準(zhǔn)蟻群算法和ACOSA算法的參數(shù)設(shè)置見表2。

表1 CloudSim參數(shù)設(shè)置

表2 ACO和ACOSA算法參數(shù)設(shè)置

4.2 實驗結(jié)果與分析

文中提出虛擬機負(fù)載不均衡值DI(Degree of Imbalance)對虛擬機負(fù)載均衡情況進行測量，計算如下：

(10)

(11)

其中，TotalLengthj表示提交到虛擬機j上的所有任務(wù)長度之和；MIPSj表示虛擬機j處理指令的能力；Tj表示虛擬機j完成分配任務(wù)的運行時間；Tmax、Tmin和Tavg分別表示虛擬機j運行時間的最大值、最小值和平均值。

ACOSA算法設(shè)計的目標(biāo)之一是改善負(fù)載不均的情況。文中以DI作為負(fù)載不均的參考值。

實驗中將ACOSA算法同先來先服務(wù)(FirstComeFirstServed，F(xiàn)CFS)和標(biāo)準(zhǔn)ACO算法進行對比分析。FCFS算法的目的是為每一任務(wù)找到最小完成時間。標(biāo)準(zhǔn)ACO算法以減少完成任務(wù)的時間為目標(biāo)。ACOSA算法根據(jù)任務(wù)大小和資源分配情況為任務(wù)選擇合適的資源，該算法不僅減少了任務(wù)的完成時間，同時改善了負(fù)載不均衡的情況。

為了驗證ACOSA算法的可行性和有效性，將收斂速度、任務(wù)完成時間和資源負(fù)載均衡作為評價各個算法性能的標(biāo)準(zhǔn)。

實驗1中，如圖2所示，設(shè)置500個任務(wù)比較算法ACOSA和ACO的收斂速度。

圖2 500個任務(wù)不同迭代次數(shù)的完成時間

圖2表明，隨著迭代次數(shù)的增加，算法ACO和ACOSA的任務(wù)完成時間逐漸減少，但是對算法ACO和ACOSA而言，迭代次數(shù)大于60后任務(wù)完成時間減少速度開始變慢，因此，文中將使用迭代次數(shù)60作為其他實驗的參考值。

實驗2中，比較了不同任務(wù)數(shù)量的完成時間。圖3為算法FCFS、ACO和ACOSA的任務(wù)完成時間。

圖3 各算法的不同任務(wù)集的完成時間

根據(jù)實驗結(jié)果可知，隨著任務(wù)數(shù)量的增加，ACOSA算法在任務(wù)調(diào)度中任務(wù)完成時間小于算法FCFS和ACO。

根據(jù)實驗2的結(jié)果，計算DI，結(jié)果見圖4。

圖4 各算法的DI值

從圖3和圖4可以看出，ACOSA算法的任務(wù)完成時間比算法FCFS和ACO分別減少了50%～60%和15%～20%，同時虛擬機的負(fù)載不均值也明顯降低。利用ACOSA算法進行云任務(wù)調(diào)度，可以有效降低任務(wù)的完成時間，同時實現(xiàn)虛擬機資源的負(fù)載均衡。通過以上對云計算調(diào)度任務(wù)算法的分析，ACOSA算法在收斂速度、任務(wù)完成時間和負(fù)載均衡方面具有更好的優(yōu)勢。圖4中任務(wù)數(shù)量較少時，ACOSA算法的DI值較高，這是因為性能好的虛擬機可能會執(zhí)行3～5個任務(wù)，性能差的虛擬機執(zhí)行0～2個任務(wù)，造成資源負(fù)載的不均衡，此處可以作為下一步改進的方向。

5 結(jié)束語

針對云計算中的任務(wù)調(diào)度問題，提出了一種基于蟻群優(yōu)化算法的蟻群模擬退火算法。該算法通過引入模擬退火算法提高蟻群算法的收斂速度、加強局部搜索能力和避免算法陷入局部最優(yōu)解，不僅將減少任務(wù)的完成時間作為目標(biāo)，而且綜合考慮了虛擬機的負(fù)載均衡情況并將降低虛擬機負(fù)載不均衡值作為算法的目標(biāo)。仿真結(jié)果表明，該算法在減少任務(wù)的完成時間和計算資源負(fù)載均衡等方面明顯優(yōu)于算法FCFS和ACO。

[1]JadejaY,ModiK.Cloudcomputing-concepts,architectureandchallenges[C]//Internationalconferenceoncomputing,electronicsandelectricaltechnologies.[s.l.]:IEEE,2012:877-880.

[2]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM,2008,51(1):107-113.

[3] 李建江,崔 健,王 聃,等.MapReduce并行編程模型研究綜述[J].電子學(xué)報,2011,39(11):2635-2642.

[4]StonebrakerM,AbadiD,DewittDJ,etal.MapReduceandparallelDBMSs:friendsorfoes?[J].CommunicationsoftheACM,2010,53(1):64-71.

[5] 徐 潔,朱健琛,魯 珂.基于雙適應(yīng)度遺傳退火的云任務(wù)調(diào)度算法[J].電子科技大學(xué)學(xué)報,2013,42(6):900-904.

[6]DorigoM,BirattariM,StutzleT.Antcolonyoptimization[J].IEEEComputationalIntelligenceMagazine,2006,1(4):28-39.

[7]LiuCY,ZouCM,WuP.Ataskschedulingalgorithmbasedongeneticalgorithmandantcolonyoptimizationincloudcomputing[C]//13thinternationalsymposiumondistributedcomputingandapplicationstobusiness,engineeringandscience.[s.l.]:IEEE,2014:68-72.

[8] 黃 翰,郝志峰,吳春國,等.蟻群算法的收斂速度分析[J].計算機學(xué)報,2007,30(8):1344-1353.

[9]ZhuJ,RuiT,FangH,etal.SimulatedannealingantcolonyalgorithmforQAP[C]//Eighthinternationalconferenceonnaturalcomputation.[s.l.]:IEEE,2012:789-793.

[10] 吳 斌,史忠植.一種基于蟻群算法的TSP問題分段求解算法[J].計算機學(xué)報,2001,24(12):1328-1333.

[11] 陳華根,吳健生,王家林,等.模擬退火算法機理研究[J].同濟大學(xué)學(xué)報:自然科學(xué)版,2004,32(6):802-805.

[12] 高 尚.蟻群算法理論、應(yīng)用及其與其它算法的混合[D].南京:南京理工大學(xué),2005.

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

[14] 高 鷹,謝勝利.基于模擬退火的粒子群優(yōu)化算法[J].計算機工程與應(yīng)用,2004,40(1):47-50.

[15] 張 暉,吳 斌,余張國.引入模擬退火機制的新型遺傳算法[J].電子科技大學(xué)學(xué)報,2003,32(1):39-42.

Improvement of Algorithm for Cloud Task Scheduling Based on Ant Colony Optimization and Simulated Annealing

QIN Jun1,DONG Qian-qian2,HAO Tian-shu2

(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)

With the rapid development of cloud computing,how to carry on task scheduling effectively is crucial in the research of cloud computing.Cloud task scheduling belongs to a NP-hard optimization problem,and many meta-heuristic algorithms have been proposed to solve it.ACO algorithm in task scheduling still has many shortcomings such as slow convergence speed,poor ability of local search and falling into local optimum easily.Therefore,a new algorithm-ACOSA is presented to solve task scheduling problem.In this algorithm,reducing task completion time and ensuring resource’s load balance as the goal,according to the local ant colony algorithm the optimal solution is constructed,and the strong local search capability of simulated annealing algorithm is applied to make the local optimal solutions as the initial solutions of simulated annealing algorithm and accept the results of current search to a certain probability in order to avoid falling into the local optimal.Simulation results show that ACOSA is superior to First Come First Served (FCFS) and Ant Colony Optimization (ACO) by reducing make span and achieving load balance.

task scheduling;cloud computing;ACO;Simulated Annealing

2016-04-27

2016-08-10

時間：2017-02-17

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

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

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1632.068.html

TP301.6

A

1673-629X(2017)03-0117-05

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