Range-free localization and its impact on large scale sensor networks

ABSTRACT

With the proliferation of location dependent applications in sensor networks, location awareness becomes an essential capability of sensor nodes. 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 provide insight into the impact of localization accuracy on various location dependent applications and suggestions on improving their performance in the presence of such inaccuracy.

REFERENCES

• 1: Bahl, P. and Padmanabhan, V. N. 2000. RADAR: An in-building RF-based user location and tracking system. In Proceedings of the IEEE INFOCOM '00.
• 2: Beutel, J. 1999. Geolocation in a picoRadio environment, M.S. Thesis, ETH Zurich, Electronics Laboratory.
• 3: Blum, B., Nagaraddi, P., Wood, A., Abdelzaher, T. F., Son, S., and Stankovic, J. A. 2003. In Proceedings of Mobisys 2003, San Francisco, CA.
• 4: Bulusu, N., Heidemann, J., and Estrin, D. 2000. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine 7, 5, 28--34.
• 5: Adaptive Beacon Placement, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.489, April 16-19, 2001
• 6: 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]
• 7: Caffery, J. Jr. 2000. A new approach to the geometry of TOA location. In IEEE Vehicular Technology Conference (VTC), Boston, MA.
• 8: 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
• 9: Crossbow. MICA Sensor Board Information, http://www.xbow.com
• 10: Doherty, L., Ghaoui, L. E., and Pister, K. S. J. 2001. Convex position estimation in wireless sensor networks. In Proceedings of the IEEE INFOCOM '01, Anchorage, AK.
• 11: 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]
• 12: Ganesan, D., Krishnamachari, B., Woo, A., Culler, D., Estrin, D., and Wicker, S. 2002. Complex behavior at scale: An experimental study of low-power wireless sensor vetworks. Technical Report UCLA/CSD-TR 02-0013.
• 13: Girod, L. and Estrin, D. 2001. Robust range estimation using acoustic and multimodal sensing. In Proceedings of IROS '01, Maui, Hawaii.
• 14: 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]
• 15: 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]
• 16: He, T., Blum, B. M., Stankovic, J. A., and Abdelzaher, T. F. 2003b. A lazy-binding communication protocol for highly dynamic wireless sensor networks. Still in submission.
• 17: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 18: Hightower, J., Boriello, G., and Want, R. 2000. SpotON: An indoor 3D location sensing technology based on RF signal strength. University of Washington CSE Report #2000-02-02.
• 19: Hong, X., Xu, K., and Gerla, M. 2002. Scalable routing protocols for mobile ad hoc networks. IEEE Network Magazine, 16, 4.
• 20: 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]
• 21: Kleinrock, L. and Silvester, J. 1978. Optimum transmission radii for packet radio networks or why six is a magic number. In Proceedings of National Telecomm Conference, 4.3.1--4.3.5.
• 22: 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]
• 23: 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]
• 24: Nagpal, R. 1999. Organizing a global coordinate system from local information on an amorphous computer. A.I. Memo, MIT A.I. Laboratory.
• 25: Nagpal, R., Shrobe, H., and Bachrach, J. 2003. Organizing a global coordinate system from local information on an ad hoc sensor network. In IPSN '03, Palo Alto.
• 26: 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]
• 27: Niculescu, D. and Nath. B. 2001. Ad-hoc positioning systems. In Proceedings of IEEE GLOBECOM '01.
• 28: Niculescu, D. and Nath, B. 2003a. DV based positioning in ad hoc networks. Journal of Telecommunication Systems 22, 1, 267--280.
• 29: Niculescu, D. and Nath, B. 2003b. Ad hoc positioning system (APS) using AoA. In Proceedings of the IEEE INFOCOM '03, San Francisco, CA.
• 30: 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]
• 31: 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
• 32: 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]
• 33: 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]
• 34: 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]
• 35: Wellenhoff, B. H., Lichtenegger, H., and Collins, J. 1997. Global Positions System: Theory and Practice, 4th Ed. Springer Verlag, NY.
• 36: 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]
• 37: 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]
• 38: 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]
• 39: Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on 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.990081]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

General Terms:
Algorithms, Design, Performance

Keywords:
Localization, location discovery, positioning, sensor network