Solution to the problem of ant being stuck by ant colony routing algorithm

doi:10.1016/S1005-8885(08)60187-9

中国邮电高校学报(英文) ›› 2009, Vol. 16 ›› Issue (1): 100-105.doi: 10.1016/S1005-8885(08)60187-9

• Artificial Intelligence • 上一篇下一篇

Solution to the problem of ant being stuck by ant colony routing algorithm

赵晶,佟为明

School of Electrical Engineering and Automation, Harbin Institute of Technology, Harbin 150001, China

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-02-26
通讯作者: 赵晶

Solution to the problem of ant being stuck by ant colony routing algorithm

ZHAO Jing, TONG Wei-ming

School of Electrical Engineering and Automation, Harbin Institute of Technology, Harbin 150001, China

Received:1900-01-01 Revised:1900-01-01 Online:2009-02-26
Contact: ZHAO Jing

摘要/Abstract

摘要：

Many ant colony routing (ACR) algorithms have been presented in recent years, but few have studied the problem that ants will get stuck with probability in any terminal host when they are searching paths to route packets around a network. The problem has to be faced when designing and implementing the ACR algorithm. This article analyzes in detail the differences between the ACR and the ant colony optimization (ACO). Besides, particular restrictions on the ACR are pointed out and the three causes of ant being-stuck problem are obtained. Furthermore, this article proposes a new ant searching mechanism through dual path-checking and online routing loop removing by every intermediate node an ant visited and the destination host respectively, to solve the problem of ant being stuck and routing loop simultaneously. The result of numerical simulation is abstracted from one real network. Compared with existing two typical ACR algorithms, it shows that the proposed algorithm can settle the problem of ant being stuck and achieve more effective searching outcome for optimization path.

关键词:

ACR;algorithm,;ACO,;route;searching;mechanism,;network;routing,;network;topology;structure

Abstract:

Key words:

ACR algorithm;ACO;route searching mechanism;network routing;network topology structure

ZHAO Jing, TONG Wei-ming. Solution to the problem of ant being stuck by ant colony routing algorithm[J]. Acta Metallurgica Sinica(English letters), 2009, 16(1): 100-105.

参考文献

1. Dorigo M, Gambardella L M. Ant colonies for the traveling salesman problem. Bio Systems, 1997, 43(2): 73-81

2. Dorigo M, Caro G Di. Ant algorithms for discreteoptimization. Artificial Life, 1999, 5(3): 137-172

3. Colorni A. Ant system for job-shop scheduling. Belgian Journal of Operations Research Statistics and Computer Since, 1994, 34(1): 39-53

4. Maniezzo V, Dorigo M, Colorni A. The ant system applied to the quadratic assignment problem. Technical Report IRIDIA/94~28, Bruxelles, Belgium: University de Bruxelles, 1999: 769-778

5. Costa D, Hertz A. Ants can colour graphs. Journal of the Operational Research Society, 1997, 48(3): 295-305

6. Kuntz P, Layzell P, Snyers D. A colony of ant-like agents for partitioning in VLSI technology. Proceedings of the 4th European Conference on Artificial Life, Jul 28-31, 1997, Boston, MA, USA. Cambridge, MA, USA: MIT Press. 1997: 417-424

7. Bullnheimer B, Hartl R F, Strauss C. Applying the ant system to the vehicle routing problem. Proceedings of 2nd Meta-Heuristics, Jul 21-24, 1997, Sophia Antipolis, France. Boston, MA, USA: Kliwer, 1998: 109-120

8. Schoonderwoerd R, Holland O, Bruten J, et al. Ant-based load balancing in telecommunications networks. Adaptive Behavior, 1996, 5(2): 169-207

9. Caro G Di, Dorigo M. AntNet: distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research, 1998, 9: 317-365

10. Caro G Di, Dorigo M. Ant colonies for adaptive routing in packet-switched communications networks. Proceedings Fifth International Conference on Parallel Problem Solving from Nature, Sep 27-30, 1998, Amsterdam, The Nether land. Berlin, Germany: Springer-Verlag, 1998: 673-682

11. Put R van der. Routing in the faxfactory using mobile agents. Technical Report R&D-SW-98-276, KPN Research,1998

12. XU H, WU S Q. A distributed QoS routing based on ant algorithm for LEO satellite network. Chinese Journal of Computers, 2007, 30(3): 361-367 (in Chinese)

13. Huang H, Hao Z F, Wu C G, et al. The convergence speed of ant colony optimization. Chinese Journal of Computers, 2007, 30(8): 1344-1353 (in Chinese)

14. Ke L J, Feng Z R, Feng Y J. Ant colony optimazation algorithm with finite grade pheromone. Acta Automatica Sinica, 2006, 32(2): 296-303 (in Chinese)

15. Yan J F, Li W H, Du B. Hybird ant colony algorithm based on scale compression. Control and Decision, 2007, 22(9): 1061-1064 (in Chinese)

16. White T, Pagurek B, Oppacher F. ASGA: improving the ant system by integration with genetic algorithms. Proceedings of the 3rd Conference on Genetic Programming (GP/SGA ’98), Jul 22-25, 1998, Wisconsin, DC, USA. 1999: 610-617

17. Li L Y, Liu Z M, Zheng Z. A new dynamic distributed routing algorithm on telecommunication networks. Proceedings of International Conference on Communication Technology (WCC-ICCT’2000): Vol 1, Aug 21-25, 2000, Beijing, China. 2000, 849-852

[1]	Chai Rong, Duan Xiaofang, Wang Lixuan. GNN-based temporal knowledge reasoning for UAV mission planning systems[J]. 中国邮电高校学报(英文版), 2024, 31(1): 12-25.
[2]	Zheng Guangming, Zhou Tianle, Lu Haiwei, Long Yifei, Bai Jing. Study on high-order frequency selective surface with interdigital capacitance loading[J]. 中国邮电高校学报(英文版), 2024, 31(1): 57-63.
[3]	许杏桃, 陶加贵. Parameter optimization of complex network based on the change-point identification [J]. 中国邮电高校学报(英文版), 2023, 30(6): 22-29.
[4]	张思聪, 戴建卓, 黄文静, 糜欣平. Behavioral finance between the spot and futures markets based on multilayer network [J]. 中国邮电高校学报(英文版), 2023, 30(6): 82-88.
[5]	赵海英郭轩 . Pointer-prototype fusion network for few-shot named entity recognition[J]. 中国邮电高校学报(英文版), 2023, 30(5): 32-41.
[6]	Feng Yuting, Gong Haobing, Hao Xiaojing, Gao Hui, Guo Xiangming. Machine-learning based ocean atmospheric duct forecasting: a hybrid model-data-driven approach[J]. 中国邮电高校学报(英文版), 2023, 30(4): 1-9.
[7]	Zhang Xijun, Zhang Guannan, Zhang Xianli, Zhang Hong, Zhang Minghu. Medium and long-term traffic flow prediction based on ACNN-Trans model[J]. 中国邮电高校学报(英文版), 2023, 30(4): 21-32.
[8]	Duan Li, Chen Lin, Luo Bing. Surveys on the application of neural networks to event extraction[J]. 中国邮电高校学报(英文版), 2023, 30(4): 43-54.
[9]	Yin Sihan, Li Yalei, Liu Xiaoping, Cui Xu, Wang Huapeng. Transformer fault diagnosis based on relational teacher-student network [J]. 中国邮电高校学报(英文版), 2023, 30(3): 41-54.
[10]	Du Rong, Chen Shudong, Li Weiwei, Zhang Xueting, Wang Xianhui, Ge Jin. Data augmentation via joint multi-scale CNN and multi-channel attention for bumblebee image generation [J]. 中国邮电高校学报(英文版), 2023, 30(3): 32-40.
[11]	Guo Hui, Zhao Xuehui. Maximum throughput design of wireless powered communication network with IRS-NOMA based on user clustering [J]. 中国邮电高校学报(英文版), 2023, 30(3): 55-64.
[12]	Zhang Luying, Liu Xiaokai, Li Zhao, Xu Fangmin, Zhao Chenglin. Prediction based dynamic resource allocation method for edge computing first networking [J]. 中国邮电高校学报(英文版), 2023, 30(3): 78-87.
[13]	韩子文张治郭宇. Gain and phase errors active calibration method based on neural network for arrays with arbitrary geometry[J]. 中国邮电高校学报(英文版), 2023, 30(2): 8-17.
[14]	杨亚涛, 张若菁, 董辉, 马英杰, 张筱薇. WBZUC: novel white-box ZUC-128 stream cipher[J]. 中国邮电高校学报(英文版), 2023, 30(2): 96-106.
[15]	Guo Xiangbo, Wang Jian, Huang Mengjie, Wang Minghui, Yang Jian, Yu Yongtao. Deep knowledge tracking algorithm based on forgetting law[J]. 中国邮电高校学报(英文版), 2023, 30(1): 17-27.

Solution to the problem of ant being stuck by ant colony routing algorithm

Solution to the problem of ant being stuck by ant colony routing algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价