Particle Swarm Optimization for Multi-constrained Routing in Telecommunication Networks

Full Text (PDF, 274KB), PP.10-17

Views: 0 Downloads: 0

Author(s)

Hongyan Cui 1,* Jian Li 1 Xiang Liu 1 Yunlong Cai 1

1. Key Laboratory of Universal Wireless Communications, Ministry of Education Beijing University of Posts and Telecommunications, Beijing, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2011.04.02

Received: 6 Nov. 2010 / Revised: 18 Jan. 2011 / Accepted: 12 Mar. 2011 / Published: 8 Jun. 2011

Index Terms

Multi-constrained Routing, Particle Swarm Optimization, Quality of Service

Abstract

By our analysis, the QoS routing is the optimization problem under the satisfaction of multiple QoS constraints. The Particles Swarm Optimization (PSO) is an optimization algorithm which has been applied to finding shortest path in the network. However, it might fall into local optimal solution, and is not able to solve the routing based on multiple constraints. To tackle this problem, we propose a new method of solving the multiple constraints routing. This paper firstly sets up a multi constrained QoS routing model and constructs the fitness value function by transforming the QoS constraints with a penalty function. Secondly, the iterative formulas of the original PSO are improved to tailor to non-continuous search space of the routing problem. Finally, the natural selection and mutation ideas of the Genetic Algorithm (GA) are applied to the PSO to improve the convergent performance. The simulation results show that the proposed GA-PSO algorithm can not only successfully solve the multi-constrained QoS routing problem, but also achieves a better effect in the success rate of the searching optimal path.

Cite This Paper

Hongyan Cui, Jian Li, Xiang Liu, Yunlong Cai, "Particle Swarm Optimization for Multi-constrained Routing in Telecommunication Networks", International Journal of Computer Network and Information Security(IJCNIS), vol.3, no.4, pp.10-17, 2011. DOI:10.5815/ijcnis.2011.04.02

Reference

[1]Dorigo M, Birattari M, Stutzle, “Ant colony optimization” in: Computational Intelligence Magazine, IEEE Volume:1, Date: Nov. 2006. page(s): 28-39.
[2]M.K. Ali, F. Kamoun, “Neural networks for shortest path computation and routing in computer networks”,IEEE Trans. Neural Netw.1993, pp:941-954.
[3]Wen Liu,Lipo Wang, “Solving the Shortest Path Routing Problem Using Noisy Hopfield Neural Networks”, Communications and Mobile Computing, 2009. CMC '09. WRI International Conference, Jan. 2009, Volume: 2, pp: 299-302.
[4]Huang ShengZhong, Huang Liangyong. “The Optimal Routing Algorithm of Communication Networks Based on Neural Network”, in: Intelligent Computation Technology and Automation (ICICTA), May 2010,Volume: 3, pp: 866–869.
[5]M. Munemoto, Y. Takai, Y. Sato, “A migration scheme for the genetic adaptive routing algorithm”, in: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics,1998, pp:2774-2779.
[6]C.W.Ahn,R.S.Ramakrishna,“A genetic algorithm for shortest path routing problem and the sizing of populations”, IEEE Trans. Evol. Comput.6, 2002,pp:566-579.
[7]Gelenbe.E, Liu.P, Laine J, “Genetic Algorithms for Route Discovery”, in:Systems Man and Cybernetics, PartB:Cybernetics,IEEE Trans, Date: Dec. 2006, Volume:36, pp: 1247-1254.
[8]G. Raidl, “A weighted coding in a genetic algorithm for the degree constrained minimum spanning tree problem”, in: Proceed- ings of the ACM Symposium on Applied Computing, 2000, pp:440–445.
[9]J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, “Routing foreseeable light path demands using a tabu search meta-heuristic”, in: Proceedings of the IEEE Global Telecommunication Conference, 2003, pp:2803–2807.
[10]J. Kennedy, R.C. Eberhart, “Particle swarm optimization”, in: Proceedings of the IEEE International Conference on Neural Networks, 1995.
[11]Zhihui Zhan,Jun Zhang,“Adaptive Particle Swarm Optimization”, in: Systems,Man,and Cybernetics,PartB:Cybernetics, IEEE Transactions on Issue Date : Dec. 2009 Volume:39, Issue:6 pp:1362-1381.
[12]Jong-Bae Park,Yun-Won Jeong, “An Improved Particle Swarm Optimization for Non-convex Economic Dispatch Problems”, in: Power Systems, IEEE Transactions on Issue ,2010, Volume:25, pp: 156–166.
[13]R. Hassan, B. Cohanim, O.L. DeWeck, G. Venter, “A comparison of particle swarm optimization and the genetic algorithm”,in: Proceedings of the First AIAA Multidisciplinary Design Optimization Specialist Conference, 2005, pp:18–21.
[14]E. Elbeltagi, T Hegazy, D. Grierson, “Comparison among five evolutionary-based optimization algorithms”, Adv. Eng Inform. 19,2005, pp:43–53.
[15]C.R. Mouser, S.A. Dunn, “Comparing genetic algorithms and particle swarm optimization for an inverse problem exercise.”, Aust. N. Z. Ind. Appl. Math. (ANZIAM) J. 46(E) 2005, pp: C89–C101.
[16]R.C. Eberhart, Y. Shi, “Comparison between genetic algorithms and particle swarm optimization”, in: Proceedings of the seventh annual conference on Evolutionary Programming (Springer-Verlag), 1998, pp:611–616.
[17]D.W.Boeringer,D.H.Werner,“Particle swarm optimization versus genetic algorithms for phased array synthesis”, IEEE Trans. Antennas Propagate. 52(3) 2004,pp:771–779.
[18]Mohammed A.W,Sahoo, N.C. “Particle Swarm Optimization Combined with Local Search and Velocity Re-Initialization for Shortest Path Computation in Networks”, in: Swarm Intelligence Symposium, IEEE 2007,pp: 266–272.