Information gathering in ad-hoc radio networks with tree topology

Chrobak, Marek, Costello, Kevin P, Gasieniec, Leszek ORCID: 0000-0003-1809-9814 and Kowalski, Dariusz R ORCID: 0000-0002-1316-7788 (2018) Information gathering in ad-hoc radio networks with tree topology. Information and Computation, 258. pp. 1-27.

Text gather_trees_ic_final_version.pdf - Author Accepted Manuscript Download (715kB)

Abstract

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 -time protocol for the model with unbounded message size, and an -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 , and show that it is asymptotically optimal. We also present a randomized -time protocol in the model without node labels or aggregation, and show that it is asymptotically optimal.

Item Type:	Article
Uncontrolled Keywords:	Radio networks, Communication protocols, Broadcasting, Gossiping
Depositing User:	Symplectic Admin
Date Deposited:	08 Jan 2018 07:42
Last Modified:	19 Jan 2023 06:46
DOI:	10.1016/j.ic.2017.11.003
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3015495