基于免疫算法的云計算任務調度算法

呂計英

（西山煤電集團信息中心，山西 太原 030053）

云計算不僅要面向大量的用戶群，還要處理海量任務與數據，因此任務調度就成為了云計算中的重點與難點。現有的常見任務調度算法有3種：FIFO調度算法、公平調度算法（Fair Scheduler）和計算能力調度算法（Capacity Scheduler）。它們都存在一些不足：FIFO調度算法會忽略不同用戶的不同作業需求，使交互性的用戶作業長期處于等待狀態，影響系統效率；公平調度算法會造成計算資源的部分浪費，影響資源利用效率；計算能力調度算法容易使作業處于長期等待狀態，陷入局部最優。為了解決這些算法的不足，一些借鑒遺傳算法、蟻群算法等智能算法的云環境任務調度算法相繼被提出。基于改進的蟻群算法的云環境任務調度算法[1]，避免了蟻群優化算法陷入局部最優，縮短了任務平均運行時間，提高了資源利用效率。針對云計算的編程模型框架，提出了一種具有雙適應度的遺傳算法的任務調度算法[2]，不僅能夠快速確定完成所有任務的時間，而且還能保證該調度策略的任務平均完成時間也較短。這增加了問題搜索空間，避免了局部最優。

本文利用免疫算法中的克隆選擇算法，將其應用于云計算環境中的任務調度問題。根據抗體與抗原之間親和力的大小，獲取優秀抗體，并對抗體進行不同程度的變異，最終找出優秀的抗體種群，得出問題的最優解。通過仿真實驗，驗證其算法的有效性，并能夠快速確定任務調度最優策略，提高了系統的整體性能與資源利用效率。

1 基于克隆選擇算法的云計算調度算法的設計

1.1 云計算的任務調度

目前，云計算環境大多采用Google公司提出的Map-Reduce編程模型，它是一種并行編程模式，非常適于產生和處理大規模的數據集。在Map-Reduce計算框架模型中，主要分為Map階段和Reduce階段。Map階段：將用戶提交的較大的作業拆分成若干個較小的任務，然后分配給多個任務服務器（Task Tracker）并行執行，輸出處理后的中間數據；Reduce階段：將Map階段處理后的中間數據進行匯總分析處理，輸出最終結果。

1.2 基于免疫算法的云計算任務調度算法

針對云計算環境中的任務調度問題，利用免疫算法中的克隆選擇算法，可以確定使總任務執行時間和任務平均執行時間都較短的任務調度策略，提高系統效率和資源利用率，滿足用戶的使用需求。

1.2.1 抗體的編碼與解碼

假設有p個作業（job），n個任務服務器node（計算資源），第t個作業被拆分為的任務（task）的數量為：taskNum（t），然后再對這些任務進行編號。假設抗體基因序列的長度為10，每個基因位的取值為1～5，隨機產生下面一個抗體基因序列：{3，2，4，5，2，1，4，3，1，5}，這個抗體基因序列代表第 1 個 task 在第3個node上執行，第2個task在第2個node上執行，……，第10個task在第5個node上執行。如上述抗體基因序列解碼為：

Node1：{6，9}；Node2：{2，5}；Node3：{1，8}；Node4：{3，8}；Node5：{4，10}。

1.2.2 初始抗體種群生成

若初始抗體種群規模為S，作業個數為J，任務個數為m，任務服務器（計算資源）的個數為n，則抗體的種群初始化描述如下：系統隨機產生S個抗體，抗體基因序列的長度為m，每個基因位的取值在任務服務器個數的范圍內隨機選取，即在[1，n]中隨機選擇。

1.2.3 克隆選擇

克隆選則是根據抗體與抗原之間的親和力大小，從抗體種群中選取優秀抗體進行克隆，增加優秀抗體的濃度，并通過不斷的變異進化找到最優抗體（問題的最優解）。因此，親和力的計算顯得尤為重要，它關系到算法的收斂速度以及解的優劣性。

對于云環境的作業調度，一個最主要的性能指標就是全部作業的完成時間，另外還需考慮作業的平均完成時間。在保證所有作業完成時間最短的基礎上，還應該滿足作業的平均完成時間也最短。

在云環境下，基于免疫算法的任務調度算法的流程如下：

第一，初始化抗體種群：隨機產生規模為S的初始抗體種群Ag.

第二，For每一代種群do

{

計算種群中每個抗體的親和力，根據親和力大小，選擇出N個優秀抗體組成臨時抗體種群Ag*N；

對臨時抗體種群Ag*N進行不同規模的克隆增殖，生成增殖種群Agp；

對種群中親和力較低的抗體進行不同程度的基因重組，完成變異操作，生成目標種群Ag′N；

引入隨機抗體進入目標種群，豐富抗體種類，變陷入局部最優；

}

第三，直到滿足算法結束條件。

第四，從抗體種群中選擇出親和力最高的抗體，確定最佳的任務調度方案。

2 仿真實驗及結果分析

由于云計算可以看作是一個特殊的網格環境，所以本文用Gridsim來模擬一個云計算的局部環境。在相同情況下，分別用遺傳算法和克隆選擇算法進行比較。

初始條件：作業（job）個數為 10，任務（task）個數為 20，任務服務器node（計算資源）的個數為5，初始抗體種群規模為50.

算法終止條件：①到達最大進化代數（這里取最大進化代數為100）；②連續20代總任務完成時間和任務平均完成都沒有變化時，認為算法基本收斂，算法結束。

圖1 總任務完成時間比較

從圖1、圖2中可以看出，在進化初期，克隆選擇算法的收斂速度要明顯快于遺傳算法的，并且通過克隆選擇算法得出的總任務的完成時間和任務平均完成時間均要小于遺傳得出的。另外，在進化后期，雖然2種算法都達到了一種基本收斂，但是克隆選擇算法收斂迭代次數以及總任務完成時間和任務平均完成時間均小于遺傳算法的，說明了其算法的優良性與有效性。

圖2 任務平均完成時間比較

3 結束語

本文借鑒了免疫算法中的克隆選擇算法，并應用到云計算環境的任務調度中。克隆選擇算法可以解決云計算環境中的任務調度問題，能夠確定較優的任務調度策略，提高了系統效率與資源利用率，是一種有效的任務調度算法。

[1]王永貴，韓瑞蓮.基于改進蟻群算法的云環境任務調度研究[J].計算機測量與控制，2011，19（5）：1203-1206.

[2]李建鋒，彭艦.云計算環境下基于改進遺傳算法的任務調度算法[J].計算機應用，2011，31（1）：184-186.