AuthorsF. Cicalese, F. Manne and Q. Xin
TitleFaster Deterministic Communication in Radio Networks
AfilliationNetworks, Communication Systems
StatusPublished
Publication TypeJournal Article
Year of Publication2009
JournalAlgorithmica
Volume54
Issue2
Number2
Pagination226-242
Date PublishedJune
PublisherSpringer
Abstract

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in O(D+\fracΔłog n}łogΔ-łogłog n}}) time units in any radio network of size n, diameter D, and maximum degree Δ = Ømega(łog n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than Ømega(D+\fracΔłog n}łogΔ}) units of time. Moreover, we show a D+O(\fracłog^3 n}łogłog n}}) schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules in Gąsieniec, Peleg, and Xin [PODC'05], i.e., a O(D+Δłog n) time schedule for gossiping and a D+O(łog^3 n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+łog^2 n) time broadcasting schedule by Kowalski and Pelc.

DOI10.1007/s00453-007-9136-0
Citation KeySimula.ND.77