摘 要：网格被普遍认为是下一代网络，而资源发现是网格资源管理的基本组成部分。完全集中式资源发现机制和完全分布式资源发现机制都存在若干优点和缺点，因此，在集中式和分布式资源发现方法的基础上，提出了基于层次模式的资源发现方法。将网格中的资源分成三层结构，其中包括物理网络层、资源信息层和索引信息层，在此分层的基础上提出了基于层次模式的资源发现方法。最后对该方法进行模拟，并对模拟结果进行分析，该方法有较好的时间扩展性和性能，同时，在这种方法中能通过并行的方法发现需要的资源。
关键词：网格；资源发现；资源组织；虚拟组织；层次模型
中图分类号：TP393.01文献标识码：A文章编号：1672-1098(2008)01-0081-04
收稿日期：2006-11-30
基金项目：安徽理工大学青年科学研究基金资助项目；安徽理工大学博、硕基金资助项目
作者简介：印玉兰(1976-)，女，江苏泰兴人，讲师，硕士，主要研究方向为网格计算、并行算法等。
Grid Resource Discovery Method Based on Hierarchical Model
YIN Yu-lan1,CUI Huan-qing2
（1. School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China; 2. College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao Shandong 266510, China）
Abstract:Grid is commonly considered as next generation network, and resource discovery is a basic component of grid resource management. There are some disadvantages in totally-centering and totally-distributed resource discovery method. Base on centering resource discovery and distributed resource discovery methods，a hierarchical resource discovery method is proposed, in which resource in grid is divided into 3 structure layers, including physical network layer, resource information layer and index information layer. Based on the layers resource discovery method based on hierarchical model was put forward. The simulation results indicate that the method has good time extensibility and performance. Furthermore, in the method required resource can be discovered by collateral way.
Key words:grid; resource discovery; resource organization; virtual organization; hierarchical model
随着高性能应用要求的不断提高，单台高性能计算机已经不能满足一些超大规模应用问题的解决。这就需要将地理上分布、系统异构的资源通过高速网络连接起来，协同解决一些大型应用问题［1］。而网格的本质特征就是：分布与资源共享。
如何在动态异构的网格环境下实现资源的有效管理是网格计算面对的根本问题。网格计算下的资源管理是针对资源的分布性、存取的普适性，进行跨多个管理域的资源管理，以及资源的定位、查询、更新。在传统的单计算机系统和机群系统中，计算资源比较集中，在使用资源之前可以快速、可靠地进行资源定位，资源查找操作对计算性能的影响很小。而在网格计算中，由于资源的广域分布、现有Internet存在的带宽和延迟限制以及网络的不可靠性，资源查找将在很大程度上影响计算性能［2］。因此，需要一种有效的资源发现方法来解决广域资源的快速定位问题。
如不特别说明，本文假设在资源节点的描述中，有关资源节点中的资源的类型、数量、对外共享的优先关系以及资源节点的有效生命期等属性信息都已描述清楚。
1 现有的资源发现机制
已有的资源发现机制主要分为两种：一种是集中式的；一种是分布式的。
传统的集中式资源发现机制有一定优点［3］：
(1) 系统的拓扑结构比较简单，容易构建和维护，而且消耗小；
(2) 不存在资源信息不一致的问题，在小范围内的发现效率较高；
(3) 服务集中，易于资源共享并发控制，而且系统的安全性比较好。
同时，存在的缺点有：
(1) 可靠性比较差，当中心服务器出现故障时，系统将不能正常工作，系统没有容错功能；
(2) 系统的可扩展性比较差，受限于中央信息节点的能力，因为系统中资源节点的信息必须存储在中心服务节点，并且所有的服务也必须通过中心服务节点，使得系统不能容易的增加大量资源。
然而，完全分布式资源发现机制与集中式资源发现机制的特点几乎正好相反，主要缺点是［3］：
(1) 资源信息空间的无序性和无结构性使得资源发现具有一定的盲目性；
(2) 节点可随时加入或离开使得系统的安全性比较难以控制。
但完全分布式资源发现机制的优点是其可扩展性和可靠性，节点可随时加入网络并将自己的资源共享给其它的用户；同时任何节点的离开或故障都不会影响系统中其它节点的正常工作。
采用完全的集中式或者完全分布式的资源发现方法都不是很理想，都存在一些缺陷，而基于层次模式的网格资源发现集中了集中式和分布式发现方法的优点。
2 基于层次模式的网格资源模型
网格资源发现是网格资源管理核心内容之一，如何根据网格的特点，有效地监控网格资源信息和状态并查找网格资源，是要解决的核心问题。
2.1 基本定义
定义1 为了便于资源或资源信息的管理，对资源或资源信息进行分割而形成的若干个整体，称为虚拟组织（Virtual Organization）。
定义2 为了便于虚拟组织中资源信息的查找，用来存放虚拟组织信息库和邻接表以概述虚拟组织资源信息的节点，称为该虚拟组织的超节点［4］（Super Node）。
定义3 为了避免访问拥塞，资源节点向网格注册时，为其提供共享的每种资源设置一定的优先关系，其中优先权最高的资源，称为这个资源节点的局部兴趣（Local Interest）。
资源有三层组织结构（见图1），第一层为资源节点的物理网络层（Physical Network Layer）；第二层为由若干个虚拟组织组成的资源信息层（Resource Information Layer）；第三层为索引信息层（Index Information Layer）。
图1 基于层次结构的资源组织模型
物理网络层是提供资源共享的资源节点,而资源信息层是网格中注册资源节点对应的信息节点，在该层中，资源信息节点根据对应物理网络层中资源节点的IP地址和地理位置的相近原则，将资源信息节点分成若干个虚拟组织，并对虚拟组织中资源信息节点的数量设置上界和下界。索引信息层是每个虚拟组织对应超节点组成的一个环形网络。
2.2 资源信息层与索引信息层的组织形式
为了提高资源发现的效率，需要对资源信息层里虚拟组织中的资源信息节点进行合理的组织。由于资源发现时是给定的资源属性，而不是具体的资源，因此根据资源属性对资源信息节点进行组织。对虚拟组织中的资源信息节点采用局部星型拓扑结构。根据资源的属性，将所有相同属性的资源聚集在一起(见图2)。
图2 a类资源的组织模型
索引信息层中的超节点主要用来存放虚拟组织的信息库和邻接表(见图3～图4)。
图3 信息库字段
图4 邻接表的格式在图3～图4中，其中MaxNum的值是随T/F字段的值而变化的：
(1) 若T/F字段的值为T，则MaxNum的值是所有局部兴趣为Type类的资源节点中含Type类资源的最大数量。
(2) 若T/F字段的值为F，则MaxNum的值是所有资源节点中含Type类资源的最大数量。
信息库中将虚拟组织里含有资源的属性、资源的数量以及资源节点对外共享的优先关系等信息都描述得很清楚，在进行资源发现时可以很快确定虚拟组织中是否含有所需资源以及所需资源可能存在的概率。
邻接表的组织是根据资源的属性建立，对每一类资源都建立一个链表，首先是按照资源的局部兴趣进行排列，再按所含该类资源的数量进行排列，形成有序的资源链表。这种方式有利于资源发现时很快能确定所需资源的大体所在方向。
4 网格资源发现算法
资源发现整个过程中， 第一阶段完成对资源发现所需信息的准备，第二阶段完成对需求资源类型的查找并确定查找的虚拟组织，第三阶段完成对需求资源全部信息的查询，第四阶段实现资源请求的确认。
算法1 层次模式的网格资源发现算法
输入：所需资源的信息
输出：资源发现结果
算法步骤：
(1) 提交所需资源的信息，在本地区域查找是否存在所需资源；若没有所需资源，则将所需资源信息发送至索引信息层；
(2) 确定所需资源的类型，将各超节点中信息库里对应类型资源的信息进行比较，根据需要进行排序比较，并作存储；
(3) 根据排序的结果，用串行或者并行的方法，对一个或几个超节点中的邻接表进行遍历，对已遍历的资源节点作已遍历的标志；
(4) 在索引信息层查找到可能存在需求资源的资源节点的信息传输到资源信息层，对该资源节点的信息进行核查，若满足需求资源的要求，则返回该资源的地址给请求的用户。否则，返回未发现资源的信息至索引信息层，继续进行资源的发现，即重复(3)。4 评价
4.1 该层次模型的特点
(1) 整个网格没有一个唯一的中央服务器，而是把中央服务器的功能分散在各个虚拟组织中，由各个虚拟组织的超节点完成，从而避免整个网格的单点失效。
(2) 每个虚拟组织具有一个超节点；超节点用于存储虚拟组织的信息库和资源邻接表。
虚拟组织的规模要在一定范围之内，如果过大则进行分解，过小则进行合并。
4.2 算法时间复杂度分析
假设所需资源类型为a，网格中有n个虚拟组织VOi（i=1,2,3,…,n），即有n个超节点，其中m个虚拟组织中有a类资源。进一步，假设第i个虚拟组织具有RNi个资源节点，该虚拟组织中各个资源节点存在所需资源的概率相同，即为1RNi。显然，时间复杂性由两部分组成：
(1) 对各信息库中的信息进行排序，选择合适的虚拟组织。利用最优的排序方法，平均时间复杂性与最坏时间复杂性均为O(mlnm)；
(2) 对所选虚拟组织的邻接表进行遍历以查找合适资源。如果采用串行查找方法，那么在该虚拟组织中进行查找的最坏时间复杂性为O(RNi)，平均时间复杂性为O(lnRNi)。
因此，整个资源发现算法的平均时间复杂性为O(mlnm)+O(lnRNi)。
最佳情况下，资源需求信息提交后，只遍历一个虚拟组织的邻接表，且在资源信息层进行信息匹配时一次就能满足资源用户的需求， 这种情况下所需的时间为选择合适的虚拟组织所需要的时间， 因此最佳时间复杂度为O(O(mlnm)+O(1))＝O(mlnm)。
参考文献：
［1］ 李伟，徐志伟，卜冠英. 网格环境下一种有效的资源查找方［J］.计算机学报，2003，11(26):1 546-1 549.
［2］ FITZBERALD S，FOSTER I，KESSELMAN C，et al.A directory service for configuring high-performance distributed computations［J］. In：Proceedings of the 6th IEEE International Symposium on High Performance Distributed Computing(HPDC 6)，Portland，OR，1997，365-375.
［3］ 刘星，肖卫东，徐磊.基于复合拓扑的网格资源发现机制［J］.计算机工程与应用，2005(9):132-136.
［4］ CARLO MASTROIANNI, DOMENICO TALIA,
ORESTE VERTA. A super-peer model for resource discovery services in large-scale Grids［J］.Future Generation Computer Systems， 2005(21)： 1 235-
1 248.
［5］ 徐志伟，冯百明，李伟.网格计算技术［M］.北京：电子工业出版社，2004.
［6］ 金海，袁平鹏，石柯.网格计算［M］.北京：电子工业出版社，2004.
［7］ 金蓓弘.分布式系统［M］.北京：机械电子工业出版社，2004.
［8］ 桂小林. 网格技术导论［M］.北京：北京邮电大学出版社，2005.
［9］ MORENO MARZOLLAL，MATTEO MORDACC-
HINI， SALVATORE ORLANDO.Resource Discovery in a Dynamic Grid Environment［J］.Proceedings of the 16th International Workshop on Database and Expert Systems Applications (DEXA’05)，2005(5):4 159-4 188.
［10］ T N ELLAHI，M T KECHADI.Distributed Resource Discovery in Wide Area Grid Environments［J］,ICCS，2004,LNCS 3038,Springer-Verlag Berlin Heidelberg，2004，210-217.
［11］ CHENG ZHU,ZHONG LIU,WEINING ZHANG.Decentralized Grid Resource Discovery Based on Resource Information Communit［J］.Journal of Grid Computing， 2004(2):261-277.
［12］ MARK A SHEDON， ANDRZEJ DUDA， RON
WEISS，et al.Discover: a Rresource Discovery System Based on Content Routing［J］.Computer Networks and ISDN System，1995(27):953-972.
［13］ WEI LI， ZHIWEI XU， FANGPENG DONG.Grid
Resource Discovery Based on a Routing-Transferring Model，［EB/OL］.2006-05-10 .cn/qkpdf/ahlg/ahlg200801/ahlg20080120-1.pdf" style="color:red" target="_blank">原版全文