（通信与信息系统专业论文）基于对等网的内容语义搜索技术研究.pdf

摘要 基于对等网的内容语义搜索技术研究 摘要 随着互联网技术的发展以及每量数据管理需求的日益增加 对等网技术在网 络应用领域起到了越来越重要的作用 如何发布数据以及如何对分布在网络中各 个节点上的数据进行基于语义的高效搜索 逐渐成为了一个重要的研究方向 在 这种趋势下 本着对基于对等网语义搜索技术实例化研究的目的 本文设计并实 现了m a r i a n a 系统 m a r x a n a 系统基于d h t 分布式路由技术 实现了在对等网之上文档信息的发 布存储功能 并构建了p 2 p 网络上的语义搜索引擎 使用户可以透明地从p 2 p 网络中获取信息 实现基于语义的信息搜索和查找 本文详细介绍了m a r i a n a 系统的设计原理及实现过程 分析了设计实现过程 中所遇到的问题 总结了期间的经验 并结合对等网语义搜索技术的理论基础 对如何实现对等网内容语义搜索系统进行了深入地研究 文章的研究重点包括以下几个方面 一 如何在对等网上建立基于语义的信息管理系统 研究了当前主流的全分布式结构化对等网技术 着重分析了d h t 网络在精确 匹配查询和内容语义检索之间的矛盾 进而提出了基于关键词语义扩展查询技术 的搜索方案 二 如何利用文本语义抽取技术实现语义网络的构建 利用基于朴素贝叶斯模型的中文关键词抽取方法所生成的关键词 动态构建 语义节点关系图 进而生成具有语义搜索能力的关键词语义网络 三 如何利用已构建的语义网络 设计搜索算法 从而达到基于语义搜索的 目标 在方面二的基础上 基于关键词的 重要度 关键词之间的 关联度 以 及文档与关键词之间的 匹配度 提出了对对等网中信息进行语义搜索的一系 列排序算法 关键字 搜索技术 信息抽取 语义 节点关联度 关键词语义节点排序 文档 语义节点排序 p 2 p 对等网 o p e n d h t 摘要基于对等网的内容语义搜索技术研究 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e tt e c h n o l o g ya n dt h ei n c r e a s i n gd e m a n do n m a s s i v ed a t am a n a g e m e n lp e e rt op e e r p 2 p n e t w o r k sh a sb e e np l a y i n gam o r ea n d m o r ei m p o r t a n tr o l ei ni n t e m e ta p p l i c a t i o n s g r e a ta m o u n to fr e s e a r c hh a sb e e n c o n d u c t e di nh o wt op u b l i s hi n f o r m a t i o na n dh o wt oc o n d u c te f f i c i e n ts e m a n t i cs e a r c h o n f f e r e n tn o d e si nt h ed i s t r i b u t en e t w o r k s i nt h i sn n do fn e t w o r kd e v e l o p m e n t t l u st h e s i si sf o c u s e do ni n t r o d u c i n gt h em a n a n as y s t e mw h i c ha i m sa tt h er e s e a r c h a n da n a l y s i so f s e m a n t i cp u b l i s ha n ds e a r c ho np e e rt op e e rn e t w o r k s b a s e do no p e n d h td i s t r i b u t e dr o u u n gt e c h n o l o g y m a r i a n as y s t e ms u p p o r t st h e d i s t r i b u t e ds t o r a g eo ff i l e s r e a l i z e st h es e m a n t i cs e a r c ho np 2 pn e t w o r k s s ot h a tu s e r s c a ne a s i l yg e tt h en e e d e di n f o r m a t i o nb yw i t h d r a w i n gd a t af r o mt h ep 2 pn e t w o r k t i n st h e s i si n 仃o d u c e si nd e t a i l st h em a n a n as y s t e mf r o mi t sd e s i g nc o n c e p t t h e b a s i ct h e o r i e s a l g o r i t h m s a n di t sr e a l i z a t i o n i nt h ep a p e r r e a d e r sc a na l s of i n dt h e c h a l l e n g e sw e r a ni n t od u r i n ge v e r yp h a s eo f t h ep r o j e c ta n dt h ee x p e r i e n c ew eg a i n e d m o r e o v e r o u rr e s e a r c hi sf u r t h e r e di nh o wt os e a r c hi n f o r m a t i o ni np 2 pn e t w o r k s w i t ht h et e e h n o l o g yo fs e m a n t i cc o n t e n ts e a r c h a r e a so f r e s e a r c hi n t e r e s t s 1 h o wt oe s t a b h s hs e m a n t i cd a t am a n a g e m e n ts y s t e mb a s e do nt h ep 2 p n e t w o r k s t h i sc h a p t e ra n a l y z e st h em a i nd i s t r i b u t e dn e t w o r k si nu s e e s p e c i a l l yt h e c o n f i l i c t sb e t w e e na c c u r a t em a t c h i n ga n ds e m a n t i cs e a r c ho fd h tn e t w o r k sa f t e rt h e a n a l y s i s an e ws e a r c ha l g o r i t h m b a s e do nt h ee x t e n d e ds e m a n t i cm e a n i n go f k e y w o r d si sp r o p o s e d 2 h o wt oc o n s t r u c tas e m a n t i cc o n t e n tn e t w o r ks t r u c t u r et h a tu s e ss e m a n t i c c o n t e n te x t r a c t i o nt e c h n o l o g y 7 u s i n gt h eb a s i cb a y e sm o d e lt og e tt h e s e m a n t i cm e a n i n go ft h ec h i n e s e k e y w o r d s m a r i a n as y s t e mc o n s t r u c tt h es e m a n t i cn o d em a pd y n a m i c a l l ya n df i n a l l y c r e a t et h es e m a n t i cn e t w o r k st h a ts u p p o r t ss e m a n t i cc o n t e n ts e a r c h 3 h o wt od e s i g nt h es e a r c ha l g o r i t h ma c c o r d i n gt ot h ee s t a b l i s h e ds e m a n t i c n e t w o r k si n0 r d e rt or e a l i z es e m a n t i cc o n t e n ts c a r e h l i 摘要基于对等网的内容语义搜索技术研究 b a s e do nc h a p t e r2 a c c o r d i n gt ok e y w o r d sr a n k i n ga n dk e y w o r d sr e l e v a n c y a n dh o wd o c u m e n ti t s e l fm a t c ht h ek e y w o r d so ft h ef i l e s an e ws e to fs o r t i n g a l g o n t h mf o rs e m a n t i cs e a r c hi sp r o p o s e df o rp 2 pn e t w o r k s k e y w o r d s s e a r c ht e c h n o l o g y i n f o r m a t i o ne x t r a c t i o n s e m a n t i c s s e m a n t i c r e l e v a n c y k e y w o r d sr a n k i n g d o c u m e n tr a n k i n g p 2 pn e t w o r k s o p e n d h t i i l 绪论 基于对等网的内容语义搜索技术研究 第一章绪论 1 1 网络信息爆炸与对等网技术的发展 近几年来 随着网络技术的日臻成熟 网络建设成本的逐渐下降 网络的应 用已经得到了广泛的普及 如今 从遍及全球的广域网络到某一地区的城域网络 再到某个企业单位之中的局域网络 大大小小的网络已经深入到了人们生活的每 一个角落 随着用户数量的增加以及互联网普及程度的提高 互联网中的信息正 在以几何级数增长着 如何合理的存储 分析以及利用网上如此巨大的信息资源 已经越来越成为网络领域的重要研究课题 传统的网络中 c s c lz e n t s e r v e r 结构是构成网络的主体 即集中架设服 务器 s e r v e r 完成数据的存储和处理 而客户端 c l i e n t 则是简单的通过 网络从服务器端获取数据 目前我们可以看到许多这种类型的应用 如门户网站 f t p 服务以及传统的 网络搜索引擎 在这种结构下 随着用户数量的增加 服务器的负载也随之迅速 增加 甚至达到了不堪重负的地步 以著名的门户网站新浪为例 网站的日均访 问次数达到了3 亿次 平均每秒就有1 1 5 7 4 次 而g o o g l e 为了实现目前的服务 规模 在2 0 0 5 年投入了数以亿计美元的资金用于基础设备的建设 而与此形成 鲜明的对比 众多分布在网络中客户端计算机的计算能力却被大量的闲置 大多 数的客户机只被用于网页显示之类的简单功能 针对这种状况 如何分散服务器的计算工作以及充分利用网络的计算能力成 为了网络发展的一个方向 近些年来 对等网技术应运而生 迅速得到了大规模 的应用 其中一个典型的例子便是大量基于对等网的文件共享程序 如著名的 b i tt o r r e n t e m u l e 1 e d o n k e y 等 据统计 通过p 2 p 软件进行资源共享 所产生的网络流量已经占据了当前网络总体流量的5 0 以上 在对等网中 网 络的计算工作被分布到网间的每一台计算机中 因此整个网络的计算能力得到了 充分的利用 并且 随着网络用户数量的增长 网络的整体计算能力也会随之得 到加强 于是客户端数量增长和服务器计算能力有限的矛盾得到了完善的解决 基于分布式散列表 d h t 的技术是目前p 2 p 网络的主要实现方式之一 在 d h t 网络中 每一个数据资源都有一个全局i d 通过h a s h 算法 网络可以迅速 定位到资源所在的节点 而并不借助中心服务器的计算能力 本文所讨论的基于 对等网的信息发布系统 就是语义搜索建立在d h t 网络模型上的一个创新和实 现 复旦大学硕士学位论文 共8 9 页 第4 页 绪论 基于对等网的内容语义搜索技术研究 1 2 对等网上基于语义的搜索技术以及m a r i a n a 在d h t 网络中 数据分布的问题得到了良好的解决 大量的数据信息 陆续 被添加到网络中 然而从另一方面来看 如何利用这些数据资源成为了一个新的 课题 目前 尽管网络中的信源品种已经大量增加 信道的带宽也有极大的改善 但如果终端用户始终无法找到自己感兴趣的信息 网络的应用依然无法良好的发 展 以i n t e r n e t 为例 2 0 0 1 年 r o p e rs t a r c h 的调查指出 3 6 的网络用户一 个星期花了超过2 个小时时间在网上搜索 7 1 的用户在使用搜索引擎的时候遇 到过麻烦 平均搜索1 2 分钟以后发现搜索受挫 搜索受挫中4 6 都是因为链接 错误 另一项由k e e n 所做的调查显示 人们平均每天有四个问题需要从外界获 取答案 其中3 1 的人使用搜索引擎寻找答案 平均每周花费8 7 5 个小时找寻 答案 5 3 3 时间花在从旁人那里获得答案 2 9 的时间花在亲戚朋友身上 2 4 3 的是时间花在销售商那里 网上查找答案的 半数以上都不成功 他们每周将花 费1 4 5 美元以上 以获取正确的信息 绝大部分 8 6 的网络用户感到应该出 现更有效的 准确的信息搜索技术 在对等网中 这一矛盾更加突出 由于没有中心服务器的概念 对等网间的 数据缺乏全局管理 即没有一台服务器 拥有全部网间资源的列表 在d h t 网络 中 定位数据依靠的是数据的全局标识 然而对于大量的用户而言 全局标识往 往不具有真实的逻辑意义 难以记忆和管理 因此 如何更好的对对等网中的数 据进行索引成为了对等网技术发展的一道关口 而实现基于d h t 网络的良好搜索 平台则是攻克这一关口的重要手段 目前 d h t 网络中的搜索方法 往往都是采用精确匹配查找 然后定位文章 的方式 这种方式的缺点是显而易见的 首先 这种精确查找的方式 割裂了文档关键词之间密切的语义联系 单单进行精确匹配的的搜索方法是基于符号的搜索 它忽略了文档关键词之 间的语义联系 导致的结果往往是搜索的范围受到了很大的限制 而搜索结果的 质量却反而不高 对于大多数的领域而言 这种搜索技术显然是有所欠缺的 用 户如果想要得到满意的答案 往往需要对于多个关键词进行反复搜索尝试 其次 这种精确匹配的搜索方式 难以对结果进行有效排序 在对等网络环境下 搜索结果往往不是由一台机器返回 如果简单的通过精 确匹配进行查询 往往返回的结果 在排列顺序上没有任何的规律 对于比较热 门的信息 用户往往会面临下面的情况 尽管搜索引擎返回了许多与查询精确匹 配的文档 但是用户仍然难以在这些浩如烟海的文档中 找到自己想要的结果 复旦大学硕士学位论文 共8 9 页 第5 页 绪论 基于对等网的内容语义搜索技术研究 实际上 之所以会产生以上诸多问题 是说明在网络信息检索领域还缺乏一 种从语义学意义上筛选内容的科学技术手段 万维网的创始人t i mb e r n e r sl e e 早在2 0 0 1 年5 月s c i e n t i f i ca m e r i c a n 杂志上发表的题为 s e m a n t i cw e b 的 文章中 就提出把互联网改造成语义网的理想 语义网是能理解人类自然语言的智能网络 我们希望通过语义技术的应用 良好的解决对等网信息检索方面所遇到的问题 正是在这种前提下 m a r l a n a 系 统应运而生了 那么 究竟什么是m a r i a n a 呢 m a r i a n a 是 个基于o p e n d h t 技术的信息发 布以及搜索平台 在文档的发布过程中 通过对于关键词抽取技术的应用 m a r i a n a 能够自动识别文档的关键词 并且通过关键词在文档中被共享的信息 在关键词之间建立起了一个复杂的语义网络 在文档的检索过程中 m a r i a n a 通 过对于搜索目标以及与搜索目标语义相关的 键词在分布式存储的文档中进行 搜索 并进行基于语义的搜索排序 从而达到良好的文档检索效果 克服了以往 对等网信息管理技术中所遇到的主要问题 1 3 论文作者的工作以及论文结构 在整个m a r l a n a 系统的设计实现过程中 作者主持了系统整体架构的设计 并全程参与了系统的实现 其间 作者进行了大量的理论研究以及实验测试 确 定了系统的理论基础并取得了大量的实验数据 并开发了包括语义搜索系统算法 部分 语义网络构建算法部分等核心模块 目前 系统的主要核心构件己基本完 成 辅助模块的开发已全面展开 在系统的设计与开发中 作者完成的具体工作有 1 根据系统中关键词的 重要度 关键词之间的 关联度 以及关键 词和文档之间的 匹配度 设计了搜索排序算法 并根据设计进行了 大量的实验 在实验的基础上 作者对该功能模块进行了实现 获得 了良好的效果 2 设计并实现了关键词语义启发式搜索算法 根据该算法 m a r i a n a 在 搜索过程中能够实现对关键词搜索的语义拓展 并根据拓展返回综合 结果列表 3 设计并实现了多关键词并发搜索过程中 对结果集进行合并排序的算 法 通过大量的理论研究和实际工作 作者在基于对等网的内容语义搜索技术领 域取得了一定的经验以及研究成果 本文便是对于这些经验以及研究成果的总 结 复旦大学硕士学位论文 共8 9 页 第6 页 绪论 基于对等网的内容语义搜索技术研究 文章的总体结构如下 第一章 绪论 阐述了当前对等网领域的研究现状 分析了在对等网中实现语义搜索的意义 及当前存在的问题 该章内容对文章的总体目标以及研究方向进行了阐述 列举 了作者在该研究方向中所涉及的领域 第二章 对等网技术以及内容语义的背景研究 本章对全文所涉及到技术领域的背景知识进行了系统的介绍 其中包括p 2 p 技术现状的研究 o p e n d h t 系统的路由算法 语义搜索和现有搜索引擎的现状研 究 提出了目前存在的语义查询和d h t 系统的矛盾 第三章 系统规划分析 本章主要对于m a r i a n a 系统的整体设计思想进行了阐述 提出了通过语义图 的自动建立以及文档信息动态排序搜索方法的应用 解决第二章所提出矛盾 方 法 之后 本章分析了系统设计及实现的重点 并对于构成系统所必需的主要模 块及其功能特点进行了阐述 第四章 系统算法设计与研究 本章的主要内容是m a r l a n a 中所应用的算法的具体设计 作者通过具体的分 析 设计了一系列语义相关的算法 并对算法的合理性和可行性进行了全面具体 的分析 第五章 m a r i a n a 系统的架构实现 本章主要阐述了m a r i a n a 系统的真实实现过程 详细介绍了系统的总体架 构 各个模块的实现技术以及原理 第六章 总结与将来的工作 本章总结了对全文进行了总结 分析了整个系统设计和实现过程中的经验 总结了目前系统的不足 对今后的工作和未来的前景 进行了进一步的展望 参考文献 列出了文章编写过程的引用以及参考的文档 资源以及著作 附录 本部分包含了术语索引 图表索引 以及实现过程中的一些详细信息 复旦大学硕士学位论文 共8 9 页 第7 页 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 第二章对等网技术及内容语义的背景研究 2 1p 2 p 技术研究现状 2 1 1p 2 p 的介绍 p 2 p 是一种分布式网络 网络的参与者共享他们所拥有的一部分硬件资源 处理能力 存储能力 网络连接能力 打印机等 这些共享资源需要由网络 提供服务和内容 能被其它对等节点 p e e r 直接访问而无需经过中间实体 在此 网络中的参与者既是资源 服务和内容 提供者 s e r v e r 又是资源 服务和 内容 获取者 c l i e n t 悯 而在客户 服务器结构中 服务器作为信息的提供者 而客户端作为信息请 求者或用户 客户端主动向服务器发出请求 服务器接收请求并对此做出应答 之后将客户所需的信息发送到客户端 p 2 p 与c s 模式的对比如下图所示 复旦大学硕士学位论文 图1 c l i e n t s e r v e r 结构 共8 9 页 第8 页 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 图2 p 2 p 结构 p 2 p 网络由p e e r 组成 任何一台能上 一的机器都可以是一个p e e r 甚至计 算机上的每一个程序都可以成为p e e r p 2 p 网络中的p e e r 是彼此直接通信的 在p 2 p 网络中 通过p e e r 之间的交互操作就可以完成工作 共享信息 p 2 p 网 络具有了许多优越的技术特点 它们包括 分散性 d e c e n t r a l i z a t l o n 可扩 展性 s c a l a b l l i t y 健壮性 r o b u s t 高性能 价格比 隐私保护 负载均衡 等 也正是因如此 p 2 p 技术具有广阔的应用前景 i n t e r n e t 上各种p 2 p 应用软 件层出不穷 用户数量急剧增加 2 0 0 4 年3 月来自w w w s l y c k c o m 的数据显示 大量p 2 p 软件的用户使用数量分布从几十万 几百万到上千万并且急剧增加 并 给i n t e r n e t 带宽带来巨大冲击 p 2 p 技术正不断应用到军事领域 商业领域 政府信息 通讯等领域 2 1 2p 2 p 网络中的拓扑结构研究 p 2 p 系统一般要构造一个非集中式的拓扑结构 在构造过程中需要解决系统 中所包含的大量结点如何命名 组织以及确定结点的加入 离开方式 出错恢复 等问题 1 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系 结 点之间的拓扑结构一直是确定系统类型的重要依据 根据拓扑结构的关系可以将p 2 p 研究分为4 种形式 中心化拓扑 c e n t r a l i z e dt o p o l o g y 全分布式非结构化拓扑 d e c e n t r a l i z e d u n s t r u c t u r e dt o p o l o g y 全分布式结构化拓扑 d e c e n t r a l i z e ds t r u c t u r e d t o p o l o g y 也称作d h t 网络 和半分布式拓扑 p a r t i a l l yd e c e n t r a l i z e d t o p o l o g y 有的文献称作h y b r i ds t r u c t u r e 复旦大学硕士学位论文 共的页 第9 页 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 中心化拓扑网络 其中 中心化拓扑结构最大的优点是维护简单 发现效率高 由于资源的发现依赖中心化的目录系统 发现算法灵活高效并能够实现复杂 查询 最大的问题与传统客户机 服务器结构类似 容易造成单点故障 访问的 热点 现象和法律等相关问题 这是第一代p 2 p 网络采用的结构模式 经典案例就是著名的m p 3 共享软件 n a p s t e r 这种结构存在很多问题 主要表现为 1 中央服务器的瘫痪容易导致整个网络的崩馈 可靠性和安全性较低 2 随着网络规模的扩大 对中央索引服务器进行维护和更新的费用将急剧 增加 所需成本过高 3 中央服务器的存在引起共享资源在版权问题上的纠纷 并因此被攻击为 非纯粹意义上的p 2 p 网络模型 对小型网络而言 集中目录式模型在管理和控制 方面占一定优势 但鉴于其存在的种种缺陷 该模型并不适合大型网络应用 全分布非结构化拓扑网络 全分布非结构化网络在重叠网络 o v e r l a y 采用了随机图的组织方式 结 点度数服从 p o w e r l a w 咀n 规律 从而能够较快发现目的结点 面对网络的动态 变化体现了较好的容错能力 因此具有较好的可用性 同时可以支持复杂查询 如带有规则表达式的多关键词查询 模糊查询等 最典型的案例是g n u t e l l a 8 l 没有索引服务器 它采用了基于完全随机图的洪泛 f l o o d l n g 发现和随机转发 r a n d o mw a l k e r 机制 为了控制搜索消息的传 输 通过t t l t i m et ol i v e 的减值来实现 这种结构面临的两个重要问题 发现的准确性和可扩展性 目前对此类结构的研究主要集中于改进发现算法和复制策略以提高发现的 准确率和性能 完全分布式结构化拓扑网络 完全分布式结构化拓扑网络采用分布式散列表 d h t 的方式 通过分布式散列函数 将输入的关键词惟一映射到某个结点上 然后通过某 些路由算法同该结点建立连接 复旦大学硕士学位论文 共8 9 页 第l o 页 对等网技术及内容语义的背景研究 基于对等网的内容语义搜索技术研究 分布式散列表 d h t 实际上是一个由广域范围大量结点共同维护的巨大散 列表 散列表被分割成不连续的块 每个结点被分配给一个属于自己的散列块 并成为这个散列块的管理者 d h t 的结点既是动态的结点数量也是巨大的 因此非中心化和原子自组织成 为两个设计的重要目标 通过加密散列函数 一个对象的名字或关键词被映射为 1 2 8 位或1 6 0 位的散列值 d h t 类结构能够自适应结点的动态加入 退出 有着良好的可扩展性 结点 i d 分配的均匀性和自组织能力 由于重叠网络采用确定性拓扑结构 d h t 可以提 供精确的发现 只要目的结点存在于网络中d h t 总能发现它 分布式散列表起源子s d d s s c a l a b l ed l s t r l b u t ed a t as t r u c t u r e s 研究 g r l b b l e 等实现了一个高度可扩展 容错的s d d s 集群 最近的1 究集中在采用新的拓扑图构建重叠路由网络 以减少路由表容量和 路由延时 这些新的拓扑关系的基本原理是在d h t 表一维空间的基础上引入更多 的拓扑结构图来反映底层网络的结构 d h t 网络最经典的案例是t a p e s t r y c h o r d c a n o 和p a s t r y 半分布式结构 半分布式结构吸取了中心化结构和全分布式非结构化拓扑的优点 选择性能 高 处理 存储 带宽等性能 的结点作为超级点 在各个超级点上存储了系统 中其他部分结点的信息 发现算法仅在超级点之间转发 超级点再将查询请求转 发给适当的叶子结点 半分布式结构是一个层次式结构 超级点之间构成一个高 速转发层 超级点和所负责的普通结点构成若干层次 最典型的案例就是k a z a a 半分布式结构的优点是性能 可扩展性较好 较容易管理 但对超级点依赖 性大 易于受到攻击 容错性也受到影响 4 种结构的综合性能比较 表h4 种结构的性能比较 比较标准 拓扑 中心化拓扑 全分布式非结构 全分布式结构化半分布式拓扑 结构化拓扑拓扑 可扩展性差差好 由 可靠性 差 好好 由 可维护性最好最好好 由 发现算法效率最高中高 中 复杂查询支持支持不支持支持 复旦大学硕士学位论文 共8 9 页 第1 i 页 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 由此 我们可以看到全分布式结构化拓扑网络具有高效的发现算法以及良好 的扩展性 可靠性 可维护性 美中不足的是现存的全分布式结构化拓扑网络不 支持复杂查询 从而对用户的信息检索带来了极大的不便 2 2d h t 系统的研究 分布式散列表 d h t 是结构化覆盖网上最重要的应用 也是最直接的应用 对于一份标识为d a t a i d 的数据 比如用文件名标识的文件 将其o a t a l d 通过哈希函数映射到地址空间 这个地址空间即为支持这个d h t 的结构化覆盖 网的地址空间 中的某个位置h a s h l d 规定该数据必须放置在当前所有结点 n o d e l d 中离h a s h l d 最近的结点上 所 写 近 也依赖于底层结构化覆盖网对 于距离的定义 由此可见 d h t 的实现必然需要有消息通信机制保证任意结点都可以与离某 个h a s h l o 最近的结点进行通信 2 2 1p a s t r y 路由算法 p a s t r y 是微软研究院提出的 基于d h t 的可扩展的分布式对象定位和 路由协议 可用于构建大规模p 2 p 系统 信息将根据其k e y 所计算的h a s h 值被 放在拥有最接近n o d e l d 的d h t 节点的上 快速定位资源的所在 方便路由 i t 4 o p a s t r y 有如下基本特性 1 每个网络节点都有一个固定的1 2 8 位n o d e l d 当收到一条含1 2 8 位k e y 的消 息时 节点能高效地将消息发送到在当前节点中 数值上n o d e l d 最接近k e y 的节点 在p a s t r y 网络中里 发送步骤的复杂度应该是0 1 0 9 n 在每个 p a s t r y 节点中 路由表要维护节点数量的复杂度是o 1 0 9 n 在消息传递经 过的每个p a s t r y 节点时 会通知回调函数 应用程序可以对这条消息做一 些处理 2 每个p a s t r y 节点监视和它n o d e l d 值最接近的l 个节点 这个集合叫作 l e a f s e t 其中比当前节点n o d e l d 大及小的节点各占l 2 应用程序可以通 过回调知道l e a f s e t 中新节点的加入 节点的失效 节点的恢复 复旦大学硕士学位论文 共8 9 页 第1 2 页 一 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 3 p a s t r y 探寻消息传递的最小距离 比如以p i n g 的延时作为判断的依据 p a s t r y 网络是分散的 灵活的 自组织的 当出现新节点 死节点 节点失 败时它会自动配置 几个重要的参数 b 一般取1 2 3 4 内部处理1 2 8 位i d 时用的进制为 2 的b 次方 l l e a fs e t 的容量 一般取 2 的b 次方 或 2 的b 1 次方 m n e i g h b o r h o o ds e t 的容量 一般取 2 的b 次方 或 2 的b 1 次方 为表达方便 n 代表网络中存活的节点数 节点需要维护的三种数据 1 l e a fs e t 表 容量为l 用于保存在数值上最接近n o d e i d 的节点 其中s m a l l e r 和l a r g e r 各占一半 2 路由表 r o u t i n gt a b l e l o g 以 2 的b 次方 为底n 的对数行 每行 2 的b 次方 一l 条数据 第n 行 表示n o d e l d 与当前节点的前n 位相同 且第n l 位与当前节点的不相同 3 邻居表 n e i g h b o r h o o ds e t 保存节点的直接邻居 如p i n g 值最小的m 个节点 它不是用来路由消息的 而是为配置网络服务的 厂 舛z r j j 彰们 j 4 r r 图3 t 路由索引表示意图 参照图3 中的左图 每一个节点维持一个路由表 路由表里n o d e l d 换算成 2 b 缺省值1 6 b 4 进制的数 举例说明 按1 6 进制 n o d e l d 为6 5 a l f c 8 3 复旦大学硕士学位论文 共8 9 页 第1 3 页 对等网技术及内容语义的背景研究 基于对等网的内容语义搜索技术研究 一共3 2 个数字 1 2 8 b i t 的节点 它的路由表中第一行填入的是这样的节点 它们n o d e l d 的第一个数字为除6 以外的值 共1 5 个 第二行填入的节点 它们 n o d e i d 的第一个数字均为6 而第二个数字则为除5 以外的值 也是1 5 个 依 此类推 第三行的节点 n o d e i d 的第一个数字为6 第二个数字为5 第三个数 字为除a 以外的值 另外每个节点还需要维持一个邻居表 表里是和本节点之间网络延迟最小的 一些节点 节点周期性的和邻居表里的节点交换信息 依此来更新路由表里的条 目 路由原理 路由是靠l e a fs e t 和路由表 而邻居表是为维护路由表而存在 的 路由表负责路由消息到目的节点附近的某个范围 而l e a fs e t 则负责精确 地找到p 的节点 参照图3 中的右图 递归路由算法 如果6 5 a l f c 这个节点需要路由一个k e y 为d 4 6 a l c 消息到目的地 首先看第一个数字 去路由表里第一行找到数字为d 的节点 根据记录的i p 地址信息 把消息发送出去 收到消息的节点 比如说 是d 1 3 d a 3 由于n o d e l d 和消息的k e y 第一个数字相同 而第二个数字不同 那 么就去节点d 1 3 d a 3 的路由表中第二行找数字为1 的节点 也是发送出去 这样 每经过一跳 n o d e i d 都可以同目的节点最少接近4 b i t 在节点数为n 的网络中 平均来说 路由一个消息到任何一个目的节点所经过的跳数小于l o g n b 是 一个影响路由表大小的配置参数 缺省为4 p a s t r y 网络是以n o d e l d 在数值上相近作基础的 脱离了实际的网络 而以 数理上的i d 作为路由的算法的依据 p a s t r y 能在无协调的网络中完成消息的路由 而且非常高划1 5 16 理论路 由步数为l o g 以 2 的b 次方 为底n 的对数 可以看出b 决定着全网的性能 b 越大当然越高效 但也会使r o u t l n g t a b l e 变大 r o u t i n g t a b l e 变大不仅占用更 多内存 更意味着传递消息时需要探测更多节点 处理更复杂的问题 因此需要 根据网络的特性选择一个b 值 鲁 2 2 2b a r n 改进的t r y 2 22b a m b o o p a s t 算法 改进的算法 b 锄b o o 17 可以认为是基于p a s t r y 对p a s t r y 协议进行了重新设计 增强了 其性能 更具有可扩展性 它采用与p a s t r y 相同的网络几何 但是却采用不同 的节点加入和邻居节点管理算法1 1 f 19 复旦大学硕士学位论文 共8 9 页 第1 4 页 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 从性能上说 b a m b o o 能更好的承受d h t 网络节点数的剧烈变化和持续扰动 即网络波动 c h u r n 波动 c h u r n 会极大增加d h t 的维护代价 使用b a m b o o 路由算法 即使在扰动很剧烈的网络环境中进行查找时仍能返回可靠性很高的结 果 并且响应时间较短 在一个带宽受限的环境中 这种优势表现得更明显 b a m b o o 在路由策略中有个特点就是即便没有节点加入或退出也会周期性地 更新路由表以尝试优化路由表 这就是所谓的p r o x i m i t yn e i g h b o rs e l e c t i o n p n s 2 2 3o p e n d h t 系统 o p e n d h t 是b a m b o o 路由算法的一个具体实现 2 1 嘲 o p e n d h t 区分了网络结点和客户端的概念 使得o p e n d h t 网络成为一个开放 的d h t 网络 通过r p c 连接到网络的客户端可使用网络提供的统一接口对网络进 行访问 完成资源的发布 查找 获取以及路由等功能 客户端不必参与维护网 络的结点信息 不必参与资源的路由查找等工作 从而减轻了负担 提高了网络 的易用性 当然 其实现的代价是降低了网络的通用性 其结构如下图所示 幂 i l 囵 一 署 二田 m 国 国 i 八旦 一 7 4 图4 o p e n d h t 网络示意图 客户端是位于d h t 网络外部的节点 它们运行应用程序代码 利用r p c 远 程过程调用 来获得o p e n d h t 节点的服务 o p e n d h t 节点除了进行d h t 路由以及 数据存储 还作为接受客户端r p c 的网关 复旦大学硕士学位论文 共8 9 页 第1 5 页 j 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 应用程序不需要考虑d h t 网络的部署与维护 但同时也不能在o p e n d h t 服务 器节点上运行a p p l i c a t i o n s p e c i f i c 代码 这一点同大多数基于d h t 的程序不 大一样 那些程序把d h t 的功能封装成库函数以供调用 这样做的好处就是 具 有充分的灵活性和性能上的优化 但是必须自己部署d h t 网络 o p e n d h t 的特点是 功能分开 系统的运行完全由i n f r a s t r u c t u r e 节点支持 无需c l i e n t 节点 的参与 同时 应用程序也只能在c l l e n t 节点运行 折中方案 系统运行和应用程序两个功能的截然分开 使得系统的灵活性降 低 但是系统更加易于部署 2 3p 2 p 存储技术的研究 p 2 p 分布式存储系统是一个用于对等网络的数据存储系统 它可以提供高效 率的 负载平衡的文件存取功能 随着对等连接的概念和有效的资源利用逐渐深入人心 p 2 p 的应用开始走向 成熟一在一个系统下进行存储 并控制分布于世界各地的数量庞大的各种资源 下面简要介绍一下与p 2 p 存储相关的各项技术 对其研究现状作简要阐述 2 3 1 搜索和定位机制 基于非结构化拓扑的p 2 p 应用通常采用泛洪搜索机制 而基于结构化拓扑的 p 2 p 应用采用d h t 搜索机制 1 针对泛洪搜索机制可扩展性差的缺点 人们提出了许多改进方法 一是从网络拓扑方面 k a z a a 和m o r p h e u s 采用超节点的概念 对系统中的 节点区别对待 让计算能力强 存储容量大 高带宽 低延迟的超节点 充当一 个区域的服务器 从而解决非结构化拓扑的扩展性问题o 二是从t t l 方面 可以使用逐渐增加t t l 的值代替固定的t t l 值 或是使用 本地索引和t t l 相结合的方式 三是从搜索机制方面 提出了用随机漫步 r a n d o mw a l k 来代替泛洪搜索机 制 还有一种方式是根据g n u t e l l a 中节点分布呈幕律 p o w e rl a w 特性 提出将 查询请求路由到聚集度高的节点 以此来克服随机漫步的盲目性 1 采用改进的 宽度优先算法 b f s 和智能搜索机制 1 提出了有向b f s 通过某些策略选择路由 使用路由索引来选择路由 以上算法虽然采用的手段不尽相同 但是目的都是减 少泛洪带来的网络流量 最终改善非结构化网络拓扑的可扩展性 复旦大学硕士学位论文 共8 9 页 第1 6 页 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 而对于结构化拓扑的i i t 搜索机制 其定位机制通常具有确定性的搜索上 界 对于d h t 搜索机制 人们则更多地是从逻辑拓扑尽可能地反映底层物理拓扑 来改进已有的算法 这是因为 在逻辑网络中相邻节点间的一跳 可能在底层物 理网络中需要跨越多跳才能到达目的地 如果p 2 p 网络的逻辑拓扑不能真实反映 节点在底层网络中的位置关系的话 将使路由延迟增加 影响对象查找操作的性 能 2 3 2 副本技术 副本技术是一种最为常用的分布式数据管理机制 通过为系统中的文件增加 副本 保存冗余的文件数据 可以十分有效的提高文件的可用性和可靠性 避免 在地理上广泛分布的系统节点由于网络断开或机器故障等动态不可测因素引起 的数据丢失m 1 副本管理机制必须能够解决两个关键的闯题 副本数量和副本位置 针对这 两个关键问题 总的来说可以分为静态副本管理策略和动态副本管理策略两种 2 3 3 信任机制 缺乏有效信任机制的p 2 p 网络 很难得到良性的发展 p 2 p 网络的无中心性 使其信任关系很难建立在少数权威和可信的节点或基础设施之上 因而在无中心 的p 2 p 网络环境中伫6 1 在对模型的具体实施和信任管理机制的实现上 大多数信 任机制仍然采用了引入中心节点的方法 即p 2 p 系统中的节点可信度由这些具有 权威性的中心节点管理 2 3 4 激励机制 针对p 2 p 系统傲励的研究发现 在p 2 p 文件共享网络中 只有少于2 0 的节 点有效工作 指共享文件 少于7 的节点提供了网络中9 0 的共享文件 这种缺 乏有效激励的问题同样严重困扰着大规模计算资源共享系统嘲1 现有的激励机制分为 集中式激励 分布式激励和基于代码不可逆假定的强 制激励汇嘲1 口刀 复旦大学硕士学位论文 共8 9 页 第1 7 页 对等网技术及内容语义的背景研究基于对等网的内容语义搜索技术研究 2 4 现有搜索引擎的研究现状与语义网络的提出 在现实世界中 比起数据信息的位置 w h e r e 人们更多的是关心所表达的 内容 w h a t 而在i n t e r n e t 大多数共享结构的实现中 对在其上传输的信息 资源和用户需求的内容并不加以明确的区分 缺乏基于内容的信息共享方式 2 4 1 搜索引擎的研究现状 同时人们在获取这些信息资源时 在很多情况下却无法获得自己真正需要的 信息 归根到底是以下两方面的原因 数据信息网络并非 一对一 的亩单通信系统 而是m 种信息资源沟通n 个 用户的复杂通信系统 随着数据网络