论文部分内容阅读
针对提高大规模信息内容的搜索效率,非结构对等网络(Peer-to-Peer, P2P)技术成为占主导地位的关键技术。但由于网络规模和信息内容的不断增大,使得全局网络信息的获取变得十分困难。在这种情况下,本文基于非结构P2P网络中节点的局部信息与需求,对非结构P2P网络中的搜索机制进行了深入的研究,主要研究工作和取得成果概括如下:(1)提出一种非结构P2P网络受限搜索机制。在非结构P2P网络中,泛洪算法和随机漫步算法简单且易于实现,但其在搜索过程中产生的冗余消息消耗了大量的网络带宽资源。针对这一问题,提出一种受限搜索机制(RFSA),定义了搜索路径和冗余搜索路径,引入本地消息索引缓存机制和搜索消息实时路径追踪机制。通过节点对消息的受限接收,消除节点对消息的重复接收与转发。利用搜索过程中携带的实时搜索路径信息,选择未出现在搜索路径中的邻居节点对消息进行转发,消除冗余搜索路径的产生。从理论上分析了RFSA所产生的消息数目和网络开销。模拟实验分别从网络开销、查询点击率、搜索覆盖率和产生的冗余消息数目等方面对受限机制下和非受限机制下的泛洪算法和随机查找算法进行了对比分析,实验结果表明在搜索覆盖率和查询点击率基本相同的情况下,受限机制下的泛洪算法和随机漫步算法能够减少大量冗余消息的产生,降低网络开销。(2)提出一种基于不同查询的可信搜索机制。非结构P2P网络中,搜索的盲目性是造成大量网络开销的主要原因之一。启发式搜索机制是降低搜索盲目性和网络开销的有效方法。启发式搜索依赖于历史的搜索信息指导未来的搜索,对重复资源的搜索更有效,但对于非重复资源和稀有资源的搜索其性能有待提高。针对这个问题,考虑社会网络与非结构P2P网络的相似性,结合社会学和心理学中人与人之间信任产生的原理,提出一种基于不同查询的可信搜索机制。首先,将节点对其邻居节点产生的可信度分为熟悉性产生的可信度和相似性产生的可信度,给出可信度计算方法。其次,从每一个查询出发,对查询进行区分,将查询分为熟悉查询与陌生查询,对不同的查询分别计算该节点对邻居节点的可信度,从而为查询推荐可信搜索节点,有效地完成搜索。实验结果显示,在三种不同的网络结构中,该搜索机制能够以较低带宽消耗获得较高的查询点击率,同时缩短了查询时间;对非结构P2P网络的动态变化也表现了良好的适应性。(3)提出了一种基于节点服务能力的两段式搜索机制。泛洪算法和随机漫步算法是两类典型的搜索算法。尽管泛洪算法在消息的向前传递过程中产生了大量的冗余消息,但其搜索覆盖了网络中最大的节点数;同时研究显示,泛洪算法在搜索的初期阶段产生了较少的冗余消息。另一方面,随机漫步有效地降低了冗余消息的产生,但其覆盖的网络节点较少,因而产生了更长的搜索时间。针对这些问题,提出了一种基于节点服务能力的两段式搜索机制CNSA。CNSA机制依据每个节点所拥有的局部信息,定义了邻居节点的服务能力,给出一种基于节点服务能力的邻居节点选择策略。并将搜索过程分为两个阶段。第一阶段是在低的TTL内实现一种受限的泛洪算法,对泛洪算法产生的冗余消息进行有效的控制,并使搜索获得一个有效的、充分大的覆盖范围。在第二阶段,即在高的TTL内实现基于节点服务能力的启发式搜索。CNSA算法充分利用了泛洪和随机漫步两种算法的优点,并结合启发式搜索机制的优点,在提高搜索宽泛性的同时,降低了搜索的盲目性。实验结果显示CNSA在8跳之内就能够获得90%以上的点击率。(4)提出了一种基于局部需求的稀有资源主动复制与搜索机制。非结构P2P网络中,已有的搜索协议对流行资源的搜索是有效的,但对于稀有资源的搜索是低效的。提高稀有资源的副本率是解决其搜索低效性的根本方法。由于稀有资源在网络中的副本较少,其查询的点击率较低,因此已存在的基于成功查询的被动副本复制策略不适合稀有资源副本流行度的提高。针对该问题,本文提出了一种稀有资源的主动搜索复制策略,由拥有稀有资源的节点主动发起对稀有资源的搜索,在搜索过程中有效获取局部需求信息,将稀有资源主动复制到有需求的区域内,从而实现稀有资源的按需复制,有效提高其流行度和点击率。基于局部需求信息,提供了三种不同的按需复制策略,并给出了一种稀有资源搜索算法。实验结果表明,这种稀有资源的主动复制与搜索策略,能够以较低的复制消耗和网络开销,有效地提高稀有资源的副本率,从而提高稀有资源的查询点击率。