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 2 n (F −t) log log n + F t F −t log n " rounds are needed to synchronize. We then describe two algorithms. The first algorithm almost matches the lower bound, yielding a running time of O " log n " rounds. The second algorithm is adaptive, terminating in O`t log 3 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 3 nŕ ounds.
Recent work REF ] also focuses on the wireless synchronization problem which requires devices to be activated at different times on a congested single-hop radio network to synchronize their round numbering while an adversary can disrupt a certain number of frequencies per round.
The wireless synchronization problem
PODC '09
Computer Science