对等网二叉模型构造及搜索算法研究

摘 要: 针对P2P网络中资源查找及其自身存在的问题,本文提出了一种分布式二叉树索引模型,通过度量网络中结点属性相似性,对所有结点进行渐近分组,形成层次性逻辑二叉树覆盖网络。在信息搜索时,查询只路由到相关的结点上,减少了信息搜索时的平均搜索路径长度,从而改善搜索效率。

关键词: P2P网络 二叉树索引模型 搜索算法

1.引言

对等(又称P2P,Peer to Peer)模型由于其结构灵活和能够充分利用边缘资源等特点得到了迅速发展,其主要应用于分布环境下的资源共享,特别是文件共享,最典型的代表如BT和NaPster[1]。在文件共享类的应用中,对P2P拓扑(或称为P2P模型)和不同拓扑上资源定位算法的研究是较为关键的问题。目前P2P网络系统的搜索算法,一种是基于无结构的,一种是基于有结构的。有结构P2P网络有时被称为第二代对等网络,因为它有更好的可扩展性,更快的查找速度,控制层面上需要更少的额外开销,所以近年来逐渐成为人们研究的热点问题。但在实际网络中P2P网络强动态性决定了难以实现对等点之间的互相快速定位,且节点之间在计算、存储能力等方面的差异也造成了节点地位的不平等[2,3],因此这种按照逻辑网络设计的算法可能会增加网络带宽消耗和请求响应时间。

本文改进已有的研究成果,提出了分布式二叉树索引模型,将搜索限制在与查询内容相关的局部结点集中,为有组织的P2P系统提供了一种基于复杂查询条件的、能有效搜索数据对象的方法。

2.系统模型构造

2.1参数定义

定义1:P是组成对等网络的所有计算机的集合,peer∈P,是网络中的某台机器。

定义2:设P2P网络系统中所有结点集合为P={pi 1≤i≤N},数据对象集合为A={aj 1≤j≤M},属性值集合为W={Wk 1≤k≤L},M为数据对象的总数,L为属性值的总数,每个结点pi的数据对象集合记为A(pi)。

2.2二叉树搜索模型构造

在实际应用中,每个结点包含的数据对象具有特定的属性值t。从某个结点发出的搜索请求与特定的数据属性相关,也与发出请求的结点相关。将含有相似度高的属性值结点尽可能组织起来将有助于搜索。

信息瓶颈方法提供了一种好的相似性度量[4]。两个变量x1和x2之间的相似度,可由x1和x2条件下y的分布,即p对结点pi的数据对象集合A(pi)进行聚类,那么每个数据对象中属性值的条件分布为:p(w|a)=,其中n(w|a)为属性w在数据对象a中的出现次数。数据对象中两个属性tk和ts之间的相似性度量为:

预先设定的相似度阈值为R,根据P2P网络中的数据对象的属性相似性,将系统中结点逐步进行层次化的分组归类。最顶层包含整个系统,接下来的每一层都是对上一层的细化。定义细化后的结构为一棵二叉树,用T表示一棵二叉树,Sim(tk,ts)小于R,加入左子树,否则加入右子树。这样得到一种在概念特征上逐渐具体,用于对结点属性值进行渐近分组的层次性二叉树结构。

网络中每个节点都有一个160bit的ID值作为标识符。节点ID的生成,各种具体的应用软件有不同的实现方法,一般是选择一个不重复的值进行SHA-1计算,这个值可以是用户的IP地址,或者只是简单地随机生成。在网络中,所有节点都被当作二叉树的一个结点,并且每一个节点的位置都由其ID值的最短前缀惟一的确定。如果分别用0和1代表二叉树的左子树、右子树,那么一个结点标识符的前H位惟一地确定了一条从逻辑树根结点到叶子域的路径。具有相同路径的结点组成一个叶子域,彼此之间具有更多的相似属性。二叉逻辑树是一种基于节点属性的虚拟结构,和混合体系结构的P2P不同,逻辑树只是通过属性体现,不需要维护相应的连接。

3.搜索算法

3.1基于二叉树覆盖网络搜索算法

每个结点根据其标识属性与逻辑树上一个确定的叶子域相对应,一条从根结点到叶子的路径标志了该叶子域内成员的属性。从虚拟根节点出发到该虚拟叶子节点的边的序列即为节点P的路径,记作path(P),使用二进制数标识路径:节点P∈Peers,Path(P)=b1,…,bn,bi{0,1}。

如图1所示,虚线包含的部分就是不同的叶子域,共有四个域,由上到下各层的前缀分别为1,01,000,0010。

假设P表示逻辑树T的任意一个结点,h表示结点P的深度[5]。共同前缀相同的结点具有相同的深度,且深度是本结点在逻辑树中前缀的字符个数。如图1节点A、B具有共同的前缀100,前缀字符个数3,即它们的深度为3。

根据在小世界社会网络中成员之间的连接概率p是相对层次距离h的函数,p=e-αh,其中α=0.92。渐近分组的层次性二叉树结构,层次越深,结点连接的可能性越大,相似度越大。

3.2资源查询策略

若用户向结点pi提交查询信息Q时,设预先设定的相似度阈值为r,则整个搜索过程如下。

(1)pi检索本地数据对象,若与Q匹配,则向用户返回结果,一次查询结束。

(2)若本地数据中找不不到所查询的资源,则计算Q与上层父结点属性的相似度,然后选择相似度大于r的值,向对应的结点发送查询消息。依次路由,直到在TTL时间内找到的所要查询的信息,并返回给结点pi。如图2(1)实线箭头表示查询过程,虚线箭头表示返回查询结果过程。

(3)若pi的下层邻居结点中包含相似度大于r的属性值,则依次路由,直到在TTL时间内找到包含有与Q相似度大于r主题的结点,返回查询结果。如图2(2)所示,否则返回步骤(2)。

(4)包含Q的结点向pi返回查询结果。查询结果是结点IP地址的集合,这些结点的属性和查询相匹配。

二叉树覆盖网资源搜索伪代码

1)BW_Location (Node n,Request r)

//if n is the request?s initiator,Check n?s attributeList

2)Forword_Request (n.s, r) // Forword the Request to n?s father Peer

3)Match=Check_attrlist (s.w, r)

// if matched, Check_attrlist( ) returns the ID of the destination,else returns NULL

4)If Match

Check_Childlist (n.w,r)// Forward the request to destination

5)Else

6)Forword_Request(Match, r)

//Forward the request to the next hop

4.结语

本文提出了一种渐近分组的层次性逻辑二叉树结构,依据P2P网络中结点属性相似性,将其组织在一起构成逻辑覆盖网络。在信息搜索时,查询只路由到相关的结点上,从而改善了搜索效率。实验结果表明,属性相似逻辑二叉树网络,可以减少信息搜索时的平均搜索路径长度,提高搜索的成功率。

参考文献:

[1]FreeNet.freenet.省略.

[2]Geoffrey F.Peer-to Peer networks[J]Computing in science & engineering 2001,6,75- 77.

[3]Watts D J,Dodds PS,Newman ME J.Identity and search in social networks. Science, 2002, 296:1302~1305.

[4]傅向华,冯博琴.主题驱动的P2P分布式信息搜索机制研究[J]小型微型计算机系统,2006.4.

[5]冯国富,姜玉泉,张金城,顾庆,陈道蓄.一种基于多重覆盖的结构化P2P搜索[J].计算机科学,2008.35,(2).

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文