Acta Metallurgica Sinica(English letters) ›› 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

赵晶,佟为明   

  1. 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   

  1. 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

摘要:

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:

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.

Key words:

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