Distributed optimization in sensor networks

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.

REFERENCES

• 1: A. Boulis, S. Ganeriwal, and M. Srivastava. Aggregation in sensor networks: An energy-accuracy trade-off. In Proc. IEEE SNPA, Anchorage, AK, May 2003.
• 2: J. C. Chen, K. Yao, and R. E. Hudson. Source localization and beamforming. IEEE Sig. Proc. Magazine, March 2002.
• 3: A. D'Costa and A. M. Sayeed. Collaborative signal processing for distributed classification in sensor networks. In Proc. IPSN, Palo Alto, CA, April 2003.
• 4: D. Estrin, R. Govindan, and J. Heidemann. Scalable coordination in sensor networks. Technical Report USC Tech Report 99-692, USC/ISI, 1999.
• 5: P. J. Huber. Robust Statistics. John Wiley & Sons, 1981.
• 6: 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.
• 7: C. Kreucher, K. Kastella, and A. Hero. Sensor management using relevance feedback learning. Submitted to IEEE Transactions on Signal Processing, June 2003.
• 8: C. Moallemi and B. Van Roy. Distributed optimization in adaptive networks. In Proc. NIPS, Vancouver, BC, Canada, December 2003.
• 9: A. Nedić and D. Bertsekas. Incremental subgradient methods for nondifferentiable optimization. Technical Report LIDS-P-2460, Massachusetts Institute of Technology, Cambridge, MA, 1999.
• 10: A. Nedić and D. Bertsekas. Stochastic Optimization: Algorithms and Applications, chapter Convergence Rate of Incremental Subgradient Algorithms, pages 263--304. Kluwer Academic Publishers, 2000.
• 11: R. Nowak. Distributed EM algorithms for density estimation and clustering in sensor networks. IEEE Trans. on Sig. Proc., 51(8), August 2003.
• 12: X. Sheng and Y.-H. Hu. Energy based acoust source localization. In Proc. IPSN, Palo Alto, CA, April 2003.
• 13: 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.
• 14: Lei Xu , Michael I. Jordan, On convergence properties of the EM algorithm for Gaussian mixtures, Neural Computation, v.8 n.1, p.129-151, Jan. 1996

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Performance

Keywords:
distributed optimization, energy-accuracy tradeoff, incremental subgradient methods