大规模非结构化P2P网络中的资源搜索方法

摘要

本发明涉及一种大规模非结构化P2P网络中的资源搜索方法。该方法为：在资源信息的发布和维护过程中，各节点根据不同邻居节点的要求对收到的BF信息在丢弃一定比例后进行转发并保存在邻居BF表中；在资源搜索过程中，各中间节点计算目标资源与邻居BF表表项的相似度，并根据BF信息的分布情况，进行多个消息之间相互协同的并行搜索。

说明书

技术领域

本发明涉及计算机网络中的资源搜索方法，尤其是支持大规模网络中的高性能资源搜索方法。

背景技术

P2P(peer-to-peer)网络是近年来兴起的一种网络。在P2P网络中，各节点在逻辑上是对等的，没有客户端和服务器之分，各个节点之间可以直接进行通信和交互。目前，P2P网络在科学研究、电子商务、电子政务和军事应用等重要领域都有着广阔的应用。为了实现资源的有效共享和综合利用，P2P网络用户需要对符合要求的资源进行搜索，资源搜索是P2P网络的关键技术之一。

根据资源组织模式，P2P网络通常可分为两种：结构化(Structured)P2P网络和非结构化(Unstructured)P2P网络。非结构化P2P网络由于其简单性和易用性，目前在Internet上得到了大量应用。本发明针对非结构化P2P网络中的资源搜索技术。

最初的非结构化P2P网络资源搜索技术(如泛洪、随机漫步等)属于“盲搜索”(blind search)方法，每一步的搜索方向具有很大的盲目性，导致当资源请求节点距离资源共享节点较远时，无法迅速搜索到所需资源。因此，目前的资源搜索方法通常由各节点预先对资源信息进行发布、传播和维护，在资源搜索过程中，资源搜索消息根据中间节点所维护的信息来选择转发的方向，进而发现资源。

目前非结构化P2P网络中的资源搜索问题可以抽象为：如何将大规模的资源信息进行发布和维护，以及如何在资源搜索过程中利用上述资源信息迅速发现资源。

在非结构化P2P网络中，在各节点之间并没有类似于DHT的P2P网络拓扑结构，发布和维护资源信息需要消耗大量的存储空间和网络带宽。因此，目前通常基于Bloom Filter(BF)技术，使用一个位向量通过较小的存储开销来概率地表示一个节点的所有元素。每个节点都维护一个“邻居表”，保存相关邻居节点的BF信息。在资源定位时，每个节点根据其“邻居表”将资源定位消息转发到最接近目标资源的邻居节点上，直到最终到达目标节点。

评价资源搜索方法性能的重要参数包括搜索延迟、搜索开销和维护开销等。搜索延迟是指为满足一次资源搜索请求，搜索消息在网络中转发的逻辑跳步数；搜索开销是指为满足一次资源搜索请求，网络中产生的搜索消息总数；维护开销是指每个节点维护本节点和邻居节点资源信息所需的存储开销。为取得良好的实用性能，资源搜索方法应该兼顾多个方面的特性。但这几个性能特性之间存在冲突，给P2P网络的广泛应用带来困难。

发明内容

本发明所要解决的技术问题在于：针对大规模非结构化P2P网络中资源信息的维护开销较小时，搜索延迟和搜索开销较大的难题，提出了一种在资源信息维护开销受限的条件下，具有低搜索延迟和低搜索开销的资源搜索方法。

为了解决上述技术问题，本发明的技术方案为：在资源信息的发布和维护过程中，各节点根据不同邻居节点的要求对收到的BF信息在丢弃一定比例后进行转发并保存在邻居BF表中；在资源搜索过程中，各中间节点计算目标资源与邻居BF表表项的相似度，并根据BF信息的分布情况，进行多个消息之间相互协同的并行搜索。具体包括：

(1)邻居BF表：每个度数为d的节点维护了一个d行c列的邻居BF表T，表中每一个表项是一个Bloom Filter向量。表项T_ij(1≤i≤d，1≤j＜c)维护了通过第i个邻居且从信息发布节点经过j步到达本节点的资源信息；表项T_ic(1≤i≤d)则维护了通过第i个邻居且从信息发布节点经过c步或c步以上到达本节点的资源信息。

(2)资源信息的发布和维护：信息发布节点使用BF表示本地资源信息并发布。在资源信息的发布与传播过程中，中间节点收到BF信息后，按照各邻居节点的要求对信息进行丢弃后传播。

(3)相似度：设资源x对应的Bloom Filter位向量为U，邻居BF表中T_N，j^A表项的Bloom Filter向量为V，使用Like(x，T_N，j^A)表示资源x与T_N，j^A表项的相似度：