International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 8, No. 5, 8 May 2016
Cover page and Table of Contents: PDF (size: 645KB)
Reliable Mobile Ad-Hoc Network Routing Using Firefly Algorithm
Full Text (PDF, 645KB), PP.10-18
Views: 0 Downloads: 0
Author(s)
D Jinil Persis
1,*
T Paul Robert
2
Index Terms
Routing, Shortest path, Optimization, Meta-heuristics, Firefly Algorithm (FA)
Abstract
Routing in Mobile Ad-hoc NETwork (MANET) is a contemporary graph problem that is solved using various shortest path search techniques. The routing algorithms employed in modern routers use deterministic algorithms that extract an exact non-dominated set of solutions from the search space. The search efficiency of these algorithms is found to have an exponential time complexity in the worst case. Moreover this problem is a multi-objective optimization problem in nature for MANET and it is required to consider changing topology layout. This study attempts to employ a formulation incorporating objectives viz., delay, hop-distance, load, cost and reliability that has significant impact on network performance. Simulation with different random topologies has been carried out to illustrate the implementation of an exhaustive search algorithm and it is observed that the algorithm could handle small-scale networks limited to 15 nodes. A random search meta-heuristic that adopts the nature of firefly swarm has been proposed for larger networks to yield an approximated non-dominated path set. Firefly Algorithm is found to perform better than the exact algorithm in terms of scalability and computational time.
Cite This Paper
D. Jinil Persis, T. Paul Robert, "Reliable Mobile Ad-Hoc Network Routing Using Firefly Algorithm", International Journal of Intelligent Systems and Applications(IJISA), Vol.8, No.5, pp.10-18, 2016. DOI:10.5815/ijisa.2016.05.02
Reference
[1]L. Liu, H. Mu, H. Luo, and X. Li, “A simulated annealing for multi-criteria network path problems,” Comput. Oper. Res., vol. 39, no. 12, pp. 3119–3135, Dec. 2012.
[2]A. W. Mohemmed and N. C. Sahoo, “Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics,” Discret. Dyn. Nat. Soc., vol. 2007, pp. 1–25, 2007.
[3]N. Houlden and V. Grout, “Principles of Optimal Interior Routing,” in Fourth Collaborative Research Symposium on Security, E-learning, Internet and Networking (SEIN 2008), 2005, pp. 274–281.
[4]Y.-K. Lin, “System Reliability with Routing Scheme for a Stochastic Computer Network under Accuracy Rate,” Int. J. Ind. Eng. Theory, Appl. Pract., vol. 20, no. 5–6, 2013.
[5]G. Janssens and J. Pangilinan, “An empirical evaluation of Martins’ algorithm for the multi-objective shortest path problem,” in The 2011 European Simulation and Modelling Conference, 2011, pp. 252–256.
[6]X. Gandibleux, F. Beugnies, and S. Randriamasy, “Martins’ algorithm revisited for multi-objective shortest path problems with a MaxMin cost function,” 4or, vol. 4, no. 1, pp. 47–59, Mar. 2006.
[7]K. Eshghi and H. Javanshir, “A Revised Version of Ant Colony Algorithm for One-Dimensional Cutting Stock Problem,” Int. J. Ind. Eng. Theory, Appl. Pract., vol. 15, no. 4, pp. 341–348, 2008.
[8]N. Pal and S. Sharma, “Robot Path Planning using Swarm Intelligence: A Survey,” Int. J. Comput. Appl., vol. 83, no. 12, pp. 5–12, 2013.
[9]S. K. Pal, C. . Rai, and A. P. Singh, “Comparative Study of Firefly Algorithm and Particle Swarm Optimization for Noisy Non-Linear Optimization Problems,” Int. J. Intell. Syst. Appl., vol. 4, no. 10, pp. 50–57, Sep. 2012.
[10]S. Klampfer and J. Mohorko, “Graph’s theory approach for searching the shortest routing path in RIP protocol: a case study,” PRZEGLĄD ELEKTROTECHNICZNY (Electrical Rev., no. 8, pp. 224–231, 2012.
[11]K. Magzhan and H. Jani, “A Review And Evaluations Of Shortest Path Algorithms,” Int. J. Sci. Technol. Res., vol. 2, no. 6, pp. 99–104, 2013.
[12]D. Medhi, Network Routing: Algorithms, Protocols, and Architectures. 2007.
[13]Z. Tarapata, “Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms,” Int. J. Appl. Math. Comput. Sci., vol. 17, no. 2, pp. 269–287, Jan. 2007.
[14]C. Cooper and A. Frieze, “Average-case complexity of shortest-paths problems in the vertex-potential model,” Random Struct. Algorithms, vol. 16, no. 1, pp. 33–46, 2000.
[15]B. V. Cherkassky, L. Georgiadis, A. V. Goldberg, R. E. Tarjan, and R. F. Werneck, “Shortest-path feasibility algorithms,” J. Exp. Algorithmics, vol. 14, pp. 1–37, Dec. 2009.
[16]N. Sarma and S. Nandi, “A Multipath QoS Routing with Route Stability for Mobile Ad Hoc Networks,” IETE Tech. Rev., vol. 27, no. 5, pp. 380–397, 2010.
[17]W. Alnumay, P. Chatterjee, and U. Ghosh, “Energy Aware Secure Routing for Wireless Ad Hoc Networks,” IETE J. Res., vol. 60, no. 1, pp. 37–41, 2014.
[18]N. Wang and S. Chang, “A reliable on-demand routing protocol for mobile ad hoc networks with mobility prediction,” Comput. Commun., vol. 29, pp. 123–135, 2005.
[19]W. Naruephiphat and C. Charnsripinyo, “Routing algorithm for balancing network lifetime and reliable packet delivery in Mobile Ad Hoc Networks,” Ubiquitous, Auton. …, pp. 257–262, 2009.
[20]J. Pangilinan and G. Janssens, “Evolutionary Algorithms for the Multiobjective Shortest Path Problem.,” Enformatika, vol. 1, no. 5, pp. 322–327, 2007.
[21]A. W. Mohemmed, N. C. Sahoo, and T. K. Geok, “Solving shortest path problem using particle swarm optimization,” Appl. Soft Comput., vol. 8, no. 4, pp. 1643–1653, Sep. 2008.
[22]M. Gła̢bowski and B. Musznicki, “Shortest Path Problem Solving Based on Ant Colony Optimization Metaheuristic,” Image Process. Commun., vol. 17, no. 1, pp. 7–18, 2012.
[23]C. V. Raghavendran, G. N. Satish, and P. S. Varma, “Intelligent Routing Techniques for Mobile Ad hoc Networks using Swarm Intelligence,” Int. J. Intell. Syst. Appl., vol. 5, no. December 2012, pp. 81–89, 2012.
[24]M. K. Sayadi, R. Ramezanian, and N. Ghaffari-Nasab, “A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems,” Int. J. Ind. Eng. Comput., vol. 1, no. 1, pp. 1–10, Jul. 2010.
[25]A. Yousif, A. H. Abdullah, S. M. Nor, and A. A. Abdelaziz, “Scheduling Jobs on Grid Computing using Firefly Algorithm,” J. Theor. Appl. Inf. Technol., vol. 33, no. 2, pp. 155–164, 2011.
[26]L. Kota, “Optimization Of The Supplier Selection Problem Using Discrete Firefly Algorithm,” Adv. Logist. Syst., vol. 6, no. 1, pp. 117–126, 2012.
[27]K. Nadhir, D. Chabane, and B. Tarek, “Firefly algorithm based energy loss minimization approach for optimal sizing & placement of distributed generation,” in Modeling, Simulation and Applied Optimization (ICMSAO), 2013, 2013, pp. 1–5.
[28]B. Filipowicz, “Firefly algorithm in optimization of queueing systems,” Bull. Polish Acad. Sci., vol. 60, no. 2, pp. 363–368, 2012.
[29]S. Kumbharana and G. Pandey, “Solving Travelling Salesman Problem using Firefly Algorithm,” Int. J. Res. Sci. Adv. Technol., vol. 2, no. 2, pp. 53–57, 2013.
[30]J. Senthilnath, S. N. Omkar, and V. Mani, “Clustering using firefly algorithm: Performance study,” Swarm Evol. Comput., vol. 1, no. 3, pp. 164–171, Sep. 2011.
[31]M. Sivakumar and M. Jayanthi, “Reliability Analysis of Link Stability in Secured Routing Protocols for MANETs,” Eng. J., vol. 18, no. 1, pp. 65–76, 2013.
[32]H. Zhang and Y. Dong, “Mobility Prediction Model Based Link Stability Metric for Wireless Ad Hoc Networks,” IEEE Wirel. Commun. Netw. …, pp. 3–6, 2006.
[33]A. Argyriou and V. Madisetti, “Using a new protocol to enhance path reliability and realize load balancing in mobile ad hoc networks,” Ad Hoc Networks, vol. 4, no. 1, pp. 60–74, 2006.
[34]N. Padmavathy and S. Chaturvedi, “Evaluation of mobile ad hoc network reliability using propagation-based link reliability model,” Reliab. Eng. Syst. Saf., vol. 115, pp. 1–9, 2013.
[35]M. Eiza, Q. Ni, T. Owens, and G. Min, “Investigation of routing reliability of vehicular ad hoc networks,” EURASIP J. Wirel. Commun. Netw., vol. 2013, no. 1, p. 179, 2013.
[36]K. Deb, Multi-Objective Optimization using Evolutionary Algorithms. 2001, p. 518.
[37]S. Yu, S. Yang, and S. Su, “Self-Adaptive Step Firefly Algorithm,” J. Appl. Math., vol. 2013, no. 1, pp. 1–8, 2013.
[38]B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617–1622, 1988.