This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in radio networks with known topology, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. The first part of the paper examines the two communication primitives in general graphs. In particular, it proposes a new (efficiently computable) deterministic schedule that uses O(D + ∆ log n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree ∆. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time
If the topology of the network is known, then the algorithm of Gasieniec et al. REF achieves the optimal O(D +log 2 n) time complexity.
Faster communication in known topology radio networks
PODC '05
Computer Science