一、网格计算概述
（一）网格的定义
网格是利用互联网把地理上广泛分布的各种资源（包括计算资源、存储资源、带宽资源、软件资源、数据资源、信息资源等）连成一个逻辑整体，就像一台超级计算机一样，为用户提供一体化信息的应用服务（计算、存储、访问等），虚拟组织实现在这个虚拟环境下进行资源共享和协同工作，彻底消除信息“孤岛”，让人们使用网格上的资源像用电一样方便简单。其中，每台参与计算的计算机就是一个“节点”，而整个计算就是由成千上万个“节点”组成的网格。
网格按功能可以划分为以下三种类型：
（1） 计算网格
计算网格着重于专门留出用于计算机能力的资源。在这类网格中，大多数计算机都是高性能服务器。
（2） 拾遗网格
拾遗网格常用于大量桌面系统。计算机上可用的CPU周期和其他资源被收集。通常授予桌面主人控制其他资源的同时可以加入网格的权利。
（3） 数据网格
数据网格负责容纳和提供跨多个组织的数据访问。用户在有访问权限的前提下访问数据，而且不必关心数据位于哪里。
1998年Fosler Ian 和 Carl Kesselman 首次对网格进行定义：计算网格是一种由硬件和软件构成的信息技术基础设施，它能够提供可靠的、协调的、可扩展的和廉价的高端计算能力的服务。
2002年Foster Ian 从三个方面更加清晰的定义了网格，他认为网格是具备有以下三个条件的系统：
（1） 网格能协调非集中式控制的资源，能集成和协调资源与用户在不同控制域内的活动，能解决包括安全、策略、认证、支付和成员资格等各种问题。
（2） 网格使用标准的、开放的、通用的协议和接口，网格是根据多用途协议和接口来构建的，该协议和接口能解决诸如鉴别、授权、资源发现和资源访问等一系列基本问题。
（3） 网格提供高质量的服务，允许按协作的方式来使用其成分资源，以及协作配置多重资源类型以满足复杂用户的需要。
（二）网格资源的特点
网格作为一种新出现的重要的网络基础设施,和其他的系统相比，它的资源有四个特点:分布性;动态性; 异构性;自治性与管理的多重性。
（1） 分布性指网格的资源是分布的。不同计算能力的计算机,各种类型的数据库乃至电子图书馆,以及其他各种分布在不同地理位置的设备与资源,都是网格资源。
（2） 动态特性是指网格的资源或服务的动态加入或减少的。由于网格是多种资源和服务的汇集，其本身的可扩展性和动态性决定了其资源也一定具有动态性。
（3） 异构性是指网格中的资源可能存在不同体系结构的计算机系统中，网格必须解决这些不同结构、不同资源之间的通信和互操作问题。
（4） 自治性是指网格资源的拥有者对该资源具有最高管理权限,网格允许资源拥有者对它的资源有自主的管理能力。同时,网格资源又是一个网格的局部,它必然要接受统一管理,否则,就无法实现共享和互操作。网格资源管理的多重性就体现在它的自主管理同时还要接受统一管理。
（三）资源发现机制的研究对网格应用的重要性
当今的网络规模膨胀、信息资源爆炸，资源的搜索方法已经成为Internet的关键基础技术之一，而现有基于资源路由器的资源发现技术有以下缺点：
（1） 服务器更新不及时，产生大量过时信息；
（2） 产生许多无价值的垃圾信息；
（3） 服务器收集的信息量有限；
（4） 存在单点失效等缺点。
如何在基于网格计算的信息资源海洋中快速发现有用的资源，探索更有效的资源发现机制与技术已经是信息工业，乃至整个计算机产业最重要的研究领域之一。而未来的网格环境下的资源将比今天的网络环境下更为丰富，更加多样，如果能够探索研究发明出更加先进高效的资源发现机制和技术，必将产生巨大的社会贡献和经济效益。
二、网格资源发现机制的基本思想
（一）网格资源发现机制的主要任务
在传统的单计算机系统和机群系统中，计算资源的分布比较集中，计算在使用资源之前可以快速、可靠的进行资源定位，资源的查找操作对计算性能的影响很小。在网格计算中，由于资源的广域分布以及现有Internet存在的带宽和延迟限制以及网络的不可靠性，广域范围内的资源定位将在很大程度上影响计算的性能。因此，我们需要一种有效的资源发现机制解决广域资源的快速定位问题。资源发现机制的任务是在短时间内高效率的找到资源所在的节点。
（二）现的网格资源的查找方式
在已有的网格系统中，资源查找主要有两种方式，即Flooding查找方法和集中查找方法。
Flooding查找方法主要应用于对等P2P网络，这是一个完全分散化的网络系统，各个网格节点在网格中地位对等，没有固定的系统拓扑结构，具体系统结构都是在发展中动态自发形成的。Flooding采用广播的方式，向邻居的计算机节点发出带有查询关键字的Query指令，查询在网络中迅速逐跳扩散，它有两个控制查询范围或查询半径的域TTL(Time To Life)和Hops，查询每前进一步，TTL就减1，Hops就加1，因此给予TTL不同的初值，就可以获得不同的查询半径。随着跳数（Hops）的增加，查询访问到的主机数量急剧增大。Flooding查找方法能够有效解决服务器模式的缺点和问题，它的基本搜索思想是利用全部网络资源为每一个成员服务，每一个节点都储存了周边相邻节点的资源信息，用最短的时间开销把查询消息扩散到最多的网络成员处，保证查找范围的最大广度和深度。但是，这不可避免地带来大量无效消息，浪费宝贵的网络带宽及机器计算资源等矛盾和问题。
相对来讲，集中查找方法可以有效的避免Flooding技术带来的难题，它的基本思想是把整个网格的资源信息都集中储存在一个资源数据库上，当用户节点需要资源时，通过资源数据库查找整个网络中的资源信息，然后定位资源在网格中的位置。集中查找的好处是可以避免大量无效的查找消息，节省网络带宽，降低查找开销，提高查找效率，有利于资源的总体调度。但是缺点也是显而易见的，那就是所有的资源查找都必须通过一个集中的资源数据库，当网格中的节点成千上万时，查找的效率会下降，甚至资源数据库可能成为整个网格的瓶颈。再者，网格资源的动态性决定了资源数据库的维护有一定的难度，需要周期性的发送消息与个资源节点联系来更新资源数据库上的资源信息。
（三）资源发现机制的基本思想和关键技术
现在比较流行的资源管理结构模型是将以上两种查找方式结合起来，即在网格的局部网络中用使用集中查找方式，在整个网格中资源路由器之间的查找则使用Flooding查找方式（如中科院的织女星网格）。在局部网络中设置资源路由器，采用C/S模式，用户节点请求资源时先访问资源路由器上的资源数据库，若局部网络中存在所需资源，则资源路由器返回该资源的节点地址。当所需资源不存在该局部网络时，需要通过资源路由器访问网格中的其他资源路由器来查询资源，此时资源路由器之间属于一种对等网络，可以采用P2P网络的Flooding技术来进行资源搜索。
其网络拓扑结构如图：
网格中相邻的部分节点组成一个局部网络，每一个局部网络设有一个资源路由器，这里的局部网络可以理解为一个公司，机构或单位所拥有计算机节点所组成的一个逻辑网络。网络上的数据是海量的，考虑到资源路由器的性能因素，必须把局部网络的节点数量控制在一定的范围之内，当节点数量超过资源路由器所能负荷的极限值，应该把该局部网络分割成两个网络，并增设资源路由器。资源路由器上有两个数据库，一个负责存放该局部网络上所有计算机节点提供的可被访问的资源信息，另一个负责存放网格中与其邻居资源路由器的网络地址。资源路由器提供的基本服务有：
① 组织所在局部网络上的所有计算机节点的资源信息数据库，对局部网络上的资源进行管理和调度。网格中的计算机节点查找资源时，首先查询所在局部网络上资源路由器的资源信息数据库，如果局部网络存在所需资源，则由资源路由器将该资源分配给所需节点。
② 维护所在局部网络上的所有计算机节点的资源信息数据库。基于网格资源的自治性与动态性，局部网络上的资源节点通过注册、修改、撤消操作来更改其在资源路由器上的资源信息。另一方面，资源路由器也周期性的向该局部网络上的各个节点发送查询消息，及时更新资源数据库，以尽可能的降低资源节点的单点失效率。
③ 根据路由地址数据库，用Flooding方法向整个网格中的所有资源路由器发送资源查询消息。当所需的资源无法在本局部网络中找到或者性能达不到要求时，请求资源的计算机接点通过资源路由器向网格中的其他资源路由器发送查询消息，在整个网格范围内查询所需资源。
④ 维护路由地址数据库。与网络路由器的原理相似，资源路由器也具有学习的功能，而且路由器之间周期性的用消息进行通讯，保证路由地址数据库的同步更新。
综合两种查找方式，在局部网络内部采用C/S模式下的集中查找，在资源路由器之间采用P2P网络模式下的Flooding查找，可以充分发挥两者的优点，互补两者的不足。不但节省网络带宽，降低资源查找开销，避免了大量无效的查询消息，而且提高资源查找效率，有利于资源的管理与调度
（四）面临的主要问题
随着网格计算的迅速发展，未来网格的规模可能非常庞大，节点数目可能达到几万甚至几亿，此时，一些小问题也将会被放大，摆在我们面前需要我们进一步去探索，去解决。网格资源发现机制面临的问题主要有：
（1）网格中的计算机节点每次请求资源，都必须先访问资源路由器，然后资源路由器再在资源信息数据库中查询所需资源的相关信息。需要优化查询算法减少资源请求节点对资源路由器的访问次数和对资源信息数据库的查询次数。
（2）Flooding搜索方式的搜索效率极其低下，在搜索的过程中会产生大量的多余的查询消息。当网格中的节点和资源路由器的数目非常庞大时，这些无用消息的数量也将会变得十分的庞大，严重浪费网络带宽。需要优化Flooding算法，提高资源搜索的精确度，缩小搜索的范围。
（3）网格中有大量的资源，有好有坏，有多有少，需要运用各种评估策略对资源进行性能分析和风险分析。
三、根据局部性原理减少资源的查询次数
（一）局部性原理
尽管网络资源无限爆炸，但每一个成员及其每一次查询，所涉及到的回答域都很有限，并且基本上保持固定不变。这就是著名的“局部性现象或局部性原理”，计算机体系结构中关键技术之一的Caching技术，就是程序执行过程中的局部性原理的有效应用。局部性原理有时间和空间两方面的含义：时间局部性，最近访问的指令和数据很可能在不久的将来再次被访问，即下一程序指令在前条指令附近的概率非常大，因此，时间局部性往往会引起对最近使用区域的集中访问；空间局部性指的是一个进程访问的各项地址彼此很近，即下一次数据访问在前次访问的数据附近的概率非常大。前者就是程序Cache，后者就是数据Cache的理论依据。同样的事实在网络资源访问中依然存在：就每一个访问成员而言，下一次的网络资源访问的回答节点落在前次网络资源的回答域中的概率非常大。
同实际社会一样，网络社会中也总是存在所谓的幂律（Power-Law）：
（1） 少的系统成员掌握着较多的受欢迎（Popular）系统资源；而系统中还存在着一些从未被访问或极少访问的节点资源；
（2） 较少的Popular节点提供了绝大多数的查询响应；而有40%的free riders节点从不提供任何服务。
具体下图所示，上面第一条更加弯曲的是查询响应曲线，下面的是结果文件提供者曲线，可以看出，小于10%的Popular节点提供了几乎所有的查询响应。因此网络中确实存在局部性现象。
网络世界里的Power-Law示意图
（二）在计算机用户节点和资源路由器设置“快表”
在操作系统原理的分页内存管理方式中，可在地址变换机构里增设一个具有高速查询能力的“联想存储器”，又称为“快表”。当CPU给出有效地址后，由地址变换机构自动地将页号送入“快表”中与其中的所有页号进行比较，若命中，则直接读出该页所对应的物理块号；若不命中，则再访问内存中的页表查寻对应的物理快号。
我们也可以将这种设计应用在网格中，在计算机用户节点和资源路由器设置类似的“快表”。“快表”按资源的不同类型分成几个子表。本地计算机上的“快表”存放的是最近该计算机节点访问过的资源信息，根据用户的需要，一般设置每个资源子表的表项为10到20个，即存放该节点最近访问过的10到20个资源的相关信息，包括资源在网格中的定位、性能系数、风险系数访问次数以及最近访问时间等。在本地计算机设置“快表”，是根据本地计算机访问资源的局部性，即该节点可能在一段时间内重复多次有相同或相近的资源需求，以及同一个资源的在网格中的定位地址在短时间内一般不会改变，即资源失效的几率较小。
本地计算机“快表”结构的主要属性如下：
资源ID
资源类型
最近访问时间
访问次数
……
因为表结构较简单，表项数目较少，而且考虑到网格中资源请求节点多为个人PC，性能有限，所以无须为本地计算机的“快表”建立数据库，可以将“快表”以数据结构中循环链表的形式存在于本地计算机的内存中，按最近访问时间排序，当“快表”存满时使用近期最少使用算法（Least Resently Used 即LRU）将一段时间内使用最少的资源信息表项替换出去。
在本地计算机设置“快表”的好处是可以最大程度的减少访问资源路由器的次数，最大的降低网络开销。
资源路由器上的“快表”存放最近通过该资源路由器的查询并成功获得资源访问权限的资源的信息，它包括三类，本局部网络中节点查询到的存在于本局部网络中的资源信息，本局部网络中节点查询到的存在于其他局部网络中的资源信息，其他局部网络通过本局部网络资源路由器查询到的资源信息，所以，资源路由器的快表不是单纯的资源数据库信息的子集，其设置与本地计算机节点上的类似，有一点不同的是资源路由器上的“快表”表项要比本地计算机节点上的多，根据该局部网络的规模，一般设置在100到300之间。
资源路由器“快表”结构的主要属性如下：
资源ID
资源类型
最近访问时间
访问次数
所在网络的路由器地址
……
这些“快表”可以是以数据结构的形式存放在内存中， 也可以是以表的形式在数据库中实现，一般情况下按最近访问时间排序，当有新的资源信息需要加入而“快表”本身已经存满时，也是采用近期最少使用算法进行替换。在资源路由器设置“快表”是为了尽量减少对路由器上资源数据库的查询次数。
（二）改进后资源查询的过程
改进后当请求节点需要查询资源时，其过程如下：
（1）请求资源的计算机节点先查询本地计算机上的资源“快表”，如果“快表”中存在满足要求的资源信息，结合资源评估策略，直接访问最佳资源信息所对应的资源节点，确认该资源可以访问后更新本地“快表”中对应的该资源的表项信息（访问次数和最近访问时间）；若该资源已不可访问，则更新本地计算机和资源路由器上的“快表”，即将该资源信息表项删除，并访问下一个最佳资源节点；如果此时“快表”中已无满足要求的资源信息，则向本局部网络的资源路由器发送资源查询请求。
（2）资源路由器接收到查询请求后先查询资源路由器上的“快表”，如果“快表”中存在满足要求的资源信息，结合资源评估策略，将最佳资源信息直接发送回请求节点。若“快表”中不存在满足要求的资源信息，则查询资源信息数据库，并将查询结果发送回请求节点。
（3）如果查询结果是本局部网络不存在满足要求的资源，则由资源路由器用Flooding方法向网格中的其他资源路由器查询。其他资源路由器接收到查询请求后执行步骤②操作。
四、根据选择扩散法优化Flooding 查询方法
（一）Flooding搜索技术的特点
在网格中的每个资源路由器之间，类似于P2P的对等网络，每个参与资源路由器点既是服务器又是客户端，既是信息的提供者又是信息的消费者。P2P信息检索的目的就是网络中的任意节点都可以提交检索的请求，然后这些检索通过某种路由机制被路由到和检索相关的节点上去，存储有和该检索相关信息的节点将会回应请求，把本地相关的内容以对等的形式直接传送到请求节点上。在P2P网络上，应用最广的要数Flooding搜索技术。
Flooding搜索技术的优点是：简单健壮，无需维护，局部节点失效不影响系统性能；效率高、延时小，总是走最短最快的路由路径；基本操作是Flooding式广播，P2P直接通信。缺点是：存在大量富余联接，增加网络交通流量，大量消耗网络带宽，直接影响并限制了网络的可扩展性能。
所以，Flooding技术本质上是广度优先搜索（
Breadth First Searching，BFS）技术，它存在的问题主要是网络中存在大量的冗余查询信息，解决Flooding问题的技术主要有Iterative Deepening、Directed BFS、Local Indices、Random Walkers 等。它们要么采用同一策略，要么相互共享某些信息，都对节点作出或多或少的修改。Flooding方法最快，系统也最为自由安全，而网络带宽资源最浪费，限制了系统的扩展性能。这些改进方法旨在降低带宽需求，但要么效率太低（Random Walkers）,要么增加的信息量过大（Local Indices），要么牺牲安全性（Iterative Deepening），要么技术上难以实现（Directed BFS）。
（二）优化Flooding技术
在这里我们引入选择扩散法，即在资源路由器应用Flooding技术向周边邻居节点扩散查询消息前，依照一定的评估策略，主动的、有目的对周边邻居节点进行选择，再向选中邻居节点发送查询消息
网格中节点成千上万，资源的数目更是不计其数，同一种资源在网格中必定会存在多个相同的复本，同一个资源请求必定可以在网格中找到多个符合要求的资源提供者。所以，我们要做的，是平衡开销和效率，以较少的网络开销，较短的响应时间，找到满足需求的资源。以选择扩散法为依据，我们可以引出优化Flooding技术的新思路——选择性的减少搜索的宽度，向“最有可能”存在资源的路由器方向发送查询消息。
优化Flooding搜索技术的研究可以抽象为如何从一个随机图中的任一个点出发定位目标点，使得整个过程遍历的点的个数最少。由于Flooding查询时会通过邻居节点发送消息并且消息的数量随着跳数的增加呈几何级增长。而研究表明只要访问少量的节点就可以满足查询需求。所以，要减少搜索的宽度，可以在搜索的早期阶段就把搜索引向资源存在概率较大的方向，即网格中的资源路由器根据自己以及周边邻居路由器的资源查询情况，把查询消息向“最有可能”的邻居节点扩散，不搜索概率小的甚至是没有可能的邻居节点，由此来优化搜索树，大大减少冗余查询信息。
而用选择扩散法来减少搜索宽度，最关键的问题是：我们要怎样制定评估策略，如何判断哪些邻居节点才是查找成功率较大即“最有可能”的节点呢？
在选择扩散的基础上，我们引入了兴趣局部性原则：每个节点都表现出某些可以捕捉到的兴趣，相近兴趣的节点保存的内容和提交的查询也相近。可就是说，在搜索的过程中，我们可以尽量向那些“志同道合”的节点靠拢。
将以上原理应用到我们的网格资源模型中，我们可以先将网格中各种资源分类，比如分为处理机资源、存储资源、数据资源、软件资源等甚至更细。在整个网格中，约定每一类资源对应一个编号，在每个资源路由器上设置一个整型变量Interest，用来存放这个编号。然后，周期性的分析资源路由器上的快表，最近查询频率最高的资源即为该节点最“感兴趣”的的资源，把整型变量Interest设置为这个资源对应的编号。在这里需要指出的是，快表里存放的是通过该资源路由器查询的资源信息，它不是单纯的资源数据库信息的子集，它反映的通过当前资源路由路器访问的各种资源的频率。所以，通过对快表的分析，可以确定在当前一段时间内该资源路由器最“感兴趣”的资源类型。
此外，再设定一个最低的搜索宽度，当资源路由器Flooding时，向邻居路由器发送资源请求的查询消息，查询邻居路由器的资源数据库，如果存在满足要求的资源则返回该资源的相关信息，否则，再判断请求的资源类型与邻居路由器的“感兴趣”的资源类型匹配是否匹配，若匹配，则继续Flooding；做不匹配，则查询在该路由器终止。
五、总结
本文讨论了网格的资源发现机制，包括现有的两种资源发现技术——集中查找技术和Flooding查找技术的介绍和它们的各自的优点与不足。在网格资源发现机制综合应用这两种资源查找技术，优势互补，提高了资源查找的效率，但随着网格节点的增多，网格的资源发现机制还不可避免的面临着一些难题。本文根据局部性原理和选择扩散法提出了对网格资源发现机制的一些优化方案，引入了“快表”和资源的“兴趣”原则，进一步降低了用户节点对资源路由器的查询次数，提高了资源的查询效率；在一定程度上降低了资源路由器向其他路由器Flooding时的盲目性，减少了大量无效的查询消息，提高了网络带宽的利用率。本资源发现机制具有较好的定位性能和可扩展性，能够适应网格资源自主控制、动态变化的特点，可以较方便地解决资源节点单点失效和查询时产生大量无效消息的问题，具有一定的好用性和通用性。
以后的研究工作包括：对上述的资源发现机制进一步进行改进和优化，如重新定义节点的邻居的概念和划分的依据，即根据某种相似的特性，把一些计算机节点划分为一个团体，团体内计算机节点彼此之间是“相识的人”，这样可以更加有效的发挥小世界原理的作用；在资源发现过程中引入资源评估机制，通过性能分析，在众多的可利用资源中选择最合适的，性能最高，安全性最好的资源；引入风险分析机制，由于网格的分布性，并发性和异步性，当可用资源数目少于请求节点数目时，必然会出现不同计算机节点为了竞争资源而进入“死锁”状态，可以考虑运用操作系统中的“银行家算法”来加以预防。
参 考 文 献
[1] 罗晓沛，候炳辉.系统分析师教程[M].北京:清华大学出版社,2003.6.
[2] 张友生，徐锋.系统分析师技术指南[M].北京:清华大学出版社,2004.9.
[3] IBM International Technical Support Organization, 2003, Introduction to Grid Computing with Globus.
[4] 董方鹏,龚奕利,李伟,查礼.网格环境中资源发现机制的研究[J].计算机研究与发展,2003年,40(12):1749-1755.
[5] 孙瑜,李志平.网格资源管理体系结构模型研究[J]. 计算机工程与应用,2003年,(17):26-29.
[6] 胡宇峰. 基于网格的资源共享技术体系分析[J]. 情报科学,2004年,22(1):118-122.
[7] 徐志伟,卜冠英,李伟,查礼. 网格环境下一种有效的资源查找方法[R].北京:中科院计算所 ,2003年.
[8] 赵维. 利用局部性原理的网格资源高效搜索方法[R].南京:金陵科技学院,2003年.
[9] 赵维. 基于语义本体论的网格资源精确搜索方法[R].南京:金陵科技学院,2003年.
[10] Jon M. Kleinberg.Navigation in a small world[R]. 2000 Macmillan Magazines Ltd,2003年.
