基于市場機制的網(wǎng)格資源調(diào)價算法

郭紹翠，楊 旭

GUO Shao-cui,YANG Xu

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4）計算價格變化幅度。

根據(jù)價格閾值δ，確定價格波動標記fpk=0，Am〈δ，1，Am≥δ。

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

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

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

（2）計算該資源域關(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，表示形成新的均衡價格p，即完成一次調(diào)價過程。調(diào)度系統(tǒng)即可根據(jù)資源價格和資源分配策略實現(xiàn)有效的資源調(diào)價。

3 性能分析及實驗

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

表1 實驗對比結(jié)果

4 結(jié)論

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

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

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

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

[3] 鄧曉衡,盧錫城,王懷民.基于可信評價的資源調(diào)度研究[J].計算機學(xué)報,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].計算機學(xué)報,2009,8：1676-1682.