A space-time diffusion scheme for peer-to-peer least-squares estimation

ABSTRACT

We consider a sensor network in which each sensor takes measurements, at various times, of some unknown parameters, corrupted by independent Gaussian noises. Each node can take a finite or infinite number of measurements, at arbitrary times (ie, asynchronously). We propose a space-time diffusion scheme, that relies only on peer-to-peer communication, and allows every node to asymptotically compute the global maximum-likelihood estimate of the unknown parameters. At each iteration, information is diffused across the network by a temporal update step and a spatial update step. Both steps update each node's state by a weighted average of its current value and locally available data: new measurements for the time update, and neighbors' data for the spatial update. At any time, any node can compute a local weighted least-squares estimate of the unknown parameters, which converges to the global maximum-likelihood solution. With an infinite number of measurements, these estimates converge to the true parameter values in the sense of mean-square convergence. We show that this scheme is robust to unreliable communication links, and works in a network with dynamically changing topology.

REFERENCES

• 1: M. Alanyali, S. Venkatesh, O. Savas, and S. Aeron. Distributed Bayesian hypothesis testing in sensor networks. In Proceedings of American Control Conference, pages 5369--5374, Boston, June 2004.
• 2: Dimitri P. Bertsekas , John N. Tsitsiklis, Gradient Convergence in Gradient methods with Errors, SIAM Journal on Optimization, v.10 n.3, p.627-642, 1999 [doi>10.1137/S1052623497331063]
• 3: V. D. Blondel, J. M. Hendrickx, A. Olshevsky, and J. N. Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking. Proceedings of IEEE Conference on Decision and Control, 2005.
• 4: J. E. Boillat, Load balancing and Poisson equation in a graph, Concurrency: Practice and Experience, v.2 n.4, p.289-313, Dec. 1990 [doi>10.1002/cpe.4330020403]
• 5: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms: design, analysis and applications. to appear in Proceedings of IEEE INFOCOM, 2005.
• 6: Jen-Yeu Chen , Gopal Pandurangan , Dongyan Xu, Robust computation of aggregates in wireless sensor networks: distributed randomized algorithms and analysis, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 7: G. Cybenko, Dynamic load balancing for distributed memory multiprocessors, Journal of Parallel and Distributed Computing, v.7 n.2, p.279-301, October 1989 [doi>10.1016/0743-7315(89)90021-X]
• 8: Véronique Delouille , Ramesh Neelamani , Richard Baraniuk, Robust distributed estimation in sensor networks using the embedded polygons algorithm, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984681]
• 9: Y. Hatano and M. Mesbahi. Agreement over random networks. In Proceedings of 43rd IEEE Conference on Decision and Control, Atlantis, Bahamas, December 2004.
• 10: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 11: A. Jadbabaie, J. Lin, and A. S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions Automatic Control, 48(6):988--1001, June 2003.
• 12: Z.-Q. Luo. An isotropic universal decentralized estimation scheme for a bandwidth constrained ad hoc sensor network. IEEE Journal on Selected Areas in Communications, 2005. Special issue on Self-Organizing Distributed Collaborative Sensor Networks, to appear.
• 13: L. Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control, 50:169--182, 2005.
• 14: R. Olfati-Saber and R. M. Murray. Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control, 49(9):1520--1533, September 2004.
• 15: K. Plarre and P. R. Kumar. Extended message passing algorithm for inference in loopy gaussian graphical models. Ad Hoc Networks, 2:153--169, 2004.
• 16: W. Ren and R. W. Beard. Consensus seeking in multi-agent systems under dynamically changing interaction topologies. IEEE Transactions on Automatic Control, 2005. to appear.
• 17: Dzulkifli S. Scherber , Haralabos C. Papadopoulos, Locally constructed algorithms for distributed computations in ad-hoc networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984625]
• 18: Demetri P. Spanos , Reza Olfati-Saber , Richard M. Murray, Approximate distributed Kalman filtering in sensor networks with quantifiable performance, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 19: S.-H. Teng, C. W. Wong, and D. T. Lee. Unstructured mesh generation: theory, practice, and perspectives. International Journal of Computational Geometry and Applicatons, 10(3):227--266, 2000.
• 20: J. N. Tsitsiklis. Problems in Decentralized Decision Making and Computation. PhD thesis, Massachusetts Institute of Technology, 1984.
• 21: J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control, 31(9):803--812, September 1986.
• 22: L. Xiao and S. Boyd. Fast linear iterations for distributed averaging. Systems and Control Letters, 53:65--78, 2004.
• 23: Lin Xiao , Stephen Boyd , Sanjay Lall, A scheme for robust distributed sensor fusion based on average consensus, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Least squares methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Theory

Keywords:
distributed algorithms, estimation, least-squares, sensor networks