Open Access Open Access  Restricted Access Subscription or Fee Access

Genetic Algorithm with Approximation Algorithm Based Initial Population Selection for Shortest Path Routing in Mobile Ad Hoc Networks

R. Nallusamy, Dr. K. Duraiswamy

Abstract


This paper proposes a new Genetic algorithm with shrink wrap algorithm based initial population selection for the dynamic shortest path routing. Shortest path routing is the basic problem for number of real life problems. Different shortest path optimization problems can be solved by using various approximation algorithms due its computational complexity.. The routing in packet switched multi-hop networks can be described as a classical combinatorial optimization problem i.e. a shortest path routing problem in graphs. The proposed algorithm shows that the GA and shrink wrap algorithms are best candidates for the optimization of dynamic shortest path routing problems due to their fastness in computation comparing to other soft computing and met heuristics algorithms.

Keywords


Combinatorial optimization, Dynamic shortest path routing problem, Genetic algorithm, Shrink wrap algorithm.

Full Text:

PDF

References


D.E.Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley, 1989.

H.E.Rauch and T.Winarske, “neural networks for routing communication traffic”, IEEE control system management, vol.no.2, pp 26-30, 1988.

Jun Wang, “A recurrent neural network for solving shortest path problem”, IEEE transactions on circuits and systems-I: Fundamental theory and applications, vol.43,no.6, June 1996.

J.Wang, “Analysis and design of a recurrent neural network for linear programming”, IEEE transactions on Circuits and systems-I, vol.40, pp 613-618, Sept.1993.

C. W. Ahn, and R. S. Ramakrishna, “A Genetic algorithm for Shortest Path Routing Problem and the Sizing of Populations”, IEEE Transactions on Evolutionary computation, vol.6, no.6, Dec. 2002 .

G.Fahner,” An algorithm structured neural net for the shortest path problem”, Proceedings of international joint conference on neural networks, vol.1, pp 153-158. 1991.

M.K.Ali and F.Kamoun, “Neural networks for shortest path computation and routing in computer networks”, IEEE transactions on neural networks, vol.4, no.6, pp 941-954, Nov.1993.

P.H.Winston, Artificial intelligence, 3rd edition, Pearson education, 2002.

C. W. Ahn, R.S.Ramakrishna, C.G.Kang, and I.C.Choi, “Shortest Path Routing algorithm using Hopfield neural network”, IEEE Electronic letters, vol. .37, no.19, pp. 1176-1178, Sept.2001.

W.Stalling, High speed networks: TCP/IP and ATM design principles,PHI, 1998

J.Moy, “Open shortest path first protocol”, RFC 1583, Mar.1994.

C.Hedrick, “Routing information protocol”, RFC 1058, June 1988.

J.J.Hopfield and D.W.Tank, “Neural computation of decision in optimization problems”, Biol. Cybern. pp. 141-152, 1985.

S.Rajasekaran and G.A.V. Pai, Neural networks, Fuzzy logic and Genetic algorithms synthesis and applications, PHI, 2007.

J.Banks, J.S.Carson II, B.L.Nelson and D.M.Nicol, Discrete event system simulation, 4th edition, PHI, 2005.

D.C.Park and S.E Choi, “A neural network based multidestination routing algorithm for communication network”, in proceedings joint conference on neural networks, pp.1673-1678, 1998.

C.W.Ahn, R. S. Ramakrishna, and C.G.Kang, “Efficient clustering based routing protocol in mobile adhoc networks”, in proc. IEEE vehicular technology conference, pp.1647-1651, 1998.

C.E.Perkins and P.Bhagwat, “Highly dynamic destination sequenced distance vector routing (DSDL) for mobile computers”, computer communications review, pp.234-244, Oct.1994.

S.Murthy and J.J.Garcia-Luna-Aceves, “An efficient routing protocol for wireless networks”, ACM mobile networks applications journal, pp.183-197, Oct.1996.

M.Munemoto, Y.Takai, and Y.Sato, “A migration scheme for the genetic adaptive routing algorithm”, in proc. IEEE int. conf. Systems,Man and cybernetics, pp.2774-2779, 1998.

J.Inagaki, M.Haseyama and H.Kitajima, “A genetic algorithm for determining multiple routes and its applications”, in proc. IEEE int. symp. Circuits and systems, pp137-140, 1999.

S.Haykin, Neural networks, 2nd edition, Pearson education Asia, 2001.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.