Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism

Abstract : In this paper the problem of information dissemination in Mobile Ad-hoc Networks (MANETs) is studied. The problem is to disseminate a piece of information, initially held by a distinguished source node, to all nodes in a target set. We assume a weak set of restrictions on the mobility of nodes, parameterized by α, the disconnection time, and β, the link stability time, such that the MANETs considered are connected enough for dissemination. Such a connectivity model generalizes previous models in that we assume much less connectivity, or make explicit the assumptions in previous papers. In MANETs, nodes are embedded in the plane and can move with bounded speed. Communication between nodes occurs over a collisionprone single channel. We show upper and lower bounds for different types of randomized protocols, parameterized by α and β. This problem has been extensively studied in static networks and for deterministic protocols. We show tight bounds on the randomized complexity of information dissemination in MANETs, for reasonable choices of α and β. We show that randomization reduces the time complexity of the problem by a logarithmic or linear factor, depending on the class of randomized protocol considered.
Type de document :
Communication dans un congrès
David Fernández-Baca. LATIN, 2012, Unknown, Springer, 7256, pp.303-314, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29344-3_26〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00992680
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 10:47:31
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : lundi 10 avril 2017 - 23:33:36

Fichier

15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Martin Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, Shmuel Zaks. Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism. David Fernández-Baca. LATIN, 2012, Unknown, Springer, 7256, pp.303-314, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29344-3_26〉. 〈hal-00992680〉

Partager

Métriques

Consultations de la notice

113

Téléchargements de fichiers

63