ABSTRACT
We propose a new iterative distributed algorithm for linear minimum mean-squared-error (LMMSE) estimation in sensor networks whose measurements follow a Gaussian hidden Markov graphical model with cycles. The embedded polygons algorithm decomposes a loopy graphical model into a number of linked embedded polygons and then applies a parallel block Gauss-Seidel iteration comprising local LMMSE estimation on each polygon (involving inversion of a small matrix) followed by an information exchange between neighboring nodes and polygons. The algorithm is robust to temporary communication faults such as link failures and sleeping nodes and enjoys guaranteed convergence under mild conditions. A simulation study indicates that energy consumption for iterative estimation increases substantially as more links fail or nodes sleep. Thus, somewhat surprisingly, energy conservation strategies such as low-powered transmission and aggressive sleep schedules could actually be counterproductive.
- D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, "Next century challenges: Scalable coordination in sensor networks," in Proc. ACM/IEEE MobiCom'99, pp. 263--270, Aug. 1999. Google ScholarDigital Library
- A. Wang and A. Chandrakasan, "Energy-eficient DSPs for wireless sensor networks," IEEE Signal Processing Mag., pp. 68--78, July 2002.Google ScholarCross Ref
- S. L. Lauritzen, Graphical Models. Oxford, 1996.Google Scholar
- C. B. Barber, D. P. Dobkin, and H. T. Huhdanpaa, "The Quickhull algorithm for convex hulls," ACM Trans. Math. Software, vol. 22, no. 4, pp. 469--483, 1996. Google ScholarDigital Library
- K. Plarre and P. R. Kumar, "Extended message passing algorithm for inference in loopy Gaussian graphical models," Ad Hoc Networks, 2002.Google Scholar
- J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988. Google ScholarDigital Library
- Y. Weiss and W. T. Freeman, "Correctness of belief propagation in Gaussian graphical models of arbitrary topology," Neural Computation, vol. 13, pp. 2173--2200, 2001. Google ScholarDigital Library
- M. J. Wainwright, Stochastic Processes on Graphs with Cycles: Geometric and Variational Approaches. PhD thesis, ECE Dept., MIT, Jan. 2002. Google ScholarDigital Library
- E. Sudderth, M. J. Wainwright, and A. S. Willsky, "Embedded trees: Estimation of Gaussian processes on graphs with cycles," tech. rep., MIT, 2003.Google Scholar
- V. Delouille, R. Neelamani, V. Chandrasekaran, and R. G. Baraniuk, "The embedded triangles algorithm for distributed estimation in sensor networks," in IEEE Statistical Signal Processing Workshop, (St. Louis), pp. 357--360, 2003.Google Scholar
- R. G. Cowell, A. P. Dawid, S. L. Lauritzen, and D. J. Spiegelhalter, Probabilistic Networks and Expert Systems. Springer, 1999. Google ScholarDigital Library
- J. Liebeherr, M. Nahas, and W. Si, "Application-layer multicast with Delaunay triangulations," tech. rep., CS Dept., University of Virginia, 2001. Google ScholarDigital Library
- X.-Y. Li, P.-J. Wan, and O. Frieder, "Coverage in wireless ad-hoc sensor networks," IEEE Trans. Computers, vol. 52, pp. 727--741, June 2003. Google ScholarDigital Library
- N. A. C. Cressie, Statistics for Spatial Data. Wiley, 1993.Google Scholar
- R. S. Varga, Matrix Iterative Analysis. Prentice-Hall, 1962.Google Scholar
- A. Abdalla, N. Deo, and P. Gupta, "Random-tree diameter and diameter-constrained MST," Congressus Numerantium, vol. 144, pp. 161--182, 2000.Google Scholar
- J.-F. Chamberland and V. V. Veeravalli, "The art of sleeping in wireless sensing systems," in IEEE Statistical Signal Processing Workshop, (St. Louis), pp. 9--12, 2003.Google Scholar
- Y. Xu, S. Bien, Y. Mori, J. Heidemann, and D. Estrin, "Topology control protocols to conserve energy in wireless ad hoc networks," Tech. Rep. 6, UCLA, Center for Embedded Networked Computing, Jan. 2003.Google Scholar
- A. Frommer and B. Szyld, "On asynchronous iterations," J. Comput. Appl. Math., vol. 123, pp. 201--216, 2000. Google ScholarDigital Library
Index Terms
- Robust distributed estimation in sensor networks using the embedded polygons algorithm
Recommendations
Robust Distributed Estimation Using the Embedded Subgraphs Algorithm
We propose a new iterative, distributed approach for linear minimum mean-square-error (LMMSE) estimation in graphical models with cycles. The embedded subgraphs algorithm (ESA) decomposes a loopy graphical model into a number of linked embedded ...
Estimating inhomogeneous fields using wireless sensor networks
Sensor networks have emerged as a fundamentally new tool for monitoring spatial phenomena. This paper describes a theory and methodology for estimating inhomogeneous, two-dimensional fields using wireless sensor networks. Inhomogeneous fields are ...
Quantization, channel compensation, and optimal energy allocation for estimation in sensor networks
In clustered networks of wireless sensors, each sensor collects noisy observations of the environment, quantizes these observations into a local estimate of finite length, and forwards them through one or more noisy wireless channels to the cluster head ...
Comments