Minimum Bend Shortest Rectilinear Route Discovery for a Moving Sink in a Grid Based Wireless Sensor Network

• Autorzy: Thomas Sanu , Mathew Thomaskutty

Identyfikatory

DOI

10.24425/ijet.2019.126310

• Języki publikacji: EN

Abstrakty

EN

In a rectilinear route, a moving sink is restricted to travel either horizontally or vertically along the connecting edges. We present a new algorithm that finds the shortest round trip rectilinear route covering the specified nodes in a grid based Wireless Sensor Network. The proposed algorithm determines the shortest round trip travelling salesman path in a two-dimensional grid graph. A special additional feature of the new path discovery technique is that it selects that path which has the least number of corners (bends) when more than one equal length shortest round trip paths are available. This feature makes the path more suitable for moving objects like Robots, drones and other types of vehicles which carry the moving sink. In the prosed scheme, the grid points are the vertices of the graph and the lines joining the grid points are the edges of the graph. The optimal edge set that forms the target path is determined using the binary integer programming.

Słowa kluczowe

EN

minimum bend shortest paths; travelling salesman problem; binary integer programming; edge orientation index; vertex bend index; vertex-edge incident matrix

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2019
• Tom: Vol. 65, No. 2
• Strony: 267--276
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Thomas Sanu

• Faculty of School of Technology and Applied Sciences, Mahathma Gandhi University, Kottayam, Kerala, India

autor

Mathew Thomaskutty

• Faculty of School of Technology and Applied Sciences, Mahathma Gandhi University, Kottayam, Kerala, India

Bibliografia

• [1] C. Tunca, S. Isik, M. Y. Donmez and C. Ersoy, "Distributed Mobile Sink Routing for Wireless Sensor Networks: A Survey," in IEEE Communications Surveys & Tutorials, vol. 16, no. 2, pp. 877-897, Second Quarter 2014. DOI: 10.1109/SURV.2013.100113.00293.
• [2] M. Di Francesco, S. K. Das, and G. Anastasi, “Data collection in wireless sensor networks with mobile elements: A survey,” ACM Trans. Sensor Networks, vol. 8, no. 1, pp. 1–31, 2011. DOI: 10.1145/1993042.1993049.
• [3] W. Liang, J. Luo, and X. Xu, “Prolonging network lifetime via a controlled mobile sink in wireless sensor networks,” in Global Commu -nications Conf. (GLOBECOM 2010), IEEE, 2010, pp. 1 –6. DOI: 10.1109/GLOCOM.2010.5683095.
• [4] Z. Wang, S. Basagni, E. Melachrinoudis, and C. Petrioli, “Exploiting sink mobility for maximizing sensor networks lifetime,” in Proc. of the 38th Annual Hawaii Int. Conf. on System Sciences (HICSS ’05), 2005, pp.03-06. DOI: 10.1109/HICSS.2005.259.
• [5] Huang, Hailong. (2017). Performance Improvement by Introducing Mobility in Wireless Communication Networks. eprint arXiv:1712.02436, 12/2017, 2017.
• [6] V. G. Deineko , B. Klinz , A. Tiskin , G. J. Woeginger “Four-point Conditions for the TSP,” Journal Discrete Optimization, Vol. 14 Issue C, November 2014 pp. 147-159. DOI: 10.1016/j.disopt.2014.09.003.
• [7] A. Maheshwari, J.R. Sack, and H.N. Djidjev. Link distance problems, in: J.R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pp. 519-558. Elsevier Science Publishers B.V. North Holland, Amsterdam, 2000.
• [8] C.D. Yang, O. Z. Lee and C. K. Wong, “On bends and lengths of rectilinear paths: A graph-theoretic approach”, Internat. J. Comput. Geom. Appl., 2 (1992), pp. 61−74. DOI: 10.1142/S0218195992000056.
• [9] K. L. Clarkson, S. Kapoor, and P. M. Vaidya, “Rectilinear shortest paths through polygonal obstacles in O(n(log n) 2 ) time”, In Proc. 3rd Annual ACM Sympos. Comput. Geom., pp 251−257, 1987. DOI: 10.1145/41958.41985.
• [10] S. Basagni, A. Carosi, C. Petrioli, Mobility in wireless sensor networks, in: Algorithms and Protocols for Ad Hoc and Sensor Networks, John Wiley & Sons, Inc., 2007.
• [11] D. P. Wagner, R. S. Drysdale, C. Stein An O(n 5/2 log n) algorithm for the rectilinear minimum link-distance problem in three dimensions. Comput. Geom. Theory Appl. 42(5) (2009) 376–387.
• [12] Diaby, M., “The Travelling Salesman Problem: A Linear Programming Formulation”, WSEAS Transactions on Mathematics, issue 6, vol. 6, pp. 745-754, 2007.
• [13] Pataki, G., 2003. Teaching Integer Programming formulations using the traveling salesman problem. SIAM Review 45 (1), 116–123.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).