基于市场机制的网格资源调价算法

郭绍翠，杨 旭

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.