Investigation on Novel Based Metaheuristic Algorithms for Combinatorial Optimization Problems in Ad Hoc Networks
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:60481", author = "C. Rajan and N. Shanthi and C. Rasi Priya and K. Geetha", title = "Investigation on Novel Based Metaheuristic Algorithms for Combinatorial Optimization Problems in Ad Hoc Networks", 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.", volume = "8", number = "6", pages = "935-6", }
