Information Gathering in Ad-Hoc Radio Networks

Abstract In the ad-hoc radio network model, nodes communicate with their neighbors via radio signals, without knowing the topology of the underlying digraph. We study the information gathering problem, where each node has a piece of information called a rumor, and the objective is to transmit all rumors to the designated target node. For the model without any collision detection we provide an O ˜ ( n 1.5 ) deterministic protocol, significantly improving the trivial bound of O ( n 2 ) . We also consider a model with a mild form of collision detection, where a node receives a 1-bit acknowledgment if its transmission was received by at least one out-neighbor. For this model we give an O ˜ ( n ) deterministic protocol for information gathering in acyclic graphs.