基于非完全信息博弈的網(wǎng)格資源分配策略研究.pdf

1、網(wǎng)格計(jì)算作為一種基于高速網(wǎng)絡(luò)、面向大區(qū)域的高性能并行和分布式計(jì)算，將地理上分布的、隸屬于不同機(jī)構(gòu)的計(jì)算、存儲等資源構(gòu)成一臺虛擬的超級巨型機(jī)，完成以往單機(jī)乃至機(jī)群都無法解決的高復(fù)雜性計(jì)算問題。其中資源管理在網(wǎng)格體系中一直是個(gè)復(fù)雜而艱巨的問題。本文針對網(wǎng)格環(huán)境中資源的動(dòng)態(tài)、異構(gòu)以及分布的特性，利用微觀經(jīng)濟(jì)學(xué)與統(tǒng)計(jì)學(xué)中的理論研究了一種優(yōu)化網(wǎng)格資源分配的新方法。研究目標(biāo)是提高資源分配效率并驗(yàn)證該方法的正確性。本文從資源分配模型，理論證明，實(shí)驗(yàn)?zāi)?/p>

2、擬三個(gè)層面上對該方法進(jìn)行了分析。具體的研究工作主要分為以下幾個(gè)方面：
　　 (1)分析了開放式網(wǎng)格體系結(jié)構(gòu)(Open Grid Services Architecture，OGSA)和五層沙漏式結(jié)構(gòu)，在此基礎(chǔ)上對三種用于網(wǎng)格資源管理的模型(層次模型，抽象所有者模型和市場經(jīng)濟(jì)模型)進(jìn)行對比研究，著重論述了市場經(jīng)濟(jì)模型在網(wǎng)格計(jì)算環(huán)境下公平，高效，便捷等特點(diǎn)。分析了近年來解決市場網(wǎng)格資源分配問題的幾種模型，并總結(jié)了資源分配領(lǐng)域的幾大矛

3、盾問題以及目前解決方法中存在的主要不足。
　　 (2)分析比對多種市場經(jīng)濟(jì)網(wǎng)格環(huán)境下資源分配模型的基礎(chǔ)之上，提出一種“多贏家”式的網(wǎng)格資源拍賣模型(Multi-Winners AuctionModel，MWAM)，即多個(gè)用戶競拍一種網(wǎng)格資源。它基于非完全信息博弈理論，通過制定明確的規(guī)則，讓競拍者通過價(jià)格競爭來確定最終競拍價(jià)，在資源提供者未能給待拍資源定價(jià)以及競拍者彼此獨(dú)立的情況下公平，靈活地形成竟拍價(jià)，即納什均衡解，并且達(dá)到利益

4、的最優(yōu)化。其快速，公平，可靠的特性以及代價(jià)小，便于交易協(xié)議的開發(fā)等優(yōu)點(diǎn)非常適合網(wǎng)格環(huán)境異構(gòu)與分布式的特性。
　　 (3)首次將隱馬爾科夫預(yù)測模型(Hidden Markov Prediction Model，HMPM)應(yīng)用到對網(wǎng)格用戶出價(jià)的預(yù)測上。建立了離散時(shí)間的HMM模型并對之前t-1個(gè)時(shí)刻在以每個(gè)用戶提交的資源需求{r1,r2,…，rt-1}為可觀測狀態(tài)序列條件下本輪分配中用戶使用資源的單位出價(jià)狀態(tài)進(jìn)行預(yù)測，從而計(jì)算出其能獲

5、得所需資源的概率。HMM理論對在網(wǎng)格計(jì)算這一高度動(dòng)態(tài)，異構(gòu)且隨機(jī)的環(huán)境下資源使用者與提供者的行為進(jìn)行了恰當(dāng)?shù)臄?shù)學(xué)描述，使得預(yù)測結(jié)果更加準(zhǔn)確，從而提高了資源分配的效率。
　　 (4)從理論上證明了“多贏家”式分配方法的可行性。且可以最大化系統(tǒng)收益。MWAM作為以經(jīng)濟(jì)學(xué)理論為依托的網(wǎng)格資源分配模型，本文從納什均衡解的存在性，激勵(lì)相容性，個(gè)人理性，系統(tǒng)收益這幾方面分析證明了其適用性與高效性。
　　 (5)通過實(shí)驗(yàn)?zāi)M驗(yàn)證了WM

6、AM在網(wǎng)格中的可行性與其自身優(yōu)勢。實(shí)驗(yàn)一方面對HMM預(yù)測的準(zhǔn)確性，以及WMAM在市場網(wǎng)格中的適用性做了縱向分析：另一方面選取序貫博弈資源分配算法，雙向拍賣分配算法，基于Qos的資源分配算法，以及“第一價(jià)格”拍賣算法，“第二價(jià)格”拍賣算法同本文的“多贏家”算法進(jìn)行橫向比較，從不同層面驗(yàn)證了結(jié)論。
　　 通過對理論證明與實(shí)驗(yàn)結(jié)果的分析可知，本文提出的“多贏家”式資源分配方法滿足微觀經(jīng)濟(jì)學(xué)中的激勵(lì)相容性與個(gè)人理性，有較大的準(zhǔn)確性與靈活