Information gathering in ad-hoc radio networks with tree topology

We study the problem of information gathering in ad-hoc radio networks, focusing on the case when the network forms a tree, with edges directed towards the root. Initially, each node has a rumor, and we aim to deliver all rumors to the root as quickly as possible without knowing the tree's topology in advance. In the deterministic case, where nodes are labeled with small integers, we give an O(n)-time protocol for the model with unbounded message size, and an O(nlog⁡n)-time protocol for bounded message size. We also consider fire-and-forward protocols, in which nodes can transmit only their own rumor or the rumor received in the previous step. We give a deterministic fire-and-forward protocol with running time O(n1.5), and show that it is asymptotically optimal. We also present a randomized O(nlog⁡n)-time protocol in the model without node labels or aggregation, and show that it is asymptotically optimal.