云計(jì)算環(huán)境下基于網(wǎng)絡(luò)博弈的任務(wù)調(diào)度算法

《云計(jì)算環(huán)境下基于網(wǎng)絡(luò)博弈的任務(wù)調(diào)度算法》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、山東師范大學(xué)碩士學(xué)位論文攻讀碩士學(xué)位期間發(fā)表的論文及參與的科研項(xiàng)目.........................59致謝...............................................................60III萬(wàn)方數(shù)據(jù)山東師范大學(xué)碩士學(xué)位論文摘要云計(jì)算是一種新的計(jì)算模式，它通過(guò)服務(wù)的形式為用戶(hù)提供各種資源。云計(jì)算的正常運(yùn)行離不開(kāi)虛擬化技術(shù)。云計(jì)算中，利用虛擬化技術(shù)，將物理服務(wù)器的資源映射到虛擬機(jī)層，在一個(gè)服務(wù)器上部署多個(gè)虛擬機(jī)，利用虛擬機(jī)來(lái)執(zhí)行用戶(hù)任務(wù)，這樣

2、不但提高了服務(wù)器的資源利用率，同時(shí)保證了不同用戶(hù)的應(yīng)用程序的獨(dú)立性。近年來(lái)，越來(lái)越多的企業(yè)架構(gòu)了自己的云服務(wù)器，云計(jì)算系統(tǒng)需要有滿(mǎn)足自身用戶(hù)需要的資源分配和任務(wù)調(diào)度策略，目前還沒(méi)有相關(guān)的任務(wù)調(diào)度標(biāo)準(zhǔn)。因此，對(duì)云計(jì)算環(huán)境下的任務(wù)調(diào)度算法研究具有重要的理論和現(xiàn)實(shí)意義。本文分析了云計(jì)算環(huán)境下的任務(wù)調(diào)度法算的研究現(xiàn)狀，總結(jié)了云計(jì)算這一新興商業(yè)模式的獨(dú)有的特點(diǎn)，對(duì)現(xiàn)有調(diào)度算法存在的問(wèn)題進(jìn)行了深入分析，然后分別針對(duì)獨(dú)立型和依賴(lài)型兩類(lèi)任務(wù)，提出了兩種任務(wù)調(diào)度算法。此外，考慮了用戶(hù)對(duì)云計(jì)算中心虛擬機(jī)資源的不同偏好性，針對(duì)多

3、用戶(hù)類(lèi)，設(shè)計(jì)了多準(zhǔn)則的任務(wù)調(diào)度算法?？傮w來(lái)說(shuō)，本文主要完成了以下工作：⑴針對(duì)云計(jì)算環(huán)境下的獨(dú)立型任務(wù)，現(xiàn)有的調(diào)度方法一般包括遺傳算法、蟻群算法、模擬退火算法等智能算法，這些算法收斂的速度較快，但是容易陷入局部最優(yōu)，并且算法過(guò)度依靠適應(yīng)度函數(shù)的設(shè)計(jì)，算法復(fù)雜度較高?？紤]到這類(lèi)隨機(jī)算法的劣勢(shì)，我們從博弈論的角度分析云計(jì)算環(huán)境下的任務(wù)調(diào)度問(wèn)題，設(shè)計(jì)了一個(gè)任務(wù)調(diào)度博弈模型，將所有用戶(hù)任務(wù)作為博弈的參與者，所選擇的虛擬機(jī)作為博弈策略，以任務(wù)處理時(shí)延作為博弈參與者的效用函數(shù)。找到了博弈的勢(shì)函數(shù)，證明了博弈是一個(gè)勢(shì)博弈，

4、并且博弈存在Nash均衡，利用數(shù)學(xué)分析，證明了該博弈的穩(wěn)定點(diǎn)就是勢(shì)函數(shù)的最小值點(diǎn)。此外，提出了一種基于勢(shì)博弈的任務(wù)調(diào)度算法，算法能夠求解博弈到達(dá)穩(wěn)定點(diǎn)時(shí)各個(gè)虛擬機(jī)上的任務(wù)量分布狀態(tài)。仿真實(shí)驗(yàn)表明，該調(diào)度算法能降低任務(wù)的整體處理時(shí)延，并且能使系統(tǒng)的負(fù)載均衡程度自適應(yīng)于用戶(hù)任務(wù)量的變化，當(dāng)任務(wù)量較少時(shí)，開(kāi)啟較少的虛擬機(jī)資源，減少系統(tǒng)的開(kāi)銷(xiāo)，當(dāng)任務(wù)量較多時(shí)，開(kāi)啟較多的虛擬機(jī)資源，保證任務(wù)的QoS。此外，考慮了虛擬機(jī)的閾值限制，對(duì)所提算法進(jìn)行了擴(kuò)展，將虛擬機(jī)閾值限制這一參數(shù)I萬(wàn)方數(shù)據(jù)山東師范大學(xué)碩士學(xué)位論文加入到算

5、法中，使得算法更具有一般性。⑵針對(duì)依賴(lài)型任務(wù)，分析了任務(wù)的DAG圖，主要研究了Fork-Join型任務(wù)圖，針對(duì)該類(lèi)任務(wù)，基于網(wǎng)絡(luò)博弈論中的Wardrop均衡原理，給出了以全體用戶(hù)任務(wù)處理時(shí)延作為代價(jià)函數(shù)的博弈分析，考慮網(wǎng)絡(luò)中全體用戶(hù)任務(wù)，將求解全體用戶(hù)的系統(tǒng)最優(yōu)問(wèn)題轉(zhuǎn)化為求解單個(gè)用戶(hù)的用戶(hù)最優(yōu)問(wèn)題，設(shè)計(jì)了一個(gè)針對(duì)該任務(wù)的調(diào)度算法，該算法能夠求解Wardrop均衡理論中的系統(tǒng)最優(yōu)狀態(tài)。最后，對(duì)此算法進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)表明，相比于單個(gè)用戶(hù)最優(yōu)的求解算法，該算法能夠較快的完成用戶(hù)任務(wù)，并且使整個(gè)云計(jì)算用戶(hù)任務(wù)達(dá)

6、到系統(tǒng)最優(yōu)。⑶針對(duì)云計(jì)算用戶(hù)任務(wù)對(duì)虛擬機(jī)資源具有不同的偏向性，對(duì)多用戶(hù)類(lèi)多準(zhǔn)則的任務(wù)調(diào)度進(jìn)行了研究。在云計(jì)算環(huán)境下，有些用戶(hù)偏向于選擇處理時(shí)延小的虛擬機(jī)資源，有些用戶(hù)偏向于選擇費(fèi)用低的虛擬機(jī)資源，有些用戶(hù)偏向于選擇更加安全的虛擬機(jī)資源。根據(jù)用戶(hù)的偏好性不同，將網(wǎng)絡(luò)中的用戶(hù)分為多類(lèi)用戶(hù)，只考慮費(fèi)用和時(shí)間這兩種指標(biāo)，為這多類(lèi)用戶(hù)同時(shí)競(jìng)爭(zhēng)虛擬機(jī)資源時(shí)設(shè)計(jì)了博弈模型，找到了博弈的勢(shì)函數(shù)，證明了該博弈為一個(gè)勢(shì)博弈，同時(shí)證明了博弈存在Nash均衡，并且Nash均衡與勢(shì)函數(shù)的最大值等價(jià)。最后，提出了一種基于多用戶(hù)類(lèi)多準(zhǔn)則

7、的任務(wù)調(diào)度算法，求解博弈達(dá)到均衡時(shí)的各個(gè)虛擬機(jī)上任務(wù)量的狀態(tài)分布。算法的仿真實(shí)驗(yàn)表明，所提算法具有收斂性，算法的求解結(jié)果與所有自私用戶(hù)經(jīng)過(guò)自由博弈后所得到的穩(wěn)定狀態(tài)是相同的，進(jìn)一步說(shuō)明了該算法的有效性及可行性。關(guān)鍵詞：云計(jì)算；任務(wù)調(diào)度算法；網(wǎng)絡(luò)博弈；任務(wù)依賴(lài)；勢(shì)博弈分類(lèi)號(hào)：TP393II萬(wàn)方數(shù)據(jù)山東師范大學(xué)碩士學(xué)位論文TaskSchedulingAlgorithmsBasedonNetworkGameinCloudComputingEnvironmentAbstractCloudcomputingisane

8、wcomputingmodel,whichprovidesavarietyofresourcesforusersthroughthemodeofservice.Cloudcomputing’snormaloperationisinseparablefromvirtualizationtechnology.Cloudcomputingmapstheresourcesofthephysicalservertoavir