Investigation on Novel Based Metaheuristic Algorithms for Combinatorial Optimization Problems in Ad Hoc Networks

Authors: C. Rajan, N. Shanthi, C. Rasi Priya, K. Geetha

Abstract:

Routing in MANET is extremely challenging because of MANETs dynamic features, its limited bandwidth, frequent topology changes caused by node mobility and power energy consumption. In order to efficiently transmit data to destinations, the applicable routing algorithms must be implemented in mobile ad-hoc networks. Thus we can increase the efficiency of the routing by satisfying the Quality of Service (QoS) parameters by developing routing algorithms for MANETs. The algorithms that are inspired by the principles of natural biological evolution and distributed collective behavior of social colonies have shown excellence in dealing with complex optimization problems and are becoming more popular. This paper presents a survey on few meta-heuristic algorithms and naturally-inspired algorithms.

Keywords: Ant colony optimization, genetic algorithm, Naturally-inspired algorithms and particle swarm optimization.

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

References:

[1] Elisa ValentinaOnet and EcaterinaVladu, "Nature inspired algorithms and Artificial Intelligence”, Journal of Computer Science, 2005.
[2] Shivakumar, B. L, Amudha, T, "A Novel Nature-inspired Algorithm to solve Complex Generalized Assignment Problems”, International Journal of Research and Innovation in Computer Engineering, Vol 2, Issue 3, (280-284), June 2012.
[3] Qinghai Bai, "Analysis of Particle Swarm Optimization Algorithm”, Computer and Information Science, Vol.3, No.1, February 2010.
[4] Zahra Beheshti, SitiMariyamHj. Shamsuddin, "A Review of Populationbased Meta-Heuristic Algorithms”, Int. J. Advance. Soft Comput. Appl., Vol. 5, No. 1, March 2013.
[5] Jianping Wang, EseosaOsagie, Parimala Thulasiraman and Ruppa K. Thulasiram, "HOPNET: A hybrid ant colony optimization algorithm for mobile ad hoc network”, Ad Hoc Networks 7, 690–705, 2009.
[6] Chenn-Jung Huang, Yi-Ta Chuang and Kai-Wen Hu, "Using particle swam optimization for QoS in ad-hoc multicast”, Engineering Applications of Artificial Intelligence 22, 1188–1193, 2009.
[7] Shengxiang Yang, Hui Cheng, and Fang Wang, "Genetic Algorithms With Immigrants and Memory Schemes for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Networks”, IEEE Transactions On Systems, Man and Cybernetics Part C: Applications And Reviews, Vol. 40, No. 1, January 2010.
[8] Jun Sun, WeiFang, XiaojunWu, ZhenpingXie and WenboXu, "QoS multicast routing using a quantum-behaved particle swarm optimization algorithm”, Engineering Applications of Artificial Intelligence 24, 123– 131, 2011.
[9] AnshuGarg, Amit Sharma, Prof. (Dr.) Ajay Pratap and Ankita Singh, "Applied Multiagent Ant Based Hybrid Routing Algorithm For Mobile Ad Hoc Networks”, International Journal. EnCoTe, v0102, 28 – 34, 2012.
[10] Sajjad Jahanbakhsh Gudakahriz, Shahram Jamali and Mina VajedKhiavi, "Energy Efficient Routing in Mobile Ad Hoc Networks by Using Honey Bee Mating Optimization”, Journal of Advances in Computer Research, Vol. 3, No. 4, November 2012.
[11] K. G. Santhiya, Dr. N. Arumugam, "A Novel Adaptive Bio-Inspired Clustered Routing for MANET”, Procedia Engineering 30, 711 – 717, 2012.
[12] Zhenyu Liu, Marta Z. Kwiatkowska, and Costas Constantinou, "A Biologically Inspired QoS Routing Algorithm for Mobile Ad Hoc Networks”, International Journal of Wireless and Mobile Computing (IJWMC), 2009.
[13] Sharvani. G. S, Dr. A. G. Ananth and Dr. T. M. Rangaswamy, "Efficient Stagnation Avoidance For Manets With Local Repair Strategy Using Ant Colony Optimization”, International Journal of Distributed and Parallel Systems (IJDPS), Vol.3, No.5, September 2012.
[14] Alireza Sajedi Nasab, ValiDerhamia, Leyli Mohammad Khanlib and Ali Mohammad ZarehaBidokia,"Energy-aware multicast routing in manet based on particle swarm optimization”, Procedia Technology 1, 434 – 438, 2012.
[15] Anjum A. Mohammed and GihanNagib, "Optimal Routing In Ad-Hoc Network Using Genetic Algorithm”, Int. J. Advanced Networking and Applications, Volume: 03, Issue: 05, Pages: 1323-1328, 2012.
[16] Ting Lu and Jie Zhu, "Genetic Algorithm for Energy-Efficient QoS Multicast Routing”, IEEE Communications Letters, Vol. 17, No. 1, January 2013.
[17] Dhamodharan. T, Vimalanand. S and Chandrasekar. C,"Bio Inspired and Evolutionary Approaches to Optimize MANET Routing”, International Journal of Computing Academic Research (IJCAR), ISSN 2305-9184 Volume 2, Number 3, pp. 88-98, June 2013.
[18] Debajit Sensarma and Koushik Majumder, "An Efficient Ant Based QoS Aware Intelligent Temporally Ordered Routing Algorithm for MANETs”, International Journal of Computer Networks & Communications (IJCNC), Vol.5, No.4, July 2013.
[19] Zulfiqar Ali and WaseemShahzad, "Analysis of Routing Protocols in AD HOC and Sensor Wireless Networks Based on Swarm Intelligence”, International Journal of Networks and Communications, 3(1): 1-11, 2013.
[20] Ibukunola. A. Modupea, Oludayo. O. Olugbarab and Abiodun. Modupe, "Minimizing Energy Consumption in Wireless Ad hoc Networks with Meta-heuristics”, Procedia Computer Science 19, 106 – 115, 2013.
[21] Pankaj Vidhate, Yogita Wankhade, "Route Optimization in Manets with ACO and GA”, IJRET: International Journal of Research in Engineering and Technology, Volume: 02 Issue: 11, Nov-2013.
[22] MENG Limin, SONG Wenbo, "Routing Protocol Based on Grover’s Searching Algorithm for Mobile Ad-hoc Networks”, Network Technology and Application, China Communications, March 2013.
[23] WANG Ya-li, SONG Mei, WEI Yi-fei, WANG Ying-he, WANG Xiaojun," Improved ant colony-based multi-constrained QoS energy-saving routing and throughput optimization in wireless Ad-hoc networks”, The Journal of China Universities of Posts and Telecommunications, 21(1): 43–53, February 2014.
[24] Gurpreet Singh, Neeraj Kumar and Anil Kumar Verma, "OANTALG: An Orientation Based Ant Colony Algorithm for Mobile Ad Hoc Networks”, Wireless Pers. Commun, Springer Science, Business Media New York, 2014.
[25] Manoj Kumar Patel, Manas Ranjan Kabat and Chita Ranjan Tripathy, "A hybrid ACO/PSO based algorithm for QoS multicast routing problem”, Ain Shams Engineering Journal 5, 113–120, 2014.
[26] Alexandros Giagkos and Myra S. Wilson, "BeeIP – A Swarm Intelligence based routing for wireless ad hoc networks”, Information Sciences 265, 23–35, 2014.
[27] Peng-YengYin, Ray-I.Chang, Chih-ChiangChao and Yen-TingChu, "Niched ant colony optimization with colony guides for QoS multicast routing”, Journal ofNetworkandComputerApplications40, 61–72, 2014.
[28] SamanHameed Amin , H.S. A-Raweshidy and RafedSabbar Abbas, "Smart data packet ad hoc routing protocol”, Computer Networks 62, 162–181, 2014.
[29] Nancharaiah. B, Chandra Mohan. B, "The performance of a hybrid routing intelligent algorithm in a mobile ad hoc network”, Computers and Electrical Engineering, Elsevier, 2014.
[30] Lazar, A., Reynolds, R. G., "Heuristic knowledge discovery for archaeological data using genetic algorithms and rough sets”, Artificial Intelligence Laboratory, Department of Computer Science, Wayne State University, 2003.
[31] Holland, J. H., "Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence”, Michigan, Ann Arbor, University of Michigan Press, 1975.
[32] Glover, F., McMillan, C., "The general employee scheduling problem: an integration of MS and AI”, Computers & Operations Research, Vol. 13, No. 5, pp. 563-573, 1986.
[33] Glover, F., "Tabu Search - Part 1”, ORSA Journal on Computing, Vol. 1, No. 2, pp.190–206, 1989.
[34] Glover, F., "Tabu Search - Part 2”, ORSA Journal on Computing, Vol. 2, No.1, pp. 4–32, 1990.
[35] Kennedy. J and Eberhart, R., "Particle swarm optimization”, Proceedings of IEEE International Conference on Neural Networks, pp. 1942–1948, 1995.
[36] Karaboga, D., "An idea based on honey bee swarm for numerical optimization”, Technical Report, TR06, 2005.
[37] M. Dorigo, "Optimization, Learning and Natural Algorithms (in Italian)”, PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, pp.140, 1992.
[38] M. Dorigo, V. Maniezzo, A. Colorni, "The ant system: optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics-Part B 26(1):29-41, 1996.
[39] HumayunBakht, "Computing Unplugged, Wireless infrastructure, Some Applications of Mobile ad hoc networks”, http://www.computingunplugged.com/issues/ issue200410/00001395001.html, April-2003.
[40] Beheshti, Z., Shamsuddin, S. M., Yuhaniz, S. S., "Binary Accelerated Particle Swarm Algorithm (BAPSA) for discrete optimization problems”, Journal of Global Optimization, 57:549-573, 2013.
[41] Wang H, Meng X, Li S, Xu H, "A tree-based particle swarm optimization for multicast routing”, Computer Networks; 54: 2775–86, 2010.
[42] Rajan. C, Shanthi. N, "Swarm Optimized Multicasting For Wireless Network”, Life Science Journal; 10(4s), 2013.
[43] Wang H, Xu H, Yi S, Shi Z,"A tree-growth based ant colony algorithm for QoS multicast routing problem”, ExpSystAppl2011;38:11787–95, 2011.