This article is part of the series Novel Techniques for Analysis and Design of Cross-Layer Optimized Wireless Sensor Networks.

Open Access Research Article

Distributed Time Synchronization in Wireless Sensor Networks with Coupled Discrete-Time Oscillators

O Simeone1* and U Spagnolini2

Author Affiliations

1 Center for Wireless Communications and Signal Processing Research, New Jersey Institute of Technology, University Heights, Newark, NJ 07102-1982, USA

2 Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci 32, Milano 20133, Italy

For all author emails, please log on.

EURASIP Journal on Wireless Communications and Networking 2007, 2007:057054 doi:10.1155/2007/57054


The electronic version of this article is the complete one and can be found online at: http://jwcn.eurasipjournals.com/content/2007/1/057054


Received:25 September 2006
Accepted:30 March 2007
Published:18 June 2007

© 2007 Simeone and Spagnolini

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

In wireless sensor networks, distributed timing synchronization based on pulse-coupled oscillators at the physical layer is currently being investigated as an interesting alternative to packet synchronization. In this paper, the convergence properties of such a system are studied through algebraic graph theory, by modeling the nodes as discrete-time clocks. A general scenario where clocks may have different free-oscillation frequencies is considered, and both time-invariant and time-variant network topologies (or fading channels) are discussed. Furthermore, it is shown that the system of oscillators can be studied as a set of coupled discrete-time PLLs. Based on this observation, a generalized system design is discussed, and it is proved that known results in the context of conventional PLLs for carrier acquisition have a counterpart in distributed systems. Finally, practical details of the implementation of the distributed synchronization algorithm over a bandlimited noisy channel are covered.

References

  1. F Sivrikaya, B Yener, Time synchronization in sensor networks: a survey. IEEE Network 18(4), 45–50 (2004). Publisher Full Text OpenURL

  2. Y-W Hong, A Scaglione, A scalable synchronization protocol for large scale sensor networks and its applications. IEEE Journal on Selected Areas in Communications 23(5), 1085–1099 (2005)

  3. RE Mirollo, SH Strogatz, Synchronization of pulse-coupled biological oscillators. SIAM Journal on Applied Mathematics 50(6), 1645–1662 (1990). Publisher Full Text OpenURL

  4. D Lucarelli, I-J Wang, Decentralized synchronization protocols with nearest neighbor communication. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys '04), November 2004, Baltimore, Md, USA, 62–68

  5. C Godsil, G Royle, Algebraic Graph Theory (Springer, New York, NY, USA, 2001)

  6. G Werner-Allen, G Tewari, A Patel, M Welsh, R Nagpal, Firefly-inspired sensor network synchronicity with realistic radio effects. Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (SenSys '05), November 2005, San Diego, Calif, USA, 142–153

  7. A-S Hu, SD Servetto, On the scalability of cooperative time synchronization in pulse-connected networks. IEEE Transactions on Information Theory 52(6), 2725–2748 (2006)

  8. Y-W Hong, A Scaglione, Distributed change detection in large scale sensor networks through the synchronization of pulse-coupled oscillators. Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '04), May 2004, Montreal, Quebec, Canada 3, 869–872

  9. S Barbarossa, F Celano, Self-organizing sensor networks designed as a population of mutually coupled oscillators. Proceedings of the 6th IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC '05), June 2005, New York, NY, USA, 475–479

  10. N Wakamiya, M Murata, Scalable and robust scheme for data fusion in sensor networks. Proceedings of the 1st International Workshop on Biologically Inspired Approaches to Advanced Information Technology (Bio-ADIT '04), January 2004, Lausanne, Switzerland, 412–427

  11. F Tong, Y Akaiwa, Theoretical analysis of interbase-station synchronization systems. IEEE Transactions on Communications 46(5), 590–594 (1998). Publisher Full Text OpenURL

  12. E Sourour, M Nakagawa, Mutual decentralized synchronization for intervehicle communications. IEEE Transactions on Vehicular Technology 48(6), 2015–2027 (1999). Publisher Full Text OpenURL

  13. R Olfati-Saber, RM Murray, Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control 49(9), 1520–1533 (2004). Publisher Full Text OpenURL

  14. L Moreau, Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control 50(2), 169–182 (2005)

  15. WC Lindsey, F Ghazvinian, WC Hagmann, K Dessouky, Network synchronization. Proceedings of the IEEE 73(10), 1445–1467 (1985)

  16. TS Rappaport, Wireless Communications: Principles and Practice (Prentice-Hall, Upper Saddle River, NJ, USA, 2001)

  17. L Xiao, S Boyd, S-J Kim, Distributed average consensus with least-mean-square deviation. Journal of Parallel and Distributed Computing 67(1), 33–46 (2007). Publisher Full Text OpenURL

  18. RA Horn, CR Johnson, Matrix Analysis (Cambridge University Press, Cambridge, UK, 1985)

  19. X-D Zhang, R Luo, Upper bound for the non-maximal eigenvalues of irreducible nonnegative matrices. Czechoslovak Mathematical Journal 52(3), 537–544 (2002). Publisher Full Text OpenURL

  20. VV Veeravalli, Decentralized quickest change detection. IEEE Transactions on Information Theory 47(4), 1657–1665 (2001). Publisher Full Text OpenURL

  21. JR Norris, Markov Chains (Cambridge University Press, Cambridge, UK, 1998)

  22. SN Elaydi, An Introduction to Difference Equations (Springer, New York, NY, USA, 1999)

  23. G Scutari, S Barbarossa, L Pescosolido, Optimal decentralized estimation through self-synchronizing networks in the presence of propagation delays. Proceedings of the 7th IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC '06), July 2006, Cannes, France, 1–5

  24. H Meyr, M Moeneclaey, SA Fechtel, Digital Communication Receivers (John Wiley & Sons, New York, NY, USA, 1998)

  25. FM Gardner, Phaselock Techniques (John Wiley & Sons, New York, NY, USA, 1966)

  26. O Simeone, U Spagnolini, Y Bar-Ness, "Small-world" effect of shadowing in pulse-couple distributed time synchronization. IEEE Communications Letters 11(3), 282–284 (2007)