（计算机应用技术专业论文）基于相关度的非结构化p2p网络搜索优化算法.pdf

摘要 p e e r t o p e e r ( p 2 p ) 网络使得互联网中的普通用户在获取资源 的同时也成为资源的提供者，聚沙成塔的效应极大地丰富了网络中的 资源数量和种类，p 2 p 网络也因为这个特点而流行起来。如何高效率 地在网络中发现资源是影响p 2 p 网络发展的关键因素之一，这也成为 了近期计算机科学研究的热门课题。本文在分析了非结构化分散型 p 2 p 网络搜索机制的基础上，提出了改进的查询搜索算法：基于相关 度的自组织搜索算法和查询转发算法，设计和实现了基于改进算法的 原型系统，并且通过实验证明了改进算法的有效性。 分析了g n u t e l l a 网络的泛洪搜索机制； 提出了基于相关度的自组织搜索算法和查询转发算法。改进算法 使得网络中的节点在搜索资源的同时动态配置相邻节点，保持自己与 最有利的节点相邻，并且选择性地转发消息至相邻节点； 讨论了改进算法的效率、可行性、健壮性以及适用场景，指出了 本文算法与其他同类算法的不同之处； 描述了应用改进算法的原型系统的视图和工作流程，给出了原型 的结构和组件设计，定义了原型之间相互通信所使用消息的格式，并 且详述了原型的实现过程； 介绍了实验环境和步骤，并通过实验结果验证了改进算法的有效 性。 关键词p 2 p ，搜索算法，邻居节点，消息 a bs t r a c t p e e r - t o p e e rn e t w o r k sa r eb e c o m i n gp o p u l a rb e c a u s ew h i l et h e i r p a r t i c i p a n t sd o w n l o a d i n g r e s o u r c e sf r o mo t h e r st h e ya l s oa c ta sr e s o u r c e p r o v i d e r s ，w h i c he x t e n d st h ea m o u n to fn e t w o r kr e s o u r c e se n o r m o u s l y h o wt of i n dt h ed e m a n d e dr e s o u r c ee f f i c i e n t l yi so n eo ft h ek e yf a c t o r s w h i c hh a v ei m p a c t so nt h ed e v e l o p m e n to fp 2 pn e t w o r k sa n di th a s b e c o m eah o tr e s e a r c ht o p i ci nt h ef i e l do fc o m p u t e rs c i e n c en o w a d a y s i n t h i st h e s i s ，t h es e a r c h i n gm e c h a n i s mi nd e c e n t r a l i z e da n du n s t r u c t u r e d p 2 pn e t w o r k s ( p u r ep 2 pn e t w o r k s ) i sa n a l y z e da n dt w oi m p r o v e d a l g o r i t h m s ：ac o r r e l a t i o n - b a s e ds e l f - o r g a n i z i n gs e a r c h i n ga l g o r i t h ma n d a s e l e c t e d c a s ta l g o r i t h ma r ep r o p o s e d ap r o t o t y p es y s t e mt h a ti m p l e m e n t s t h ea l g o r i t h m si sp r e s e n t e d i nt h ee n d ，e x p e r i m e n t a lr e s u l t sa r eg i v e nt o s h o wt h ea d v a n t a g e so ft h ei m p r o v e da l g o r i t h m s i nt h i s t h e s i s ，t h ef l o o d i n g b a s e ds e a r c h i n ga l g o r i t h mu s e di n g n u t e l l a ( at y p i c a lp u r ep 2 pn e t w o r k ) i se x p l o r e d ； t w oi m p r o v e da l g o r i t h m sa r ep r o p o s e dt oe n a b l en o d e si np 2 p n e t w o r kt oc h a n g et h e i rc u r r e n tn e i g h b o r sw h e ns e a r c h i n gr e s o u r c e ss oa s t ok e 印t h e m s e l v e sn e a rt ot h ep o t e n t i a lp r o v i d e r so fr e s o u r c e sa n dt o c h o o s es o m eo ft h e i rn e i g h b o r st os e n dm e s s a g e sw h e nr e c e i v i n gt h e m f r o mo t h e rn o d e s t h e e f f i c i e n c y , f e a s i b i l i t ya n dr o b u s t i c i t yo ft h ei m p r o v e da l g o r i t h m s a r ed i s c u s s e d ；d i f f e r e n c e sb e t w e e nt h ea l g o r i t h m si nt h i st h e s i sa n do t h e r i n t e r e s t - b a s e da l g o r i t h m sa r ep r e s e n t e d t h ew o r k i n gp r o c e s so ft h ep r o t o t y p es y s t e mw h i c hi n v o l v e st h e a l g o r i t h m sa r ed e s c r i b e da n dd e t a i l s i nd e s i g n i n gt h es t r u c t u r ea n d c o m p o n e n t so ft h es y s t e ma n dd e f i n i t i o no ft h ec o m m u n i c a t i o nm e s s a g e f o r m a ta r eg i v e n d e t a i l si nt h ee x p e r i m e n ta r ei n t r o d u c e da n de f f i c i e n c yo ft w o a l g o r i t h m si sp r o v e db yt h ee x p e r i m e n t a lr e s u l t s p 2 p , s e a r c h i n ga l g o r i t h m ，n e i g h b o rn o d e s ，m e s s a g e i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特另t l d n 以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在论文中作了明确的说明。 作者签名： 口国 采f 镑t 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位 论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用 复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所 将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。 q 固 作者签名：墨! 鱼： 导师签名举日期：盟年月丑日 硕士学位论文 第一章绪论 第一章绪论 p e e r - t o p e e r ( p 2 p ) 技术正获得越来越广泛的应用，许多网络用户都使用过 p 2 p 文件下载软件、p 2 p 视频播放软件，也浏览过发表p 2 p 资源的网站。财富杂 志更将p 2 p 列为影响i n t e m e t 未来的四项科技之一。本文将开展针对p 2 p 网络查 询搜索的研究。 1 1 研究背景 在p 2 p 网络中，为数众多的普通节点成为数据的主要载体，打破了少数服 务器垄断资源的局面【l 】；节点之间直接交换信息，避免或减轻了单点故障和服务 器性能瓶颈的问题；节点拥有充分的自主性，可以自由地加入或离开网络【2 】。目 前的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 网络的搜索效率却相对较低。作为p 2 p 网络中的关键技 术，各种结构p 2 p 网络中的搜索算法直接影响着相应的p 2 p 应用的推广与流行。 在此背景下，分析具体的p 2 p 网络结构特点并研究对应的改进搜索算法具有积 极的意义。 1 2 国内外研究现状 n a p s t e r t 3 1 ，g n u t e l l a t 4 】等p 2 p 系统的广泛应用，使得p 2 p 成为计算机科学极 度活跃的研究课题【5 】【6 1 。现阶段，国内外p 2 p 搜索算法的研究热点主要集中在以 下三个方面：( 1 ) 在非结构化p 2 p 网络结构基础上，引入统计信息对节点的路 由进行指导，改善搜索的效率，避免泛洪搜索引起的巨大通信量；( 2 ) 在结构化 p 2 p 网络中，通过研究语义路由以及将节点在覆盖网( o v e r l a y ) 1 7 上的逻辑地址 与节点在物理网络中的i p 地址对应起来的方法，提高语义路由效率和可扩展性； ( 3 ) 在结构化以及非结构化p 2 p 网络的基础上，研究融合两者的方法，提出新 的网络模型，并提出基于新模型的资源分布、路由查找和成员关系降1 2 】。 在文献【1 3 】中，搜索引擎中广泛使用的t o p k 查询被应用到非结构化p 2 p 系 统中。文献作者采用了层次化的方法实现分布式的t o p k 查询，将结果的合并和 排序分散到p 2 p 网络中的各个节点上，充分利用了网络中的资源。其次根据节 硕士学位论文 第一章绪论 点返回的结果为节点构建直方图，利用直方图估计节点可能的分数上限，对节点 进行选择，提高了查询效率。文献【1 4 】的作者首先设计了一种键聚类( k e y c l u s t e r i n g ) 算法，通过逐步调整将节点索引记录按照一定中心进行聚类，在物理 网络层上建立具有全局视角的路由层，提高了搜索性能。然后利用小世界 ( s m a l l w o r l d ) i i 弘博j 的研究成果，将确定式聚类改为带有随机性的概率式聚类， 在导航表中引入指向远距离节点的快捷连接，减少了平均路径长度。 针对基于分布式哈希表( d h t ) 的结构化p 2 p 网络搜索问题，以下研究从 不同方面提出了改进方法。文献【1 9 】的作者研究了路由目的节点、语义路由节点 序列和聚类邻居集中节点三者之间的逻辑关联关系，并将其应用于所提出的基于 自组织聚类的语义路由改进算法s c s r a a ( s e l f - o r g a n i z i n gc l u s t e r i n gs e m a n t i c r o u t i n ga d v a n c e da l g o f i t h m ) 中，从而达到提高语义路由效率的目的。文献 2 0 】提出 一种新的基于匹配路径和概率平衡树的p 2 p 语义路由模型，该模型通过层次化 和匹配路径组织资源存储结构和节点排布方式，达到一种近似平衡的分布特征， 使节点能够根据查询内容本身进行路由决策，并同时保持较低的维护开销。与其 他p 2 p 系统相比，该模型在支持查询灵活性的同时保持了良好的可扩展性和路 由效率，维护成本相对较低。文献 2 1 1 针对提高访问资源的平均成功率提出了新 的资源索引分布方案，改进了结构化p 2 p 网络中的对象分布和定位。并依次建 立了全局映射关系、路由表、对象定位和路由算法、对象索引分布方案和节点加 入、退出时的维护算法。该模型适合于建立网络海量应用，能够适应众多节点自 发组成的动态网络结构，提供均衡的负载分布和较好的对象访问效率。由于基于 d h t 的p 2 p 系统不能有效地支持范围查询，a s p n e s 等人提出了一个称为跳图的 数据结构。因为不使用散列，与d h t 相比跳图能更有效地支持范围查询。另外， 由于跳图具有很多节点之间的冗余连接，跳图能够高度容忍节点故障。文献 2 2 】 阐述了一种可扩展分布式数据结构l i n k n e t 。与跳图相比，这种新的数据结构使 用虚拟链接减少了存储开销并加速了查找过程。 在综合研究结构化p 2 p 网络和非结构化p 2 p 网络的基础上，文献【2 3 】提出了 新的基于索引的结构化p 2 p 网络模型i s p 2 p 。i s p 2 p 采用两层混合结构：底层 是普通的p 2 p 网络节点，上层是性能较好的稳定的索引节点。底层节点与上层 节点相连，可以自由的加入和退出。上层节点组成结构化的索引网络，通过分布 式哈希表在索引网络中搜索资源。i s p 2 p 模型利用p 2 p 网络中节点的性能差异， 提高了查找性能，且能适应p 2 p 网络的高度动态性。文献【2 4 】提出了一个基于特 征信息定位的p 2 p 网络模型b a m e t 。b a r n e t 网络模型中节点之间的拓扑互联关系、 节点的加入、离开以及节点之间消息的路由方式采用作者提出的新p 2 p 路由模 型。该网络模型中的信息资源定位方式采用的是基于特征信息的定位。这种定位 2 硕士学位论文第一章绪论 技术避免了传统定位方法的单点瓶颈问题，同时提高了信息资源定位以及访问的 效率。 由于很多p 2 p 系统支持基于关键词的查询，为了弥补用户提交的查询用词 与节点中文档索引用词的差别以及用户查询信息的不足，文献【2 5 】提出了两种 p 2 p 环境下的查询扩展方法：利用查询与文档的关联关系构建的l e m ( 1 0 c a l e x p a n s i o nm e t h o d ) 查询扩展方法；基于查询与文档用词的直接关联提出的h e m ( h i s t o r yb a s e de x p a n s i o nm e t h o d ) 查询扩展方法。并在此基础上，提出了一种基 于查询扩展的混合p 2 p 环境下的搜索算法s e ( s e a r c hb a s e do nq u e r ye x p a n s i o n ) 。 s e 算法利用了历史查询记录信息，查询记录不仅蕴涵了查询与文档的关联关系， 也包含了查询、文档与源节点的关联关系，因而可以建立查询与节点的直接关联， 这种关联为路由查询提供了一定的指引信息。因此，查询扩展及其搜索算法能够 极大地提高搜索的效果。 在针对非结构化p 2 p 网络的研究中，信息搜索和将节点分类的聚类算法占 很大比例。本文的研究则从节点之间的关系着手，基于“用户将来很可能还会受 益于当前对用户有益的节点厣这一思想，提出优化的查询搜索算法。优化算法与 黄维雄等人提出的b e s t p e e r 系统 2 6 1 中自配置策略思想有相似之处，因此本文将 在第二章中将介绍该系统。 1 3 研究内容和本文结构 本文的研究内容包括：非结构化分散型p 2 p 网络的特点以及搜索机制；优 化的查询搜索算法；基于优化算法的原型系统的设计与实现；优化算法有效性的 实验验证。 本文共分6 章，第一章介绍了课题背景和总结了国内外研究现状；第二章简 要介绍了p 2 p 网络的相关概念、分类以及特点，并重点介绍了一个改进的p 2 p 系统卅e s t p e e r ；第三章详细描述了优化算法，并且分析了算法的特点；第四 章说明了基于优化算法的p 2 p 原型系统的设计与实现；第五章介绍了实验过程 并进行了结果分析；第六章总结了全文，提出了下一步工作的方向。 3 硕士学位论文 第二章p 2 p 网络及b e s t p e e r 系统 第二章p 2 p 网络及b e s t p e e r 系统 p 2 p 网络模型与客户服务器( c s ) 模型有较大差别，且不同结构的p 2 p 网 络之间有较大的区别【2 7 】，针对不同类别的p 2 p 网络，研究方向与手法也不尽相 同。本章简单介绍了p 2 p 网络的相关概念，着重描述了非结构化的p 2 p 网络模 型，为下一章做理论基础上的铺垫。 2 1 p 2 p 网络简介 p 2 p 网络并不是新概念，上世纪7 0 年代i n t e m e t 出现以来它就存在了。互联 网最基本的t c p i p 并没有服务器和客户机的概念，所有的网络设备都是平等的， 互联网上的任何系统都具有服务器和客户机的功能。然而，受到早期计算机性能、 资源等因素的限制，大多数普通互联网用户没有能力提供网络服务，因此逐渐形 成了客户服务器架构。在这种架构下，用户可以以低廉的成本方便的访问互联 网，推动了互联网的普及。然而，随着互联网日益深入到大众的生活中，人们需 要更直接广泛的信息交流。近年来，技术上的变化和个人计算机计算能力的提高 使这一需求具备了实现的可能性，并为p 2 p 带来了大范围的复兴。一个著名的 p 2 p 应用就是n a p s t e r 。n a p s t e r 为用户提供了r a p 3 音乐文件的共享平台，它使得 用户可以在网络上共享自己硬盘中的r a p 3 文件，也可以搜索其他用户共享的r a p 3 文件并下载。n a p s t e r 的p 2 p 特性使得它在短时间里就吸引了5 0 0 0 万用户。随着 n a p s t e r 的成功，各种p 2 p 应用纷至沓来，这些应用使用户可以通过p 2 p 网络共 享数据和计算资源以及进行实时通信。 总的来说，p 2 p 网络具有这些基本特点：( 1 ) 分散性：p 2 p 系统将信息的载体 和传送信息的带宽分布到了网络中节点上，信息传输和服务直接在节点之间进 行，无须中间环节的介入；( 2 ) 健壮性：由于分散性的特点，服务器的角色在网 络中被淡化或消除了【2 引，因此单点故障不会给系统的稳定性和服务质量带来影 响。( 3 ) 可扩展性：p 2 p 网络中的节点拥有双重角色：它们既是服务器也是客户 端，节点向其他节点请求服务也响应其他节点的请求。因此p 2 p 网络可以通过 集合更多的节点来扩充网络规模、资源和服务能力而不需要c s 架构中的高性能 服务器【2 9 1 。 2 2p 2 p 网络的分类及特点 p 2 p 网络没有固定的分类标准，划分依据也有多种。按资源组织与搜索机制， p 2 p 网络可以分为结构化p 2 p 网络和非结构化p 2 p 网络【3 0 1 。 4 硕士学位论文第二章p 2 p 网络及b e s t p e e r 系统 2 2 1 结构化p 2 p 网络的特点 结构化p 2 p 网络基于分布式哈希表( d h t ) 3 1 】将节点组织成特定结构的覆 盖网络。在结构化p 2 p 网络中，系统为每个节点分配唯一的标识i d ，为资源对 象分配关键字k e y 。当节点共享一个关键字为k 的资源时，通过哈希映射得到 对应的i i ) k ，然后将该资源的信息( 既可以是资源的位置也可以是资源本身) 存 放至i d 等于i d k 的节点。资源信息的存放过程需要将资源信息由共享节点路由 至i d k 节点。当搜索关键字为k 的资源信息时，先进行哈希映射得到i d k ，然后 从i d k 节点取得该资源信息。这种p 2 p 系统的优点是在进行资源定位时，可以保 证在一定查询跳数内找到网络中存在的资源，但是只能根据资源的键进行准确匹 配的查询【3 2 1 。另外结构化p 2 p 系统对结构要求过于严格，更新代价过大，因此 只适用于小规模组织严密的p 2 p 应用哪j 。 c h a r d 0 4 1 ，c a n t 3 习都属于结构化p 2 p 系统，c h o r d 由m i t 提出，它提供一个 合适于p 2 p 环境的分布式资源发现服务。该模型通过维护相邻节点的路由表来 进行资源定位和查找。通过使用d h t 技术使得查找指定资源只需要维护l o g n 长 度的路由表，但仍存在命名冲突、消息的传递效率不高和可扩展性差的问题。 c a n 项目是由b e r k e l e y 开发的，采用n 维集合分割的拓扑结构实现资源按内容 寻址。n 维几何分割的实现方法使得系统具有较好的可扩展性，但理论上比较复 杂【3 6 】。 2 2 2 非结构化p 2 p 网络的特点 顾名思义，非结构化p 2 p 网络没有特定的组织结构，但是p 2 p 网络控制层 面的实现有不同的方式。非结构化p 2 p 网络可以细分为以下三种结构：集中式 结构、分散式结构和混合式结构。 集中式网络结构中使用了中央服务器来实现一些管理。所有的节点需要登陆 中央服务器注册节点和共享资源的信息。资源搜索请求也被发送到服务器，服务 器若找到资源，则告知请求节点从拥有资源的对等节点上直接下载，此时服务器 不再参与。这种p 2 p 网络结构的特点是具有高效的查找效率，查找开销较小， 但是该结构有单点故障的缺陷：当中央服务器发生故障时，p 2 p 系统会崩溃。因 此，系统的可靠性完全依赖于中央服务器，安全性低3 7 1 。这种结构的代表是 n a p s t e r 。 5 硕士学位论文第二章p 2 p 网络及b e s t p e e r 系统 服务器 图2 - 1 集中式结构 分散式网络结构完全不设置中央服务器，查询以泛洪方式在网络中传播，收 到查询消息的节点首先查找本地文件，然后把结果发送至查询节点。这种网络结 构在查询过程中会产生很多查询消息，但是此结构具有容错性，可用性好。这种 结构的代表是g n u t e l l a 。 凰： 图2 - 2 分散式结构 混合式结构是以上两种结构的结合体，目的是继承两者的优点。通过引入超 级节点( s u p e r - p e e r ) 3 8 】，混合式结构既有集中式的特点又有分散式的特点。超 级节点成为与其相邻节点的服务器，就像集中式结构一样，超级节点完成这些节 点的注册与查询工作。超级节点又通过完全分布式结构连接起来。混合式结构在 控制层面引入了两层：一层是普通节点通过c s 模式连接到超级节点；另一层是 超级节点通过完全分布式无结构网络连接到一起。这种结构的代表应用是 e d o n k e y 、k a z a a 3 9 1 。 6 昌，直 i ， 、 一 昌、二，屠 硕士学位论文第二章p 2 p 网络及b e s t p e e r 系统 服务器 图2 - 3 混合式结构 针对现有的非结构化p 2 p 网络，有许多改进的p 2 p 系统被提出，其中包括 黄维雄等人提出的b e s t p e e r 平台系统。 2 3b e s t p e e r 系统 b e s t p e e r 是一个通用的p 2 p 系统平台，在这个平台上可以简单有效地开发各 种p 2 p 应用。b e s t p e e r 网络由两类实体组成( 如图2 4 所示) ，包括大量的普通 节点和少量的位置独立的全局名查找服务器( l i g l o ) 。网络中的每个节点都运 行b e s t p e e r 软件，可以与该网络中任意节点交互信息，共享网络资源。 n 图2 - 4b e s t p e e r 网络( 引用自文献【2 6 】) 7 硕士学位论文 第二章p 2 p 网络及b e s t p e e r 系统 b e s t p e e r 网络引入了移动a g e n t 技术【4 0 1 1 4 1 1 ，进一步提高了共享能力。因为 a g e n t 可以携带代码和数据，所以它可以有效地执行任何指定的功能。从而， b e s t p e e r 不但可以提供文件和原数据的共享，而且可以在数据提供节点本地处理 数据，然后只返回处理结果。b e s t p e e r 的另一特性是网络中的节点可以动态地重 新配置，这种方法的实质就是将最有益的节点保持在最近邻近的位置上。每个节 点可以自动地重新配置，并且节点可以重新定义它的直接邻居节点数量，以便为 自己提供更好的服务。在b e s t p e e r 中，有两个预先给定的重新配置的策略： 策略一( m a x c o u n t ) ：通过响应节点返回给查询节点的结果数量决定怎样重 新配置。处理过程如下： 节点提出请求后得到返回结果。节点根据每个响应节点返回结果的数量 将响应节点排序。这是根据返回结果多的响应节点会更好地满足将来的查询这一 假设。 节点找出k 个结果数量最高的响应节点，与它们建立直接连接，重新配 置网络。其中k 是系统参数，由节点来设置。 策略二( m i n h o p s ) ：如果可以从不远处的节点那里得到结果，那么就没有 必要把它作为邻居节点，因为不必经过很长的路径就可以找到它。而找到更远处 的有益节点可能会很耗时，所以可以将远处的节点作为直接邻居，这样可以在总 共步数最小的情况下获得响应结果。根据这样的假设，节点根据查询步数排序， 然后建立与那些步数多的节点的直接连接。 b e s t p e e r 解决了非结构化p 2 p 系统的某些局限性：比如它提高p 2 p 系统的可 扩充性和灵活性，提供了多内容粒度查询的支持，而且使得节点间的连接不再是 静态、随机的。 2 4 小结 本章介绍了p 2 p 及其特点，分别描述了两大类四种结构p 2 p 网络的基本工 作原理和优缺点。非结构化p 2 p 网络是本章介绍的重点，因为非结构化分散型 p 2 p 网络是本文的研究对象( 后续章节中如出现“p 2 p 网络一字样，无特别说明 均指非结构化分散型p 2 p 网络) 。在2 3 小节，特别介绍了b e s t p e e r 系统一 种有代表性的改进型非结构化p 2 p 系统，该系统的自动重新配置特性与下一章 描述的非结构化分散型p 2 p 网络搜索改进技术有相通之处。 8 硕士学位论文第三章搜索算法的优化 第三章搜索算法的优化 非结构化分散型p 2 p 网络中的搜索是在一种广播式的搜索，如g n u t e l l a 。网 络中的节点收到查询以后不仅进行本地搜索，而且将查询发送到除查询消息来源 节点以外的所有邻居节点。搜索范围由t i m et ol i v e ( t t l ) 决定。广播式的搜 索比较简单，当t t l 取值适当时，查询具有很高的查全率，能满足用户的查询 需求。但是由于采用广播的方式转发查询，容易造成查询洪流，引起网络拥塞， 降低p 2 p 网络的性能 4 2 - 4 4 1 。在研究了非结构化分散型p 2 p 网络的搜索机制之后， 本章描述了一种搜索优化算法，该优化算法通过发掘p 2 p 网络中节点间的相关 度，在查询过程中动态地将相关度高的节点聚集起来，使得查询在有限的转发次 数中获得更高的查全率。同时，节点也被赋予了一定的自治力，节点可以通过探 测周围的网络状态做出转发选择：广播查询还是选择性的转发查询。 3 1 非结构化分散型p 2 p 网络的搜索机制 非结构化分散型p 2 p 模型也称为纯p 2 p 模型( p u r ep 2 pm o d e l ) 。纯p 2 p 模 型中没有网络中全部共享资源的集中告示( 比如n a p s t e r 网络中的中央服务器) ， 每一个搜索节点的查询消息被广播到与其直接相连的节点，而这些节点又将消息 继续广播到与自己直接相连的节点，消息被不停的广播直到查询结果满足查询条 件或者t t l 达到了最大值( 如图3 1 所示) 。 图3 - 1 广播式的搜索算法 g n u t e l l a 协议【4 5 】采用的就是这种搜索机制。在c m u t e l l a 模型中，所有的节点 既是服务器也是客户端，在正常情况下节点( 在g n u t e l l a 中被称为s e r v e n t ) 执行 服务器和客户端的任务。节点提供客户端的接口使用户可以发出搜索请求和查看 检索结果，同时它们也接收来自其他节点的查询请求，检查本地共享资源中与请 求匹配的部分，返回有用的结果。g n u t e l l a 协议定义了节点通过网络通讯的方式。 9 硕士学位论文第三章搜索算法的优化 协议包括了用于节点间进行数据通讯的描述符集和管理内部节点描述符交换的 一些规则。表3 一l 是描述符的定义： 表3 - 1 描述符定义 描述符说明 用于动态发现网络上的主机。一个节点收到一个p i n g 的描述符时， 9 表示希望其回应一个或多个p o n g 描述符。 用于同应p i n g 。包括一个连接到g n u t e l l a 网络的主机的地址和该节 。 点能提供的共享数据的信息。 搜索分布式网络的首要机制。一个节点收到q u e r y 描述符后，如果在 。 本地数据集中发现匹配的数据将回应一个q u e r y h i t 。 用于回应q u e r y 。这个描述符提供含有足够信息的容器来装载匹配相 q u e r y h i t 一 关q u e r y 请求的数据。 p u s h一个用于允许防火墙中的节点向网络提供基于文件的数据的机制。 一旦节点成功连接上网络，它便通过发送和接收g n u t e l l a 协议描述符来通 信。g n u t e l l a 协议描述符在网络中按照以下规则经由节点路由： p o n g 描述符只能沿着相应p i n g 描述符的路径被发送。这保证了响应的 p o n g 描述符只对那些路由了p i n g 描述符的节点可见。如果一个节点接收到描述 符i d 为n 的p o n g 描述符，却没有路由过i d 为1 1 的p i n g 描述符，那么它必须抛 弃这个p o n g 描述符，并且不再向前传送这个描述符到任何连接节点。 q u e r y h i t 描述符只能沿着相应q u e r y 描述符的路径被发送。这保证了响 应的q u e r y h i t 描述符只对那些路由了q u e r y 描述符的节点可见。如果一个节点 接收到描述符i d 为n 的q u e r y h i t 描述符，却没有路由过i d 为n 的q u e r y 描述 符，那么它必须从网络中移除这个q u e r y h i t 描述符。 p u s h 描述符只能沿着相应q u e r y h i t 描述符的路径被发送。这保证了p u s h 描述符只对那些路由了q u e r y h i t 描述符的节点可见。如果一个节点接收到节点 标识符为1 1 的p u s h 描述符，却没有路由过节点标识符为n 的q u e r y h i t 描述符， 那么它必须从网络中移除这个p u s h 描述符。p u s h 描述符必须通过节点标识符路 由，而不是描述符i d 。 节点必须将收到的p i n g 和q u e r y 描述符发送到所有与其直接相连的节 点，但不包括发来p i n g 和q u e r y 的节点。 在向前发送p i n g 和q u e r y 描述符之前，节点必须将描述符头中的1 匝 域减l ，h o p s 域加l 。如果t t l 域减1 后变为0 ，节点不会继续发送此描述符。 1 0 硕士学位论文第三章搜索算法的优化 节点如果收到了之前收到过的描述符，它将不会发送该描述符到任何相 连节点。 以上规则定义了g n u t e l l a 网络中的搜索是一种广播式的搜索，节点除了进行 本地搜索外还将查询广播发送给所有与它直接相连节点。搜索范围由，丌l ( t t l 可以看作消息能被转发的次数) 给出，查询每转发一次，1 咀减1 ，当t t l 等 于0 时，就停止广播查询。为了防止回路的产生，每个查询消息( q u e r y 描述符) 都有唯一的编号( 描述符i d ) 。如果节点收到重复的查询消息，则说明产生了回 路，节点不再继续传播查询。这一查询过程可以用一棵查询树来表示，如图3 2 所示。发起查询的节点a 为查询树的根节点。查询被广播发送给节点所有的相连 节点( 树中节点的所有子节点) ，每次转发t t l 减l ，当”r l 等于0 或者没有其 他相连节点的节点为树中的叶子节点。 查询发起节点 点 古 端瓣搿 图3 - 2 查询树 广播式的搜索比较简单，当1 见取值适当，网络规模适中时，查询具有较 高的查全率，能满足用户的查询需求。但是随着网络中节点的不断增多，网络规 模不断扩大，这种泛洪方式的搜索方法将造成网络流量急剧增加，从而导致网络 中部分低带宽节点因网络资源过载而失效。所以在g n u t e l l a 网络中，存在比较严 重的分区、断链现象。也就是说，一个查询只能在网络中的很小一部分进行，搜 索的结果可能不完全，因此网络的可扩展性不好。本章接下来的部分将提出改进 的搜索算法和查询消息转发策略以提高查询搜索的查全率和性能。 3 2 基于相关度的自组织的搜索 描述p 2 p 网络中节点间关系的时候，经常用到一个名词：邻居。在许多文 献中“邻居 一词的含义不尽相同，因此首先给出本文对“邻居 的定义： ( 定义3 1 邻居节点：节点p 的邻居节点( 简称邻居) 是与p 逻辑上直接 相连的节点。在节点p 中存储了其所有邻居的i p 地址，节点p 不要求与其邻居 在物理网络中直接相连。 硕士学位论文第三章搜索算法的优化 在g n u t e l l a 网络中，节点的邻居在节点连入网络以后就随机决定了。除非已 有的邻居节点退出网络或有新节点加入网络，否则节点的邻居是固定的。因此 g n u t e l l a 对网络中的查询搜索次数不敏感节点的每次查询都会沿着相同的路 径被发送。事实上，在每一次查询中，查询节点对搜索结果的筛选都包含了有价 值的信息，比如：在搜索结果列表中选择节点进行资源下载，这个过程包含了用 户的一些想法：这些节点共享的资源正是我想要的，说不定它们还有更多我感兴 趣的东西；那些节点共享的资源有些名不符实，下次最好不要在搜索结果列表中 列出它们了等等。这些信息体现了p 2 p 网络用户的个人喜好。节点如果记录下 用户的喜好，作为下次搜索的参考，使得查询消息在t t l 的限制范围内被更多 用户感兴趣的节点收到，同时也避免无关的节点收到查询消息，这样便能在类似 的场景中提高查询效率，降低网络负载。 为了达到这个目标，要求p 2 p 网络中的节点可以动态地配置其邻居节点。 这种重新配置的依据是一个简单的假设：节点可以在与其相关度更高的节点中搜 索到更多有用的资源。改进算法里p 2 p 系统中的节点会把自己感兴趣且相关度 高的节点作为其邻居节点，为了不增加节点和网络的负担，每一个节点的邻居数 量是有限制的，甚至可以是固定的。图3 3 显示了一个节点的重新配置邻居的过 程。 ( a ) 动态配置前p e e re ( b ) 动态配置后 图3 - 3 节点动态配置邻居的过程 在图3 - 3 ( a ) 中，节点x 是发出查询请求的节点。x 的请求被直接发送给节点 b 和节点a 。但是，只有在节点c 和节点e 中才有x 请求的对象，则节点x 直 接从节点c 和e 获得结果。同时，x 会发现尽管节点c 和e 对它有益且兴趣相 投( 相关度很高) ，但是它们并不是邻居，于是，节点x 重新配置自己的邻居节 点，将这两个节点加入其中。新的网络结构如图3 - 3 ( b ) 所示。这种重新配置方法 的实质就是将已访问的与自己兴趣爱好相近的高相关度节点设置为邻居节点。衡 硕士学位论文 第三章搜索算法的优化 量相关度的两个因素是兴趣相关度和行为相关度。 3 2 1 兴趣相关度 为了后面的论述更加方便，首先定义一个算法中用到的数据结构兴趣域 ( i n d o m a i n ) 。 ( 定义3 2 ) 兴趣域：由向量表示，表征节点的兴趣和对各个兴趣类别的感 兴趣程度。一个兴趣域d 表示为： d = ( d l ，d 2 ，d 3 ，d n ) 其中 ( 1 ) d k ( k ( 1 ，n ) ) 是非负实数，代表一个兴趣类别( 如：计算机，天文， 医学等) ，d k 的值衡量节点对该兴趣类的感兴趣程度，d k 的取值可以有多种算法。 ( 2 ) 兴趣域向量的长度1 1 取决于兴趣类别的数量。 在基于兴趣相关度的自组织的搜索算法中，兴趣域用于记录节点的兴趣爱 好。p 2 p 网络中的每个节点都拥有一个自身的兴趣域和一个邻居节点表( 存储邻 居节点的i p 地址和邻居节点的兴趣域) 。定义中d k 的取值可以根据p 2 p 系统应 用环境的不同而定制。在最普遍的情况下，d k 的值可以为节点共享的每一类资源 的数目。例如：节点a 所在p 2 p 网络中共规划有4 个兴趣类别：计算机，天文， 医学，文学；节点a 共享了1 3 个和计算机有关的资源，6 个和文学有关的资源， 则节点a 的兴趣域就是( 1 3 ，0 ，0 ，6 ) 。这样统计的前提是：节点共享的资源 需要被划分到相应的兴趣类别中。资源分类可以是手动的或自动的，自动分类通 过“自动分类机 ( a u t o m a t i cc l a s s i f i e r ) 完成。如果资源是文档类型的，自动分 类机可以通过提取关键字的方法完成分类：去掉文档中的虚词，提取有意义的词 语，并计算每个词语出现的频率，频率最高的前m 个词语被认定为关键字，拥 有最多关键字的类别就被认为是该文档的类别。比如一个文档中的关键字是： p 2 p ，查询，树，哈希，那这篇文档就可以被划分到计算机类中。如果资源是非 文档类型的，就需要用元数据来描述资源。自动分类机可以通过分析元数据各项 属性的值来获得资源所属类别。自动分类机的分类算法包括：文本匹配 4 6 1 、贝 叶斯判定网络【4 刀以及聚类算法1 4 8 1 。这些分类的技术之前已经被广泛地研究过了， 不属于本文的讨论范围。 对于两个兴趣域分别为d i ( d n ，d i 2 ，d i 3 ，缸) 和o j ( 吗l ，啦，d j 3 ，d j o 的 节点p i 和a j 来说，它们之间的兴趣相关度( h i j ) 的计算公式为： 七 d 订d hq = 1 3 ( 3 - 1 ) 硕士学位论文 第三章搜索算法的优化 公式3 1 中d i l d i ，d j , d j ( 1 ( 1 ，k ) ) ，k 为兴趣域的长度。 h i i 的数值越大，表示节点p i 和p j 的兴趣相关程度越高，反之表示兴趣相关 程度低。在上面提到的例子中，如果网络中另外两个节点b 和c 的兴趣域分别 为( o ，1 0 ，0 ，1 8 ) 、( 5 ，0 ，0 ，1 2 ) ，则节点a 和b 的兴趣相关度h a a 为0 3 6 6 ， 节点a 和节点c 的兴趣相关度h a c 为0 3 4 9 ，计算过程如下： 【r 1 3 0 + 0 x 1 0 + 0 x 0 + 6 x 1 8 1 0 8 ，、， 。” 1 3 2 + 0 2 + 0 2 + 6 2 4 0 2 + 1 0 2 + 0 2 + 1 8 2 , , 2 0 5 4 2 4 ”- 矿下垒些竺芸丝垒坚：当：o 7 3 6 j ，= f = = = = = = = = = = = = 1 2 = = = = = = = = = = = = = ；= = = = = = u ，j o 小 1 3 2 + 0 2 + 0 2 + 6 2 5 2 + 0 2 + 0 2 + 1 2 22 0 5 1 6 9 。 由于日仙 g m i n ( g m i n 为p q 。l c f y 通过计算自己与 当前邻居节点表中每个节点的综合相关度，并比较得出的最小值) ，则节点p q 唧 从邻居节点表中删除与g m i n 对应的节点，并将节点p 加入到邻居节点表中。该 算法表示如下： 算法3 - 1 基于相关度的自组织搜索算法 目的：根据查询在p 2 p 网络中搜索资源，同时配置节点的邻居节点表。 输入：查询q u e r y ，查询关键词k e y w o r d s ，跳数兀l 输出：符合查询条件的资源q u e r y h i t 在搜索节点s 方： s o p t i m i z e d _ s e a r t h ( q u e r y ) b e g i n i f ( q u e r yi sf r e s h ) a n d ( q u e r y t t l 0 ) t h e n b e g i n q u e r y t t l - ，q u e r y h o p s + + ； b r o a d c a s t ( q u e r y