（计算机应用技术专业论文）ldpastry：移动p2p基于位置辅助的网络模型和路由机制.pdf

己0 。t 一 j i j i ill llji t lr 1 p i ll fl l l l 西华大学学位论文独创性声明1 y 17 5 0 2 6 8 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 z - 作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：啪吵跏殇7 指导教师签名易1 侄启7 日期：沙h r ；。 j 日期尊。( d 一3l l i i 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签名： 日期：w 7 口夕 嚣尝彳) 日期d 巾小3 、 i 西华大学硕士学位论文 摘要 移动p 2 p 网络( m o b i l ep e e r t o p e e rn e t w o r k ，简称m p 2 p ) 是由互相通信的移动 设备组成的，它受限于电池能源、动态多变的网络拓扑、移动设备的有限传输范围、较 低的存储和短暂的路由生命周期以及无线带宽等等。随着无线通信技术的进步和移动用 户数目的不断增加，在移动环境下进行p 2 p 计算成为网络研究努力的方向。 本文针对在移动自组网里泛洪查询产生大量的冗余消息同时可扩展性不好的问题 和p a s t r y 在底层物理位置邻近的节点在覆盖层可能相距很远出现查询绕路现象问题等， 提出了基于位置辅助的l d p a s t r y 网络模型。尽量使覆盖网络和底层物理网络相匹配， 其目的是降低网络时延、减少路由跳数、减少冗余、同时还考虑了开销和系统性能等问 题。该模型将网络中的节点按照实际物理位置的邻近性划分为不同的域，使得在底层物 理位置邻近的在覆盖层逻辑位置也邻近。新模型充分考虑了节点性能的差异，把节点分 为簇头、锚节点和普通节点，域之间的通信靠域内簇头管理信息表。论文中讨论了节点 的位置定位方式，节点的移动、加入、退出、失效问题以及路由查找算法。 另外l d p a s t r y 模型成功得把p a s t r y 中的叶子集合和邻居集合合成一个，统一称为 叶子集合，使得叶集在保证l d p a s t r y 路由正确性的同时还增强了其工作的局部性，同 时新增了一个簇头集合。实验结果表明，l d p a s t r y 不仅继承了p a s t r y 的可扩展性，而 且降低了网络流量，减少了路由定位开销，提高了搜索效率。 关键词：移动p 2 p ；移动自组网；网络模型；路由机制；位置辅助 ? 。l d p a s t r y ：移动p 2 p 基于位置辅助的网络模型和路由机制一- a b s t r a c t m o b i l ep 2 pn e t w o r k ( m o b i l ep e e r - t o p e e rn e t w o r k , r e f e r r e dt oa sm p 2 p ) i sc o m p o s e d o fm u t u a lc o r r e s p o n d i n gm o b i l ed e v i c e s ；i ti sl i m i t e db yb a t t e r yp o w e r ，w i r e l e s sb a n d w i d t ha s w e l la sd y n a m i cn e t w o r kt o p o l o g y a st h ed e v e l o p m e n to ft h ew i r e l e s sc o m m u n i c a t i o n s t e c h n o l o g ya n dt h eg r o w i n gn u m b e ro fm o b i l eu s e r s ，h o wt or u nap 2 pn e t w o r kt oc o m p u t e u n d e ram o b i l ee n v i r o n m e n tb c c o m e sac o n t i n u o u sg o a lt oa c h i e v e t i m e l yc o n s i d e r a t i o n a b o u tt h eu n d e r l y i n gp h y s i c a lt o p o l o g ya n dt h ee s t a b l i s h m e n to far o b u s tr o u t i n gs t r a t e g yi s c r u c i a li nt h ef a c eo fp r o b l e m sa st h ed y n a m i c a l l yc h a n g i n gn e t w o r kt o p o l o g y ，t h el i m i t e d t r a n s m i s s i o nr a n g eo fm o b i l ed e v i c e s ，t h el o ws t o r a g eo ft h em o b i l ed e v i c e sa sw e l la st h e m u t i n gs h o r tl i f ec y c l e ，e t c i nt h i sp a p e r , w h e r ei nm a n e t f l o o d i n gq u e r i e sg e n e r a t eal a r g en u m b e ro fr e d u n d a n t m e s s a g e sa tt h es a m et i m ep o o rs c a l a b i l i t yp r o b l e m sa n dp a s t r yi nt h eu n d e r l y i n gp h y s i c a l l o c a t i o no ft h ea d j a c e n tn o d e si nt h ec o v e rl a y e rm a yb ev e r yf a ra w a y q u e r ym u t i n gb e h a v i o r p r o b l e m so c c u r ，e t c p r o p o s e dl o c a t i o n - b a s e da s s i s t e dl d p a s t r yn e t w o r km o d e l t ot h e o v e r l a yn e t w o r ka n dt h eu n d e r l y i n gp h y s i c a ln e t w o r kt om a t c h , w h i c ha i m st or e d u c en e t w o r k l a t e n c y ，f e w e rr o u t i n gh o p se x t e n s i o n ，r e d u c er e d u n d a n c y ，w h i l ea l s ot a k i n gi n t oa c c o u n t o v e r h e a da n ds y s t e mp e r f o r m a n c ei s s u e s n em o d e lw i l lb et h en e t w o r kn o d ei na c c o r d a n c e w i t ht h ea c t u a lp h y s i c a ll o c a t i o no ft h ep r o x i m i t yd i v i d e di n t od i f f e r e n td o m a i n s ，m a k e st h e p h y s i c a ll o c a t i o nn e a rt h eb o t t o mi nt h el c i g i c a ll o c a t i o na n dc l o s ep r o x i m i t yt oc o v e r t h e n e wm o d e lf u l l yt a k e ni n t oa c c o u n td i f f e r e n c e si nt h ep e r f o r m a n c eo ft h en o d e t h en o d ei s d i v i d e di n t oc l u s t e rh e a d ，a n c h o rn o d e sa n do r d i n a r yn o d e s ，t h ec o m m u n i c a t i o nb e t w e e nt h e d o m a i n sb yc l u s t e rh e a do fm a n a g e m e n ti n f o r m a t i o nw i t h i nt h et a b l e p a p e rd i s c u s s e st h e l o c a t i o no ft h en o d el o c a t i o nm e t h o d ，n o d em o v e m e n t ，t oj o i n ，e x i t ，f a i l u r e s ，a n dr o u t i n g s e a r c ha l g o r i t h m a n o t h e rs u c c e s sw a st h ep a s t r yl d p a s t r ym o d e lo fl e a fs e ta n dn e i g h b o r h o o ds e t si n t o o n e ，u n i f i e da sl e a fc o l l e c t i o n ，m a k i n gl e a fc o l l e c t i o nr o u t e si ne n s u r i n gt h ec o r r e c t n e s so f l d p a s t r ya l s oe n h a n c et h el o c a l i t yo ft h e i rw o r k e x p e r i m e n t a lr e s u l t ss h o wt h a t ，l d p a s t r y n o to n l yi n h e r i t e dt h ep a s t r y 。ss c a l a b i l i t y ，b u ta l s or e d u c e st h en e t w o r kt r a f f i c , r e d u c i n g r o u t i n go v e r h e a dp o s i t i o nt oi m p r o v et h es e a r c he f f i c i e n c y k e yw o r d s ：m o b i l ep 2 p ；m o b i l ea dh o cn e t w o r k ；n e t w o r km o d e l ；m u t i n gm e c h a n i s m ； l o c a t i o na i d e d 西华大学硕士学位论文 目录 摘要j i a b s t r a c t i i 1 弓i 言1 1 1 研究背景和问题1 1 2 章节安排2 1 3 本文创新点3 2 拓扑不匹配问题与结构化p 2 p 模型4 2 1 移动网络中的广播技术及其拓扑不匹配问题4 2 2 基于d h t 的结构化p 2 p 模型7 2 2 1 c h o r d 协议。8 2 2 2 p a s t r y 协议9 2 2 3k a d e m l i a 仂- 议1 3 2 3 无线传感器网络1 3 3 国内外研究现状1 5 3 1 层次化移动p 2 p 覆盖网络模型1 5 3 2 基于物理拓扑的p 2 p 网络模型1 6 3 3 应用移动代理的p 2 p 网络模型1 7 4 基于位置辅助的网络模型l d p a s t r y 2 0 4 1 l d p a s t r y 模型的基本思想2 0 4 2 l d p a s t r y 模型的体系结构2 l 4 2 1 底层物理网络分区j 2 2 4 2 2 节点标识i d 的结构：2 4 4 2 3 簇头竞争机制2 5 4 3 节点位置定位2 5 4 3 1 锚节点位置信息获取。2 5 4 3 2 普通节点位置信息获取2 6 4 4 节点管理信息表3 1 4 5 节点移动、加入和退出3 3 4 5 1 节点跨区移动3 3 4 5 2 节点加入3 7 4 5 3 节点退出3 8 l u l d p a s t r y ：移动p 2 p 基于位置辅助的弼络模型和路由机制 4 6 l d p a s t r y 路由3 9 4 6 1 路由信息。3 9 4 6 2 路由过程。4 1 5 性能分析与实验。4 4 5 1 性能分析4 4 5 2 实验环境。4 5 5 2 1 n s 2 简介。4 5 5 2 2 实验环境4 6 5 3 数据分析4 7 6 总结及后续工作5 0 6 1 总结。5 0 6 2 后续工作。5 0 参考文献5 2 攻读硕士学位期间发表学术论文情况5 5 1 改谢! ；6 i v 西华大学硕士学位论文 1 引言 1 1 课题来源、研究背景和问题 本文课题来源于四川省教育厅重点项目：p 2 p 系统中复杂搜索技术的研究，项目编 号0 8 z a 0 2 3 。 移动计算与通信装置( 例如，蜂窝电话机、微型计算机、手持数字装置、个人数字 助理、可佩戴计算机) 的迅速增长正在推动信息社会的变革。有着固定基础设施的有线 通信网络已趋于成熟，但有线网络存在着使用的局限性，有线网络对物理线路的具有依 赖性( 例如：在覆盖不到的区域和有线设施已被破坏的区域不能使用) 。因此无线通信 网络成为了新的研究方向。 无线通信网络根据其组网控制方式一般分为两类：1 ) 集中式控制，即有中心网络 ( i n f r a s t r u c t u r e dn e t w o r k ) ；2 ) 分布式控制，即无中心网络( i n f r a s t r u c t u r e l e s s n e t w o r k ) ( 又称无线移动a dh o c 网) 。 有中心网络，例如有无线蜂窝移动通信网络，g s m g p r s 、c d m a 移动通信系统以及未 来的第三代蜂窝移动通信系统。有中心网络可以利用现成的基站等基础设施，在基站的 覆盖范围内方便地实现数据通信，但它存在的主要问题是建网成本高，建设周期长。 无中心网络，例如有无线移动a dh o c 网和智能传感器网络。它们都属于无线移动自 组织网，是一个由自组织节点或终端组成的集合。移动a dh o c 网络由一组无线移动节点 组成，是一种不需要依靠现有固定通信网络基础设施的、能够迅速展开使用的网络体系， 所需人工干预最少，是没有任何中心实体、自组织、自愈的网络；各个网络节点相互协 作、通过无线链路进行通信、交换信息，实体信息和服务共享；网络节点可以动态、频 繁地加入和离开网络，不需要事先通知，在此过程中也不会对其他节点间的通信有影响， 同时网络中的节点也可以高速移动，从而使节点群快速变化，节点间的链路时通时断。 当在特殊场合，如果没有预先部署好的固定设施可以利用时，此时需要一种能够临时快 速自动组网的移动通信技术，而a dh o c 网络可以实现此功能。在无线移动a dh o c 网中， 每个节点既是主机又是路由器，所有节点都参与对网络的控制分布。无线移动a dh o c 网 没有专用的固定基站，网络中所有的节点相当于移动的路由器，这些节点作为同等实体 相互连接，实现信息包的转发，它们都参与路由的发现和维护过程。移动a dh o c 网络是 对等网络，网络中的节点具有游牧特性：节点在一定的区域内自由移动，动态地产生和 拆毁其与其泡节点的关系。具有同一目的的一组节点能够产生节点编队( 即节点群) 并 且一齐移动，这类似于军队的编队和旅游中的旅行团队。 l o p a s t r y ：移动p 2 p 基于位置辅助的网络模型和路由机制 在移动自组网( m o b i l ea dh o cn e t w o r k ，m a n e t ) 里，网络本身在路由和传输算法 上都是以p 2 p 方式实现。移动网络在可靠性、网络拓扑稳定性、节点能力方面都要比有 线网络差，这使得开发基于移动网络的应用要比有线网络困难得多。p 2 p 作为一种分布 式计算模型，在互联网中的应用已获得了成功。在p 2 p 网络中，所有节点的地位都是相 同的，它们之间通过相互配合来完成资源发现、数据分发等任务。与传统的c s 模式相 比，它避免了对服务器的依赖，从而具有更好的可靠性、传输效率、容错性和扩展性， 这些特点也使得它尤其适合移动网络。基于m a n e t 和p 2 p 系统的这些特点，于是出现了 m p 2 p ( m o b i l ep 2 p ) 的概念，将p 2 p 部署在包括w i f i ，a dh o c ，3 g 等各种无线网络上进 行数据共享和传输成为一种新的趋势。 节点的移动性使得移动p 2 p 网络的覆盖层拓扑经常发生变化，造成覆盖层与底层物 理网络拓扑不一致，引起网络结构一致性问题，网络结构一致性问题会导致网络搜索性 能变差，产生移动性扰动( m o b i l i t yc h u r n ) ，引起数据传输的低效。同时如何以有效 的手段快速响应用户的资源请求关系到整个p 2 p 应用的效率和性能。p 2 p 系统是为共享而 产生的系统，移动p 2 p 系统的高度动态特征使其需要同样高度动态变化的资源发现策略 与之相适应。 在一个移动a dh o c 网络中，各个移动节点共享一个单一的公共信道，使用载波侦听 多址访问c s m a 协议，但是没有使用碰撞检测c d 协议，这种移动网络的同步不太可靠，不 能得到整个网络的拓扑信息来支持和帮助做出广播操作的时间安排，所以大多采用泛洪 进行广播，在泛洪基础上进行改进，但是如果盲目地进行泛洪，那么可能出现严重的多 余重播、信道竞争、传输碰撞问题。由于非结构化网络将重叠网络认为是一个完全随机 西华大学硕士学位论文 第2 章，介绍了三种基于d h t 结构化的p 2 p 网络模型。阐述了p 2 p 的基本概念， 详细分析了三种p 2 p 的体系结构，路由算法，并提出了它们的优缺点。 第3 章，介绍了国内外的研究现状。为本论文的l d p a s t r y 算法的提出做好了铺垫。 第4 章，基于位置辅助的p 2 p 网络模型l d p a s t r y 。本章是全文的核心部分，对该模 型进行了详细的分析论述。 第5 章，对l d p a s t r y 进行了性能分析和仿真实验，以验证前述的正确性。 第6 章，总结及后续工作。对本论文所作的工作做了概括性的总结，对后续的工作 做了进一步阐述，提出了本论文需要完善和发展的地方。 1 3 本文创新点 参照p a s t r y ，在m p 2 p 网络中提出了基于位置辅助的l d p a s t r y 模型，重在加入了位 置信息和对节点进行分层管理。另外l d p a s t r y 模型成功得把p a s t r y 中的叶子集合和邻 居集合合成一个，统一称为叶子集合，使得叶集在保证l d p a s t r y 路由正确性的同时还 增强了其工作的局部性。 l d p a s t r y ：移动p 2 p 基于位置辅助的网络模型和路由机制 2 拓扑不匹配问题与结构化p 2 p 模型 移动对等网络具有以下特征n ，： l 、节点自身资源受限：大多移动设备需要满足便携要求，然而当前移动终端的受 带宽、计算处理能力、存储能力、能量供应等限制，使其在贡献资源的同时必须考虑自 身的能耗等因素；同时服务连接的数量也受到限制。 2 、网络层编址和标识机制不统一：与传统p 2 p 系统的网络层采用固定不变的唯一 i p ( i n t e r n e tp r o t o c 0 1 ) 地址作为节点标识相比，移动网络环境的异构性使得其网络层 所采用的编址及通信方式有很大不同，要在其上建立统一面向应用的移动p 2 p 网络，就 必须屏蔽网络层中不同的网络设备标识的差别。 3 、网络拓扑结构不断变化：相对于传统p 2 p 网络拓扑结构相对的稳定来说，移动p 2 p 网络的节点移动性使拓扑结构不断发生变化，从而造成覆盖层( o v e r l a y ) 网络与底层物 理网络连接状态不匹配，最后引起资源发现和数据传输的低效。 移动网络中的广播技术嘲： l 、简单泛洪：简单泛洪要求每个节点重播全部分组，其算法从一个源节点给其所 有相邻节点广播一个分组开始，每一个相邻节点又将这个分组重播给自己的所有相邻节 点，且只重播一次。这个过程依此持续进行下去，直到全部可达网络节点接收到这个分 组后才停止。一 2 、概率广播法：基于概率的广播法使用对网络拓扑的某种基本了解来给节点分配 重播的概率。 ( 1 ) 计数器广播法；计数器广播法的基础就是一个节点接收到一个广播分组的次 数反比于该节点重播该分组所能够覆盖的新区域大小。一个节点接收到一个新分组后， 用一个随机数p a d 初始化计数器，随机选择的p a d 位于0 t m a x 秒之间。在p a d 秒计数其间， 每当接收到一个多余的广播分组，则将计数器加一。如果p a d 结束时计数器小于某个门 限值，则重播该广播分组；否则，只需要丢掉该广播分组。门限值大于6 表示可达新区 域范围非常小。 ( 2 ) 概率广播法；与泛洪有点类似，不过节点按照预先确定的概率进行重播。当 在节点密集的网络中时，多个节点共享类似的传输覆盖范围。所以使若干个节点停止重 播就能够节省节点的网络资源，同时又不会危害分组交付的有效性。当在节点稀疏网络 4 西华大学硕士学位论文 中是，共享传输覆盖范围少得多。因此假如概率参数不高，那么使用概率广播法则会导 致节点接收不到所有广播分组。 3 、区域广播法：基于区域的广播法假定各个节点具有共享传输距离，一个节点只 有在重播达到足够大的新覆盖范围的条件下才会重播。 ( 1 ) 位置广播法；位置广播法使用较为精确的期望新覆盖区域估计来决策是否重 播。位置广播法要求每个节点必须具有确定自己位置的能力，比如如采用内置的g p s 。 ( 2 ) 距离广播法；一个使用距离广播法的节点比较自己与每个先前已经重播一个 给定分组的相邻节点之间的距离。根据所接收到的一个新的广播分组，初始化一个随机 数p a d ，存储多余的分组。当p a d 结束的时候，检查所有源节点位置是否存在小于门限距 离的较近节点，假如存在，该节点不得播。 4 、邻区了解广播法 ( 1 ) 自行精减泛洪法( f l o o d i n gw i t hs e l fp r u n i n g ，f w s p ) ；这是最简单的邻 区了解广播法。自行精减泛洪法要求每个节点知道其一跳相邻节点的信息，通过周期 性广播“h e l l o ”分组来实现。 ( 2 ) 可扩展广播算法( s c a l a b l eb r o a d c a s ta l o g o r i t h m ，s b a ) ：s b a 要求所有节 点知道其两跳范围内相邻节点的信息。接收节点根据邻区信息的发送节点身份决定其重 播是否能够到达新节点。通过周期性发送“h e l l o “分组来获取两跳范围内相邻区域信 息。每个“h e l l o 分组包含本节点识别码( i p 地址) ，以及已知相邻节点列表。一个 节点接收到其所有相邻节点发送的“h e l l o 分组后，就获得以自己为中心的两跳拓扑 信息。 2 f i g u r e2 1b r o a d c a s tp l a ni n m o b il ea dh o cn e t w o r k 图2 1m a n e t 网络广播方案 口 口 口 口 四 f i g u r e2 2p r o b l e mo fs i g n a lo v e r l a p 图2 2 图2 1 ( b ) 的信号重叠问题 l d p a s t r y ：移动p 2 p 基于位置辅助的圆终模型和路由机制 采用以上的广播技术很容易产生广播暴。比如当一个移动节点决定将一条广播 给自己相邻节点的时候，所有这些相邻节点已经有了此条广播消息，这样就形 重播，浪费流量；反之一个移动节点广播一条消息后，假如其多个相邻节点都 该条消息，些时也可能产生严重的相互竞争；而且没有采取退避机制，可能会 而导致严重损害。如图2 1 ，白色节点为源节点，灰暗节点为中继转发节点： 更为严重，在( b ) 中，本来只需要两次发送就能够完成一个广播，但是，如果 的话，则需要七次才能够完成一个广播。 图2 1 ( b ) 如果反应到实际物理层中，就会产生一个信号重叠问题。产生这种多余重 播的原因是：从不同天线发出的无线信号很可能相互重叠在一起，若一副天线覆盖的范 围为一个圆，则如图2 2 可以反映图2 1 ( b ) ，图中的灰暗程度表示信号重叠程度。从图 中可以看出，很多区域被同一个广播分组覆盖多次，在最坏情况下，一个区域被同一个 广播分组覆盖多达七次。 此处来举一个算式，可以看出问题的严重。假设移动节点a 发送广播消息，移动节 点b 重播此条消息。设s 表示移动节点a 的无线电波覆盖范围，& 表示移动节点b 的 无线电波覆盖范围，重播覆盖区域为上图的阴影部分用s b 一。表示。设r 表示节点a 和b 的无线电波覆盖范围的半径，d 表示节点a 和b 之间的距离。可以推 出：is 口一i _ l 品i - i 邑n 矗l ij g r 2 4 区- 2 一x 2 d x ； 当d 一，时，覆盖区域为 。2 ，：、 is , 一l r 2i 等+ 半l 一0 6 1 a ，2 ，此时最大。理论证明一次重播只能够提供为前一次0 6 1 jz ， 的新覆盖范围。 叠加层和物理网络的拓扑如果不匹配，也可能使得同一消息可能多次穿越相同的物 理链接，从而引发大量不必要的流量。见图2 3 实线表示p 2 p 邻居节点之间的逻辑连接， 箭头表示沿着逻辑连接传送的查询消息，节点s 是发起查询的源节点。可以看见洪泛搜 索机制在p 2 p 网络叠加层拓扑结构中产生大量不必要的重复消息。图2 4 ( a ) 和( b ) 是( c ) 物理网络拓扑上的两个叠加层拓扑。假设节点c 1 和c 3 位于相同区域内，c 2 和c 4 位于另一 个区域。设c 1 和c 4 的物理链接时延是( c ) 部分中的链接时延最长的。可见( b ) 的叠加拓扑 结构比( a ) 高效。假设域内延迟为d 白，域间延迟为d k ，本地查询延迟为d ( 此处忽略 不计) 。那么图2 4 ( a ) 如四个节点要按c 3 _ q c ，_ c _ c l 全部游历，反映到实 际物理层的走向为： ( g - c l _ c 4 ) - ( g 呻c l c 3 ) _ ( g c l g 呻c ：) 呻( c 2 一c 4 呻c 1 ) ，此时遍历 6 西华大学硕士学位论文 四个节点的延迟时间是魄+ 5 叱+ 2 d 。一魄+ 5 丸，而( b ) 图延迟时间仅为d k + 豺加。 这就是叠加层和底层物理网络的拓扑结构不匹配所造成的问题。拓扑失配是指由于覆盖 网络的逻辑拓扑结构和底层物理网络的拓扑结构之间存在不一致，而使得应用层覆盖网 络中的通信给底层物理网络带来很大的负载。解决拓扑失配问题能使移动p 2 p 系统更合 理地使用底层的基础设施，大大有效地减少网络时延，降低不合理的网络流量。 f i g u r e2 3r e p e a tf l o o d i n g q u e r ym e s s a g e sg e n e r a t e d 图2 3 洪泛查询产生重复消息徊1 蓄她 l 飞i 苫 f i g u r e2 4t o p o l o g yd o e sn o tm a t c h 图2 4 拓扑不匹配问题旧1 2 2 基于d h t 的结构化p 2 p 模型 p 2 p ( p e a r - t o p e a r ) 网络中的每个p e e r 节点高度自治又相互依赖，所谓自治是指每 个p e e r 节点独立决定自己的行为而不受其他诸如集中式授权机构的控制。同时每个p e e r 节点又需要相互协作获得资源。p 2 p 一般不依赖于专用的集中服务器。网络中的每一台 计算机既能充当网络服务的请求者，又能对其它计算机的请求做出响应，提供资源与服 务。p 2 p q b 所有的p e e r j 匿过规则或者不规则的方式在网络体系结构的应用层建立虚拟连 接，使整个p e e r 群体互连组成了一个应用层，即逻辑上的叠加网络，称为覆盖网络( 0 v e r l a v n e t w o r k ) 。这一网络构建于底层物理网络之上，依赖于底层物理网络的支持，且它的构 建独立于底层物理网络( 如图2 5 ) 。 根据覆盖网的结构可以把p 2 p 系统划分为结构化( 如c h o r d 、p a s t r y 、c a n 、k a d e m l i a 等) 和非结构化( 如g n u t e l l a 、f r e e n e t 等) 两种。在结构化p 2 p 网络中，资源放置与网络 拓扑相关，输入的关键字通过分布式哈希函数d h t 唯一映射到某个节点上：然后通过路 l d p a s t r y ：移动p 2 p 基r 位篁箍助的网络模型和路由机制 糟理男终真实连接 d a 一一一。一0 h 【jf 卜、h 鲁_ 一二- -f r ， 8 【 - ： 6 、k j一 曩筮网缯虚报连接 f i g 2 5o v e r l a yn e t w o r k 图2 5 覆盖网络 算法同该节点建立连接，文件( 或文件指针) 存放在确定的位置上，系统提供从文件标 符到存放该文件节点标识的映射服务，然后通过查询请求路由到该节点。通过这些方 系统提供了一个可扩展的方案实现了文件的“精确匹配 查询。虽然结构化p 2 p 网络 保证路由有效进行，但在动态性极高的网络环境下，节点的频繁加入与退出需要较大 的维护开销，且当节点退出以后路由表没有及时重建也会导致查找失败。 以上几个均忽略了p 2 p 网络中的三种不匹配： 1 1 拓扑失配：p 2 p 网络是处在应用层的逻辑网络，然而现有p 2 p 网络的构建策略忽略 了底层基础设施的情况，但是p 2 p 网络中的通信又完全依赖底层基础设施的支持。对于 不受限制的p 2 p 网络构建策略会给底层基础设施带来相当严重的通讯负载。 差别失配：目f i p 2 p 网络的构建策略过分强调节点的地位对等性，忽略了网络中 各个节点之间的差异的客观存在。节点的自身能力和在p 2 p 网络中的角色之间的差异可 能导致网络中出现性能瓶颈，从而妨碍整个网络的运行效率。 3 ) 请求失配：p 2 p 网络中的资源在整个系统中具有一定的集中性，不是随机分布， 大部分的请求都是由少量内容丰富的节点提供的。另外对资源的成功查询历史记录没有 被用于指导以后的查询，使得查询效率低下。 2 2 1 c h o r d 协议1 c h o r d 算法在2 0 0 1 年由s t o i c a 等人发表。每个数据项和节点与一个标识符关联。它 的d h t 的关键字是一个z b i t 的标识符，即在【o 2 j 一1 】区间中取整数。标识符形成一个一 维的对z 取模的标识符环，范围为( 2 一1 ) 0 。一个节点的标识符指的是一个i d ；一个 数据项的标识符指的是一个关键字。从形式上而言，( k e y ，v a l u e ) 对( k ，v ) 由其i d 大于或等于k 的这样的节点持有，这样的一个节点称为关键字k 的后继。即在一个c h o r d 8 西华人学硕士学位论文 环中具有顺时针增长i d 的一个节点负责其( 指i d ) 逆时针方向之前的所有关键字。表2 1 总结- c h o r d 节点1 3 的路由表各项属性及其定义。如图2 6 ，是一个初始化标识符环，其 中z 一6 ，即有2 6 6 4 个标识符、7 个数据项和1 0 个节点。关键字k 5 的后继按顺时针方向 其下一个节点是节点n 8 ，其中k 5 就是这样定位的。因为它们的标识符相等，k 4 3 的后继 是n 4 3 。环结构对2 6 6 4 取模，其结果是k 6 1 定位在n 8 上。 硒1 ，- 。- 。、， n 8 的指钊。表 ，一、 乡矿、l k 5 j l d x目的i d 后继 墨黼一 f k 1 d 、 p l f n 1 7 0n 8 + ln i o 科，式4 3n v 1n 8 + 2n i o 2n 8 + 4n 1 5 3n 8 + 8n 1 8 4n 8 + 1 6n 2 4 5n 8 + 3 2n 4 3 f i g