（计算机科学与技术专业论文）非结构化对等网络资源定位技术研究.pdf

f r e s e a r c ho nu n s t r u c t u r e d p e e r t o p e e r n e t w o r k r e s o u r c el o c a t i o n c a n d i d a t e ：z h ug u i m i n g s u p e r v i s o r ：p r o f j i ns h i y a o ad i s s e r t a t i o n s u b m i t t e di np a r t i a lf u l f i l l m e n to f t h er e q u i r e m e n t s f o rt h ed e g r e eo fd o c t o r o fe n g in e e r in g i nc o m p u t e rs c i e n c ea n dt e c h n o l o g y g r a d u a t es c h o o lo f n a t i o n a lu n i v e r s i t yo f d e f e n s et e c h n o l o g y c h a n g s h a ，h u n a n ，p r c h i n a m a y ，2 0 1 0 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的 研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：生整翊e l 期： 如c 睥5 月午日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档，允许论文被查阅和借阆；可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 鼻朽硝 作者指导教师签名：堡二垄 日期：矽f 碑罗月珥日 e 1 期：2 - - , d 年厂月工学e t 国防科学技术大学研究生院博士学位论文 目录 摘要i a b s t r a c t i i i 第一章绪论1 1 1 研究背景l 1 1 1基本概念1 1 1 2p 2 p 计算的历史3 1 1 3 p 2 p 系统的分类4 1 1 4 主要应用领域7 1 1 5 非结构化p 2 p 网络资源定位面临的挑战一9 1 2 相关工作1o 1 2 1 盲路由10 1 2 2 提示性路由1 1 1 2 3 拓扑优化15 1 2 4 复制与缓存1 6 1 3 本文工作17 1 4 论文结构2 1 第二章非结构化p 2 p 网络的增量式查询一2 3 2 1 基于熟人关系的增量式p 2 p 搜索算法i p s b s a r 2 3 2 1 1i p s b s a r 算法2 4 2 1 2i p s b s a r 算法分析2 8 2 1 3 模拟实验3 0 2 2 非结构化p 2 p 网络增量式查询一般算法模型3 5 2 2 1 增量式查询一般算法模型3 5 2 2 2 模型分析3 7 2 2 3 模拟实验。3 8 2 3 本章小结。4 0 第三章基于b l o o mf i l t e r 的概率路由算法研究4 1 3 1 研究背景4 1 3 2o b f ：一种面向p 2 p 网络概率路由的b l o o mf i l t e r 。4 3 ：；2 1b l o o mf i l t e r 4 3 第1 页 国防科学技术大学研究生院博士学位论文 3 2 2o b f ( o p e r a t i v eb l o o mf i l t e r ) 一4 4 3 2 3 分析与比较4 6 3 3d w a l k e r - 一种基于衰减b l o o mf i l t e r 的p 2 p 网络概率路由算法5 3 ：；：；1d w a l k e r 5 3 3 3 2 理论分析5 7 3 3 3 模拟实验一5 8 3 4 本章小结6 2 第四章基于副本复制和b l o o mf i l t e r 的网络覆盖研究6 3 4 1d c b f 算法。6 3 4 1 1 基于有向随机网络的路由条目更新6 3 4 1 2 基于b l o o mf i l t e r 的副本放置策略6 4 4 2d c b f 算法分析6 5 4 3 模拟实验6 7 4 4 本章小结一7 3 第五章基于语义聚类拓扑的查询路由算法研究一7 5 5 1s c q r - 基于语义聚类拓扑的超节点模式的p 2 p 查询路由算法7 5 5 1 1s c q r 算法7 6 5 1 2 算法分析7 7 5 1 3 模拟实验8 0 5 2s o s c - 基于自组织语义聚类拓扑的完全分布式p 2 p 查询路由算法8 2 5 2 1s o s c 算法8 2 5 2 2 算法分析8 6 5 2 3 模拟实验8 9 5 2 4 讨论9 2 5 3 本章小结9 3 第六章结论与展望一9 5 致谢9 7 参考文献9 9 攻读博士学位期间发表的主要学术论文、1 0 7 攻读博士学位期间参与的科研项目一10 8 第1 l 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 实验参数3 1 表2 2 实验参数3 8 表3 1 参数值设置5 1 表3 2 实验参数5 8 表5 1 算法模拟参数。8 0 表5 2 算法模拟参数。8 9 第页 国防科学技术大学研究生院博+ 学位论文 图目录 图1 1p 2 p 网络拓扑示例2 图1 2p 2 p 网络技术的主要功能模块2 图1 3 结构化p 2 p 网络资源发布和搜索过程示例5 图1 4 非结构化p 2 p 网络基“泛洪方式的搜索过程示例6 图1 5e d b f 中资源对象元信息的指数衰减14 图2 1i p s b s a r 算法伪码2 6 图2 2 邻居表n e i g h b o r l i s t 未满而队列为空时加谢指针变化前后位置2 8 图2 3 邻居表n e i g h b o r l i s t 己满而队列为空时加铆指针变化前后位置2 8 图2 4 各算法资源占有率、命中率、路由延迟和访问节点个数对比3 3 图2 5 查询请求节点接收返回节点列表3 6 图2 6 增量式查询一般算法模型一3 6 图2 7 增量式查询一般算法模型与不同路由算法相结合的增量式查询效果3 9 图3 1 弱状态路由示例。4 2 图3 2 将元素x 、y 添加到b l o o mf i l t e r 中的结果示例4 3 图3 3 节点接收路由条目更新操作的算法伪码4 5 图3 4 计算路由条目与查询语义相关性的算法伪码4 6 图3 5 有效路由成功率51 图3 6 单播路由成功率5 2 图3 7 空间开销5 2 图3 8 节点接收和转发b l o o mf i l t e r 的算法伪码5 4 图3 9d w a l k e r 查询路由算法伪码5 7 图3 1 0 临界值f 的取值范围与饱和率口的关系5 9 图3 1 1 查询命中率和查询代价与各节点共享资源个数关系6 0 图3 1 2 路由条目中b l o o mf i l t e r 的个数与资源个数关系6 l 图4 1 节点接收和转发带有副本对象元信息的消息算法伪码6 5 图4 2 依指数衰减传递副本的b l o o mf i l t e r 的算法伪码6 5 图4 3 不同网络规模、节点出度和传递距离下的覆盖率、无噪率和最优路由率7 0 图4 4 传递距离为ia v gi 、la v gi 1 和ia v gi 2 时的无噪率7 0 图4 5 覆盖率与副本个数关系7 1 图4 6 查准率7 2 图4 7d c b f 与b u b b l e s t o r m 结果对比7 3 第1 v 页 国防科学技术大学研究生院博十学位论文 图5 1s c q r 查询路由算法的伪码7 7 图5 2 查询成功率与最大路由跳数关系。8 1 图5 3 语义更新创建算法伪码8 5 图5 4 语义更新接收算法伪码8 5 图5 5s o s c 算法的查询路由算法伪码8 7 图5 6 查询成功率与最大路由跳数关系9 0 图5 7 实验值与理论值对比关系9 0 图5 8 衰减系数d 对s o s c 算法性能影响9 1 图5 9 聚类总数和聚类节点数对s o s c 算法性能影响9 2 第v 页 国防科学技术大学研究生院博士学位论文 第v i 页 国防科学技术大学研究生院博士学位论文 摘要 对等网络( p e e r - t o p e e r ，p 2 p ) 是近年来兴起的一种重要网络技术，在很多领 域里都有着广泛的应用。当前，i n t e r n 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 增量式查询算法i p s b s a r 和非结构化p 2 p 网络的增量式查询一般算法模 型。算法i p s b s a r 基于人类社会关系中的熟人关系，将人类社会关系中个体之间 交流与合作机制引入到p 2 p 网络中，通过一种新的邻居节点访问和更新方式，使 得查询请求节点尽量将查询请求优先转发给尚未访问的语义相关节点，实现了增 量式搜索。增量式查询一般算法模型可以与查询路由算法相结合，使得针对同一 查询语义的增量式查询尽力优先访问语义最为相关的节点。分析和模拟表明，算 法i p s b s a r 能够以较低的代价和较低的路由延迟，获得较高的增量式查询命中率； 对同一语义进行穷尽式搜索时，能够搜索出满足查询语义的绝大多数资源，有效 实现增量式搜索，具有较高的效率；增量式查询一般模型能够与查询路由算法相 结合，实现增量式搜索。 针对弱状态路由机制的存在的问题，提出了一种面向p 2 p 网络概率路由的 b l o o mf i l t e r ( o b f ) 和基于衰减b l o o mf i l t e r 的高效概率路由算法d w a l k e r 。o b f 通过保存对象的更新操作、以及发布该对象的源节点等属性，使得o b f 能够解决 基于b l o o mf i l t e r 的p 2 p 网络中信息多径叠加问题，有效抑制噪音的影响，进而使 得弱状态路由算法能够以很高的概率将查询消息沿着正确的方向进路由。d w a l k e r 基于有向随机网络，以指数衰减b l o o mf i l t e r 的形式发布和传递节点共享资源的元 信息，且最大传递距离小于网络中任意两点之间距离的期望值，从而有效抑制了 衰减b l o o mf i l t e r 传递过程中的多径叠加问题；以多个b l o o mf i l t e r 代替仅用单个 b l o o mf i l t e r 表达一个路由条目，在保持单个b l o o mf i l t e r 假阳性判定概率的前提 第i 页 国防科学技术大学研究生院博士学位论文 下，可根据需要动态增加b l o o mf i l t e r ，以容纳更多资源对象的路由信息；仅通过 本地知识，以严格的数学分析，计算出各个b l o o mf i l t e r 值为l 的比特位个数的最 大比例，以及下一跳转发节点的路由条目至少被查询匹配的值为1 的比特位个数 的临界值，使得进入目标对象传播范围内的查询消息既能够以较高的概率辨认出 正确路由方向，又能够以较小的概率产生冗余的沿着错误方向的路由。分析和模 拟表明，o b f 使得基于弱状态的路由能够以很高的概率沿着正确方向进行； d w a l k e r 能够以较低的查询代价、路由条目中较少b l o o mf i l t e r 的个数和较低的路 由延迟实现较高的查询命中率。 为使得网络中的任一节点对任意对象的查询请求，均能以较低的查询代价、 在确定的路由延迟内、高概率的命中目标对象，本文提出了基于副本复制和b l o o m f i l t e r 的网络覆盖算法d c b f 。d c b f 基于有向随机网络，对各个资源对象在网络 中创造少量的副本，各个副本被放置到网络中的某个随机节点，接收资源对象副 本的节点，以分布式衰减b l o o mf i l t e r 向邻近节点传递副本的成员资格信息。实验 和理论均表明，d c b f 算法仅需要发布少量的副本个数，即可覆盖网络中绝大多数 节点，能够使得网络中任何一个节点，发起针对任何一个资源对象的查询，均能 够以极低的查询代价，在确定的路由延迟范围内，高概率的路由到目标节点。 本文进一步提出了基于语义聚类拓扑的超节点模式的p 2 p 查询路由算法 s c q r 、基于语义聚类拓扑的分布式模式的p 2 p 查询路由算法s o s c 。s c q r 算法， 使得各节点依据语义相似性，形成语义聚类；各语义聚类选取一个聚类语义计算 者，负责计算聚类语义，同时与所有相邻聚类计算者建立连接关系，从而使得各 个聚类计算者能够感知到比单个聚类节点多得多的远程语义聚类；且查询消息在 聚类计算者之间转发，从而使得路由算法能够较快的将查询消息路由到目的聚类 节点。s o s c 算法通过直接用节点共享资源的关键词频率向量表达节点语义，各节 点均试图与最相似的节点建立邻居关系，以及以指数衰减方式传递节点语义向量， 创造性的解决了对等计算环境中聚类语义的表达和传递问题，使得节点可感知周 围节点的语义层次，从而使得各节点均能够以语义聚类为基础进行快速路由。分 析和实验均表明，算法s c q r 和s o s c 具有较小的路由延迟、较低的查询代价和 较高的查询命中率。此外，对基于衰减b l o o mf i l t e r 的s o s c 算法实现进行了相应 的讨论，提出了具体的实现方法。 关键词：对等计算；非结构化拓扑；增量式查询；b l o o mf i l t e r = 弱状态路由； 概率路由；副本复制；语义聚类；资源定位 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，p e e r - t o p e e r ( p 2 p ) c o m p u t i n gh a sb e c o m eap o p u l a r n e t w o r kc o m p u t i n gt e c h n i q u e a p p l i c a t i o n so fp e e r - t o - p e e rc o m p u t i n gh a v es p r e a di n t o m a n yf i e l d s u n s t r u c t u r e dp e e r - t o p e e rs y s t e m sh a v eb e e nw i d e l yu s e d , i nw h i c ht h e r ei s n o 夙e dl i n kr e l a t i o n s h i p sa m o n gn o d e sa n db e t w e e ni e s o u l o co b j e c t sa n dn o d e s r e s o u r c el o c a t i o ni s 锄i m p o r t a n tb a s i cs e r v i c ei nl a r g e - s c a l ep e e r - t o - p e e rs y s t e m s ， w h i c hi m p l e m e n t st o p o l o g yc o n s t r u c t i o n , m e s s a g er o u t i n ga n dr e s o u r c es e a r c h t h e l a r g e - s c a l e ，h i g h l yd y n a m i c ， a n d w i d e l y s c a t t e r e dc h a r a c t e r i s t i c s b r i n gm a n y c h a l l e n g i n gp r o b l e m sf o rr e s o u r c el o c a t i o nt e c h n i q u eo fu n s t r u c t u r e dp e e r - t o - p e e r n e t w o r k s u s u a l l y , r e s o u r c el o c a t i o nt e c h n i q u ef o ru n s t r u c t u r e dp e e r - t o p e e rn e t w o r k s h a sal o we f f i c i e n c yw h i c hi sh a r dt og e tl o wq u e r yl a t e n c ya n dh i 曲q u e r yh i tr a t e 埘廿l l o wc o s ta tt h es a m et i m ei ft h e r ei sn oo t h e rs u p p o r t i n gm e c h a n i s m , w h i l ei n c r e m e n t a l s e a r c hh a sa l s on o tb e e ns u p p o r t e db yu n s t r u c t u r e dp e e r - t o - p e e rn e t w o r k s t h i st h e s i s d e e p l ys t u d i e su n s t r u c t u r e dp e e r - t o - p e e rr e s o u r c el o c a t i o nt e c h n i q u e t a sf o ri n c r e m e n t a ls e a r c hh a sn o tb e e ns u p p o r t e db yr e s o u r c el o c a t i o nt e c h n i q u eo f u n s t r u c t u r e dp e e r - t o - p e e rn e t w o r k s ，t h i st h e s i s p r e s e n t sa l li n c r e m e n t a lp 2 ps e a r c h a l g o r i t h mb a s e d o ns o c i a l a c q u a i n t a n c er e l a t i o n s h i p ( i p s b s a r ) a n dag e n e r a l i n c r e m e n t a ls e a r c hm o d e lf o ru n s t r u c t u r e dp 2 pn e t w o r k s i p s b s a rm i m i c sb e h a v i o r s o fp e e r si ns o c i a ln e t w o r k st oe s t a b l i s hd i f f e r e n ts e m a n t i cl i n k sa m o n gp e e r sa c c o r d i n g t ot h el e v e lo fk n o w i n ge a c ho t h e r , a n di n t r o d u c e san o v e la g g 七s sa n du p d a t em o d eo f n e i g h b o rl i s tt od oi n c r e m e n t a ls e a r c h t h eg e n e r a li n c r e m e n t a ls e a r c hm o d e lc a nw o r k 、啊吐lq u e r yr o u t i n ga l g o r i t h m st om a k ei n c r e m e n t a ls e a r c ht r yt oa c c e s ss e m a n t i cm o s t r e l a t e dn o d e s a n a l y s i sa n de x p e r i m e n tr e s u l t ss h o wt h a ti p s b s a rc a na c h i e v eh i g h i n c r e m e n t a lq u e r yh i tr a t e 、肮血l o wc o s ta n dl o wl a t e n c y , a n de f f i c i e n t l yr e t r i e v em o s to f r e l e v a n tr e s o u r c e sw h e nd o i n ge x h a u s t i v ei n c r e m e n t a ls e a r c h 、析t l lt h es a m eq u e r y s e m a n t i c ，t h eg e n e r a li n c r e m e n t a ls e a r c hm o d e lc a nw o r kw i 也q u e r yr o u t i n ga l g o r i t h m s t oi m p l e m e n ti n c r e m e n t a ls e a r c h a sw e a ks t a t er o u t i n gc a l ln o td or o u t i n gp r o p e r l y , t h i st h e s i sp r e s e n t san e wb l o o m f i l t e r ( o b f ) o r i e n t e da tp e e r - t o - p e e rn e t w o r kp r o b a b i l i s t i cr o u t i n ga n da ne f f i c i e n t p e e r - t o p e e rn e t w o r kp r o b a b i l i s t i cr o u t i n gs c h e m e ( d w a l k e r ) b a s e do nd e c a y i n gb l o o m f i l t e r s o b fi sb a s e do ns t o r i n ge a c hu p d a t ea n di t sp r o p e r t i e ss u c ha ss o u r c 宅n o d e s i s s u i n gr e s o u r c eo b j c o tw h i c hp r o v i d e s aw a yf o re a c hn o d et os t o r em e m b e r s h i p i n f o r m a t i o nr e c e i v e do n l yf r o ms h o r t e s tp a t h , a n di sa b l et or e s t r a i ne f f e c t so fn o i s e e f f e c t i v e l y , a n dt h e r e f o r eo b fi sa b l et om a k ew e a ks t a t er o u t i n gs c h e m e sd or i g h t d e c i s i o n sw i t l lk g hp r o b a b i l i t y d w a l k e ri s s u e sa n df o r w a r d sr e s o u r c eo b j e c t s m e t a - i n f o r m a t i o n 、纠t l ld e c a y i n gb l o o mf i l t e r sb a s e do nd i r e c t e dr a n d o mn e t w o r k d w a l k e rm a k e st h em a xf o r w a r d e dd i s t a n c el e s st h a nt h ee x p e c t e dd i s t a n c eb e t w e e n 第i i i 页 国防科学技术大学研究生院博士学位论文 a n yt w on o d e sw h i c he f f e c t i v e l yc o n s t r a i nt h ep r o b l e mo fm u l t i - p a t ha r r i v i n g o f d e c a y i n gb l o o mf i l t e r s d w a l k e rr e p l a c e ss i n g l eb l o o mf i l t e r 、) i ，i t l lm u l t i p l eb l o o mf i l t e r s 弱ar o u t i n ge n t r y , w h i c hc a nh o l dm o r er o u t i n gi n f o r m a t i o nw h i l ec o n s t r a i n i n gs i n g l e b l o o mf i l t e rf a l s ep o s i t i v e d w a l k e rc o m p u t e st h em a xp r o p o r t i o no fb i t sv a l u e d1o fa b l o o mf i l t e ra n dt h el e a s tn u m b e ro fc o m m o nv a l u e d1b i t so fa ne n t r yb l o o mf i l t e r 、撕证l aq u e r yb l o o mf i l t e r , w h i c hm a k eaq u e r yr o u t i n gi nt h er i g h td i r e c t i o n 晰廿lh i 曲 p r o b a b i l i t yw h i l eg e n e r a t i n gr e d u n d a n te r r o rr o u t i n g 、撕ll o wp r o b a b i l i t y a n a l y s i sa n d e x p e r i m e n tr e s u l t ss h o wt h a to b f i sa b l et om a k ew e a ks t a t er o u t i n gs c h e m e sd or i g h t d e c i s i o n s 、) l ，i t l ll l i g hp r o b a b i l i t y , d w a l k e rc 锄a c h i e v eh i g hq u e r yh i tr a t e 、拥n 1l o wc o s t , l o wl a t e n c y , a n df e wn u m b e ro fb l o o mf i l t e r so far o u t i n ge n t r y i no r d e rt om a k ea n yq u e r yi s s u e db ya n yn o d ea c h i e v eh i g hq u e r yh i t s 谢廿ll o w c o s ta n dl a t e n c y , t h i st h e s i sp r e s e n t san o d e sc o v e t i n ga l g o r i t h mc a l l e dd c b fw h i c hi s b a s e do nd a t ac o p y i n ga n db l o o mf i l t e rt e c h n i q u e d c b fm a k e saf e wc o p i e so fe a c h s h a r e dr e s o u r c eo b j e c t , a n dp l a c e se a c hc o p yo nar a n d o ms e l e c t e dn o d eb a s e do na d i r e c t e dr a n d o mn e t w o r k e a c hn o d ef o r w a r d sac o p i e do b j e c tm e t a - i n f o r m a t i o nt o n e i g h b o rn o d e s 、析t hd i s t r i b u t e dd e c a y i n gb l o o mf i l t e r s a n a l y s i sa n de x p e r i m e n tr e s u l t s s h o wt h a td c b fc a l lm a k em o s to fn o d e sf e e lm e t a i n f o r m a t i o no fa n yo b j e c tb y m a k i n go n l yaf e wc o p i e sa n df o r w a r d i n gac o p i e do b j e c t m e t a - i n f o r m a t i o n 、析t h d i s t r i b u t e dd e c a y i n gb l o o mf i l t e r , a n dt h e r e f o r ec a na c h i e v eh i g hq u e r yh i t s 、砘t 1 1l o w c o s ta n dl a t e n c y t h i st h e s i sa l s op r e s e n t sa p e e r - t o p e e rq u e r yr o u t i n ga l g o r i t h mb a s e do ns e m a n t i c c l u s t e r ( s c q r ) w h i c hi sas u p e r - n o d em o d ea n das e l f - o r g a n i z i n gs e m a n t i cc l u s t e r b a s e dp e e r - t o p e e rq u e r yr o u t i n ga l g o r i t h m ( s o s c ) w h i c hi st o t a l l yd i s t r i b u t e d s c q r m a k e sn o d e sc l u s t e r e da c c o r d i n gt ot h e i rs e m a n t i c ，a n de a c hc l u s t e re l e c t sas u p e r - n o d e a sc l u s t e rc o m p u t i n gn o d ew h i c hi sr e s p o n s i b l ef o rc o m p u t i n gc l u s t e rs e m a n t i ca n d e s t a b l i s h i n gl i n k s 、而t l la l ln e i g h b o rc l u s t e rc o m p u t i n gn o d e s q u e r yi sr o u t e da m o n g c l u s t e rc o m p u t i n gn o d e s t h r o u g he x p r e s s i n gn o d es e m a n t i cb yi t ss h a r e dr e s o u r c e s k e y w o r d sf i e q u e n c yv e c t o r , e s t a b l i s h i n gan e i g h b o rl i n kb e t w e e nn o d e sw h o s es e m a n t i c i sm o s tr e l e v a n t , a n dt r a n s m i t t i n gn o d es e m a n t i ca f t e rb e i n gd e c a y e d , s o s cc r e a t i v e l y s o l v e st h ep r o b l e mo fc l u s t e rs e m a n t i ce x p r e s s i n ga n dt r a n s m i t t i n gi nad i s t r i b u t e d e n v i r o n m e n t s o s cm a k e san o d ef e e lt h es e m a n t i ch i e r a r c h yo fi t sn e a r b yn o d e s ，a n d t h e r e f o r ee a c hn o d ec a nd om e s s a g er o u t i n gb a s e do ns e m a n t i cc l u s t e r a n a l y s i sa n d e x p e r i m e n t sr e s u l t ss h o w t h a ts c q ra n ds o s cc a l la c h i e v eh i g hq u e r yh i t 、炳也s m a l l r o u t i n gl a t e n c ya n dq u e r yc o s t f u r t h e r m o r e ，d e t a i l e di m p l e m e n t a t i o no fs o s cb a s e do n d e c a y i n gb l o o mf i l t e ri sa l s od i s c u s s e d k e yw o r d s ：p e e r - t o p e e rc o m p u t i n g ，u s t r u c t u r e d t o p o l o g y ，i n c r e m e n t a l s e a r c h ，b l o o mf i l t e r ，w e a ks t a t er o u t i n g ，p r o b a b i l i s t i cr o u t i n g ，d a t ac o p y ，s e m a n t i c c l u s t e r ，i e s o u r c el o c a t i o n 第i v 页 国防科学技术大学研究生院博十学位论文 第一章绪论 对等网络( p e e r - t o p e e r