【作者】 李林青；

【导师】 张德干；

【作者基本信息】 天津理工大学 ， 计算机软件与理论， 2010， 硕士

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

【Abstract】 With the era of pervasive computing comes, variety of service discovery technology that support pervasive computing environment is researching. Considering the high degree self-organization of pervasive computing environment.P2P service discovery algorithm provides a good theoretical basis for researching service discovery in pervasive environment.At present, the P2P resource discovery algorithms are concentrated indexing algorithms, structured algorithms, unstructured algorithms and mixed-discovery algorithm. Napster system as the representative of concentrated indexing algorithm, using a centralized directory server mechanism, there is single point of failure problem in this algorithm, the directory server will be the bottleneck of the entire P2P system, once the central server have any problems, will cause the entire system collapsed. Gnutella is the representation of unstructured algorithms, it using flood or similar flooding algorithm, each user broadcasts the message to the user which directly linked to it, after these users received the message, they also broadcast the message to the respective users who connect it.By analogy, until the request is answered or the TTL value of a message reduce to O.The reliability of the algorithm is poor,and the consumption of the network resource are huge.The typical representative of structure algorithms including Tapestry, Pastry, CAN and Chord, all of them are using a distributed hash table (DHT) data structure,and according to different algorithms they decide the way of the nodes maintain hash table in network. In these typical representation of structure algorithms, Chord algorithm has the best performance and used the most widely. Mixed-discovery algorithm combines concentrated indexing algorithm and fully distributed algorithm to construct the network topology.In this paper, we focus on how to enhance the discovery efficiency and coverage of the structure algorithm. Based on the Chord algorithm, combining with Small World theory, we put forward a new algorithm for fingertable construction. The traditional DHT discovery algorithm each node maintain the fingertable that store node information of adjacent node, In order to build Small-World Model, This issue put forward the idea to add a remote node information. The fingertable of each node delete redundant information by calculating, add the corresponding remote index.It is different from algorithm of select the remote connection node randomly. This paper selects the remote connection node by calculateing local node, after adding a remote connection node it can assure both make the range of service discovery cover all network and not increase the length of fingertable, simplifies the calculation of the fingertable and maintenance work. The simulation proved that the algorithm can reduce the path length of service discovery effectively, improve success rate of service discovery.This paper formed by the five chapters. The first chapter describes the resource background of discovery research and research status of P2P model; The second chapter describes the characteristics of P2P networks and search models of P2P network, these theory laid the foundation of service discovery in pervasive environment that we research; The third chapter describes the traditional Chord and Chord algorithm, and analyse the shortage of them; The fourth chapter gives an improved method of Chord algorithm. And theoretical analysis of the improved algorithm, simulation and simulation results analysis; The fifth chapter is the summary and prospects.更多还原