郭紹翠，楊 旭

GUO Shao-cui,YANG Xu

（煙臺(tái)職業(yè)學(xué)院，煙臺(tái) 264670）

0 引言

網(wǎng)格資源是由地理上分布的、隸屬不同機(jī)構(gòu)、異構(gòu)的各類計(jì)算資源、存儲(chǔ)資源等組成，由于資源構(gòu)成的復(fù)雜性，因而在網(wǎng)格環(huán)境下資源管理存在以下難點(diǎn)[1,2]：資源隸屬于不同的機(jī)構(gòu)，不同的機(jī)構(gòu)對(duì)于本地計(jì)算資源有不同的使用策略，因而在網(wǎng)格環(huán)境下對(duì)資源的管理不存在統(tǒng)一的管理策略。

由于在網(wǎng)格環(huán)境下資源的供給與需求是動(dòng)態(tài)變化的，相應(yīng)地均衡價(jià)格需實(shí)時(shí)反映資源的供需動(dòng)態(tài)變化，為此，本文提出分布分組調(diào)價(jià)算法。運(yùn)用經(jīng)濟(jì)學(xué)原理研究網(wǎng)格資源集中式調(diào)價(jià)算法[3]和分布調(diào)價(jià)WALRAS 算法的性能在文獻(xiàn)[4]中進(jìn)行了比較。分布式單獨(dú)調(diào)價(jià)方法的優(yōu)點(diǎn)非常適合于分布系統(tǒng)；本文提出的分布分組調(diào)價(jià)算法，結(jié)合集中式調(diào)價(jià)算法收斂速度快的特點(diǎn)，改進(jìn)分布式WALRAS算法，使得在網(wǎng)格環(huán)境下資源供需發(fā)生變化后資源價(jià)格能夠快速調(diào)整到均衡價(jià)格。

1 資源調(diào)價(jià)的系統(tǒng)框架

如圖1所示，在網(wǎng)格系統(tǒng)中，系統(tǒng)對(duì)資源的需求隨時(shí)間動(dòng)態(tài)變化，相應(yīng)資源的價(jià)格也隨時(shí)間動(dòng)態(tài)變化。為實(shí)現(xiàn)資源價(jià)格調(diào)整，在系統(tǒng)中存在兩類Agent[5]：一類Agent是管理本地的資源域，稱為資源域Agent(R-Agent)，通常R-Agent與資源域中的各類資源和網(wǎng)格應(yīng)用處于同一機(jī)構(gòu)的局域網(wǎng)中，并且R-Agent負(fù)責(zé)根據(jù)當(dāng)前的資源價(jià)格收集該資源域內(nèi)資源供需情況，形成該資源域的超額需求；另一類Agent負(fù)責(zé)整個(gè)系統(tǒng)中某一資源組的價(jià)格調(diào)整，即調(diào)整這一組資源的價(jià)格，使得這一組資源在整個(gè)系統(tǒng)中的供需均衡，此類Agent稱為資源組調(diào)價(jià)器(R-Auctioneer)，R-Auctioneer處在廣域網(wǎng)范圍中，與R-Agent通過網(wǎng)格中間件提供的安全通信功能進(jìn)行通信。

圖1 資源調(diào)價(jià)的系統(tǒng)框架

網(wǎng)格資源調(diào)價(jià)系統(tǒng)由上述兩類Agent組成，通常當(dāng)系統(tǒng)資源供需發(fā)生變化后，調(diào)價(jià)過程需要反復(fù)循環(huán)調(diào)價(jià)，直至達(dá)到新的均衡價(jià)格。對(duì)于每次循環(huán)調(diào)價(jià)，R-Agent和R-Auctioneer需要通過網(wǎng)格中間件在廣域網(wǎng)范圍中進(jìn)行通信，因此一種有效的調(diào)價(jià)算法，需要降低調(diào)價(jià)的通信開銷，最有效的方式即是減少一次調(diào)價(jià)過程所需的循環(huán)調(diào)價(jià)次數(shù)。

2 分布分組調(diào)價(jià)算法

網(wǎng)格系統(tǒng)由各種不同類型的資源組成，不同類型資源的價(jià)格相關(guān)程度存在差異。資源組內(nèi)一種資源價(jià)格的變化導(dǎo)致同組內(nèi)的其他資源價(jià)格有明顯的變化，而引起該資源組外的資源價(jià)格變化較小。分布分組算法包括R-Auctioneer的算法和R-Agent的算法，分別如下所示：

設(shè)網(wǎng)格系統(tǒng)中資源域總數(shù)為M，網(wǎng)格系統(tǒng)中資源總數(shù)為N，根據(jù)價(jià)格相關(guān)性將系統(tǒng)資源分成G個(gè)組，相應(yīng)地R-Auctioneer的數(shù)目為G，設(shè)資源組k中的資源種類為nk ，則有

資源組k的價(jià)格通過R-Auctioneer k進(jìn)行調(diào)節(jié)，對(duì)于R-Auctioneer k執(zhí)行以下算法：

1）確定資源組內(nèi)資源的初始價(jià)格p0k，設(shè)為前一次調(diào)價(jià)所得的均衡價(jià)格。

2）接收M個(gè)R-Agent提交的超額需求函數(shù)zi(pk)，得到

3）迭代求解新的資源價(jià)格pk。利用多元函數(shù)的Taylor 公式,在p0k 處線性化展開，可得近似公式

其中,Z'(pk) 是向量函數(shù)Z(pk) 的一階導(dǎo)數(shù),為一矩陣[ Z'i j ] nk'×nk，其中

通過式(4) 得到新的價(jià)格矢量pk，再將新得到的pk作為式(4) 中的p0k 計(jì)算新的價(jià)格矢量，這樣迭代直到Z(pk) 〈ε停止，記此時(shí)的pk 為p3k，其中ε為均衡閾值。

4）計(jì)算價(jià)格變化幅度。

根據(jù)價(jià)格閾值δ，確定價(jià)格波動(dòng)標(biāo)記fpk=0，Am〈δ，1，Am≥δ。

5）發(fā)送新的價(jià)格矢量pk和價(jià)格波動(dòng)標(biāo)記fp給所有的R-Agent，每個(gè)R-Agent從G個(gè)R-Auctioneer接收到新的資源價(jià)格p3k和價(jià)格波動(dòng)標(biāo)記fpk，其中k =1,2,...,G，形成全體資源的新價(jià)格矢量p={p31,p2 ,...,p3G}，以及價(jià)格波動(dòng)標(biāo)記Fp ={fp1,f p2,...,f pG}1如果Fp=0，即新價(jià)格p滿足全體資源超額需求Z(p)≈0，則p為均衡價(jià)格，記為p3。如果Fp≠0，每個(gè)R-Agent 則需要計(jì)算新的超額需求函數(shù)，算法如下：對(duì)于R-Agent i，有

for (k=1；k≤G；k++)

（1）固定資源組j 的價(jià)格矢量pj，j=1,2,...,G，j ≠k；

（2）計(jì)算該資源域關(guān)于pk的資源組k超額需求函數(shù)zi(pk)；

（3）發(fā)送zi (pk) 到R2Auctioneer k；Endfor

當(dāng)網(wǎng)格資源的供需發(fā)生變化后,系統(tǒng)中的R-Auctioneer和R-Agent分別循環(huán)執(zhí)行上述算法,直到Fp=0，表示形成新的均衡價(jià)格p，即完成一次調(diào)價(jià)過程。調(diào)度系統(tǒng)即可根據(jù)資源價(jià)格和資源分配策略實(shí)現(xiàn)有效的資源調(diào)價(jià)。

3 性能分析及實(shí)驗(yàn)

本文提出的分布分組算法，根據(jù)資源價(jià)格的相關(guān)程度將系統(tǒng)資源分成若干資源組，采用WALRAS算法的分布方式對(duì)各資源組分別進(jìn)行調(diào)價(jià)，同時(shí)結(jié)合集中式同步調(diào)價(jià)的優(yōu)點(diǎn)，在資源組內(nèi)根據(jù)該組資源供需均衡同步調(diào)整價(jià)格1因此，當(dāng)系統(tǒng)資源供需發(fā)生變化后資源價(jià)格可以快速調(diào)整到均衡價(jià)格1表1表明，當(dāng)資源供需發(fā)生變化后分布分組算法調(diào)整價(jià)格到均衡價(jià)格的速度比WALRAS 算法快約30%，對(duì)于情況(1)，WALRAS算法調(diào)價(jià)到均衡價(jià)格的調(diào)價(jià)循環(huán)次數(shù)為25 次，而對(duì)于分布分組算法的調(diào)價(jià)循環(huán)次數(shù)為17 次；對(duì)于情況(2)，WALRAS 算法調(diào)價(jià)到均衡價(jià)格的調(diào)價(jià)循環(huán)次數(shù)為26 次，而對(duì)于分布分組算法的調(diào)價(jià)循環(huán)次數(shù)為18 次。

表1 實(shí)驗(yàn)對(duì)比結(jié)果

4 結(jié)論

通過仿真實(shí)驗(yàn)比較了WALRAS 算法和分布分組算法的性能。與傳統(tǒng)的集中式同步調(diào)價(jià)算法，以及適用于分布式環(huán)境WALRAS 調(diào)價(jià)算法相比，本文提出的分布分組調(diào)價(jià)算法具有以下優(yōu)點(diǎn)：

根據(jù)資源價(jià)格相關(guān)性，將資源分成若干資源組，根據(jù)每一組的資源供需情況分別對(duì)每組資源進(jìn)行調(diào)價(jià)。因此與集中式同步調(diào)價(jià)算法相比較而言具備很好的可擴(kuò)展性，適用于網(wǎng)格環(huán)境下的資源價(jià)格調(diào)整。

[1] LI Lin,Li Taoshen,GE Zhihui.Study on Trust Mechanism of Manufacturing Grid[J].軟件學(xué)報(bào),2009：51-53.

[2] 馬滿福,吳健,胡正國(guó),等.網(wǎng)格計(jì)算資源管理中的信譽(yù)度模型[J].計(jì)算機(jī)應(yīng)用2005,25(1)：61-64.

[3] 鄧曉衡,盧錫城,王懷民.基于可信評(píng)價(jià)的資源調(diào)度研究[J].計(jì)算機(jī)學(xué)報(bào),2007,30(10)：1750-1762.

[4] Liu Yan-ling BAI Bao-xing.Trust Model for P2P Networks Based on Relationship Set[J].Journal of Jilin University.2009,02：67-68

[5] 陳建剛,王汝傳,張琳.基于模糊集合的網(wǎng)格資源訪問的信任機(jī)制[J].計(jì)算機(jī)學(xué)報(bào),2009,8：1676-1682.