对等网络中基于关键字的搜索

摘要

对等网络以其大规模，自组织，以及健壮性等优特近年来受到学术界越来越多的关注。自第一代对等网络系统Napster开始，文件共享一直是对等网络的一个非常重要的应用。由于对等网络的大规模的特点，文件共享系统可以充分利用各个加入该系统的用户的资源来提高服务的质量。然而这一特定也同时给对等网络文件共享系统带来了很大的挑战。其大规模分布式的特性使得在对等网络文件共享系统中的文件搜索变得非常困难，同时给网络也带来了非常大的负担。因此，如何在对等网络中实现高效的搜索是一个非常重要的研究课题。 本论文将系统研究在两类流行的对等网络系统中——非结构化对等网络和结构化对等网络——如果实现高效的基于关键字的搜索。针对于对等网络大规模分布式的特点，我们着力于从提高搜索准确率和降低网络负担两方面来研究这一课题。以前提出的搜索机制往往要么搜索效果不佳、要么网络负担比较重，而很少能同时兼顾两方面。我们提出的搜索机制能很好的平衡两方面的因素，实现高效的对等网络搜索。 在非结构化对等网络中，本文提出了一种基于学习的查询消息路由协议来实现高效的搜索。由于它利用了路由过程中查询及查询应答消息所携带的信息来构建和维护查询路由表，极大地减轻了查询对于网络所带来的不必要的负担。同时我们充分利用了在现实对等网络中所观察到的查询消息存在大量重复这一现象，利用加强学习的思想来达到优化查询路由决策的目标。这一机制相对于以前所提出的机制而言，同时获得了满意的搜索结果和极低的额外网络负担。 在结构化对等网络中，文件按照其关键字在不同的节点上建立索引。对于多关键字的搜索就需要将不同关键字所对应的文件列表在节点间进行交换来实现来找到同时具有这些关键字的文件。由于单个关键字所对应的文件数量非常大，这一过程中网络负担也很严重。通过分析我们发现多个集合的交集的大小是由这几个集合的特性决定的。因此，找到一种合适的多集合求交的顺序策略，就能极大的降低这一过程中的网络负担。本文提出了一种高效的调度策略极大的降低了网络负担。