Range-free localization schemes for large scale sensor networks

ABSTRACT

Wireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of the hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point-to-point distance estimates. Because coarse accuracy is sufficient for most sensor network applications, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. In this paper, we present APIT, a novel localization algorithm that is range-free. We show that our APIT scheme performs best when an irregular radio pattern and random node placement are considered, and low communication overhead is desired. We compare our work via extensive simulation, with three state-of-the-art range-free localization schemes to identify the preferable system configurations of each. In addition, we study the effect of location error on routing and tracking performance. We show that routing performance and tracking accuracy are not significantly affected by localization error when the error is less than 0.4 times the communication radio radius.

REFERENCES

• 1: P. Bahl and V. N. Padmanabhan, RADAR: An In-Building RF-Based User Location and Tracking System, In Proceedings of the IEEE INFOCOM '00, March 2000.
• 2: J. Beutel, Geolocation in a PicoRadio Environment, M.S. Thesis, ETH Zurich, Electronics Laboratory, Dec. 1999.
• 3: 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.
• 4: N. Bulusu, J. Heidemann and D. Estrin, Density Adaptive Algorithms for Beacon Placement in Wireless Sensor Networks, In IEEE ICDCS '01, Phoenix, AZ, April 2001.
• 5: Nirupama Bulusu , John Heidemann , Deborah Estrin , Tommy Tran, Self-configuring localization systems: Design and Experimental Evaluation, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.24-60, February 2004 [doi>10.1145/972627.972630]
• 6: J. Caffery, Jr. A New Approach to the Geometry of TOA Location, In IEEE Vehicular Technology Conference (VTC), Boston, Mass, September 2000.
• 7: 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
• 8: L. Doherty, L. E. Ghaoui and K. S. J. Pister, Convex Position Estimation in Wireless Sensor Networks, In Proceedings of the IEEE INFOCOM '01, Anchorage, AK, April 2001.
• 9: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 10: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin and S. Wicker, Complex Behavior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks <http://lecs.cs.ucla.edu/Publications/papers/Deepak-Empirical.pdf>, Technical Report UCLA/CSD-TR 02-0013, 2002.
• 11: L. Girod and D. Estrin, Robust Range Estimation using Acoustic and Multimodal Sensing, In Proceedings of IROS '01, Maui, Hawaii, October 2001.
• 12: 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]
• 13: Tian He , John A. Stankovic , Chenyang Lu , Tarek Abdelzaher, SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.46, May 19-22, 2003
• 14: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 15: J. Hightower, G. Boriello and R. Want, SpotON: An indoor 3D Location Sensing Technology Based on RF Signal Strength, University of Washington CSE Report #2000-02-02, February 2000.
• 16: X. Hong, K. Xu, and M. Gerla, Scalable routing protocols for mobile ad hoc networks, IEEE Network magazine, vol 16, No. 4, 2002.
• 17: 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]
• 18: L.Kleinrock and J.Slivester, Optimum transmission radii for packet radio networks or why six is a magic number, In proceedings of national Telecomm conference, Pages 4.3.1--4.3.5, 1978
• 19: 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]
• 20: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 21: MICA Sensor Board Information, http://www.xbow.com
• 22: R. Nagpal, Organizing a Global Coordinate System from Local Information on an Amorphous Computer, A.I. Memo 1666, MIT A.I. Laboratory, August 1999.
• 23: R. Nagpal, H. Shrobe, J. Bachrach, Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network, In the 2nd International Workshop on Information Processing in Sensor Networks (IPSN '03), Palo Alto, April, 2003.
• 24: 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]
• 25: D. Nicolescu and B. Nath, Ad-Hoc Positioning Systems (APS), In Proceedings of IEEE GLOBECOM '01, November 2001.
• 26: D. Niculescu and B. Nath, DV Based Positioning in Ad hoc Networks, In Journal of Telecommunication Systems, 2003.
• 27: D. Niculescu and B. Nath, Ad Hoc Positioning System (APS) using AoA, INFOCOM'03, San Francisco, CA,2003
• 28: 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]
• 29: 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
• 30: 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]
• 31: 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]
• 32: 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]
• 33: B. H. Wellenhoff, H. Lichtenegger and J. Collins, Global Positions System: Theory and Practice, Fourth Edition. Springer Verlag, 1997.
• 34: 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]
• 35: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 36: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance for 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.958498]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
localization, location discovery, positioning, sensor networks