（计算机应用技术专业论文）基于兴趣驱动的p2p搜索方法研究.pdf

哈尔滨工程大学硕士学位论文 摘要 p 2 p ( p e c rt op c o r ) 技术是目前网络技术中的研究热点，如何高效地搜索 p 2 p 网络上的资源是p 2 p 网络技术的核心问题。无结构p 2 p 网络环境下基于 兴趣驱动的p 2 p 搜索方法的研究是其中一个重要的课题。目前，基于兴趣驱 动的p 2 p 搜索方法存在两方面的不足：( 1 ) 这些方法单一的从用户角度或从节 点内容本身角度来挖掘节点兴趣存在片面性。( 2 ) 这些方法在扩展搜索兴趣的 上下文语义方面还存在不足或根本无法扩展。 针对以上的问题，本文通过引入概念格理论，在基于社会网与小世界理 论的s o c i a l - p 2 p 方法基础之上，对s o c i a l p 2 p 方法进行了改进，提出了一种 改进的基于兴趣驱动的p 2 p 搜索方法( i i s m ) 。h s m 首先通过节点内容的匹配 算法和记录最近一段时间内的用户搜索行为来建立朋友列表，从用户与节点 内容两个视角体现节点兴趣，克服了目前基于兴趣驱动的p 2 p 搜索方法视角 单一的缺点。然后鉴于概念格理论的信息导航与扩展语义功能在信息检索领 域的成功应用，本文将概念格理论引入到基于兴趣驱动的p 2 p 搜索方法中， 把朋友列表作为形式背景构造概念格，通过生成具有偏序关系的概念来聚集 兴趣相近的网络节点，并以此建立兴趣域。搜索消息首先在概念格内查询， 通过概念使搜索消息在兴趣相近的网络节点中转发，以此来缩短搜索的路径 长度和搜索消息的数量，并且通过概念的偏序关系扩展了查询消息的上下文 语义，增强了搜索的精确度。最后，实验证实该方法比s o c i a l p 2 p 搜索方法 和传统的泛洪搜索方法具有更好的召回率和精确率，并且降低了网络负载， 提高了搜索效率。 关键词：无结构p 2 p 网络；p 2 p 搜索；兴趣域；概念格 哈尔滨工程大学硕士学位论文 a b s t r a c t p e e r - t o - p e e rt e c h n o l o g yi st os t u d yt h eh o tp o i n ti nn e t w o r k sa tp r e s e n t h o w t os e a r c ht h er e s o u r c e si nt h ep 2 pn e t w o r k se f f i c i e n t l yi st h ek e yp r o b l e mw h e n t h ep 2 pn e t w o r k sa r ed e v e l o p e d ，n l er e s e a r c h e so fi n t e r e s t - b a s e dd r i v e np 2 p s e a r c hm e t h o do nu n s t r u c t u r e dp 2 pn e t w o r ki st h em o s ti m p o r t a n ti s s u e n o w a d a y s ，t h e r ea r et o wd e f i c i e n c i e so ft h ei n t e r e s t - b a s e dd r i v e np 2 ps e a r c h m e t h o d ( 1 ) t h ei n t e r e s to fn o d ei ss o l e l yd i s c o v e r e db yt h e s em e t h o d sf r o mt h e u s e ro rn o d ec o n t e n t sp o i n to fv i e ww h i c hi su n i l a t e r a l ( 2 ) 1 1 1 e s em e t h o d sa r e l a c ko fc o n t e x ts e m a n t i ce x p a n s i b i l i t yo rh a v en o tt h ea b i l i t y a i m sa tt h ea b o v ep r o b l e m s ，p a p e ri m p r o v et h es o c i a l p 2 ps e a r c hm e t h o d w h i c hb a s e do ns o c i a ln e tt h e o r ya n ds m a l l w o r l dt h e o r yb yi n t r o d u c i n gt h ef c a m e t h o d t i l i sa r t i c l ep u tf o r w a r da ni m p r o v e di n t e r e s t - b a s e dp 2 ps e a r c hm e t h o d ( i i s m ) i i s mb u i l d st h ef r i e n dl i s tb yt h em a t c h i n ga l g o r i t h mo fn o d ec o n t e n t a n d r e c o r d i n gt h eu s e rb e h a v i o rr e c e n t l y , s o 吐l a ti tc a nb u i l di n t e r e s td o m a i nb o t hi n t h ev i e wo fa s e ra n dn o d ec o n t e n t n l em e t h o da l s oo v e r c o m e st h es i m p l i c i t yo f t h ep o i n to fv i e wi ni n t e r e s t b a s e dd r i v e np 2 ps e a r c hm e t h o da tp r e s e n t t h e n , i n v i e wo ft h es u c c e s s f u la p p l i c a t i o no fc o n c e p tl a t t i c e t h e o r yo nt h ea r e ao f i n f o r m a t i o nr e t r i e v a l ，t h ep a p e ri n t r o d u c e st h ec o n c e p tl a t t i c et h e o r yi n t ot h ep 2 p s e a r c hm e t h o d s t h e ni te x t r a c tf o r m a lc o n t e x tf r o mf r i e n dl i s tt ob u i l da c o n c e p t l a t t i c e n l ec o n c e p tl a t t i c ec l u s t e rn o d e so fs i m i l a ri n t e r e s ta n db u i l dt h ei n t e r e s t d o m a i nb yc o n c e p t sw h i c hh a v ed e f l e c t i o no r d e r i nt h i sm e t h o d ，n o d ef o r w a r d s m e s s a g eb yc l u s t e r i n gc o n c e p t sw h i c hc l u s t e rn o d e so fs i m i l a ri n t e r e s ta n dh a v e d e f l e c t i o no r d e r a n di t s c a p a b l eo fe x t e n dt h ec o n t e x ts e m a n t i cs e a r c hb yt h i s m e t h o d s ot h a tt h i sm e t h o dc a nc u td o w nt h es e a r c hp a t ha n dr e d u c et h es e a r c h m e s s a g e n l em e t h o dc a na l s oe n h a n c et h es e a r c ha c c u r a c y f i n a l l y , p a p e rv e r i f i e d t h em e t h o db ye x p e r i m e n t s t oc o m p a r e 、析ms o c i a l - p 2 ps e a r c hm e t h o da n d t r a d i t i o n a lf l o o d i n gm e t h o d t h er e s u l ti n d i c a t e dt h a ti i s mh a sb e t t e rr e c a l la n d 哈尔滨工程大学硕士学位论文 a c c u r a c ya n dl o w e rn e t w o r kl o a d s oi i s mr a i s et h ee f f i c i e n c yo fp 2 ps e a r c ht o c o m p a r e w i t ht h es o c i a l p 2 pa n dt r a d i t i o n a lf l o o d i n gm e t h o d k e y w o r d s ：u n s t r u c t u r e dp 2 pn e t w o r k ；p 2 ps e a r c h ；i n t e r e s td o m a i n ；c o n c e p t l a t t i c e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除文中已注明引用的内 容外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 ， 作者( 签字) ：初战缘 日期：矽岬年弓月泪 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：初娩罐导师( 签字) ：琊 日期： 2 口l 7 年弓月6 日，爰奄蚂年弓月i f 日 i 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题研究的目的和意义 随着互联网的迅速发展和广泛普及导致网上信息按指数级数增长。基于 开放互联的t c p i p 网络通信技术提供了简单易行的互联标准，网络规模越 来越大，连入网络中的设备、计算单元的数量和种类也越来越多，分布在 i n t e m e t 各个角落的各种资源也越来越丰富。因此如何在庞大的互联网上获得 有价值的信息已成为人们日益关注的问题。 搜索引擎为搜集、发现信息，并对信息进行理解、提取、组织和处理提 供了有力的帮助。传统集中式搜索引擎中( 例如：g o o g l e 、百度等) 以网页 快照、倒排序索引、集中检索为关键技术，采用客户机朋艮务器结构。集中式 搜索引擎存在以下局限性：把i n t e m e t 上的所有文档资源下载到搜索引擎的 数据库中是极其困难的，特别在信息成指数级数增长的情况下，这个问题在 不久的将来会更加突出；另一个局限是“蜘蛛程序”定期对资源建立快照，这 种间断的快照方式有两个不利结果，一个是“死链接”问题，另一个是i n t e m e t 上的最新数据不能被立即搜索到。 p 2 p ( p e e r - t o - p e e r ) 模式正是在资源规模和种类不断增大的情况下，用 于解决海量信息资源的合理利用问题而提出的分布式计算模式。在这种模式 下，服务器与客户机的界限消失了，网络应用的核心从服务器向网络终端设 备边缘化，无需依赖集中式服务器。成员之间主动协作，直接从其他成员而 不是从服务器的参与中获益。由于数据存储、处理能力和网络带宽等都以一 种完全分散、异步的方式运行，各种负载可以得到均衡，有效地解决了资源 服务的瓶颈问题，并易于扩展。然而，这种分散也带来了一些问题，为了保 障搜索的效果，就必须遍历比较多的节点以获得较高的检索召回率【1 1 。遍历 节点的增多，必然导致更多的搜索请求在网络上传播，同时导致更多的无效 搜索请求的传播，这致使网络的效率下降。同时也增加了等待时间，影响了 哈尔滨工程大学硕士学位论文 工作效率。因此解决当前p 2 p 搜索方法存在的查全率的提高导致搜索时间较 大增长和网络效率明显降低的问题成为热点问题。 1 2p 2 p 搜索方法的研究现状 随着网络技术的不断发展，p 2 p 网络拓扑结构的发展也大致经历了三个 阶段。从中央目录式的拓扑结构，到纯分布式的无结构网络拓扑，再到结构 化的网络拓扑结构，p 2 p 的网络应用模型也随之不断的改变，其中，p 2 p 网 络模型的核心就是p 2 p 搜索技术。因此，随着网络模型的进化，p 2 p 搜索技 术也随之发生了改变。 目前，针对p 2 p 搜索算法的研究主要集中在无结构p 2 p 网络和结构化的 p 2 p 网络上，还有基于复杂搜索和基于内容的新一代搜索技术。当前p 2 p 搜 索技术中最重要的研究成果就是基于s m a l lw o r l d 理论【2 3 1 的无结构p 2 p 网络 的搜索算法和基于d h t t ( d i s t r i b u t eh a s ht a b l e ) 的结构化搜索算法。 在结构化的p 2 p 网络中，目前主要的研究是基于d h t 算法的逻辑覆盖 网络，并且主要有针对两方面的改进： ( 1 ) 基于拓扑结构上的改进。其中，具有代表性的研究项目主要有加卅i 大 学伯克利分校的c a n 项目 5 1 和t a p e s t r y 项目 6 1 ，麻省理工学院的c h o r d 项目 川，以及微软研究院的p a s t r y 项目等。这些系统一般都假定节点具有相同的 能力，都采用d h t 算法定位资源的，并且拓扑结构都具有确定性。因此，这 种方式对于规模较小的系统较为有效，但是这种假设并不适合大规模的 i n t e m e t 部署。 ( 2 ) 支持语义搜索方面的改进。由于，结构化p 2 p 网络一般采用d h t 的 方式，其资源定位一般具有确定性，因此结构化p 2 p 网络的只适合精确查找， 这就决定了它不能支持基于语义的复杂检索，而且也不适合大规模的应用。 许多研究都努力在增强结构化网络的语义搜索能力方面进行改进，文献【8 】中 提出了一种适用于d h t 的基于质心法的p 2 p 全文检索方法，通过l s i 方法 来挖掘单词间的语义关系，并通过对各个单词向量进行加权平均聚类的方法 来获得文档的内容索引，这种方法能较好地体现文本内容语义。文献 9 】从 建立相应的p 2 p 网络节点物理位置参照系入手，依据节点坐标间的相对距离， 2 哈尔滨工程大学硕士学位论文 - 来自组织聚类节点的物理邻居节点。并且通过将聚类节点的h a s h 输出值特性 与传统基本语义路由过程所遍历的节点i d 序列的特性相关联，归纳出目的节 点、传统语义路由中继节点序列、聚类邻居节点集三者之间的逻辑关联特性， 以提高语义路由的效率问题。 在无结构的p 2 p 网络模型中，传统的搜索方法如泛洪( f l o o d i n g ) 方法【1 0 】和 随机漫步( r a n d o m - w a l k ) 方法【1 1 1 等，具有二定的盲目性，在网络负载和搜索效 率方面存在瓶颈。为了提高搜索的精确性和召回率，目前的在无结构的p 2 p 网络中，搜索方法的改进主要集中在以下两方面： ( 1 ) 基于拓扑结构的改进。基于无结构的p 2 p 网络模型在拓扑结构方面的 改进主要是增加超节点的混合式拓扑网络，如g n u t e l l a 2 t 1 2 1 的系统中，就是采 用了超级节点的网络结构。在这种分层的网络结构中，每个超级节点即和叶 节点相连，又和其他超级节点相连，当超级节点收到来自叶节点的搜索请求 后，它将消息转发给其相邻叶节点和相邻的超级节点，相邻的超级节点收到 的消息后，转发给其所属的叶节点。在这个过程不相干的节点不参与搜索的 过程，因此可有效的避免采用单纯的泛洪式搜索所产生的问题，如产生过大 网络负载、不适应大规模的网络、大量消耗网络带宽等问题。 ( 2 ) 以小世界理论( s m a l l w o r l d ) 为基础的改进。 小世界现象特征的发现和引入会对p 2 p 搜索算法产生重大影响。尤其对于 无结构的p 2 p 网络，带来了很多的新思想。其中，基于兴趣域的p 2 p 搜索方法 成为了目前研究的热点。 基于兴趣局部性优化的p 2 p 搜索方法基于这样的原则【1 3 】：每个节点都表 现出某些可以捕捉到的兴趣，相近兴趣的节点保存的内容和提交的查询也相 近。通过挖掘每个节点的兴趣，把节点按照兴趣关系组成网络，使得兴趣相 近的节点在网络中比较近。如果将兴趣相似的节点划分到同一个兴趣域中， 搜索请求首先在兴趣域中传播，可大大提高搜索效率，减小网络流量。这种 按兴趣组成的网络表现出和社会网络相近的所谓“小世界”特性。这些特性用 于提高搜索效率证明是有效的。女1 n e u r o g r i d t l 4 】通过统计历史的搜索经验来聚 集兴趣相似的节点，减少了搜索的范围，增加搜索的查准率，但其主要依靠 关键字查找，缺乏语义相关性方面的扩展能力。s o c i a l p 2 p t l 5 】引入了社会网 理论，通过模拟社会中人与人之间的关系，修改节点的连接关系，以体现小 3 哈尔滨工程大学硕士学位论文 世界的特性，而且具有搜索的语义相关性扩展能力，但是其主要依靠其他工 具对信息的人工分类来划分搜索的主题，在体现上下文语义方面还缺乏灵活 性。文献 1 6 1 9 也通过不同的角度建立了兴趣域，以使网络呈现小世界的特 性，提高搜索的效率。 为了支持复杂搜索与更好的语义路由，最近还出现了一些新一代的p 2 p 搜索技术。这些技术更多的与数据库技术结合，将文件共享应用向复杂查询 处理方向转化并引导其向资源发现和语义网方向发展。其中基于内容的p 2 p 搜索是这方面研究的重点，其中语义异构问题和语义索引问题是难点。 目前这方面的研究中的热点是基于本体【2 0 1 的检索方式。借助于本体知识 很好地理解用户所提交的搜索消息，把搜索消息扩展成多个语义相关的消息， 合理地扩大了搜索的范围，从而有效地提高查全率。这种方式中每个节点通过 本体来描述共享数据加入系统中，每个节点根据本体定义了内容的上下文语 义，并且根据本体的上下文语义计算收到的查询与本地内容的相似度。文献 2 1 1 将网络分为虚拟的知识层和物理连接层，通过本体建立知识层之间的语 义相关度来确定转发消息的路由方向并确立消息的转发级别，提高了搜索的 语义精确性，文献 2 2 】也进行了类似的研究。 1 3 问题的提出 近年来，p 2 p ( 对等网络) 应用非常广泛，其中最流行的应用是无结构的p 2 p 网络下的文件共享。其主要原因是无结构的p 2 p 网络拓扑结构、搜索方法的 简单性和灵活性。从早期的n a p s t e r 到g n u t e l l a t 2 3 1 、k a z z a 等，p 2 p 文件共享系 统在不断的改进和演化，改进的主要目标是：找到更好的搜索方法，使得系统既 有较高的命中率，又具有较好的搜索效率。然而，现有的无结构的结构p 2 p 网 络都不能同时满足这个目标。传统的无结构的p 2 p 网络主要采用泛洪 ( f l o o d i n g ) 方法和随机漫步( r a n d o m w a l k ) 方法，造成了大量的冗余信息，增加 了网络负载，造成了网络拥塞，在查准率和召回率方面性能也不高，而且可 扩展性不强。所以为了减轻网络负载提高搜索的精确性和召回率，大多数研 究采用了内容聚类和挖掘节点兴趣等方式。这些方式通过挖掘节点的兴趣把 有相似兴趣的节点之间建立联系，聚集在一起形成节点簇。这样在搜索请求 4 哈尔滨工程大学硕士学位论文 首先在兴趣域相同的节点之间转发，减少搜索的盲目性，增加了命中效率， 也减少了信息的冗余，减轻了网络负载。因此基于兴趣域局部化的p 2 p 搜索 方法的研究目前主要集中在如何聚类相似兴趣节点。目前，挖掘节点的兴趣 在视角上主要有两方面：一方面是从用户角度来挖掘节点兴趣，大多数的研 究也主要是通过挖掘用户的兴趣来聚类相似节点的，这种方式采用了对用户 提交的检索行为进行记录，以此来划分用户的兴趣的类别，达到聚类的目的， 如s a mj o s e p h 的n e u r o g r i d 通过学习历史搜索经验来挖掘节点的兴趣，动态 的自适应的聚集相似兴趣节点，达到兴趣相似节点聚类的目的。还有a l p i n e t l 6 1 方法，它把用户分成组来管理共享信息，每个组用户根据自己请求的被满足的 程度来评估其他用户，并设定信任值。在这种方法中组的建立完全依赖于p 2 p 网络之外的用户，并以通过其他用户来定义自己的兴趣，但是用户各自的定义 方式往往不尽相同。文献【1 7 】根据节点的搜索兴趣来寻找相似节点，相似节 点间建立快捷链接，搜索请求通过建立快捷链接的方式转发。另一方面，是 从系统角度根据节点的内容聚类，研究发现节点存储的内容也在一定程度上 反映了节点的兴趣，所以把存储相近主题的节点聚在一起而达到分类的目的。 最近基于内容相似的无结构的p 2 p 搜索方法的研究也有很多，如文献【1 8 】提 出了一种利用节点之间的集合差异度实现基于内容的聚类的搜索方法，通过 集合差异度计算将具有相似文件的节点聚集到一起，搜索时先找到自己所属 的“节点簇”，再在本簇中广播查询消息。文献 1 9 】是根据节点存储的信息资源 挖掘节点的兴趣，然后建立本地的兴趣索引表，以此转发搜索请求到相似节 点。 无论是从用户角度还是从节点存储内容角度来挖掘节点兴趣都存在一定 的局限性。( 1 ) 从用户角度讲，用户提交的查询只是反映用户共享兴趣的一个 部分，尤其对于提供大量信息的节点，所产生的查询只是反映其存储内容的 一个很小的子集，因此需要去挖掘其共享内容所反映的兴趣，从而使得网络 中其他节点在需要时能够高效地检索这些内容。( 2 ) 从系统角度看，挖掘节点 共享内容所反映的兴趣对于不断变化的且内容极大丰富的网络很难灵活的反 应用户的兴趣，并且由于网络的规模庞大，网络的全局视图难以确定，难以 对所有节点的内容进行聚类分析，还有网络中节点资源数量相差很大，对于 传统聚类方式也有很大难度。 5 哈尔滨工程大学硕士学位论文 1 4 本文的主要内容及章节安排 本文综合了用户行为和节点本地内容两个视角，在s o c i a l p 2 p 算法的基 础上进行改进，提出了一种基于兴趣驱动的p 2 p 搜索的方法。这种方法首先 在整体上从用户角度入手，根据社会网理论【2 4 】与小世界理论，建立朋友列表， 聚集相似兴趣的用户，然后通过形式分析方法，挖掘朋友节点之间的关系， 建立概念格，通过概念格把内容相近的朋友聚集成为概念，这样把搜索请求 转发到与之匹配的概念( 相似兴趣的节点簇) 中去，来更有效地提高搜索的精 确性和召回率，同时也减少了网络流量。 论文的主要章节安排如下： 第1 章论述了课题的研究背景和意义，总结了当前的p 2 p 搜索方法的国内 外研究现状和基于兴趣驱动的p 2 p 搜索方法存在的主要问题。 第2 章首先阐述了p 2 p 技术的理论基础，并介绍了当前p 2 p 的主要的三种 网络模型及其原理，然后对当前的基于兴趣域的p 2 p 搜索方法进行了研究， 为本文的研究打下理论基础。 第3 章主要对形式化分析方法( f c a ) 进行了讨论，阐述了f c a 的主要理论 基础以及概念格的理论模型和主要的构造方法，然后分析了概念格的分布式 扩展模型，最后根据f c a 的理论基础提出了一种基于概念格的兴趣域构建的 方法。为后面的论文研究中兴趣域的构建做好铺垫。 第4 章通过将f c a 方法融入至u s o c i a l p 2 p 搜索方法中，提出了一种改进的 基于兴趣驱动的p 2 p 搜索方法，这种方法通过小世界与社会网理论构建朋友 关系，并结合概念格理论聚类相似的兴趣节点。此章详细阐述了朋友关系建 立过程与朋友概念格的构建过程，并在此基础上建立兴趣域。然后阐述了这 种搜索方法的主要算法和同步机制。 第5 章通过实验证明了这种方法相对于传统p 2 p 网络的泛洪式搜索方法 和s o c i a l p 2 p 方法搜索方法的召回率与精确率都有明显提高，并且减轻了网络 负载。 6 哈尔滨工程大学硕士学位论文 第2 章p 2 p 技术概述 近几年来，p e e r - t o p e e r 技术成为了逐渐兴起的热门网络技术，它改变了 人们应用网络的方式，也为未来网络的发展提供了一种新的方向。从最初以 n a p s t e r 为代表的集中目录式的p 2 p 网络模型，发展到后来以c m u t e l l a 为代表 的完全分布式的无结构p 2 p 网络模型，然后再到以c a n 、c h o r d 、t a p e s t r y 和p e s t r y 等为代表的基于分布式哈希表( d h t ) 的结构化p 2 p 网络模型，p 2 p 网络的发展大致历经了三个阶段，分别采用了不同的资源定位技术和路由方 法。本章首先阐述一下p 2 p 技术的基本概念，然后对前面三种最重要的对等 网络模型加以介绍，并描述三种对等网络模型中的一些典型系统。最后，简 要介绍一下基于兴趣域的p 2 p 搜索方法。 2 1p 2 p 技术的介绍 p 2 p 的英文全称是“p e e rt op e e r ，其中p e e r 是“同等的人、伙伴”的意思。 国内一般将p 2 p 翻译成“端对端”或者“点对点”。计算机对等网络( p 2 p ) 技术是 目前流行于国际计算机网络技术研究领域的一个热点。在最近几年，p 2 p 技 术频繁见诸于在国际各大商业和主流杂志上，被财富杂志誉为将改变因 特网未来的四大新技术之一。并且，包括微软、s u n 、i b m 等许多著名的公 司和企业先后投入到对p 2 p 技术的研究中。而实际上，2 0 世纪7 0 年代中期， 源于局域网中文件共享的p 2 p 技术就开始流行起来，目前大家所关注的p 2 p 并 非新技术，而是旧有技术新的应用模式。 根据文献 1 3 】p 2 p 有两个层面的基本含义： ( 1 ) p 2 p 通信模式。这种模式区别于传统的客户机服务器或者主从 ( m a s t e r s l a v e ) 模式，每个通信方都具有相同的能力，并且每个通信方都可以 发起一个通信过程。 ( 2 ) p 2 p 网络。p 2 p 网络是运行在互联网上的动态变化的逻辑网络。这个 网络是由一些运行同一个网络程序的客户端彼此互连而构成的，客户端彼此 7 哈尔滨工程大学硕士学位论文 间可以直接访问存储在对方驱动器上的文件。 由此可见，p 2 p 网络中的每个节点兼具客户端和服务器的双重身份，既是 信息资源的获取者又是信息资源的提供者。随着各类数字终端、服务器资源、 网络带宽等资源不断的以类摩尔定律的方式增长，用更直接的共享方式来提 高沟通效率，从而进一步的提升网络、设备和信息服务的效能是人们一直追 求的目标。 目前，p 2 p 在加强网络上的文件交换、集群计算、协同工作、服务共享 等方面已经充分显示出了其强大的技术优势，其工作模型见图2 1 。 图2 1p 2 p 工作模型图 如图2 1 所示，与传统的c s 模式不同，在p 2 p 模式中，网络中的每一个节 点既是客户机，又是服务器，它们在网络中的地位是完全平等的。每一个节点都 是信息的提供者和信息的获取者，只要节点在网络中处于在线状态，就可以进 行信息的交换，这样在线的网络节点就可以获得即时的有效的信息资源，同 时也能提供即时的信息资源给其他节点。 2 2p 2 p 网络模型 从最初以n a p s t e r 为代表的有着中央目录服务器的p 2 p 网络结构，发展 到后来以g n u t e l l a 为代表的完全分布式的无结构p 2 p 网络和提供节点匿名发 布和获取文档的f r e e n e t ，再到以c a n 、c h o r d 等为代表的基于分布式哈希表 的结构化p 2 p 网络，p 2 p 网络的发展历经了大致三个阶段，分别采用了不同 的资源定位和路由模型。各种模型各有优缺点，有的还存在着本身难以克服 8 哈尔滨工程大学硕士学位论文 的缺陷，因此在目前p 2 p 技术还远未成熟的阶段，各种网络结构依然能够共 存，甚至呈现相互借鉴的形式。下面将对这三种最重要的对等网络模型加以 介绍。 2 2 1 集中目录式结构网络模型 最早出现的p 2 p 应用模式是集中目录式p 2 p 结构( 见图2 2 ) ，由于其仍然 具有中央服务器，所以也被称为非纯粹的p 2 p 结构。其中n a p s t e r 是最典型 的代表，它用来共享m p 3 音乐文件，并且它的用户注册与提供资源服务的 过程类似于传统的c s 模式，区别只是所有资源并非集中存储在服务器上， 而是分布的存储在各个节点中。查询节点根据网络流量和延迟等信息选择合 适的节点建立直接连接，而不必经过中央服务器进行。 h 查询 卜一- 下载 图2 2 集中式目录结构的p 2 p 网络模型 图2 2 中所示，每个节点( 如a 节点) 向中央目录服务器提交本地存储的 文档目录，并由中央目录服务器对文档进行注册，建立索引。例如当节点b 向中央目录服务器发起搜索请求时，中央目录服务器首先检索本地的文档索 引，然后向节点b 返回存储着相关匹配文档的节点c 的地址。最后，节点b 之间向c 节点发送搜索请求，节点c 响应请求，开始向节点b 提供下载服务， 而不再通过中央目录服务器。 9 哈尔滨工程大学硕士学位论文 在集中目录式p 2 p 模式中，由于采用了集中式的目录服务器，网络模型 可以提供快速准确的搜索服务，并且搜索的方式也可以很灵活，用户提供给 目录服务器的资源目录描述信息越详实，其准确度和灵活性就越高。但是这 种结构最大的缺陷在于可扩展性不高，集中式的中央目录服务器容易成为系 统的瓶颈。这种模型的另外一个缺陷是安全性较差，没有认证方法。 因此，尽管这种简单的网络结构显示了p 2 p 系统信息量巨大的优势，同 时也反映了p 2 p 系统在法律版权和资源浪费方面存在的问题。 2 2 2 无结构的纯p 2 p 网络模型 无结构的纯p 2 p 网络模型取消了集中的中央服务器，每个节点随机地接 入网络，并且节点之间是完全平等的关系，也就是对等节点。每个对等节点 都拥有若干邻居节点，并以端到端的方式建立了逻辑覆盖网络。每个对等节 点通过相邻节点广播传递查询消息和共享信息，同时为了防止产生搜索环路， 每个节点还会记录搜索的路径。由于缺乏中央目录服务器且文档并不存储在 特定的节点上，所以资源查找最基本的方式是泛洪f l o o d i n g ) 盲目搜索。 查询 + 下载 图2 3 无结构的纯p 2 p 网络模型 图2 3 是基于无结构的纯p 2 p 网络模型的示例图，图中每个节点都将接 到的搜索请求消息转发给它的所有的邻居节点，并由邻居节点再进一步转发 1 0 哈尔滨工程大学硕士学位论文 搜索消息给更多的邻居节点，直至找到期望的文件或者达到系统允许的最大 搜索跳数( t r l 为o ) 后搜索失败。如果成功找到目标文件，那么发起搜索请求 的节点就直接从保存目标文件的节点那里下载目标文件。 g n u t e l l a 2 3 i 是现在应用最广泛的无结构的完全分布式的网络模型，它取消 了中心服务器，具有较好的扩展性和容错性。 下面是g n u t e l l a 的搜索方法的描述： 7 a l g o r i t h m ：g n u t e l l a 算法 ( 1 ) g n u t e l l a 网络上的任何一个网络节点在需要查询资源时，先根据查询的内容形成 一条查询消息( q u e r y 消息) ； ( 2 ) 查询源主机将该q u e r y 消息发送给网络上所有与其直接相连的主机； ( 3 ) 收到q u e r y 消息的主机搜索自身的资源。如果有与查询消息相匹配的资源，则表示 命中，把命中响应按照q u e r y 消息传播的路径发送给源查询节点：如果没有，则不发送； ( 4 ) 收到q u e r y 消息的节点将该消息转发至除发送消息的节点以外的其他节： ( 5 ) 重复步骤( 3 ) ( 4 ) 。 g n u t e l l a 是一个用于文档共享的对等网络系统，最大的区别在于g n u t e l l a 是纯粹的p 2 p 系统，没有中央目录服务器。搜索请求同时转发给尽可能多的 邻居节点进行文档的搜索，它还通过设置大于零的t t l 值来限制每个搜索请 求传播的范围以避免过多的网络流量。对于大量分布在系统中的热门文档， 由于g n u t e l l a 以泛洪方式发送请求，因此查询的命中率高，并且部分节点失 效时不影响整个系统，具有较好的鲁棒性。但对于分布在系统中少量节点上 的稀有文档，g n u t e l l a 只能通过设置较大的t 1 凡值才能有效的找到，同时正 是由于使用了泛洪的方式传播消息，消耗了网络中大量带宽。虽然加入t t l 域后节省了一部分带宽资源，但又会出现“短路”的情况，即查找的资源虽然 在网络中存在，但由于超出了t r r l 值而无法定位到该资源。根据c l i p 2 公司 最近的研究显示，5 6k b p sm o d e m 用户最多处理查询消息2 0 个s 。当网络节 点大于10 0 0 时，处理极限被突破。随着这部分节点失效，o n u t e l l a 网络被分 片，使查询访问只能在网络很小一部分进行，导致网络可扩展性下降。 为了改进泛洪搜索的低效性人们纷纷提出了各种改进的方法。 随机漫步( r a n d o m w a l k ) 搜索从本质上和泛洪搜索方法相似，都属于盲目 搜索。和泛洪将搜索请求转发给所有邻居节点的方式不同，请求者发出k 个 1 1 哈尔滨工程大学硕士学位论文 查询请求给随机挑选的阶相邻节点。然后每个查询信息在以后的漫步过程 中直接与请求者保持联系，询问是否还要继续下一步。如果请求者同意继续 漫步，则又开始随机选择下一步漫步的节点，否则中止搜索。与泛洪搜索相 比，随机步搜索可以大大降低对网络带宽的消耗，提高系统的可扩展性，但 是随机步搜索方式的一个主要缺陷是搜索的延时比较大。假设一个随机步搜 索进程需要经过t 步才能完成搜索请求，那么n 个随机步进程同时进行搜索需 要经过的平均跳数为t n ，即搜索延时缩短为原来的1 n 。采用n 个随机步的搜 索方案带来的网络中流量的增加和单随机步相比是线形的，并不会像泛洪搜 索那样在网络中产生过量的流量，同时也降低了单随机步搜索带来的时延， 因此是在网络带宽的消耗和搜索时延之间的一种折衷方案。 在无结构的p 2 p 网络中还有一些经典算法 2 5 - 2 7 1 ，如下： j ( 1 ) m o d i f i e d b f s 方法： 这种方法是在宽度优先方法f l o o d i n g 上面作了一定修改。与泛洪搜索方 法不同，发出搜索的节点只是随机的选取一定比例的相邻节点作为查询信息 的发送目标，而不是发送给所有相邻节点。相比于泛洪方法来说，是以时间 换取空间的有效尝试。 ( 2 ) i t e r a t i v ed e e p e n i n g 搜索方法： 迭代递增是泛洪方法的改进，策略循环递增1 l 值，这个值用来控制泛 洪的搜索深度。跟泛洪搜索方法给，丌l 赋一个较大的值不同，这种方法在初 始阶段，给t t l 一个很小的值，如果在1 几减为零，还没有搜索到资源， 则给t t l 重新赋更高的值。这种策略可以减少搜索的半径，但是在最坏的情 况下，延迟很大，如果p 2 p 网络内重复资源丰富，这种方法在不影响搜索质 量的基础上将减少网络内的查询流量，这种算法也可称为e x p a n d i n g r i n g ( 扩 展环搜索) 。 ( 3 ) d i r e c t e db f s 搜索方法： 这种方法不将搜索请求发送到所有的邻居节点，而是根据节点所记录的 关于各个邻居节点的一些历史信息，只将搜索请求发送给一部分能够返回较 多结果的邻居节点，从而可以使用较短的时间得到所需数量的结果，并且可 以减少所需的消息量。为了能够智能的选择邻居，每个节点都维护了其邻居 的一些简单统计数据，比如该邻居以前返回的结果数，或到该邻居的延迟。 1 2 哈尔滨工程大学硕士学位论文 从这些统计数据中，可以实施启发式的选择最好的邻居来发送查询，比如： 选择返回以前查询的结果最多的邻居；选择以前返回结果中平均路径跳数最 小的邻居，结果的跳数越小就预示着该邻居到有用数据的距离越小；选择转 发查询消息最多的邻居，转发查询越多就预示着该邻居节点越稳定，处理能 力越强。 ( 4 ) r o u t i n gi n d i c e s 搜索算法 路由索引法中，每个节点维护了邻居的一些指标，节点根据这些指标将 查询请求转发给最好的邻居。这些指标是一个数据结构，给定一个查询，返 回一些按照这个查询某个方面的优劣程度排序了的邻居节点，从而使得节点 能够根据这个排序，将搜索请求传递到更可能响应请求的邻居节点。这种方 法不适合动态变化很快的对等网络。 ( 5 ) a d a p t i v ep r o b a b i l i s f i cs e a r c h ( a p s ) 搜索算法： a p s 使用k 个行走器，转发时不是采用随机选择邻居，而是根据邻居的 历史有选择的概率性的选择下一个转发节点。在这种方法中，对等体能够根 据以前搜索的反馈有效的指导行走器的搜索，同时只是保留了邻居的一些信 息。a p s 搜索有较高的准确性、较低的带宽消耗、能够发现较多的目标、在 动态环境中有较好的健壮行，这些特点来源于a p s 的学习方法。 ( 6 ) c a c h e 搜索算法 这种方法不同于盲目搜索的地方在与它在每个节点上，不管是中央节点 还是简单节点都存有路径信息。这就是c a c h e 的思路。新的搜索并不需要直 接达到资源的存储地，只要在搜索的路径中找到以前搜索的记录也就是在它 以前的搜索的基础上找到源p 地址，就可以把请求消息返回。这样可以极大 的减少搜索的消息，提高效率。 2 2 3 结构化p 2 p 网络模型 所谓结构化与无结构的p 2 p 网络模型的根本区别在于每节点所维护的邻 居是否能够按照某种全局方式组织起来以利于快速查找。结构化p 2 p 模式是 一种采用纯分布式的消息传递方法和根据关键字进行查找的定位服务，目前 的主流方法是采用分布式哈希表( d h t ) 技术，这也是目前扩展性最好的p 2 p 路 1 3 哈尔滨工程大学硕士学位论文 由方式之一。由于d h t 各节点并不需要维护整个网络的信息，只在节点中存 储其临近的后继节点信息，因此较少的路由信息就可以有效地实现到达目标 节点，同时又取消了泛洪算法。该模型有效地减少了节点信息的发送数量， 从而增强了p 2 p 网络的扩展性。同时，出于冗余度以及延时的考虑，大部分 d h t 总是在节点的虚拟标识与关键字最接近的节点上复制备份冗余信息，这 样也避免了单一节点失效的问题。 d h t 是一个广域范围内大量节点共同维护的巨大散列表。散列表被分割 成不连续的块，每个节点被分配给一个属于自己的散列块，并成为这个散列 块的管理者【2 7 1 。网络节点按照一定的方式分配一个唯一的节点标识符资源对 象通过散列运算产生一个唯一的资源标识符。当需要查找该资源时，通过散 列运算可定位到存储该资源的节点。 d h t 的主要原理：每一个节点都拥有一个地址标识( i d ) ，节点的内容用 关键字( k e y ) 进行标识，并且每个m 和k e y 在网络中的值都是唯一的。设计 一个哈希函数h a s h ( k e y ) ，建立d 与关键字( k e y ) 之间的映射。这样所有的 二元组( k e y , i d ) 构成了一个巨大的散列表，在查询关键字k e y 时通过 h a s h ( k e y ) 方式来找到对应节点。当然不同的d h t 算法的哈希方式不同。不 同的d h t 算法也决定了p 2 p 网络的逻辑拓补结构，比如c a n 就是一个n 维 向量空间，c h o r d 是一个环形拓补，t a p e s t r y 则是一个网状拓补。 下面介绍一下几种经典的结构化p 2 p 网络系统： ( 1 ) c a n c a n ( c o n t e n t - a d d r e s s a b l en e t w o r k ) ，是基于d h t 的结构化网络中的典 型系统。c a n 是基于虚拟的1 1 维笛卡儿坐标空间实现其数据的组织和搜索功 能的，整个空间被划分为许多区域，然后它将整个坐标空间动态地分配给系 统中的所有结点