结构化覆盖网络CayDHT 的复杂搜索算法

doi:10.3969/j.issn.1000-565X.2011.10.015

华南理工大学学报（自然科学版） ›› 2011, Vol. 39 ›› Issue (10): 84-89.doi: 10.3969/j.issn.1000-565X.2011.10.015

结构化覆盖网络CayDHT 的复杂搜索算法

梁活民¹肖文俊² 魏文红³

1．华南理工大学计算机科学与工程学院，广东广州 510006;2．华南理工大学软件学院，广东广州 510006; 3．华南理工大学电子与信息学院，广东广州 510640

收稿日期:2011-04-07 修回日期:2011-04-15 出版日期:2011-10-25 发布日期:2011-09-01
通信作者: 梁活民(1980-) ，男，博士生，主要从事网络虚拟化、并行与分布计算研究． E-mail:iosliang@126.com
作者简介:梁活民(1980-) ，男，博士生，主要从事网络虚拟化、并行与分布计算研究．
基金资助:
国家自然科学基金资助项目( 61170313， 61103037) ; 博士后科学基金资助项目( 20110490883)

Complex Search Algorithm for Structured Overlay Network CayDHT

Liang Huo-min¹Xiao Wen-jun² Wei Wen-hong³

1. School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China; 2. School of Software Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China; 3. School of Electronic and Information Engineering,South China University of Technology,Guangzhou 510640,Guangdong,China

Received:2011-04-07 Revised:2011-04-15 Online:2011-10-25 Published:2011-09-01
Contact: 梁活民(1980-) ，男，博士生，主要从事网络虚拟化、并行与分布计算研究． E-mail:iosliang@126.com
About author:梁活民(1980-) ，男，博士生，主要从事网络虚拟化、并行与分布计算研究．
Supported by:
国家自然科学基金资助项目( 61170313， 61103037) ; 博士后科学基金资助项目( 20110490883)

摘要/Abstract

摘要： CayDHT 是一种基于Cayley 图的常数度结构化对等覆盖网络，对于精确的单关键字搜索效率非常高，但不支持不限定搜索形式的复杂搜索．通过分析CayDHT 的拓扑性质，提出了一种基于虚拟搜索树的复杂搜索算法VTCS．该算法无需维护额外的树结构，根据消息参数就可以获得下一跳节点的地址．理论分析表明该算法可以在O( logN) 的时间复杂度内完成无冗余消息的搜索．仿真实验比较了Flooding、RW 和VTCS，结果表明VTCS是较为合理的方案．

关键词: 覆盖网络, CayDHT, Cayley 图, 复杂搜索

Abstract:

CayDHT is a constant-degree structured peer-to-peer overlay network based on Cayley graph,and it is very efficient in accurate single keyword search but does not support complex searches with unrestricted form. In this paper,by analyzing the topological properties of CayDHT,a virtual tree-based complex search ( VTCS) algorithm is proposed,which needs no maintenance of the extra tree structure and can obtain the address of the next hop only according to the parameters inside the messages. Theoretical analyses indicate that the proposed algorithm can complete the search without redundant messages within O( logN) hops. Simulation results show that VTCS is more reasonable than Flooding and RW.

Key words: overlay networks, CayDHT, Cayley graph, complex search

梁活民肖文俊魏文红. 结构化覆盖网络CayDHT 的复杂搜索算法[J]. 华南理工大学学报（自然科学版）, 2011, 39(10): 84-89.

Liang Huo-min Xiao Wen-jun Wei Wen-hong. Complex Search Algorithm for Structured Overlay Network CayDHT[J]. Journal of South China University of Technology (Natural Science Edition), 2011, 39(10): 84-89.

[1]	宋玮赵跃龙. P-Grid覆盖网络的加速收敛构建算法[J]. 华南理工大学学报（自然科学版）, 2010, 38(11): 96-103.
[2]	谭伟姚锡凡. 基于ASP的制造网格资源发现模型[J]. 华南理工大学学报（自然科学版）, 2009, 37(8): 49-55，60.
[3]	魏文红, 肖文俊. 一种具有小世界特征的结构化P2P覆盖网络[J]. 华南理工大学学报（自然科学版）, 2009, 37(10): 66-72.
[4]	林伟伟齐德昱. 基于分层结构和树型覆盖网络的网格资源发现模型[J]. 华南理工大学学报（自然科学版）, 2008, 36(5): 6-12.

结构化覆盖网络CayDHT 的复杂搜索算法

Complex Search Algorithm for Structured Overlay Network CayDHT

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价