云計(jì)算環(huán)境下的自主調(diào)度技術(shù)研究.pdf

1、云計(jì)算是信息技術(shù)革命的產(chǎn)物，是一種大規(guī)模復(fù)雜計(jì)算系統(tǒng)。云計(jì)算系統(tǒng)時(shí)刻都在處理海量數(shù)據(jù)和應(yīng)用任務(wù)，具有高度的動(dòng)態(tài)性。由于云計(jì)算系統(tǒng)具有資源規(guī)模龐大且異構(gòu)多樣、用戶群體廣泛、應(yīng)用任務(wù)類型各異且QoS目標(biāo)約束各異等特性，系統(tǒng)需要頻繁地對(duì)云平臺(tái)中的各種資源與應(yīng)用任務(wù)進(jìn)行實(shí)時(shí)調(diào)度和動(dòng)態(tài)管理。而云計(jì)算作為一種商業(yè)計(jì)算模式，其目的是實(shí)現(xiàn)資源共享與協(xié)同工作，并同時(shí)滿足用戶的服務(wù)請(qǐng)求和云服務(wù)提供商的服務(wù)收益。因此，如何對(duì)云資源進(jìn)行合理的分配，對(duì)海量應(yīng)用任

2、務(wù)進(jìn)行高效管理與實(shí)時(shí)調(diào)度，在確保云計(jì)算系統(tǒng)負(fù)載均衡和提高云資源利用率的前提下，降低用戶的成本，提高云服務(wù)提供商的收益，是目前云計(jì)算環(huán)境下的研究熱點(diǎn)之一。
　　從本質(zhì)上說(shuō)，云計(jì)算環(huán)境下的任務(wù)調(diào)度是需要建立一種應(yīng)用任務(wù)與計(jì)算資源之間合適的映射關(guān)系的調(diào)度策略，其目的是實(shí)現(xiàn)計(jì)算資源的合理分配與應(yīng)用任務(wù)的高效執(zhí)行。早期傳統(tǒng)的分布式計(jì)算系統(tǒng)、網(wǎng)格計(jì)算系統(tǒng)等，通過(guò)系統(tǒng)吞吐量和任務(wù)完成時(shí)間等性能指標(biāo)衡量調(diào)度管理的效果。但是在云計(jì)算環(huán)境下，任務(wù)調(diào)度

3、問(wèn)題往往更加復(fù)雜。首先，云計(jì)算環(huán)境下應(yīng)用任務(wù)請(qǐng)求往往是非集中式的，而且規(guī)模巨大，傳統(tǒng)的集中式的資源管理系統(tǒng)已經(jīng)不再適用，云計(jì)算系統(tǒng)必須以一種分布式的并行模式對(duì)任務(wù)和資源進(jìn)行調(diào)度與管理；其次，云資源通常來(lái)自不同的云服務(wù)提供商，各個(gè)機(jī)構(gòu)的云資源往往是異構(gòu)的，如何將各種異構(gòu)資源組合成完整的服務(wù)提供給用戶是非常復(fù)雜的；再者，由于云計(jì)算系統(tǒng)具有動(dòng)態(tài)可擴(kuò)展的性質(zhì)，相應(yīng)的任務(wù)調(diào)度也必須滿足可擴(kuò)展性與自適應(yīng)性；然后，云計(jì)算作為一種商業(yè)模式，云服務(wù)提供商

4、首先要考慮的是如何提高自身的資源利用率，提升共享使用率從而降低成本，獲得盡可能多的服務(wù)收益，這就使得任務(wù)調(diào)度必須考慮云計(jì)算系統(tǒng)的整體負(fù)載均衡問(wèn)題。最后，從用戶的角度而言，云服務(wù)提供商所提供的服務(wù)是否滿足用戶任務(wù)調(diào)度的QoS多目標(biāo)需求是任務(wù)調(diào)度策略必須考慮的問(wèn)題。
　　因此，針對(duì)上述目前云計(jì)算環(huán)境下任務(wù)調(diào)度存在的問(wèn)題，本文對(duì)云環(huán)境下的任務(wù)調(diào)度技術(shù)做了詳細(xì)而系統(tǒng)的研究，其主要內(nèi)容包括四個(gè)方面：云環(huán)境下用戶任務(wù)調(diào)度的QoS多目標(biāo)優(yōu)化問(wèn)題

5、、云資源利用率與云計(jì)算系統(tǒng)負(fù)載均衡問(wèn)題、云計(jì)算系統(tǒng)任務(wù)調(diào)度策略執(zhí)行效率問(wèn)題、用戶任務(wù)調(diào)度成本與云服務(wù)提供商服務(wù)收益問(wèn)題。本文在對(duì)這些問(wèn)題進(jìn)行深入研究的基礎(chǔ)上，設(shè)計(jì)了一套云計(jì)算環(huán)境下的自主調(diào)度體系架構(gòu)，并對(duì)其中重要功能都給出了詳細(xì)的算法與實(shí)驗(yàn)結(jié)果。論文的主要研究?jī)?nèi)容包括以下幾個(gè)方面：
　　1）在分析和研究了云計(jì)算環(huán)境下任務(wù)調(diào)度存在的問(wèn)題及目標(biāo)要求的基礎(chǔ)上，提出了一種云計(jì)算環(huán)境下的自主調(diào)度體系架構(gòu)。在自主調(diào)度體系架構(gòu)中，系統(tǒng)為每個(gè)向云

6、計(jì)算系統(tǒng)請(qǐng)求服務(wù)的用戶創(chuàng)建一個(gè)云代理進(jìn)行智能分析和決策，并為每個(gè)云代理設(shè)計(jì)了分析、評(píng)估、博弈等功能與算法。本文通過(guò)對(duì)云代理功能進(jìn)行分類，設(shè)計(jì)了一個(gè)兩層的自上而下的自主調(diào)度模型。其中，針對(duì)用戶與云服務(wù)提供商之間的協(xié)商問(wèn)題，設(shè)計(jì)了云代理協(xié)商模型。云代理通過(guò)一系列約束規(guī)則與目標(biāo)規(guī)則選擇符合用戶QoS目標(biāo)約束的SLA協(xié)議，并對(duì)SLA協(xié)議進(jìn)行評(píng)估。其次，針對(duì)多個(gè)用戶對(duì)關(guān)鍵資源的競(jìng)爭(zhēng)而導(dǎo)致的資源沖突問(wèn)題，設(shè)計(jì)了云代理博弈模型。云代理將系統(tǒng)全局收益函

7、數(shù)引入到用戶個(gè)體的收益函數(shù)中，在滿足用戶QoS多目標(biāo)優(yōu)化需求的前提下，云代理之間通過(guò)自主競(jìng)爭(zhēng)博弈的模式，使整個(gè)系統(tǒng)達(dá)成全局利益最優(yōu)。云代理通過(guò)協(xié)商、自主博弈的方式實(shí)現(xiàn)了用戶任務(wù)的自主調(diào)度，提高了任務(wù)調(diào)度策略的執(zhí)行效率，并且降低了用戶的調(diào)度成本，也提高了云服務(wù)提供商的服務(wù)收益。
　　2）針對(duì)在云計(jì)算環(huán)境下，用戶如何判斷云服務(wù)提供商在SLA中承諾的資源是否滿足用戶任務(wù)的QoS需求，本文提出了一種星型結(jié)構(gòu)下的SLA任務(wù)調(diào)度評(píng)估算法。該算

8、法通過(guò)云代理將云服務(wù)提供商SLA中承諾的資源抽象為標(biāo)準(zhǔn)的虛擬資源，并將用戶任務(wù)與虛擬資源的映射關(guān)系抽象為星型拓?fù)浣Y(jié)構(gòu)的云計(jì)算系統(tǒng)。通過(guò)評(píng)估云計(jì)算系統(tǒng)的性能與可靠性，評(píng)估相應(yīng)云服務(wù)提供商所承諾的資源的服務(wù)質(zhì)量。用戶將SLA中承諾的服務(wù)質(zhì)量作為一種判斷標(biāo)準(zhǔn)，判斷云服務(wù)提供商提供的服務(wù)是否能夠滿足用戶任務(wù)的QoS需求。
　　3）針對(duì)用戶任務(wù)調(diào)度的QoS多目標(biāo)優(yōu)化問(wèn)題，提出了一種基于NSGA-II的多目標(biāo)優(yōu)化調(diào)度算法。云計(jì)算環(huán)境下，用戶如

9、何在一組有效的SLA集合中，選出符合其QoS多目標(biāo)優(yōu)化需求的調(diào)度策略依然是非常困難的問(wèn)題。用戶請(qǐng)求的任務(wù)集通常包含多個(gè)任務(wù)，每個(gè)任務(wù)都可以和不同的云服務(wù)提供商簽訂SLA協(xié)議，整個(gè)任務(wù)集的SLA協(xié)議由單個(gè)任務(wù)的SLA協(xié)議組合而成，組合過(guò)程往往呈現(xiàn)出指數(shù)級(jí)的復(fù)雜度。另一方面，用戶的QoS目標(biāo)之間往往是沖突的，例如，服務(wù)時(shí)間和服務(wù)成本之間是沖突的，要獲得快速響應(yīng)的服務(wù)，就需要計(jì)算能力較高的資源，而計(jì)算能力越高其成本就越高，必然無(wú)法同時(shí)滿足兩個(gè)

10、目標(biāo)。本文提出的算法為用戶提供了一種高效快速的選擇機(jī)制，通過(guò)NSGA-II算法對(duì)多個(gè)目標(biāo)進(jìn)行并行搜索，與傳統(tǒng)的將多個(gè)目標(biāo)轉(zhuǎn)化為單目標(biāo)問(wèn)題相比，本文的算法能夠在滿足用戶QoS多目標(biāo)優(yōu)化需求的前提下，高效地為其選擇合理的最優(yōu)的SLA任務(wù)調(diào)度策略。
　　4）在已經(jīng)簽訂了SLA協(xié)議的情況下，用戶任務(wù)選擇SLA中不同的云資源構(gòu)成了不同的任務(wù)調(diào)度策略。針對(duì)如何判斷哪些調(diào)度策略滿足用戶的QoS多目標(biāo)優(yōu)化需求，提出了一種虛擬樹(shù)型結(jié)構(gòu)下的調(diào)度評(píng)估算

11、法。根據(jù)云資源的性質(zhì)，將用戶任務(wù)與云資源的映射關(guān)系建模為由網(wǎng)絡(luò)連接起來(lái)的虛擬樹(shù)型結(jié)構(gòu)。在樹(shù)型結(jié)構(gòu)下，通常需要考慮共享傳輸通道失效引起的共因失效問(wèn)題。針對(duì)此問(wèn)題，本文利用最小生成樹(shù)算法對(duì)云資源與傳輸通道進(jìn)行數(shù)學(xué)建模。對(duì)于一個(gè)任務(wù)分配給多個(gè)資源節(jié)點(diǎn)冗余執(zhí)行的情況，只要存在一個(gè)資源節(jié)點(diǎn)不失效，該任務(wù)就能成功完成；對(duì)于多個(gè)任務(wù)共享同一資源的情況，算法通過(guò)在云資源節(jié)點(diǎn)上增加新的分支和葉子節(jié)點(diǎn)，如果是并行任務(wù)就平均分配共享資源，如果是串行任務(wù)則獨(dú)享

12、資源。因此，在樹(shù)型結(jié)構(gòu)下，用戶任務(wù)與云資源之間是一種動(dòng)態(tài)靈活的映射模式。本文提出的算法能夠?qū)θ我庖粋€(gè)任務(wù)調(diào)度策略的服務(wù)質(zhì)量進(jìn)行快速且準(zhǔn)確的評(píng)估，將其應(yīng)用于云代理博弈模型的效用函數(shù)計(jì)算中，在提高每個(gè)用戶的調(diào)度策略執(zhí)行效率的同時(shí)，也提高了云服務(wù)提供商的資源利用率。
　　5）針對(duì)大量用戶同時(shí)提交任務(wù)調(diào)度請(qǐng)求的問(wèn)題，以及多個(gè)用戶之間對(duì)關(guān)鍵資源的競(jìng)爭(zhēng)問(wèn)題，本文在博弈論的基礎(chǔ)上提出了一種基于囚徒困境博弈的多代理自主調(diào)度算法。該算法假設(shè)每個(gè)用戶

13、具有自己的偏好和自私性的特性，總是傾向最大化自己的利益，每個(gè)用戶都只會(huì)選擇對(duì)自己最有利的資源，不管是否對(duì)其他用戶產(chǎn)生影響。由于用戶的個(gè)體理性，形成了囚徒困境，導(dǎo)致了資源分配沖突，比如大多數(shù)用戶都選擇了同一個(gè)資源，使得系統(tǒng)負(fù)載不均衡。算法通過(guò)云代理之間的自主博弈過(guò)程，將云計(jì)算系統(tǒng)的全局效用目標(biāo)融入到每個(gè)用戶的局部效用目標(biāo)中，通過(guò)設(shè)計(jì)云代理之間的博弈規(guī)則和對(duì)應(yīng)的獎(jiǎng)勵(lì)因子，在每個(gè)云代理追求各自效用目標(biāo)的前提下，使得整個(gè)云計(jì)算系統(tǒng)獲得全局最優(yōu)收