Transmitting Once to Elect a Leader on Wireless Networks.

Distributed wireless network devices are mostly battery-powered. Transmitting a message on distributed wireless networks uses more energy than receiving one, which in turn uses more energy than internal computations. Therefore, in this paper, we study the problem of randomized leader election in synchronous distributed single-hop networks with a special focus on the energy complexity. We provide algorithmic solutions to the implicit version of leader election problem where non-leader nodes need not be aware of the identity of the leader. Because the size of a message impacts the energy consumption, we highlight that the solutions we propose consume very little energy: each device is allowed to send a single one-bit message only once and listen to the network during two time slots at most. We first consider four well-studied variants of the radio network (RN) model depending on the transmission and reception abilities of the participating devices: RNstrongCD: both transmitters and listeners can detect collision, RNsenderCD: only transmitters can detect collision, RNCD: only listeners can detect collision, RNnoCD: no device can detect collision. Next, we study the beeping network model. The time and energy complexities of all our algorithms are deterministic and they succeed in electing a unique leader with high probability even under the restriction that each node can only send once a single one-bit signal. When the nodes are aware of the total number n of the participants, our algorithm elects a leader in O (log n) rounds. When n is not known beforehand but an upper bound u on n with log u = Θ (log n) is known by all participating nodes, we design a randomized algorithm with O (log 2 n) time complexity for the RN models. For beeping networks, our algorithm has O (n ε) time complexity ( 0 < ε < 1 ). The parameter ε can be tuned to increase the probability of success of the algorithms. [ABSTRACT FROM AUTHOR]