基于小世界现象的P2P网络搜索研究

刘艳艳等

摘 要：本文依据小世界特性提出了一种P2P网络搜索引擎系统模型，并给出了系统模型中对等网络节点的拓扑结构，提出了一种搜索机制，使查询消息更高效的传播，实验数据说明本文搜索机制与洪泛算法相比更加有效。

关键词：小世界； P2P网络；搜索；簇

中图分类号： TP393.2 文献标识码：A

1 引言（Introduction）

非结构化P2P[1]在搜索方面的优势，引导人们开发基于对等网络的强大的搜索工具。其广泛采用的洪泛（Flooding）搜索机制[2]，查询从一个节点以广播方式传播到其他节点，直到查找到查询结果，从而导致每次查询都产生大量的网络流量，对网络造成很大的负担，影响了非结构化P2P系统的扩展性。本文依据P2P网络的小世界现象，提出一种搜索机制，以提高查询效率。

2 小世界现象（Small-world）

小世界[3，4]（SW：Small-world）现象简单地讲就是社会网络中任意两个陌生人之间，经过较少的中间相识者就有可能建立起联系。这种现象在社会科学中发展成为一个重要的研究领域以后，经过许多次成功实验，证实在一个成功的通信链中，中间步骤的平均数总在5和6之间，称为“6度原理”。一些文献表明，P2P网络有时会自动演进到一个小世界[5]。

基于小世界现象构造的模型称为小世界模型，小世界模型基于这样一个原则：每个节点都表现出某些可以捕捉到的兴趣，兴趣相近的节点所保存的内容和提交的查询呈现出一定的相关性，通过挖掘每个节点的兴趣，使得相关性高的节点在网络中比较接近。这种按照节点间相关性组成的网络所表现出和社会网络相近的特性——具有较高的聚集度和存在短链，即所谓的小世界特性，小世界特性被证明对于提高检索效率是非常有效的。

3 基于小世界现象的P2P网络搜索引擎模型（P2P

network search engine model based on small

world phenomenon）

P2P网络的搜索引擎关键是对共享内容的深度挖掘，在对等节点之间进行信息检索时快速高效地进行信息反馈，要求寻找网络中对等节点之间的短路径。

在P2P网络搜索引擎系统模型设计时，考虑小世界模型簇聚合以及存在短链特点。簇聚合意味着具有度数较高的对等节点，这类对等节点在网络中的连通性较好，作为搜索引擎中的索引服务器保存文档的索引信息。存在短链意味着能够通过短链进行信息的检索和作为反馈路由。同时还考虑网络中资源信息本地化管理，资源信息搜索由本地网络发起进行全局检索，结合小世界模型构建如图1所示的小世界P2P网络搜索引擎系统模型。

图1描述的搜索引擎系统模型以P2P小世界网络为中枢，将信息搜索和对等点中共享的资源信息联系起来，整个系统模型分为三个层次：用户层（用户界面）、网络层（缓存、P2P网络、信息搜索和文件传输）以及文件处理层（文件处理和共享）。系统模型中信息搜索模块采用语义检索算法进行文档资源的信息搜索；文件传输模块主要是把文档进行分组传送和一般的网络数据传输相同；界面模块主要是采集用户查询请求。

5 实验分析（Experimental analysis ）

5.1 实验条件

模拟实验在自行构造小世界网络拓扑中进行文档的中文文档主题搜索，即搜索符合查询请求的文档主题信息，网络拓扑和文档主题数具体实验参数如表1所示，在构造的网络拓扑上实现泛洪式的Query Routing算法和本文提出的使用小世界网络中度数较高的节点进行关键字查询搜索，从查全率和查询产生的消息量两个方面对两种搜索方式进行比较。

实验中按照关键字进行查询，将文档主题进行简单分词处理，并对分词得到的关键字在每个节点中建立索引，在小世界网络中度数较高的节点对本簇中所有节点的关键字建立索引关联文件，将关键字、文档ID源文档IP地址和源文档端口号建立联系，实现快速定位，索引关联文件结构如表2所示。

5.2 实验结果及分析

实验1控制TTL值，随机选择20个节点发起查询，统计每次查询产生的查询消息量，最后计算平均值，实验结果如图3所示。

实验结果表明在相同TTL值的条件下本文提出的搜索机制搜索产生的查询消息量比Query Routing算法泛洪式搜索产生的查询消息量少。

实验2控制TTL值，随机选择20个节点发起查询，统计每次查询返回的文档主题数量，最后计算平均值，实验结果如图4所示。

实验结果表明在相同TTL值的条件下本文提出的搜索机制查询返回的文档主题数量比Query Routing算法泛洪式搜索返回查询结果数量多。

从实验中可以得出如下结论：在自行构造的小世界网络中，在相同TTL相同的情况下，本文使用度数较高节点搜索查询产生的消息量是使用全分布式无结构P2P网络的Query Routing算法泛洪式搜索的50%—60%，而进行关键字查询返回的结果文档主题数平均是Query Routing算法泛洪式搜索的1.37倍，即查全率为Query Routing算法的1.37倍。

6 结论（Conclusion）

本文在研究分析小世界模型特性的基础上提出了基于小世界模型的P2P网络搜索引擎系统模型，在此基础上提出了一种搜索机制，即使用小世界网络中度数高的节点进行消息传递的步骤数会减少，从而查询产生的消息量少，通过实验进一步验证了这一机制。但是由于进行的是关键字的查询，查询结果中存在非查询意图的搜索结果，查询的满意度有待提高。

参考文献（References）

[1] 罗杰文.Peer to Peer综述.中科院计算技术研究所，2005：2-3.

[2] 杨天路，等.P2P网络技术原理与系统开发案例[M].北京：人民

邮电出版社.

[3] （德）Ralf Steinmetz，等.王玲芳，等，译.P2P系统及其应用[M].北

京：机械工业出版社，2008.

[4] 周晋，等.基于Small-World网络的非结构化DHT算法.国家自

然科学基金项目（60003004），2005：109-117.

[5] 雷勇，李薇.基于小世界与兴趣相关度的P2P网络搜索研究

[D].微型机与应用，2012（18）：42-44.

[6] 杜丽娟，史定华，陈倩.增长的可导航网络模型[D].上海大学

学报（自然科学版），2009，15（1）：20-25.

作者简介：

刘艳艳（1982-），女，硕士，工程师.研究领域：软件工程.

李洪建（1981-），男，学士，高级工程师.研究领域：软件

技术及网络工程.

代兴义（1981-），男，硕士，高级工程师.研究领域：计算

机应用及软件开发.