Information gathering in ad-hoc radio networks with tree topology

We study information gathering in ad-hoc radio networks without collision detection, focussing on the case when the network forms a tree with edges directed towards the root. Initially, each node has a piece of information that we refer to as a rumor. The goal is to deliver all rumors to the root of the tree as quickly as possible. The protocol must complete this task even if the tree topology is unknown. In the deterministic case, assuming that the nodes are labeled with small integers, we give an O(n)-time protocol that uses unbounded messages, and an O(n log n)-time protocol using bounded messages. We also consider fireand- forward protocols, in which a node can only transmit its own rumor or the rumor received in the previous step. We give a deterministic fire-and-forward protocol with running time O(n^1.5), and we show that it is asymptotically optimal. We then study randomized algorithms where the nodes are not labelled. In this model, we give an O(n log n)-time protocol and we prove that this bound is asymptotically optimal.