On the complexity of distributed BFS in ad hoc networks with non-spontaneous wake-ups
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)) . log D . log n) and with the number of point-to-point messages sent O (n . (min (D, n = f (n)) + f (n)) . log D . 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).
ad hoc network message complexity bfs tree distributed algorithm