Leader Election in Shared Spectrum Radio Networks

摘要

We study the leader election problem in the context of a congested single-hop radio network. We assume a collection of N synchronous devices with access to a shared band of the radio spectrum, divided into T frequencies. To model unpredictable congestion, we assume an abstract interference adversary that can choose up to t ＜ F frequencies in each round to disrupt, preventing communication. The devices are individually activated in arbitrary rounds by an adversary. On activation, a device does not know how many other devices (if any) are also active. The goal of the leader election problem is for each active device to output the id of a leader as soon as possible after activation, while preserving the safety constraint that all devices output the same leader, with high probability. We begin by establishing a lower bound of Ω((log~2 N/(F-t)log log N)+ (Ft)/(F-t)·log N) rounds, through reduction to an existing result in this model. We then set out to prove this bound tight (within log log N factors). For the case where t = 0, we present a novel randomized algorithm, based on a strategy of recruiting herald nodes, that works in Ο(log~2 N/F+log N) time. For 1 ≤ t ≤ F/6, we present a variant of our herald algorithm in which multiple real (potentially disrupted) frequencies are used to simulate each non-disrupted frequency from the t = 0 case. This algorithm works in Ο(log~2 N/F+ t log N) time. Finally, for t ＞ F/6 we show how-to improve the trapdoor protocol of [5], used to solve a similar problem in a non-optimal manner, to solve leader election in optimal Ο((log N+Ft)/(F-t)·log N) time, for (only) these large values of t. We also observe that if F = ω(1) and t ≤ (1-∈)F for a constant ∈ ＞ 0, our protocols beat the classic Ω(log~2 N) bound on wake-up in a single frequency radio network, underscoring the observation that more frequencies in a radio network allows for more algorithmic efficiency-even if devices can each only participate on a single frequency at a time, and a significant fraction of these frequencies are disrupted adversarially.