Efficient algorithms for leader election in radio networks

Abstract

We present energy efficient algorithms for leader election in single channel single-hop radio networks with no collision detection. We present a deterministic solution with sublogarithmic energy cost (the best previous result was O(log n)) and show a double logarithmic lower bound. We prove that this lower bound holds in a randomized case, in a certain sense.For the case, when the number n of active stations can be approximated in advance, we show a randomized algorithm with energy consumption O(log* n) that yields a result with high probability (the best previous result was O(log log n)).