School of Information Science and Engineering, Guangxi University for Nationalities, Nanning, China; Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Nanning, China

---

Abstract—Quality of Service (QoS) anycast routing problem is a nonlinear combination optimization problem, which is proved to be a NP-complete problem, at present, the problem can be prevailingly solved by heuristic methods. Ant colony optimization algorithm (ACO) is a novel random search algorithm. On the one hand, it does not depend on the specific mathematical description, on the other hand, which has the advantages of robust, positive feedback, distributed computing. Consequently, ACO has been widely used in solving combinatorial optimization problems. However, the basic ACO has several shortcomings that the convergence rate is slow and it’s easily to stuck in local optimum for solving QoS anycast routing problem. In this paper, the basic ACO has been improved, firstly, iteration operator is introduced in the node selection, which can make the node selection strategy is adjusted dynamically with the iteration. Secondly, pheromone evaporation coefficient is adjusted adaptively according to the distribution of ant colony. Finally, according to the evolutionary speed of the population, the premature convergence is estimated. The mutation and secondary ant colony operation is introduced, which can make the algorithm successfully to escape from local optima, and can rapidly approximate to the global optimum. Simulation results show that the algorithm has preferable global search ability and can effectively jump out of local optimum and rapidly converge to the global optimal solution. Thereby, the algorithm is feasible and effective.

Index Terms—Ant Colony Algorithm, QoS Anycast Routing, iteration operator, dispersed degree, populations of the speed of evolution.

[PDF]

Cite: Yongsheng Li, " A Quality of Service Anycast Routing Algorithm Based on Improved Ant Colony Optimization," Journal of Computers vol. 8, no. 4, pp. 968-974, 2013.