Quasi-optimal energy-efficient leader election algorithms in radio networks

摘要

Radio networks (RN) are distributed systems (ad hoc networks) consisting in n ≥ 2 radio stations. Assuming the number n unknown, two distinct models of RN without collision detection (no-CD) are addressed: the model with weak no-CD RN and the one with strong no-CD RN. We design and analyze two distributed leader election protocols, each one running in each of the above two (no-CD RN) models, respectively. Both randomized protocols are shown to elect a leader within O(log (n)) expected time, with no station being awake for more than O(log log (n)) time slots (such algorithms are said to be energy-efficient). Therefore, a new class of efficient algorithms is set up that match the Ω(log (n)) time lower-bound established by Kushilevitz and Mansour [E. Kushilevitz, Y. Mansour, An Ω(D log(N/D)) lower-bound for broadcast in radio networks, SIAM J. Comp. 27 (1998) 702-712).].