ACOCS：一種云環境下資源調度混合算法

ACOCS：一種云環境下資源調度混合算法*

黎煌達,程良倫

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

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

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

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

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

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

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

作者簡介:

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引言

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

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

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

2相關知識

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

2.1蟻群算法

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

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

2.2布谷鳥搜索算法

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

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

2.3云任務調度模型

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

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

3基于DAG的任務調度模型

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

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

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

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

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

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

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

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

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

4.1優化搜索策略

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

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

(1)

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

(2)

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

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

4.2信息素更新策略

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

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

(3)

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

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

4.3算法描述

算法的描述如下：

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

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

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

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

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

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

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

5實驗分析

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

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

Table 1　 Runtime parameters

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

Table 2　 Relationship between the number

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

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

Table 3　 Relationship between the number of

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

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

6結束語

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

參考文獻:

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

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

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

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

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

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

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