一种基于dht的网格动态资源查找算法

《一种基于dht的网格动态资源查找算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、航空学报一种基于DHT的网格动态资源查找算法高艳丽（衡水学院经济学与管理学系，河北衡水053000）摘要：P2P与网格都是新型的分布式计算模型，在分析现有网格动态资源发现机制的基础上，将P2P的相关技术引入其中，提出了一种基于DHT的网格动态资源查找算法．该算法结合DHT技术和泛洪式查找技术，在实际的分布式网络之上建立一层结构化的Overlay层．实验结果表明，当用户需要在系统中获取信息时，通过该查找算法，查询只在一些特定的结点上进行，这样就避免了泛洪式查找的盲目性，因此大大提高了信息搜索的效率．关键词：网

2、格；P2P；DHT网络；泛洪技术；动态资源查找中图分类号：TP393文献标识码：A文章编号:1673-2065(2009)01-0016-05第1期高艳丽一种基于DHT的网格动态资源查找算法190引言网格作为一种分布式计算环境，目的在于利用互联网把分散在不同地理位置的各种可用空闲资源整合起来，实现计算资源、存储资源、数据资源等的全面共享，最终实现网络虚拟环境中的资源共享和协同工作．在任何资源共享的环境中，一个基本的服务就是资源发现，即当给出一个所需资源的描述，资源发现机制就返回一个与描述匹配的资源位置[1]

3、．P2P是一种实现资源共享的分布式技术，与网格在动态性和异构性方面具有相同的特点．但它们之间存在着两点主要的不同．首先，P2P系统最初被设计时主要考虑在各个peers之间共享文件资源，而网格则要处理计算资源、存储资源、数据资源等等不同类型的资源．其次，P2P系统的动态性主要体现在系统中的结点和共享的资源，它们可以在任何时间加入或者离开，然而在网格环境中，各个结点以一种相对静态的方式连接在网络上，网格的动态性主要体现在资源状态的快速变化上．考虑到P2P系统与网格自身的特点，P2P技术与网格技术进行了有效的融合

4、，在网格环境中利用基于DHT的P2P技术实现了对于某一类资源的多属性查询和范围查询[2-3]．然而，对于网格中的动态资源，由于它们的属性值变化非常的频繁，这就使得单纯应用DHT技术很难实现对于网格动态资源的查询．针对这一问题，本文提出一种基于DHT的网格动态资源查找算法，通过该算法能够有效地将DHT技术与动态资源查找技术相结合，从而实现网格动态资源的查找，同时对算法性能进行了分析．1相关工作当前，主要有两种P2P资源发现技术被逐渐应用到网格环境当中，一种是基于DHT的查找，另一种是泛洪式(Flooding)

5、查找．基于DHT的查找技术主要应用在对于静态网格资源的查找，因为动态网格资源属性值的快速频繁的变化，使得DHT的更新维护变得非常困难，因此，泛洪式查找技术被用于动态网格资源的查找和静态网格资源的模糊查找．见表1．表1不同类型的资源所采用的查找技术查找方式静态网格资源动态网格资源精确查找DHTFlooding范围查找DHTFlooding模糊查询FloodingFlooding第1期高艳丽一种基于DHT的网格动态资源查找算法191.1DHT概述在P2P通信中引入DHT是为了在实际网络之上建立一层结构化的Ove

6、rlay层，即一个逻辑层，便于信息的查找，而不需要像Gnutella那样每次查找信息都需要泛洪．基于这种思想产生了各种不同的DHT模型，包括CAN[4]、Chord[5]、Pastry[6]、Tapestry[7]、Kademlia[8]等．这些模型的主要不同之处是对于P2P结点的组织方式，但不论使用那种模型，在结点加入DHT网络时都需要为结点哈希产生一个标识符NodeId，从而决定它在DHT网络中的位置，以及它在逻辑网络中的路由表．每个结点要维护一些资源信息，即(key,value)对，key决定存储的目

7、标结点，value则是存储在目标结点的信息，可以是内容的索引，也可能是内容的本身．结点进行信息的插入和查找时，同样也是对信息的关键字进行哈希，产生一个键值K，找到NodeId与此键值K最接近的结点，进行操作．1.2Chord概述Chord在2001年由麻省理工学院提出，它采用一致性哈希作为哈希算法，在Chord协议中规定为SHA-1．Chord使用一个定长m位的标识符来标识每个结点，结点按标识符从小到大顺时针组成一个环形结构，如图1所示，结点加入Chord时随机产生一个标识符NodeId，根据此NodeId

8、由网络中已有的引导结点通过寻路找到维护此NodeId所在区域的目标结点，划分它的区域给新结点，更新其路由表，并帮助新结点建立一个新的路由表，称为finger表，表中包括m个后继结点和一个前驱结点，前驱结点即NodeId比本结点小的最近结点，设本结点NodeId为n，则m个后继结点分别为NodeId等于或大于n+20，n+21，…，n+2m-1的第一个结点，图1列举了NodeId为4的结点的finger表(m=6)