TY - JOUR

T1 - Information gathering in ad-hoc radio networks with tree topology

AU - Chrobak, Marek

AU - Costello, Kevin

AU - Gasieniec, Leszek

AU - Kowalski, Darek R.

N1 - Funding Information:
Research supported by grants CCF-1217314 (NSF) and H98230-13-1-0228 (NSA).
Publisher Copyright:
© Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - 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(n1.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.

AB - 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(n1.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.

UR - http://www.scopus.com/inward/record.url?scp=84921489746&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84921489746&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-12691-3_11

DO - 10.1007/978-3-319-12691-3_11

M3 - Article

AN - SCOPUS:84921489746

SN - 0302-9743

VL - 8881

SP - 129

EP - 145

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -