skip to main content
10.1145/1065870.1065875acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
Article

Tolerance of localization imprecision in efficiently managing mobile sensor databases

Published: 12 June 2005 Publication History

Abstract

Query processing on mobile sensor networks requires efficient indexing and partitioning of the data space to support efficient routing as the network scales up. Building an index structure in an ad hoc manner requires two operations: localization to discover the sensor's position; and assignment to each sensor of the appropriate data space partition. We propose a fully distributed, cost-effective scheme, which integrates localization, indexing and data space management for sensors. We show that without affecting the overall performance of routing and query processing, our localization scheme, which involves merely local interaction, is performed with significantly less message and time cost than traditional approaches.

References

[1]
Xin Li, Y.J.K., Ramesh Govindan, Wei Hong. Multi-dimensional Range Queries in Sensor Networks. in Sensys'03. 2003. Los Angeles, CA.
[2]
Thomas Moscibroda, R.O.D., Mirjam Wattenhofer, Roger Wattenhofer. Virtual Coordinates for Ad hoc Sensor Networks. in DIALM-POMC. 2004. Philadelphia, Pennsylvania.
[3]
Aram Galstyan, B.K., Kristina Lerman, and Sundeep Pattern. Distributed Online Localization in Sensor Networks Using a Moving Target. 2004.
[4]
Volker Gaede, O.G., Multidimensional access methods. ACM Comp. Surveys (CSUR), 1998. 30(2): 170 -- 231.
[5]
Krishna Kant Chintalapudi, A.D., Ramesh Govindan, Gaurav Sukhatme., On the Feasibility of Ad-Hoc Localization Systems, in Techinal Report. 2003, Computer Science Department, University of Southern California: Los Angeles, CA.
[6]
S. Roumeliotis, G.B. Collective Localization: a Distributed Kalman Filter Approach. in Proc. IEEE ICRA. 1999. San Francisco, CA.
[7]
Srdan Capkun, M.H., Jean-Pierre Hubaux, GPS-free positioning in mobile Ad-Hoc networks. 2001.
[8]
Andreas Savvides, C.-C.H.a.M.B.S. Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors. in ACM SIGMOBILE. 2001. Rome, Italy.
[9]
Christopher Taylor, A.R., Jonathan Bachrach, and Howard Shrobe, Simultaneous localization and tracking in an ad hoc sensor network. 2005.
[10]
Whitehouse, C.D., The design of Calamari: an Ad-hoc Localization System for Sensor Networks. 2002, University of California at Berkeley.
[11]
A. Savvides, W., Garber, R. L. Moses and M. B. Srivastava, An Analysis of Error Inducing Parameters in Multihop Sensor Node Localization. IEEE Transactions on Mobile Computing, To appear.
[12]
Aris M. Ouksel, P.S., The Interpolation-Based Grid File. PODS1985, 90--105, 1985.
[13]
Aris M. Ouksel, O.M. The Nested Interpolation Based Grid File. in Symposium on Mathematical Fundamentals of Database Systems (MFDBS) 173--187. 1991.
[14]
Aris M. Ouksel, O.M., A Robust and Efficient Spatial Data Structure. Acta Informatica, 1992. 29(4).
[15]
Aris M. Ouksel, G.M. G-Grid: A Class of Scalable and Self-organizing Data Structures for Multi-dimensional quering and content routing in P2P network. in the Second International Workshop on Agents and Peer-to-Peer Computing (AP2PC'2003). 2003. Melbourne: Australia.
[16]
Dragos Niculescu, B.N. Ad Hoc Positioning System. in IEEE Globecom. 2001.
[17]
A. Savvides, H.P., M. B. Srivastava. The bits and flops of the N-hop multilateration primitive for node localization problems. in First ACM International Workshop on Wireless Sensor Networks and Application (WSNA). 2002. Atlanta, GA.
[18]
Koen Langendoen, N.R., Distributed localization in wireless sensor networks: a quantitative comparison. Computer Networks: The International Journal of Computer and Telecommunications Networking, 2003. 43(3): p. 499--518.
[19]
Lin Xiao, A.M.Ouksel., Query Processing in Sensor Databases: A Novel Approach, in CISORS-TECHREPORT-2005-2. 2005, University of Illinois at Chicago, Department of Information and Decision Sciences.
[20]
Andreas Savvides, W.G., Sachin Adlakha, Randolph Moses and Mani B. Strivastava. On the Error Characteristics of Multihop Node Localization in Ad-Hoc Sensor Networks. in Proceedings of the Second International Workshop on Information Processing in Sensor Networks (IPSN'03). 2003. Palo Alto, CA.
[21]
Chris Savarese, J.R., Koen Langendoen. Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks. in Proceedings of the General Track: 2002 USENIX Technical Conference. 2002.
[22]
K. Whitehouse, D.C. Calibration as a Parameter Estimation Problem in Sensor Network. in Proc. ACM Workshop on Sensor Networks and Applications. 2002. Atlanta, GA.
[23]
Karim Seada, A.H., Ramesh Govindan. On the effect of localization errors on geographic face routing in sensor networks. in Proceedings of the third international symposium on Information processing in sensor networks.Poster Session. 2004. Berkeley, California.
[24]
S. Ratnasamy, P.F., M. Handley, R. Karp, and S. Shenker. A Scalable Content-Addressable Network. in Proc. of the ACM SIGCOMM. 2001. San Diego, CA.
[25]
I. Stoica, R.M., D. Karger, M. F. Kaashoek and H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. in Proceedings of the ACM SIGCOMM. 2001. San Diego, CA.
[26]
S. Ratnasamy, B.K., L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker. GHT: A Geographic Hash Table for Data-Centric Storage. in Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications. 2002. Atlanta, GA.

Cited By

View all
  • (2010)Peer-to-Peer Data Clustering in Self-Organizing Sensor NetworksIntelligent Techniques for Warehousing and Mining Sensor Network Data10.4018/978-1-60566-328-9.ch009(179-212)Online publication date: 2010
  • (2010)Dynamic multiroot, multiquery processing based on data sharing in sensor networksACM Transactions on Sensor Networks10.1145/1754414.17544216:3(1-38)Online publication date: 24-Jun-2010
  • (2010)Self-Organizing Mobile Mesh Networks with Peer-to-Peer Routing and Information Search ServicesProceedings of the 2010 Third International Conference on Advances in Mesh Networks10.1109/MESH.2010.14(17-22)Online publication date: 18-Jul-2010
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiDE '05: Proceedings of the 4th ACM international workshop on Data engineering for wireless and mobile access
June 2005
108 pages
ISBN:1595930884
DOI:10.1145/1065870
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. data space partitioning
  2. integrated scheme
  3. localization
  4. wireless network sensor database

Qualifiers

  • Article

Conference

MobiDe05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 23 of 59 submissions, 39%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2010)Peer-to-Peer Data Clustering in Self-Organizing Sensor NetworksIntelligent Techniques for Warehousing and Mining Sensor Network Data10.4018/978-1-60566-328-9.ch009(179-212)Online publication date: 2010
  • (2010)Dynamic multiroot, multiquery processing based on data sharing in sensor networksACM Transactions on Sensor Networks10.1145/1754414.17544216:3(1-38)Online publication date: 24-Jun-2010
  • (2010)Self-Organizing Mobile Mesh Networks with Peer-to-Peer Routing and Information Search ServicesProceedings of the 2010 Third International Conference on Advances in Mesh Networks10.1109/MESH.2010.14(17-22)Online publication date: 18-Jul-2010
  • (2008)Scalable multi-dimensional range queries and routing in data-centric sensor networksProceedings of the 3rd international conference on Scalable information systems10.5555/1459693.1459726(1-9)Online publication date: 4-Jun-2008
  • (2008)Multidimensional Range Query and Load Balancing in Wireless Ad Hoc and Sensor NetworksProceedings of the 2008 Eighth International Conference on Peer-to-Peer Computing10.1109/P2P.2008.27(205-214)Online publication date: 8-Sep-2008
  • (2007)W*-Grid: A Robust Decentralized Cross-layer Infrastructure for Routing and Multi-Dimensional Data Management in Wireless Ad-Hoc Sensor NetworksSeventh IEEE International Conference on Peer-to-Peer Computing (P2P 2007)10.1109/P2P.2007.44(159-166)Online publication date: Sep-2007
  • (2006)Scalable Self-Configuring Integration of Localization and Indexing in Wireless Ad-Hoc Sensor NetworksProceedings of the 7th International Conference on Mobile Data Management10.1109/MDM.2006.136Online publication date: 10-May-2006
  • (2006)W_gridProceedings of the 2006 international conference on Frontiers of High Performance Computing and Networking10.1007/11942634_40(377-386)Online publication date: 4-Dec-2006
  • (2005)Zone sharingProceedings of the 2nd international workshop on Data management for sensor networks10.1145/1080885.1080890(21-26)Online publication date: 30-Aug-2005

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media