基于混合算法的云計(jì)算任務(wù)調(diào)度方法研究

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

關(guān)鍵詞： 混合算法； 云計(jì)算； 任務(wù)調(diào)度； 遺傳算法； 模擬退火算法

中圖分類號(hào)： TN911?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，云計(jì)算（Cloud Computing）這一新興技術(shù)模式應(yīng)運(yùn)而生。云計(jì)算是由并行計(jì)算、分布式計(jì)算以及網(wǎng)格計(jì)算發(fā)展而來，其是一種根據(jù)需要，隨時(shí)隨地對(duì)計(jì)算機(jī)設(shè)備、應(yīng)用程序亦或是存儲(chǔ)資源等共享資源進(jìn)行訪問的計(jì)算模式。云計(jì)算體系架構(gòu)主要由平臺(tái)即服務(wù)（PaaS）、基礎(chǔ)設(shè)施即服務(wù)（IaaS）以及軟件即服務(wù)（SaaS）三層組成[1?3]。

云計(jì)算環(huán)境下，將一個(gè)任務(wù)分配成多個(gè)子任務(wù)，分發(fā)到云環(huán)境中的各個(gè)計(jì)算機(jī)節(jié)點(diǎn)，各個(gè)計(jì)算機(jī)節(jié)點(diǎn)執(zhí)行各自子任務(wù)，并將結(jié)果返回，組合即得到原任務(wù)的解。在不同的環(huán)境和任務(wù)下，計(jì)算節(jié)點(diǎn)、任務(wù)數(shù)量規(guī)模以及用戶數(shù)量各不相同，因此如何高效合理地對(duì)云計(jì)算環(huán)境下任務(wù)進(jìn)行調(diào)度，使得任務(wù)完成時(shí)間最短，消耗成本最低已然成為目前云計(jì)算領(lǐng)域研究熱點(diǎn)之一[4?5]。

在云計(jì)算環(huán)境中，考量任務(wù)調(diào)度方法好壞的尺度主要有任務(wù)完成時(shí)間、帶寬資源、負(fù)載均衡以及計(jì)算成本等。目前，針對(duì)任務(wù)調(diào)度方法的研究中，為了降低研究難度，通常只針對(duì)某一個(gè)考量任務(wù)調(diào)度方法好壞的尺度進(jìn)行研究，問題是經(jīng)常出現(xiàn)優(yōu)化后的方法以較高的計(jì)算成本為代價(jià)換來較短的任務(wù)完成時(shí)間，有時(shí)是得不償失的，因此本文將任務(wù)完成時(shí)間和計(jì)算成本均作為優(yōu)化的目標(biāo)，對(duì)任務(wù)調(diào)度方法進(jìn)行研究，平衡任務(wù)完成時(shí)間和計(jì)算成本，提高云計(jì)算的效率[6]。

1 云計(jì)算任務(wù)調(diào)度問題描述

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

2 混合優(yōu)化算法

使用遺傳優(yōu)化算法對(duì)上述提出的任務(wù)調(diào)度問題進(jìn)行求解，并將模擬退火算法、自適應(yīng)機(jī)理相結(jié)合，建立更加適合云計(jì)算任務(wù)調(diào)度求解的混合優(yōu)化算法。常規(guī)遺傳算法經(jīng)常容易出現(xiàn)最優(yōu)的染色體丟失，造成局部尋優(yōu)能力下降，或者出現(xiàn)早熟線性。模擬退火算法廣泛應(yīng)用于組合優(yōu)化等領(lǐng)域。模擬退火算法是模擬熱力學(xué)物理中的冷卻與退火過程，其局部尋優(yōu)能力較強(qiáng)，但是整體尋優(yōu)能力和效率均不夠高。因此本文將遺傳算法和模擬退火算法進(jìn)行混合，發(fā)揮各自優(yōu)點(diǎn)，彌補(bǔ)缺點(diǎn)。在遺傳算法的循環(huán)尋優(yōu)過程中，利用模擬退火算法的局部尋優(yōu)能力和能夠避免陷入局部最小值的優(yōu)點(diǎn)，同時(shí)對(duì)遺傳算法的交叉、變異概率進(jìn)行自適應(yīng)改進(jìn)，以提高算法的尋優(yōu)效率和收斂精度。混合優(yōu)化算法的工作流程見圖2。

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

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

通?？紤]到計(jì)算量和可行性，選取如下的降溫方式作為模擬退火算法的控制溫度下降函數(shù)：

[Tk+1=λTk] （1）

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

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

[FtimeI=1completeTimeI·uLB] （2）

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

式中：[uLB]是平衡任務(wù)負(fù)載因子，描述各個(gè)資源的利用情況，值越大，利用率越高，則對(duì)應(yīng)的[completeTimeI]越低[9]。

成本的適應(yīng)度函數(shù)表示為：

[FcostI=1completeCostI] （4）

如果適應(yīng)度函數(shù)只對(duì)時(shí)間約束進(jìn)行考慮，則計(jì)算資源的利用率越低，完成任務(wù)時(shí)間越長(zhǎng)的個(gè)體，其適應(yīng)值越小。如果適應(yīng)度函數(shù)只對(duì)成本約束進(jìn)行考慮，則完成任務(wù)所需成本越高的個(gè)體，其適應(yīng)值越小。如果適應(yīng)度函數(shù)同時(shí)對(duì)時(shí)間約束和成本約束進(jìn)行考慮，則適應(yīng)度函數(shù)為：

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

式中：[α]和[β]均在0～1之間，并且[α+β=1]。如果[α=1]，[β=0]，則通過算法進(jìn)行任務(wù)調(diào)度得到的結(jié)果是所消耗時(shí)間最短；如果[α=0]，[β=1]，則通過算法進(jìn)行任務(wù)調(diào)度得到的結(jié)果是所消耗成本最少[10?11]。

3 實(shí)驗(yàn)分析

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

4 結(jié) 語

本文將任務(wù)完成時(shí)間和計(jì)算成本均作為優(yōu)化的目標(biāo)，對(duì)任務(wù)調(diào)度方法進(jìn)行研究，平衡任務(wù)完成時(shí)間和計(jì)算成本，提高云計(jì)算的效率。將遺傳算法和模擬退火算法進(jìn)行混合，發(fā)揮各自優(yōu)點(diǎn)，彌補(bǔ)缺點(diǎn)。在遺傳算法的循環(huán)尋優(yōu)過程中，利用模擬退火算法的局部尋優(yōu)能力和能夠避免陷入局部最小值的優(yōu)點(diǎn)，同時(shí)對(duì)遺傳算法的交叉、變異概率進(jìn)行自適應(yīng)改進(jìn)，以提高算法的尋優(yōu)效率和收斂精度。使用Cloudsim 3.0云仿真平臺(tái)進(jìn)行對(duì)比測(cè)試，結(jié)果表明：使用同時(shí)對(duì)任務(wù)完成時(shí)間和計(jì)算成本優(yōu)化的任務(wù)調(diào)度算法能夠較好平衡任務(wù)完成時(shí)間和計(jì)算成本，另外本文使用的混合算法，對(duì)任務(wù)完成時(shí)間和計(jì)算成本優(yōu)化效果更加明顯，要優(yōu)于常規(guī)遺傳算法。

參考文獻(xiàn)

[1] 王登科，李忠.基于粒子群優(yōu)化與蟻群優(yōu)化的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（1）：290?293.

[2] 朱宗斌，杜中軍.基于改進(jìn)GA的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（5）：77?80.

[3] 朱宇航，鄭麗英，鄔開俊.基于改進(jìn)DE的云計(jì)算任務(wù)調(diào)度算法[J].蘭州交通大學(xué)學(xué)報(bào)，2013，32（1）：101?106.

[4] 鄔海艷.基于云計(jì)算環(huán)境下資源調(diào)度算法研究[D].贛州：江西理工大學(xué)，2012.

[5] 李建鋒，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2011，31（1）：184?186.

[6] 王波，張曉磊.基于粒子群遺傳算法的云計(jì)算任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（6）：84?88.

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

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

[9] 王靈霞，趙宏.云環(huán)境下基于免疫遺傳算法的任務(wù)調(diào)度問題研究[J].自動(dòng)化與儀器儀表，2015（3）：114?116.

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

[11] 鄧見光.云計(jì)算任務(wù)調(diào)度策略研究[D].廣州：華南理工大學(xué)，2014.