无结构P2P网络中一种高效的资源搜索机制

研究与开发　

无结构Ｐ２Ｐ网络中一种高效的资源搜索机制　

赵佩章。张同光　

（新乡学院计算机与信息工程学院新乡４５３００３）　

１　引言　在众多Ｐ２Ｐ资源搜索技术中，基于语义相关的搜索被重点关注。本文在基于语义分组的Ｐ２Ｐ网　络拓扑下，提出了一种新颖高效的搜索方式ＳＫＩＰ（ｓｅａｒｃｈ　ｗｉｔｈ　Ｋ－Ｉｔｅｒａｔｉｏｎ　ｐｒｅｆｅｒｅｎｃｅ），即Ｋ一层迭代　优先选择算法。查询定位到目标节点后，ＳＫＩＰ系统使用　一层迭代优先选择算法进行搜索。实验　表明，ＳＫＩＰ算法具有高效的搜索效率和较低的搜索开销，与现有的基于语义的搜索策略相比，具　有更高的查准率和更低的查询开销。　

近来Ｐ２Ｐ网络飞速发展，已成为互联网中最流行的应　

用之一。作为一个分布式的网络，其效率在很大程度上依　

赖于资源搜索的机制。尽管近年来关于Ｐ２Ｐ资源搜索的研　

究很多，但是在资源搜索方面一直存在很多需要解决的　

问题【ｌ１。通常情况下，结构化Ｐ２Ｐ网络更倾向于采用ＤＨＴ　

（ｄｉｓｔｒｉｂｕｔｅｄ　ｈａｓｈ　ｔａｂｌｅ，分布式散列表）的搜索方式；对于无　

结构Ｐ２Ｐ网络来说，例如ＧｎｕｔｅＵａ圆，资源搜索主要是使用　

洪泛（ｆｌｏｏｄｉｎｇ）或者有一定控制的洪泛来进行，如随机走　

（ｒａｎｄｏｍ　ｗａｌｋ）ｍ．由于这样会在资源搜索过程中访问大量　

不相关的节点。因此造成较低的搜索效率。为了提高无结　

构Ｐ２Ｐ网络资源搜索效率，研究人员提出了许多搜索机　

制　。但是这些搜索机制都没有考虑到节点之间语义的　

相关性，因此这些搜索机制仍然具有较高的搜索开销。　

在语义相关的Ｐ２Ｐ网络中．相关的节点连接在一起．　

形成一个语义组　ＧＥＳｔＳｌ和Ｃｓｓｔｇｌ两种搜索机制都使用ＶＳＭ　

新乡学院科技创新基金资助项目　（ｖｅｃｔｏｒ　ｓｐａｃｅ　ｍｏｄｅ，向量空间模型）㈣来计算节点的语义　

相关度。ＧＥＳ首先会对每一个节点进行矢量抽取。然后借　助于ＶＳＭ来计算节点间语义相关度，并依据计算出来的　

语义相关度数值生成网络拓扑。最后采用语义目标节点定　

位和洪泛相结合的搜索方式。ＣＳＳ在ＧＥＳ的基础上，将每　个节点按照所含内容的不同种类再细分为更小的虚拟节　

点，此法虽然可以提高资源查询的精准度，但是虚拟节点　

的引入却极大地增加了网络的开销。　

在本文中．提出了一种新颖高效的资源搜索机制　

ＳＫＩＰ。在ＧＥＳ和ＣＳＳ中，当通过ｂｉａｓｅｄ　ｗＭｋ（偏好查找）方　

法找到一个语义目标节点后。使用洪泛的方式在语义组中　

进行查询。本文提出的ＳＫＩＰ搜索机制将使用Ｋ一层迭代优　先选择的方法来取代ＧＥＳ和ＣＳＳ中的洪泛方式，同时，在　

整个拓扑结构的维护中，ＳＫＩＰ与ＧＥＳ所产生的开销相同．　

ＳＫＩＰ在查准率和查询开销上的表现要优于ＧＥＳ．而ＣＳＳ　

却要产生更大的虚拟节点开销。　

２相关研究　

一般来说，

Ｐ２Ｐ网络分为结构化Ｐ２Ｐ网络和无结构　ｇ　％　ｓ　；；　《ｇ　ｊ电信科学＿ｌ１　

Ｐ２Ｐ网络两种。对于结构化Ｐ２Ｐ网络来说，通常使用ＤＨＴ　

技术。例如ＣＡＮｔ”］、Ｐａｓｔｒｙｔ＝］￣Ｃｈｏｒｄｔ”１都是使用ＤＨＴ对资　

源进行搜索。ＤＨＴ方法尽管有着较高的搜索效率，但是它　

只能对关键字进行精确匹配，无法进行语义相关的查询。　

无结构Ｐ２Ｐ网络．例如Ｇｎｕｔｅｌｌａ，能够使用语义相关信息来　

进行资源搜索，但是其搜索的效率却比较低。　

当前无结构Ｐ２Ｐ网络被广泛应用，对于无结构Ｐ２Ｐ网　

络的搜索来说．主要有盲目搜索和非盲目搜索。盲目搜索　

算法，是不依靠任何提示信息而对其所有邻居节点或者部　

分邻居节点进行盲目的消息转发，直到满足停止的条件，　

如洪泛、ｒａｎｄｏｍ　ｗａｌｋ、ＢＦＳ（ｂｒｅａｄｔｈ　ｆｉｒｓｔ　ｓｅａｒｃｈ，宽度优先搜　

索）　等。非盲目搜索算法主要是路由索引［１５】的方式。　

为了减少洪泛的使用和提高搜索效率，一些搜索算法　

引入了历史查询信息。参考文献【ｌ６，１７］所述算法是基于兴　

趣定位的搜索算法，假设节点Ａ中有节点Ｂ需要的某一类　

内容，那么节点Ａ中的另外一些类的内容也是节点Ｂ所感　

兴趣的，在节点Ｂ发起搜索查询时，首先会将查询请求消息　

发送到节点Ａ中。参考文献『１８１提出了一种ＳＯＮ（ｓｅｍａｎｔｉｃ　

ｏｖｅｒｌａｙ　ｎｅｔｗｏｒｋ，语义覆盖网络）的搜索机制，对网络中的每　

个节点所包含的内容进行分类，并向全网络广播。每一个新　

加人的节点都需要广播，这样极大地增加了网络开销。　

还有一些Ｐ２Ｐ搜索机制，如ＳＥＴＳ（ｓｅａｒｃｈ　ｅｎｈａｎｃｅｄ　ｂｙ　

ｔｏｐｉｃ　ｓｅｇｍｅｎｔａｔｉｏｎ，话题分割搜索）　，它是采用超级节点方　

式，每个超级节点负责一类的内容，同时根据普通节点所　

含不同的内容连接到不同的超级节点上。ＳＥＴＳ的搜索路　

由分为全局路由和本地路由。全局路由就是在不同的超级　

节点之间进行路由．寻找不同类的内容：本地路由就是主　

要在某一个超级节点的范围内进行洪泛查询。由于采用超　

级节点的方式，因此单点失效是ＳＥＴＳ机制的一个致命问　

题。ＧＥＳｔ　】采用分布式的方法．并且通过语义相关性建立连　

接，形成语义组。在进行资源搜索时，ＧＥＳ使用ｂｉａｓｅｄ　ｗａｌｋ　算法找到目标语义节点，通过目标语义节点在语义组中进　

行洪泛查询。在ＧＥＳ的基础上，有研究人员提出了ＣＳＳｔ蚓．　

ＣＳＳ把每一个节点里面不同种类的内容再分成不同的虚　

拟节点，这样提高了查询的效率。但是却忽略了分割虚拟　

节点的开销。　

３　ＶＳＭ的背景介绍　

ＶＳＭＩ。ｑ是一种使用节点所包含的关键词来表示节点　

内容的方法。在ＶＳＭ方法中，使用关键词的矢量来表示每　一个文档或者查询消息．通过余弦内积和的计算方法来判　

断是否语义相关，对于一个文档Ｄ和查询消息Ｑ来说，其　

计算方法为：　

肌Ｌ（Ｄ，Ｑ）＝　，　（１）　ＥｎＱ　在式（１）中，ｔ是在文档Ｄ和查询消息Ｑ中同时出现　

的关键词＇，ｎ　是关键词ｔ在文档Ｄ中的权重，ｆＱ，　是关键词　

ｔ在查询消息Ｑ中的权重。　

４　ＳＫＩＰ设计　

在这一部分中，将详细阐述ＳＫＩＰ，分为节点矢量、拓　

扑构建和搜索协议３个子部分。　

４．１节点矢量　

对于每一个节点来说，把它的关键词按照权重抽取出　

来，形成节点矢量，使用节点矢量来表示这个节点的内容。　

使用ＶＳＭ来计算节点矢量间的语义相关度。首先，对于一　

个节点中的每一个文档按权重抽取出关键词，每一个关键　

词的权重根据该关键词在文档中出现的频率来确定：其　

次，对于一个节点来说，将节点中每个文档的带权重关　

键词加起来，便得到该节点的权重关键词．其计算方法　

为　：　，在这里，ｎ是该节点中文档数目，　是各个文档　ｉ＝１　相同的关键词。最后，把所有按照上述方法计算出来的带　

权重关键词组合在一起，便形成了该节点的节点矢量。　

以节点　和节点ｙ为例，它们的节点间语义相关度　

用节点矢量的计算方式如下：　

Ｅ　Ｌ（Ｘ，Ｙ）＝Ｌ，ｆｘ，　西，　（２）　ｔＥｘＹ　在式（２）中，ｔ是在节点　的节点矢量和节点ｙ的节　

点矢量中共同拥有的关键词　是关键词ｔ在节点Ｘ中的　权重　，　是关键词ｔ在节点Ｙ中的权重。如果通过式（２）　计算出来的相关度数值大于或等于某一个门限值。那么这　

两个节点被认为是语义相关，反之，则不相关。　

同样，可以用如下的式子来计算节点　和查询消息Ｑ　

之间的相关度：　

髓Ｌ（Ｘ，Ｑ）：　，　（３）　ｔ￣ｘ，Ｙ　４．２拓扑构建　每一个节点有两类邻居：一类是随机邻居，即是通过　

式（２）

计算出来的语义相关度数值小于设定的相关度门限　鼗　研燮与谱发　

值ＲＥＬ—ＴＨＲＥＳＨＯＬＤ；一类是语义邻居，即通过式（２）计算　

出来的语义相关度数值大于或等于设定的相关度门限值　

ＲＥＬ—ＴＨＲＥＳＨＯＬＤ。拓扑构建的目标有两个，一是把语义　

相关的节点通过语义连接组成语义组，二是每个节点保持　

一定数目的随机连接以便于发现新的语义连接。拓扑构建　

算法包含两个部分，一个是邻居发现部分。另一个是邻居　

维持部分。　

在邻居发现部分，起始节点会发起一个消息，该消息　

包含有本节点的节点矢量信息、语义相关度门限值　

ＲＥＬ—ＴＨＲＥＳＨＯＬＤ、ｍ（ｔｉｍｅ．ｔｏ．１ｉｖｅ，生命周期）等，该消息　

将随机地发送给其他节点。当消息到达一个节点后，该节　

点将会用式（２）计算与起始节点的语义相关度，然后把　

ｍ的数值减去１，再随机地发送出去，直到ｍ的数值　

等于０，这条消息将会被丢弃。　

ＭＡＸ＿ＳＥＭ＿ＬＩＮＫＳ是每个节点允许的最大语义邻居连　

接数，　ＮＤ＿ＬＩＮＫＳ是每个节点允许的最大随机邻居　

连接数。同时，每个节点有２个邻居候选ｃａｃｈｅ：一个是随　

机邻居ｃａｃｈｅ；一个是语义邻居ｃａｃｈｅ。根据式（２）计算出来　

的语义相关度数值。该节点将会被起始节点按照是否语义　

相关分别放人随机邻居ｃａｃｈｅ和语义邻居ｃａｃｈｅ中，起始　节点将会从语义邻居ｃａｃｈｅ中选择语义相关度最高的前　

ＭＡＸ．ｓＥＭ　ＬＩＮＫＳ个语义相关节点作为它的语义邻居：同　

时从随机邻居ｃａｃｈｅ中随机选择ＭＡ　一　ＮＯＬＩＮＫＳ个节　

点作为随机邻居。对于语义邻居，起始节点会将它们按照　

语义相关度的数值从高到低进行排序。　

在邻居维持部分，其任务就是从邻居候选ｃａｃｈｅ中选择新　

的邻居以及保持现有符合要求的邻居。每个节点会周期性　

地从它的语义邻居ｃａｃｈｅ中选择新的语义邻居来更新它　

的语义邻居连接，其算法为０ｄ印ｆ＿ｓｅ　ｅ动６０　０，需要注　

意的是，当语义相关度数值大于或等于门限锄ＥＬ—ＴＨＲＥＳＨＯＬＤ　的节点数大于最大语义邻居连接数ＭＡＸ＿ＳＥＭ＿ＬＩＮＫＳ时，　

起始节点将选择相关度最高的前ＭＡＸ＿ＳＥＭ＿ＬＩＮＫＳ作为　

新的语义邻居。同理，节点的随机邻居数也不能超过　

ＭＡＸ＿ＲＮＤ＿Ｌ　。节点的邻居重新连接后，每个节点根据　

语义相关度的数值从高到低对语义邻居进行排序。在图１　

中，给出了邻居拓扑调整与维持的伪代码。　

４．３搜索协议　

ＳＫＩＰ资源搜索定位查询算法的主要思想简言之就　

是：优先搜索查询语义相关度最高的那部分节点。　

当一个节点发起查询请求时，首先使用ｂｉａｓｅｄ＿ｗａｌｋ　ｆ）　

ｘ．ｕｐｄａｔｅ—ｓｅｒｅ—ｎｅｉｇｈｂｏｒ０／／Ｕｐｄａｔｅ　ｓｅｍａｎｔｉｃ　ｎｅｉｇｈｂｏｒｓ　Ｙ／／ａ　ｎｏｄｅ　ｔｈａｔ　ｉｓ　ｎｏｔ　ｉｎ　ｔｈｅ　Ｘ＇Ｓ　ｓｅｍａｎｔｉｃ　ｎｅｉｇｈｂｏｒ　ｃａｃｈｅ，ｂｕｔ　ｐｏｓｓｅｓｓｅｓ　ｔｈｅ　ｈｉｇｈｅｓｔ　ｒｅｌｅｖａｎｃｅ　／／ｄｅｇｒｅｅ　ｔｏ　ｎｏｄｅ　Ｘ　ｉｆ｛ＳｅｍＬｉｎｋ＜ＭａｘＳｅｍＬｉｎｋ｝　｛Ｘ　Ｃｏｎｎｅｃｔｓ　Ｙ　Ｙ　ｂｅｃｏｍｅｓ　ｏｎｅ　ｏｆ　Ｘ’Ｓ　ｓｅｍａｎｔｉｃ　ｎｅｉｇｈｂｏｒｓ　ＳｅｍＬｉｎｋ＋＋／／ｉｎｃｒｅｍｅｎｔ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ＳｅｍＬｉｎｋ　｝　ｅｌｓｅ　ｉｆ　ｒＹ　ｐｏｓｓｅｓｓｅｓ　ａ　ｒｅｌｅｖａｎｃｅ　ｄｅｇｒｅｅ　ｔｈａｔ　ｉｓ　ｈｉｇｈｅｒ　ｔｈａｎ　ａｎｙ　Ｘ’Ｓ　ｓｅｍａｎｔｉｃ　ｎｅｉｇｈｂｏｒ）　｛Ｚ／／ａ　ｓｅｍａｎｔｉｃ　ｎｅｉｇｈｂｏｒ　ｏｆ　Ｘ，ｔｈａｔ　ｐｏｓｓｅｓｓｅｓ　ｔｈｅ　ｌｏｗｅｓｔ　ｒｅｌｅｖａｎｔ　ｄｅｇｒｅｅ　Ｘ　ｄｉｓｃａｒｄｓ　Ｚ／／ｄｒｏｐ　Ｚ　ｆｒｏｍ　ｔｈｅ　ｓｅｍａｎｔｉｃ　ｎｅｉｇｈｂｏｒ　ｃａｃｈｅ　１Ｘ　ｃｏｎｎｅｃｔｓ　Ｙ／／ａｄｄ　Ｙ　ｉｎｔｏ　ｔｈｅ　ｓｅｍａｎｔｉｃ　ｎｅｉｇｈｂｏｒ　ｃａｃｈｅ　）　Ｘ．ｕｐｄａｔｅ—ｒａｎ—ｎｅｉｇｈｂｏｒ０／／Ｕｐｄａｔｅ　ｒａｎｄｏｍ　ｎｅｉ【ｇｈｂｏｒｓ　Ｙ／／ａ　ｎｏｄｅ　ｔｈａｔ　ｉｓ　ｎｏｔ　ｉｎ　ｔｈｅ　Ｘ　Ｓ　ｒａｎｄｏｍ　ｎｅｉ【ｇｈｂｏｒ　ｃａｃｈｅ．ｂｕｔ　ｐｏｓｓｅｓｓｅｓ　ｔｈｅ　ｌｏｗｅｓｔ　ｒｅｌｅｖａｎｃｅ　／／ｄｅｇｒｅｅｔｏ　ｎｏｄｅＸ　ｉｆ＇（Ｙ．ｃａｐａｃｉｔｙ＜＝Ｘ．ｃａｐａｃｉｔｙ）＆＆（ＲａｎＬｉｎｋ＜ＭａｘＲａｎＬｉｎｋ）　｛Ｘ　Ｃｏｎｎｅｃｔｓ　Ｙ　Ｙ　ｂｅｃｏｍｅｓ　ｏｎｅ　ｏｆ　Ｘ’Ｓ　ｒａｎｄｏｍ　ｎｅＪ　ｇｈｂｏ￣　ＲａｎＬｉｎｋ＋＋｜｜ｉｎｃｒｅｍｅｎｔ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ＲａｎＬｉｎｋ　｝　ｅｌｓｅ　ｉｆ　ｆＹ．ｃａｐａｃｉｔｙ　ｉｓ　ｈｉｇｈｅｒ　ｔｈａｎ　ａｎｙ　Ｘ’Ｓ　ｒａｎｄｏｍ　ｎｅｉｇｈｂｏｒ）　（Ｚ／／ａ　ｒａｎｄｏｍ　ｎｅ　Ｊ　ｇｈｂｏｒ　ｏｆ　Ｘ，ｔｈａｔ　ｐｏｓｓｅｓｓｅｓ　ｔｈｅ　ｈｉ【ｇｈｅｓｔ　ｄｅｇｒｅｅ　Ｘ　ｄｉｓｃａｒｄｓ　Ｚ／／ｄｒｏｐ　Ｚ　ｆｒｏｍ　ｔｈｅ　ｒＤｎｄｏｍ　ｎｅｉｇｈｂｏｒ　ｃａｃｈｅ　Ｘ　ｃｏｎｎｅｃｔｓ　Ｙ／／ａｄｄ　Ｙ　ｉｎｔｏ　ｔｈｅ　ｒａｎｄｏｍ　ｈｅ：ｉｇｈｂｏｒ　ｃａｃｈｅ　｝　图１