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

Jacir Luiz BORDIM; Yasuaki ITO; Koji NAKANO

doi:10.1093/ietfec/e89-a.5.1355

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

Jacir Luiz BORDIM, Yasuaki ITO, Koji NAKANO

Full Text Views

0

Share
Cite this

Summary :

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- (f ≥ 1), in log log n+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- (f ≥ 1), in log log n+o(log log n)+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 log n) 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1355-1361

Publication Date: 2006/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.5.1355

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Jacir Luiz BORDIM, Yasuaki ITO, Koji NAKANO, "An Energy Efficient Leader Election Protocol for Radio Network with a Single Transceiver" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 5, pp. 1355-1361, May 2006, doi: 10.1093/ietfec/e89-a.5.1355.
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- (f ≥ 1), in log log n+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- (f ≥ 1), in log log n+o(log log n)+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 log n) 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1355/_p

Copy

@ARTICLE{e89-a_5_1355,
author={Jacir Luiz BORDIM, Yasuaki ITO, Koji NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Energy Efficient Leader Election Protocol for Radio Network with a Single Transceiver},
year={2006},
volume={E89-A},
number={5},
pages={1355-1361},
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- (f ≥ 1), in log log n+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- (f ≥ 1), in log log n+o(log log n)+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 log n) 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.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1355},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - An Energy Efficient Leader Election Protocol for Radio Network with a Single Transceiver
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1355
EP - 1361
AU - Jacir Luiz BORDIM
AU - Yasuaki ITO
AU - Koji NAKANO
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1355
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - 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- (f ≥ 1), in log log n+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- (f ≥ 1), in log log n+o(log log n)+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 log n) 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.
ER -