基于本体的P2P网络资源检索算法研究

雷 申，刘方爱

（1.山东师范大学 信息科学与工程学院，山东 济南250014；2.山东省分布式计算机软件新技术重点实验室，山东 济南250014）

0 引 言

P2P（peer－to－peer）系统的应用都依赖于系统的搜索效率，而P2P网络中资源如何被高效的定位仍然是P2P应用面临的巨大挑战［1］。P2P网络可以分为非结构化P2P网络和结构化P2P网络［2］。非结构化P2P网络基于洪泛等算法进行路由，路由效率低且扩展性差［3］。而结构化P2P网络（如 Chord［4］、CAN［5］等）通过 DHT （distributed hash table）进行路由，相对无结构化P2P网络具有查询速度快、路由延迟低、扩展性能好［6］等优点。而DHT网络中的拓扑结构不仅仅是节点之间的位置关系，更重要的是为节点中原本没有位置关系的资源赋予了与节点拓扑相似的关系［7］。因此，在结构化P2P中，资源可以被高效的定位，同时DHT也使查询请求只能根据资源的关键字进行精确的匹配，并且不支持语义关联检索，缺乏模糊搜索能力，使部分查询结果在内容上匹配程度不高。因此，如何在基于DHT的结构化P2P网络中实现语义层次的检索是结构化P2P网络面临的主要问题之一。

文献 ［8］构建了一个P2P网络环境下的文献检索系统SemreX，并提出一种基于语义相似度的P2P拓扑管理和查询路由算法来提高系统的搜索效率。文献 ［9］结合向量空间模型VSM、本体 （Ontology）与DHT技术将相似文档聚集在临近位置，减少了路由跳数，在一定程度上加快了检索的速度，扩大了检索的范围。但是系统中特征向量产生的高维矩阵增加了计算复杂度。文献 ［10］针对P2P网格，提出了一种基于分布式网格本体的P2P网格资源匹配模型。在该模型中，全局本体由各个节点的独立的本地网格资源本体构成。网格资源匹配操作完全分布式地由节点自主控制。文献 ［11］划分了网络中资源的主题，提出了一种语义覆盖网络SSON，其基于结构化P2P网络路由，具有可靠、高效等特点。

本文在以往研究的基础上，提出一种基于DHT和本体的搜索方法SOC （semantic ontology chord），将类似文档聚集在一起、使相同兴趣的节点趋近于邻近位置来改善搜索效率，同时支持模糊查询。该方法具有较好的实用性和扩展性，为有组织的P2P系统提供了一种高效的数据查询方法。

1 基于本体的P2P网络搜索方法

1.1 本体的应用

本体的概念来源于哲学，目前被广泛接受的定义由Gruber给出［12］，即 “本体是概念模型的明确的规范说明”。本体就是通过对某特定领域内的知识用公认的规范进行定义，并描述这些定义与定义之间的关系，使人和机器都可处理和交流的一种知识模型。它可以包括这个领域都有哪些概念、这些概念都有什么属性以及概念间的层次和关系等。本体的应用广泛，目前已被应用于电子工程、化学、电子商务和数据挖掘等领域。

SOC可以利用 SWRC （semantic web research community ontology）［13］等 已 设 计 好 的 本 体 来 构 建 节 点 本 体。SWRC是学术科研领域的一个本体，用与描述科研机构、科研项目和出版物等概念以及它们之间的关系。利用SWRC将节点本体细化为文献本体和主题分类本体两部分。其中文献本体由文献的概念、属性以及各种关系等组成；而主题分类本体则包含了对领域内各种主题的分类和主题之间的关系，例如 “软件工程”与 “计算机科学”之间是subTopicof和superTopicof的关系等。

通过节点本体，能够较好的解决因关键词精确匹配带来的资源内容不符等问题，使查询请求和节点间能建立较强的语义关系，使检索上升到语义层。对于有查询请求的节点：可以对用户的检索请求进行处理和规范，根据关键词对要查询的资源进行归类，判断需要查询的资源属于哪个类别，以获得更好的查询效果；对于收到查询请求的节点：可以通过请求消息计算出相近似的资源并返回，使网络能够最大限度的满足查询请求。

本体中两个主题之间在语义上的相似度可以通过文献［14］介绍的相似性函数 （见式 （1））来计算，其通过计算两个主题t1、t2在主题层中的位置来计算它们之间的距离，当距离较近并高于某一个阈值时则认为两个主题相似。

其中α，β≥0。l是在本体的层次结构中主题t1、t2之间的最短路径。h是第一个包含t1、t2的父主题的层次位置。显然l越大或h越小，t1、t2之间的相似度越小；反之亦然。α和β是参数，分别决定了最短路径长度l和父主题层次h的影响比重，文献 ［14］经过实验表明α和β的值分别在0.2和0.6时最佳。由式 （1）可知，当不同的主题通过计算即t1≠t2时，Sim的值越大，则t1、t2之间的相似度就越大。

1.2 SOC基本设计

Chord是MIT提出的一种典型的结构化P2P网络模型，具有映射简单、搜索速度快等优点。它通过一致性散列 （consistent hashing）运算将节点和文档映射到值域为［0，2m－1］的环形结构中，并在此基础上利用DHT实现资源定位。SOC是从Chord模型调整而来，其网络中每个节点共享一个相同的领域本体，并利用该本体来进行查询请求的优化。在Chord原有的结构基础上改进了节点维护的资源索引，使查询时可以返回更多相近主题的结果，进而提高查全率。

Chord模型中，文件被关联到＜Key，Value＞对，节点标识符也采用节点名字 （如IP地址）的散列值，节点的每个资源对应的＜Key，Value＞对被保存到与Key相近的节点标识符的机器中，使查询消息所代表的资源对象与节点地址相关联。当有新节点加入网络或者有新的资源关联到＜Key，Value＞对时，将对应的＜Key，Value＞对转移到更相近的节点上，节点离开时其保存的＜Key，Value＞也会转移到相邻的节点。

SOC保持原有放置机制不变，将＜Key，Value＞对改进为＜Class，Key，Value＞，Class是节点通过共享的领域本体对资源进行规范和处理后的分类信息的散列值，资源文件将会由Class和Key确定。此时节点的每个资源对应的＜Class，Key，Value＞信息将被保存到与Class相近的节点标识符的机器中，而原本散列关键词得到的Key因查询需求不进行散列。在查询的过程中，节点将包含Class和Key的请求发送到与Class键值最接近的节点上，目标节点将同一Class下与Key相近的＜Class，Key，Value＞返回。源节点根据返回的Value信息找到放置资源的节点进行资源传输。

SOC中每个节点除维护原有的路由信息外还维护着一张兴趣节点表，其保存了提供资源的节点的历史传输信息，即通过Class查询后得到的Value中成功提供资源的节点信息。事实上，若同一个节点在一定时间范围内总是能满足另一个节点的查询请求，那么这两个节点有可能具有较为相似的兴趣；另一方面，如果节点在查询时优先向有相同兴趣的节点发送请求，那么得到匹配资源的几率会增大。节点在查询时可以先向兴趣节点表中记录的节点发送查询请求，目标节点在收到请求时通过一定算法计算出与请求最接近的资源信息后返回。

1.3 SOC中的路由

SOC初始时路由算法与Chord模型类似，在SOC中节点同样需要保存m个其它节点的信息，这些信息的集合称为查询表，表格中节点的间距以2k－2的关系排列 （k是表中的数组下标）。节点将自身资源的＜Class，Key，Value＞保存到标识符与Class键值相近的节点上并维护，在查询时将包含Class和Key的请求信息发送给对应节点即可。节点在查询到需要的资源后，记录提供资源节点信息到兴趣节点表，在下一次查询时先向兴趣节点表中的节点发送查询请求，这样将有较大几率获得期望结果。下面是路由算法的详细过程：

（1）当节点A有查询请求时，通过节点本体处理查询关键词，得到关键词在相关领域内的分类信息，然后将分类信息散列为Class键值。

（2）如果节点的兴趣节点表为空，则根据查询表将包含Class和Key的请求信息发送到与Class键值最接近的节点A’上，跳至 （3）；否则还需要向兴趣节点表中的节点发送请求，并在请求中附加信息以证明此请求为一个兴趣查询请求，除步骤 （3）外还需要进行步骤 （4）。

（3）收到查询请求的节点X根据Class键值与自身存储键值比较，如果吻合，则通过本体计算出自身维护的与Key相同或相似的资源索引，并返回结果，否则返回已知与Class最相近的节点信息；重复这一步骤，直到找到相对应的节点为止。

（4）收到带有附加信息查询请求的节点，根据式 （1）计算自身资源与Key对应主题的相似度并在大于某一阈值时返回对应结果。

（5）节点A查询到＜Class，Key，Value＞时根据Value信息找到存储资源的节点B并传输资源，并记录节点B的地址等信息。

查询过程的伪代码如下：

A.Search（reqStr）｛//节点A发起发起查询，reqStr为处理后的查询信息

while（hasResult＝＝0）｛//无查询结果返回时

A’＝A.find ＿matched ＿node （reqStr）；//查 找 与reqStr最匹配的节点

A.send（reqStr）； //向匹配节点发送查询请求

if（A’.match （reqStr））｛//如果目标节点匹配

hasResult＝1；

return result； //返回结果

｝else｛ //否则重复直到有结果返回

A＝A’；

｝

｝

if（interestTable.length＞0）｛//如果兴趣节点表不为空

A.Send （reqInterestStr）；//向兴趣节点发送请求

｝

｝

如图1所示为SOC中一个节点查询数据的过程。

图1 SOC中节点查询示例

1.4 节点信息维护

1.4.1 节点的加入

SOC中节点p的加入步骤与Chord类似。一般的，新节点p加入网络的过程是通过网络中已存在的节点p’完成的，具体情况如下：①根据Chord规则更新p的前向节点、后继节点、网络中已存在的其它节点和自身的指针表信息；②将网络中归属于p的＜Class，Key，Value＞信息转移到节点p上并由p维护。

一般情况下，一个节点加入网络需要影响的节点数为O（logN），更新这些节点的信息需要的时间为O（log2N）。

1.4.2 节点的离开

节点的离开分为正常离开和异常离开。正常离开时会将自身保存的＜Class，Key，Value＞信息转移到后继节点上，然后由后继节点负责其它节点的更新，更新策略与节点加入时相同。当节点因特殊原因异常离开网络时，会导致通过该节点的信息无法路由。为此，网络中每个节点维护一张后继节点表，其中包含已在网络中的r个后继节点信息。当节点的后继异常离开时，将后继节点表中第一个正常节点当作自己的后继节点，并由它负责其它节点的更新。

1.4.3 信息的更新

节点除维护查询表、后继节点表和属于自己的＜Class，Key，Value＞信息外，还需要维护一张兴趣节点表。兴趣节点表中保存了m个提供资源的节点与自身的历史传输记录，通常如表1所示。

表1 兴趣节点表示例

表1中兴趣节点地址即网络中节点标识符，查找成功率为查找成功的次数与向该节点发送查询请求的次数的比值。另外，节点在收到兴趣查询请求时，若自身资源不能满足请求，可以将兴趣节点表中查找成功率较高的节点地址返回。兴趣节点表根据提供资源节点的查询历史与查询成功率来不断更新，查询成功率高的节点将被排在表的更上面位置。

2 仿真与分析

根据SOC的特点，基于PeerSim［15］模拟器建立实验仿真环境，评估和分析了SOC中性能相关的参数。下面主要针对节点的查全率来测试模型的性能，并与传统Chord模型相应性能进行对比。

实验设置了1000个节点的网络规模，将含有56个主题类别的3000篇文档随机分配给节点，每个节点拥有文档数量最多不超过5篇。图2显示了随着模拟次数的变化，SOC与Chord的查全率的变化和比较情况。

图2 查全率比较

图3显示了SOC与Chord中随着节点的增多查全率的变化情况，这里的查全率是综合3次实验的平均值。可以看出，SOC相比Chord在查全率上有更好的效率。这是因为，SOC利用本体使节点支持模糊查询，并且使兴趣相近节点在网络中处于临近位置，因此实验中相比Chord具有更高的查全率。

3 结束语

图3 随着节点的增多时算法查全率比较

本文基于Chord模型，针对DHT网络只能进行精确关键词匹配查询的缺陷，介绍了一种基于DHT和本体的网络资源检索方法SOC （semantic ontology chord），该方法改进了DHT网络中的资源标识符，使目标节点能够返回更多的相关资源；利用全局共享的节点本体实现了模糊查询；同时使相近兴趣节点趋于临近位置，使节点在查询时有较大几率获得匹配结果。最后通过对模型进行仿真，测试了模型的性能，结果表明，该方法相比较Chord模型提高了5%－10%的查全率。

［1］WANG J Z，Bhulawala V.Design and implementation of a P2P cooperative proxy cache system ［J］.Journal of Interconnection Networks，2007，8 （2）：147－162.

［2］LAI Q.Technology of peer－to－peer network ［J］.China Science and Technology Information，2005，106 （15）：52 （in Chinese）.［赖庆.计算机对等网P2P技术 ［J］.中国科技信息，2005，106 （15）：52.］

［3］DENG ZM.Research on P2Psearch technology ［D］.Xi’an：University of Electronic Science and Technology of China，2007（in Chinese）.［邓祖明.P2P搜索技术研究 ［D］.西安：电子科技大学，2007.］

［4］Stoiea I，Morrs R，Karger D，et al.Chord：A scalable peer－to－peer lookup service for Internet applications ［C］.San Diego，CA，USA：ACM SIGCOMM Computer Communication Review－Proceedings of the SIGCOMM Conference，2001：149－160.

［5］Ratnasamy S，Francis P，Handley M，et al.A Scalable content－addressable network ［C］.San Diego，CA，USA：ACM SIGCOMM Computer Communication Review－Proceedings of the SIGCOMM Conference，2001：161－172.

［6］HUANG QF.Performance analysis and search algorithm improvement of structured P2Pnetwork ［D］. Wuhan：Huazhong University of Science and Technology，2008 （in Chinese）.［黄庆凤.结构化P2P网络性能分析与搜索算法研究［D］.武汉：华中科技大学，2008.］

［7］ZHOU XB，ZHOU J，LU HC，et al.A layered interest based topology organizing model for unstructured P2P ［J］.Journal of Software，2007，18 （12）：3131－3138 （in Chinese）.［周晓波，周健，卢汉成，等.一种基于层次化兴趣的非结构化P2P拓扑形成模型 ［J］.软件学报，2007，18 （12）：3131－3138.］

［8］CHEN HH，JIN H，NING XM，et al.SemreX：A semantic similarity based P2Poverlay network ［J］.Journal of Software，2006，17 （5）：1170－1181 （in Chinese）. ［陈汉华，金海，宁小敏，等.SemreX：一种基于语义相似度的P2P覆盖网络［J］.软件学报，2006，17 （5）：1170－1181.］

［9］WANG ZX，ZHANG DL，LIU L，et al.P2Pcomplex search based on ontology ［J］.Computer Applications，2007，27（4）：780－783 （in Chinese）.［王志晓，张大陆，刘雷，等.基于本体的P2P复杂搜索 ［J］.计算机应用，2007，27 （4）：780－783.］

［10］LU GM，GU XF，SUN SX，et al.Ontology based resource matching in the P2Pgrid ［J］.Computer Science，2006，33（4）：75－79 （in Chinese）. ［卢国明，顾小丰，孙世新，等.基于本体的网格资源匹配算法研究 ［J］.计算机科学，2006，33 （4）：75－79.］

［11］YU J，WANG BQ.SSON：A Semantic overlay network structure based on the routing mechanism of structured P2P network ［J］.Computer Science，2007，134 （16）：4－6 （in Chinese）.［于婧，汪斌强.SSON：一种基于结构化P2P网络路由的语义覆盖网络结构 ［J］.计算机科学，2007，134（16）：4－6.］

［12］DU XY，LI M，WANG S.A survey on ontology learning research ［J］.Journal of Software，2006，17 （9）：1837－1847（in Chinese）. ［杜小勇，李曼，王珊.本体学习研究综述［J］.软件学报，2006，17 （9）：1837－1847.］

［13］York Sure，Stephan Bloehdorn，Peter Haase，et al.The SWRC ontology－semantic web for research communities ［C］.Springer，Covilha，Portugal：Proceedings of the 12th Portuguese Conference on Artificial Intelligence，2005.

［14］Liy，Mclean ZAD.An approach for measuring semantic similarity between words using multiple information sources ［J］.IEEE Transaction on Knowledge and Data Engineering，2003，15 （4）：871－882.

［15］Márk Jelasity，Alberto Montresor，Gian Paolo Jesi，et al.PeerSim P2Psimulator ［EB/OL］. ［2011－05－08］.http：//peersim.sourceforge.net.