Localization for mobile sensor networks

ABSTRACT

Many sensor network applications require location awareness, but it is often too expensive to include a GPS receiver in a sensor network node. Hence, localization schemes for sensor networks typically use a small number of seed nodes that know their location and protocols whereby other nodes estimate their location from the messages they receive. Several such localization techniques have been proposed, but none of them consider mobile nodes and seeds. Although mobility would appear to make localization more difficult, in this paper we introduce the sequential Monte Carlo Localization method and argue that it can exploit mobility to improve the accuracy and precision of localization. Our approach does not require additional hardware on the nodes and works even when the movement of seeds and nodes is uncontrollable. We analyze the properties of our technique and report experimental results from simulations. Our scheme outperforms the best known static localization schemes under a wide range of conditions.

REFERENCES

• 1: Jeffrey Antol, Philip Calhoun, John Flick, Gregory A. Hajos, Robert Kolacinski, David Minton, Rachel Owens and Jennifer Parker. Low Cost Mars Surface Exploration: The Mars Tumbleweed. NASA Langley Research Center. NASA/TM-2003-212411. August 2003.
• 2: Paramvir Bahl and Venkata N. Padmanabhan. RADAR: An In-Building RF-Based User Location and Tracking System. IEEE InfoCom 2000, March 2000.
• 3: P. Bergamo and G. Mazzini. Localization in Sensor Networks with Fading and Mobility. IEEE PIMRC. September 2002.
• 4: Wolfram Burgard, Dieter Fox, Daniel Hennig and Timo Schmidt. Estimating the Absolute Position of a Mobile Robot Using Position Probability Grids. 14th National Conference on Artificial Intelligence (AAAI). 1996.
• 5: Wolfram Burgard, Andreas Derr, Dieter Fox, and Armin B. Cremers. Integrating Global Position Estimation and Position Tracking for Mobile Robots: The Dynamic Markov Localization Approach. IEEE/RSI International Conference on Intelligence Robots and Systems (IROS). 1998.
• 6: Nirupama Bulusu, John Heidemann and Deborah Estrin. GPS-less Low Cost Outdoor Localization for Very Small Devices. IEEE Personal Communications Magazine. October 2000.
• 7: Nirupama Bulusu, John Heidemann and Deborah Estrin. Density Adaptive Algorithms for Beacon Placement in Wireless Sensor Networks. IEEE ICDCS 2001. April 2001.
• 8: Tracy Camp, Jeff Boleng and Vanessa Davies. A Survey of Mobility Models for Ad Hoc Networks Research. Wireless Communications and Mobile Computing. Volume 2, Number 5. 2002.
• 9: Haowen Chan , Adrian Perrig , Dawn Song, Random Key Predistribution Schemes for Sensor Networks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.197, May 11-14, 2003
• 10: Frank Dellaert, Dieter Fox, Wolfram Burgard and Sebastian Thrun. Monte Carlo Localization for Mobile Robots. IEEE International Conference on Robotics and Automation (ICRA). May 1999.
• 11: Lance Doherty, Kristofer Pister and Laurent El Ghaoui. Convex Position Estimation in Wireless Sensor Networks. IEEE InfoCom 2001. April 2001.
• 12: Arnaud Doucet , Simon Godsill , Christophe Andrieu, On sequential Monte Carlo sampling methods for Bayesian filtering, Statistics and Computing, v.10 n.3, p.197-208, July 2000 [doi>10.1023/A:1008935410038]
• 13: Arnaud Doucet, Nando de Freitas and Neil Gordon. An Introduction to Sequential Monte Carlo Methods. In Sequential Monte Carlo Methods in Practice, eds. Arnaud Doucet, Nando de Freitas and Neil Gordon. 2001.
• 14: Laurent Eschenauer , Virgil D. Gligor, A key-management scheme for distributed sensor networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586117]
• 15: Xiaoyan Hong , Mario Gerla , Guangyu Pei , Ching-Chuan Chiang, A group mobility model for ad hoc wireless networks, Proceedings of the 2nd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.53-60, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313237.313248]
• 16: John Geweke. Bayesian Inference in Econometric Models Using Monte Carlo Integration. Econometrica. Volume 57, Number 6. 1989.
• 17: Neil J. Gordon, D. J. Salmond, and A. F. M. Smith. Novel Approach to Nonlinear/Non-Gaussian Bayesian State Estimate. IEE Proceedings. Volume 140, pp. 107--113. 1993.
• 18: J. E. Handschin. Monte Carlo Techniques for Prediction and Filtering of Non-Linear Stochastic Processes. Automatica 6. pp. 555--563.1970.
• 19: 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]
• 20: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 21: Lingxuan Hu and David Evans. Using Directional Antennas to Prevent Wormhole Attacks. Network and Distributed System Security Symposium (NDSS), February 2004.
• 22: Yih-Chun Hu, Adrian Perrig and David Johnson. Packet Leashes: A Defense against Wormhole Attacks in Wireless Ad Hoc Networks. IEEE InfoCom 2003. April 2003.
• 23: Michael Isard , Andrew Blake, Contour Tracking by Stochastic Propagation of Conditional Density, Proceedings of the 4th European Conference on Computer Vision-Volume I, p.343-356, April 15-18, 1996
• 24: Chris Karlof and David Wagner. Secure Routing in Sensor Networks: Attacks and Countermeasures. First IEEE International Workshop on Sensor Network Protocols and Applications, May, 2003.
• 25: Brad Karp and H. T. Kung. Greedy Perimeter Stateless Routing. MobiCom 2000.
• 26: 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]
• 27: A. Kong, J. S. Liu and W. H. Wong. Sequential Imputations and Bayesian Missing Data Problems. Journal of the American Statistical Association. Volume 89, pp. 278--288. 1994.
• 28: Uwe Kubach , Kurt Rothermel, Exploiting location information for infostation-based hoarding, Proceedings of the 7th annual international conference on Mobile computing and networking, p.15-27, July 2001, Rome, Italy [doi>10.1145/381677.381680]
• 29: 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]
• 30: Andrew M. Ladd, Kostas E. Bekris, Algis P. Rudys, Dan S. Wallach and Lydia E. Kavraki. On the Feasibility of Using Wireless Ethernet for Indoor Localization. IEEE Transactions on Robotics and Automation. Volume 20, Number 3. June 2004.
• 31: Kenneth Lodding. Personal communication. March 2004.
• 32: Martin Mauve, Jorg Widmer and Hannes Hartenstein. A Survey on Position-Based Routing in Mobile Ad-Hoc Networks. IEEE Network Magazine. 2001.
• 33: Peter Maybeck. Stochastic Models. Estimation and Control, Volume 1. Academic Press, New York, 1979.
• 34: Radhika Nagpal, Howard Shrobe, and Jonathan Bachrach. Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network. 2nd International Workshop on Information Processing in Sensor Networks (IPSN). April 2003.
• 35: Dragos Niculescu and Badri Nath. DV Based Positioning in Ad hoc Networks. Kluwer Journal of Telecommunication Systems. 2003.
• 36: Dragos Niculescu and Badri Nath. Ad Hoc Positioning System (APS) Using AoA. IEEE InfoCom 2003.
• 37: Neal Patwari , Alfred O. Hero, III, Using proximity and quantized RSS for sensor localization in wireless networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941354]
• 38: Adrian Perrig , Robert Szewczyk , J. D. Tygar , Victor Wen , David E. Culler, SPINS: security protocols for sensor networks, Wireless Networks, v.8 n.5, p.521-534, September 2002 [doi>10.1023/A:1016598314198]
• 39: D. B. Rubin. Using the SIR algorithm to simulate posterior distributions. Bayesian Statistics 3. Oxford University Press. 1988.
• 40: 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]
• 41: Yi Shang , Wheeler Ruml , Ying Zhang , Markus P. J. Fromherz, Localization from mere connectivity, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778439]
• 42: Sebastian Thrun , Dieter Fox , Wolfram Burgard , Frank Dallaert, Robust Monte Carlo localization for mobile robots, Artificial Intelligence, v.128 n.1-2, p.99-141, May 2001 [doi>10.1016/S0004-3702(01)00069-8]
• 43: B. H. Wellenhoff, H. Lichtenegger and J. Collins. Global Positioning System: Theory and Practice, Fourth Edition. Springer Verlag. 1997.
• 44: Jungkeun Yoon , Mingyan Liu , Brian Noble, Sound mobility models, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939007]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Experimentation

Keywords:
Monte Carlo localization, localization, mobility, sensor networks