李琳娜，钟冬望，王 芬

（武汉科技大学冶金工业过程系统科学湖北省重点实验室，湖北武汉，430065）

网格作为一种分布式计算环境，目的在于利用互联网把分散在不同地理位置的各种可用空闲资源整合起来，实现计算资源、存储资源、数据资源、软件资源、知识资源、专家资源等的全面共享，最终实现网络虚拟环境中的资源共享和协同工作［1］。网格本质上是一个基础设施，它允许位置无关的资源和服务获取，这些资源和服务是由地理上分布的机器和网络提供的。支持这种位置无关计算的一个基本操作就是资源发现，即如何有效地发现资源，为上层的资源调度、资源应用提供一个透明的全局资源视图［2］。为了建立分布式、易扩展、性能好的资源发现机制，国内外学者已进行了相关的研究和探讨［3－6］。何秀强等［5］通过借鉴P2P的思想，采用分布式资源发现方法解决了集中式发现机制中的系统瓶颈和查询效率低的问题。但是，在网格环境下，如果采用完全分布式架构，由于资源数量巨大，资源请求消息扩散将会给网络带来很大负荷。这就要求进一步优化分布式资源发现机制，混合式的资源发现机制应运而生。本文提出了一个改进的基于层次结构的混合式资源发现模型，并对其体系结构、资源信息共享方式及消息扩散机制进行说明和论证。

1 分层体系结构

混合式资源发现模型将传统网格中所使用的集中式网络拓扑结构与P2P网络中的分布式网络拓扑结构有机融合在一起，形成一种逻辑上分层、层间彼此逻辑独立的资源查询和消息扩散方式［7］。这种基于层次结构的模型将网格中的各种资源、服务及用户组织成3个层次：最底层是各种资源、服务及用户；上面一层是机构（IS），底层的资源、服务及用户按其物理位置或管理策略分为不同机构；最上面一层是虚拟组织（VO），若干个机构根据它们所提供的资源和服务类型及属性，加入具有相似属性的VO。在这个层次结构模型中，同一个VO内的各个机构之间，以及各个VO之间，都是平坦的关系，它们通过网络联系在一起，如图1所示。图1中，SN为VO的超级节点。

图1 基于层次结构的网格资源发现模型Fig.1 Resource discovery model based on layer

2 资源信息共享协议

由于网格中的资源、服务具有分布广泛、动态变化的特点，为了保证查询请求的成功率，必须正确维护成员结点的信息，并及时向外部扩散本地资源及服务信息，以使得网格中各个节点所掌握的异地信息及时得到更新。在混合式资源发现模型中，采用了一种两层的信息共享协议：第一层是在同一VO内的覆盖网络上建立信息共享关系并进行信息扩散，交换彼此的资源及服务信息；第二层则是在网格内的所有VO之间构造的覆盖网络上建立信息共享关系并进行信息扩散，交换彼此的服务属性信息。

2.1 虚拟组织内构建覆盖网络

循环移数结构覆盖网络构建方式的核心思想就是按照所有节点的统一编号，将与节点距离为2的整数幂的节点加为其邻居节点，构建成循环移数结构的覆盖网络。在本模型中各虚拟组织内部就采用这种策略构造覆盖网络。为了在VO内构建这种循环移数结构的覆盖网络，设计了一个信息共享协议，在协议中有两种类型的消息：neighbor消息和accept消息。消息的描述及算法如下：

（1）neighbor消息。一个机构加入VO时要在该VO的SN上注册，由SN分配一个ID序号，将所有SN构成一个新环，然后从初始节点（ID＝0）开始的所有节点按顺时针方向向与自身相隔为2的整数幂的节点发送neighbor消息。neighbor算法如下：

（2）accept消息。当一个节点收到neighbor消息时，则向对方发送accept消息，告知对方已接受它为邻居，并将对方信息保存在本地。accept算法如下：

2.2 虚拟组织间构建覆盖网络

由于VO之间交换的消息主要是各个VO的资源属性信息，而且各个VO的超级节点SN通常都是由性能较稳定的节点担当，所以考虑在VO之间构建的覆盖网络可以采用信息全共享策略。所有SN的资源属性信息进行相互复制，各个SN节点上都存储了所有SN节点的资源属性信息。

3 消息扩散协议

为了实现资源信息节点之间的信息共享及资源请求消息在资源信息节点上的扩散，针对分层结构模型，采用了两层消息扩散协议。将整个网络中大规模的消息扩散划分成以虚拟组织为逻辑单位的分区域消息扩散。在各个区域内部要想提高消息扩散的效率，必须设计出高效可靠的消息扩散算法。现有的消息扩散算法存在的主要问题是减少冗余消息和保证消息扩散可靠性之间的矛盾，如何解决这一矛盾是优化消息扩散算法的关键。

3.1 问题描述

在讨论算法之前，以循环移数结构覆盖网络为基础做下面的假设：

假设1：覆盖网络的规模为N＝2n。

假设2：每个节点都有一个对应的ID。

假设3：每个节点只知道与其直接相连的邻居节点的信息。

定义1：覆盖网络中节点v的度d（或邻居数）是指此节点相连的邻居节点个数。

定义2：消息从初始节点扩散到覆盖网络中的每一个节点的过程为一次消息扩散。

定义3：平均每节点在一次消息扩散中转发消息的个数为消息扩散开销f，

式中：mi为节点i转发的消息个数；N为覆盖网络规模（节点个数）。

消息扩散若基于洪泛（flooding）机制，当节点收到消息时，如果该消息是第一次到达，则将消息转发给其除消息来源以外的所有邻居节点，系统中节点的平均邻居数为k，则其消息扩散开销为

式中：ki为节点i的度数，即邻居数。

在规模为N＝2n的移数循环结构覆盖网络中，若采用洪泛机制，显然ki＝2n－1，则其消息扩散开销为

定义4：当节点收到消息后，再次收到相同的消息为冗余消息。

定义5：平均每个节点在一次消息扩散中收到的冗余消息个数为消息冗余传输开销D。

对于循环移数结构覆盖网络，其消息冗余传输开销为

下面给出一个在循环移数结构覆盖网络中使用洪泛算法的消息扩散过程实例。在图2所示结构中，若以ID＝0节点为初始节点开始进行消息扩散，一次消息扩散过程需要轮转发。

图2 洪泛算法消息扩散过程示例Fig.2 Example of message expanding based on flooding algorithm

第一轮初始节点0向它的所有邻居节点转发消息：

第二轮节点1，2，4，6，7向其邻居节点（除初始节点）转发消息：

一次消息扩散过程中共产生25条消息，其中18条为冗余消息，其消息冗余传输开销为2.3，即平均每个节点接收2个冗余消息。虽然在此结构中由于设置了合适的转发跳数（在规模为N＝2n循环移数结构中，跳数为就可以覆盖整个网络），使得冗余消息传输开销已经大大减少，但是仍然还存在消息冗余严重的现象。大量冗余消息的产生，来自盲目的洪泛，该算法中每轮的传输都只排除一个节点（消息来源节点）。如在第二轮中，1、2、4、6、7都是0的邻居节点，所以它们之间相互转发的消息都是冗余消息。

由上面的分析讨论可知，现有的消息扩散算法的消息冗余传输开销很大，占用了大量网络带宽，所以减少冗余消息的传输是改进消息扩散算法的关键问题。

3.2 M－flooding消息扩散算法

在循环移数结构覆盖网络中，如果邻接双方知道对方已经接收到此消息，就不再转发该消息给对方；如果能够记录这些已经接收消息的节点，并将该信息放在消息头中发送给其他节点，使其他节点不再发送此消息到已经记录过的节点，就可大大减少消息冗余，这就是改进算法的出发点。

每轮传输时，可以在传输的消息报文中预留一个节点轨迹标记，将每次发送的目标邻居节点集记录在此标记中，收到消息后，首先检查节点轨迹标记，消息只发往不在标记中的邻节点，这样就可以避免消息在近邻节点间的冗余传输。

如在图2所示算例中采用这种消息扩散算法，其消息扩散过程如图3所示。由图3中可见：

第一轮：初始节点0将其所有邻居节点和自身，即｛0，1，2，4，6，7｝作为节点轨迹添加到消息头，并向其所有邻居节点转发消息：0→1，0→2，0→4，0→6，0→7。

第二轮：节点1，2，4，6，7收到消息后，首先检查其邻居节点是否已记录在节点轨迹标签，只向不在标签中的节点转发消息：1→3，1→5，2→3，4→3，4→5，6→5，7→3，7→5。

同时在标签中记录新的节点，这样便减少了12条冗余消息。可见带标记的洪泛算法虽然思路简单，却可以有效减少传输冗余。

图3 M－flooding算法的消息扩散过程Fig.3 Example of message expanding based on M－flooding algorithm

4 结语

本文提出混合式网格资源发现模型，是对现有资源发现机制和P2P技术的融合。但本文目前所做的工作仅在于理论上的探讨，没有考虑网络本身的复杂情况，如在循环移数结构覆盖网络的构建过程中，没有把节点之间消息的传递时间作为邻居节点的考虑因素。因此，在后续工作中，将结合网格技术的最新发展，在更复杂的网络结构上研究该模型的有效性。另外对于所提出的消息扩散算法还可以进一步优化。

［1］ Ian Foster，Carl Kesselman.The grid：blueprint for a new computing infrastructure［M］.San Francisco：Morgan Ksufmann Publishers，1998：593－621.

［2］ 徐志伟，冯百明，李伟.网格计算技术［M］.北京：电子工业出版社，2004：59－126.

［3］ 徐志伟.基于P2P和服务质量的语义Web服务发现［J］.计算机技术与发展，2009，19（12）：25－28.

［4］ 李文娟，史维峰.基于分布式的语义Web服务发现新模型［J］.计算机技术与发展，2009，19（12）：108－112.

［5］ 何秀强，王寅峰，董小社，等.基于P2P技术的网格资源发现中的覆盖网络的构建［J］.微电子学与计算机，2005，22（7）：19－23.

［6］ Czajkowski K，Fitzgerald S，Foster I.Grid information services for distributed resource sharing［C］／／Proc of the 10th IEEE HPDC，Washington DC：IEEE Computer Society Press，2001：181－194.

［7］ 熊金波，谢艳辉，张珊珊.基于DSOF的网格资源发现模型研究［J］.计算机工程与设计，2009，30（23）：5 317－5 320.