The Multi-Constrained Multicast Routing Improved by Hybrid Bacteria Foraging-Particle Swarm Optimization

Satya Prakash Sahoo; Manas Ranjan Kabat

doi:10.7494/csci.%Y.%v.%i.3131

Authors

Satya Prakash Sahoo Veer Surendra Sai University of Technology
Manas Ranjan Kabat

DOI:

https://doi.org/10.7494/csci.%25Y.%25v.%25i.3131

Keywords:

QoS routing, Multicasting, Particle Swarm Optimization, Bacteria Foraging Optimization

Abstract

To solve multicast routing under multiple constraints, it is required to generate a multicast tree that ranges from a source to the destinations with minimum cost subject to several constraints. In this paper, PSO has been embedded with BFO to improve the convergence speed and avoid premature convergence that will be used for solving QoS multicast routing problem. The algorithm proposed here generates a set of delay compelled links to every destination present in the multicast group. Then the Bacteria Foraging Algorithm (BFA) selects the paths to all the destinations sensibly from the set of least delay paths to construct a multicast tree. The robustness of the algorithm being proposed had been established through the simulation. The efficiency and effectiveness of the algorithm being proposed was validated through the comparison study with other existing meta-heuristic algorithms. It shows that our proposed algorithm IBF-PSO outperforms its competitive algorithms.

Downloads

Download data is not yet available.

References

Wang, Z., Crowcroft, J.: Quality of service for supporting multi- media application. IEEE J. Select Areas Commun. 14, 1228–1234 (1996)

Molnar, M.; Bellabas, A.; Lahoud, S.; The cost optimal solution of the multi-constrained multicast routing problem. Computer Networks.2012, 56, 3136-3149.

Forsati, R.; Haghighat, A.T.; Mahdavi, M.; Harmony search based algorithms for bandwidth-delay-constrained least-cost multicast routing. Computer Communications.2008, 31, 2505–2519.

Geem, Z.W.; Kim, J.H.; Loganathan, G.V.; A new heuristic optimization algorithm: harmony search. Simulation.2001, 76 (2), 60–68.

Geem, Z.W.; Tseng, C.; Park, Y.; Harmony search for generalized orienteering problem. Lecture Notes in Computer Science.2005, 3412,741–750.

Abdel-Kader, R. F.; Hybrid discrete PSO with GA operators for efficient QoS-multicast routing. Ain Shams Engineering Journal. 2011, 2,21–31.

Dorigo, M.; Caro G. D.; The ant colony optimization meta-heuristic, new ideas in optimization. McGraw-Hill, 1999.

Gong, B.; Li, L.; Wang, X.; Multicast Routing Based on Ant Algorithm with Multiple Constraints. IEEE International Conference on Wireless Communications, Networking and Mobile Computing, 2007, 1945-1948.

Haghighat, A.T.; Faez, K.; Dehghan, M.; Mowlaei, A.; Ghahremani, Y.; GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing. Computer Communications. 2004, 27, 111–127.

Hwang, R.H.; Do, W.Y.; Yang, S.C.; Multicast Routing Based on Genetic Algorithms. Journal of Information Science and Engineering.2000, 16, 885-901 .

Kennedy, J., Eberhart, R.C.; Particle Swarm Optimization. IEEE International Conference on Neural Networks.1995, 1942–1948.

Korani, W; Bacterial Foraging Oriented by Particle Swarm Optimization Strategy for PID Tuning, GECCO, 2008.

Kosiur, D.; IP Multicasting: The Complete Guide to Interactive Corporate Networks. Wiley, New York, 1998 .

Kun Z.; Heng W.; Liu F.Y.; Distributed multicast routing for delay and delay variation-bounded Steiner tree using simulated annealing. Computer Communications.2005, 28 (11),1356–1370.

Lee, K.S.; Geem, Z.W.; A new meta-heuristic algorithm for continues engineering optimization: harmony search theory and practice. Computer Methods in Applied Mechanics and Engineering.2004, 194, 3902–3933.

Palmer, C.C.; Kershenbaum, A.; Representing trees in genetic algorithms. IEEE world Congress on Computational Intelligence.1993, 1, 379-384.

Patel, M.K; Kabat, M.R.; Tripathy, C. R.; A Hybrid ACO/PSO based algorithm for QoS multicast routing problem. Ain Shams Engineering Journal. 2014, 5,113-120.

Peng, B.; Lei L.; A Method for QoS Multicast Routing Based on Genetic Simulated Annealing Algorithm. International Journal of Future Generation Communication and Networking. 2012, 5, 1, 43-60.

Pradhan, R.; Kabat, M.R.; Sahoo, S. P; A Bacteria Foraging-Particle Swarm Optimization Algorithm for QoS multicast Routing. Lecture notes on Computer Science.2013, 8297,590-600.

Qu, R.;Xu, Y.; Castro, J. P.; Particle swarm optimization for the Steiner tree in grapg and delay delay-constrained multicast routing problems. Journal of Heuristics, 2013, 19, 317-342.

Passino, K.M.: Biomimicry of bacterial foraging for distributed optimization and control. IEEE Control Sys. Mag. 22(3), 52–67 (2002)

Quinn, B.; IP Multicast Applications: Challenges and Solutions. IETF

RFC 3170, 2001.

Ravikumar, C.P.; Bajpai, R.; Source-based delay-bounded multicasting in multimedia networks. Computer Communications.1998, 21, 126–132.

Rong, Q.; Ying X,; Castro, J. P.; Landa-Silva, D.; Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems. Journal of Heuristics.2013, 19, 317–342.

Shi, L.; Li, L.; Zhao, W.; Qu, B.; A Delay constrained Multicast Routing Algorithm Based on the Ant Colony Algorithm. Lecture Notes in Electrical Engineering.2013,219, 875-882.

Sun, J.; Fang, W; Xiaojun, W; Xie, Z.; Xu, W.; QoS multicast routing using a quantum-behaved particle swarm optimization algorithm. Engineering Applications of Artificial Intelligence.2011, 24, 123–131,

Sun, J.; Feng, B.; Xu, W.B.; Particle swarm optimization with particles having quantum behavior, In Proceedings of Congress on Evolutionary Computation.325–331(2004).

Sun, J.; Xu, W.B.; Feng, B.; A global search strategy of quantum-behaved particle swarm optimization, In Proceedings of IEEE Conference on Cybernetics and Intelligent Systems, 2004, 111–116.

Wang, H.; Meng, X.; Li, S., Xu, H.; A tree-based particle swarm optimization for multicast routing. Computer Network.2010,54, 2775–86.

Wang, H.; Shi, Z.; Li, S.; Multicast routing for delay variation bound

using a modified ant colony algorithm. Journal of Network and Computer Applications.2009, 32, 258–272.

Wang, H.; Xu, H.; Yi, S.; Shi, Z.; A tree-growth based ant colony algorithm for QoS multicast routing problem. Expert Systems with Applications.2011, 38, 11787–11795.

Wang, Z.; Shi, B.; Zhao, E.; Bandwidth-delay-constrainted least-cost multicast routing based on heuristic genetic algorithm. Computer Communications.2001, 24, 685–692.

Xi-Hong, C.; Shao-Wei, L.; Jiao, G.; Qiang, L.; Study on QoS multicast routing based on ACO-PSO algorithm. Proceedings of 2010 international conference on intelligent computation technology and automation. 2010, 534–753.

Yen, J. Y.; Finding the k-shortest loop-less paths in a network, Managent Science.1971, 17(11), 712–716.

Yin, P.Y.; Chang, R.I.; Chao, C.C.; Chu. Y.T.; Niched ant colony optimization with colony guides for QoS multicast routing. Journal of network and computer applications.2014, 40, 61-72.

Younes, A.; An Ant Algorithm for Solving QoS Multicast Routing Problem. International Journal of Computer Science and Security (IJCSS).2011, 5(1), 766-777.

Zhang, L.; Cai, L.; Li, M.; Wang, F.; A method for least-cost QoS multicast routing based on genetic simulated annealing algorithm. Computer Communications. 2009, 32, 105–110.