非结构化P2P网络搜索技术研究

P2P文件共享首先要解决文件定位的问题。理论上，P2P搜索技术的搜索范围将在几秒钟内以几何级数增长，几分钟内就可搜遍几百万台PC上的信息资源。当然，实际环境中还需要考虑网络带宽以及路由优化方面的问题。特别是P2P网络规模比较大以及异构网络存在、节点分散且不断的离开加入所造成的不稳定、数据种类繁多等特点的存在。因此，设计高效的搜索机制，快速而准确地找到所需要的数据，才能使 P2P 网络得以广泛应用。
 
　　非结构化P2P 网络解决了网络结构中心化的问题，扩展性和容错性较好。但是它采用应用层广播的协议,导致消息量过大，网络负担过重，无法得知整个网络的拓扑结构或组成网络的各对等点的身份，新的对等点进入网络时，系统必须向这个对等点提供一个对等点列表，但P2P网络的强动态性决定了这个对等点列表不可能长时间有效,另外这类系统更容易受到垃圾信息，甚至是病毒的恶意攻击。

P2P常用网络搜索技术分析

Gnutella模型是应用最广泛的纯(非结构化)P2P拓扑结构，没有索引服务器，每一个联网计算机在功能上都是对等的，既是客户机同时又是服务器。查询信息不是发送至中央服务器，而是向所有的对等点发布。不需要向目录服务器报告共享的信息，而是将请求泛洪到直接相连的邻居，直到收到响应，或者达到了最大的泛洪步数。它采用了基于完全随机图的洪泛(Flooding)发现和随机转发机制。为了控制搜索消息的传输，通过TTL (Time To Live)的减值来实现。这种模型需要很多的网络带宽来进行资源的搜索工作。随着联网节点的不断增多，网络规模不断扩大，通过这种洪泛方式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效，甚至存在比较严重的分区、断链现象。导致一个查询访问只能在网络的很小一部分进行，因此网络的可扩展性不好。

之后，又出现了其他改进的分布式系统，如通过KaZaA引入超级节点。把查询请求集中到超级节点，减少了网络带宽的消耗。相互连接的超级节点带有指向各对等点数据的指针，而所有的请求通过路由到达超级节点。但是当查询率相当高时， P2P系统仍然会出现一些问题：节点容易过载，系统运行容易出错。而且随着系统的增大这个问题就越发严重。

对现有的非结构化P2P网络的改进

拓扑自适应

考虑到网络的异构和各节点处理能力的不同，用节点每秒能处理的查询量来表示节点的能力。通过计算，获得各节点的处理能力，进而避免任何节点过载以处理更多的查询，适应不断增大的系统规模。

当源节点发布消息时，它通过非结构化P2P 网络的自适应机制来定位其他的节点；各节点之间的联系通过3次握手协议来完成。在源节点发送的信息前带有惟一标识GUID。这一标识是任意产生的16位字符串，它能跟踪信息的传输，并且将反馈信息原路路由回源节点。每一个节点都维护一个缓存，其中包含一张其他节点信息的表，表里有节点的IP地址，端口号和它们的能力。节点使用消息交换机制进行主机节点的信息交换，如果连接某一节点失败，则在缓存表中将该节点标记为死节点。缓存定期删除死节点的记录。拓扑适应算法的目标是保证网络中处理能力强的节点连接较多的邻居节点，并且处理能力低的节点离能力高的节点很近。

为了实现这一目标，所有节点都将各自计算出自己的关联度。关联度不仅决定是否运行拓扑自适应，而且决定了该节点被使用的频率。关联度越低就越经常使用拓扑适应。用0到1之间的一个值来表示该节点与其当前邻居节点的关联程度。L=0表示关联性很低，L=1表示关联性很高。

如果一个节点连接的节点数低于允许的最小连接数，那么其L=0；如果L<1,将增加节点来提高L。随着其邻居增多，关联程度也将提高，直至接近或到达其处理能力。对于任一节点X的所有邻居计算Mi=Ci /i(其中Ci 表示节点的处理能力，i表示节点的邻居数)，则L=∑Mi /Cx ；若求得的L>1.0或X的邻居数大于设置的最大邻居数，则L=1。

如果X节点要增加其邻居，那么它将从它的缓存中任意选择一些节点作为其邻居的候选，从这些任选的节点中，X将选择最大处理能力大于它的节点。如果候选的节点中没有满足这一条件的，它任意从候选节点中任意选择一个作为其邻居。假定被选的备用节点为Y，X将与Y 进行3次握手，在握手时，网络中的每一个节点将决定是否接受这个新节点作为其邻居，根据该节点的处理能力、已经存在节点以及新节点的关联度数作出判断：

若现有的邻居数+1<=最大邻居数，则接受Y；
　　否则，{从X的邻居中选择能力低于Y节点能力的节点，放在子集S中。
　　如果不存在这样的节点，则拒绝Y；
　　否则，{从子集S选择度数最大的节点作为候选节点Z。
　　如果Y的处理能力大于X的所有邻居节点的能力，或Z节点的邻居数大于Y节点的邻居数, 则放弃Z节点，接受Y节点；
　　否则，拒绝Y节点

单跳复制

为了提高搜索效率，每个节点动态维护其邻居节点内容的索引，这些索引在邻居节点间建立连接时相互交换信息获得，并周期性进行增量更新。这样，当一个节点收到查询信息，它不仅可以返回自己相匹配的内容，也可以返回其邻居节点的相匹配的内容。

当某一邻居节点因为拓扑自适应或节点离开系统而变成非邻居节点时，该邻居节点的的索引也要更新。

随机搜索

利用TTLs (Time-to-Live)和节点查询记录来避免冗余路径查询。发送查询的起始节点给发送的查询分配一个GUID。各中间节点将记录它将查询(GUID)转发给的邻居节点，使带有相同GUID的查询访问不再转发给已经转发过的邻居，这样，避免同一查询两次经过同一路径。每一个查询带有一个最大响应数的参数，即查询得到的匹配答案的最大数。

除了TTL，查询持续时间都将受到最大响应的限制。节点找到一个匹配的答案，查询的最大响应值都将减1。如果查询的最大响应值减到0，查询将结束。查询反馈信息将按原路径发回源节点。如果节点对查询有响应，无论相匹配的内容是来自自己本身，还是邻居节点的，都将拥有匹配内容的节点地址追加到该查询。这样就能保证对同一文件查询不会产生重复的回复；只有当节点有相匹配的内容并且不在查询消息列表中时，才生成查询响应。

模拟结果

我们通过模拟比较改进资源定位搜索方法(IRS)与经典的方法FLOOD法和SUPER(Supernode mechanism)，在评价中定义两个参数：1.失效点FP(failure point)：一个节点在阈值点的查询率，超过该阈值点，查询的成功率低于90%，这个参数可直接反映系统的处理能力，并与查询时延相关。 2.跳数(FP-HC)：在FP点之前的平均跳数(找到所查询文件所经过的跳数)。下表是在不同复制因子下改进方法(IRS)与FLOOD法和SUPER的比较结果。

可以看出，改进的方法(IRS)随复制率的增高，性能明显优于其它两种方法。不难看出，这是由于在SUPER方法中，超级节点之间使用洪泛法限制了其系统的可扩展性。IRS方法可以提高P2P系统的查询处理能力，并且在系统规模较大、查询量较大的时候，实现较高的查询成功率，具有较好的可扩展性。由上表可以看出IRS方法的可扩展性与系统的复制率有关。

综上所述，P2P系统最大的特点就是用户之间直接共享资源，其核心技术就是分布式对象的定位机制，这也是提高网络可扩展性、解决网络带宽被吞噬的关键所在。在充分考虑到节点多样性的基础上，通过拓扑自适应，单跳复制，搜索机制等方面提出了非结构化P2P网络系统网络上资源定位，资源搜索改进方法，以减少了查询需要发送的消息和需要访问的节点数，在提高系统性能提高的同时，保证系统的健壮性。

未来的网络将呈现大规模分布式、全球性计算和全球性存储的特征，从长远的趋势来看，对于访问和传输服务的需求必将远远大于对于计算功能的需要。随着分布式系统经典问题的解决以及优化的资源动态分配和资源恢复技术的成熟，P2P与网格技术必将结合起来，以影响整个计算机网络的概念和人们的信息获取模式。