Tian He
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.
- 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.Google Scholar
Cross Ref
- J. Beutel, Geolocation in a PicoRadio Environment, M.S. Thesis, ETH Zurich, Electronics Laboratory, Dec. 1999.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- N. Bulusu, J. Heidemann, D. Estrin and T. Tran, Self-configuring Localization Systems: Design and Experimental Evaluation <http://lecs.cs.ucla.edu/~bulusu/papers/Bulusu02b.html> , ACM Transactions on Embedded Computing Systems (TECS), Special Issue on Networked Embedded Computing, 2003. Google ScholarDigital Library
- J. Caffery, Jr. A New Approach to the Geometry of TOA Location, In IEEE Vehicular Technology Conference (VTC), Boston, Mass, September 2000.Google ScholarCross Ref
- S. Capkun, M. Hamdi and J.P. Hubaux, GPS-Free Positioning in Mobile Ad-Hoc Networks, In Proceedings of HICCSS '01, Maui, Hawaii, January 2001. Google ScholarDigital Library
- 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.Google Scholar
- D. Estrin, R. Govindan, J. Heidemann and S. Kumar, Next Century Challenges: Scalable Coordination in Sensor Networks,In Proceedings of MOBICOM '99, Seattle, Washington, 1999. Google ScholarDigital Library
- 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.Google Scholar
- L. Girod and D. Estrin, Robust Range Estimation using Acoustic and Multimodal Sensing, In Proceedings of IROS '01, Maui, Hawaii, October 2001.Google ScholarCross Ref
- A. Harter, A. Hopper and P. Steggles, A. Ward and P. Webster, The anatomy of a context-aware application, In Proceedings of MOBICOM '99, Seattle, Washington, 1999. Google ScholarDigital Library
- T. He, J. A. Stankovic, C. Lu, and T. F. Abdelzaher, SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks, In Proceedings of IEEE ICDCS '03, Providence, RI, May 2003. Google ScholarDigital Library
- J. Hightower and G. Boriello, Location Systems for Ubiquitous Computing, IEEE Computer, 34(8):57--66, August 2001. Google ScholarDigital Library
- 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.Google Scholar
- X. Hong, K. Xu, and M. Gerla, Scalable routing protocols for mobile ad hoc networks, IEEE Network magazine, vol 16, No. 4, 2002. Google ScholarDigital Library
- B. Karp and H. T. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, In Proceedings of MOBICOM '00, New York, August 2000. Google ScholarDigital Library
- 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, 1978Google Scholar
- Y. B. Ko and N. H. Vaidya, Location-Aided Routing (LAR) in Mobile Ad Hoc Networks, In Proceedings of MOBICOM '98, Dallas, TX, 1998. Google ScholarDigital Library
- J. Li, J. Jannotti, D. S. J. De Couto, D. Karger and R. Morris, A Scalable Location Service for Geographic Ad-Hoc Routing, In Proceedings of MOBICOM '00, New York, August 2000. Google ScholarDigital Library
- MICA Sensor Board Information, http://www.xbow.comGoogle Scholar
- R. Nagpal, Organizing a Global Coordinate System from Local Information on an Amorphous Computer, A.I. Memo 1666, MIT A.I. Laboratory, August 1999.Google Scholar
- 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. Google ScholarDigital Library
- J. C. Navas and T. Imielinski, Geographic Addressing and Routing, In Proceedings of MOBICOM '97, Budapest, Hungary, September 26, 1997. Google ScholarDigital Library
- D. Nicolescu and B. Nath, Ad-Hoc Positioning Systems (APS), In Proceedings of IEEE GLOBECOM '01, November 2001.Google ScholarCross Ref
- D. Niculescu and B. Nath, DV Based Positioning in Ad hoc Networks, In Journal of Telecommunication Systems, 2003.Google Scholar
- D. Niculescu and B. Nath, Ad Hoc Positioning System (APS) using AoA, INFOCOM'03, San Francisco, CA,2003Google ScholarCross Ref
- N. B. Priyantha, A. Chakraborty and H. Balakrishnan, The Cricket Location-Support System, In Proceedings of MOBICOM '00, New York, August 2000. Google ScholarDigital Library
- C. Savarese, J. Rabay and K. Langendoen, Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks, USENIX Technical Annual Conference, Monterey, CA, June 2002. Google ScholarDigital Library
- A. Savvides, C. C. Han and M. B. Srivastava, Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors, In Proceedings of MOBICOM '01, 2001, Rome, Italy, July 2001. Google ScholarDigital Library
- A. Savvides, H. Park and M. Srivastava, The Bits and Flops of the N-Hop Multilateration Primitive for Node Localization Problems, In First ACM International Workshop on Wireless Sensor Networks and Application, Atlanta, GA, September 2002. Google ScholarDigital Library
- R. Want, A. Hopper, V. Falcao and J. Gibbons, The Active Badge Location System, ACM Transactions on Information Systems, January 1992. Google ScholarDigital Library
- B. H. Wellenhoff, H. Lichtenegger and J. Collins, Global Positions System: Theory and Practice, Fourth Edition. Springer Verlag, 1997.Google Scholar
- K. Whitehouse and D. Culler, Calibration as Parameter Estimation in Sensor Networks, In First ACM International Workshop on Wireless Sensor Networks and Application, Atlanta GA, September 2002. Google ScholarDigital Library
- Y. Xu, J. Heidemann and D. Estrin <http://netweb.usc.edu/estrin/>, Geography-informed Energy Conservation for Ad Hoc Routing <http://www.isi.edu/scadds/papers/yaxu-mobicom2001.ps.gz> , In Proceedings of MOBICOM '01, Rome, Italy, July 2001. Google ScholarDigital Library
- T. Yan, T. He, J. A. Stankovic, Differentiated Surveillance Service for Sensor Networks <http://www.cs.virginia.edu/~th7c/paper/D-SensingCoverage.pdf>, In Proceeding of First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003), Los Angeles, CA 2003. Google ScholarDigital Library
Index Terms
- Range-free localization schemes for large scale sensor networks
Recommendations
Range-free localization and its impact on large scale sensor networks
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 ...
Poster abstract: Range-based localization in sensor networks: localizability and accuracy
IPSN '13: Proceedings of the 12th international conference on Information processing in sensor networksLocalizability and accuracy are two fundamental problems in many range-based localization schemes for sensor networks. This poster addresses the two problems theoretically by introducing two new concepts: the effective degree and the lower bound of ...
Low-cost two-hop anchor node-based distributed range-free localization in wireless sensor networks
ICCSA'10: Proceedings of the 2010 international conference on Computational Science and Its Applications - Volume Part IIIDue to the fact that most of the sensor network applications are based on the location information of sensor nodes, localization is an essential research area. Some localization schemes in the literature require sensor nodes to have additional devices ...
Comments