Skip to main content
Open Access Publications from the University of California

UC Riverside

UC Riverside Electronic Theses and Dissertations bannerUC Riverside

Information Gathering Problem in Ad-Hoc Radio Networks With Layer Topology


In this thesis we analyze the gathering problem on acyclic graphs in the adhoc radio network framework where the topology of the underlying digraph is unknown. In this problem, each node holds a single message, and the goal is for all nodes to transmit their message to a specified root node. Our main result is a near-optimal lower bound of Ω(n^2/ log n) on the time cost for gathering in acyclic graphs without message aggregation. The key idea is to reduce this problem to a "gathering between layers" problem, isolating the difficulties caused as multiple copies of a message spread through the network.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View