基于P2P模式的普适服务发现策略的研究

摘要

随着普适计算时代的到来，各种支持普适计算环境的服务发现技术研究在如火如荼的进行。考虑到普适计算环境的高度自组织特性，P2P模式的资源查找算法为研究普适环境中的服务发现提供了优秀的理论基础。目前已有的P2P资源发现算法主要有集中索引算法、结构化算法、非结构化算法以及混合发现算法。集中索引算法以Napster系统为代表，采用了集中式的目录服务器机制，该算法存在单点失效的问题，即目录服务器将成为整个P2P系统的瓶颈，一旦中心服务器出现问题，将导致整个系统崩溃。非结构化算法代表系统为Gnutella，采用洪泛或类洪泛算法，每一个用户消息都将被广播给与该用户直接相连的若干其他用户，这些用户收到消息后，也同样地将消息广播给各自连接的用户，依此类推，直到请求被应答或消息的。VFL（Time To Live）值减少为O，该算法可靠性差，对网络的资源消耗大，安全性低，容易大量散播垃圾文件和病毒。结构化算法典型代表包括Tapestry，Pastry，CAN和Chord等，它们都采用了一种分布式哈希表（Distributed HashingTable，DHT）的数据结构，并根据不同的算法决定网络中节点维护哈希表的方式。这几种采用不同节点和资源部署方式的结构化算法中，性能最好、应用最为广泛的是Chord。混合发现算法则结合了集中索引和完全分布式两种算法来构建网络拓扑。
　　 本文针对如何提升结构化算法的发现效率和发现覆盖率问题，基于Chord算法，结合Small World理论，提出新的指针表构建算法。传统的DHT发现算法中，每个节点维护的指针表存储的是临近节点的节点信息。为了构建Small-World模型，本课题提出了添加远程节点信息的思想，每个节点维护的指针表通过计算后删除冗余信息，加入相应的远程索引。与一些已经提出的采用随机选取远程连接节点的算法不同，本文将通过本地节点的计算来选取远程节点，保证加入远程连接节点后既能使服务发现的范围覆盖整个网络，又不会增加指针表的长度，并简化了指针表的计算和维护工作。通过仿真证明了该算法能有效减小服务发现的路径长度，提高服务发现成功率。
　　 本研究分为五个部分：第一章介绍了P2P模式的资源发现研究背景和研究现状；第二章介绍了P2P网络的特点和P2P网络的搜索模式，为我们研究普适环境的服务发现模式奠定了理论基础；第三章介绍了原始的Chord及改进后的Chord协议，并分析了它们各自的不足。第四章给出了本文对Chord算法的改进方案，并对改进算法进行理论分析、仿真以及仿真结果分析；第五章是总结及展望。