Name
Title | ||
|---|---|---|
An Energy Efficient Leader Election Protocol for Radio Network with a Single Transceiver |
Abstract | ||
|---|---|---|
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 Ω(n) awake time slots, our leader election protocol is optimal in terms of the expected awake time slots. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1093/ietfec/e89-a.5.1355 | IEICE Transactions |
Keywords | Field | DocType |
log log n,time slot,energy efficient leader election,distributed algorithms,adhoc networks,radio network,single transceiver,leader election protocol need,protocol work,total awake time slot,log logn,awake time slot,collision detection,randomized algorithms,anonymous radio network,leader election protocol,energy efficient,energy dissipation,mobile station,leader election,distributed algorithm,randomized algorithm | Leader election,Randomized algorithm,Discrete mathematics,Radio networks,Transceiver,Collision detection,Computer science,Efficient energy use,Communication channel,Distributed algorithm | Journal |
Volume | Issue | ISSN |
E89-A | 5 | 0916-8508 |
Citations | PageRank | References |
5 | 0.48 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacir Luiz Bordim | 1 | 57 | 18.86 |
| Yasuaki Ito | 2 | 511 | 60.47 |
| Koji Nakano | 3 | 1165 | 118.13 |