基于蚁群优化算法的Chord模型

doi:10.3969/j.issn.1000-3428.2012.04.033

计算机工程 ›› 2012, Vol. 38 ›› Issue (04): 100-103. doi: 10.3969/j.issn.1000-3428.2012.04.033

基于蚁群优化算法的Chord模型

张建伟，刘思，李朝阳，蔡增玉

(郑州轻工业学院计算机与通信工程学院，郑州 450002)

收稿日期:2011-05-17 出版日期:2012-02-20 发布日期:2012-02-20
作者简介:张建伟(1971－)，男，副教授，主研方向：宽带信息网络，网络安全；刘思、李朝阳，硕士研究生；蔡增玉，讲师
基金资助:
国家“973”计划基金资助项目(2007CB307102, 2007CB30 7100)；河南省基础与前沿技术研究计划基金资助项目(0823004102 80)

Chord Model Based on Ant Colony Optimization Algorithm

ZHANG Jian-wei, LIU Si, LI Chao-yang, CAI Zeng-yu

(School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China)

Received:2011-05-17 Online:2012-02-20 Published:2012-02-20

摘要/Abstract

摘要： 提出一种具有物理拓扑匹配能力的Chord模型(Ant-Chord)，用以存储网络标识间的映射信息。该模型将整个Chord环中的存储节点看成一个旅行商问题(TSP)，利用蚁群优化算法对TSP问题进行快速求解，用得到的解构建Chord环，并通过洛阳铲法对Chord环的路由跳数进行优化。Ant-Chord模型实现简单，对原始Chord模型改动不大，路由表的额外存储开销也较小。仿真结果表明，与同类Chord模型相比，Ant-Chord在资源发现的平均路由跳数、时延方面均有明显优势。

关键词: 网络标识分离, Chord模型, 蚁群优化算法, 旅行商问题, 物理拓扑匹配

Abstract: This paper proposes a Chord model(Ant-Chord) which has an ability of physical topology matching to store the mapping information of identifiers. The ideas of Ant-Chord is to regard the storage nodes in the whole Chord as a TSP problem and solve the TSP problem quickly by using the ant colony algorithm, then to build the Chord with the obtained Traveling Salesman Problem(TSP), and proposes a method which called Luoyang Shovel Method(LSM) to optimize the Ant-Chord’s routing hops. The model is simple and easy to implement, which has small changes within the original Chord model and little extra overhead cost in the routing table storage. Simulation results show that Ant-Chord has obvious advantages in average routing hops and delay in comparison with other Chord models.

Key words: network identifier separation, Chord model, Ant Colony Optimization(ACO) algorithm, Traveling Salesman Problem(TSP), physical topology matching

中图分类号:

TP393

张建伟, 刘思, 李朝阳, 蔡增玉. 基于蚁群优化算法的Chord模型[J]. 计算机工程, 2012, 38(04): 100-103.

ZHANG Jian-Wei, LIU Sai, LI Chao-Yang, CA Ceng-Yu. Chord Model Based on Ant Colony Optimization Algorithm[J]. Computer Engineering, 2012, 38(04): 100-103.

http://www.ecice06.com/CN/Y2012/V38/I04/100

参考文献

[1] Mathy L, Lancaster U, Iannone L, et al. LISP-DHT: Towards a DHT to Map Identifiers onto Locators[EB/OL]. (2008-05-12). http://inl.info.ucl.ac.be/system/files/draft-mathy-lisp-dht-00.txt.
[2] Luo Hongbin, Qin Yajuan. A DHT-based Identifier-to-locator Mapping Approach for a Scalable Internet[J]. IEEE Trans. on Parallel and Distributed Systems, 2009, 20(12): 1790-1802.
[3] Zhang Jianwei, Zhan Xiaosu, Zou Dongyao. A Network Locality Aware Algorithm Based on Identity Mapping[C]//Proc. of the 2nd International Conference on Signal Processing Systems. Dalian, China: [s. n.], 2010.
[4] 张宏科, 苏伟. 新网络体系基础研究一体化网络与普适服务[J]. 电子学报, 2007, 35(4): 593-598.
[5] 董平, 秦雅娟, 张宏科. 支持普适服务的一体化网络研究[J]. 电子学报, 2007, 35(4): 599-606.
[6] 陈沅涛, 吴海珍. 基于Chord的动态多路由算法[J]. 计算机工程, 2010, 36(4): 97-98, 102.
[7] Dorigo M, Gambardella L M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Trans. on Evolutionary Computation, 1997, 1(1): 53-66.
[8] Wu Weiyu, Chen Yang, Zhang Xinyi, et al. LDHT: Locality-aware Distributed Hash Tables[C]//Proc. of the International Conference on Information Networking. Busan, Korea: [s. n.], 2008.
[9] Dabek F, Li J, Sit E, et al. Designing a DHT for Low Latency and High Throughput[C]//Proc. of the 1st Symposium on Networked System Design and Implementation. [S. l.]: IEEE Press, 2004: 85-98.
[10] Feng Hong, Li Minglu. PChord: Improvement on Chord to Ach- ieve Better Routing Efficiency by Exploiting Proximity[C]//Proc. of International Conference on Distributed Computing Systems Workshops. [S. l.]: IEEE Press, 2005: 806-811.
[11] Xiong Jiping, Zhang Youwei, Hong P, et al. Chord6: IPv6 Based Topology-aware Chord[C]//Proc. of the Joint International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Services. Papeete, Tahiti: [s. n.], 2005: 19-23.
[12] 王双, 禹继国. 无结构P2P网络中的混合式搜索方法[J]. 计算机工程, 2011, 37(7): 109-111.
[13] Magoni D. Nem: A Software for Network Topology Analysis and Modeling[C]//Proc. of MASCOTS’02. [S. l.]: IEEE Computer
Society, 2002: 364-371.
[14] Magoni D, Pansiot J J. Internet Topology Modeler Based on Map Sampling[C]//Proc. of the ISCC’02. Taormina, Italy: IEEE Press, 2002: 1021-1027.

[1]	宋佳艳, 苏圣超. 基于改进蚁群优化算法的自动驾驶多车协同运动规划[J]. 计算机工程, 2022, 48(11): 299-305,313.
[2]	赵启超, 杨余旺, 谢勇盛, 汤小芳, 李操. 密集MANET下MPR的改进蚁群优化算法研究[J]. 计算机工程, 2021, 47(4): 135-140,172.
[3]	王若愚, 陈勇全. 基于强化学习的旅行商问题解构造方法[J]. 计算机工程, 2020, 46(11): 293-300.
[4]	赵琴,陈健,张月琴. 基于逐次适应蚁群优化算法的个性化微学习推荐[J]. 计算机工程, 2018, 44(2): 238-243,276.
[5]	彭云建,黄璐. 基于蚁群优化算法的ReInForM动态路由[J]. 计算机工程, 2017, 43(8): 138-143.
[6]	沈记全,孔祥君. 基于改进蚁群优化算法的QoS区间数服务组合方法[J]. 计算机工程, 2016, 42(7): 181-188,193.
[7]	耿志强,邱大洪,韩永明. 基于混沌的MMAS算法及其在旅行商问题中的应用[J]. 计算机工程, 2016, 42(3): 192-197.
[8]	李贵华,黄敏. 考虑多种运输方式的第四方物流路径优化算法[J]. 计算机工程, 2015, 41(3): 273-277.
[9]	吕金秋,游晓明,刘升. 基于α-邻近的改进蚁群算法[J]. 计算机工程, 2015, 41(2): 184-188.
[10]	郭小燕，王联国，代永强. 基于分段混合蛙跳算法的旅行商问题求解[J]. 计算机工程, 2014, 40(1): 191-194,198.
[11]	李明, 曾建潮, 何小娟. 基于贝叶斯统计推断的离散分布估计算法[J]. 计算机工程, 2013, 39(8): 249-252.
[12]	王会颖, 倪志伟, 吴昊. 求解多维背包问题的MapReduce蚁群优化算法[J]. 计算机工程, 2013, 39(4): 248-253.
[13]	龚跃，吴航，赵飞. 基于非均匀变异算子的改进蚁群优化算法[J]. 计算机工程, 2013, 39(10): 196-199.
[14]	牟廉明. 求解子旅行商问题的改进蚁群算法[J]. 计算机工程, 2012, 38(23): 190-193,197.
[15]	陈成栋, 陈华平, 朱颀, 李小林. 两阶段流水车间批调度问题的蚁群优化算法[J]. 计算机工程, 2012, 38(19): 137-141.

选择文件类型/文献管理软件名称

选择包含的内容

基于蚁群优化算法的Chord模型

Chord Model Based on Ant Colony Optimization Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于蚁群优化算法的Chord模型

Chord Model Based on Ant Colony Optimization Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价