论文部分内容阅读
随着P2P网络的快速发展,越来越多的人在P2P网络上获取或者共享信息资源。资源共享已成为P2P网络最主要的应用之一,资源搜索机制的有效性是影响其应用能力的关键。当前如何设计高效率、低代价,且适合分布式的、动态的无结构P2P网络的搜索算法已成为P2P网络研究中的热点。目前存在的经典的网络搜索算法主要有:泛洪(Flooding)、随机游走(Random Walk,简称RW)、最大度(Highest-Degree Local Search,简称DS)等,但是这些策略均没有找到搜素效率与搜索代价之间的最佳平衡点,算法性能不够理想,无法应对未来大规模、分布式的动态无结构P2P网络环境的要求。
针对无结构P2P网络搜索算法效率低下的问题,研究者们提出了利用agent设计搜索算法的思想,并设计了RW,DS,VD(Virtual Degree Local Search)等搜索算法。所谓agent就是指信息世界中具有一定程度智能,能代表用户自治地完成任务的实体。本文则通过进一步分析DS搜索算法的缺点和无结构P2P网络幂律分布的特点,首先提出了基于跳转次数的局部搜索算法(Local Search withJump_times,简称LSJ)。该策略区别最大度结点搜索算法:它提高了选择agent移动中所要暂停的结点的条件；同时若agent在所在环境中无法找到满足要求的结点,则将会跳到其它区域继续搜索,算法用跳转次数来控制agent的活动。然后本文采用GLP算法生成的网络对比分析了此算法与经典的搜索算法在搜索性能上的差异。实验结果表明,LSJ在减少重发查询信息的次数和提高搜索覆盖率方面均优于经典的搜索策略。这是因为在搜索中agent不但最大限度的利用度数高的结点转发查询信息,而且agent有效的跳出当前的搜索区域,从而扩大了搜索范围,减小了结点重复转发查询信息的几率。
为了进一步提高无结构P2P网络搜索算法效率,本文依据无结构P2P网络的弱连接特性,又提出了基于agent的“共同邻居最少”的局部搜索算法(LeastCommon Neighbors local search,简称LCN)。此算法的最大特点:用两个结点拥有的共同邻居数作为衡量该结点之间连接的强弱标准,根据“弱连接”现象,agent通过不断选择与其所在结点共同邻居最少的结点来转发查询信息,从而搜索算法在扩大搜索范围的同时减少了信息重复转发的几率,从而降低了通信代价。实验表明LCN算法与当前的搜索策略相比,无论在搜索效率还是鲁棒性方面均具有较好的性能。
总结以上工作,本文的主要贡献可归纳为:
(1)在深入分析网络搜索策略和网络结构等因素对搜索结果影响的基础上,依靠更有效的利用最大度结点在转发查询信息中的作用,提出了基于跳转次数的局部搜索算法(Local search with jump_times,简称LSJ),实验结果表明此算法可以更有效的提高搜索的效率。
(2)利用弱连接在信息传播中的作用,提出了LCN算。实验结果表明,此算法相对于当前已存在的基于agent的搜索策略具有更好的搜索性能和鲁棒性。