skip to main content
10.1145/1363686.1364164acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
research-article

Synchronization of strongly pulse-coupled oscillators with refractory periods and random medium access

Published: 16 March 2008 Publication History

Abstract

The weakly pulse-coupled oscillator framework has proven to be a valuable resource for the development of peer-to-peer synchronization algorithms [9]. But leveraging it in a practical implementation (e.g. in wireless ad hoc/sensor networks) is problematic due to the difficulty in achieving precise coordination of broadcast messages. We found that a pseudo-random medium access control (MAC) protocol produces a super-linear increase in the number of messages required per node with increasing network size, which would normally discourage its use. However, introducing a "refractory period" reduces this growth to linear with a small constant (verified by numerical simulations). Furthermore, the refractory period allows for an increase in the coupling constant, effectively making the network "strongly" pulse-coupled. We show that the combination of the refractory period, strong coupling, and probabilistic medium access results in a significant decrease in the average number of messages required per node in several practical network topologies (and as much as ~ 90% over the original idealistic mechanism in line topologies).

References

[1]
Green Hills Software. http://www.ghs.com.
[2]
I. Chlamtac, C. Petrioli, and J. Redi. Energy-conserving access protocols for identification networks. IEEE/ACM Transactions on Networking, 7(1):51--59, 1999.
[3]
L. Dai, P. Basu, and J. Redi. An accurate and energy efficient scheme for slot synchronization in wireless sensor networks. In Proceedings of IEEE/Create Net BROADNETS Conference, 2006.
[4]
E. M. Izhikevich. Weakly pulse-coupled oscillators, FM interactions, synchronization, and oscillatory associative memory. IEEE Transactions on Neural Networks, 10(3):508--26, 1999.
[5]
Y. Kuramoto. Collective synchronization of pulse-coupled oscillators and excitable units. Physica D, 50:15--30, 1991.
[6]
L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--65, 1978.
[7]
D. Lucarelli and I. Wang. Decentralized synchronization protocols with nearest neighbor communication. In Proceedings of SenSys, 2004.
[8]
M. Maróti, B. Kusy, G. Simon, and A. Lédeczi. The flooding time synchronization protocol. In Proceedings of SenSys, 2004.
[9]
R. Mirollo and S. Strogatz. Synchronization of pulse-coupled biological oscillators. SIAM Journal of Applied Math, 50(6):1645--62, 1990.
[10]
L. Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control, 50(2):169--182, 2005.
[11]
J. Redi. Energy-Conserving Protocols for Wireless Data Networks. PhD thesis, Boston University, 1998.
[12]
A. Scaglione and Y. Hong. Time synchronization and reach-back communications with pulse-coupled oscillators for UWB wireless ad hoc networks. In the IEEE Conference on Ultra Wideband Systems and Technologies, 2003.
[13]
SiRF Technologies. SiRFstarIII GSC3e/LP product insert. http://www.sirf.com.
[14]
U.S. Department of Defense. Global positioning system standard positioning service performance standard. http://www.navcen.uscg.gov, 2001.
[15]
G. Werner-Allen, G. Tewari, A. Patel, M. Welsh, and R. Nagpal. Firefly-inspired sensor network synchronicity with realistic radio effects. In Proceedings of SenSys, 2005.

Cited By

View all
  • (2020)Multi-scale verification of distributed synchronisationFormal Methods in System Design10.1007/s10703-020-00347-zOnline publication date: 20-Sep-2020
  • (2017)Self-Synchronization in Duty-Cycled Internet of Things (IoT) ApplicationsIEEE Internet of Things Journal10.1109/JIOT.2017.27571384:6(2058-2069)Online publication date: Dec-2017
  • (2017)Investigating Parametric Influence on Discrete Synchronisation Protocols Using Quantitative Model CheckingQuantitative Evaluation of Systems10.1007/978-3-319-66335-7_14(224-239)Online publication date: 11-Aug-2017
  • Show More Cited By

Index Terms

  1. Synchronization of strongly pulse-coupled oscillators with refractory periods and random medium access

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SAC '08: Proceedings of the 2008 ACM symposium on Applied computing
    March 2008
    2586 pages
    ISBN:9781595937537
    DOI:10.1145/1363686
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 16 March 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. pulse-coupled oscillators
    2. self-organizing
    3. synchronization
    4. wireless sensor networks

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    SAC '08
    Sponsor:
    SAC '08: The 2008 ACM Symposium on Applied Computing
    March 16 - 20, 2008
    Fortaleza, Ceara, Brazil

    Acceptance Rates

    Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

    Upcoming Conference

    SAC '25
    The 40th ACM/SIGAPP Symposium on Applied Computing
    March 31 - April 4, 2025
    Catania , Italy

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2020)Multi-scale verification of distributed synchronisationFormal Methods in System Design10.1007/s10703-020-00347-zOnline publication date: 20-Sep-2020
    • (2017)Self-Synchronization in Duty-Cycled Internet of Things (IoT) ApplicationsIEEE Internet of Things Journal10.1109/JIOT.2017.27571384:6(2058-2069)Online publication date: Dec-2017
    • (2017)Investigating Parametric Influence on Discrete Synchronisation Protocols Using Quantitative Model CheckingQuantitative Evaluation of Systems10.1007/978-3-319-66335-7_14(224-239)Online publication date: 11-Aug-2017
    • (2014)Scalability Issues of Firefly-Based Self-Synchronization in Collective Adaptive SystemsProceedings of the 2014 IEEE Eighth International Conference on Self-Adaptive and Self-Organizing Systems Workshops10.1109/SASOW.2014.15(68-73)Online publication date: 8-Sep-2014
    • (2013)Blind and buffer phase area based on M&S model fireflies synchronization in WSNs2013 First International Symposium on Future Information and Communication Technologies for Ubiquitous HealthCare (Ubi-HealthTech)10.1109/Ubi-HealthTech.2013.6708071(1-4)Online publication date: Jul-2013
    • (2011)EBSProceedings of the 5th International Conference on Communication System Software and Middleware10.1145/2016551.2016560(1-6)Online publication date: 4-Jul-2011
    • (2008)Opportunistic forwarding in wireless networks with duty cyclingProceedings of the third ACM workshop on Challenged networks10.1145/1409985.1409991(19-26)Online publication date: 15-Sep-2008

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media