Research & Development 研究与开发
基于P2P的搜索技术算法分析
研 究 与 开 发
申志伟1
马少武1
王佳楠2
北京 100032 100032
唐雄燕1
1 中国联通集团国家工程实验室 2 联通宽带在线有限公司 北京
摘 要 通过论述P2P搜索技术的发展,现状;介绍目前主流的P2P搜索算法;分析其优势在于应用先进 的对等搜索理念,可不通过给定的中央服务器,也可不受信息文档格式和宿主设备的限制,对互联网络 进行全方位搜索,并提出下一步工作建议. 关键词 P2P;搜索技术;互联网
Gnutel1a采用带有深度限制的广度优先搜索(BFS)
引言
搜索引擎的出现给用户在互联网上快速准确地得到 有价值的信息带来极大便利. P2P理念与搜索引擎技术相结合,是第三代搜索引 擎技术发展的一个热点.P2P搜索技术不需要中心服务 器的支持,不受信息文档结构的限制,使每个参与者在 搜索时可以共享文件,目录,与传统的搜索引擎相比具 有更好的深度和广度.
方法,这类系统又称为非结构化的P2P系统.当一个节 点需要搜索一个文件,它向所有邻居节点发送这个请 求,邻居节点又向它们的邻居节点发送请求,就这样向 外扩张,拥有所请求文件的节点就可以响应这个请求, 这种搜索方法称作泛洪请求.尽管各个节点对本地文件 的搜索通常是采用文件标识符的搜索,理论上可以使用 任何的匹配方法,例如基于关键字的全文搜索,只要各 个节点将本节点满足搜索请求的结果返回给请求的源节 点即可.但这种模型本身因为采用应用层广播的协议, 导致消息量过大,网络负担过重,使得性能较差的节点 很快就成为整个系统的瓶颈:相对于所使用的消息量, 搜索效率并不高.
1
研究现状[1]
Napster雏形的建立及普及推动了P2P技术的研究
和应用.越来越多的P2P软件的发布和流行,一步步的 验证了对等计算思想的成功,如Gnutel1a,Freenet, BitTorrent,KaZaA,Skype,Edonkey等. Napster采用中央索引的方法实现资源的搜索.任 何一个注册的节点,都要向中央服务器传送自己所共享 资源的一个索引.一个节点想要搜索资源,将带有所要 搜索资源标识的搜索请求发送到中央服务器,中央服务 器检索存储在本地的资源,告知资源请求者有该资源的 节点标识,然后资源请求者直接去访问资源拥有者节 点,下载所请求的文件或者使用其它资源.Napster模 式集中搜索的特点决定了其可伸缩性和可靠性不好.
2
P2P搜索与传统搜索的区别
传统搜索(如Baidu,Google等)并不是真正的搜索
互联网,它搜索的实际上是预先整理好的网页数据库的 索引,其搜索引擎工作过程大致是首先从互联网上抓取 网页资料,然后建立互联网网页索引数据库,最后在索 引数据库中进行搜索. 而P2P搜索是真正的搜索互联网.在P2P网络中, 用户将各自的资源共享出来,资源就存放在用户的PC 上.一台PC上的用户的搜索请求通过网络同时发给网
6
信息通信技术
络上另外N台PC,如果搜索请求未得到满足,这N台 PC中的每一台都会把该搜索请求转发给另外N台PC, 这个过程不断进行下去.这样,搜索范围将在几秒钟内 以几何级数增长,几分钟内就可搜遍几百万台PC上的 信息资源.
在本地的索引之后,将存有该文件的节点地址(节点2) 发给节点1,然后节点1就直接从节点2下载该文件.
3.2
分布式搜索[3]
分布式搜索可以分为非结构化搜索算法和结构化搜
索算法.
Research & Development
3
P2P搜索算法分析
在对当前主流的P2P搜索算法进行分析之前,先对
P2P搜索技术分别从用户角度和网络角度给出其基本的 评价指标[2]. 从用户角度来看,好的搜索技术可以使用户能够有 效的定位需要的内容,用户评价一个搜索技术的好坏, 主要从返回的结果数量,满意程度和搜索响应时间来进 行评价.从网络的角度来评价搜索技术,主要包括搜索 的效率,搜索技术的可扩展性及健壮性. 搜索算法是决定P2P系统性能的首要因素,下面分 析一下目前主流的P2P搜索算法.从索引存储位置角度 划分,P2P搜索算法分为集中式搜索,分布式搜索和混 合式搜索三类.按照索引受控程度,分布式搜索又可再 分为非结构化搜索算法和结构化搜索算法两类. 1) 非结构化P2P网络中的搜索技术.按照搜索策 略,可以分为两大类:泛洪搜索和信息搜索.泛洪搜索 是通过在网络中传播查询信息并且把这些信息不断扩散 给每个节点.而信息搜索是在搜索的过程中利用一些己 有的信息来辅助查找过程.由于信息搜索对资源的存储 有一些知识,所以信息搜索能够比较快的找到资源.下 面简要分析这两种算法. ① 泛洪搜索 盲目搜索(Blind search):在最初的Gnutella协议 中,使用的泛洪方法,就是一种典型的盲目搜索.在网 络中,每个节点都不知道其他节点的资源.当需要寻找 某个文件时,把这个查询信息传递给它的相邻节点,如 果相邻节点含有这个资源,就返回一个Query hit的信 息给Requester.如果与它相邻的节点都没有这个被查 询文件,就把这条消息转发给自己的相邻节点.由于这 种搜索策略是首先遍历自己的邻接点,然后再向下传 播,所以又称为广度优先搜索方法(BFS).BFS搜索把 消息传播给所有的邻接点,它消耗了大量的网络带宽, 使消息堵塞严重,效率比较低,扩展性不好.一些人在 BFS的基础上进行改进,它的方法是随机抽取一定比例 的相邻节点传递消息,而不是像泛洪一样把查询信息传

下一页