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

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: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 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: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 4: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 5: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 6: Regina Bischoff , Roger Wattenhofer, Analyzing Connectivity-Based Multi-Hop Ad-hoc Positioning, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom'04), p.165, March 14-17, 2004
• 7: Yi Shang , Wheeler Ruml , Ying Zhang , Markus P. J. Fromherz, Localization from mere connectivity, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778439]
• 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: Aram Galstyan , Bhaskar Krishnamachari , Kristina Lerman , Sundeep Pattem, Distributed online localization in sensor networks using a moving target, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984632]
• 11: Gyula Simon , Miklós Maróti , Ákos Lédeczi , György Balogh , Branislav Kusy , András Nádas , Gábor Pap , János Sallai , Ken Frampton, Sensor network-based countersniper system, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031497]
• 12: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 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.
• 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: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Unit disk graph approximation, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022634]
• 18: Thomas Moscibroda , Regina O'Dell , Mirjam Wattenhofer , Roger Wattenhofer, Virtual coordinates for ad hoc and sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022633]
• 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: Chris Savarese , Jan M. Rabaey , Koen Langendoen, Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.317-327, June 10-15, 2002
• 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 , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 23: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 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: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 26: Dragoş Niculescu , Badri Nath, VOR base stations for indoor 802.11 positioning, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023727]
• 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 , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 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: Andreas Savvides , Heemin Park , Mani B. Srivastava, The bits and flops of the n-hop multilateration primitive for node localization problems, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570755]
• 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: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990096]
• 34: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 35: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Experimentation, Measurement

Keywords:
Bézier, SEXTANT, event localization, motes, node localization, positioning