efficient algorithms for leader election in radio networks
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 )).
efficiency algorithm radio network energy energy efficiency collision detection log cost lower bound randomization case activation randomized algorithm energy consumption probability