GASANT: An ant-inspired least-cost QoS multicast routing approach based on genetic and simulated annealing algorithms
Keywords:
Multicast Routing, Quality of Service (QoS), Ant Colony Optimization (ACO), Genetic Algorithm (GA), Simulated Annealing (SA)Abstract
Computing least-cost multicast routing tree while satisfying QoS constraints has become a key issue especially by growing communication networks. To solve this problem, a triplex algorithm called GASANT which is based on Ant Colony Optimization (ACO), Genetic Algorithm (GA), and Simulated Annealing (SA) has been proposed in this paper. Through ACO, we have both provided improved initial population to feed GA and reduced search process. Besides, SA has been deployed to refrain GA from getting stuck into local optimum solutions. Simulation results assert that GASANT not only has high speed convergence time, but also generates least-cost multicast routing trees of high QoS.
References
W. Zhengying, S. Bingxin, Z. Erdun, Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm Computer Communications, Volume 24, Issues 7-8, April 2001.
F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem, Annals of Discrete Mathematics, vol. 53, 1992.
R. M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations, 1972.
V. P. Kompella, J. Pasquale, G. C. Polyzos, Multicast routing for multimedia communication IEEE/ACM Transactions on Networking. 1(3) (1993) 286-292. http://dx.doi.org/10.1109/90.234851
M. Parsa, Q. Zhu, J.J. Garcia-Luna-Aceves, An iterative algorithm for delay-constrained minimumcost multicasting, IEEE/ACM Transactions on Networking 6 (4) 1998. http://dx.doi.org/10.1109/90.720901
R. Widyono, The design and evaluation of routing algorithms for realtime channels, Technical Reports TR-94-024, Tenet Group, Department of EECS, University of California at Berkeley, 1994.
A.G. Waters, A new heuristic for ATM multicast routing, 2nd IFIP Workshop on Performance Modeling and Evaluation of ATM networks, 1994.
Q. Sun, H. Langendorfer, An efficient delay-constrained multicast routing algorithm, Journal of High-Speed Networks 7(1) 1998 43-55.
H.F. Salama, D.S. Reeves, Y. Viniotis, Evaluation of multicast routing algorithms for real-time communication on high-speed networks, IEEE Journal on Selected Areas in Communications 15(3) (1997) 332-345. http://dx.doi.org/10.1109/49.564132
F. Xiang, L. Junzhou, W. Jieyi, G. Guanqun, QoS routing based on genetic algorithm, Computer Communications 22(15-16) (1999) 1392-1399. http://dx.doi.org/10.1016/S0140-3664(99)00113-9
A.T. Haghighat, K. Faez, M. Dehghan, A. Mowlaei, Y. Ghahremani, GA-Based Heuristic Algorithms for QoS Based Multicast Routing, knowledge-based systems 16 (2003) 305-312. http://dx.doi.org/10.1016/S0950-7051(03)00032-7
C.P. Ravikumar, R. Bajpai, Source-based delay-bounded multicasting in multimedia networks, Computer Communications 21 (1998) 126-132. http://dx.doi.org/10.1016/S0140-3664(97)00124-2
Z. Wang, B. Shi, E. Zhao, Bandwidth-delay-constrainted least-cost multicast routing based on heuristic genetic algorithm, Computer Communications 24 (2001) 685-692. http://dx.doi.org/10.1016/S0140-3664(00)00273-5
S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall, 2003.
Q. Zhang, Y.W. Leung, An orthogonal genetic algorithm for multimedia multicast routing, IEEE Trans. Evol. Comput. 3 (1) (1999) 53-62. http://dx.doi.org/10.1109/4235.752920
K. Vijayalakshmi, and S. Radhakrishnan, Dynamic Routing to Multiple Destinations in IP Networks Using Hybrid Genetic Algorithm (DRHGA), International Journal of Information Technology. 4(1) 2008.
Vijayalakshmi, S. Radhakrishnan, Artificial immune based hybrid GA for QoS based multicast routing in large scale networks (AISMR), Computer communications, 2008. http://dx.doi.org/10.1016/j.comcom.2008.08.005
N. Shimamoto, A. Hiramatsu, K. Yamasaki, A dynamic routing control based on a GA, In proceedings of the IEEE International Conference on Neural Network (1993) pp. 1123-1128.
J.J. Wu, R.H. Hwang, H.I. Lu, Multicast routing with multiple QoS constraints in ATM networks, Information Sciences 124 (2000) 29-57. http://dx.doi.org/10.1016/S0020-0255(99)00102-4
Li Zhang, Lian-bo Cai, Meng Li, Fa-hui Wang, A method for least-cost QoS least-Cost multicast routing based on genetic simulated annealing algorithm, Computer Communications, 31 (2008) 3984-3994.
Sushil J. Louis Gregory J. E. Rawlins, Predicting Convergence Time for Genetic Algorithms, Technical Report, Indiana University, 1992.
R. R. Hill, Ch. Hiremath, Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems, International Journal of Operational Research 2005 - Vol. 1, No.1/2 pp. 145 - 159.
G. Di Caro, M. Dorigo, AntNet: Distributed Stigmergetic Control for Communications Networks, Journal of Artificial Intelligence Research 9 (1998) 317-365.
Özgür Yeniay, Penalty Function Methods for Constrained Optimization with Genetic Algorithms, Journal of Mathematical and Computation Applications, 10(1) (2005) pp. 45-56.
J. D. Schaffer, A. Morishima, An Adaptive Crossover Distribution Mechanism for Genetic Algorithms, ICGA 1987.
C. Guoliang, W. Xufa, Z. Zhenquan, Genetic Algorithm and its Application, People's Posts and Telecommunications Press, 1996.
M. Farooq, Implementation of AntNet in OMNeT++, http://www.omnetpp.org/component/content/article/9-software/3559, November 2009.
B.M.Waxman, Routing of multipoint connections. IEEE J. Select. Areas Commun. 6(9) (1998) 1617-1622. http://dx.doi.org/10.1109/49.12889
S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, New Series, Vol. 220, No. 4598 (1983) pp. 671-680.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
