The wireless synchronization problem
The wireless synchronization problem
复制标题
无线同步问题
DOI：
10.1145/1582716.1582749
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Calvin C. Newport
中科院分区：
文献类型：
--
作者：
S. Dolev;Seth Gilbert;R. Guerraoui;F. Kuhn;Calvin C. Newport
在本文中，我们研究的<i>无线同步问题</i>，需要在不同的时间激活的设备在一个拥挤的单跳无线电网络，以同步其轮编号。我们假设一个集合的<i>n个</i>同步设备的访问无线电频谱的共享频带，分为<i>F个</i>窄带频率。我们假设通信介质遭受不可预测的，甚至可能是恶意的干扰，我们的对手，可以破坏高达<i>t</i>频率每轮模型。设备开始在不同的轮中执行，并且参与者的确切数量事先不知道。
我们首先证明了一个下界，证明了至少需要Ω（log<i>2n</i>/（<i>F-t</i>）<i>loglogn</i>+<i>Ft</i>/<i>F-tlogn</i>）轮才能同步.<i></i><i></i><i></i><sup></sup>然后，我们描述两个算法。第一个算法几乎匹配下界，产生<i>O</i>（<i>F</i>/F-tlog<sup>2</sup><i>n</i> +<i>Ft</i>/F-tlog<i>n</i>）轮的运行时间。<i></i><i></i><i></i><i></i>第二个算法是<i>自适应的</i>，在<i>良好的</i>执行中，在<i>O</i>（<i>t</i>′ log<sup>3</sup><i>n</i>）轮中终止，也就是说，当设备开始同时执行时，并且对于某些<i>t</i>′ <<i>t，</i>在任何给定的轮中，中断的频率都不会超过<i>t</i>′。在所有的执行中，即使是那些不好的执行，它也会在<i>O</i>（<i>F</i>log<sup>3</sup><i>n</i>）轮中终止。
In this paper, we study the <i>wireless synchronization problem</i> which requires devices activated at different times on a congested single-hop radio network to synchronize their round numbering. We assume a collection of <i>n</i> synchronous devices with access to a shared band of the radio spectrum, divided into <i>F</i> 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 <i>t</i> 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<sup>2</sup><i>n</i>/(<i>F</i>-<i>t</i>)loglog<i>n</i> + <i>Ft</i>/<i>F</i>-<i>t</i> log<i>n</i>) rounds are needed to synchronize. We then describe two algorithms. The first algorithm almost matches the lower bound, yielding a running time of <i>O</i>(<i>F</i>/<i>F</i> - <i>t</i> log<sup>2</sup><i>n</i> + <i>Ft</i>/<i>F</i> - <i>t</i> log<i>n</i>) rounds. The second algorithm is <i>adaptive</i>, terminating in <i>O</i>(<i>t</i>′ log<sup>3</sup><i>n</i>) rounds in <i>good</i> executions, that is, when the devices begin executing at the same time, and there are never more than <i>t</i>′ frequencies disrupted in any given round, for some <i>t</i>′ < <i>t</i>. In all executions, even those that are not good, it terminates in <i>O</i>(<i>F</i> log<sup>3</sup><i>n</i>) rounds.