论文部分内容阅读
对等网络技术能够准确高效地提供精确匹配和多关键字查询等简单查询服务,是解决计算机网络中大规模信息资源共享的重要手段。然而随着网络规模的快速增长,拓扑结构多元化及用户对查询需求的不断提高,传统的对等网络搜索技术面临严峻挑战。
对等网络的拓扑结构是路由策略及查询类型的基础。不同拓扑结构适合不同的路由策略,支持不同类型的查询,因而具有不同的效率(成功率和响应时间)和代价(带宽和处理器资源)。研究并设计具有高可扩展性的拓扑结构及相关路由策略和查询类型是目前对等网络面临的重要挑战。
为了在对等网络上实现高效、低成本及可扩展地支持复杂查询这一目标,本文从非结构化和结构化两种拓扑网络出发,在路由算法、对等网络建模及复杂查询类型等方面开展了研究。本文的主要贡献包括:
1.针对非结构化网络上如何提高查询效率和降低代价,提出基于信任的概率优先路由算法Preferential Walk(P-Walk)。该算法将概率策略与信任机制相结合,利用查询反馈信息指导路由。根据实测数据设计非结构化网络仿真平台。大量对比实验表明
P-Walk不仅能提高查询效率、降低代价,而且能有效识别并隔离恶意结点,是一种在大规模分布式网络环境下可行的路由策略。
2.针对如何构建结构化拓扑以扩展支持复杂查询,设计环状结构化拓扑网络HarmonicRing(HRing)。分析HRing基本结构特点,设计结点加入、退出及失效处理操作。分析并验证HRing在静态及各种动态环境下的性能、代价及容错性。HRing的长链接构建独立于ID空间,这不仅消除了长链接分布、负载平衡及查询效率三方面的相互制约和影响,而且能使ID空间保留数据语义,支持复杂查询。
3.针对在结构化网络上如何支持复杂查询,提出在HRing网络上构建分布式索引和语义链的方法。对于分布式索引,提出索引结构设计策略及在HRing上的构建和维护方法。对于语义链,提出语义链的构建方法、维护方法及语义链网络的负载平衡方法。分布式索引和语义链使HRing能够有效支持基于关键字和基于关系的多种复杂查询。