Using A Hybrid Algorithm to Improve the Quality of Services in Multicast Routing Problem

Authors: Mohammad Reza Karami Nejad

Abstract:

A hybrid learning automata-genetic algorithm (HLGA) is proposed to solve QoS routing optimization problem of next generation networks. The algorithm complements the advantages of the learning Automato Algorithm(LA) and Genetic Algorithm(GA). It firstly uses the good global search capability of LA to generate initial population needed by GA, then it uses GA to improve the Quality of Service(QoS) and acquiring the optimization tree through new algorithms for crossover and mutation operators which are an NP-Complete problem. In the proposed algorithm, the connectivity matrix of edges is used for genotype representation. Some novel heuristics are also proposed for mutation, crossover, and creation of random individuals. We evaluate the performance and efficiency of the proposed HLGA-based algorithm in comparison with other existing heuristic and GA-based algorithms by the result of simulation. Simulation results demonstrate that this paper proposed algorithm not only has the fast calculating speed and high accuracy but also can improve the efficiency in Next Generation Networks QoS routing. The proposed algorithm has overcome all of the previous algorithms in the literature.

Keywords: Routing, Quality of Service, Multicaset, Learning Automata, Genetic, Next Generation Networks.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081729

References:

[1] R. Osteen and P. Lin., Picture skeletons based on eccentricities of points of minimum spanning trees, SIAM J Comput, 1974,pp.23-40.
[2] N. Lin, X. Chen and X. Li., QoS Multicast Routing Algorithm based on Immune Genetic method in NGN, SIAM J Comput, 2010, IEEE, pp.1-4.
[3] JC. Gower and GJS. Ross., Minimum spanning trees and single linkage cluster analysis, 1969, J R Stat Soc pp.54-64.
[4] RL. Graham and P. Hell., On the history of the minimum spanning tree problem,1985,IEEE Ann HistComput,pp.43-57.
[5] H.F. Salama, D.S. Reeves and Y. Viniotis., Evaluation of multicast routing algorithms for real-time communication on high-spee networks, 1997, IEEE Journal on Selected Areas in Communications,pp. 332-345.
[6] Yu. Hao, Z. Huang and S. Rui., Principles and techniques, 2007,Beijing: Publishing House of Electronics Industry.
[7] KR. Hutson and DR. Shier., Minimum spanning trees in networks with varying edge weights, 2006, Ann Oper Res ,pp.3-18.
[8] A. Jain and jW. Mamer., Approximations for the random minimal spanning tree with application to network provisioning, 1988, Oper Res 36: pp.575-584.
[9] A. Kang, R. Lee, CL. Chang and SK. Chang., Storage reduction through minimal spanning trees and spanning forests, 1977, IEEE Trans Comput, C-26:pp.425-434.
[10] S. Lakshmivarahan and MAL. Thathachar., Bounds on the convergence probabilities of learning automata,IEEE Trans Syst Man Cybern, SMC-6: pp.756-763.
[11] S. Lakshmivarahan, MAL.Thathachar., Bounds on the convergence probabilities of learning automata, 1976, IEEE Trans Syst Man Cybern, SMC- 6:pp.756-763.
[12] M. Parsa and Q.J. Zhu., An iterative algorithm for delay-constrained minimum-cost multicasting, 1998, IEEE/ACM Transactionson Networking 6 (4) pp. 461-474.
[13] A. Valleho, A. Zaballos, D. Vernet, D. Cutiller and J. Dalmau., Implementation of Traffic Engineering in NGNs using Hybrid Genetic Algorithms, 2008, IEEE,pp.262-267.
[14] S. Marchand-Maillet and YM.A. Sharaiha., Minimum Spanning Tree Approach to Line Image Analysis, 1996, In: Proceedings of 13th international conference on pattern recognition (ICPR’96), pp 225.
[15] KS. Narendra and KS. Thathachar., Learning automata: an introduction, 1989, Printice-Hall, New York.
[16] G. Schollmeier and C. Winker., Providing Sustainable Qos in Next Generation Networks, 2004, IEEE Communications Magazine , pp 102- 107.
[17] F. WahabKaram and T. Jensen., A Survey on QoS in Next Generation Networks,2010, Information Sciences and Service Sciences, pp 91-102.
[18] V.P. Kompella, J.C. Pasquale and G.C. Polyzos., Multicast Routing for Multimedia Communication, 1993, IEEE/ACM Transactions on Networking ,pp 286-292.
[19] Z. Wang and J. Crowcroft., Quality of Service for Supporting Multimedia Applications, 1996, IEEE Journal On Selected Areas in Communications,pp.1228-1234.
[20] L. Wei-yan and Y. Shun., A QoS Multicast Routing Algorithms Based on Genetic Algorithm in Next-Generation Networks, 2005, Journal of Electronics & Information Technology.
[21] L. Yunjie and Z. Yunyong., The next generation network service and quality, 2005, Beijing: Publishing House of Electronics Industry.
[22] Z. Wang, B. Shi and E. Zhao., Bandwidth-delay-constrainted least-cost multicast routing based on heuristic genetic algorithm, 2001, Computer Communications, pp.685-692.
[23] L. Qian., A New Qos Routing Architecture In NGI, 2005, Phd Thesis, Universit Du Qubec ? Montral,pp.1-64.
[24] Y. Wang, L. Li and D. Xu., Pervasive Qos Routing in Next Generation Networks, 2008, Elsevier,pp.3485-3491.
[25] A. YounesHamed., An Ant Algorithm for Solving QoS Multicast Routing Problem, 2011, International Journal of Computer Science and Security (IJCSS),pp. 157-167.
[26] X. Wang, P. Liu and M. Huang., Genetic Algorithm and Pareto Optimum Based QoS Multicast Routing Scheme in NGI, 2007, Springer-Verlag Berlin Heidelberg,pp.115-122.
[27] C.P. Ravikumar and R. Bajpai., Source-Based Delay-Bounded Multicasting in Multimedia Networks, 1998, Computer Communications 21, pp. 126-132.
[28] K. Zhang, H. Wang and F. Liu., Distributed Multicast Routing for Delay and Delay Variation Bounded Steiner Tree Using Simulated Annealing, 2004, Elsevier, pp.1356-1370.