PinPoint: An Asynchronous Time-Based Location Determination System

ABSTRACT

This paper presents the design, implementation and evaluation of the PinPoint location determination system. PinPoint is a distributed algorithm that enables a set of $n$ nodes to determine the RF propagation delays between every pair of nodes, from which the inter-node distances and hence the spatial topology can be readily determined. PinPoint does not require any calibration of the area of interest and thus is rapidly deployable. Unlike existing time-of-arrival techniques, PinPoint does not require an infrastructure of accurate clocks (e.g., GPS) nor does it incur the o(n²) message exchanges of "echoing" techniques. PinPoint can work with nodes having inexpensive crystal oscillator clocks, and incurs a constant number of message exchanges per node to determine the location of $n$ nodes. Each node's clock is assumed to run reliably but asynchronously with respect to the other nodes, i.e., they can run at slightly different rates because of hardware (oscillator) inaccuracies. PinPoint provides a mathematical way to compensate for these clock differences in order to arrive at a very precise timestamp recovery that in turn leads to a precise distance determination. Moreover, each node is able to determine the clock characteristics of other nodes in its neighborhood allowing network synchronization. We present a prototype implementation for PinPoint and discusses the practical issues in implementing the mathematical framework and how PinPoint handles the different sources of error affecting its accuracy. Evaluation of the prototype in typical indoor and outdoor environments shows that PinPoint gives an average accuracy of four to six feet, in different environments, allowing PinPoint to support accurate rapidly deployable localization scenarios.

REFERENCES

• 1: http://www.atheros.com.
• 2: Ronald Azuma, Tracking requirements for augmented reality, Communications of the ACM, v.36 n.7, p.50-51, July 1993 [doi>10.1145/159544.159581]
• 3: P. Bahl and V. N. Padmanabhan. RADAR: An In-Building RF-based User Location and Tracking System. In IEEE Infocom 2000, volume 2, pages 775--784, March 2000.
• 4: N. Bulusu, J. Heidemann, and D. Estrin. Gps-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine, 7(5):28--34, October 2000.
• 5: Srdjan Čapkun , Maher Hamdi , Jean-Pierre Hubaux, GPS-free Positioning in Mobile Ad Hoc Networks, Cluster Computing, v.5 n.2, p.157-167, April 2002 [doi>10.1023/A:1013933626682]
• 6: Guanling Chen , David Kotz, A Survey of Context-Aware Mobile Computing Research, Dartmouth College, Hanover, NH, 2000
• 7: X. Cheng, A. Thaeler, G. Xue, and D. Chen. TPS: A Time-Based Positioning Scheme For Outdoor Sensor Networks. In Proceedings of IEEE Infocom, volume 4, pages 2685--2696, 2004.
• 8: L. Doherty, K. Pister, and L. E. Ghaoui. Convex Position Estimation in Wireless Sensor Networks. In Proceedings of IEEE Infocom, volume 3, pages 1655--1663, 2001.
• 9: G. Durisi and G. Romano. Simulation analysis and performance evaluation of an UWB system in indoor multipath channel. In IEEE Conference on Ultra Wideband Systems and Technologies, pages 255--258, 2002.
• 10: P. Enge and P. Misra. Special issue on GPS: The Global Positioning System. Proceedings of the IEEE, 87(1):3--172, January 1999.
• 11: R. J. Fontana and S. J. Gunderson. Ultra-wideband precision asset location system. In IEEE Conference on Ultra Wideband Systems and Technologies, pages 147--150, May 2002.
• 12: R. J. Fontana, E. Richley, and J. Barney. Commercialization of an ultra wideband precision asset location system. In IEEE Conference on Ultra Wideband Systems and Technologies, pages 369--373, November 2003.
• 13: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 14: X. Ji. Sensor Positioning in Wireless Ad-hoc Sensor Networks with Multidimensional Scaling. In Proceedings of IEEE InfoCom, volume 4, pages 2652--2661, 2004.
• 15: P. Krishnan, A. Krishnakumar, W. H. Ju, C. Mallows, and S. Ganu. A System for LEASE: Location Estimation Assisted by Stationary Emitters for Indoor RF Wireless Networks. In IEEE Infocom, volume 2, pages 1001--1011, March 2004.
• 16: John Krumm , Steve Harris , Brian Meyers , Barry Brumitt , Michael Hale , Steve Shafer, Multi-Camera Multi-Person Tracking for EasyLiving, Proceedings of the Third IEEE International Workshop on Visual Surveillance (VS'2000), p.3, July 01-01, 2000
• 17: Andrew M. Ladd , Kostas E. Bekris , Algis Rudys , Lydia E. Kavraki , Dan S. Wallach , Guillaume Marceau, Robotics-based location sensing using wireless ethernet, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570674]
• 18: Julio C. Navas , Tomasz Imielinski, GeoCast—geographic addressing and routing, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.66-76, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262132]
• 19: D. Niculescu and B. Nath. Ad-hoc Positioning System (APS). In IEEE GlobeCom, volume 5, pages 2926--2931, 2001.
• 20: D. Niculescu and B. Nath. Ad Hoc Positioning System (APS) Using AoA. In Proceedings of IEEE Infocom, volume 3, pages 1734--1743, 2003.
• 21: Robert J. Orr , Gregory D. Abowd, The smart floor: a mechanism for natural user identification and tracking, CHI '00 extended abstracts on Human factors in computing systems, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/633292.633453]
• 22: Venkata N. Padamanabban , Lealkshminarayanan Subramanian, Determining the geographic location of Internet hosts, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.324-325, June 2001, Cambridge, Massachusetts, United States
• 23: 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]
• 24: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 25: 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]
• 26: 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]
• 27: Curt Schurgers , Gautam Kulkarni , Mani B. Srivastava, Distributed On-Demand Address Assignment in Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.10, p.1056-1065, October 2002 [doi>10.1109/TPDS.2002.1041881]
• 28: S. Tekinay. Special issue on Wireless Geolocation Systems and Services. IEEE Communications Magazine, April 1998.
• 29: The Institute of Electrical and Electronics Engineers, Inc. IEEE Standard 802.11 - Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications. 1999.
• 30: Roy Want , Andy Hopper , Veronica Falcão , Jonathan Gibbons, The active badge location system, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.91-102, Jan. 1992 [doi>10.1145/128756.128759]
• 31: M. Welborn. System considerations for ultra-wideband wireless networks. In Proceedings of IEEE Radio and Wireless Conference (RAWCON), pages 5--8, 2001.
• 32: Jay Webr , Colin Lanzl, Designing a positioning systems for finding things and people indoors, IEEE Spectrum, v.35 n.9, p.71-78, Sept. 1998 [doi>10.1109/6.715187]
• 33: A. Youssef, M. Youssef, M. Younis, and A. Agrawala. The Overlapped K-hop (OK) Clustering Algorithm. Technical Report CS-TR-4735, Department of Computer Science, University of Maryland College Park, July 2005.
• 34: Moustafa Youssef , Ashok Agrawala, The Horus WLAN location determination system, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067193]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
location determination, ranging techniques, rapidly deployable location determination, time-of-arrival location determination