ABSTRACT
Wireless sensor networks are capable of collecting an enormous amount of data over space and time. Often, the ultimate objective is to derive an estimate of a parameter or function from these data. This paper investigates a general class of distributed algorithms for "in-network" data processing, eliminating the need to transmit raw data to a central point. This can provide significant reductions in the amount of communication and energy required to obtain an accurate estimate. The estimation problems we consider are expressed as the optimization of a cost function involving data from all sensor nodes. The distributed algorithms are based on an incremental optimization process. A parameter estimate is circulated through the network, and along the way each node makes a small adjustment to the estimate based on its local data. Applying results from the theory of incremental subgradient optimization, we show that for a broad class of estimation problems the distributed algorithms converge to within an e-ball around the globally optimal value. Furthermore, bounds on the number incremental steps required for a particular level of accuracy provide insight into the trade-off between estimation performance and communication overhead. In many realistic scenarios, the distributed algorithms are much more efficient, in terms of energy and communications, than centralized estimation schemes. The theory is verified through simulated applications in robust estimation, source localization, cluster analysis and density estimation.
- A. Boulis, S. Ganeriwal, and M. Srivastava. Aggregation in sensor networks: An energy-accuracy trade-off. In Proc. IEEE SNPA, Anchorage, AK, May 2003.Google ScholarCross Ref
- J. C. Chen, K. Yao, and R. E. Hudson. Source localization and beamforming. IEEE Sig. Proc. Magazine, March 2002.Google ScholarCross Ref
- A. D'Costa and A. M. Sayeed. Collaborative signal processing for distributed classification in sensor networks. In Proc. IPSN, Palo Alto, CA, April 2003. Google ScholarDigital Library
- D. Estrin, R. Govindan, and J. Heidemann. Scalable coordination in sensor networks. Technical Report USC Tech Report 99-692, USC/ISI, 1999.Google Scholar
- P. J. Huber. Robust Statistics. John Wiley & Sons, 1981.Google Scholar
- P. Ishwar, R. Puri, S. Pradhan, and K. Ramchandran. On compression for robust estimation in sensor networks. In Proc. of IEEE ISIT, Yokohama, Japan, September 2003.Google Scholar
- C. Kreucher, K. Kastella, and A. Hero. Sensor management using relevance feedback learning. Submitted to IEEE Transactions on Signal Processing, June 2003.Google Scholar
- C. Moallemi and B. Van Roy. Distributed optimization in adaptive networks. In Proc. NIPS, Vancouver, BC, Canada, December 2003.Google Scholar
- A. Nedić and D. Bertsekas. Incremental subgradient methods for nondifferentiable optimization. Technical Report LIDS-P-2460, Massachusetts Institute of Technology, Cambridge, MA, 1999.Google Scholar
- A. Nedić and D. Bertsekas. Stochastic Optimization: Algorithms and Applications, chapter Convergence Rate of Incremental Subgradient Algorithms, pages 263--304. Kluwer Academic Publishers, 2000.Google Scholar
- R. Nowak. Distributed EM algorithms for density estimation and clustering in sensor networks. IEEE Trans. on Sig. Proc., 51(8), August 2003. Google ScholarDigital Library
- X. Sheng and Y.-H. Hu. Energy based acoust source localization. In Proc. IPSN, Palo Alto, CA, April 2003. Google ScholarDigital Library
- J. Shin, L. Guibas, and F. Zhao. A distributed algorithm for managing multi-target identities in wireless ad-hoc sensor networks. In Proc. IPSN, Palo Alto, CA, April 2003. Google ScholarDigital Library
- L. Xu and M. Jordan. On convergence properties of the EM algorithm for gaussian mixtures. Neural Computation, 8:129--151, 1996. Google ScholarDigital Library
Index Terms
- Distributed optimization in sensor networks
Recommendations
Quantized incremental algorithms for distributed optimization
Wireless sensor networks are capable of collecting an enormous amount of data. Often, the ultimate objective is to estimate a parameter or function from these data, and such estimators are typically the solution of an optimization problem (e.g., maximum ...
Distributed weighted-multidimensional scaling for node localization in sensor networks
Accurate, distributed localization algorithms are needed for a wide variety of wireless sensor network applications. This article introduces a scalable, distributed weighted-multidimensional scaling (dwMDS) algorithm that adaptively emphasizes the most ...
Distributed wireless sensor network localization via sequential greedy optimization algorithm
Node localization is essential to most applications of wireless sensor networks (WSNs). In this paper, we consider both range-based node localization and range-free node localization with uncertainties in range measurements, radio range, and anchor ...
Comments