基于混合算法的云計算任務調度方法研究

摘 要： 目前針對任務調度方法的研究中，為了降低研究難度，通常只針對某一個考量任務調度方法好壞的尺度進行研究，經常會出現優化后的方法以較高的計算成本為代價換來較短的任務完成時間，有時是得不償失的。因此該文將任務完成時間和計算成本均作為優化的目標，對任務調度方法進行研究，平衡任務完成時間和計算成本，提高云計算的效率。該文使用遺傳優化算法對上述提出的任務調度問題進行求解，并將模擬退火算法、自適應機理相結合，建立更加適合云計算任務調度求解的混合優化算法。最后，通過實驗分析，以僅對任務完成時間優化和僅對計算成本優化的算法進行比較，該文研究的混合算法的云計算任務調度方法能夠有效平衡任務完成時間和計算成本，有效提高云計算的效率，降低其計算成本。

關鍵詞： 混合算法； 云計算； 任務調度； 遺傳算法； 模擬退火算法

中圖分類號： TN911?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2016）12?0070?03

Abstract： In order to reduce the difficulty of study， only the level of stand or fall of task scheduling method is usually considered in the researched， but the optimized method often causes a higher computational cost in exchange for shorter task completion time， which sometimes is not worth the candle. Therefore， both the task completion time and computation cost are all taken as optimization object in this paper to conduct the research of the task scheduling method， balance the task completion time against computation cost， and improve the efficiency of cloud computing. In this paper， a genetic optimization algorithm is used to solve the proposed task scheduling problem， and the simulation annealing algorithm is combined with adaptive mechanism to establish a hybrid optimization algorithm which is more suitable for cloud computing task scheduling. The task completion time optimization algorithm and cost optimization algorithm are compared by means of experimental analysis. The cloud computing task scheduling method of the hybrid optimization algorithm can effectively balance the task completion time against computing cost， effectively improve the efficiency of cloud computation， and reduce its computational cost.

Keywords： hybrid algorithm； cloud computing； task scheduling； genetic algorithm； simulated annealing algorithm

0 引 言

隨著互聯網技術的不斷發展，云計算（Cloud Computing）這一新興技術模式應運而生。云計算是由并行計算、分布式計算以及網格計算發展而來，其是一種根據需要，隨時隨地對計算機設備、應用程序亦或是存儲資源等共享資源進行訪問的計算模式。云計算體系架構主要由平臺即服務（PaaS）、基礎設施即服務（IaaS）以及軟件即服務（SaaS）三層組成[1?3]。

云計算環境下，將一個任務分配成多個子任務，分發到云環境中的各個計算機節點，各個計算機節點執行各自子任務，并將結果返回，組合即得到原任務的解。在不同的環境和任務下，計算節點、任務數量規模以及用戶數量各不相同，因此如何高效合理地對云計算環境下任務進行調度，使得任務完成時間最短，消耗成本最低已然成為目前云計算領域研究熱點之一[4?5]。

在云計算環境中，考量任務調度方法好壞的尺度主要有任務完成時間、帶寬資源、負載均衡以及計算成本等。目前，針對任務調度方法的研究中，為了降低研究難度，通常只針對某一個考量任務調度方法好壞的尺度進行研究，問題是經常出現優化后的方法以較高的計算成本為代價換來較短的任務完成時間，有時是得不償失的，因此本文將任務完成時間和計算成本均作為優化的目標，對任務調度方法進行研究，平衡任務完成時間和計算成本，提高云計算的效率[6]。

1 云計算任務調度問題描述

云計算的任務調度問題主要由提交任務、獲取可利用資源信息、執行任務調度策略以及返回計算結果這四部分完成。云計算的任務調度過程如圖1所示。首先，用戶將任務提交至由多計算資源組成的云計算系統，系統將任務劃分為多個子任務；之后，根據特定的任務調度方法，將子任務與云計算環境下的可用計算資源建立聯系并分配任務，通常，一個子任務只能夠分配給一個可利用計算資源，但是一個可利用計算資源能夠接受多個任務；最后各個計算資源將計算結果返回云計算系統并整合結果，完成計算任務[7]。

2 混合優化算法

使用遺傳優化算法對上述提出的任務調度問題進行求解，并將模擬退火算法、自適應機理相結合，建立更加適合云計算任務調度求解的混合優化算法。常規遺傳算法經常容易出現最優的染色體丟失，造成局部尋優能力下降，或者出現早熟線性。模擬退火算法廣泛應用于組合優化等領域。模擬退火算法是模擬熱力學物理中的冷卻與退火過程，其局部尋優能力較強，但是整體尋優能力和效率均不夠高。因此本文將遺傳算法和模擬退火算法進行混合，發揮各自優點，彌補缺點。在遺傳算法的循環尋優過程中，利用模擬退火算法的局部尋優能力和能夠避免陷入局部最小值的優點，同時對遺傳算法的交叉、變異概率進行自適應改進，以提高算法的尋優效率和收斂精度?；旌蟽灮惴ǖ墓ぷ髁鞒桃妶D2。

模擬退火算法的工作流程如下：

使用上述的模擬退火算法的好處是，若新解性能更好，則將新解作為當前解；若新解惡化，則以一定概率將新解作為當前解，從而確保算法尋找局部最優解的能力。

通常考慮到計算量和可行性，選取如下的降溫方式作為模擬退火算法的控制溫度下降函數：

[Tk+1=λTk] （1）

式中：[λ]正數，并且略微低于1；[k]是降溫次數[8]。

設定遺傳算法中種群規模為[S]，資源數量為[M]，分配子任務個數為[N]，則生成初始種群表述為：系統隨機得到[S]個長度為[N]的染色個體， 基因值是范圍在1～M之間的隨機數。遺傳算法中的適應度函數會影響算法的收斂速度和收斂精度，個體的適應值大小會影響其遺傳到下一代的概率大小。本文研究的云計算任務調度問題，需要對完成所有分配的子任務的時間和成本進行考慮。時間的適應度函數表示為：

[FtimeI=1completeTimeI·uLB] （2）

[uLB=i=1MsumTimeiM×completeTimeI] （3）

式中：[uLB]是平衡任務負載因子，描述各個資源的利用情況，值越大，利用率越高，則對應的[completeTimeI]越低[9]。

成本的適應度函數表示為：

[FcostI=1completeCostI] （4）

如果適應度函數只對時間約束進行考慮，則計算資源的利用率越低，完成任務時間越長的個體，其適應值越小。如果適應度函數只對成本約束進行考慮，則完成任務所需成本越高的個體，其適應值越小。如果適應度函數同時對時間約束和成本約束進行考慮，則適應度函數為：

[FitnessI=α·FtimeI+β·FcostI] （5）

式中：[α]和[β]均在0～1之間，并且[α+β=1]。如果[α=1]，[β=0]，則通過算法進行任務調度得到的結果是所消耗時間最短；如果[α=0]，[β=1]，則通過算法進行任務調度得到的結果是所消耗成本最少[10?11]。

3 實驗分析

使用墨爾本大學開發的Cloudsim 3.0云仿真平臺對本文研究的任務調度算法進行性能分析。使用僅對任務完成時間優化的常規遺傳算法和對計算成本優化的常規遺傳優化算法以及同時對任務完成時間和計算成本優化的常規遺傳算法作為對比。模擬退火算法中，設定初始退火溫度為[T0=200 ℃]，[λ=0.92]。遺傳算法中，交叉概率[Pc1=0.95]，[Pc2=0.7]，變異概率[Pm1=0.1]，[Pm2=0.01]，[α=0.35]，[β=0.65]。設定種群規模為[S=100]，分配子任務個數為[N=1 500]，資源數量為[M=10]， 最大迭代次數為200。得到測試結果如圖3所示。測試結果表明，使用的四種任務調度算法測試過程中，在算法迭代起始階段，四種算法對任務完成時間和計算成本的優化效果基本相同，但在迭代中后期，各種算法的優化性能顯現出差異。僅對任務完成時間優化的常規遺傳算法對任務完成時間起到較好的優化，但是對于計算成本沒有較好的優化效果，使用該種任務調度算法，計算成本較高。而僅對計算成本優化的常規遺傳算法對計算成本起到較好的優化，但是對于任務完成時間沒有較好的優化效果，使用該種任務調度算法，任務完成時間較長。而使用同時對任務完成時間和計算成本優化的任務調度算法能夠較好平衡任務完成時間和計算成本。另外本文使用的混合算法，在遺傳算法的循環尋優過程中，利用模擬退火算法的局部尋優能力和能夠避免陷入局部最小值的優點，同時對遺傳算法的交叉、變異概率進行自適應改進，使得對任務完成時間和計算成本優化效果更加明顯，要優于常規遺傳算法。

4 結 語

本文將任務完成時間和計算成本均作為優化的目標，對任務調度方法進行研究，平衡任務完成時間和計算成本，提高云計算的效率。將遺傳算法和模擬退火算法進行混合，發揮各自優點，彌補缺點。在遺傳算法的循環尋優過程中，利用模擬退火算法的局部尋優能力和能夠避免陷入局部最小值的優點，同時對遺傳算法的交叉、變異概率進行自適應改進，以提高算法的尋優效率和收斂精度。使用Cloudsim 3.0云仿真平臺進行對比測試，結果表明：使用同時對任務完成時間和計算成本優化的任務調度算法能夠較好平衡任務完成時間和計算成本，另外本文使用的混合算法，對任務完成時間和計算成本優化效果更加明顯，要優于常規遺傳算法。

參考文獻

[1] 王登科，李忠.基于粒子群優化與蟻群優化的云計算任務調度算法[J].計算機應用與軟件，2013，30（1）：290?293.

[2] 朱宗斌，杜中軍.基于改進GA的云計算任務調度算法[J].計算機工程與應用，2013，49（5）：77?80.

[3] 朱宇航，鄭麗英，鄔開俊.基于改進DE的云計算任務調度算法[J].蘭州交通大學學報，2013，32（1）：101?106.

[4] 鄔海艷.基于云計算環境下資源調度算法研究[D].贛州：江西理工大學，2012.

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

[6] 王波，張曉磊.基于粒子群遺傳算法的云計算任務調度研究[J].計算機工程與應用，2015，51（6）：84?88.

[7] 金偉健，王春枝.基于蝙蝠算法的云計算資源分配研究[J].計算機應用研究，2015，32（4）：1184?1187.

[8] 吳虎勝，張鳳鳴，趙法棟.利用自適應混合遺傳算法求解平車裝載問題[J].鐵道學報，2013，35（12）：1?8.

[9] 王靈霞，趙宏.云環境下基于免疫遺傳算法的任務調度問題研究[J].自動化與儀器儀表，2015（3）：114?116.

[10] 宋芳琴.基于改進的蝙蝠算法在云計算中的資源分配[J].計算機系統應用，2015，24（8）：128?132.

[11] 鄧見光.云計算任務調度策略研究[D].廣州：華南理工大學，2014.