Simultaneous localization, calibration, and tracking in an ad hoc sensor network

ABSTRACT

We introduce Simultaneous Localization and Tracking, called SLAT, the problem of tracking a target in a sensor network while simultaneously localizing and calibrating the nodes of the network. Our proposed solution, LaSLAT, is a Bayesian filter that provides on-line probabilistic estimates of sensor locations and target tracks. It does not require globally accessible beacon signals or accurate ranging between the nodes. Real hardware experiments are presented for 2D and 3D, indoor and outdoor, and ultrasound and audible ranging-hardware-based deployments. Results demonstrate rapid convergence and high positioning accuracy.

REFERENCES

• 1: Pubudu N. Pathirana , Nirupama Bulusu , Andrey V. Savkin , Sanjay Jha, Node Localization Using Mobile Robots in Delay-Tolerant Sensor Networks, IEEE Transactions on Mobile Computing, v.4 n.3, p.285-296, May 2005 [doi>10.1109/TMC.2005.43]
• 2: Aram Galstyan , Bhaskar Krishnamachari , Kristina Lerman , Sundeep Pattem, Distributed online localization in sensor networks using a moving target, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984632]
• 3: V. Cevher and J.H. McClellan, "Sensor array calibration via tracking with the extended kalman filter," in IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2001, vol. 5, pp. 2817--2820.
• 4: J. J. Leonard and P. M. Newman, "Consistent, convergent, and constant-time SLAM," in International Joint Conferences on Artificial Intelligence (IJCAI), 2003.
• 5: Yufeng Liu , Rosemary Emery , Deepayan Chakrabarti , Wolfram Burgard , Sebastian Thrun, Using EM to Learn 3D Models of Indoor Environments with Mobile Robots, Proceedings of the Eighteenth International Conference on Machine Learning, p.329-336, June 28-July 01, 2001
• 6: S. Thrun, Y. Liu, D. Koller, A.Y. Ng, Z. Ghahramani, and H. Durrant-Whyte, "Simultaneous localization and mapping with sparse extended information filters," Submitted for journal publication, April 2003.
• 7: Andrew J. Davison , David W. Murray, Simultaneous Localization and Map-Building Using Active Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.865-880, July 2002 [doi>10.1109/TPAMI.2002.1017615]
• 8: N. Ayache and O. Faugeras, "Maintaining representations of the environment of a mobile robot," IEEE Tran. Robot. Automat., vol. 5, no. 6, pp. 804--819, 1989.
• 9: R. Smith, M. Self, and P. Cheeseman, "Estimating uncertain spatial relationships in robotics," in Uncertainity in Artificial Intelligence, 1988.
• 10: H. Balakrishnan, R. Baliga, D. Curtis, M. Goraczko, A. Miu, N. B. Priyantha, A. Smith, K. Steele, S. Teller, and K. Wang, "Lessons from developing and deploying the cricket indoor location system," Tech. Rep., MIT Computer Science and AI Lab, http://nms.lcs.mit.edu/projects/cricket/#papers, 2003.
• 11: 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]
• 12: X. Ji and H. Zha, "Sensor positioning in wireless ad hoc networks using multidimensional scaling," in Infocom, 2004.
• 13: L. Doherty, L. El Ghaoui, and K. S. J. Pister, "Convex position estimation in wireless sensor networks," in Proceedings of Infocom 2001, April 2001.
• 14: N. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller, "Anchor-free distributed localization in sensor networks," 2003.
• 15: David Moore , John Leonard , Daniela Rus , Seth Teller, Robust distributed network localization with noisy range measurements, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031502]
• 16: Alexander T. Ihler , John W. Fisher, III , Randolph L. Moses , Alan S. Willsky, Nonparametric belief propagation for self-calibration in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984656]
• 17: E. Olson, J. J. Leonard, and S. Teller, "Robust range-only beacon localization," in Proceedings of Autonomous Underwater Vehicles, 2004.
• 18: P. F. McLauchlan, "A batch/recursive algorithm for 3D scene reconstruction," Conf. Computer Vision and Pattern Recognition, vol. 2, pp. 738--743, 2000.
• 19: A. Gelman, J. Carlin, H. Stern, and D. Rubin., Bayesian Data Analysis, Chapman & Hall/CRC, 1995.
• 20: G. Golub and C.F. Van Loan, Matrix Computations, The Johns Hopkins University Press, 1989.
• 21: Prabal Dutta, "On random event detection in wireless sensor networks," M.S. thesis, Ohio State University, Aug. 2004.
• 22: Y. Kwon, K. Mechitov, S. Sundresh, W. Kim, and G. Agha, "Resilient localization for sensor networks in outdoor environments," Eng Tech Report 2449, UIUC, 2004.
• 23: C. Taylor, "Simultaneous localization and tracking in wireless ad-hoc sensor networks," M.Eng. thesis, MIT CSAIL, May 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms

Keywords:
calibration, localization, position estimation, statistical machine learning, tracking, wireless sensor networks