ML-Chord中基于动态查询的查询策略

孙娟娟，禹继国

（曲阜师范大学 计算机科学学院，山东 日照 276826）

0 引言

无结构P2P网络一般采用洪泛法进行资源定位。该方法在查询受欢迎文件时非常有效，但在查询稀有文件时效率不高；结构化P2P网络一般利用分布式哈希表来定位资源。该方法在查询稀有文件时比较有效，但在进行多关键字查询或者区间查询时效率比较低。鉴于它们的优缺点，P2P网络中的混合查询机制引起了越来越多研究者的关注。

文献[1]将现有P2P混合查询策略分成两类：第一类是基于检测的简单混合策略。该策略首先执行洪泛，如果在一个预定的时间内没有返回足够多的查询结果，就将其作为一个DHT再次发起查询过程，直到查询内容最终被定位到；第二类是采用闲聊方式利用收集到的聚集信息来估算文件的受欢迎程度，并且通过在相关文件数目上设定阈值以确定是采用洪泛还是采用DHT。

1 相关工作

动态查询是无结构P2P网络中采用的查询技术，该方法使用较少的节点就能够到达目标节点。查询发起者在一个小的TTL值内通过“刺探”过程将查询信息发送给网络中的一些节点并由此开始查询过程。“刺探”查询的目标是对定位到的资源评估其受欢迎程度[2]。

文献[3]中，Lu等在Chord[4]的基础上，提出了多层次P2P资源共享模型 ML-Chord。该模型中的所有资源基于一个选择的本体被分成不同的类别，每一个类别对应一个覆盖层；同时选出能力强的节点作为桥节点连接到所有Chord环上，所有桥节点组成一个Chord环。

动态查询是在无结构P2P网络中采用的查询技术，采用这种查询方法可以使用较少的节点就可以达目标节点。查询发起者在一个小的 TTL内通过把查询信息发送给网络中的一些节点开始搜索过程。这个“刺探”查询的目标是对定位到的资源。这个“刺探”查询的目标是对定位到的资源评估其受欢迎程度。一种结合动态查询的搜索算法应用在了无结构P2P网络中[5],将动态查询应用到无结构的洪泛[6]比文献[5]中的查询方法取得了更好的搜索效率。

文献[5]中，Talia等在Chord上将动态查询技巧与文献[7]提出的有效广播算法结合。查找过程是首先进行一个刺探阶段，如果在刺探阶段已得到足够多的查询结构，则终止查询。否则，根据刺探阶段得到的数据估算文件的受欢迎程度作为调整洪泛范围的依据。

2 ML-Chord中动态查询的执行

2.1 ML-Chord的结构

图1 ML-Chord的结构示意

若系统中有C个类别覆盖层，则整个逻辑覆盖网中有T=C+1个逻辑覆盖层。图1中所示的节点和虽然标识符不同，但它们是同一个节点，即相同的节点位于两个覆盖层上，这也意味着该节点需要维护两套路由表。

2.2 动态查询过程

由于P2P用户常在本地空间上存储相似文件，如图2所示：查询与a和b相关的文件，与a有关的文件广泛存储在系统中的节点上，而与b有关的文件之存储在少量节点上，若按照计算得到。然而，Pa的值应大于Pb的值，由此出现了文件受欢迎程度误差偏大的情况。

图2 系统中文件分布举例

2.3 ML-Chord中的动态查询算法

对于给定的一棵二项式树，它的性质：①Bi中的节点数是2i；②Bi的深度为i；③Bi中在l层上的节点数目通过二项式系数及动态查询算法需要用到的参数得到。表1给出了相关的参数定义。

表1 参数定义

首先，将当前查找到的资源数目Rc赋值为0，当接收到一个查询应答时Rc的数目就会增加1，集合U初始化为节点中存储的与资源 R属于同一类别的覆盖层的路由表内所有的独一无二的指针数。将Hi设置为N(U), N(U)与网络中可以查询到的主机数目相一致，从集合U中选择出第一个需要访问的子集V,集合U随之做相应更新。

3 性能分析

现在考虑一般情况：假设匹配的资源在节点间均匀分布，在刺探阶段可以得到资源受欢迎程度的准确估计，大多数的查询只需要 2次迭代（其中包括刺探阶段）。这种情况下，最大的查询时间是刺探查询时间和覆盖最深子树的迭代查询时间，即TS=TH×((L+2)+(DU+2))，又Du=log2(N-1)，得到同理，若普通节点只加入一次覆盖层且所有节点在覆盖层上均匀分布，查询的时间复杂度为

4 结语

这里将动态查询部署在多层次结构化 P2P系统ML-Chord上，节点根据查询资源的类别选择执行动态查询，或者由能力更高的桥节点代为执行。动态查询的优点在于允许执行任意类型的查询，可以根据文件的受欢迎程度调整查询范围，减少了网络负载。更改后的文件受欢迎程度的简单估算方法提高了计算准确性，有效地提高了查询效率。

[1] CHEN Hanhua, JIN Hai, LIU Yunhao, et al.Difficulty-aware Hybrid Search in Peer-to-peer Networks[C].USA:IEEE,2009:71-82.

[2] VLADIMIR VISHNEVSKY, ALEXANDER SAFONOV, MIKHAIL YAKIMOV, et al.Alexander D.Gelman.Scalable Blind Search and Broadcasting over Distributed Hash Tables[J].Computer Communications, 2008, 31(02): 292-303.

[3] LU Juilin, HUANG Yungfa, LU Shuchiu.ML-Chord: A Multi-Layered P2P Resource Sharing Model[J].Network and Computer Applications, May 2009, 32(03):578-588.

[4] STOICA I, MORRIS R, KARGER D, et al.Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[C].[EB/OL].(2006-11-24) [2009-12-23].http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf.

[5] FISK A.Gnutella Dynamic Query Protocol v0.1[EB/OL].(2003-05-12) [2009-12-23]. http://www9.limewire.com/developer/dynamic_query.html.

[6] JIANG H, JIN S.Exploiting Dynamic Querying Like Flooding Techniques in Unstructured Peer-to-peer Networks[C].USA:IEEE,2005:1121-1123.

[7] SAMEH EL A, LUC ONANA ALIMA, PER BRAND, et al.Efficient Broadcast in Structured P2P Networks[EB/OL].(2009-11-10)[2009-12-23].http://soda.swedish-ict.se/2811/

[8] PAOLO TRUNFIO, DOMENICO TALIA.Implementing Dynamic Querying Search in k-ary DHT-based Overlays[C].[s.l.]:Computer Science, 2008:275-286.

[9] DOMENICO TALIA, PAOLO TRUNFIO.Dynamic Querying in Structured Peer-to-Peer Networks, Submitted for Publication[EB/OL](2008-11-02)[2009-12-23].Available at:http://grid.deis.unical.it/papers/pdf/DQ-DHT.pdf.