基于分布式哈希表的对等网络数据检索研究

摘要

P2P(peer-to-peer）系统是一个迅速发展的研究领域。P2P系统的应用已从传统的文件共享领域逐步扩展到更广泛的广域分布计算领域，因而需要P2P系统提供确定性定位与低查询开销等关键特性。基于分布式哈希表(DistributedHashTable，简称DHT)的P2P系统在广域网支持巨量集的数据一致性分布，并提供低跳步的路由精确定位，以及具有低查询开销和高容错自组织等优良性能，已经成为学术界研究的热点。 然而，分布式哈希表技术的引入在带来其先进性的变革影响的同时，也带来了新的挑战性问题。第一，由于拓扑是一种结构化的拓扑，相对比非结构化的拓扑，其维护开销显著加大。特别是在大规模和动荡的网络环境下，维护开销相当可观。第二，由于DHT采用哈希技术仅提供精确查询匹配，使用查询受到极大的约束。如何突破精确查询匹配的限制，增强P2P查询能力是当前P2P系统的急需解决的问题。本文针对上述问题，主要主要研究贡献如下： 1．结构化DHT系统能够提供高效、可靠的服务，有着巨大的潜在应用前景。然而在典型的动态环境下的结构化对等网络存在的维护开销过大问题，尤其是在高度动态的环境下。在本篇论文中，我们通过P2P网络中的节点会话特性，提出了一个基于DHI拓扑的超级节点对等网络SPChord来控制维护开销。该系统使用了一个简单但是有效的聚簇技术生成超级节点对等网络。主要的技术优点有：(1)簇的管理方式是自然演化的，管理开销很小。由于它不依赖于任何附加的前提条件，所以它可以直接应用于现有的DHT算法的改进。(2)即使簇的大小很小，它也能大大改善系统的维护开销和性能，这就意味着相比于现有的普通DHT对等网络系统来说，它有着更好的可扩展性，使得DHT系统能够更好地适应动态网络。仿真结果表明维护开销得到了极大的减少，而查找失败率也有很大程度的减小，同时查找性能也大大提高。 2．针对当前对等网络信息检索系统存在的无法适应高维文本空间以及检索代价过高的问题，提出了基于索引汇聚的对等网络信息检索系统IRSPC，该系统构建在SPChord叠加网之上，主要的创新点有：(1)IRSPC综合了结构化对等网络和非结构化对等网络的查询方式，并引入了信息检索领域的评价机制，保证和查询相关程度高的文档能以较小的代价优先被查询到。(2)关键词权重的计算完全是分布式的，不依赖于集中式的统计数据(如TFIDF的计算)。(3)IRSPC能适应高维大文本集的全文检索，并且具有良好的可扩展性和查询精度。 3．针对当前DHT系统多关键词检索效率低下、网络带宽开销过大的问题，我们采用了TFIDF关键词赋权技术和关键词关联关系挖掘以改进对等网络关键词检索效率，提出了基于关联关键词集检索的DHT对等网络关键词检索系统pKSS。pKSS的主要的创新点有：(1)通过WWW或FTP搜索站点的查询日志挖掘关键词之间的关联关系，并根据关键词之间的关联关系对文档索引词和查询语句中的查询词分组以支持基于关联关键词集的对等网络检索。(2)通过采用TFIDF技术，选出文档最重要的L个索引词并连同关联关键词集发布到对等网络。当用户发布查询时，查询中的关键词按照其IDF值和相互之间的关联关系进行分组，因而使pKSS的关键词检索效率在关联关键词集划分的基础上得到大大提高。实验结果清楚地表明：pKSS在索引的插入和存储开销上要远远低于KSS，在查询的带宽开销上也明显比标准的分布式倒排索引低。 4．针对当前元数据描述规范广泛采用XML的现状，提出了基于DHT对等网络的XML元数据索引和查询系统PXIQ。PXIQ系统为XML数据查询提供了良好的可扩展性和丰富的表达能力。除DHT内在的固有特性之外，PXIQ还有几个独特的优特点：首先，PXIQ能针对XML实施语义查询，查询语言采用XPath;其次，PXIQ能支持DHT对等网络中的范围查询；第三，PXIQ能支持DHT对等网络中的关键字检索和语义结构查询。从实验结果可以看到，PXIQ能够适应具有大量主机节点的对等网络环境。 5.针对当前DHT对等网络数据检索中存在的“热点”(负载不均衡)问题，本章提出了基于负载重定向的RLBA负载均衡算法以提高数据检索的性能和效率。RLBA负载均衡算法的整个负载均衡过程以及节点负载统计表的维护不依赖于任何集中式信息。该负载均衡的过程仅需要付出的代价为对节点资源的访问需要进行统计跟踪和重定向，一般的P2P数据检索系统从应用的角度也希望对节点资源进行统计跟踪，而负载重定向在DHT系统中进行负载均衡通常很难避免，并且重定向仅增加了一个路由跳数，对性能影响不大。因此，相对于其它的P2P负载均衡算法，RLBA算法的特点一是算法开销小，另外是不依赖于任何集中式信息。

目录

文摘

英文文摘

论文说明：本文主要图索引及表格索引

上海交通大学学位论文版权使用授权书及原创性声明

第1章绪论

第2章基于DHT拓扑的超级节点对等网络

第3章DHT对等网络中的信息检索

第4章基于查询词分组的关键词检索

第5章基于DHT对等网络的元数据查询

第6章基于DHT对等网络的负载均衡

第7章总结与展望

参考文献

作者攻读博士学位期间发表的学术论文

致谢