Nonparametric belief propagation for self-calibration in sensor networks

ABSTRACT

Automatic self-calibration of ad-hoc sensor networks is a critical need for their use in military or civilian applications. In general, self-calibration involves the combination of absolute location information (e.g. GPS) with relative calibration information (e.g. time delay or received signal strength between sensors) over regions of the network. Furthermore, it is generally desirable to distribute the computational burden across the network and minimize the amount of inter-sensor communication. We demonstrate that the information used for sensor calibration is fundamentally local with regard to the network topology and use this observation to reformulate the problem within a graphical model framework. We then demonstrate the utility of nonparametric belief propagation (NBP), a recent generalization of particle filtering, for both estimating sensor locations and representing location uncertainties. NBP has the advantage that it is easily implemented in a distributed fashion, admits a wide variety of statistical models, and can represent multi-modal uncertainty. We illustrate the performance of NBP on several example networks while comparing to a previously published nonlinear least squares method.

REFERENCES

• 1: M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp. A tutorial on particle filters for online nonlinear/non-Gaussian bayesian tracking. IEEE Transactions on Signal Processing, 50(2):174--188, February 2002.
• 2: P. Clifford. Markov random fields in statistics. In G. R. Grimmett and D. J. A. Welsh, editors, Disorder in Physical Systems, pages 19--32. Oxford University Press, Oxford, 1990.
• 3: A. Doucet, N. de Freitas, and N. Gordon, editors. Sequential Monte Carlo Methods in Practice. Springer-Verlag, New York, 2001.
• 4: T. Eren, D. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. O. Anderson, and P. N. Belhumeur. Rigidity, complexity, and randomization in network localization. Technical Report TR1257, Yale University, 2003.
• 5: M. Fazel, H. Hindi, and S. P. Boyd. Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. In Proceedings, American Control Conference, 2003.
• 6: B. Frey, R Koetter, G. Forney, F. Kschischang, R. McEliece, and D. Spielman (Eds.). Special issue on codes and graphs and iterative algorithms. IEEE Transactions on Information Theory, 47(2), February 2001.
• 7: S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6):721--741, November 1984.
• 8: H. Gharavi and S. Kumar (Eds.). Special issue on sensor networks and applications. Proceedings of the IEEE, 91(8), August 2003.
• 9: A. T. Ihler, E. B. Sudderth, W. T. Freeman, and A. S. Willsky. Efficient multiscale sampling from products of Gaussian mixtures. In Neural Information Processing Systems 17, 2003.
• 10: M. Isard. PAMPAS: Real--valued graphical models for computer vision. In IEEE Computer Vision and Pattern Recognition, 2003.
• 11: D. Koller, U. Lerner, and D. Angelov. A general algorithm for approximate inference and its application to hybrid Bayes nets. In Uncertainty in Artificial Intelligence 15, pages 324--333, 1999.
• 12: S. Kumar, F. Zhao, and D. Shepherd (Eds.). Special issue on collaborative information processing. IEEE Signal Processing Magazine, 19(2), March 2002.
• 13: S. L. Lauritzen. Graphical Models. Oxford University Press, Oxford, 1996.
• 14: R. Moses, D. Krishnamurthy, and R. Patterson. Self-localization for wireless networks. Eurasip Journal on Applied Signal Processing, 2003.
• 15: R. Moses and R. Patterson. Self-calibration of sensor networks. In SPIE vol. 4743: Unattended Ground Sensor Technologies and Applications IV, 2002.
• 16: K. Murphy, Y. Weiss, and M. Jordan. Loopy-belief propagation for approximate inference: An empirical study. In Uncertainty in Artificial Intelligence 15, pages 467--475, July 1999.
• 17: D. Niculescu and B. Nath. Ad-hoc positioning system. In Proceedings, IEEE GlobeCom, November 2001.
• 18: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 19: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 20: B.W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall, New York, 1986.
• 21: E. B. Sudderth, A. T. Ihler, W. T. Freeman, and A. S. Willsky. Nonparametric belief propagation. In IEEE Computer Vision and Pattern Recognition, 2003.
• 22: J. B. Tenenbaum, V. De Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500), December 2000.
• 23: M. W. Trosset. The formulation and solution of multidimensional scaling problems. Technical Report TR93-55, Rice University, 1993.
• 24: Yair Weiss, Belief Propagation and Revision in Networks with Loops, Massachusetts Institute of Technology, Cambridge, MA, 1997

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Nonparametric statistics
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Algorithms

Keywords:
NBP, belief propagation, calibration, localization, nonparametric, sensor network