基于k-完美差异图的超节点拓扑结构构造

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于k-完美差异图的超节点拓扑结构构造范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

收稿日期:2011-02-28;修回日期:2011-04-16。基金项目:国家自然科学基金资助项目（60973031; 60973127）。

作者简介:谭义红（1971-）,男, 湖南茶陵人,副教授,博士研究生，CCF会员,主要研究方向:P2P网络、信息检索; 陈治平（1971-），男，湖南湘潭人, 副教授，博士，主要研究方向：机器学习、信息检索； 李学勇（1972-）,男,湖南邵阳人, 教授,博士研究生,主要研究方向:网络分析、信息检索; 林亚平（1955-）,男，湖南邵阳人,教授,博士生导师,博士,主要研究方向:传感器网络、信息检索。

文章编号:1001-9081（2011）08-02021-04doi:10.3724/SP.J.1087.2011.02021

（1.长沙学院 信息与计算科学系，长沙410003; 2.湖南大学 计算机与通信学院，长沙410082）

（）

摘 要:在超节点网络中，超节点拓扑结构及其动态维护和搜索路由机制,是影响网络性能和搜索效率的关键因素之一。在完美差异图（PDG）的基础上,提出了一种新的k-PDG结构,并利用该结构,建立了超节点网络――KPDGN,给出了KPDGN的动态维护和搜索路由机制。分析和模拟结果表明: KPDGN具有常数度数和固定邻接点特性,减少了查询所产生的带宽消耗,降低了拓扑构造和修复成本。

关键词:超节点拓扑结构；完美差异图；动态拓扑维护；搜索路由机制

中图分类号: TP393.02文献标志码:A

Super-peer topology construction based on k-perfect difference graph

TAN Yi-hong1,2, CHEN Zhi-ping1, LI Xue-yong1, LIN Ya-ping2

（1. Department of Information and Computing Science, Changsha University, Changsha Hunan 410003, China;

2. School of Computer and Communication, Hunan University, Changsha Hunan 410082, China）

Abstract: In the super-peer network, the super-peer topology structure and its mechanism of dynamic maintenance and search routing are important factors affecting network performance and search efficiency. In this paper, a new structure named k-Perfect Difference Graph （PDG） was proposed by analyzing the characteristics and the deficiencies of PDG, new Super-peer Network based on k-PDG （KPDGN） was constructed, and then the mechanism of dynamic maintenance and search routing was presented in KPDGN. The analysis and simulation results show that compared with current supper-peer topology, KPDGN has good performance with constant degree and fixed adjacent nodes, which reduces the bandwidth consumption during searching and the cost of topology construction and maintenance.

Key words: super-peer topology structure; Perfect Difference Graph （PDG）; dynamic topology maintenance; search routing mechanism

0 引言

近年来,P2P技术广泛应用于分布式信息检索等领域。为了解决原有P2P系统低带宽节点瓶颈问题,提高检索结果质量,增强网络的可扩展性,人们在无结构化P2P的基础上,构建了超节点网络（super-peer network）［1］1,［2-4］。在超节点网络中,所有节点根据性能的高低,分成超节点（super-peer）和普通节点（client peer）。超节点作为普通节点的服务器,负责网络的管理和维护,查询处理和路由等操作。因此超节点的拓扑结构是影响网络稳定和搜索效率的重要因素之一。

在早期出现的超节点网络［1］1,［5］中,超节点间采用无严格组织的非结构化拓扑结构,文档索引集中存放在超节点,路由传递具有随意性。其优点是支持模糊查询,系统容错好,节点失效影响小；缺点是在搜索时需通过泛洪（flooding）或随机漫步（random walk）等盲目搜索方式进行,产生的查询消息量大或查询效率低。

Li等人［6］597-601采用完美差异图（Perfect Difference Graph, PDG）技术组织超节点,构造超节点拓扑结构,既具有超节点非结构化拓扑结构的优良特性（如支持模糊查询等）,同时克服了此结构的不足（如提高了查询效率,减少了搜索所产生的查询消息量）,但缺点是不适应动态网络环境,拓扑结构动态维护复杂。

本文对PDG进行改进,提出了一种新颖的k-PDG拓扑结构,并利用该结构,建立了一种新的超节点拓扑网络（Super-Peer Network based on k-PDG, KPDGN）。分析和模拟结果表明:与现有超节点拓扑结构相比,除具有支持模糊查询、减少搜索所产生的查询消息量外,在动态适应性方面,KPDGN能更好地降低超节点失效对拓扑产生的影响,在性能上,KPDGN具有更小的拓扑构造和失效修复成本。

1 相关工作

为了提高非结构化超节点拓扑的搜索效率,文献［2,7-8］根据节点共享文档的语义相关性,将语义相似的普通节点和超节点连接构建语义组。当普通节点提交与语义组语义相关的查询请求时,由语义组超节点完成查询操作,而不需将查询请求转发到其他超节点。但若在语义组内不能得到满意的查询结果,则仍需通过泛洪方式将查询请求广播到其他超节点。文献［9］提出每个超节点存储所有语义组的语义特征索引,查询请求可直接提交到更有可能获取查询结果的超节点,但超节点每次更新数据或加入退出网络时,需将相关索引信息发送到所有超节点,存在网络带宽资源消耗大和网络动态维护困难等问题。

由于非结构化超节点拓扑的无规则性,超节点的连接关系缺乏全局性,不能按指定路由路径进行信息转发,搜索具有盲目性,因此有研究者尝试采用传统的网络拓扑图来构建超节点拓扑结构。比如,SUPS［10］利用实体―关系（Entity Relationship, ER）模型来建立度数平衡的低直径随机图（random graph）的超节点拓扑结构,节点度数为O（n log n）。在文献［6］602中,每个节点的度数为O（）。虽然上述结构减少了网络直径,但超节点的度数和连接对象随着网络规模的变化而变化,当网络中超节点加入退出时,所有超节点需不断更新和邻接信息。

文献［11］利用tree和ring结构构建拓扑结构,以提高搜索效率和识别稀缺资源（rare resources）。但作者给了很多理想假设,如超节点有很高的性能,能连接足够多普通节点,超节点是静态的等,这与现实应用环境相差很大。另外,所采用的ring结构使超节点只具有两个邻居节点,节点失效对网络影响较大。

文献［12］中提出了一种新的常数度数的P2P系统,它模仿立方体互连圈的拓扑结构,每个节点只需要维护Ο（1）个邻居。模拟实验表明,在网络规模较大和节点出入频繁的动态P2P网络中,该系统具有较好的性能。但缺点在于,这种基于分布式hash表进行数据定位的系统不支持模糊查询,这是因为不同的资源标识产生不同ID标识。

本文提出的k-PDG拓扑结构,与已有网络拓扑图相比,具有常数度数、固定邻居等特性,使得拓扑结构动态维护简单。

2 背景知识

定义1 PDG［6］596是一种基于完美差异集（Perfect Difference Set, PDS）无向互联网络图,记为PDG（δ）。它包含Nδ2+δ+1个节点,编号为0,1,…,N-1,其中δ为PDS的元素个数。在PGD中,任意节点i的邻接点有（i±sj）mod N（1≤j≤δ）个,sj是PDS{s1,s2,…,sj}中元素。节点度数d2δ,网络直径D2。

表1列出了部分节点数N及其δ和PDS元素（sj）之间的相关性。

表1 节点数N、δ和PDS元素（sj）之间的相关性

图1是基于PDS元素{1,4,14,16}的PDG（4）图,包含N21个节点,编号依次为0,1,…,20, δ4, d8, D2。每个节点有8个邻接点,例如0号节点有（0±1）mod 21, （0±4）mod 21, （0±14）mod 21, （0±16）mod 21等8个邻接点。

3 KPDGN

3.1 KPDGN模型定义

定义2 将k个相同结构的PDG（2）连接成的图,称为k-PDG拓扑结构。PDG（2）是定义1中取δ2的PDG（δ）图。构造方式如下。

1）每个PDG（2）中节点序号为0～6,按照定义1方式连接。k个PDG（2）图按如下方式连接:第j个PDG（2）与第（j±1）mod k个PDG（2）图内序号相同的节点相连接（j0,1,…,k-1）。

2）k-PDG节点编码。k-PDG中任意节点A的编码两部分（a0,a1）,其中a0是PDG（2）的序号,0≤a0≤k-1;a1是PDG（2）内的节点序号,0≤a1≤6,记为:A（a0a1）或（a0,a1）。若两节点的a0相同,则表示两节点处在同一个PDG（2）中。

3）k-PDG邻接点。对于任意节点A（a0a1）,其邻接点共有6个,即（a0,（a1±1）mod 7）,（a0,（a1±3）mod 7）,（（a0±1）mod k, a1）。为了描述方便,本文将6个邻接点归为4类:内前驱、内后继、外前驱、外后继。其中:内前驱邻接点为（a0,（a1+1）mod 7）,（a0,（a1+3） mod 7）;内后继邻接点为（a0,（a1-1）mod 7）,（a0,（a1-3）mod 7）;外前驱,外后继邻接点分别为（（a0+1） mod k, a1）和（（a0-1） mod k, a1）。

图1 PDG（4）拓扑结构示意图

k-PDG网络中超节点按k-PDG进行组织,如图2所示（由于篇幅有限,只画出部分节点的外前驱和外后继邻接点）。每个PDG（2）代表一个语义组,图中包含3个PDG（2）图,即k3,N21。每个PDG（2）包含7个超节点,每个超节点都有唯一的编码（a0a1）和邻接点。如A（00）有A0（01）、A1（03）、A2（06）、A3（04）、A4（10）、A5（20）共6个邻接点。

图2 k-PDG拓扑结构示意图

定义3 KPDGN模型定义为三元组M（V,E,I）。其中：V为节点集,包括如图2所示的超节点和普通节点。超节点负责网络的查询和路由任务,并为普通节点建立和索引,普通节点通过超节点进行查询。E为边集,包括如图2所示的超节点间的边和超节点与普通节点间的边。超节点间的边由k-PDG拓扑结构中节点邻接关系组成,是路由的核心部分。超节点与普通节点间的边由超节点与普通节点连接关系组成,是根据语义相似性建立连接。I为文档索引,包括普通节点的本地文档索引和超节点为普通节点建立的文档索引。

定义4 超节点定义为五元组SP（ID,IP,C,L,R,I）。其中：ID为超节点编码,IP表示超节点IP地址,C表示超节点最大连接普通节点的数量,L表示超节点当前连接普通节点的数量,R表示邻接表,I表示连接普通节点的相关信息及文档索引。

定义5 普通节点定义为六元组CP（ID,IP,C,T,S,L）。其中：ID表示普通节点编码,IP表示普通节点IP地址,C表示普通节点的容量,T表示普通节点的类型。普通节点分为两类:一类是一般普通节点；另一类是候选超节点。每个普通节点加入网络时,根据容量被确定是否作为候选超节点。其中:1表示是候选超节点,0表示是一般普通节点。S表示连接超节点的相关信息,L表示共享文档索引。

定义6 超节点SP的邻接表定义为R{〈neiSP,realSP,SPIP,Status,neivSeq〉}。其中：neiSP表示SP邻接点的编码;realSP表示neiSP是否为虚拟超节点,如果是则为1,否则为0；SPIP存储IP地址,如果realSP为1则存储的是虚拟超节点的IP地址,否则表示存储neiSP的IP地址;Status表示neiSP的状态,取值1和0,1表示neiSP有效,0表示neiSP无效;neivSeq表示neiSP为SP邻接点的序号,取0～5。以图2为例,超节点SP（00）的邻接表为{〈（01）,1,IP,1,0〉,〈（03）,1,IP,1,1〉,〈（06）,1,IP,1,2〉,〈（04）,1,IP,1,3〉,〈（10）,1,IP,1,4〉},〈（20）,1,IP,1,5〉}。