網(wǎng)格任務(wù)調(diào)度中服務(wù)質(zhì)量保證相關(guān)問題研究.pdf

1、網(wǎng)格是一種先進(jìn)的信息技術(shù)基礎(chǔ)設(shè)施,目的是有效整合Internet上廣泛分布的各種計(jì)算資源、存儲(chǔ)資源、通信資源、信息資源等,向用戶提供虛擬、統(tǒng)一、透明的計(jì)算環(huán)境。網(wǎng)格的重要性已經(jīng)受到多個(gè)國家和政府的關(guān)注,并吸引了大量的研究。合理、有效地調(diào)度網(wǎng)格任務(wù)可以充分利用網(wǎng)格資源,提高系統(tǒng)效率,更好地完成用戶的網(wǎng)格應(yīng)用,因此網(wǎng)格任務(wù)調(diào)度問題成為網(wǎng)格研究的重要內(nèi)容之一。隨著開放網(wǎng)格服務(wù)體系結(jié)構(gòu)(OGSA)標(biāo)準(zhǔn)的確立,“面向服務(wù)”成為近些年網(wǎng)格發(fā)展的方向

2、,服務(wù)質(zhì)量(QoS)成為網(wǎng)格任務(wù)調(diào)度過程中必須要考慮的一個(gè)重要因素?！熬W(wǎng)格之父”IanFoster更是把提供非平凡的服務(wù)質(zhì)量作為網(wǎng)格的判斷標(biāo)準(zhǔn)之一。由于網(wǎng)格具有動(dòng)態(tài)性和自治性的特點(diǎn),QoS保證是一項(xiàng)非常復(fù)雜和具有挑戰(zhàn)性的工作。資源預(yù)留是實(shí)現(xiàn)QoS保證的有效手段,但也會(huì)產(chǎn)生“資源碎片問題”,影響非預(yù)留任務(wù)的完成效果。如何在有效使用資源預(yù)留的同時(shí)減少它所帶來的不良后果成為一個(gè)很有意義的研究內(nèi)容。網(wǎng)格經(jīng)濟(jì)(Grid Economy)的出現(xiàn)為網(wǎng)

3、格資源管理提供了一個(gè)公共的解決方案,其中雙向拍賣模型被廣泛地應(yīng)用于網(wǎng)格資源分配中。但目前基于雙向拍賣的網(wǎng)格資源分配和任務(wù)調(diào)度大多直接使用經(jīng)濟(jì)學(xué)領(lǐng)域中已有的拍賣理論,僅僅關(guān)注于用戶的經(jīng)濟(jì)收益,而對(duì)服務(wù)質(zhì)量的有效保證重視不夠。目前,服務(wù)網(wǎng)格是網(wǎng)格構(gòu)建的主流方向之一。在服務(wù)網(wǎng)格環(huán)境下,調(diào)度器需要根據(jù)用戶的即時(shí)要求,動(dòng)態(tài)地把大量臨時(shí)性的網(wǎng)格服務(wù)組合為可增值的復(fù)合服務(wù)。因此,需要一種服務(wù)調(diào)度機(jī)制來實(shí)現(xiàn)網(wǎng)格服務(wù)的組合、匹配,同時(shí)向用戶提供所需的服務(wù)

4、質(zhì)量。
　　 本文針對(duì)在網(wǎng)格任務(wù)調(diào)度過程中與服務(wù)質(zhì)量保證相關(guān)的若干問題進(jìn)行了研究,具體工作從對(duì)服務(wù)質(zhì)量保證的“事先規(guī)劃”和“事中注意”兩個(gè)方面開展。前者涉及了與資源預(yù)留相關(guān)的任務(wù)調(diào)度問題；后者聚焦于如何把用戶服務(wù)質(zhì)量需求映射到基于經(jīng)濟(jì)機(jī)制的資源分配和網(wǎng)格服務(wù)調(diào)度中。本文取得的主要?jiǎng)?chuàng)新成果如下:
　　 1.提出了一種模糊的網(wǎng)格資源預(yù)留機(jī)制FRRM。傳統(tǒng)的資源預(yù)留機(jī)制在預(yù)留任務(wù)實(shí)際使用資源之前就完成了資源分配,無法應(yīng)對(duì)在預(yù)留

5、提前時(shí)間內(nèi)資源的動(dòng)態(tài)變化。FRRM能夠感知預(yù)留提前時(shí)間內(nèi)資源狀態(tài)的變化,根據(jù)資源的運(yùn)行時(shí)信息動(dòng)態(tài)地調(diào)度已接納的預(yù)留請(qǐng)求。引入了資源-預(yù)留圖對(duì)FRRM下的預(yù)留請(qǐng)求接納控制以及預(yù)留任務(wù)調(diào)度策略進(jìn)行描述,分析了FRRM對(duì)資源故障的容錯(cuò)性。分別在模擬任務(wù)集和真實(shí)任務(wù)集上進(jìn)行了FRRM和傳統(tǒng)預(yù)留機(jī)制的對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明FRRM能夠顯著減小任務(wù)搶占代價(jià),有效提高資源利用率,對(duì)網(wǎng)格的動(dòng)態(tài)環(huán)境具有更好的適應(yīng)性。
　　 2.給出了當(dāng)存在資源預(yù)

6、留時(shí),針對(duì)于搶占式任務(wù)和非搶占式任務(wù)的調(diào)度策略。前者可以通過對(duì)已有調(diào)度策略的改進(jìn)來實(shí)現(xiàn)；后者則被建模為一個(gè)多組裝箱(Multi-line Bin Packing,MBP)問題。提出了Multi2Single算法把MBP問題轉(zhuǎn)化為具有相同最優(yōu)化目標(biāo)的單組裝箱(Single-line Bin Packing,SBP)問題,并在經(jīng)典裝箱(Bin Packing,BP)問題研究的基礎(chǔ)上給出了解決SBP問題的啟發(fā)式裝箱算法。通過理論分析和模擬實(shí)驗(yàn)

7、對(duì)裝箱算法的最壞情況漸近性能比和平均性能比進(jìn)行了分析。與傳統(tǒng)的調(diào)度算法Mim-min和Suffrage相比,我們提出的算法可以明顯減小非預(yù)留任務(wù)的最大調(diào)度長度(makespan),有效緩沖了預(yù)留任務(wù)對(duì)非預(yù)留任務(wù)調(diào)度目標(biāo)的不良影響。
　　 3.提出了一種面向可量化網(wǎng)格資源的貪心雙向拍賣協(xié)議GDAP和一種面向網(wǎng)格服務(wù)的服務(wù)質(zhì)量可保證的雙向拍賣協(xié)議QDAP。證明了GDAP具有策略性防偽、個(gè)人理性和弱預(yù)算平衡的特點(diǎn)。與傳統(tǒng)的基于MDA(

8、Multi-unit Double Auction)的拍賣策略相比,GDAP在兼顧經(jīng)濟(jì)效益的同時(shí)能夠大大提高網(wǎng)格資源利用率及用戶滿意率,有利于實(shí)現(xiàn)網(wǎng)格大規(guī)模資源共享的目標(biāo)。QDAP首次把服務(wù)質(zhì)量引入到雙向拍賣協(xié)議中,在最大化服務(wù)利用率的同時(shí)向消費(fèi)者提供有效的服務(wù)質(zhì)量支持。把QDAP與傳統(tǒng)的雙向拍賣策略PMDA和CDA進(jìn)行了實(shí)驗(yàn)對(duì)比,結(jié)果表明QDAP具有更好的拍賣公平性、較高的服務(wù)利用率,更加適應(yīng)于服務(wù)網(wǎng)格環(huán)境。
　　 4.研究了

9、具有多QoS約束的網(wǎng)格服務(wù)調(diào)度問題。以移動(dòng)Agent作為應(yīng)用的載體,通過移動(dòng)Agent在不同服務(wù)實(shí)例之間的遷移來滿足用戶對(duì)復(fù)合網(wǎng)格服務(wù)的訪問需求。提出了一種多QoS約束下基于螞蟻算法的移動(dòng)Agent路由算法(MRBAA),MRBAA支持移動(dòng)Agent對(duì)多個(gè)服務(wù)的并行訪問,并考慮了服務(wù)間的數(shù)據(jù)交互。在MRBAA下,移動(dòng)Agent以最大化用戶效用為目標(biāo)進(jìn)行遷移,同時(shí)兼顧用戶的QoS需求。與快速貪心算法和隨機(jī)選擇算法的對(duì)比實(shí)驗(yàn)表明,MRBAA