P2P文件搜索系统中基于标签的文件搜索方法

王 哲,何宗泽，韩 啸

(1.吉林省经济管理干部学院 发展规划处,长春 130012；2.吉林大学 仪器科学与电气工程学院，长春 130061；3.吉林大学 学报编辑部,长春 130012)



研究简报

P2P文件搜索系统中基于标签的文件搜索方法

王 哲1,何宗泽2，韩 啸3

(1.吉林省经济管理干部学院 发展规划处,长春 130012；2.吉林大学 仪器科学与电气工程学院，长春 130061；3.吉林大学 学报编辑部,长春 130012)

针对点对点(P2P)文件搜索技术存在网络带宽消耗大和查询速度慢等问题,为专用的P2P系统设计一种基于标签的文件搜索方案.该方案给出了将系统底层每个节点所控制的相关文件上传到中间层子服务器,及将顶层中央服务器接收到的文件查询转发到相关子服务器的方法,并运用标签优先顺序技术实现了查询的快速转发.性能评估结果表明,基于标签的文件搜索方法在转发查询过程中,必须检测的标签个数由一个很小的常数界定,从而节省了系统的网络带宽,提高了文件的搜索速度.

P2P系统；标签；文件搜索

随着互联网应用规模的迅速扩大,传统的客户机/服务器模式(Client/Server,C/S模式)由于存在服务器端的单点故障、带宽和性能瓶颈等因素,已满足不了用户的需求.为克服C/S模式的缺陷,点对点(Peer-to-Peer,P2P)系统目前已成为计算机领域的研究热点之一[1].

P2P充分利用节点资源,形成一个自组织网络[2].每个节点在网络中的地位都对等,既充当服务器为其他节点提供服务,同时也充当客户机,享用其他节点提供的服务.在P2P系统中文件搜索任务是在大规模、动态性的P2P网络中找到满足需求的文件,同时仅花费系统可接受的网络通讯开销、单点可接受的计算开销及用户可接受的等待时间[3].目前,P2P搜索技术主要包括如下内容：

1)基于中心化拓扑的搜索.这种搜索方式需要一个中央服务器存放其他节点所共享资源的索引,节点搜索资源时将带有所搜索资源标识的搜索请求发送到中央服务器,中央服务器检索资源索引,告知资源请求者拥有该资源的节点标识,然后资源请求者再直接访问资源拥有者的节点,下载所请求的文件或者使用其资源[4].这种方式的优点是搜索全面且速度较快;但中央服务器的负载能力制约了节点的数量,系统的扩展性不够；一旦中央服务器崩溃,则整个系统将瘫痪无法运行.

2)基于非结构化拓扑的搜索.与中心化拓扑搜索不同,这种方式没有中央服务器,用户的请求以广播的方式发给所有节点,这些节点若不能满足请求,则将请求继续以广播的方式发给与自己相连接的其他节点,直到请求得到响应为止.这种搜索方式的优点是简便易行,且具有较高的鲁棒性和可扩展性；缺点是网络带宽的消耗巨大.

3)基于结构化拓扑的搜索.这种方式一般采用支持多关键词的分布式散列表技术,即一个文件与一个key值相对应(一般通过对文件进行Hash得到),系统中的每个节点负责保存一定范围的key值[5].搜索文件时,先用同样的算法计算出每个key的Hash值,再根据Hash值找到key对应信息的储存位置,从而快速定位文件的位置.这种搜索方式的优点是速度快,但key值出现在文件中的频率不同,导致节点存储信息的不对称.

1 P2P系统模型

本文针对一个专用的P2P文件搜索系统,实现分布式环境下一种有效的文件搜索设计方案.该系统采用3层架构,即由顶层、中间层和底层组成.其中,底层由大量的用户节点组成,这些用户节点根据所包含的用户兴趣相似性或地理位置的接近性分成若干个组,每组都对应于中间层的一个子服务器,组内的用户节点通过一个逻辑链路被连接到相对应组的子服务器上；中间层由若干子服务器组成,即S={S1,S2,…,Sm},主要负责处理某组内用户节点所提交的文件查询消息,并通过反复收集用户节点所包含的“新”索引信息保持与用户节点的集成性；顶层采用一个中央服务器,主要负责文件查询服务,维护用户节点与子服务器的对应性.

2 基于标签的文件筛选技术

在P2P文件搜索系统中,中央服务器包含一组标签,它们被附加到用户节点包含的每个文件及子服务器包含的索引上.令T={t1,t2,…,tn}表示所有标签的集合,则T中每个标签代表实际应用中一个对象的关键词或关键短语.例如,标签“中国”可表示几个不同的含义,它代表国家的名字或一种文化等.在设计方案中,文件上附带的标签集合依据标签的普及性确定,假设集合T已由几个专家和管理者预先指定.根据Zipf第一定律,在自然语言的语素库中,每个单词出现的频率与其在频率表中的排序成反比[6].为了高效地筛选出与标签相关联的文件,应避免选择高频词作为T的成员,即T中应包含出现频率较低并具有代表性的标签.

2.1 标签优先顺序 令σ是从T到{1,2,…,|T|}的一个双射(|T|表示集合T的基数),则σ(t)称为标签t的优先级.如果σ(t1)<σ(t2),则在σ下标签t1比标签t2的优先级高.由σ定义一个标签序列,称为标签的一个优先顺序：σ-1(1),σ-1(2),…,σ-1(|T|),其中σ-1表示函数σ的逆函数.

2.2 标签集包含关系 令T1,T2⊆T是标签集的两个子集.在σ下,若T2的优先顺序是T1优先顺序的一个前缀,则T2包含T1,记为T1⊆σT2.例如,T={t1,t2,…,t9},且σ(ti)<σ(ti+1),其中1≤i≤8.在σ下,假设T1={t1,t2,t3},T2={t1,t2},因为T2的优先顺序t1,t2是T1优先顺序t1,t2,t3的前缀,则T2包含T1；假设T3={t2,t3,t4},因为T2的优先顺序t1,t2是T3优先顺序t2,t3,t4的前缀,则T2包含T3.若T1σT2,且T2σT1,则T1和T2在σ下没有可比性.判断T1,T2包含关系的函数Inclusion(T1,T2)描述如下：

1)如果|T1|<|T2|,则函数返回false并终止;

2)如果T2=Ø,则函数返回到true并终止;

3)令t1为T1中优先级最高的标签,并且t2为T2中优先级最高的标签,令T1∶=T1{t1}且T2∶=T2{t2};

4)如果t1≠t2,则函数返回到false并终止;否则,执行2).

3 文件上传算法

底层用户节点所包含的每个文件都已被用户添加了标签,每个子服务器都与标签的一个子集对应.本文通过标签集合包含关系将文件和子服务器相关联,当文件被重新创建或文件的内容被用户节点修改时,则将用户节点所包含的索引上传到子服务器的算法步骤如下：

3)连接子服务器Si并上传文件索引给Si.

文件上传算法由中央服务器处理,将给定的文件索引传递给它的子服务器,而标签和子服务器之间的相关性通过中央服务器的一个列表进行维护.因此,如果一个子服务器Si在步骤2)中得到确认,则用户节点可立即获得在Si中的信息,包括它的IP地址和端口号.为降低每个子服务器的负载,每个子服务器只存储文件的索引,而文件的实际内容存储在各个用户节点中；同时,每个用户节点都保持所含文件的子服务器信息,这样可保证文件索引一旦被用户节点修改,就能马上更新.

4 查询转发算法

在专用P2P系统中,顶层的中央服务器负责完成将接收到的相关文件查询转发到一个子服务器.因此,高效的查询转发算法是文件搜索过程的核心技术.令NR为一个系统变量,表示到目前为止所发现的文件总数,当每次发现一个新文件时,令NR=NR+1,当NR达到预定值时,搜索过程停止.中央服务器的查询转发算法步骤如下：

3)C连接到子服务器Si并将q转发给Si;

4)子服务器Si接收到查询q后,进行类似于传统搜索引擎的文件搜索,并把搜索结果返回给发出请求的用户节点,匹配结果数目提交给中央服务器C;

5 方案性能评估

在设计方案中,文件搜索效率的高低取决于相关文件查询转发到一个子服务器的时间长短和速度快慢,本文通过检测标签的数目对设计方案的性能进行评估.

5.1 判别树 令T={t1,t2,…,tn}是一个标签集,σ是定义在集合T上的标签序列.设计方案中,中间层的每个子服务器都与T的子集T′相对应,且存在一个子服务器,它与序列σ下包含T′的标签集相关.该模式可由如下树型结构表示：

1)树的每个节点与一个标签集相关联,令T(u)表示与节点u相关联的标签集;

2)树的根节点与一个空的标签集相关联;

3)令t′是T(u)中最低优先级的标签,且i′=σ-1(t′),则节点u没有子节点或有n-i′个与标签集T(u)∪{σ(j)}相关的子节点,其中i′+1≤j≤n;

4)每个叶子节点对应于一个与子服务器相关的标签集,若叶子节点在其父节点最左边,则由子服务器充当其父节点.

在标签集满足上述树型结构的条件下,从客户端收到的查询是从根节点出发向叶子节点(包含该查询的标签集)的搜索过程.因此,中央服务器识别一个与给定查询相关的子服务器所需的时间与查询相关的叶子节点的深度成比例,即通过计算判别树的最大深度可评估本文方案的性能.

5.2 评估实例 设N表示系统中用户节点所含文件的总数,pi表示标签ti附加到文件的概率(在Zipf第一定律下,标签ti被附加到文件的概率与(1/i)ε成正比,其中参数ε称为Zipf参数).假设不同标签间相互独立,且树型结构中与节点相关联的文件数不超过α×N个,其中α是常数.

例1将一个用户感兴趣的文件赋予较高优先级,得到一个优先序列σ(ti)<σ(tj)且pi>pj,则每个节点的孩子节点(具有最高优先级的孩子节点)与其父节点的最大(子)集群相关联(称这种优先级最高的孩子节点为“最左”节点).因此,判别树中每层最左节点将与该层中最大的集群相关联,其中从根节点到该节点的距离为节点所在层数.

假设pi的优先序列符合Zipf第一定律,其中:参数N=10 000;T=100;α∈[0.01,0.1];Zipf参数ε∈[0.05,0.15].例1和例2的计算结果分别如图1(A)和(B)所示.由图1可见,例2判别树的最大深度比例1判别树的最大深度小得多.

图1 数值计算结果Fig.1 Results of numerical evaluation

[1] 翟晓萍,张顺颐,李君.一种分层的P2P网络模型 [J].电信快讯,2008(10):27-30.(ZHAI Xiaoping,ZHANG Shunyi,LI Jun.Hierarchical P2P Network Model [J].Telecommunications Information,2008(10):27-30.)

[2] 赵丽敏.基于Chord查找算法的P2P系统研究 [D].北京:北京大学,2014.(ZHAO Limin.Research on P2P System Based on Chord Lookup Method [D].Beijing:Peking University,2014.)

[3] 刘维光,陈立伟.一种基于DHT的P2P搜索方法 [J].微计算机信息,2006,22(3):131-133.(LIU Weiguang,CHEN Liwei.Research of P2P Searching Technology Based on DHT [J].Microcomputer Information,2006,22(3):131-133.)

[4] 裴云霞,张岳.浅谈P2P搜索技术 [J].科技信息,2007(30):50.(PEI Yunxia,ZHANG Yue.Analysis of P2P Search Technology [J].Science &Technology Information,2007(30):50.)

[5] 李运娣,冯勇.基于DHT的P2P搜索定位技术研究 [J].计算机应用研究,2006(10):226-228.(LI Yundi,FENG Yong.Study of Data Search in DHT P2P Networks [J].Application Research of Computers,2006(10):226-228.)

[6] Newman M E J.Power Laws,Pareto Distributions and Zipf’s Law [J].Contemporary Physics,2005,46(5):323-351.

(责任编辑：韩 啸)

FileSearchingBasedonTaginaP2PFileSearchSystem

WANG Zhe1,HE Zongze2,HAN Xiao3

(1.DepartmentofDevelopmentPlanning,JilinProvinceEconomicManagementCadreCollege,Changchun130012,China;2.CollegeofInstrumentation&ElectricalEngineering,JilinUniversity,Changchun130061,China;3.EditorialDepartmentofJournalofJilinUniversity,Changchun130012,China)

A tag-based file search method was designd for point to point (P2P)system to solve the large consumption of network bandwidth and slow query problem,which determines a way of uploading associated files held by each peer in the bottom layer to subservers in the middle layer and a way of forwarding a query received by the central server in the top layer to an appropriate subserver relevant to the query.A technique of priority sequence of tags was introduced to realize a quick forwarding of queries.The result of performance evaluation indicates that the number of tags which must be examined in forwarding a given query is bounded by a small constant,so as to save network bandwidth and raise the speed of file searching.

P2P system;tag;file search

10.13413/j.cnki.jdxblxb.2015.03.35

2014-10-13.

王 哲(1981—),男,汉族,硕士,讲师,从事计算机网络技术的研究,E-mail:20862282@qq.com.通信作者：韩 啸(1981—),男，汉族，博士研究生，编辑，从事计算机网络技术的研究,E-mail:hanxiao@jlu.edu.cn.

国家自然科学基金青年基金(批准号：61300147).

TP316.4

：A

：1671-5489(2015)03-0538-04