BeepBeep: a high accuracy acoustic ranging system using COTS mobile devices

ABSTRACT

We present the design, implementation, and evaluation of BeepBeep, a high-accuracy acoustic-based ranging system. It operates in a spontaneous, ad-hoc, and device-to-device context without leveraging any pre-planned infrastructure. It is a pure software-based solution and uses only the most basic set of commodity hardware -- a speaker, a microphone, and some form of device-to-device communication -- so that it is readily applicable to many low-cost sensor platforms and to most commercial-off-the-shelf mobile devices like cell phones and PDAs. It achieves high accuracy through a combination of three techniques: two-way sensing, self-recording, and sample counting. The basic idea is the following. To estimate the range between two devices, each will emit a specially-designed sound signal ("Beep") and collect a simultaneous recording from its microphone. Each recording should contain two such beeps, one from its own speaker and the other from its peer. By counting the number of samples between these two beeps and exchanging the time duration information with its peer, each device can derive the two-way time of flight of the beeps at the granularity of sound sampling rate. This technique cleverly avoids many sources of inaccuracy found in other typical time-of-arrival schemes, such as clock synchronization, non-real-time handling, software delays, etc. Our experiments on two common cell phone models have shown that we can achieve around one or two centimeters accuracy within a range of more than ten meters, despite a series of technical challenges in implementing the idea.

REFERENCES

• 1: Lewis Girod , Martin Lukac , Vlad Trifa , Deborah Estrin, The design and implementation of a self-calibrating distributed acoustic sensing platform, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182815]
• 2: Moustafa Youssef , Adel Youssef , Chuck Rieger , Udaya Shankar , Ashok Agrawala, PinPoint: An Asynchronous Time-Based Location Determination System, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134698]
• 3: Andy Harter , Andy Hopper , Pete Steggles , Andy Ward , Paul Webster, The anatomy of a context-aware application, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.59-68, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313476]
• 4: 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]
• 5: Kamin Whitehouse , David Culler, Calibration as parameter estimation in sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570747]
• 6: J. Sallai, G. Balogh, M. Maroti, A. Ledeczi, and B. Kusy, "Acoustic ranging in resource-constrained sensor networks,' in ICWN '04: Proceedings of the International Conference on Wireless Networks. Las Vegas, Nevada, USA: CSREA Press, June 2004.
• 7: 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]
• 8: Radu Stoleru , Tian He , John A. Stankovic , David Luebke, A high-accuracy, low-cost localization system for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098921]
• 9: Miklós Maróti , Péter Völgyesi , Sebestyén Dóra , Branislav Kusý , András Nádas , Ákos Lédeczi , György Balogh , Károly Molnár, Radio interferometric geolocation, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098920]
• 10: Radu Stoleru , Pascal Vicaire , Tian He , John A. Stankovic, StarDust: a flexible architecture for passive localization in wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182814]
• 11: M. Kushwaha, K. Molnar, J. Sallai, P. Volgyesi, M. Maroti, and A. Ledeczi, "Sensor node localization using mobile acoustic beacons," in MASS05: IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Nov. 2005.
• 12: K. D. Frampton, "Acoustic self-localization in a distributed sensor network," IEEE Sensors Journal, vol. 6, no. 1, pp. 166 -- 172, 2006.
• 13: R. J. Fontana, E. Richley, and J. Barney, "Commercialization of an ultra wideband precision asset location system," in ICUWB '03: IEEE International Conference on Ultra Wideband Systems and Technologies, Nov 2003, pp. 369--373.
• 14: {Online}. Available: http://www.betanews.com/article/Bluetooth_21_EDR_Ratified_TouchtoConnect_On_the_Way/1175023711
• 15: Mike Hazas , Christian Kray , Hans Gellersen , Henoc Agbota , Gerd Kortuem , Albert Krohn, A relative positioning system for co-located mobile devices, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067190]
• 16: David Frohlich , Allan Kuchinsky , Celine Pering , Abbe Don , Steven Ariss, Requirements for photoware, Proceedings of the 2002 ACM conference on Computer supported cooperative work, November 16-20, 2002, New Orleans, Louisiana, USA [doi>10.1145/587078.587102]
• 17: Scott Counts , Eric Fellheimer, Supporting social presence through lightweight photo sharing on and off the desktop, Proceedings of the SIGCHI conference on Human factors in computing systems, p.599-606, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985768]
• 18: Guobin Shen , Yanlin Li , Yongguang Zhang, MobiUS: enable together-viewing video experience across two mobile devices, Proceedings of the 5th international conference on Mobile systems, applications and services, June 11-13, 2007, San Juan, Puerto Rico [doi>10.1145/1247660.1247667]
• 19: P. Enge and P. Misra, "Special issue on GPS: The Global Positioning System," in Proceedings of the IEEE, January 1999, pp. 3--172.
• 20: 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]
• 21: Wiki, "Speed of sound." {Online}. Available: http://en.wikipedia.org/wiki/Speed_of_sound
• 22: James Aspnes , Tolga Eren , David K. Goldenberg , A. Stephen Morse , Walter Whiteley , Yang Richard Yang , Brian D. O. Anderson , Peter N. Belhumeur, A Theory of Network Localization, IEEE Transactions on Mobile Computing, v.5 n.12, p.1663-1678, December 2006 [doi>10.1109/TMC.2006.174]
• 23: Kamin Whitehouse , Chris Karlof , Alec Woo , Fred Jiang , David Culler, The effects of ranging noise on multihop localization: an empirical study, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 24: D. Niculescu and B. R. Badrinath, "Ad hoc positioning system (aps) using aoa," in INFOCOM '03: the 22st Annual IEEE Conference on. Computer Communications, San Francisco, CA, 2003.
• 25: P. Bahl and V. N. Padmanabhan, "Radar: An in-building rf-based user location and tracking system," in INFOCOM '00: the 19th Annual IEEE Conference on. Computer Communications. Tel-Aviv, Israel: IEEE Infocom, March 2000.
• 26: Gaetano Borriello , Alan Liu , Tony Offer , Christopher Palistrant , Richard Sharp, WALRUS: wireless acoustic location with room-level resolution using ultrasound, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067191]
• 27: BatSystem. {Online}. Available: http://www.cl.cam.ac.uk/research/dtg/research/wiki/BatSystem
• 28: V. Gerasimov , W. Bender, Things that talk: using sound for device-to-device and device-to-human communication, IBM Systems Journal, v.39 n.3-4, p.530-546, July 2000
• 29: M. Brandstein and H. Silverman, "A practical methodology for speech source localization with microphone arrays," Computer, Speech, and Language, vol. 11, no. 2, pp. 91--126, April 1997.
• 30: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 31: 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]
• 32: Yiming Ji , Saâd Biaz , Santosh Pandey , Prathima Agrawal, ARIADNE: a dynamic indoor signal map construction and localization system, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134697]
• 33: L. Girod and D. Estrin, "Robust range estimation using acoustic and multimodal sensing," in IROS '01: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 3, 2001, pp. 1312--1320.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers

General Terms:
Algorithms, Design, Performance

Keywords:
acoustic ranging, localization, proximity detection, ranging, ranging systems