計算機網絡工程論文范文云計算任務調度混合算法

　　這篇計算機網絡工程論文范文為提高云計算速度，描述云計算任務調度問題，及混合優(yōu)化算法，并實驗對本文的任務調度算法進行性能分析，提出可行性辦法。《上海信息化》(月刊)創(chuàng)刊于2000年，由《上海信息化》雜志社主辦。是國內第一本全面反映政府、企業(yè)信息化建設的綜合類公開出版刊物。雜志定位為政府信息化的窗口，企業(yè)信息化的舞臺，IT從業(yè)人員的講壇。創(chuàng)刊以來，雜志立足長三角，面向全國，以創(chuàng)新開放的理念、豐富貼切的內容、廣泛深入的觸角，以及鮮活生動的人物報道，在業(yè)界產生了較大影響。獲“世博報道優(yōu)秀期刊”。

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

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

　　0 引 言

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

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

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

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

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

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

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

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

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

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

　　[Tk+1=λTk] (1)

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

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

　　[FtimeI=1completeTimeI·uLB] (2)

　　[uLB=i=1MsumTimeiM×completeTimeI] (3)

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

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

　　[FcostI=1completeCostI] (4)

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

　　[FitnessI=α·FtimeI+β·FcostI] (5)

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

　　3 實驗分析

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

　　4 結 語

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

轉載請注明來自發(fā)表學術論文網：http://www.zpfmc.com/dzlw/11172.html