Energy-Efficient Leader Election Protocols for Single-Hop Radio Networks

Marcin Kardas 1 Marek Klonowski 1 Dominik Pajak 2, 3
1 IMCS - Institute of Mathematics and Computer Science [Wroclaw]
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 LaBRI - Laboratoire Bordelais de Recherche en Informatique
Abstract : In this paper we investigate leader election protocols for single-hop radio networks from perspective of energetic complexity. We discuss different models of energy consumption and its relation with time complexity. We also present some results about energy consumption in classic protocols optimal with respect to time complexity -- we show that some very basic, intuitive algorithms for simplest models (with known number of stations) do not have to be optimal when energy of stations is restricted. We show that they can be significantly improved by introducing very simple modifications. Our main technical result is however a protocol for solving leader election problem in case of unknown number of stations $n$, working on expectancy within $O(\log^\epsilon n)$ rounds, with each station transmitting $O(1)$ number of times and no station being awake for more than $O(\log \log \log n)$ rounds.
Type de document :
Communication dans un congrès
ICPP - 42nd International Conference on Parallel Processing, Oct 2013, Lyon, France. IEEE, pp.399-408, 2013, ICPP. 〈10.1109/ICPP.2013.49〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00996429
Contributeur : Dominik Pajak <>
Soumis le : lundi 26 mai 2014 - 15:10:05
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : mardi 26 août 2014 - 12:00:34

Fichier

i3e-main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | LABRI | UNIV-BORDEAUX | INRIA-BORDEAUX

Citation

Marcin Kardas, Marek Klonowski, Dominik Pajak. Energy-Efficient Leader Election Protocols for Single-Hop Radio Networks. ICPP - 42nd International Conference on Parallel Processing, Oct 2013, Lyon, France. IEEE, pp.399-408, 2013, ICPP. 〈10.1109/ICPP.2013.49〉. 〈hal-00996429〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

319

Téléchargements de fichiers

157

Contact


archive-ouverte@inria.fr