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

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

　　摘 要： 目前針對(duì)任務(wù)調(diào)度方法的研究中，為了降低研究難度，通常只針對(duì)某一個(gè)考量任務(wù)調(diào)度方法好壞的尺度進(jìn)行研究，經(jīng)常會(huì)出現(xiàn)優(yōu)化后的方法以較高的計(jì)算成本為代價(jià)換來(lái)較短的任務(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)度問(wèn)題進(jìn)行求解，并將模擬退火算法、自適應(yīng)機(jī)理相結(jié)合，建立更加適合云計(jì)算任務(wù)調(diào)度求解的混合優(yōu)化算法。最后，通過(guò)實(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)度; 遺傳算法; 模擬退火算法

　　0 引 言

　　隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，云計(jì)算(Cloud Computing)這一新興技術(shù)模式應(yīng)運(yùn)而生。云計(jì)算是由并行計(jì)算、分布式計(jì)算以及網(wǎng)格計(jì)算發(fā)展而來(lái)，其是一種根據(jù)需要，隨時(shí)隨地對(duì)計(jì)算機(jī)設(shè)備、應(yīng)用程序亦或是存儲(chǔ)資源等共享資源進(jìn)行訪問(wè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)行研究，問(wèn)題是經(jīng)常出現(xiàn)優(yōu)化后的方法以較高的計(jì)算成本為代價(jià)換來(lái)較短的任務(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)度問(wèn)題描述

　　云計(jì)算的任務(wù)調(diào)度問(wèn)題主要由提交任務(wù)、獲取可利用資源信息、執(zhí)行任務(wù)調(diào)度策略以及返回計(jì)算結(jié)果這四部分完成。云計(jì)算的任務(wù)調(diào)度過(guò)程如圖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)度問(wèn)題進(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é)物理中的冷卻與退火過(guò)程，其局部尋優(yōu)能力較強(qiáng)，但是整體尋優(yōu)能力和效率均不夠高。因此本文將遺傳算法和模擬退火算法進(jìn)行混合，發(fā)揮各自優(yōu)點(diǎn)，彌補(bǔ)缺點(diǎn)。在遺傳算法的循環(huán)尋優(yōu)過(guò)程中，利用模擬退火算法的局部尋優(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)度問(wèn)題，需要對(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]，則通過(guò)算法進(jìn)行任務(wù)調(diào)度得到的結(jié)果是所消耗時(shí)間最短;如果[α=0]，[β=1]，則通過(guò)算法進(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è)試過(guò)程中，在算法迭代起始階段，四種算法對(duì)任務(wù)完成時(shí)間和計(jì)算成本的優(yōu)化效果基本相同，但在迭代中后期，各種算法的優(yōu)化性能顯現(xiàn)出差異。僅對(duì)任務(wù)完成時(shí)間優(yōu)化的常規(guī)遺傳算法對(duì)任務(wù)完成時(shí)間起到較好的優(yōu)化，但是對(duì)于計(jì)算成本沒(méi)有較好的優(yōu)化效果，使用該種任務(wù)調(diào)度算法，計(jì)算成本較高。而僅對(duì)計(jì)算成本優(yōu)化的常規(guī)遺傳算法對(duì)計(jì)算成本起到較好的優(yōu)化，但是對(duì)于任務(wù)完成時(shí)間沒(méi)有較好的優(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)過(guò)程中，利用模擬退火算法的局部尋優(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é) 語(yǔ)

　　本文將任務(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)過(guò)程中，利用模擬退火算法的局部尋優(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ī)遺傳算法。

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