ACOCS：一種云環(huán)境下資源調度混合算法*

黎煌達,程良倫

(廣東工業(yè)大學計算機學院,廣東 廣州 510006)

摘要：蟻群算法在優(yōu)化組合問題中有著重要的意義，傳統(tǒng)的蟻群調度算法搜索速度慢、容易陷入局部最優(yōu)。針對這種情況，結合布谷鳥搜索算法，提出一種基于蟻群算法與布谷鳥搜索算法的混合算法(ACOCS)，用于云環(huán)境下的資源調度。該方法有效保留了蟻群算法求解精度高和魯棒性的特性，并融入了布谷鳥搜索具有快速全局搜索能力的優(yōu)勢。仿真實驗結果表明，提出的ACOCS調度算法有效減少了調度所需的響應時間，也在一定程度上提高了系統(tǒng)資源利用率。

關鍵詞：調度；蟻群算法；布谷鳥搜索

中圖分類號：TP301.6 文獻標志碼：A

doi:10.3969/j.issn.1007-130X.2015.06.003

收稿日期：*2014-04-25;修回日期：2014-06-11

基金項目：國家自然科學基金重點資助項目(U2012A002D01)通信地址：510006 廣東省廣州市廣東工業(yè)大學計算機學院

作者簡介:

Address:Faculty of Computer,Guangdong University of Technology,Guangzhou 510006,Guangdong,P.R.China

ACOCS:A hybrid resource scheduling algorithm in cloud environment

LI Huang-da,CHENG Liang-lun

(Faculty of Computer,Guangdong University of Technology,Guangzhou 510006,China)

Abstract:The ant colony algorithm has great significance in solving composition optimization problems. However, the traditional ant colony scheduling algorithm has some drawbacks such as slow searching speed and easy to fall into local optimum. In view of this situation, combining the ant colony algorithm with the cuckoo search algorithm, we propose a hybrid algorithm (ACOCS) for resource scheduling in cloud environment. This method not only effectively preserves the high accuracy and robustness of the ant colony algorithm , but also integrates the rapid global search capability feature of the cuckoo search algorithm . Simulation results show that the proposed ACOCS scheduling strategy is better than the ant colony algorithm. It not only reduces the response time required for effective scheduling, but also improves the system resource utilization to some extent.

Key words:scheduling;ant colony algorithm;cuckoo search

1引言

云計算是當下一個非常熱門的課題，它的思想是把許多有計算能力的設備互聯(lián)起來，一方面有利于資源的全局共享，另一方面也有效地利用閑置的計算資源。也就是說，其目的是通過架構下一代數(shù)據(jù)中心作為虛擬服務來增強服務功能，使用戶從世界上任何角落都能夠獲得和部署應用程序，對于滿足用戶的服務質量的要求具有成本優(yōu)勢[1]。這種模式也順應了大數(shù)據(jù)時代的發(fā)展，把數(shù)據(jù)進行分布式的統(tǒng)一管理，減輕了終端的負荷，減少了服務對硬件的依賴。這種方式使得用戶一旦能夠訪問云服務，則可以輕松地獲取所需的資源，而且這種收費模式按照所需計算，其概念就和我們的家庭水電的收費一樣，這種概念一旦實現(xiàn)，必然會極大地改善我們的生活水平，因此研究這樣一個方向是極具意義的。

作為一種新型的計算模式，云計算的資源動態(tài)分布，異構多樣，這使得它的任務調度策略較為復雜，這也成為了云計算研究中的一大熱點，如何有效地讓用戶任務與當前可用資源進行動態(tài)分配和合理調度，提供高質量服務的同時，還綜合考慮到可擴展性、執(zhí)行效率和均衡負載等因素。因此，合理高效地在云環(huán)境下進行任務調度是一個非常復雜的問題，也成為了一個重要的課題，目前已經(jīng)吸引眾多學者投入精力去研究。按照調度問題不同，可以把現(xiàn)有的資源調度策略分為兩大類：第一類是根據(jù)資源異構及資源任務的動態(tài)變化提出自適應的調度算法。第二類是將啟發(fā)式算法運用于資源調度的研究中。如今在這一塊的研究中已經(jīng)取得了一系列的工作成果。文獻[2]提出了一種動態(tài)資源分配的方法，它考慮了任務請求的到達和銷毀時間，并且可以預測系統(tǒng)的計算能力和激活時間。文獻[3]提出了一種基于Agent的調度方法，它利用服務代理機制使得用戶任務請求間進行有效通信，實現(xiàn)資源的最大化利用。文獻[4]提出一種能量感知任務融合技術，以優(yōu)化云數(shù)據(jù)中心虛擬集群的能量消耗，任務融合是一種最大化利用資源的方式，可以更好地利用資源并合理地使用IT服務。文獻[5]提出了一個基于截止期、可靠性、資源感知的分布式調度系統(tǒng)，此調度系統(tǒng)綜合考慮了真實網(wǎng)絡拓撲和通信模型，該分布式調度系統(tǒng)使得在低成本條件下的大規(guī)?？茖W計算成為可能。文獻[6]提出一種基于遺傳-蟻群算法的任務調度策略，集成了這兩種算法的雙重優(yōu)點，通過實驗證明在大規(guī)模任務調度環(huán)境下的效率優(yōu)勢。

上述的研究都各有側重點，也有著不足，但是都給我們一個思路去思考調度問題。文本主要從節(jié)約調度時間和功耗的角度出發(fā)，通過研究當前的啟發(fā)式算法來設計高效的調度混合算法，主要的思路是通過蟻群算法和布谷鳥搜索算法的有效融合，提高算法的全局搜索能力，改善算法的收斂速度。并通過實驗分析來說明所提出的算法能夠在云環(huán)境的資源調度中取得較好的效果。

2相關知識

在提出新的混合算法之前，我們必須先對對蟻群算法、布谷鳥搜索算法和云計算下任務調度模型進行介紹，簡單分析它們的優(yōu)缺點，從而進一步研究如何進行融合。

2.1蟻群算法

蟻群算法ACO(Ant Colony Optimization)是受自然界中螞蟻搜索食物行為的啟發(fā)而形成的一種智能優(yōu)化算法。它的思想是模擬蟻群的集體覓食過程中的群體協(xié)作行為，實現(xiàn)求解路徑上的信息積累反饋，并逐步取得最優(yōu)路徑。算法最早是由意大利學者Dorigo等人提出的，并被應用到TSP等一系列組合優(yōu)化問題中，目前取得了良好的效果。

與其他啟發(fā)式算法相比，蟻群算法在信息交換積累方面更加高效，也容易實現(xiàn)優(yōu)化，因此在求解能力上具有很強的魯棒性和精確性。而且作為一種隨機種群進化算法，具有本質的并行性。但是，蟻群算法一般需要較長的搜索時間，容易出現(xiàn)停滯，造成收斂速度慢，易陷入局部最優(yōu)。

2.2布谷鳥搜索算法

布谷鳥搜索CS(Cuckoo Search)是2009年由劍橋大學的 Yang Xin-she和 Deb S 開發(fā)的元啟發(fā)式算法。該算法是受到布谷鳥的孵育寄生行為而啟發(fā)的。重要的是，該算法利用Levy飛行取代了簡單的各向同向性隨機搜索路徑，從而增強了算法的搜索功能。

該算法之所以有較強的搜索性能，主要原因是：(1)有很好的全局搜索和局部搜索的平衡；(2)算法受控制的參數(shù)數(shù)量較少。在CS算法中主要有兩個參數(shù)：為群體規(guī)模n和發(fā)現(xiàn)概率p。一旦n固定下來，p就是控制精英選擇和平衡全局搜索與局部搜索的重要工具。與其他啟發(fā)算法相比，CS算法的優(yōu)點在于選用參數(shù)少、搜索路徑優(yōu)、全局優(yōu)化能力強。

2.3云任務調度模型

在云計算平臺的任務調度中主要有三個方面的任務需要完成。依次為：任務解析、資源檢測和資源分配與任務調度，如圖1所示。首先，先由任務解析器把用戶提交的任務分解成合適的任務執(zhí)行單元，并放進任務池中。然后，根據(jù)每個執(zhí)行單元之間的約束關系形成任務執(zhí)行的聯(lián)系圖，一般用有向無環(huán)圖(DAG)表示；同時，由資源檢測單元監(jiān)測任務處理單元的狀態(tài)，并將硬件信息反饋給資源分配與調度單元。最后，由該單元完成資源的分配與任務的調度。

Figure 1　Scheduling model of cloud tasks 圖1　云任務調度模型

3基于DAG的任務調度模型

本文所研究的問題是由云計算平臺抽象而來的，提出的算法是針對任務節(jié)點的執(zhí)行時間和能源消耗作為優(yōu)化的目標。問題可以描述如下：

輸入：以DAG圖的形式表示任務節(jié)點；

輸出：將任務節(jié)點分配到云平臺上執(zhí)行，獲取最短執(zhí)行時間和最少的能源消耗，輸出任務分配調度方案。

為了方便研究，我們假設計算節(jié)點是相同的，也就是各個節(jié)點在功能、性能和損耗方面具有同樣的等級。而且，我們忽略集群系統(tǒng)中出現(xiàn)的故障處理，而把故障處理時間集成到每個任務的執(zhí)行時間。對于能耗消耗率的考慮，我們簡單地用節(jié)點的功率來表示，因為通信的功耗主要取決于數(shù)據(jù)的大小和通信鏈路的傳輸速率。

任務的表現(xiàn)形式是如圖2所示的有向無環(huán)圖G=(n,e)。其中，n表示任務節(jié)點；e代表任務之間的約束關系，邊上的數(shù)值是節(jié)點之間的通信成本，代表完成任務所損耗的能量。

Figure 2　Task dependency DAG graph 圖2　任務依賴DAG圖

4基于蟻群-布谷鳥搜索的任務調度策略

針對第2節(jié)中所提出的任務調度模型，本節(jié)我們將提出一種混合的ACOCS算法來快速。

蟻群算法憑借其良好的并行性、自組織性、正反饋性和魯棒性，非常適用于組合優(yōu)化的問題研究。但是，也存在不少的問題：(1)信息素是該算法最重要的信息載體，因此如何設計優(yōu)秀的信息素更新策略是一個問題。(2)蟻群覓食搜索的時間較長，對于算法的收斂速度產(chǎn)生較大的影響，而且容易陷入局部最優(yōu)。為了解決這一問題，本文引入CS算法，該算法需要設置的參數(shù)較少，容易實現(xiàn)，而且搜索的能力較強，對于全局搜索的速度較快，因此把它作為蟻群算法中覓食過程的搜索策略可以有效地提高全局搜索的效率，并且可以作為改變全局信息素積累的一種方法。

4.1優(yōu)化搜索策略

蟻群算法的搜索時間較長，蟻群中單只螞蟻的運動是隨機的，但當問題的規(guī)模較大時會增加搜索最優(yōu)解的難度，而且全局性會變差。混合算法的一大目標就是結合CS算法的搜索優(yōu)勢，并且改善蟻群算法搜索所帶來的局部性和收斂慢的缺點。

CS算法的搜索路徑與普通的路徑不同，它使用的是隨機性較強的Levy飛行的搜索方式。這種方式是一個步長大小服從Levy分布的隨機游走，而游走方向是服從均勻分布的，并且還使用了具有Levy分布特征的Mantegna法則來選擇步行向量。

(1)

其中，⊕是點對點乘法；Levy(λ)就是一個步長大小服從Levy分布的隨機游走，可以表示為:

(2)

而步長大小主要通過Mantegna法則來實現(xiàn)。另外，α是步長控制量，主要用來控制方向和補償大小。

把CS的搜索思想應用于蟻群算法中，可以使一些新解的產(chǎn)生是通過圍繞最優(yōu)解的Levy游走而漸漸達到最優(yōu)的，這時也加快了局部搜索。而通過偏離較遠的位置隨機產(chǎn)生的一部分新解是遠離當前最優(yōu)解的，這樣就可以確保系統(tǒng)沒有陷入局部最優(yōu)解。

4.2信息素更新策略

蟻群算法中的信息素是非常重要的信息。一個好的信息素分布可以引導螞蟻快速準確地尋找到最優(yōu)解，同時螞蟻本身的行為可以影響和改變信息素的分布。本文所提出的算法首先是利用蟻群算法本身的搜索策略來進行一次迭代，對局部的節(jié)點進行信息素的更新。再把所求得的當前最優(yōu)解轉換到CS算法中去進一步迭代，對全局的信息素進行更新。

在時間t,每一個任務被分配到任意節(jié)點的概率可以由以下公式計算得出：

(3)

其中，τ是信息素濃度，η為可見度，本文采用η=aP+bC來計算，a和b是人工設置的系數(shù)，代表所占的權重；P反映的是節(jié)點的計算性能；而C反映的是節(jié)點的通信能力。α為信息素取法因子，反映螞蟻在路徑搜索中隨機性因素所用的強度，β為期望啟發(fā)式因子，反映螞蟻在路徑搜索先驗性、確定性因素作用的強度。

這樣的信息素更新策略有效地利用了CS算法中的精英保留策略，體現(xiàn)了算法局部搜索和全局搜索很好的結合，而且有效增加了混合算法解的多樣性，使算法有效地避免陷入局部最優(yōu)，從而達到全局最優(yōu)的目的。

4.3算法描述

算法的描述如下：

步驟1初始化算法中的起始值。設定當前的任務數(shù)、測試的節(jié)點數(shù)，還有初始時刻的信息素。

步驟2每個螞蟻獨自進行隨機搜索，根據(jù)公式(3)計算在搜索過程中留下的信息素，得出一次迭代的解。

步驟3利用上一步中得到的一組當前解初始化為CS算法的起始值，然后利用位置更新公式(1)繼續(xù)進行搜索，并通過與發(fā)現(xiàn)概率對比進行選擇，得出一組較優(yōu)解和較優(yōu)鳥窩位置。

步驟4把上一步得到的較優(yōu)位置作為當前節(jié)點的信息素保留下來，并根據(jù)所選取的計算節(jié)點，計算對應的調度方案的調度長度L，并更新全局信息素。

步驟5若迭代次數(shù)到達所預定的最大迭代次數(shù)，或者迭代出現(xiàn)退化現(xiàn)象，則算法終止。那么，最優(yōu)調度方案取為當前記錄的最優(yōu)解集。

算法的流程圖如圖3所示：

Figure 3　Flowchart of ACOCS algorithm 圖3　ACOCS算法流程圖

5實驗分析

為驗證本文中所提出的AOCCS算法的性能，采用云計算仿真軟件CloudSim進行測試。主要與ACO算法進行比較并分析實驗結果。實驗的硬件環(huán)境為：IntelCorei5-2410M2.3GHzCPU,4GB內存。軟件環(huán)境為：Windows7操作系統(tǒng)，Eclipse3.2和Java1.6.0語言開發(fā)工具，以及CloudSim2.1.1仿真器。

參考文獻程序運行過程中需要按照實際情況設定運行時參數(shù)，本文涉及到的運行時參數(shù)設定由表1給出。由[10]可知道，α的最優(yōu)取值范圍為[1.0,3.0]，這里取中間值2；β的最優(yōu)取值范圍為[2.0,4.0]，這里取中間值3。這里假設節(jié)點的通信能力和計算能力均衡，則A取值0.5，B取值0.5。另外，為了節(jié)省實驗的時間，節(jié)點選取10個，螞蟻數(shù)選取20個，最大迭代次數(shù)選取100次。如表1所示。

Table 1　 Runtime parameters

表2和圖4為ACOCS算法與AOC算法隨著任務數(shù)增加完成任務調度所需要的時間。由圖4可以看出，當任務數(shù)較少時，兩種算法完成調度的時間差不多，但隨著任務數(shù)的增加，ACOCS算法的完成時間增長較慢，速度得到明顯的提高。

Table 2　 Relationship between the number

Figure 4　Comparison of completion time between the two algorithms 圖4　兩種算法完成時間比較

表3和圖5為ACOCS算法與AOC算法隨著任務數(shù)增加所消耗的能源量。圖5可以看到，當任務數(shù)較少時，兩個算法的能耗量基本相同，但是當任務數(shù)增加之后，ACOCS算法的能耗量得到改善的效果更好。

Table 3　 Relationship between the number of

Figure 5　Comparison of energy consumption between the two algorithms 圖5　兩種算法能量消耗比較

通過上述實驗可以知道，ACOCS算法較于ACO算法在執(zhí)行時間和能量消耗方面都明顯有優(yōu)勢，而且隨著任務數(shù)的增加，表現(xiàn)出來的性能更好。這都是因為提高了算法的搜索速度和全局性，使得ACOCS算法能夠較快地收斂，減少了迭代的次數(shù)；而且還保留著ACO原有的并行性優(yōu)勢。

6結束語

本文對云計算的資源調度問題進行了一些探討，并介紹了當前一些工作成果。在這些工作的啟發(fā)下，通過對蟻群算法和布谷鳥搜索算法進行深入的研究，分析兩種啟發(fā)式算法可以互相促進的特點，并進一步提出一種基于布谷鳥搜索改進的蟻群算法的資源調度融合算法。該算法主要通過在蟻群算法中融入布谷鳥搜索的優(yōu)勢，增強了蟻群算法的全局搜索和收斂速度。仿真實驗測試結果表明，該算法有效減少了調度所需的響應時間，也一定程度上提高了系統(tǒng)資源利用率。接下來的工作是進一步從其他方面來測試該算法的性能，并把這種策略應用到實際的云環(huán)境系統(tǒng)。

參考文獻:

[1]ChenQuan,DengQian-ni.Cloudcomputinganditskeytechnology[J].ComputerApplication,2009,29(1):2562-2567.(inchinese)

[2]TammaroD,DoumithEA,ZahrSA,etal.Dynamicresourceallocationincloudenvironmentundertime-variantjobrequests[C]//Procof2011IEEE3rdInternationalConferenceonCloudComputingTechnologyandScience,2011:592-598.

[3]SongH,BaeCS,LeeJW,etal.Utilityadaptiveservicebrokeringmechanismforpersonalcloudservice[C]//ProcofMilitrayCommunicationsConference,2011:1622-1627.

[4]HsuCH,ChenSC,LeeCC,etal.Energy-awaretaskconsolidationtechniqueforcloudcomputing[C]//Procof2011IEEE3rdInternationalConferenceon.CloudComputingTechnologyandScience(CloudCom), 2011:115-121.

[5]ZhaoL,RenY,SakuraiK.Aresourceminimizingschedulingalgorithmwithensuringthedeadlineandreliabilityinheterogeneoussystems[C]//Procof2011IEEEInternationalConferenceon.AdvancedInformationNetworkingandApplications,2011:275-282.

[6]DengJian-guang,YuanHua-qiang,ZhaoYue-long.Agridtaskschedulingstrategybusedongeneticalgorithmandantcologyalgorithm[J].ApplicationResearchofcomputer,2011,28(12):4485-4488.(inChinese)

[7]SelvaraniS,SadhasivamGS.Improvedcost-basedalgorithmfortaskschedulingincloudcomputing[C]//Procof2010IEEEInternationalConferenceon.ComputationalIntelligenceandComputingResearch(ICCIC),2010:1-5.

[8]LiL.Anoptimisticdifferentiatedservicejobschedulingsystemforcloudcomputingserviceusersandproviders[C]//Procofthe3rdInternationalConferenceonMultimediaandUbiquitousEngineering,2009:295-299.

[9]WangFan.TheoreticalresearchandapplicationoftheCuckoosearchalgorithm[D].Xi’an:Xi’anPolytechnicUniversity,2011.(inChinese)

[10]SongJin-juan.Animprovedantcolonyalgorithmanditsapplicationinshortestpartproblem[D].Taiyuan：NorthCentralUniversity,2013.(inChinese)

參考文獻：附中文

[1]陳全,鄧倩妮. 云計算及其關鍵技術[J]. 計算機應用,2009,29(1):2562-2567.

[6]鄧見光,袁華強,趙躍龍. 一種基于遺傳—蟻群算法的網(wǎng)格任務調度策略[J]. 計算機應用研究,2011,28(12):4485-4488.

[9]王凡.CuckooSearch算法的理論研究與應用[D].西安：西安工程大學,2011.

[10]宋錦娟. 一種改進的蟻群算法及其在最短路徑問題中的應用[D].太原：中北大學,2013.

黎煌達(1989-),男,廣東廉江人，碩士生，研究方向為云計算和信息物理融合系統(tǒng)。E-mail:403471414@qq.com

LIHuang-da,bornin1989,MScandidate,hisresearchinterestsincludecloudcomputing,andcyberphysicalsystem.

程良倫(1965-),男,廣東廣州人，博士后，博士生導師，研究方向為無線傳感器網(wǎng)絡和信息物理融合系統(tǒng)。E-mail:llcheng@gdut.edu.cn

CHENGLiang-lun,bornin1965,postdoctor,PhDsupervisor,hisresearchinterestsincludewirelesssensornetwork,andcyberphysicalsystem.