Article

Sextant: a unified node and event localization framework using non-convex constraints

Authors:

Emin Gün SirerAuthors Info & Claims

MobiHoc '05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing

Pages 205 - 216

https://doi.org/10.1145/1062689.1062715

Published: 25 May 2005 Publication History

Abstract

Determining node and event locations is a canonical task for many wireless network applications. Yet dedicated infrastructure for determining position information is expensive, energy-consuming, and simply unavailable in many deployment scenarios. This paper presents an accurate, cheap and scalable framework, called Sextant, for determining node position and event location in sensor networks. Sextant operates by setting up and solving a system of geographic constraints based on connectivity information from the underlying communication network. Sextant achieves high accuracy by enabling non-convex constraints to be used to refine position estimates. It represents position estimates as potentially non-contiguous collections of points. This general representation enables Sextant to use _negative information_, that is, information on where a node or event is not located, to refine location estimates. Sextant unifies both node and event detection within the same general framework. It can provide high precision without dedicated localization hardware by aggressively extracting constraints from the link layer, representing areas precisely with Bézier-enclosed polygons and probability distributions, and using event detection to refine node position estimates. A compact representation and a fully distributed implementation make the framework practical for resource-limited devices. The framework has been implemented, deployed and tested on laptops, PDAs and Mica-2 motes. Physical experiments show that a large number (98%) of the nodes in a network can determine their positions based on a small number (30%) of landmark nodes and that a large number (90%) of events can be located with low median error.

References

[1]

Y.-B. Ko and N. H. Vaidya, "Location-Aided Routing in Mobile Ad Hoc Networks," in Proceedings of Computing and Networking, Dallas, TX, Oct. 1998, pp. 66--75.

Digital Library

[2]

L. Blazevic, S. Giordano, and J. L. Boudec, "Self-Organizing Wide-Area Routing," in Proceedings of World Multiconference on Systemics, Cybernetics and Informatics, Orlando, FL, July 2000.

[3]

B. Karp and H. T. Kung, "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks," in Proceedings of the International Conference on Mobile Computing and Networking, Boston, MA, Aug. 2000, pp. 243--254.

Digital Library

[4]

F. Kuhn, R. Wattenhofer, and A. Zollinger, "Worst-Case Optimal and Average-Case Efficient Geometric Ad Hoc Routing," in Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, MD, June 2003.

Digital Library

[5]

P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, "Routing with Guaranteed Delivery in Ad Hoc Wireless Networks," in Proceedings of the Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Seattle, WA, Aug. 1999.

Digital Library

[6]

R. Bischoff and R. Wattenhofer, "Analyzing Connectivity-Based Multi-Hop Ad Hoc Positioning," in Proceedings of the International Conference on Pervasive Computing and Communications, Orlando, FL, Mar. 2004, p. 165.

Digital Library

[7]

Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, "Localization From Mere Connectivity," in Proceedings of the International Conference on Mobile Computing and Networking, Annapolis, MD, June 2003, pp. 201--212.

Digital Library

[8]

D. Niculescu and B. Nath, "Ad Hoc Positioning System Using AoA," in Proceedings of IEEE INFOCOM Conference on Computer Communications, San Fransisco, CA, 2003.

[9]

------, "Ad Hoc Positioning System," in Proceedings of the IEEE Global Telecommunications Conference, San Antonio, TX, Nov. 2001, pp. 2926--2931.

[10]

A. Galstyan, B. Krishnamachari, K. Lerman, and S. Pattem, "Distributed Onlin Localization in Sensor Networks Using a Moving Target," in Proceedings of the International Symposium on Information Processing in Sensor Networks, Berkeley, CA, Apr. 2004, pp. 61--70.

Digital Library

[11]

G. Simon, M. Maroti, A. Ledeczi, G. Balogh, B. Kusy, A. Nadas, G. Pap, J. Sallai, and K. Frampton, "Sensor Network-Based Countersniper System," in Proceedings of International Conference on Embedded Networked Sensor Systems, Baltimore, MD, 2004, pp. 1--12.

Digital Library

[12]

A. Savvides, C. Han, and M. Srivastava, "Dynamic Fine-grained Localization in Ad Hoc Networks of Sensors," in Proceedings of the International Conference on Mobile Computing and Networking, Rome, Italy, July 2001, pp. 166--179.

Digital Library

[13]

R. Stoleru and J. A. Stankovic, "Probability Grid: A Location Estimation Scheme for Wireless Sensor Networks," in Proceedings of the IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, Santa Clara, CA, Oct. 2004.

[14]

K. Lorincz and M. Welsh, "A Robust, Decentralized Approach to RF-Based Location Tracking," Harvard University, Cambridge, MA, Tech. Rep. TR-19-04, 2004.

[15]

J. Chen and R. E. Hudson, "Maximum-likelihood source localization and unknown sensor location estimation for wideband signals in the near-field," IEEE Transactions on Signal Processing, vol. 50, pp. 1843--1854, Aug. 2002.

Digital Library

[16]

R. Brooks, C. Griffin, and D. Friedlander, "Self-Organized Distributed Sensor Network Entity Tracking," International Journal of High Performance Computing Applications, vol. 16, no. 5, Aug. 2002.

[17]

F. Kuhn, T. Moscibroda, and R. Wattenhofer, "Unit Disk Graph Approximation," in Proceedings of ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, PA, Oct. 2004.

Digital Library

[18]

T. Moscibroda, R. O'Dell, M. Wattenhofer, and R. Wattenhofer, "Virtual Coordinates for Ad Hoc and Sensor Networks," in Proceedings of ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, PA, Oct. 2004.

Digital Library

[19]

P. Bahl and V. N. Padmanabhan, "RADAR: An In-Building RF-Based User Location and Tracking System," in Proceedings of IEEE INFOCOM Conference on Computer Communications, 2000, pp. 775--784.

[20]

C. Savarese, J. Rabay, and K. Langendoen, "Robust Positioning Algorithms for Distributed Ad Hoc Wireless Sensor Networks," in Proceedings of USENIX Annual Technical Conference, Monterey, CA, June 2002, pp. 317--327.

Digital Library

[21]

D. Assaf, "The Sensitivity of Spline Functions on Triangulations to Vertex Perturbation," Ph.D. dissertation, Vanderbilt University, May 1998.

[22]

J. M. Kahn, R. H. Katz, and K. S. J. Pister, "Next Century Challenges: Mobile Networking for "Smart Dust"," in Proceedings of the International Conference on Mobile Computing and Networking, Seattle, WA, Aug. 1999, pp. 271--278.

Digital Library

[23]

J. Hightower and G. Boriello, "Location Systems for Ubiquitous Computing," IEEE Computer, vol. 34, no. 8, pp. 57--66, Aug. 2001.

Digital Library

[24]

A. Ward, A. Jones, and A. Hopper, "A New Location Technique for the Active Office," IEEE Personal Communications, vol. 4, no. 5, pp. 42--47, Oct. 1997.

[25]

N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, "The Cricket Location-support System," in Proceedings of the International Conference on Mobile Computing and Networking, Boston, MA, Aug. 2000, pp. 32--43.

Digital Library

[26]

D. Niculescu and B. Nath, "VOR Basestations for Indoor 802.11 Positioning," in Proceedings of the International Conference on Mobile Computing and Networking, Philadelphia, PA, Sept. 2004.

Digital Library

[27]

N. Bulusu, J. Heidemann, and D. Estrin, "GPS-Less Low Cost Outdoor Localization for Very Small Devices," in Proceedings of IEEE Personal Communications, May 2000, pp. 28--34.

[28]

S. Capkun, M. Hamdi, and J.-P. Hubaux, "GPS-Free Positioning in Mobile Ad Hoc Networks," in Proceedings of HICSS, Jan. 2001, pp. 3481--3490.

Digital Library

[29]

L. Doherty, K. S. J. Pister, and L. E. Ghaoui, "Convex Position Estimation in Wireless Sensor Networks," in Proceedings of IEEE INFOCOM Conference on Computer Communications, vol. 3, Anchorage, AK, Apr. 2001, pp. 1655--1663.

[30]

A. Savvides, H. Park, and M. B. Srivastava, "The Bits and Flops of the N-hop Multilateration Primitive for Node Localization Problems," in Proceedings of the Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, Sept. 2002.

Digital Library

[31]

F. Zhao, J. Liu, J. Liu, L. Guibas, and J. Reich, "Collaborative Signal and Information Processing: An Information Directed Approach," Proceedings of the IEEE, vol. 91, no. 8, pp. 1199--1209, Aug. 2003.

[32]

J. Sallai, G. Balogh, M. Maroti, and A. Ledeczi, "Acoustic Ranging in Resource Constrained Sensor Networks," Vanderbilt University, Nashville, TN, Tech. Rep. ISIS-04-504, 2004.

[33]

T. He, S. Krishnamurthy, J. A. Stankovic, T. Abdelzaher, L. Luo, R. Stoleru, T. Yan, L. Gu, J. Hui, and B. Krogh, "Energy-Efficient Surveillance System Using Wireless Sensor Networks," in Proceedings of the International Conference on Mobile Systems, Applications, and Services, Boston, MA, June 2004.

Digital Library

[34]

G. Farin, Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. 1em plus 0.5em minus 0.4em Academic Press, 1988.

Digital Library

[35]

J. Zhao and R. Govindan, "Understanding Packet Delivery Performance In Dense Wireless Sensor Networks," in Proceedings of the ACM Sensys, Los Angeles, CA, Nov. 2003.

Digital Library

Cited By

Gencer ABasu SEyal Ivan Renesse RSirer E(2018)Decentralization in Bitcoin and Ethereum NetworksFinancial Cryptography and Data Security10.1007/978-3-662-58387-6_24(439-457)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-3-662-58387-6_24
Ali KJaved THassanein HOteafy S(2016)Non-audible acoustic communication and its application in indoor location-based services2016 IEEE Wireless Communications and Networking Conference10.1109/WCNC.2016.7565076(1-6)Online publication date: Apr-2016
https://doi.org/10.1109/WCNC.2016.7565076
Ali KNaqvi I(2016)EveTrack: An event localization and tracking scheme for WSNs in dynamic environments2016 IEEE Wireless Communications and Networking Conference10.1109/WCNC.2016.7564802(1-6)Online publication date: Apr-2016
https://doi.org/10.1109/WCNC.2016.7564802
Show More Cited By

Index Terms

Sextant: a unified node and event localization framework using non-convex constraints
1. Networks
  1. Network protocols

Recommendations

A hybrid wireless sensor network framework for range-free event localization

In event localization, wireless sensors try to locate the source of an event from its emitted power. This is more challenging than sensor localization as the power level at the source of an event is neither predictable with precision nor can be ...
Node Localization Algorithm Based on Mobile Anchor in Wireless Sensor Networks
ICIT '17: Proceedings of the 2017 International Conference on Information Technology

Node localization is one of the prerequisites for the applications of Wireless Sensor Networks. To solve the high overhead problem caused by the requirement for the anchor node density, mobile anchor node(MA) is used instead of the static anchor node. ...
Asymmetric Event-Driven Node Localization in Wireless Sensor Networks

Localization of wireless sensor nodes has long been regarded as a problem that is difficult to solve, especially when considering characteristics of real-world environments. This paper formally describes, designs, implements, and evaluates a novel ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing

May 2005

470 pages

ISBN:1595930043

DOI:10.1145/1062689

General Chair:
P. R. Kumar
University of Illinois at Urbana-Champaign, Urbana, IL
,
Program Chairs:
Andrew T. Campbell
Columbia University
,
Rogert Wattenhofer
ETH Zurich, Switzerland

Copyright © 2005 ACM.

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MobiHoc05

Sponsor:

MobiHoc05: The Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing 2005

May 25 - 27, 2005

IL, Urbana-Champaign, USA

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
667
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gencer ABasu SEyal Ivan Renesse RSirer E(2018)Decentralization in Bitcoin and Ethereum NetworksFinancial Cryptography and Data Security10.1007/978-3-662-58387-6_24(439-457)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-3-662-58387-6_24
Ali KJaved THassanein HOteafy S(2016)Non-audible acoustic communication and its application in indoor location-based services2016 IEEE Wireless Communications and Networking Conference10.1109/WCNC.2016.7565076(1-6)Online publication date: Apr-2016
https://doi.org/10.1109/WCNC.2016.7565076
Ali KNaqvi I(2016)EveTrack: An event localization and tracking scheme for WSNs in dynamic environments2016 IEEE Wireless Communications and Networking Conference10.1109/WCNC.2016.7564802(1-6)Online publication date: Apr-2016
https://doi.org/10.1109/WCNC.2016.7564802
Huang HZhou JLi WZhang JZhang XHou G(2016)Wearable indoor localisation approach in Internet of ThingsIET Networks10.1049/iet-net.2016.00075:5(122-126)Online publication date: 1-Sep-2016
https://doi.org/10.1049/iet-net.2016.0007
Sinha KGhosh SSinha B(2015)IntroductionWireless Networks and Mobile Computing10.1201/b19361-2(1-40)Online publication date: 22-Oct-2015
https://doi.org/10.1201/b19361-2
He Y(2014)A Localization Algorithm of Nodes Based on Hypersphere Granular Computing in Wireless Sensor NetworksAdvanced Materials Research10.4028/www.scientific.net/AMR.998-999.1390998-999(1390-1393)Online publication date: Jul-2014
https://doi.org/10.4028/www.scientific.net/AMR.998-999.1390
Yuan ZChen SGhinea GMuntean G(2014)User Quality of Experience of Mulsemedia ApplicationsACM Transactions on Multimedia Computing, Communications, and Applications10.1145/266132911:1s(1-19)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1145/2661329
Prasad MRussell MHammond T(2014)Designing Vibrotactile Codes to Communicate Verb PhrasesACM Transactions on Multimedia Computing, Communications, and Applications10.1145/263728911:1s(1-21)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1145/2637289
Ghinea GTimmerer CLin WGulliver S(2014)MulsemediaACM Transactions on Multimedia Computing, Communications, and Applications10.1145/261799411:1s(1-23)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1145/2617994
Luque FGalloso IFeijoo CMartín CCisneros G(2014)Integration of Multisensorial Stimuli and Multimodal Interaction in a Hybrid 3DTV SystemACM Transactions on Multimedia Computing, Communications, and Applications10.1145/261799211:1s(1-22)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1145/2617992
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten