Decentralized synchronization protocols with nearest neighbor communication

ABSTRACT

A class of synchronization protocols for dense, large-scale sensor networks is presented. The protocols build on the recent work of Hong, Cheow, and Scaglione [5, 6] in which the synchronization update rules are modeled by a system of pulse-coupled oscillators. In the present work, we define a class of models that converge to a synchronized state based on the local communication topology of the sensor network only, thereby lifting the all-to-all communication requirement implicit in [5, 6]. Under some rather mild assumptions of the connectivity of the network over time, these protocols still converge to a synchronized state when the communication topology is time varying.

REFERENCES

• 1: N. Biggs. Algebraic Graph Theory. Cambridge University Press, Cambridge, UK, 1996.
• 2: Jeremy Elson , Deborah Estrin, Time Synchronization for Wireless Sensor Networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.186, April 23-27, 2001
• 3: J. Elson and K. Romer. Wireless sensor networks: A new regime for time synchronization. In Proceedings of the First Workshop on Hot Topics In Networks, 2002.
• 4: C. Godsil and G. Royle. Algebraic Graph Theory. Springer-Verlag, New York, New York, 2001.
• 5: Y. W. Hong and A. Scaglione. Time synchronization and reach-back communications with pulse-coupled oscillators for UWB. In Proceedings of the IEEE Conference on Ultra Wideband Systems and Technologies, Reston, VA, November 2003.
• 6: Y. W. Hong, L. F. Cheow, and A. Scaglione. A simple method to reach detection consensus in massively distributed sensor networks. In Proceedings of the IEEE International Symposium on Information Theory, Chicago, IL, June 2004.
• 7: Frank C. Hoppensteadt , Eugene M. Izhikevich, Weakly connected neural networks, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 8: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 9: An-swol Hu , Sergio D. Servetto, Asymptotically optimal time synchronization in dense sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941352]
• 10: E. Izhikevich. Weakly pulse-coupled oscillators, FM interactions, synchronization, and oscillatory associative memory. IEEE Transactions on Neural Networks, 10(3):508--526, May 1999.
• 11: A. Jadbabaie, J. Lin, and A. S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6):15--30, 2003.
• 12: H. Khalil. Nonlinear Systems. Prentice Hall, Upper Saddle River, New Jersey, 1996.
• 13: Yoshiki Kuramoto, Collective synchronization of pulse-coupled oscillators and excitable units, Physica D, v.50 n.1, p.15-30, May 1991 [doi>10.1016/0167-2789(91)90075-K]
• 14: D. Liberzon and A. S. Morse. Basic problems in stability and design of switched systems. IEEE Control Systems Magazine, 19(5):59--70, 1999.
• 15: Renato E. Mirollo , Steven H. Strogatz, Synchronization of pulse-coupled biological oscillators, SIAM Journal on Applied Mathematics, v.50 n.6, p.1645-1662, Dec. 1990 [doi>10.1137/0150098]
• 16: L. Moreau. Leaderless coordination via bidirectional and unidirectional time-dependent communication. In Proceedings of the IEEE Conference on Decision and Control, pages 3070--3075, Maui, Hawaii, December 2003.
• 17: L. Moreau. Stability of multi-agent systems with time-dependent communication links. Preprint http://arxiv.org/abs/math.OC/0306426, 2003.
• 18: R. Olfati-Saber and R. M. Murray. Consensus protocols for networks of dynamic agents. In Proceedings of the American Control Conference, pages 951--956, Denver, CO, June 2003.
• 19: R. Olfati-Saber and R. M. Murray. Agreement problems in networks with directed graphs and switching topology. In Proceedings of the IEEE Conference on Decision and Control, pages 4126--4132, Maui, Hawaii, December 2003.
• 20: W. Ren, R. W. Beard, and T. W. McLain. Coordination variables and consensus building in multiple vehicle systems. In Proceedings of the Block Island Workshop on Cooperative Control, Springer-Verlag Series: Lecture Notes in Control and Information Sciences, 2003.(to appear).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Theory

Keywords:
pulse-coupled oscillators, sensor networks, synchronization