基于市場機制的網格資源調價算法

郭紹翠，楊 旭

GUO Shao-cui,YANG Xu

（煙臺職業學院，煙臺 264670）

0 引言

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

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

1 資源調價的系統框架

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

圖1 資源調價的系統框架

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

2 分布分組調價算法

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

設網格系統中資源域總數為M，網格系統中資源總數為N，根據價格相關性將系統資源分成G個組，相應地R-Auctioneer的數目為G，設資源組k中的資源種類為nk ，則有

資源組k的價格通過R-Auctioneer k進行調節，對于R-Auctioneer k執行以下算法：

1）確定資源組內資源的初始價格p0k，設為前一次調價所得的均衡價格。

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

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

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

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

4）計算價格變化幅度。

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

5）發送新的價格矢量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 則需要計算新的超額需求函數，算法如下：對于R-Agent i，有

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

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

（2）計算該資源域關于pk的資源組k超額需求函數zi(pk)；

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

當網格資源的供需發生變化后,系統中的R-Auctioneer和R-Agent分別循環執行上述算法,直到Fp=0，表示形成新的均衡價格p，即完成一次調價過程。調度系統即可根據資源價格和資源分配策略實現有效的資源調價。

3 性能分析及實驗

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

表1 實驗對比結果

4 結論

通過仿真實驗比較了WALRAS 算法和分布分組算法的性能。與傳統的集中式同步調價算法，以及適用于分布式環境WALRAS 調價算法相比，本文提出的分布分組調價算法具有以下優點：

根據資源價格相關性，將資源分成若干資源組，根據每一組的資源供需情況分別對每組資源進行調價。因此與集中式同步調價算法相比較而言具備很好的可擴展性，適用于網格環境下的資源價格調整。

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

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

[3] 鄧曉衡,盧錫城,王懷民.基于可信評價的資源調度研究[J].計算機學報,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] 陳建剛,王汝傳,張琳.基于模糊集合的網格資源訪問的信任機制[J].計算機學報,2009,8：1676-1682.