Skip Navigation

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 2006 E89-A(5):1355-1361; doi:10.1093/ietfec/e89-a.5.1355
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Request Permissions
Google Scholar
Right arrow Articles by BORDIM, J. L.
Right arrow Articles by NAKANO, K.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Copyright © 2006 The Institute of Electronics, Information and Communication Engineers

Special Section on Discrete Mathematics and Its Applications -- Papers

An Energy Efficient Leader Election Protocol for Radio Network with a Single Transceiver

Jacir Luiz BORDIM1, Yasuaki ITO2 and Koji NAKANO2

1 The author is with the Department of Computer Science, University of Brasilia, 70910-900 Brasilia - DF, Brazil., 2 The authors are with the School of Engineering, Hiroshima University, Higashihiroshima-shi, 739-8527 Japan. E-mail: nakano{at}hiroshima-u.ac.jp

In this work we present an energy efficient leader election protocol for anonymous radio network populated with n mobile stations. Previously, Nakano and Olariu have presented a leader election protocol that terminates, with probability exceeding 1 – 1/f (f ≥ 1), in log logn + o(log log n)+ O(log f) time slots [14]. As the above protocol works under the assumption that every station has the ability to transmit and monitor the channel at the same time, it requires every station to be equipped with two transceivers. This assumption, however, is unrealistic for most mobile stations due to constraints in cost, size, and energy dissipation. Our main contribution is to show that it is possible to elect a leader in an anonymous radio network where each station is equipped with a single transceiver. Quite surprisingly, although every station has only one transceiver, our leader election protocol still runs, with probability exceeding 1 – 1/f(f ≥ 1), in log log n + o(log logn)+ O(log f) time slots. Moreover, our leader election protocol needs only expected O(n) total awake time slots, while Nakano and Olariu's protocol needs expected O(nlog logn) total awake time slots. Since every leader election protocol needs at least {Omega}(n) awake time slots, our leader election protocol is optimal in terms of the expected awake time slots.

Key Words: adhoc networks, collision detection, distributed algorithms, randomized algorithms

Manuscript received August 22, 2005. Manuscript revised November 6, 2005. Final manuscript received December 15, 2005.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.