（计算机软件与理论专业论文）混合p2p网络中基于资源特性的搜索机制研究.pdf

摘要 摘要 近年来，p 2 p 网络受到广泛的关注并发展迅速，而资源搜索是p 2 p 网络的关 键技术之一，如何高效地搜索网络资源是p 2 p 网络的研究重点。本文主要从资源 特征分类、资源密度、资源热度等方面，研究了混合p 2 p 网络中基于资源特性的 搜索机制。具体研究内容如下： 本文首先研究了基于资源特征分类的搜索机制。根据p 2 p 网络资源的特征对 其抽象分类，用一个特征向量表示资源，用一个特征图表示节点。通过计算节点 间的相似度来构建兴趣覆盖网络，根据查询请求和节点的相关度来决定搜索策 略，并提出了一个基于资源分类的搜索算法f o r w 。实验结果表明，f o r w 算 法发送的消息数是随机漫步的8 0 左右，搜索延迟是随机漫步的2 8 6 。 接着，从理论上研究了资源密度对p 2 p 搜索算法的影响。在资源随机分布的 假设下分析了资源密度同搜索性能的关系，给出了随机漫步和洪泛搜索的平均搜 索时间和通信开销下界，并分析得出结论：增加资源备份或者降低节点被重复搜 索的概率能显著提升稀有资源的搜索性能，但较难提升稠密资源的搜索性能。然 后设计了一个随机漫步改进算法m r w ( m o d i f i e di d o mw a l k ) 以验证结论。 仿真实验验证了文中得出的结论，结果表明实验数据同理论分析结果符合，m r w 算法的搜索时间为普通随机漫步的8 0 左右。 最后，研究了混合p 2 p 网络中稀有资源的搜索策略。针对无结构p 2 p 网络中 稀有资源搜索成功率低、搜索代价高的问题，提出了两种基于网络覆盖的稀有资 源搜索策略：r s r 和f r s r 。r s r 在随机漫步的基础上考虑邻居节点的热度，改 进了请求转发方式。f r s r 在结合洪泛搜索的情况下，改进随机漫步转发策略。 实验结果表明，r s r 搜索稀有资源的时间比普通随机漫步减少了2 2 9 ，平均搜 索成功率提高了2 6 2 ，通信开销降低了2 2 8 ；f r s r 则比随机转发方式减少 了1 5 4 的搜索时间，提高了1 4 2 的搜索成功率。 关键词：混合p 2 p 网络，资源搜索，特征分类，资源密度，稀有资源 a b s t r a c t a b s t r a c t i i lt h er e c e my e a r s ，p 2 p ( p e e r - t o - p e e r ) n e t 、o r k sh a v er e c e i v e dr n u c ha t t e n t i o na n d d e v e l o pf a s t r e s o u r c es e a r c hi sa 1 1i m p o n a n t 印p l i c a t i o n o fp 2 p ，a i l dh o wt oi m p r o v e t h es e a r c hp e r f o m a n c eh a sb e e ns t u d i e dal o t i nt h i st h e s i s ，m e c h a n i s mo fr e s o u r c e s e a r c hi i lh v b r i dp 2 pn 加r k si ss t l l d i e d b a s e do nr e s o u r c ef e a t u r ec l a s s i f i c a t i o n ， r e s o u r c ed e n s i t y 锄l dr e s o u r c ep o p u l 撕哆t h em a i nc o n t e n ti nd e t a i l si sa sf o l l o w s ： f i r s t l y ，m es e a r c hm e c h a i l i s mb a s e do nr e s o u r c ef e a t l l r ec l a s s i f i c a t i o ni ss t u d i e d a f b e rr e s o u r c ec l a u s s i f i e d ，e a c ho b j e c tc a i lb ed e s c m e da u sav e c t o r ，a n ds oc a ne a c h r 1 0 d e t h e nt 1 1 ep r o x i m i 锣o ft w on o d e sc a nb ec o m p u t e dt of o 肌o u tt 1 1 ei n t e r e s t o v e r l a vn e t w o r k ，a l l dt h es e a r c ha l g o r i t l u i lw i ub ea d j u s t e da c c o r d i n gt ot h ep r o x i m i t y b e 眦e e nt h en o d ea n dm er e q u e s t as e a r c ha l g o r i sp r o p o s e db a s e do nr e s o u r c e c l a s s i f i c a t i o n e x p e r i m e n tr e s u l ts h o w st h a tt ：h ea l g o r i t h mr e d u c e s t h ec o m m u n i c a t i o n c o s tt o8 0 a r l ds e a r c ht i m et o2 8 6 c o m p a r e d 、) r i t l lr a i l d o m 、a l k s e c o n d l y ，m ei m p a c to fr e s o u r c ed e n s i t ) ro ns e a r c ha l g o r i t h m si np 2 p n e t v v o r k si s s t l l d i e d t h et h e s i sg i v e sm el o w e rb o m l do ns e a r c ht i m ea n dc o m m u n i c a t i o nc o s to f r a u 帕o mw a l ka r l dn o o d i i 培m e t h o dg i v e nt 1 1 a tr e s o u r c ei su n i f o m l yd i s t r i b u t e di nm e n e 铆o r k i ti sc o n c l u d e dt l l a ti n c r e a s i n gr e s o u r c ec o p i e so rr e d u c i n gn o d e s r e p e a t e d v i s i t i n gt i m e sc a i li m p r o v es e a r c hp e 晌肌a n c ef o rm r er e s o u r c e ，b u tt h e ya r en o t e 衔c i e n tf o rp o p u l a rr e s o u r c e as e a r c ha l g o r i t l u i lb a s e do nt h ea n a l y s i sa b o v ei s p r o p o s e d s i m u l a t i o nr e s u l t sa r ea l li nc o n s i s t e n c ew i t ht h ec o n c l u s i o ni nt h i st h e s i s ， a n di t sa l g o r i t h mr e d u c e st l l es e a r c ht i m et 08 0 o fc o m m o n 舢d o m w a l k t h i r d l y ，n l es e a r c hs 仃a t e g ) rf o rr a r er e s o u r c eb a s e dn e m o r kc o v e r i np 2 pn e t 、o r k s i ss t u d i e d u n s n u c t u r e dp 2 pn e 咖r k sh a v ep o o rp e r | 0 n n a n c eo nl o c a t i n g r a r e r e s o u r c e ，t w on e ws t r a t e 西e sf o rr a r er e s o u r c es e a r c hr s r a n df r s ra r ep r o p o s e di n t h i st 1 1 e s i s b a s e do nr a n d o mw a l k ，r s rm o d i f i e sr e q u e s t - f o r w a r dm 锄e rb yt 矗k i n g t h ep o p u l a r i 田o fn e i 曲b o rn o d e sn oc o n s i d e r a t i o n w h i l e ， f r s rc o m b i n e s n o o d i n gs e a r c hw i t l lm d o mw a l k s i m u l a t i o n ss h o wt h a tc o m p a u r e dw i t hm d o m w a l k ，r s rr e d u c e st l l er e s p o n s et i m eb y2 2 9 a i l dc o m m u n i c a t i o nc o s tb y2 2 8 ， a n di m b r o v e ss u c c e s sr a t eb y2 6 2 c o m p a r e d 而t hm d o mr e q u e s tp a s s i n gm e t h o d ， f r s rr e d u c e st h er e s p o n s et i m eb y15 4 a n di m p r o v e ss u c c e s sr a t eb y1 4 2 k e vw o r d s ：h v b r i dp 2 pn e 伯，o r k ，r e s o u r c es e a r c h ，f e a t u r ec l a s s i f i c a t i o n ，r e s o u r c e d e n s i 吼i 己a r ei 沁s o u r c e i i 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除己特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名： 亟盘! 量 抛譬年6 月中日 第1 章绪论 第1 章绪论 近年来，p 2 p 网络( p e e r - t o p e e rn e t 、r k ) 1 】受到广泛地关注并发展迅速，占 据了当前i n t e m e t 超过半的带宽，被认为是改变i n t e m e t 的新一代网络技术 2 1 。 p 2 p 网络使得i m e m e t 用户能够更加高效、充分地利用网络资源，加快了网络资 源的传播与更新速度。 资源搜索技术是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 1p 2 p 网络简介 p 2 p 网络( p e e r - t 0 p e e rn e t w o r k ) 1 】又称对等网络，它是计算机网络与分布式 系统相结合的产物【2 】。i n t e m e t 是最大的计算机网络，客户服务器模式 ( c l i e r 彬s e r v e rm o d e ，简称c s ) 是i n t e m e t 常用的工作模式 2 】。在此模式中，服务器 处于核心地位，等待客户端的请求连接。但是随着网络规模的增加，这种模式使 得服务器的负担越来越重，许多客户因而得不到服务。于是，人们利用分布式系 统的思想，把服务器的一些任务分给普通的p c 节点，于是就产生了p 2 p 网络 2 1 。 p 2 p 的概念在很早就被提出，2 0 世纪7 0 年代，就有人在局域网内利用p 2 p 技术实现文件共享 2 】。但p 2 p 的真正发展要归功于i n t e m e t 网络的发展，正是 i r l t e m e t 给了p 2 p 网络一个充分展现其优势的平台：1 9 9 9 年世界上第一个应用性 的p 2 p 网络n a p s t e r 3 】出现在人们面前，在半年时间内拥有了5 0 0 0 万的网络用 户，创造了一个网络神话，使得在之后几年内p 2 p 技术被广泛应用于各个领域。 p 2 p 网络更确切的说，应该被称为p 2 p 覆盖网络( p e e r _ t o p e e ro v e r l a v n e 咖r k ) 【1 】，它是在实际物理网络基础之上形成的虚拟网络。如图1 1 所示【1 ， 底层是物理网络，物理网络可以是i n t e m e t 网络、无线网络( w i r e l e s sn e t w o r k ) 等，上层是p 2 p 覆盖网络，虚线表示节点在p 2 p 网络中的邻居关系。由图可知， p 2 p 网络中相邻节点在实际物理网络中可能相距很远。 第1 章绪论 哪络，臻 p 2 p 覆盖网络 粤- o 、了一一、，二，“n 譬” 一凰一皂， 凰 ， 物理网络 图l 。lp 2 p 覆盖网络 p 2 p 网络使得网络资源被充分共享与使用，同c s 模式相比，应用中心从单 一服务器分散到每一个节点上，对i n t e m e t 网络有很好的适应性 2 】。p 2 p 网络大 致具有以下特点 1 ，2 ： ( 1 ) 节点地位平等 p 2 p 网络又称对等网络【1 】，顾名思义是指网络中的节点地位对等。传统c s 模式中，服务器和客户端的地位是不对等的，服务器处于主导地位，所有服务均 由服务器提供，客户端主动向服务器连接请求服务，许多用户由于服务器带宽的 限制得不到服务 2 】。而p 2 p 网络中不再由服务器端单独提供服务，普通节点也 可以提供服务，所有成员在功能、地位上都是平等的，每个节点想采取什么样的 行为与其他节点交换什么信息，由本身决定，谁也没有控制谁的特权【1 ，这种 平等性使得网络中的用户能够平等的享受服务，在享受服务的同时也为别人提供 服务，充分挖掘了网络节点的潜力，增进了节点间的信息交流，充分利用了网络 带宽。 ( 2 ) 资源共享与冗余 由于p 2 p 网络节点的自由性，每个节点可以为别人共享资源，这就大大增加 了网络中的资源总数，而传统c s 只能有服务器提供资源共享，相比c s 模式， p 2 p 网络的资源数以指数量级增长 4 】。每个节点都可以是一个提供资源共享的服 务器，别的节点可以请求并下载这些共享资源，每个节点都可以相互交流资源信 息，这就使得同一资源在网络中会存在多个备份，有很大的冗余度 5 】。资源的 2 。 第l 章绪论 冗余度同资源的热门程度相关，越热门的资源在网络中被请求的越多，因而备份 数会越多 2 】。资源的冗余使得一个网络用户可以向多个用户请求同一个资源， 并同时从多个用户获取数据，这样便加快了数据下载速度 4 。 ( 3 ) 动态性与可扩展性 p 2 p 网络节点的行为取决于底层网络的特性，i r l t e m e t 网络、无线网络用户都 具有较大的动态性 2 ，因而动态性也是p 2 p 网络的重要特点。p 2 p 网络中节点 的加入与离开比较频繁，以结构化形式组织p 2 p 网络节点会付出较大的代价，而 以自适应、松散耦合方式来组织p 2 p 网络则有较大优势 1 】。 网络的可扩展性( s c a l a b i l i 够) 【5 是指当网络节点增加时，每个节点能够承载 由此带来的负载，是否需要增加额外的设备来接纳新加入的节点。c s 模式的主 要缺点就是可扩展性差，当网络节点数增加时，服务器的负载便线性增加，即使 是服务器的性能再好，但都有一个极限，无法应付网络规模的不断膨胀 2 】。而 p 2 p 网络则具有较好的可扩展性，当网络节点增加时，随之带来的通信开销由其 他节点同时分担，所以每个节点增加的负载不会很大，当网络规模增加时，p 2 p 网络也不需要增加额外的设备【2 】。 ( 4 ) 容错性 网络的容错性【5 】往往同拓扑结构相关，拓扑组织越严格，容错性相对较差【1 】。 p 2 p 网络容错性可以从两个方面来分析，一是克服了单点失效【l 】，c s 模式中服 务器是整个系统的瓶颈，服务器的失效会导致整个系统的失效，因而c s 模式系 统的容错性较差，而p 2 p 网络取消或者弱化了服务器，网络便不存在关键中心节 点，避免了单点失效。二是资源完整性与可利用性 5 】。因为p 2 p 网络有冗余性 2 】， 所以当一个资源节点失效时，网络还是可以提供服务，不至于资源的完全丢失， 普通c 倍采用备份服务器数据的方式来保证数据的完整性和可利用性，而p 2 p 网络不需要额外的备份开销。 p 2 p 网络的应用主要包括 2 】：资源共享下载、流媒体应用、实时通信与网络 游戏、搜索引擎、协同工作、分布式计算、分布式存储等。 ( 1 ) 资源共享下载 信息资源共享一直是网络技术发展的重要推动力，也是p 2 p 网络最典型的应 用 4 】。p 2 p 技术使得网络带宽被充分利用，文件下载速度较c s 模式得到明显提 升。继n a p s t e r 3 】之后，出现了多种基于不同结构的文件共享p 2 p 网络，几乎每 一种都得到了广泛的应用。b t 6 】等软件都采用了p 2 p 技术实现资源共享与快速 下载。 3 。 第1 章绪论 ( 2 ) 流媒体应用 传统的c s 结构在提供多媒体服务时，受网络带宽的限制，可以承受的用户 很有限【2 】。例如服务器拥有1 0 m 带宽，每个服务需要2 5 0 k 带宽，则普通c s 模式只能同时为4 0 个用户服务，而利用了p 2 p 技术，可以同时为上万个用户提 供服务 7 】。现有的多媒体软件如p p l i v e 7 】、p p s t r e 锄 8 】、s o p c a s t 9 等等都利用 p 2 p 技术提高了服务性能。 ( 3 ) 实时通信与网络游戏 实时通信也是p 2 p 网络的重要应用 2 】，例如q q 1 0 】、m s n 1 1 】等即时通信 工具，虽然目前的应用都有中央服务器，但是服务器只是用于用户认证，一旦认 证通过，以后的信息交流则通过节点间的互连直接通信【1 0 ，1 1 】。许多网络游戏 也利用p 2 p 技术来提高服务器的承载人数，每个游戏用户成为一个对等节点， 节点间可以传输大量的信息 2 】。 ( 4 ) 搜索引擎 目前的网络搜索引擎，例如g o o g l e 【1 2 】、b a i d u 【1 3 】，主要是基于服务器的目 录式搜索 1 2 ，1 3 ，使用了大量服务器存储索引，用户搜索时实际上在这些服务 器搜索索引。这种目录式搜索的方式只能搜索到2 0 3 0 的网络资源，而基于 p 2 p 的搜索引擎可以远远超过这个搜索深度，理论上可以搜索到所有的网络共享 资源 2 】。美国搜索引擎设计公司i 5d i g i t a l 在2 0 0 2 年已正式推出基于p 2 p 开发 的搜索引擎p a l l d a n g o 1 4 】。 ( 5 ) 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完 成计算任务、共享信息资源等 1 5 】，p 2 p 技术使得用户间协作工作更加方便、高 效【2 】。c o v e 1 6 是基于i n t e m e t 的p 2 p 协同应用软件的典型代表。 ( 6 ) 分布式计算 分布式计算将大型计算分解成小的计算任务，每个计算机负责一小部分计算 任务，然后再将所有计算结果归纳整合，利用p 2 p 网络中用户的空闲c p u 可以 完成连超级计算机都不可能完成的任务 1 5 】。例如由b e r k e l e y 大学负责的研究项 目s e t i h o m e 1 7 】，利用了1 0 0 万台计算机的空闲计算资源，来研究外星系文 明。 ( 7 ) 分布式存储 随着网络的发展，人们开始利用基于i n t e m e t 的p 2 p 网络来实现文件分布式 存储，其中典型的系统包括：o c e a j l s t o r e 1 8 】、f a u r s i t e 1 9 】等，这些系统目标是提 4 第1 章绪论 供全球性的文件存储服务。 1 2p 2 p 网络分类与混合p 2 p 网络 p 2 p 网络有多种分类方法，从拓扑和资源组织的角度出发，根据拓扑和资源 是否被结构化组织，把p 2 p 网络分为有结构p 2 p 网络( s t m c t u u e dp 2 pn e t 、v o r k s ) 和无结构p 2 p 网络( u 1 1 s t m c t u r e dp 2 pn e t 、v o r k s ) 两类 1 】： ( 1 ) 有结构p 2 p 网络 有结构p 2 p 网络中节点和网络资源以一定的方式被组织起来，资源不是随机 存放在网络节点上，从而提高了资源搜索的效率 1 】。有结构p 2 p 网络一般采用 分布式哈希表( d i s t l l l b u t e dh a s ht a b l e ，简称d h t ) 来组织节点和资源 2 0 2 4 】，每 个资源在标识空间内获得唯一的资源标识k e y ，每个节点有唯一的节点i d 。资源 发布时根据哈希规则，资源标识k e y 被映射到节点i d 空间内的一个节点，因而 每个资源被放到一个确定的节点上。在查找资源时，通过资源标识k e y 进行查找。 图1 2 1 】表示了基于d h t 的有结构p 2 p 网络中资源的组织、发布以及查找。 图1 2 基于d h t 的结构化p 2 p 网络的应用接口 有结构p 2 p 网络中每个节点包含一个路由表，查找资源时根据路由表信息搜 索节点。不同的有结构p 2 p 网络具有不同的d h t ，因而对资源和节点组织也不 同，基于d h t 的p 2 p 网络 2 0 2 4 可以保证在o ( 1 0 9 n ) 时间内搜索到资源，n 为 网络节点数。在有结构网络中，两个节点间的连接路径跟实际物理链路相差较大。 有结构p 2 p 网络一般包括：c a n ( c o n t e n ta d d r e s s a b l en e t 、v o r k ) 【2 2 】， t a p e r s t 巧 2 4 】，c h o r d 2 3 】，p a s 时【21 】，l 1 0 时的平均搜索时间。实验 结果显示，当m 1 0 时，普通随机漫步在普通拓扑网络中的平均搜索时间比理 3 8 第3 章基于资源密度的搜索机制研究 论下限值高较多，m r w 算法的时间小于普通随机漫步，是普通随机漫步的8 0 左右，但仍大于理论下限值，这说明还可以改进m r w 算法提高搜索效率。 7 0 8 0 5 0 e = 4 0 藿 仍 拐3 d 2 0 1 0 1 02 0 3 0 4 0 5 0 6 0 r e s o u r 。ec o d - e s 图3 。5m 1 0 时，随机漫步平均搜索时间 从图3 5 可以看出当m l o 时，三种情况下的搜索时间相差无几，这说明在 资源密度较大时，随机漫步可以改进的空间不大，表明通过改进转发方式或者降 低节点被重复搜索的概率，都较难提高普通随机漫步的搜索性能。 3 4 2 洪泛搜索 理论分析已知平均网络中，洪泛搜索在节点可能被重复访问和不被重复访问 时，平均搜索时间理论下限相差不多，但通信开销在m 较小时相差较多，在m 较大时差不多。分析表明在搜索稀有资源时，降低重复搜索概率可以减少洪泛搜 索的通信开销，在搜索稠密资源时，较难通过降低重复搜索节点的概率来减少通 信开销。由于理论下限是最优情况，而实际搜索时的性能相差较大，搜索通信开 销会比理论下界大很多。 ( 1 ) 洪泛平均搜索时间 图3 6 比较了普通拓扑网络中和平均网络中的洪泛平均搜索时间。结果显示 在资源密度较小时，普通拓扑网络中的搜索时间低于在平均网络中的搜索时间， 甚至低于洪泛的理论下限。但随着资源数的增大，洪泛搜索在普通拓扑网络中的 搜索时间大于在平均网络中的搜索时间。 3 9 第3 章基于资源密度的搜索机制研究 01 02 0 3 0 4 0 5 06 0 r e s o u r c o p i e s 图3 6 普通拓扑网络和平均网络中的洪泛平均搜索时间 结果表明，在资源密度较小时，网络中节点度的差异可以降低洪泛的搜索时 间，但在资源密度较大时，在平均网络中搜索时间最短。 ( 2 ) 洪泛通信开销 图3 7 比较了洪泛搜索在普通拓扑网络中和平均网络中的通信开销。结果显 示在资源数较少时，洪泛的消息量随着资源数增多而急剧下降，然后变化趋向于 平缓。这说明洪泛方式在搜索资源密度较小的资源时通信代价较大，搜索密度较 大的资源时通信代价相对较小。结果显示洪泛搜索在普通拓扑网络中的通信开销 大于在平均网络中的通信开销。 曹1 c ) 墨1 吾 雪 e e 8 r e s o u r c o p i e s 图3 7 洪泛搜索通信开销 4 0 8 6 4 2 0 8 6 4 2 o 8 6 4 2 o 3 3 3 3 3 2 2 2 2 2 1 t t t l oil3j 第3 章基丁资源密度的搜索机制研究 苗 8 舌 吾 。 e 8 芑 暑 匝 图3 8 洪泛搜索在普通拓扑网络中和平均网络的通信开销比 图3 8 为洪泛搜索在普通拓扑网络中和平均网络的通信开销比。由图可知洪 泛搜索在普通拓扑网络中的消息数为平均网络中的2 5 3 倍，在资源数小于3 时 比较特殊，消息数比值小于2 5 。在平均网络中，理想的洪泛搜索消息数约为普 通洪泛的4 0 。 一般以带宽消耗来评价洪泛搜索的性能。假设以单位搜索时间内产生的消息 量来评价洪泛搜索的性能。 8 写 量 宅 芒 董 嚣 d r e s o u r c o p i e s 图3 9 洪泛搜索性能 、图3 9 为洪泛搜索在不同资源密度下的搜索性能。结果显示在资源密度较小 时，洪泛搜索性能较差，在资源密度较大时，洪泛搜索性能较好。这说明洪泛搜 索比较适合查找资源密度较大的资源，不适合查找稀有资源。 4 1 第3 章基于资源密度的搜索机制研究 3 5 小结 本章在资源随机分布的假设下首先分析了节点访问概率同资源搜索时间的 关系，然后分析了资源密度同平均搜索时间、通信开销的关系，给出了随机漫步 和洪泛搜索的平均搜索时间下界、通信开销下界，得出两个结论： 结论3 1 假设资源随机分布，在不同拓扑的p 2 p 网络中，普通单路随机漫步 的平均搜索时间下限为l g ，消息数下限为l g 。 结论3 2 假设资源随机分布，单路随机漫步的平均搜索时间和搜索消息数下 限均为旦旦。 留，l + l 基于上述分析提出了基于资源密度的搜索算法的设计思路，得出结论3 ，3 ： 增加资源备份或者降低节点被重复搜索的概率能显著提升稀有资源的搜索性能， 但很难提升稠密资源的搜索性能。 在上述理论的基础上设计了一个随机漫步改进算法m r w 。最后实验验证了 本文中分析得出的结论，实验结果同理论符合，m r w 算法的搜索时间为普通随 机漫步的8 0 左右。 4 2 第4 章混合p 2 p 网络中稀有资源搜索策略研究 第4 章混合p 2 p 网络中稀有资源搜索策略研究 p 2 p 网络中存在许多只有较少备份且无索引的资源，这部分资源通常被称为 稀有资源。由上一章的分析结论可知，同一算法在搜索稀有资源和稠密资源时有 不同的搜索性能，因而在搜索稀有资源和稠密资源时应采用不同的搜索策略。 网络覆盖时间是指遍历网络中所有节点的平均时间。本章针对无结构p 2 p 网 络中稀有资源搜索成功率低、搜索代价高的问题，从网络覆盖的角度改进随机漫 步搜索方式，在不降低热门资源搜索效率的前提下，提高稀有资源的搜索效率。 本章通过理论分析表明：降低网络覆盖时间可以提高稀有资源的搜索性能；网络 中节点被访问概率差异越小，网络覆盖时间越短。基于上述理论分析，提出两种 稀有资源搜索策略：r s r ( r a n d o ms e a r c hf o rr a r er e s o u r c e ) 和f r s r ( f l o o d i n g a i l dr a n d o ms e a r c hf o ri h r er e s o u r c e ) ，通过降低网络覆盖时间，提高稀有资源的 搜索性能。r s r 在随机漫步的基础上考虑邻居节点的热度，改进请求转发方式。 f r s r 在结合洪泛搜索的情况下，改进随机漫步转发策略。实验结果表明，r s r 搜索稀有资源的时间比普通随机漫步减少2 2 9 ，平均搜索成功率提高2 6 2 ， 通信开销降低2 2 8 ；f r s r 则比随机转发方式减少1 5 4 的搜索时间，提高 1 4 2 的搜索成功率。 本章首先介绍现有搜索算法用于提高稀有资源搜索性能的策略，接着分析稀 有资源搜索同网络覆盖的关系，然后设计基于网络覆盖的稀有资源搜索策略，最 后实验仿真。 4 1 概述 在无结构p 2 p 网络中，稀有资源搜索成功率低、搜索代价高 1 】，从而降低了 稀有资源在网络中的可用性 4 】，因此提高它们的搜索效率具有重要意义。 洪泛搜索( f l o o d i n g ) 2 9 】和随机漫步( r a n d o mw a l k ) 【5 2 】搜索是无结构p 2 p 网 络最常用的两种搜索方式 1 】，一般采用建立索引或者增加备份的方式来提高稀 有资源的搜索效率。例如文章【6 2 】在发布资源时，先发送一个查询包，以查询成 功的距离来估算发布资源索引的概率。查询成功的距离可以表征资源在网络中的 密度，如果所发布的资源是一个稀有资源，那么被建立索引的概率会较高，而稠 密资源不容易被建立索引。这种方式大大提高了稀有资源的搜索性能，也能避免 稠密资源的索引泛滥。但是在p 2 p 资源网络中稀有资源较多时，采用增加备份或 者建立索引的方式会使索引和备份数量会比较大，节点的频繁加入与离开也会导 4 3 第4 章混合p 2 p 网络中稀有资源搜索策略研究 致大量索引的失效与更新。 冯国富等【5 8 】研究表明，优化无结构的拓扑网络可以提高资源的搜索效率， 因而可以通过拓扑结构的优化可以提高稀有资源的搜索效率。在无索引的无结构 p 2 p 网络中，m z h o n g 等 7 2 】从网络拓扑的角度，根据节点包含内容被访问的热 度，构造概率转移矩阵，提高了随机漫步算法的搜索效率，但它本质上只提高了 热门资源的搜索效率，对稀有资源的搜索效率还是没有提升。 利用资源的分类特征也可以提高稀有资源的搜索效率，假如已知所搜索资源 的分类特征，由第二章分析可知，通过构建兴趣网络，在相同兴趣的节点内搜索 到所需资源的概率较大 4 0 】，因而通过特征兴趣的引导可以提高搜索效率。文献 【4 0 4 2 】研究表明，利用兴趣的局部性原理可以提高搜索算法的性能。构建兴趣网 络需要一定的代价，其搜索性能依赖于资源特征分类。如果单纯利用构建兴趣网 络的方式来提高稀有资源的搜索效率，代价较大。 本章从网络覆盖的角度出发，改进随机漫步搜索方式，以提高稀有资源的搜 索效率，在混合p 2 p 网络中设计稀有资源搜索策略。 4 2 稀有资源搜索与网络覆盖 网络覆盖时间是指遍历网络中所有节点的平均时间【7 3 】。本小节首先分析稀 有资源搜索效率跟网络覆盖时间的关系，分析结果表明降低网络覆盖时间可以提 高稀有资源的搜索效率，接着研究节点访问概率同网络覆盖时间的关系。 4 2 1 网络覆盖时间与稀有资源搜索效率 假定在无结构p 2 p 网络中，资源随机分布，同时不考虑每个节点上的资源数 差异，那么每个节点拥有所需稀有资源的概率相同。假定稀有资源在网络中只被 一个节点拥有，那么每个节点拥有指定稀有资源的概率为l 疗，则稀有资源搜索 成功的概率正比于被搜索的节点数，搜索时间正比于网络覆盖时间。即网络覆盖 时间越短，稀有资源搜索效率越高。 热门节点是指被访问频率较高的节点，不热门节点是指被访问频率较低的 节点。若假设每个节点拥有相等的资源数r ，由于热门节点主要包含热门资源， 则稀有资源存在于不热门节点的概率更大。设热门节点数为玛，假设其余节点均 为不热门节点，则不热门节点数为坞，显然 ，设热门节点上稀有资源的比 例为口，不热门节点中稀有资源的比例为6 ，显然口 6 ，则指定稀有资源在热门 节点上的概率为 g l = 碍阳，( 碍阳+ 吃，6 ) = 碍口( 强口+ 雅2 6 ) ( 4 。1 ) 4 4 第4 章混合p 2 p 网络中稀有资源搜索策略研究 指定稀有资源在不热门节点上的概率为 9 2 = 伤而( 确m + 他而) = 嘭6 ( ，z l 口+ 吃6 ) ( 4 ，2 ) 由于强 吃，口 6 ，显然g l 留2 。因此，当节点上资源数相等时，相对于遍 历热门节点，遍历不热门节点更能提高稀有资源的搜索效率。 综上可知，缩短网络覆盖时间，能提高稀有资源的搜索效率。如果各个节点 资源数相同，那么不热门节点被遍历的范围越广，就越能提高稀有资源的搜索效 率。 4 2 2 网络覆盖时间 网络覆盖时间跟网络拓扑相关，由定理3 1 可知，在确定搜索算法后，网络 覆盖时间跟节点被访问概率相关。c h e n a v i n 等 7 3 】研究表明改进传统随机漫步 算法选择下跳路由的策略，可以降低随机漫步算法的网络覆盖时间，但没有考 虑节点被访问概率的差异。一般在纯随机搜索访问的情况下，度越大的节点被访 问的概率越大 5 8 】。 定理3 1 表明，随机搜索算法在等概率网络中的资源平均搜索时间最短。也 就是说节点被等概率访问时，随机搜索算法的搜索效率最高。 下面在定理3 1 基础上，分析在无结构p 2 p 网络中节点被访问概率差异与网 络覆盖时间的关系。同定理3 1 分析方法相同，按照节点被访问概率，把网络分 成z 部分，每一部分内的节点被访问的概率相同。网络参数假设如下： 表4 1 网络参数假设 符号内容 刀 网络节点数 强第f 部分网络中的二常点数 吼访问的节点属于第f 部分网络的概率 0 在经过后步后，第，部分网络已被访问过的节点数 f 噎七步后网络中已被访问过的节点数 表4 1 中，= 刀，吼= 1 a l = l= t 定理4 1 ：等概率网络的网络覆盖时间最短；网络中节点被访问概率差异越小， 网络覆盖时间越短。 证明：由定理3 1 可知，经过七步随机查询后，整个网络的覆盖范围为 f，f = r = 刀m 一群) = 刀一一群 4 5 第4 章混合p 2 p 网络中稀有资源搜索策略研究 当满足届= 厦= = 屏= l 一1 刀，厂取到最大值厂= 刀一，2 ( 1 一l ) 。 在等概率网络中，相同查询步数能获得最大的网络覆盖度，从另角度可知， 等概率网络的网络覆盖时间最短。 下面证明节点被访问概率差异越小，网络覆盖时间越短。首先对，为2 时的 情况进行分析，此时 = 刀一( 惕群+ 伤膨) 鼽约束条慨 啊屈：盖= 一。 令口= 屈屈，表示不同节点被访问概率的差异，则 2 = 刀一( 口。+ 刀一，z 1 ) ( 刀一1 ) ( 口伟+ 门一伟) r 求导可知，当o 2 时，采用归纳法证明。假设，= f 时，猜测成立，则当，= f + 1 ，把r 个 部分网络看成一个部分网络，结合，= 2 时的情况，便知此时结论也成立。综上， 得出结论：网络中节点被访问概率差异越小，网络覆盖时间越短。证毕 图4 1 网络覆盖度同节点访问概率差异的关系图 图4 1 在假定只有两种节点访问概率的情况下，给出了经过2 0 0 0 0 步搜索后 的网络覆盖度，比较了网络覆盖度同节点访问概率差异的关系。其中p 2 p 网络包 含2 0 0 0 0 个节点。 从图中可以看出，当两种节点访问概率相等时，可以达到约7 0 的网络覆盖 度，而如果节点访问概率之比为l o 时，只能达到4 0 左右的网络覆盖度。随着 4 6 第4 章混合p 2 p 网络中稀有资源搜索策略研究 节点访问概率之比的增大，网络覆盖范围越来越小。同时也可以从图中看到，当 节点访问概率之比相对较小时，网络覆盖度变化幅度比较大，当节点访问概率之 比相对较大时，变化幅度趋向于平缓。 在节点访问概率之比等于1 0 时，计算得到需要经过5 5 0 0 0 步左右，才能达 到7 0 的网络覆盖度，是等概率访问时所需访问步数的2 8 倍左右。所以，降低 节点访问概率差异，可以大大减少网络覆盖时间。 由上述分析和定理4 1 可知，在设计稀有资源搜索策略时，应该尽量缩小节 点被访问概率的差异，使网络能够趋向于等概率网络，从而降低网络覆盖时间。 4 3 基于网络覆盖的稀有资源搜索策略 由前一节分析已知，在设计算法时，缩小节点被访问概率的差异可以减少稀 有资源的搜索时间。 本节在设计稀有资源搜索策略时，考虑了邻居的节点热度信息。在随机漫步 搜索算法的基础上，改进请求转发方式，尽量缩小节点被访问概率的差异，使网 络能够趋向于等概率网络，从而提高稀有资源的搜索性能。 首先在混合p 2 p 网络中设计了一个资源搜索算法，i m ( i n d e x e sm a n a g e r ) 索引 热门资源，当请求的资源不在i m 上时，采用稀有资源搜索策略。然后设计了两 个基于网络覆盖的稀有资源搜索策略。 4 3 1 搜索模型定义与假设 在拥有海量资源的无结构p 2 p 网络中，网络的动态性较大，资源更新频率 较快 1 。在此基础上，引入索引管理节点i m ( i n d e x e sm a l l a g e r ) ，如图4 2 所示， 每个i m 节点负责管理一部分普通节点。i m 节点由普通节点选举产生，它的硬 件配置跟普通节点相仿，它负责存储被搜索频率较高的资源索引。由于i m 节点 能力有限，查询时它只负责搜索本地和其它i m 的资源索引，不搜索其他普通节 点。 i m 节点负责管理两个表：节点表( n o d el i s t ) 和索引表( i n d e x e sl i s t ) 。 节点表存储它所管辖区域内的节点地址信息，每个i m 的节点表大小可以不相同， 根据节点本身能力而定。每个普通节点可以向i m 节点申请加入它所管辖的区域， 并可以被多个i m 节点记录，节点离开时向i m 节点发送离开信息。 4 7 第4 章混合p 2 p 网络中稀有资源搜索策略研究 图4 2 混合p 2 p 网络搜索模型 索引表记录索引资源的信息，包括资源名，热度值，和资源拥有节点的信息。 索引表根据资源热度值排序，索引表大小取决于节点能力。一般情况下，假设i m 节点的索引表大小近似等于本区域内所有热门资源的索引。 每个i m 节点同时还记录一部分其他i m 节点的信息作为自己的邻居，并定 时交流更新相互间的索引热度信息。 i m 节点接受普通节点的资源热度更新消息。定义资源i 的热度值尺( f ) 更新规 则如下：足( f ) = 尺( z ) ，+ 1 ，其中，= 地一，。) ，r 是一个小于等于1 的递减因子， 当， 1 ，r 取1 ，t 为当前时刻，为上次更新时刻。 设节点i 拥有资源数( f ) ，度为d ( f ) ，节点热度为尸( f ) ，邻居集合为墨，何， 为i 不再转发消息的邻居集合。每个普通节点的热度p ( f ) 由节点本身记录，p ( f ) 同节点被访问频率成正比，定义尸( f ) 为： 尸( f ) ：口p ( f ) + 垒兰竺( 4 3 ) f 。 口是节点热度的递减因子，所砌船表示单位时间出内节点被访问的次数， 是跟节点本身其他特性相关的因子，例如节点拥有的资源数，资源查询分布等。 由于p 2 p 网络动态性较强，因而实际上每个节点的邻居和度都在变化。在一 次查询成功后，源查询节点将目标查询节点加为邻居。所以，被查询频率较