On the complexity of distributed BFS in ad hoc networks with spontaneous wake-up.

Abstract : We study time and message complexity of the problem of building a BFS tree by a spontaneously awaken node in ad hoc network. Computation is in synchronous rounds, and messages are sent via point-to-point bi-directional links. Network topology is modeled by an undirected graph. Each node knows only its own id and the id's of its neighbors in the network and no pre-processing is allowed; therefore the solutions to the problem of spanning a BFS tree in this setting must be distributed. We deliver a deterministic distributed solution that trades time for messages, mainly, with time complexity $O(D\cdot\min(D,n/f(n)) \cdot \log D \cdot \log n)$ and with the number of point-to-point messages sent $O(n\cdot(\min(D,n/f(n)) + f(n)) \cdot \log D \cdot \log n)$, for any $n$-node network with diameter $D$ and for any monotonically non-decreasing sub-linear integer function $f$. Function $f$ in the above formulas come from the threshold value on node degrees used by our algorithms, in the sense that nodes with degree at most $f(n)$ are treated differently that the other nodes. This yields the first BFS-finding deterministic distributed algorithm in ad hoc networks working in time $o(n)$ and with $o(n^2)$ message complexity, for some suitable functions $f(n)=o(n/\log^2 n)$, provided $D=o(n/\log^4 n)$.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, 15 (3), pp.101-118
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00991414
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 15 mai 2014 - 11:33:57
Dernière modification le : lundi 15 janvier 2018 - 11:43:26
Document(s) archivé(s) le : vendredi 15 août 2014 - 11:01:19

Fichier

2321-8410-1-PB.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00991414, version 1

Collections

Citation

Dariusz R. Kowalski, Krzysztof Krzywdziński. On the complexity of distributed BFS in ad hoc networks with spontaneous wake-up.. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, 15 (3), pp.101-118. 〈hal-00991414〉

Partager

Métriques

Consultations de la notice

106

Téléchargements de fichiers

108