The wireless synchronization problem

ABSTRACT

In this paper, we study the wireless synchronization problem which requires devices activated at different times on a congested single-hop radio network to synchronize their round numbering. We assume a collection of n synchronous devices with access to a shared band of the radio spectrum, divided into F narrowband frequencies. We assume that the communication medium suffers from unpredictable, perhaps even malicious interference, which we model by an adversary that can disrupt up to t frequencies per round. Devices begin executing in different rounds and the exact number of participants is not known in advance.

We first prove a lower bound, demonstrating that at least Ω(log²n/(F-t)loglogn + Ft/F-t logn) rounds are needed to synchronize. We then describe two algorithms. The first algorithm almost matches the lower bound, yielding a running time of O(F/F - t log²n + Ft/F - t logn) rounds. The second algorithm is adaptive, terminating in O(t′ log³n) rounds in good executions, that is, when the devices begin executing at the same time, and there are never more than t′ frequencies disrupted in any given round, for some t′ < t. In all executions, even those that are not good, it terminates in O(F log³n) rounds.

REFERENCES

• 1: Norman Abramson, THE ALOHA SYSTEM: another alternative for computer communications, Proceedings of the November 17-19, 1970, fall joint computer conference, November 17-19, 1970, Houston, Texas [doi>10.1145/1478462.1478502]
• 2: Ian F. Akyildiz , Won-Yeol Lee , Mehmet C. Vuran , Shantidev Mohanty, NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.13, p.2127-2159, 15 September 2006 [doi>10.1016/j.comnet.2006.05.001]
• 3: N. Alon , A. Bar-Noy , N. Linial , D. Peleg, On the complexity of radio communication, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.274-285, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73033]
• 4: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection, Distributed Computing, v.5 n.2, p.67-71, September 1991 [doi>10.1007/BF02259748]
• 5: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 6: Annalisa De Bonis , Leszek Gasieniec , Ugo Vaccaro, Optimal Two-Stage Algorithms for Group Testing Problems, SIAM Journal on Computing, v.34 n.5, p.1253-1270, 2005 [doi>10.1137/S0097539703428002]
• 7: I. Chlamtac and S. Kutten. On broadcasting in radio networks--problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240--1246, 1985.
• 8: Bogdan S. Chlebus , Dariusz R. Kowalski, A better wake-up in radio networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011806]
• 9: Bogdan S. Chlebus , Leszek Gąsieniec , Alan Gibbons , Andrzej Pelc , Wojciech Rytter, Deterministic broadcasting in unknown radio networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.861-870, January 09-11, 2000, San Francisco, California, United States
• 10: Bogdan S. Chlebus , Leszek Gasieniec , Alan Gibbons , Andrzej Pelc , Wojciech Rytter, Deterministic broadcasting in ad hoc radio networks, Distributed Computing, v.15 n.1, p.27-38, January 2002 [doi>10.1007/s446-002-8028-1]
• 11: Marek Chrobak , Leszek Gasieniec , Dariusz Kowalski, The wake-up problem in multi-hop radio networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 12: Marek Chrobak , Leszek Gasieniec , Wojciech Rytter, Fast broadcasting and gossiping in radio networks, Journal of Algorithms, v.43 n.2, p.177-189, May 2002 [doi>10.1016/S0196-6774(02)00004-4]
• 13: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Round Robin is optimal for fault-tolerant broadcasting on wireless networks, Journal of Parallel and Distributed Computing, v.64 n.1, p.89-96, January 2004 [doi>10.1016/j.jpdc.2003.09.002]
• 14: Artur Czumaj , Wojciech Rytter, Broadcasting Algorithms in Radio Networks with Unknown Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.492, October 11-14, 2003
• 15: S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. Gossiping in a multi-channel radio network: An oblivious approach to coping with malicious interference. In Proceedings of the International Symposium on Distributed Computing, 2007.
• 16: Shlomi Dolev , Seth Gilbert , Rachid Guerraoui , Calvin Newport, Secure communication over radio channels, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400767]
• 17: M. Farach-Colton, R. J. Fernandes, and M. A. Mosteiro. Lower bounds for clear transmissions in radio networks. In Proceedings of the Latin American Symposium on Theoretical Informatics, 2006.
• 18: Leszek Gasieniec , Andrzej Pelc , David Peleg, The Wakeup Problem in Synchronous Broadcast Systems, SIAM Journal on Discrete Mathematics, v.14 n.2, p.207-222, 2001 [doi>10.1137/S0895480100376022]
• 19: S. Gilbert, R. Guerraoui, D. Kowalski, and C. Newport. Interference-resilient information exchange. In Proceedings of the IEEE Conference on Computer Communications, 2009.
• 20: Ramakrishna Gummadi , David Wetherall , Ben Greenstein , Srinivasan Seshan, Understanding and mitigating the impact of RF interference on 802.11 networks, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 21: Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
• 22: Tomasz Jurdzinski , Grzegorz Stachowiak, Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks, Proceedings of the 13th International Symposium on Algorithms and Computation, p.535-549, November 21-23, 2002
• 23: J. Komlos and A. Greenberg. An asymptotically fast non-adaptive algorithm for conflict resolution in multiple access channels. IEEE Transactions on Information Theory, March 1985.
• 24: Dariusz R. Kowalski , Andrzej Pelc, Broadcasting in undirected ad hoc radio networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.73-82, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872045]
• 25: D. Kowalski and A. Pelc. Time of radio broadcasting: Adaptiveness vs. obliviousness and randomization vs. determinism. In Proceedings of the Colloquium on Structural Information and Communication Complexity, 2003.
• 26: Dariusz R. Kowalski , Andrzej Pelc, Time of Deterministic Broadcasting in Radio Networks with Local Knowledge, SIAM Journal on Computing, v.33 n.4, p.870-891, 2004 [doi>10.1137/S0097539702419339]
• 27: Dariusz R. Kowalski , Andrzej Pelc, Deterministic Broadcasting Time in Radio Networks of Unknown Topology, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.63-72, November 16-19, 2002
• 28: Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract), Proceedings of the 6th Annual European Symposium on Algorithms, p.283-294, August 24-26, 1998
• 29: Dominic Meier , Yvonne Anne Pignolet , Stefan Schmid , Roger Wattenhofer, Speed Dating Despite Jammers, Proceedings of the 5th IEEE International Conference on Distributed Computing in Sensor Systems, p.1-14, June 08-10, 2009, Marina del Rey, CA, USA [doi>10.1007/978-3-642-02085-8_1]
• 30: Mario Strasser , Christina Pöpper , Srdjan Capkun , Mario Cagalj, Jamming-resistant Key Establishment using Uncoordinated Frequency Hopping, Proceedings of the 2008 IEEE Symposium on Security and Privacy, p.64-78, May 18-21, 2008 [doi>10.1109/SP.2008.9]
• 31: Mario Strasser , Christina Pöpper , Srdjan Čapkun, Efficient uncoordinated FHSS anti-jamming communication, Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing, May 18-21, 2009, New Orleans, LA, USA [doi>10.1145/1530748.1530778]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Theory

Keywords:
disrupted radio channel, synchronization