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

1、網(wǎng)格是一種先進的信息技術(shù)基礎(chǔ)設(shè)施,目的是有效整合Internet上廣泛分布的各種計算資源、存儲資源、通信資源、信息資源等,向用戶提供虛擬、統(tǒng)一、透明的計算環(huán)境。網(wǎng)格的重要性已經(jīng)受到多個國家和政府的關(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)準的確立,“面向服務(wù)”成為近些年網(wǎng)格發(fā)展的方向

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

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

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

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

6、留時,針對于搶占式任務(wù)和非搶占式任務(wù)的調(diào)度策略。前者可以通過對已有調(diào)度策略的改進來實現(xiàn)；后者則被建模為一個多組裝箱(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ā)式裝箱算法。通過理論分析和模擬實驗

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

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

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