Distributed wireless network's devices are battery-powered most of the time. Transmitting a message uses more energy than receiving one which spends more energy than internal computations. Therefore in this paper, we will focus on the energy complexity of leader election, a fundamental distributed computing problem. As the message's size impacts on the energy consumption, we highlight that our algorithms have almost optimal time complexities: each device is allowed to send only once 1 - bit message and to listen to the network during at most 2 time slots. We will firstly work on Radio Networks on which the devices can detect when a node transmits alone: RNstrongCD where both senders and receivers have collision detection capability, RNsenderCD, RNreceiverCD and RNnoCD. If the nodes know their number n, our algorithm elects a leader in optimal O(log n) time slots with a probability of 1 - 1/poly(n). Then, if all nodes do not know n but know its upper bound u such that log u = Θ(log n), it has O(log~2 n) time complexity on RNnoCD and RNsenderCD. On RNreceiverCD and RNstrongCD, it has O(log~(1+α) n) time complexity where α∈]0,1[ is constant. For the Beeping Networks model on which the devices cannot detect single transmissions, it has O(n~α) time complexity with probability 1 - 1/poly(n).
展开▼
