基于蟻群模擬退火的云任務調度算法改進

秦 軍，董倩倩，郝天曙

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

基于蟻群模擬退火的云任務調度算法改進

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

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

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

任務調度；云計算；蟻群算法；模擬退火算法

1 概 述

云計算[1]是分布式計算、并行計算和網格計算的商業發展。云計算通過互聯網實現計算設施、存儲設備、應用程序等資源的共享，為不同的用戶提供計算、存儲等各種服務。在云計算環境中，用戶通過付費的方式使用云提供商提供的服務或基礎設施。根據用戶提交的作業請求，云計算調度中心為其分配資源。然而，如何進行高效的任務調度仍然是云計算系統所面臨的一個重大挑戰。

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

圖1 云計算任務調度模型

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

2 形式化描述

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

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

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

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

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

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

3.1 初始化參數

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

(1)

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

3.2 狀態遷移規則

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

(2)

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

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

(3)

其中,VMExeTimej表示截止到t時刻在虛擬機Vj上執行任務的總時間；VMAverage表示根據上次迭代結束時，在當前最優解情況下每臺虛擬機平均運行的時間。

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

(4)

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

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

3.3 信息素更新規則

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

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

(5)

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

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

(6)

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

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

(7)

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

3.4 Metropolis準則

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

ΔTC=TCk-TClocal_best

(8)

(9)

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

3.5 終止準則

抽樣穩定準則對應模擬退火過程中的抽樣過程，即在同一溫度下，經過連續M次干擾局部最優解均保持不變，則認為滿足抽樣穩定準則；算法終止準則對應模擬退火過程中的退火過程，即當前溫度T小于Tmin，則認為滿足算法終止準則，終止算法。

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

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

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

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

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

步驟5：判斷當前溫度T下局部最優值是否滿足抽樣穩定準則，滿足則轉步驟6，否則返回步驟4。

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

步驟7：T(t+1)=cT(t)，c為一常數。判斷當前溫度T(t+1)是否小于Tmin，若滿足算法終止準則，則輸出最優解，算法結束；否則返回步驟2。

4 仿真實驗與性能分析

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

4.1 仿真參數設置

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

表1 CloudSim參數設置

表2 ACO和ACOSA算法參數設置

4.2 實驗結果與分析

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

(10)

(11)

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

ACOSA算法設計的目標之一是改善負載不均的情況。文中以DI作為負載不均的參考值。

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

為了驗證ACOSA算法的可行性和有效性，將收斂速度、任務完成時間和資源負載均衡作為評價各個算法性能的標準。

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

圖2 500個任務不同迭代次數的完成時間

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

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

圖3 各算法的不同任務集的完成時間

根據實驗結果可知，隨著任務數量的增加，ACOSA算法在任務調度中任務完成時間小于算法FCFS和ACO。

根據實驗2的結果，計算DI，結果見圖4。

圖4 各算法的DI值

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

5 結束語

針對云計算中的任務調度問題，提出了一種基于蟻群優化算法的蟻群模擬退火算法。該算法通過引入模擬退火算法提高蟻群算法的收斂速度、加強局部搜索能力和避免算法陷入局部最優解，不僅將減少任務的完成時間作為目標，而且綜合考慮了虛擬機的負載均衡情況并將降低虛擬機負載不均衡值作為算法的目標。仿真結果表明，該算法在減少任務的完成時間和計算資源負載均衡等方面明顯優于算法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].電子學報,2011,39(11):2635-2642.

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

[5] 徐 潔,朱健琛,魯 珂.基于雙適應度遺傳退火的云任務調度算法[J].電子科技大學學報,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].計算機學報,2007,30(8):1344-1353.

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

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

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

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

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

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

[15] 張 暉,吳 斌,余張國.引入模擬退火機制的新型遺傳算法[J].電子科技大學學報,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

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

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

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