Chapter 17
Distributed Algorithms in Sensor Networks
Usman A. Khan,
Soummya Kar,
José M. F. Moura,
Usman A. Khan
Department of Electrical & Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA
Search for more papers by this authorSoummya Kar
Department of Electrical & Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA
Search for more papers by this authorJosé M. F. Moura
Department of Electrical & Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA
Search for more papers by this authorUsman A. Khan,
Soummya Kar,
José M. F. Moura,
Usman A. Khan
Department of Electrical & Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA
Search for more papers by this authorSoummya Kar
Department of Electrical & Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA
Search for more papers by this authorJosé M. F. Moura
Department of Electrical & Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA
Search for more papers by this authorBook Editor(s):Simon Haykin,
K. J. Ray Liu,
Simon Haykin
Department of Electrical Engineering, McMaster University, Hamilton, Ontario, Canada
Search for more papers by this authorK. J. Ray Liu
Department of Electrical & Computer Engineering, University of Maryland, College Park, MD, USA
Search for more papers by this authorSummary
This chapter contains sections titled:
-
Introduction
-
Preliminaries
-
Distributed Detection
-
Consensus Algorithms
-
Zero-Dimension (Average) Consensus
-
Consensus in Higher Dimensions
-
Leader–Follower (Type) Algorithms
-
Localization in Sensor Networks
-
Linear System of Equations: Distributed Algorithm
-
Conclusions
-
References
REFERENCES
- M. D. Ilić, L. Xie, U. A. Khan, and J. M. F. Moura, “Modelling future cyberphysical energy systems,” paper presented at the IEEE Power Engineering Society General Meeting, Pittsburgh, PA, July 2008.
- M. D. Ilić, L. Xie, U. A. Khan, and J. M. F. Moura, “Modeling, sensing and control of future cyber-physical energy systems,” IEEE Trans. Syst. Man Cybernet. Spec. Issue Eng. Cyber-Phys. Ecosyst., Jul. 2008, submitted for publication.
- U. A. Khan, D. Ilić, and J. M. F. Moura, “Cooperation for aggregating complex electric power networks to ensure system observability,” paper presented at the IEEE International Conference on Infrastructure Systems, Rotterdam, Netherlands, Nov. 2008, accepted for publication.
- R. R. Tenney and N. R. Sandell, “Detection with distributed sensors,” IEEE Trans. Aerospace Electron. Syst., vol. AES-17, no. 4, pp. 501–510, July 1981.
- J. N. Tsitsiklis, “Problems in decentralized decision making and computation,” PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1984.
-
J. N. Tsitsiklis, “Decentralized detection by a large number of sensors,” Math. Control Signals Syst., vol. 1, no. 2, pp. 167–182, 1988.
10.1007/BF02551407 Google Scholar
- P. K. Varshney, Distributed Detection and Data Fusion, Secaucus, NJ: Springer, 1996.
- J.-F. Chamberland and V. V. Veeravalli, “Decentralized detection in sensor networks,” IEEE Trans. Signal Processing, vol. 51, pp. 407–416, Feb. 2003.
- S. Aldosari and J. M. F. Moura, “Detection in sensor networks: The saddlepoint approximation,” IEEE Trans. Signal Process., vol. 55, no. 1, pp. 327–340, Jan. 2007.
- J. N. Tsitsiklis and M. Athans, “On the complexity of decentralized decision making and detection problems,” IEEE Trans. Automatic Control, vol. AC-30, no. 5, pp. 440–446, May 1985.
- J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” IEEE Trans. Automatic Control., vol. AC-31, no. 9, pp. 803–812, Sept. 1986.
- H. J. Kushner and G. Yin, “Asymptotic properties of distributed and communicating stochastic approximation algorithms,” Siam J. Control Optimization, vol. 25, no. 5, pp. 1266–1290, Sept. 1987.
- A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” IEEE Trans. Automatic Control, vol. AC-48, no. 6, pp. 988–1001, June 2003.
- R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Trans. Automatic Control, vol. 49, no. 9, pp. 1520–1533, Sept. 2004.
- L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” Syst. Control Lett., vol. 53, pp. 65–78, 2004.
- S. Kar, S. A. Aldosari, and J. M. F. Moura, “Topology for distributed inference on graphs,” IEEE Trans. Signal Process., vol. 56, no. 6, pp. 2609–2613, June 2008.
- M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” J. Assoc. Comput. Machin., vol. 32, no. 2, pp. 374–382, Apr. 1985.
- N. A. Lynch, Distributed Algorithms, San Francisco, CA: Morgan Kaufmann, 1997.
- G. V. Cybenko, “Dynamic load balancing for distributed memory multiprocessors,” J. Parallel Distrib. Comput., vol. 7, pp. 279–301, 1989.
-
C. Reynolds, “Flocks, birds, and schools: A distributed behavioral model,” Computer Graphics, vol. 21, pp. 25–34, 1987.
10.1145/37402.37406 Google Scholar
- T. Vicsek, A. Czirok, E. Ben Jacob, I. Cohen, and O. Schochet, “Novel type of phase transitions in a system of self-driven particles,” Phys. Rev. Lett., vol. 75, pp. 1226–1229, 1995.
- W. Ren, R. W. Beard, and E. M. Atkins, “A survey of consensus problems in multi-agent coordination,” paper presented at the American Control Conference, Portland, OR, June 2005, pp. 1859–1864.
- R. Olfati-Saber, J. Alex Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” IEEE Proc., vol. 95, no. 1, pp. 215–233, Jan. 2007.
- Y. Hatano and M. Mesbahi, “Agreement over random networks,” paper presented at the 43rd IEEE Conference on Decision and Control, Vol. 2, Dec. 2004, pp. 2010–2015.
- Y. Hatano, A. K. Das, and M. Mesbahi, “Agreement in presence of noise: Pseudogradients on random geometric networks,” paper presented at the 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference, CDC-ECC '05, Seville, Spain, Dec. 2005.
- S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” IEEE/ ACM Trans. Networks, vol. 14, no. SI, pp. 2508–2530, 2006.
- S. Kar and J. M. F. Moura, “Sensor networks with random links: Topology design for distributed consensus,” IEEE Trans. Signal Process., vol. 56, no. 7, pp. 3315–3326, July 2008.
- M. E. Yildiz and A. Scaglione, “Differential nested lattice encoding for consensus problems,” in ACM/IEEE Information Processing in Sensor Networks, Cambridge, MA, Apr. 2007.
- A. T. Salehi and A. Jadbabaie, “On consensus in random networks,” paper presented at the The Allerton Conference on Communication, Control, and Computing, Allerton House, IL, Sept. 2006.
- M. Porfiri and D. J. Stilwell, “Stochastic consensus over weighted directed networks,” in Proceedings of the 2007 American Control Conference, New York, July 11–13, 2007.
- S. Kar and José M. F. Moura, “Distributed consensus algorithms in sensor networks: Link failures and channel noise,” IEEE Trans. Signal Process., 2008, accepted for publication.
- A. Kashyap, T. Basar, and R. Srikant, “Quantized consensus,” Automatica, vol. 43, pp. 1192–1203, July 2007.
- T. C. Aysal, M. J. Coates, and M. G. Rabbat, “Distributed average consensus with dithered quantization,” IEEE Trans. Signal Process., 2008, to appear.
- S. Kar and J. M. F. Moura, “Distributed consensus algorithms in sensor networks: Quantized data,” available: http://arxiv.org/abs/0712.1609, Nov. 2007.
- A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, “On distributed averaging algorithms and quantization effects,” Technical Report 2778, LIDS-MIT, Nov. 2007.
- P. Frasca, R. Carli, F. Fagnani, and S. Zampieri, “Average consensus on networks with quantized communication,” Int. J. Robust Nonlinear Control, 2008, submitted for publication.
- M. Huang and J. H. Manton, “Stochastic approximation for consensus seeking: Mean square and almost sure convergence,” in Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, LA, Dec. 12–14, 2007.
- R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algorithms and theory,” IEEE Trans. Automatic Control, vol. 51, no. 3, pp. 401–420, 2006.
- H. Tanner, A. Jadbabaie, and G. J. Pappas, “Flocking in fixed and switching networks,” IEEE Trans. Automatic Control, vol. 52, no. 5, pp. 863–868, 2007.
- U. A. Khan and J. M. F. Moura, “Distributing the Kalman filter for large-scale systems,” IEEE Trans. Signal Process., vol. 56, part 1, no. 10, pp. 4919–4935, Oct. 2008.
- I. D. Schizas, A. Ribeiro, and G. B. Giannakis, “Consensus-based distributed parameter estimation in ad hoc wireless sensor networks with noisy links,” in Proc. of Intl. Conf. on Acoustics, Speech and Signal Processing, Honolulu, HI, 2007, pp. 849– 852.
- R. Olfati-Saber, “Distributed Kalman filters with embedded consensus filters,” paper presented at the 44th IEEE Conference on Decision and Control, Seville, Spain, Dec. 2005, pp. 8179–8184.
- M. Alanyali and V. Saligrama, “Distributed tracking in multi-hop networks with communication delays and packet losses,” paper presented at the 13th IEEE Workshop on Statistical Sig. Proc., Bordeaux, France, July 2005, pp. 1190–1195.
- S. Kar, J. M. F. Moura, and K. Ramanan, “Distributed parameter estimation in sensor networks: Nonlinear observation models and imperfect communication,” available: http://arxiv.org/abs/0809.0009, Aug. 2008.
- A. Rahmani and M. Mesbahi, “Pulling the strings on agreement: Anchoring, controllability, and graph automorphism,” paper presented at the American Control Conference, New York City, July 11–13, 2007, pp. 2738–2743.
- U. A. Khan, S. Kar, and J. M. F. Moura, “Distributed sensor localization in random environments using minimal number of anchor nodes,” IEEE Trans. Signal Process., submitted for publication, see http://arxiv.org/abs/0802.3563, Aug. 2008.
- D. Bertsekas and J. Tsitsiklis, Parallel and Distributed Computations, Englewood Cliffs, NJ: Prentice-Hall, 1989.
- F. R. K. Chung, Spectral Graph Theory, Providence, RI: American Mathematical Society, 1997.
-
B. Bollobás, Modern Graph Theory, New York: Springer Verlag, 1998.
10.1007/978-1-4612-0619-4 Google Scholar
- B. Mohar, “The Laplacian spectrum of graphs,” in Graph Theory, Combinatorics, and Applications, Vol. 2, Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk (Eds.), New York: Wiley, 1991, pp. 871–898.
- A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, New York: Academic, 1970.
-
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge: Cambridge University Press, 1985.
10.1017/CBO9780511810817 Google Scholar
- P. Lancaster and M. Tismenetsky, The Theory of Matrices, Second Edition with Applications, Computer Science and Applied Mathematics, New York: Academic, 1985.
- C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 1997.
- H. L. Van Trees, Detection, Estimation, and Modulation Theory: Part I, New York: Wiley, 1968.
- R. R. Tenney and N. R. Sandell, Jr., “Detection with distributed sensors,” IEEE Trans. Aerospace Electron. Syst., vol. 17, no. 4, pp. 501–510, 1981.
- J. N. Tsitsiklis, “Decentralized detection,” in Advances in Statistical Signal Processing, H. V. Poor and J. B. Thomas (Eds.) Greenwich, CT: JAI Press, 1993, pp. 297–344.
- P. K. Willett, P. F. Swaszek, and R. S. Blum, “The good, bad, and ugly: Distributed detection of a known signal in dependent Gaussian noise,” IEEE Trans. Signal Process., vol. 48, no. 12, pp. 3266–3279, 2000.
-
S. Aldosari and J. M. F. Moura, “Fusion in sensor networks with communication constraints,” in IPSN04 Information Processing in Sensor Networks, Berkeley CA, Apr. 2004, IEEE/ACM, pp. 108–115.
10.1145/984622.984638 Google Scholar
- S. Aldosari and J. M. F. Moura, “Detection in decentralized sensor networks,” in ICASSP04, IEEE International Conference on Signal Processing, Vol. II, Montreal, Québec, Canada, May 17–21 2004, New York: IEEE, pp. 277–280.
- L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” Syst. Controls Lett., vol. 53, no. 1, pp. 65–78, Apr. 2004.
- S. A. Aldosari and J. M. F. Moura, “Distributed detection in sensor networks: connectivity graph and small-world networks,” paper presented at the 39th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, Oct. 2005, pp. 230–234.
- S. A. Aldosari and J. M. F. Moura, “Topology of sensor networks in distributed detection,” paper presented at the ICASSP'06, IEEE International Conference on Signal Processing, Vol. 5, Toulouse, France, May 2006, pp. 1061–1064.
- F. R. Gantmacher, Matrix Theory, Vol. I, Chelsea Publishing 1959.
- R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proc. IEEE, vol. 95, no. 1, pp. 215–233, Jan. 2007.
- G. E. Shilov and R. A. Silverman, Linear Algebra, Courier Dover, 1977.
- M. J. Sippl and H. A. Scheraga, “Cayley–Menger coordinates,” Proc. Nat. Acad. Sci. U.S.A., vol. 83, no. 8, pp. 2283–2287, Apr. 1986.
- G. Springer, Introduction to Riemann Surfaces, Reading, MA: Addison-Wesley, 1957.
- J. G. Hocking and G. S. Young, Topology, Reading, MA: Addison-Wesley, 1961.
-
L. S. Zurlo, P. E. Mercado, and C. E. de la Vega, “Parallelization of the linear load flow equations,” Power Tech. Proc. 2001 IEEE Porto, vol. 3, p. 5, 2001.
10.1109/PTC.2001.964959 Google Scholar
- L. Schenato and G. Gamba, “A distributed consensus protocol for clock synchronization in wireless sensor network,” paper presented at the Decision and Control, 2007 46th IEEE Conference on, Dec. 2007, pp. 2289–2294.
- G. Golub and C. Van Loan, Matrix Computations, Baltimore, MD: Johns Hopkins University Press, 1996.
- U. A. Khan and J. M. F. Moura, “Distributed Iterate-Collapse inversion (DICI) algorithm for L-banded matrices,” paper presented at the 33rd IEEE International Conference on Acoustics, Speech, and Signal Processing, Las Vegas, NV, Mar. 30–Apr. 4, 2008.
-
D. Kempe and F. McSherry, “A decentralized algorithm for spectral analysis,” in STOC '04: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, New York: ACM, 2004, pp. 561–568.
10.1145/1007352.1007438 Google Scholar
