Route Optimization by using Multiple Travelling Sales Person Problem in MANETs

Authors

  • M V Narayana  Department of CSE, Guru Nanak Institutions Technical Campus, Ibrahimpatnam, Hyderabad, Telangana, India

Keywords:

MANET, TSP, MTSP, Nearest Neighbor Algorithms, Euclidean Distance

Abstract

Finding the route between two mobile nodes is one of critical task in Mobile Adhoc Networks (MANETs). In this work mainly focusing on route optimization with nearest neighbour for Multiple Travelling Sales Person Problems (MTSP). MANET is a multi-hop wireless network with mobility feature like mobile phones, computers. Each node will be act as router and communicate without server concept. In the Travelling Sales Person Problem (TSP), all the possible number of routes to be found by a salesperson (Mobile Routing Agent) through cover every node and finally come back to starting point along with possible number of shortest paths. Mobile Routing Agent collects the node and its total information in the network like node position, neighbour node data and message agent (salesperson) helps during the data transmission. The main aim of the proposed concept is to obtain the optimum route between source and destination nodes. With MTSP, Provide acceptable solution to overall network congestion in terms of hop count and distance, the constant updates of the hops and choosing the best path over the network.

References

  1. Jaspal jindal, Vishal Gupta, "Fuzzy Improved Genetic Approach for Route Optimization in MANET", International Journal of Advanced Research in Computer Science and Software Engineering. Vol-3, Issue 6, June 2013.
  2. P.Deepalakshmi, Dr.S.Radhakrishnan, "Ant Colony Based QOS Routing Algorithm Mobile Ahoc Network", International Journal of Recent Trends in Engineering, Vol-1, No. 1, May 2009.
  3. Gutin, G., A. Punnen, eds. 2002. Traveling Salesman Problem and Its Variations. Kluwer Academic Publishers, Dordrecht, The Netherlands.
  4. Toth, P., D. Vigo, eds. 2001. The Vehicle Routing Problem. Vol. 9. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA.
  5. Lin, S. (1965) "Computer Solutions of the Traveling Salesman Problem." Bell Syst. Journal 44, 2245-2269.
  6. Lin, S., and B. W. Kernighan. (1971) "An Effective Heuristic Algorithm for the Traveling Salesman Problem." Oper. Res. 21, 498-516.
  7. Dorigo, M., V. Maniezzo & A. Colorni (1991). "The Ant System: An Autocatalytic Optimizing Process". Technical Report No. 91-016 Revised, Politecnico di Milano, Italy
  8. Dorigo, M. & Gambardella, L., (1997) "Ant Colonies for the Traveling Salesman Problem". BioSystems, 43, 73-81.
  9. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M. N., Teller, A.H. and Teller, E., (1958) "Equations of State Calculations by Fast Computing Machines", J. Chem. Phys. 21, 1087- 1092
  10. Lin, F., Kao, C., & Hsu, C., (1993) "Applying the Genetic Approach to Simulated Annealing in Solving Some NP-Hard Problems". IEEE Transactions on Systems, Man, and Cyberspace 23, 1752-1767.
  11. Goldberg, D., Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley, 1989
  12. Bonomi, E., & Lutton, J., (1984) "The N-city Traveling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm". SIAM Review, 26 (4), 551 - 569.
  13. Matsuda, S., (1996) "Set Theoretic Comparison of Mappings of Combinatorial Optimization Problems to Hopfield Neural Networks.", Systems and Computers in Japan 27, 45-59
  14. Zar Chi Su Su Hlaing, May Aye Khine University of Computer Studies, Yangon.An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem.
  15. Miss Shweta Modi, Jitendra Prithviraj. Multiple Feasible Paths in Ant Colony Algorithm for mobile Adhoc Networks with Minimum Overhead.
  16. Vittorio Maniezzo, Luca Maria Gambardella, Fabio de Luigi .Ant Colony Optimization.
  17. Macro Dorigo,Vittorio Maniezzo and Alberto Colorni. Ant System: Optimization by a Colony of Cooperating Agents.
  18. Dorigo M. and G. Di Caro(1999).The Ant Colony Optimization Meta-Heuristic edited by D. Corne, M.Dorigo and F. Glover, New Ideas in Optimization, McGraw-Hill, 11-32.
  19. Macro Dorigo,Gianni Di Caro .Ant Colony Optimization : A New Mata-Heuristic.
  20. Keller, C. P. 1985. Multiobjective routing through space and time: The MVP and TDVP problems. Unpublished doctoral dissertation, Department of Geography, The University of Western Ontario, London, Ontario, Canada.
  21. Keller, C. P., M. Goodchild. 1988. The multiobjective vending problem: A generalization of the traveling salesman problem. Environ. Planning B: Planning Design 15 447-460
  22. Ehrgott, M. 2000. Approximation algorithms for combinatorial mul-ticriteria optimization problems. Internat. Trans. Oper. Res.7 (1) 5-31
  23. M V Narayana, G Narsimha, SSVN Sarma, "Secure- ZHLS: Secure Zone Based Hierarchical Link State Routing Protocol using Digital Signature", International Journal of Applied Engineering Research, ISSN 0973-4562 Volume 10, Number 9 (2015) pp. 22927-22940.
  24. M V Narayana, G Narsimha, SSVN Sarma, "Genetic - ZHLS Routing Protocol for Fault Tolerence and Load Balancing" Journal of Theoretical and Applied Information Technology, ISSN: 1992-8645 and E-ISSN: 1817-3195, 10th January 2016. Vol.83. No.1, pp. 72 - 80.

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2018-02-28

Issue

Volume 3, Issue 1, January-February-2018

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
M V Narayana, " Route Optimization by using Multiple Travelling Sales Person Problem in MANETs, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 3, Issue 1, pp.776-781, January-February-2018.