（计算机应用技术专业论文）ad+hoc网络中p2p文件共享机制研究.pdf

南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文：( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 j 作者暨授权人签字： 王盔剧 2 0 1 0 年5 月2 8 日 南开大学研究生学位论文作者信息 论文题目 a dh o c 网络中p 2 p 文件共享机制研究 姓名王志刚学号2 1 2 0 0 7 0 3 3l答辩日期2 0 1 0 年5 月2 8 日 论文类别博士口学历硕士硕士专业学位口高校教师口同等学力硕士口 院系所信息技术科学学院专业计算机应用技术 联系电话1 3 7 5 2 2 5 4 4 3 5e m a i l w z g y a n t a i 16 3 c o r n 通信地址( 邮编) ：天津市南开区南开大学西区公寓3 - l 一2 0 5 备注：无是否批准为非公开论文 否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交 校图书馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 。? 一”。 。j。j。?1。1 1j。 j j + i 。一一_ 。一。+ 、j 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利川管理办法，我校的博士、硕十学位获 得者均须向南开人学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开人学有关研究生学位论文收藏和利朋的管理规定。南开人学拥有在 著作权法规定范同内的学位论文使川权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开人学博硕十学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图j 10 馆等场所提供校内师生阅读，在校吲网上提供论文目录检索、文 摘以及论文全文浏览、卜- 载等免费信息服务：( 3 ) 根据教育部有关规定，南开人学向教育部 指定单位提交公开的学位论文：( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范嗣的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他；【! i l 体发表论文的权利。 非公开学位论文，保密期限内不向外提交币i 提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图1 5 馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 l ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开人学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如冈不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权忙签署一式两份，由研究生院和幽1 5 馆留存。 ，11 作者暨授权人签字：参量塑 一 2 0 1 0 年6 月2 1r 南开大学研究生学位论文作者信息 论文题目a dh o c 网络中p 2 p 文什共享机制研究 姓名 千忠刚卜学号l 2 1 2 0 0 7 0 3 3 1i 答辩日期 l2 0 1 0 年5 月2 8 日 论文类圳博十口学历硕十一硕十专业学位口高校教师口同等学力硕十口 院| 系| 骶信息技术科学学院i专业l计算机应刚技术 联系电话13 7 5 2 2 5 4 4 3 5e m a i l w z g y a n t a i 1 6 3 g o r e 通信地址( 邮编) ：大津市南开区南开人学阿区公寓3 1 2 0 5 ( 3 0 0 0 7 i ) 鱼生! 垂l 蕉查垫壅丝! ! 坌墅堡奎至 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交 校图书馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所取 得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任 何他人创作的、己公开发表或者没有公开发表的作品的内容。对本论文所涉及的 研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文 原创性声明的法律责任由本人承担。 学位论文作者签名；2 0 1 0 年5 月2 8 日 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申请 和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本说明 为空白。 论文题目 申请密级口限制( 2 年)口秘密( 1 0 年)口机密( 2 0 年) 保密期限 2 0 年月日至2 0年月日 审批表编号批准日期 2 0 年月 日 限制2 年( 最长2 年，可少于2 年) 秘密1 0 年( 最长5 年，可少于5 年) 机密2 0 年( 最长1 0 年，可少于1 0 年) 摘要 摘要 无线自组网( a dh o en e t w o r k ) 具有无中心、自组织、无基础设施、多跳路 由、动态拓扑等特点，既可以单独组网，又可以整合到互联网，在很多的领域 具有应用价值。p 2 p 网络具有分散性、容错性好、自主性强等优点，被广泛应用 于文件共享中。在a dh o c 中进行p 2 p 文件共享具有良好的应用前景，但也面临 着拓扑高度动态变化、节点异构性、节点能力受限等诸多挑战，导致查询效率 低、网络开销大等问题。为此本文提出了自适应资源发现机制( s e l f - a d a p t i v e r e s o u r c ed i s c o v e r y ：s a r d ) 。 s a r d 充分考虑了节点的异构性，提出了代理方案，代理节点承担较多的任 务，充分发挥能力强节点在计算、存储、电量等方面的优势。在代理方案中通 过保证覆盖网络与物理分布的一致性来降低网络通信的开销，并且通过代理分 裂、连接限制、代理退化和角色动态自适应调整等负载均衡措施来保护代理节 点，防止代理节点负载过重。s a r d 还利用反馈和满意度相结合的措施，及时通 告各个节点的状态信息和实现查询过程的可控。 论文采用s e t d e s t 生成a dh o c 网络的动态拓扑，在模拟环境对s a r d 的 性能进行了评测。模拟实验结果表明，与经过适应性修改的g n u t e l l a 相比，s a r d 可以降低网络通信开销，并具有较高的命中率、成功率和满意度，而且能够在 很大程度上节省网络整体的电量损耗，有效保护电量有限的节点，维持网络中 有较多的节点在线。 关键词：无线自组网，p 2 p 网络，文件共享，代理机制，节点异构性 a b s t r a c t a b s t r a c t a dh o cn e t w o r kw i t ht h ec h a r a c t e r i s t i c so fs e l fo r g a n i z a t i o n ，d e c e n t r a l i z a t i o n ， n oi n f r a s t r u c t u r e ，m u k i p l eh o pr o u t e s ，d y n a m i c a lt o p o l o g y , c a nn o to n l yb eo r g a n i z e d i n t on e t w o r ka l o n eb u ta l s ob ei n t e g r a t e di n t oi n t e r n e t i th a sa p p l i e dv a l u e si nm a n y f i e l d s p 2 pn e t w o r k 、析t ht h ea d v a n t a g e so fd e c e n t r a l i z a t i o n , g o o df a u l t - t o l e r a n c e ， i n d e p e n d e n c ei sw i d e l ya p p l i e di nf i l es h a r i n g p 2 pf i l es h a r i n g o v e ra dh o eh a sg o o d p r o s p e c t st os a t i s f yt h er e q u i r e m e n to fp r o d u c t i o n , e n t e r t a i n m e n t h o w e v e rp 2 pf i l e s h a r i n go v e ra dh o ch a st h ep r o b l e m so fl o we f f i c i e n c y , h i 曲o v e r h e a d ，d u et ot h e h i g h l yd y n a m i c a lt o p o l o g y , h e t e r o g e n e i t yo fn o d e s ，l i m i t e dc a p a c i t yo fn o d e s t o s o l v et h e p r o b l e m s ，w ep r o p o s es a r d ( s e l f - a d a p t i v e r e s o u r c e d i s c o v e r y m e c h a n i s m ) i nt h ep a p e r a g e n ts o l u t i o ni sd e s i g n e di ns a r d t om a k eb e s tu s eo ft h en o d e sw i t ls t r o n g c a p a c i t y i nc o m p u t a t i o n ，m e m o r y , e n e r g y a g e n tn o d e st a k ec h a r g eo fm o r e r e s p o n s i b i l i t i e st h a nr e g u l a rn o d e s t h eo v e r l a yn e t w o r k i sc l o s et ot h ep h y s i c a ln o d e s d i s t r i b u t i o nt or e d u c et h en e t w o r kc o m m u n i c a t i o no v e r h e a d w ed e s i g na g e n ts p l i t ， l i n kl i m i t ，a g e n td e g r a d a t i o n ，d y n a m i c a lr o l es w i t c ht oc o n t r o la n db a l a n c el o a dt o p r o t e c ta g e n tn o d e s w ea l s od e s i g nt h em e t h o do fc o m b i n a t i o no ff e e d b a c ka n d s a t i s f a c t i o nd e g r e et om a k es u r et h a ts t a t u si n f o r m a t i o no fn o d e sc a nb ea d v e r t i s e di n t i m ea n dt h ep r o c e s so fq u e r yc a nb ec o n t r o l l e d w es i m u l a t es a r di nt h ea dh o ct o p o l o g yg e n e r a t e db ys e t d e s tt oe v a l u a t e t h ep e r f o r m a n c e t h es i m u l a t i o nr e s u l ts h o w st h a ts a r dh a sg o o dp e r f o r m a n c ew i t h l o wn e t w o r kc o m m u n i c a t i o no v e r h e a d ，h i 曲h i tr a t e ，h i 曲s u c c e s s f u lr a t ea n dh i 曲 r a t eo fs a t i s f a c t i o nc o m p a r e dt og n u t e l l a i ts h o w st h a ts a r dc a nr e d u c et h ee n e r g y c o s ta n dp r o t e c tt h en o d e sw i t hl o we n e r g yt ok e e pm o r en o d e so n l i n ei n t h en e t w o r k k e yw o r d s ：a dh o cn e t w o r k , p 2 pn e t w o r k , f i l es h a r i n g ，a g e n tm e c h a n i s m ， h e t e r o g e n e i t yo f n o d e s i i 目录 目录 第一章引言1 第一节a dh o e 网络1 第二节p 2 p 网络2 第三节论文选题3 第四节本文研究内容4 第五节论文结构4 第二章相关研究6 第一节无结构模式。6 2 1 1 盲搜索6 2 1 2 基于信息的搜索7 2 1 3 基于分类的搜索8 第二节结构化模式。9 第三节a dh o e 中p 2 p 文件共享1 0 2 3 1 研究现状1 0 2 3 2 挑战分析1 2 第四节本章小结1 4 第三章s a r d 机制设计1 6 第一节概要设计1 6 3 1 1 网络环境的假设1 6 3 1 2p 2 p 模式选择1 6 3 1 3s a r d 设计目标l7 3 1 4 代理机制引入与代理节点选择标准。1 7 3 1 5 状态反馈1 9 i i i 3 1 6 3 1 7 第二节 3 2 1 3 2 2 3 2 3 3 2 4 3 2 6 3 2 7 3 2 8 第三节 第四章模 第一节 4 1 1 4 1 2 第二节 4 2 1 4 2 2 4 2 3 第三节 4 3 1 4 3 2 4 3 3 4 3 4 4 3 5 第四节 第五章总 第一节 第二节 参考文献 致谢。 附录 附录a ： 附录b ： 个人简历、 v 第一章引言 第一章引言 第一节a dh o e 网络 a dh o c 是一种特殊的无线移动网络，它的名字源于拉丁语，含义是“f o rt h e s p e c i a lp u r p o s eo n l y ”，通常它被称作无线自组网，也被称作多跳无线网。a dh o c 是由一组带有无线通信接收发射装置的移动终端节点组成的一个多跳的、临时 性、无中心网络，可以在任何时刻、任何地点快速构建起来一个移动通信网络， 并且不需要现有网络基础设施的支持，网络中每个节点可以自由移动，图1 1 给 出了a dh o e 网络的物理结构和逻辑拓扑的示意图。a dh o c 具有如下的特点【1 1 ： ( 1 ) 独立组网：a dh o e 可以不依赖于任何预设的基础设施独立组织网络； ( 2 ) 无中心：a dh o e 采用无中心结构，节点可以随时加入和离开，任何节 点的故障不会影响整个网络的运行，具有较强的抗毁性； ( 3 ) 自组织：a dh o e 没有严格的控制睁心，所有的节点通过分层网络协议 和分布式算法协调各自的行为； ( 4 ) 多跳路由：普通节点协同完成，不需要路由器等专用设备，当两个移动 主机( 如图1 1 中的主机a 和c ) 在彼此的通信覆盖范围内时，它们可以直接通 信。但是由于移动主机的通信覆盖范围有限，如果两个相距较远的主机，如图 1 1 中的主机a 和d 要进行通信，则需要通过它们之间的移动主机c 的转发才 能实现； ( 5 ) 动态拓扑：a dh o c 的动态变化的网络拓扑结构主要体现为节点和链路 的数量和分布变化，这是由于节点的随机移动、节点的开关机、信号的干扰、 地形的变化等因素引发的网络结构变化； ( 6 ) 安全性差：移动网络通常比固定网络更容易受到物理安全攻击，易于遭 受窃听、欺骗和拒绝服务等攻击。现有的链路安全技术有些已应用于无线网络 中来减小安全攻击。不过a dh o c 网络的分布式特性相对于集中式的网络具有一 定的抗毁性。 第一章引言 物理网络结构 g 图1 1a dh o c 网络的物理结构和逻辑拓扑 逻辑网络结构 a dh o c 网络的初衷是为军事服务，但由于其灵活便捷的特点，被应用于越 来越广泛的领域，尤其在灾难营救、野外科学考察、偏远矿山作业以及临时会 议等特殊环境下显示出无与比拟的优越性，此外a dh o c 还可以作为接入网与其 它的网络进行整合式组网。 第二节p 2 p 网络 p 2 p ( p e e r - t o p e e r ) 是一种分布式网络，网络的参与者共享他们所拥有的一 部分软硬件资源，这些资源被其它对等节点( p e e r ) 直接访问，网络中的参与者 既是资源提供者，又是资源获取者。p 2 p 具有非中心化、可扩展性好、健壮性、 性价比高、隐私保护性好、负载均衡等特点，与传统的服务器客户端模式相比， p 2 p 技术具有无可比拟的优势，p 2 p 模式成为许多新型业务的首选模式 根据在p 2 p 的覆盖网络( o v e r l a yn e t w o r k ) 中节点彼此之间的连接情形， p 2 p 分为无结构p 2 p 和结构化p 2 p 无结构p 2 p 的覆盖网络中的节点之间连接任意建立，基于洪泛( f l o o d i n g ) 或者在其基础上改进的方法进行文件定位，无结构p 2 p 优势在于可以很容易组 网，容错性好，支持复杂查询，受拓扑变化影响小。它的主要缺点是可扩展性 2 第一章引言 比结构化p 2 p 要差一些，代表应用有g n u t e l l a t 引，k a z a a t m 等。 结构化p 2 p 中采用d h t ( 分布式哈希表) 将关键字唯一映射到某个节点上， 当节点需要查询某个文件时，可以将查询消息有效地路由到拥有需要的文件的 节点，代表有c h o r d 4 1 等。结构化p 2 p 的优势在于其搜索机制只需要较小的通信 开支，从而在理论上具有更好的可扩展性，但是不支持模糊匹配等复杂的文件 查询方式，而且基于d h t 的拓扑维护算法比无结构p 2 p 复杂的多。 p 2 p 根据应用不同可以分为文件共享( 例如g n u t e l l a ) 、分布式计算( 例如 s e t i h o m e 5 】) 、应用层组播、网络搜索( i n f r a s e a r c h l 6 1 ) 、即时通信( 例如 s k y p e t 7 】) ，p 2 p 应用为用户提供了更丰富的资源及更好的服务质量，已经成为互 联网的主要应用之一。德国的研究机构i p o q u e 公司的最新( 2 0 0 8 2 0 0 9 年度) 统 计数据【8 】表明，p 2 p 消耗了5 0 以上的网络带宽，晚上时段甚至高达9 5 的带宽 被p 2 p 占用，另外在v o l p 领域，s k y p e 占据了欧美国家v o i p 流量的9 5 左右。 第三节论文选题 近年来无线通信技术迅猛发展，无线传输速度有了很大的提高，电子技术 的发展使得无线设备的性能，无论是计算能力还是存储能力都得到了很大的提 升，这些为无线网络上的应用研究提供了基础。无线设备为人们的日常工作生 活带来了很多的便利，随着无线设备的发展，音频、视频以及其它文件的分享， 越来越受到关注，无线网络中文件传输，通常是通过基站转发，这无疑会占用 带宽、降低效率，甚至会带来用户的费用开销，蓝牙( b l u e t o o t h ) 9 1 技术也只能 满足一对一的文件共享。由于a dh o c 具有的高速率、易组网、成本低、性能稳 定等优势而受到了越来越多的关注，而且a dh o e 既可以独立组网，还可以以接 入网的形式整合到互联网中，非常适合于移动用户之间的文件共享。a dh o c 和 p 2 p 都没有固定设施和关于节点加入和离开的先验知识u o j ，广义地讲，a dh o e 是一种节点能力受限的移动的无线p 2 p 网络【1 1 1 。因为这些共同的特性，加上有 线网络上p 2 p 文件共享的成功，在a dh o c 中进行p 2 p 文件共享是可行的。应用 场景包括汽车之间共享交通和天气信息，移动设备之间共享音乐、视频剪辑等 文件、野外作业环境共享勘测数据掣圮j 。 a dh o c 具有无中心、节点电量有限、节点移动导致拓扑高度动态变化、节 点异构性等特点，给在其上面进行文件共享带来了挑战，此外a dh o e 与p 2 p 的 3 第一章引言 网络模型和连接方式也有很大的不同。如果直接将p 2 p 现有的技术应用于a d h o c 网络中，将会因为对a dh o c 网络环境考虑不足产生额外的开销，甚至会导 致部分能量有限的节点因为电量消耗加速而断电，影响网络整体的性能。所以， 为a dh o c 网络上的p 2 p 文件共享研究更加切合需要的机制是很有必要的。 本文将在分析以往的一些共享方法基础之上，提出一种有效的a dh o c 中的 p 2 p 文件共享机制来解决上面这些难题，减少网络开销，提升文件查询的效率。 第四节本文研究内容 本文首先介绍a dh o c 网络上进行文件共享的需求以及采用p 2 p 技术的优 点，这是本文研究a dh o c 中进行p 2 p 文件共享机制的基础；然后将介绍国内外 的研究成果，并且分析它们优缺点；接下来将探讨在a dh o c 中进行p 2 p 文件共 享面临的挑战，得出在a dh o c 进行p 2 p 文件共享，采取基于无结构p 2 p 模式的 方案更加合理，在此基础上将提出s a r d 机制( s e l f - a d a p t i v er e s o u r c ed i s c o v e r y m e c h a n i s m ) 。 s a r d 机制充分考虑a dh o e 网络中节点的异构性的特点，引入代理机制， 提高文件搜索效率，保证从长期来看网络中有更多的节点参与到文件共享中。 并且在代理选择方面进行探讨，提出代理分裂、代理退化等策略应对可能出现 的“热点 ( h o t s p o t ) 问题，对代理退出等也进行了考虑。s a r d 中覆盖网络根 据拓扑的变化能够进行自适应的调整，从而降低因为逻辑拓扑和底层物理通信 之间的严重不匹配带来的额外的网络开销。此外还将进行通信协议的设计，通 信过程简单易于实现。 本文最后将进行模拟实验，与g n u t e l l a ( 经过修改以满足a dh o e 网络的要 求) 进行比较，根据实验结果来检验和评测s a r d 的性能。 第五节论文结构 本文共分为五个部分，具体结构如下： 第一章，介绍本文的课题背景，包括a dh o e ，p 2 p 网络的基本概念，论文 选题依据，本文研究内容概要； 第二章，列举出国内外在相关领域的研究成果，并对其进行简要的分析和 4 评述。探讨 计提出一些 后文中设计 第三章 绍了s a i 出等环节， 第四章 第五章 第二章相关研究 第二章相关研究 第一节无结构模式 无结构p 2 p 文件共享机制分为三大类：盲搜索( b l i n ds e a r c h ) 、基于信息搜 索( i n f o r m e ds e a r c h ) 和基于分类搜索( c l a s s i f i e ds e a r c h ) 。 2 1 1 盲搜索 盲搜索( b l i n ds e a r c h ) 中，网络中节点上并不存储任何与文件查询有关系 的信息，除了基础的洪泛( f l o o d i n g ) 外，还有一些经过改进的机制，例如随机 漫步( r a n d o mw a l k ) 【13 1 ，迭代递增( i t e r a t i v ed e e p e n i n g ) 1 1 4 等 洪泛在g n u t e l l a 和其它一些无结构p 2 p 网络中被采用。在洪泛中，发起查 询的源节点向它所有邻居节点广播查询消息，邻居节点再向自己的除了发送查 询消息的那个节点之外的邻居节点转发查询请求消息，1 v r l 被用来控制查询的 深度，每一步转发订l 值都会减l ，减到0 则查询停止。收到查询消息的节点 查找自身的资源，如果有与查询消息相匹配的资源，则形成一个应答消息，并 按照查询消息来时的路径反向发送至源节点。 优点： ( 1 ) 结点覆盖率高。研究报告【1 5 】指出，在大约5 万个结点的p 2 p 网络中，采 用洪泛方式，t t l 初始值设为7 时，能够搜索到9 5 的结点。这是因为，在洪 泛中，随着t t l 的增加，搜索到的结点个数是按指数增加的。 ( 2 ) 查询成功率高，命中的结果数目多。从一个结点发起的查询可在几乎整 个p 2 p 网络中传播，满足查询条件的结点必须给予回应。 ( 3 ) 健壮性好。一个结点出现故障或是退出对其余结点几乎没有影响，因为 在洪泛中，每个结点要向所有邻居结点发送消息，查询消息能够通过结点之间 所有可能的路径被转发。 ( 4 ) 响应时间快。这是因为在洪泛中，结点是以并行的方式向邻居结点发送 查询消息的。 缺点：如果网络中存在环，导致节点会把查询消息转发给已经接到过该查 6 第二章相关研究 询的节点，从而产生冗余消息，带来额外的网络流量，占据网络带宽，对网络 的可扩展性也带来影响 随机漫步中，请求者发出k 个查询请求给随机挑选的k 个相邻节点。然后 每个查询信息在以后的漫步过程中直接与请求者保持联系，询问是否还要继续 下一步。如果请求者同意继续漫步，则又开始随机选择下一步漫步的节点，否 则中止搜索。 优点：相对于洪泛方式，由于冗余查询消息大幅度减少，明显降低了网络 开销，此外，实现起来也比较容易。 缺点：由于随机选择部分邻居节点作为后继节点，导致查询成功率无法得 到保证。 迭代递增，在某些文献中也被称为扩展环( e x p a n d i n gr i n g ) 【l6 1 ，它是洪泛的 改进，策略循环递增t t l 值，这个值用来控制f l o o d i n g 的搜索深度。与洪泛方 法给t t l 赋一个较大的值不同，这种方法在初始阶段，给t t l 一个很小的值， 如果在t t l 减为0 ，还没有搜索到资源，则给t t l 重新赋更高的值。 优点：可以减少搜索的半径，如果p 2 p 网络内重复资源丰富，这种方法在 不影响搜索质量的基础上将减少网络内的查询流量。 缺点：如果要查询的文件很稀缺的话，将会需要多次迭代，不仅仅会因为 反复访问某些节点浪费网络资源，而且会带来较大的网络延迟。 2 1 2 基于信息的搜索 虽然无结构p 2 p 网络对于整体资源的分布没有统一的管理和分配，但是通 过对节点搜索的目标和结果的分析，可以从局部了解网络资源的分布，获得对 网络的逐步认识，利用这种认识来指导搜索过程，可以进一步提高搜索的效率， 这种方式就是基于信息搜索。在基于信息搜索中，节点通常会存储一些信息， 诸如文件索引或分布信息、节点硬件性能、网络拓扑信息来指导查询的过程中 数据包的流向，往往表现为将查询消息优先转发给最有可能命中查询的邻居节 点或者逻辑最优路径上的节点。这种机制既可以减少查询开销，又不严重损害 命中率和响应时间，不过维护这些指导信息还是会带来一些开销的。代表机制 有a p s 0 7 】，路由索引【1 跚和局部索引【1 4 】等 a p s ( a d a p t i v ep r o b a b i l i s t i cs e a r c h ) 是一种改进的基于信息的随机漫步算法， 它在转发时不是随机选择邻居，而是根据邻居节点的查询历史结果，概率性地 7 第二章相关研究 选择下一个转发节点。a p s 方法增加或者减少某个邻居的选中概率是利用反馈 机制，对经常返回结果的邻居结点增大选中的概率，反之减小其概率。a p s 方 法在查询成功率和响应时间方面都要优于r a n d o mw a l k s 方法，但是a p s 存在一 个问题，如果某几个关键字相关的文件突发查询，之后对它们查询减少，系统 中的反馈机制需要一段时间才能调整概率分布符合当前查询规律，因此不适合 查询频率分布不均匀，波动比较大的系统【l 引。 路由索引( r o u t i n gi n d i c e s ) 策略假设可将文档分成若干种类型，每个结点 维护一张路由信息表，记录可通过邻接结点获取的各种类型文档的数量。由各 结点根据一定度量标准，结合本地路由表信息选择具有最佳转发因子的结点， 例如选择通过该邻居方向能访问到的文件总数最大的节点。借助索引可以提高 搜索效率，降低延迟，减少消息传递，但是其深度优先的搜索方法会明显增大 响应时间。 在局部索引( l o c a li n d i c e s ) 机制中，每个结点建立r 跳距离内的其它所有 结点的数据索引。当结点收到查询消息时，可以代替r 跳距离内的其它所有结 点处理查询请求。采用这种方法，查询很少一部分结点就相当于查询了许多结 点。局部索引中，一项很重要的工作就是如何建立和维护r 跳距离内其它结点 的数据索引，特别是当结点加入或离开以及更新本地数据的时候，会产生一些 额外的网络流量。 2 1 3 基于分类的搜索 在基于分类的搜索中，通常将系统中的结点聚合成类，来提高查询的性能。 分类主要是基于相同的兴趣或者主题。文献 2 0 】中揭示网络表现出和社会网络相 近的所谓“小世界( s m a l l w o r l d ) 特性。一般认为，兴趣或者主题相近的结点 存储的文件和提交的查询关键字也很相近。该类型的搜索的典型的代表有 s e t s 【2 1 】等。 s e t s ( s e a r c he i l l l a n c e db yt o p i cs e g m e n t a t i o n ) 通过结点共享的文件来挖掘 结点的兴趣。由代理结点定期采集各个结点共享的文件索引，然后通过聚类的 方法把这些索引分成若干主题区域，每个结点属于一个主题区域。对每次查询， 通过计算查询关键字和各个主题区域中心的距离来判断该查询所属的主题区 域。查询过程是先路由到该查询所属的目标区域，然后再在目标区域中进行广 播。这种方法最大的不足之处在于代理结点的负荷较重，而且共享文件有时很 8 难界定所属的主 结构化p 2 p 复杂的路由机制，在结构化p 2 p 中，采用d h t ( 分布式哈希表) 作为数据结构 来有效的实现搜索功能。其原理是将网络的全体节点作为一张共同维护的哈希 表，动态的节点以动态形式成为哈希表的一部分。结构化p 2 p 的优势在于其搜 索机制只需要较小的通信开支，就可以快速定位文件资源所在的位置，在理论 上具有更好的可扩展性，但是不支持模糊匹配等复杂的文件查询方式，而且基 于d h t 的拓扑维护算法比无结构p 2 p 复杂的多。结构化p 2 p 的典型代表有 c h o r d t 2 2 1 ，c a n 2 3 ，p a s t r y 2 4 1 ，k a d e m l i a 2 5 】等。 c h o r d 是美国麻省理工大学提出的一个适合p 2 p 环境的分布式资源发现服 务。在c h o r d 中，每个节点维护少量的路由信息，通过这些路由信息，来进行 资源的查找。每个关键字的哈希值都保存在它的后继( s u c c e s s o r ) 节点中，后继 节点是节点标识符大于等于关键字k 标识符的第一个节点，我们将其记为 s u c c e s s o r ( k ) 。如果m 是关键字和节点标识符的位数( 采用二进制表示) ，那么每 个节点只需要维护一张最多1 1 1 个表项的路由表，称之为指针表( f i n g e rt a b l e ) 。 节点n 的查找表的第i 个表项包括的是s = s u c c e s s ( n + 2 i 1 ) ，这里1 m e m l e f t ，这是因为r t t 直观地通过端到端的延迟反映了网络的性能，e n e r g y l e t t 反映了该节点在网络中可能继续工作的最大时间，m e m l e f f 反映了该节点的存 储能力，代理节点承担网络大部分的负载，作为代理节点要求它能够快速响应 被它代理的节点的请求，此外还要求选择的代理节点具有长时间工作的可能性 和较大的存储空间。 第三章s a r d 机制设计 假设选定的代理节点为a j ，然后向a 发送s a r d _ r e g i s t e r 注册消息，该消 息携带n i 共享的文件列表，a j 收到注册消息后，将n i 加入g u e s t l i s t ，并且将它 所共享的文件加入f i l e l i s t 中，以便后面接受查询。 上面的节点加入网络的过程的算法流程的伪代码，如图3 3 所示。 i f ( r e c e i v es a r d i nm e s s a g e ) t h e n r e s p o n s es a r d i n r e sm e s s a g ew h i c hp i g g y st h ea g e n t l i s t ； e n d i f i f ( n e w l y e n t e ro rn oe n t i t yi na g e n t l i s t o rn o n ei na g e n t l i s tc a n c o n n e c t ) t h e n s e n ds a r d _ i n m e s s a g e ； w a i t f o ，r e s p o n s e ； i f f i n i s hc o l l e c t i n ga g e n tt h e n p i n ga l lt h ea g e n ti nt h el i s t ； c o l l e c tt h er e s p o n s e sw i t hn o d ei n f o r m a t i o n ； e n d i f s o r tt h el i s tb yr 1 7 i na s c e n d i n go r d e r ； c o m p u t e t h ew e i g h t so f t h e f i r s t3 a g e n t si nt h es o r t e dl i s tu s i n gt h e f o r m u l a ( 3 1 ) ： s e l e c tt h ea g e n tw i t hl a r g e s tw e i g h ta sd e s t i n a t i o na g e n t ； r e g i s t e rt ot h es e l e c t e da g e n t ； e n d i f 图3 3 新节点加入流程伪代码 3 2 4 文件查询过程 在s a r d 中，文件查询并不是盲目的全网搜索并将所有符合条件的文件的 信息都提供给用户，这是从网络开销和用户满意度来考虑的。用户通常只需要 数目有限的匹配查询请求的文件就足够了，对于网络中流行度高的文件的查询 会有非常多的匹配信息，只需要较小的查询范围就可以找到足够多的匹配选项， 而对于稀缺文件则往往需要更大的查询范围才能找到足够多的匹配选项。鉴于 2 6 第三章s a r d 机制设计 此，文件请求发起者需要在发起请求时设定一个满意值s a t i s f y 一v a l u e ，后续 文件查询的过程中匹配的条目一旦达到了s a t i s f yv a l u e 就通知停止查询过 程，这样可以保证满足用户需求的前提下，尽可能缩小查询范围，减少开销。 对于非常稀缺的文件会因为查询消息进过多次转发，t t l 在每次转发时减1 ，直 到减为零而停止查询过程，防止查询消息在网络中无限制地转发下去。 我们将分别给出在查询过程中普通节点和代理节点的流程图，图3 4 给出了 s a r d 中普通节点在文件查询过程中的流程图。 y 图3 4 文件查询流程图( 普通节点) 2 7 第三章s a r d 机制设计 在图3 4 中，节点n i 首先向自己的代理节点s i 发送包含关键字k i 的查询请 求s a r dq u e r y 消息，然后等待响应消息，如果超时没有响应或者命中数没有 达到满意值，则停止本次查询。在查询过程中收到某个代理节点发来的 r e s t y p e = 0 x 0 1 的s a r d消息，则更新该代理节点的最新的状态信息，response 如果该消息表明该节点命中查询条件的结果数为零，则计算当前是否获得了达 到满意值s a t i s f yv a l u e 的结果数，达到则通知停止转发，未达到则通知继 续转发。如果命中结果数不为零，则等待r e s t y p e = 0 x 0 2 的s a r dr e s p o n s e 消 息，收到后则检查当前获得结果数是否达到了满意值s a t i s f y 虬u e ，达到则 通知停止转发，未达到则通知继续转发。 图3 5 给出了代理节点在文件查询过程中的流程图。 一、 挲) 图3 5 文件查询流程图( 代理节点) 2 8 第三章s a r d 机制设计 在图3 5 中，代理节点收到查询请求s a r dq u e r y 消息，首先检查该消息 u i d 是否在本地记录的u i d l i s t 中出现过，如果出现则抛弃该消息，以免反复转 发同一个查询请求。然后检查文件列表f i l e l i s t 和c a c h e l i s t 中符合查询条件的 条目数，将命中条目数和本节点的状态信息封装为r e s t y r p e = 0 x 0 1 的 s a r d 消息发送给查询发起者，使该节点可以及时获悉本节点状态信response 息，如果命中数大于o 则继续发送r e s t y p e = 0 x 0 2 的s a r dr e s p o n s e 消息给查 询发起者，如果收到查询发起者进一步转发的通知，则将t t l 减1 ，如果t t l 大于0 ，则将查询请求转发给自己的邻居代理节点。如此继续进行下去，直到 t t l = o 或者查询发起者通知停止转发。 引入t t l 是为了限制查询消息的生命周期，防止查询请求消息在网络中无 限制转发。代理节点在响应查询请求时，将状态信息发送给请求者，可以及时 通知网络中节点，有利于在选择新的代理节点时做决策。查询过程由查询发起 者决定是否继续，代理节点接到查询请求发起者的反馈后，可以已经