ACOSA：一種基于MapReduce 的啟發式調度算法*

賀立 戴新發 夏靜

（武漢數字工程研究所 武漢 430205）

1 引言

在信息化時代，互聯網產生的數據量呈爆炸性增長，而如何高效處理這些數據以提供高質量服務成為當前面臨的關鍵問題。針對該問題，互聯網發生了一次重大變革，即云計算的出現。MapReduce［1］是一個編程模型，也是一個處理和生成超大數據集的算法模型的相關實現。Hadoop［2］是MapReduce的開源實現，它不僅廣泛應用于批量大作業同時也用于處理相應低效率的短作業。

現有的MapReduce 調度算法存在許多問題。比如FIFO 調度算法相對簡單、便于理解、易于實現。若單個作業發送到集群，則該作業會將整個集群資源占據；若多個作業發送到集群，則調度器基于作業的發送順序完成作業調度。雖然所有用戶共享整個集群資源，但FIFO 給用戶提供資源的機會并不公平，所以FIFO 調度器在實時調度處理方面并不適用。Fair 算法調度器給所有用戶都分配了獨立資源池以確保公平性。因此，不管某用戶提交多少作業，都不會影響到其他用戶的資源池，所有用戶都可以得到相同的共享資源，但無法保證所有節點負載均衡；資源的利用率不高。Capacity 算法隊列設計層次化；彈性分配；容量保證；可操作性高但不支持不支持負載均衡和搶占。

根據現有調度算法的缺點，本文提出了一種基于ACO 和SA 的組合優化算法——ACOSA 算法，該算法可以結合了ACO 算法和SA 算法在調度算法中實現的優點，摒棄了缺點。縮短任務完成的時間以及平衡了對資源的負載。

2 ACO算法和SA算法概述

在整個現代隨機數學上普遍認為Ants 組合啟發式算法組合隨機搜索算法是一種對所有啟發式算法進行隨機組合的最優化隨機搜索算法。基于組合Ants 的啟發式優化組合算法（Ant Colony Optimization，ACO）最早由m.dorigo［3］提出，隨后metropolis提出了SA（Simulated Annealing）組合優化想法，并在啟發式優化和系統優化組合領域得到廣泛應用［4］。SA算法用于獲取組合全局最優解。

2.1 ACO算法原理

Ant 是一種社會昆蟲，其可能只有一種結構和行為構成。一只小型的Ant 可以同時執行少量的結構與動作，且大多數動作用于信息傳遞。一個組織性良好且結構化較高的研究團隊對Ants 的結構與行為進行了研究，結果發現Ants可以完成遠遠超出Ant個人能力的任務。盡管每個Ant個體都有不同的分工，但激素通過其自身獨特的信息系統傳遞信息，Ants可以通過信息的傳遞來“聞到糖分”并收集。

2.2 SA原理

SA 的基本結構設計和思想主要目的是通過模擬了物理學中固體的溫度逐漸退火和停止冷卻的一種物理過程，即當物理學中固體的內部溫度逐漸地升高到物理固體已經有了足夠高的物理固體溫度時逐漸地退火和停止冷卻物理固體的一種物理過程。例如當一個固體物理學中的固體內部原子開始連續地加熱時，物理學家發現固體其中的內部原子在固體中連續地做劇烈熱運動，由此，原子能量得以不斷的增加與釋放。隨著固體內部溫度的不斷升高，物理學中固體的內部原子和顆粒逐漸從有序地轉變為了無序。例如當物理固體的內部溫度逐漸地降低時，顆粒逐漸從無序變化到縱坐標，最終在常溫下恢復到最初的基本狀態。

3 ACOSA算法設計

ACOSA 算法是搜索函數ACO 和ACOSA 的組合。如2.1 節所示，ACOSA 是通過設計和模擬人類在自然界中搜索函數Ant 的過程而提出的一種全局搜索算法。實際上該算法不僅具有很強的復雜性和全局搜索能力，還具有魯棒性和快速反饋的優點，但其容易過早的陷入局部最優解。由2.2 節可知，SA 是在固態物理退火機制的基礎上所提出的一種搜索算法，該算法具有強大的本地搜索功能，可以接受比當前解決方案差的結果并跳過。雖然SA 引擎具有以上所述的優點，但其并沒有充分了解整個文字搜索的空間結構，因此其文字搜索的準確效率很有可能會受到大大降低。為了能夠更好地幫助克服函數ACO 的不足，例如對于收斂的函數速度，本地搜索功能弱和易于本地優化的問題，本文提出ACOSA 算法（Ant Clony Optimization Simulated Anealling）。

3.1 ACOSA算法過程

SA 主要研究用于優化ACO 模型。ACOSA 的這個算法主要特點是認為包括兩個主要的算法階段：ACO和SA。也就是說，首先通過ACO來構建候選人是解決這個問題的整體方案，然后通過SA 調整和優化獲得的候選解決方案。

ACO 操作階段：主要考慮節點負載平衡時，任務的完成時間能夠有所縮短。ACO 利用正反饋縮小候選解的搜索范圍，促使局部最優解轉向全局最優解，最終得到有效的全局最優解。

SA階段：在ACO得到局部最優解的基礎上，一定溫度Ti下，基于Metropolis 原理，利用SA 機制判斷是否接受候選方案，這構成了一個新的解決方案全局最優。

在ACO 中引入SA，以形成新的ACOSA 算法，該算法彌補了ACO 算法的缺點，避免其陷入局部最優解。

3.2 ACOSA算法的相關設定

云環境中的資源節點具有異構性、動態性以及不確定性。由此，本研究基于異構環境提出編程算法，并做出以下假設：

1）用戶分配的任務具有獨立性和不可分割性；未按照正確順序執行任務；除非節點發生故障，否則在執行期間無法中斷任務。

2）云環境中的資源節點數量遠遠小于任務數量。

通過數據分析和進行測量計算構造一個節點中CPU的網絡數據處理計算能力，網絡的內存帶寬和構造網絡中的內存容量情況來進行測量計算構造一個節點的網絡性能和平均計算構造一個節點數據群集的網絡性能。計算各個信息節點j的初始元素值以及信息素濃度：

式中：RT 為n*m 矩陣；RTij為任務i 在各節點j 上的平均執行時間與速度，其中包含通信時間和計算時間。

ACOSA 算法的主要目的是極大地減少了節點中每一個任務的平均完成速度和時間，同時還要考慮到每一個節點的任務負載平衡的情況。

1）節點選擇概率

將大于Ants 的輪盤概率節點隨機分配到所有的輪盤概率任務上，假設任務在i 處放置了a 只Ants，Ants（k=l，2，…，a）在所有的m 個輪盤概率節點中隨機選擇一個輪盤概率能夠同時滿足輪盤概率的放置節點并將其分配到所有的任務i上。

為維持兩個節點間的負載均衡，需根據ACOSA 算法對其進行計算，并將所得結果用于輪盤概率啟發計算函數。任務Ti分配到節點Nj的概率為

式中：τj(t)為在t時信息素濃度的計算函數；ηj(t)為t時的啟發函數；allowedk為節點集合｛N1，N2…Nm｝-tabuk。

本研究為了更加公平地運用該算法，設置信息素濃度計算函數的初始值ηj(0)=c。根據式（8）計算信息素啟發函數：

式中：Timej為節點Nj在t 時執行任務的次數與時間。

式中：Timeexec（Ti，Nj）為任務i 在各節點j 上執行任務的次數與時間；Timetra（Ti，Nj）為任務i 發送至節點j上的數據傳輸時間；根據式（9）可以計算得到各節點i 在Nj上的任務運行次數與時間；TimeBest-avg為上次迭代任務已經結束，且取得最優解，在該情況下各節點執行任務的次數與時間。

2）信息素更新

ACO 對Ants 在節點上分泌的信息素種類進行檢測，以有效地加快包含Ants的節點數據搜索速度并有效地優化搜索路徑。在本文中，信息素的分泌通常是在特定的節點而不是路徑中進行的。所以，在Ant 完成其所分配的任務后會對信息素節點繼續更新。此外，本地信息素在等到所有Ants完成任務后才會結束。信息素更新的表達式為

式中：ρ為路徑信息素的揮發系數，其值越大，殘存的信息素對當前選擇路徑的影響就越小。

Ant 將所有任務分配完之后，對已訪問節點上的局部信息素進行更新，其計算表達式為

式中：Timej為第i 次迭代完成后，節點j 上各任務所需完成時間。

若所有Ant 能同時完成所分配的任務，則對其進行全局任務信息素的更新，其方法為

式中：Bestj為節點j在任務得到一個全局最優解后，其完成剩余任務所需時間。

3）Metropolis準則

根據ACO 能夠得到局部最優解，而根據SA 可以增加局部最優的搜索能力，基于置換規則，能夠破壞節點當前任務的局部最優解，即從節點中隨機選擇兩個最優任務。如果兩個最優任務都對應于不同的局部最優節點請選擇交換一個節點。如果更換后節點縮短了局部最優任務完成的時間，請選擇接受新的節點解決方案，否則根據SAMetropolis的標準判斷您是否接受新的解決方案。根據式（14）和（15），接受一個新解p 的隨機概率到底是多少？如果隨機函數p 的隨機值遠遠小于在當前的溫度范圍r 下生成的隨機值，則將不可能接受新的隨機概率解決方案，否則將接受新的解決方案。

式中：TCnew、TCcur-best分別為當前溫度T 下，節點完成所有任務所需時間；ACO中的全部節點完成任務所需的最短時間。ΔTC 時間概率值是表示在當前任務節點的運行溫度ΔTC 時間大于溫度T 下，交換一個新節點任務后在該節點的運行溫度和當前運行的溫度時間之差所產生減少的概率值。P 為絕對溫度ΔTC＞0時，節點新值在改時間點所減少的概率。

4）抽樣穩定準則和終止準則

SA 算法中的采樣溫度退火過程與判斷采樣溫度穩定性的最優解相對應，即在溫度相同的情況下，局部最優解在經過m 次的連續干擾后，其采樣溫度仍然保持不變。此時，認為該算法符合當前采樣該算法的終止準則與SA過程算法中的終止性退火相對應，也就是說如果在當前采樣溫度t下，其最優解比Tmin小，則認為該采樣算法符合終止性退火準則，從而終止該算法。

3.3 ACOSA算法實現流程

ACOSA算法的基本步驟為：

Step1：初始化有關參數。評估模型指標包括迭代次數n；Ant 的規模m；溫度衰減參數α；SA 初始溫度T0；信息素揮發因子ρ；評估信息素濃度的重要性β；信息素濃度的重要性最大值a。

Step2：在全部任務上隨機布置Ants，由式（7）構造候選解。

Step3：基于完成全部任務所需時間最小化的原則，再次構造一個局部最優解的鄰域，按照式（11）和（12）對信息素進行計算和更新。

Step4：基于SA 的置換規則，構造鄰域內的新解，根據式（14）和（15）判斷該解接受與否。

Step5：在當前抽樣穩定溫度r 下，判斷局部最優值以及該條件參數是否符合抽樣溫度自動穩定繼續旋轉運動準則，若滿足條件則直接返回穩定旋轉準則步驟6，否則直接返回抽樣繼續穩定運轉準則步驟4。

Step6：按照式（11）和（13）對全局信息素進行更新。

Step7：T(t+1)=a7T(t)，其中a為溫度變化常數。算法需判斷常數值是否小于當前溫度常數，T(t+1)?Tmin與否，若該溫度常數符合這個通用算法的溫度終止轉換準則，則這個溫度常數值的轉換結果為零，此時轉至Step8，否則返回Step2。

Step8：判斷當前迭代次數的條件是否全部符合，且是否達到當前最大迭代次數，若條件滿足，則終止算法，否則返回Step2。

4 仿真實驗與性能分析

本節采用的實驗仿真平臺為CloudSim3.0，用其分析云計算ACOSA、ACO 和FCFS 調度算法的應用性能。

4.1 仿真參數設置

在實驗仿真平臺（CloudSim）中可以設置5個資源和虛擬計算機的數據中心，50 個對虛擬機的資源和100個～1000個對虛擬機資源和對任務的虛擬計算機進行長度仿真的模擬實驗。數據中心發送到對資源和虛擬任務計算機長度的參數設置為1000mi～20000mi（MillionInstructions）。云長度仿真模擬實驗中的參數設置如表1所示，ACOSA與ACO算法的參數設置如表2所示。

表1 CloudSim的參數設置

表2 ACO和ACOSA算法參數設置

4.2 實驗結果與分析

采用虛擬機負載不均值DI（DegreeofImbalance）對虛擬機的負載均衡情況進行評價，計算表達式見式（15）、（16）。

式中所有提交完成分配指令到每一個系統節點j 上的所有完成分配任務的運行長度之和用TotalLengthj表示每一個系統節點j 和j 的所有完成和分配任務處理能力是分配指令的運行速度和處理能力。Timej所表示的系統運行的時間分別是每一個系統節點j 和j 的所有完成和分配任務所需的系統運行長度和處理時間。Timeavg，Timemax、Timemin分別表本每一個節點j運行長度和時間的平均值、最大值和最小平均值。

由圖1 可知，隨著迭代次數的持續增加，采用ACOSA 與ACO 算法可逐漸縮短任務的完成時間，但對于這兩種算法，任務開始完成的時間在迭代完成次數之后逐漸開始減少的迭代完成次數遠遠大于60。

圖1 550個任務不同迭代次數的完成時間

在實驗2 中，對不同數量調度任務的主要完成和執行時間進行比較。例如圖2 描述了任務調度圖中的fcfs，ACO 和任務ACO，SA 的任務調度算法對于一個調度任務的主要調度完成和執行時間包括調度和任務的執行時間。從上圖所示的兩個任務調度實驗算法分析的結果中我們已經看到了可以清楚地明顯可以看出，隨著我國大型企業任務調度數量的進一步大大地增加，任務調度中經常使用的調度任務fs 和ACOSA 兩種任務調度算法使得大型企業任務的調度完成率和中型企業調度完成任務的執行時間逐漸大大地小于任務調度中經常使用的fcfs和任務ACOSA兩種任務調度算法

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

利用實驗2 的結果對負載不均衡值DI 進行計算，得到的結果如圖3所示。

圖3 各算法的DI值

從圖2 和3 中能夠清楚地看出，任務調度的效果遠遠優于它的f和fs兩個最前處理算法的原因就是ACOSA 兩個最前處理算法，它們處理任務的最前和完成最后的執行和處理的時間比基于它的fcfs兩個算法的處理任務最前的完成和最后執行的處理任務時間分別明顯地縮短了50%～60%和15%～20%，并且明顯程度上優于其他的ACOSA 任務最前處理的算法。同時，虛擬機上還可能存在不平等的資源和負載。通過深入學習與應用分析前面所使用的云計算及其他可編程任務的最前處理算法顯著的增加或減少負載，可知ACOSA 算法無論是在任務的最前完成執行速度和處理時間還是在完成收斂和運行速度等方面都將具有更好的負載平衡優勢和更好的負載平衡。

5 結語

本文根據蟻群算法作業調度和蟻群策略的特點優化了MapReduce的作業調度性能，對目前蟻群算法的性能優化方向和作業調度策略進行充分闡述與分析，并重點討論啟發式蟻群算法ACO 和ACOSA 的基本原理和其取舍。本文針對將蟻群啟發式算法易用于受局部最優“未成熟”算法影響的局部蟻群啟發式算法的一些缺點，詳細地介紹了將SA 算法引入新的ACOSA 算法的優點以及ACOSA啟發式算法解決問題。本研究采用的仿真工具主要是ACOcloudsim，用其對新ACOSA算法進行模擬計算，并以任務完成時間、收斂速度和消耗的負載均衡值為評價指標分析仿真結果的可靠性，結果顯示：ACOSA啟發式算法在三個指標上均有良好表現。