計算機網(wǎng)絡(luò)工程論文范文云計算任務(wù)調(diào)度混合算法

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

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

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

　　0 引 言

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

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

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

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

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

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

　　使用遺傳優(yōu)化算法對上述提出的任務(wù)調(diào)度問題進(jìn)行求解，并將模擬退火算法、自適應(yīng)機理相結(jié)合，建立更加適合云計算任務(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)能力較強，但是整體尋優(yōu)能力和效率均不夠高。因此本文將遺傳算法和模擬退火算法進(jìn)行混合，發(fā)揮各自優(yōu)點，彌補缺點。在遺傳算法的循環(huán)尋優(yōu)過程中，利用模擬退火算法的局部尋優(yōu)能力和能夠避免陷入局部最小值的優(yōu)點，同時對遺傳算法的交叉、變異概率進(jìn)行自適應(yīng)改進(jìn)，以提高算法的尋優(yōu)效率和收斂精度�；旌蟽�(yōu)化算法的工作流程見圖2。

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

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

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

　　[Tk+1=λTk] (1)

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

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

　　[FtimeI=1completeTimeI·uLB] (2)

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

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

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

　　[FcostI=1completeCostI] (4)

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

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

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

　　3 實驗分析

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

　　4 結(jié) 語

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

轉(zhuǎn)載請注明來自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/11172.html