On the complexity of distributed BFS in ad hoc networks with non-spontaneous wake-ups

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 a 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 . min(D; n=f(n)) . logD . log n) and with the number of point-to-point messages sent O(n. (min(D; n=f(n))+f(n)) . logD. 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(n2) message complexity, for some suitable functions f(n) = o(n= log2 n), provided D = o(n= log4 n).
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 3 (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-00965724
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 15:47:41
Dernière modification le : lundi 15 janvier 2018 - 11:43:26
Document(s) archivé(s) le : jeudi 26 juin 2014 - 10:51:36

Fichier

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

Identifiants

  • HAL Id : hal-00965724, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

300

Téléchargements de fichiers

157