Using A Hybrid Algorithm to Improve the Quality of Services in Multicast Routing Problem
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:62773", author = "Mohammad Reza Karami Nejad", title = "Using A Hybrid Algorithm to Improve the Quality of Services in Multicast Routing Problem", 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.", volume = "6", number = "10", pages = "1267-6", }
