Spatial Query Localization Method in Limited Reference Point Environment

Authors: Victor Krebss

Abstract:

Task of object localization is one of the major challenges in creating intelligent transportation. Unfortunately, in densely built-up urban areas, localization based on GPS only produces a large error, or simply becomes impossible. New opportunities arise for the localization due to the rapidly emerging concept of a wireless ad-hoc network. Such network, allows estimating potential distance between these objects measuring received signal level and construct a graph of distances in which nodes are the localization objects, and edges - estimates of the distances between pairs of nodes. Due to the known coordinates of individual nodes (anchors), it is possible to determine the location of all (or part) of the remaining nodes of the graph. Moreover, road map, available in digital format can provide localization routines with valuable additional information to narrow node location search. However, despite abundance of well-known algorithms for solving the problem of localization and significant research efforts, there are still many issues that currently are addressed only partially. In this paper, we propose localization approach based on the graph mapped distances on the digital road map data basis. In fact, problem is reduced to distance graph embedding into the graph representing area geo location data. It makes possible to localize objects, in some cases even if only one reference point is available. We propose simple embedding algorithm and sample implementation as spatial queries over sensor network data stored in spatial database, allowing employing effectively spatial indexing, optimized spatial search routines and geometry functions.

Keywords: Intelligent Transportation System, Sensor Network, Localization, Spatial Query, GIS, Graph Embedding.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1074279

References:

[1] David K. Goldenberg , Arvind Krishnamurthy , Wesley C. Maness , Yang Richard , Yang Anthony Young , A. Stephen Morse , Andreas Savvides , Brian D. O. Anderson. (2005). Network Localization in Partially Localizable Networks. in Proceedings of IEEE INFOCOM, pp 313 - 326.
[2] Thomas Locher, Pascal Von Rickenbach and Roger Wattenhofer. (2008). Sensor networks continue to puzzle: Selected open problems. In Proc. 9th Internat. Conf. Distributed Computing and Networking (ICDCN).
[3] Spatial Queries over Sensor Networks (2005). Amir Soheili, Vana Kalogeraki, Dimitrios Gunopulos. In Proceeding: GIS '05 Proceedings of the 13th annual ACM international workshop on Geographic information systems, pages 61 - 70, ACM New York, NY, USA 2005
[4] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher. Range-free localization schemes in large scale sensor networks. In Proceedings of the Ninth International Conference on Mobile Computing and Networking (Mobicom), pages 81-95, San Diego, CA, Sept. 2003.
[5] Paramvir Bahl and Venkata N. Padmanabhan. (2000). RADAR: an inbuilding RF-based user location and tracking system. pp. 775 - 784.
[6] Chengdu Huang , Brain M. Blum , Advsalahuddinahmed , John A. Stankovic , Tarek Abdelzaher. (2003). Range-Free Localization Schemes for Large Scale Sensor Networks. Department of Computer Science, University of Virginia.
[7] James Newsome, Dawn Song. (2003). Graph Embedding for Routing and Data-Centric Storage in Sensor Networks Without Geographic Information. In SenSys '03: Proceedings of the 1st international conference on Embedded networked sensor systems (2003), pp. 76-88.
[8] James Aspnes, David Goldenberg, and Yang Richard Yang. On the computational complexity of sensor network localization. (2004). Proceedings. Lecture Notes in Computer Science 3121, Springer-Verlag, pp. 32-44.
[9] TRANSACTIONS ON MOBILE COMPUTING, DECEMBER 2005 1 A Theory of Network Localization J. Aspnes, T. Eren Member, IEEE D.K. Goldenberg Student Member, IEEE, A. S. Morse Fellow, IEEE W. Whiteley, Y. R. Yang Member, IEEE, B. D. O. Anderson Fellow, IEEE, P. N. Belhumeur Fellow, IEEE p-p 4-7.
[10] Yunhao Liu, Zheng Yang (2010). Location, Localization, and Localizability Location-awareness Technology for Wireless Networks. Springer New York Dordrecht Heidelberg London, pages 112-114.
[11] Craig Gotsman, Yehuda Koren. (2005). Distributed Graph Layout for Sensor Networks. Journal of Graph Algorithms and Applications vol. 9, no. 1.
[12] ESRI Shapefile Technical Description An ESRI White PaperÔÇöJuly 1998.
[13] J.B. Saxe. (1979). Embeddability of weighted graphs in k-space is strongly NP-hard. In Proceedings of the 17th Allerton Conference in Communications, Control and Computing, pages 480-489.
[14] Gerhard J. Woeginger. (2003). Exact algorithms for NP-hard problems: A survey, Combinatorial Optimization - Eureka, You Shrink!, LNCS, pp. 185ÔÇö207.
[15] Oracle Spatial User-s Guide and Reference, 10g Release 2 (10.2) B14255-03 Copyright ┬® 1999, 2006, Oracle. All rights reserved. Primary Author: Chuck Murray.
[16] J. Zhang, M. Zhu, D. Papadias, Y. Tao, and D. L. Lee. Location-based Spatial Queries. In SIGMOD Conference, pages 443-454, 2003.