对等点（P2P）网络搜索技术的研究

摘要

对等点（Peer-to-Peer，简称P2P）网络是一种新兴的复杂网络。随着P2P网络的广泛应用，人们发现即使每个用户提供少量文件，整个用户群所共享的文件数也是非常庞大的。要想充分利用这些资源，首先要能够快速准确地找到它们。因此，P2P网络搜索技术研究成为了一个重要的研究课题。 P2P网络搜索技术涉及到图论、统计物理学、网络测量、数学建模及算法设计等多个领域。如何利用近年复杂网络的研究成果对P2P网络模型进行优化与改进，以达到提高搜索效率和精度的目的；如何基于现有P2P网络模型设计出更加有效的局部搜索策略等已成为P2P网络搜索技术研究中的重要内容。 本文研究了基于P2P网络结构原理的复杂网络映射模型，分析了基于P2P网络模型的局部搜索策略的搜索性能。论文的主要内容和成果总结如下： ① 对复杂网络的研究背景进行了简介，并总结了现有P2P网络结构及搜索技术的研究成果。 ② 根据P2P网络是建立在Internet上的一种逻辑映射网络的特点，提出了一种基于较大规模的底层网络生成较小规模的映射网络模型的算法，并将均匀的随机图和非均匀的无标度网络作为底层网络，研究了所生成的映射网络模型的结构性质。仿真结果表明无论底层网络是均匀网络还是非均匀网络，所生成的映射网络都为均匀网络，并且随着关键参数比较半径的不断增大，网络将会越来越均匀。 ③ 研究了广度优先搜索、k阶遍历器随机游走和最大度搜索三种局部搜索策略在两种P2P网络模型—PRU（Pandurangan-Raghavan- Upfal）和CAN（Content-addressable Network）中的搜索性能，着重比较分析了搜索策略与P2P网络拓扑结构的关系。仿真表明，P2P网络中的最短路径分布是网络搜索中的一个重要影响因素。CAN中采用广度优先搜索不会在瞬间产生大量冗余的查询信息，降低了网络拥塞的概率，而具有适当遍历器个数的随机游走搜索能在PRU网络中产生比较理想的效果。