Abstract
The deterministic broadcasting time in radio networks, whose node know only their immediate nodes, is discussed. The broadcasting in radio networks was modeled as undirected graphs. In each of the step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message in which can reach all of its neighbor. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbor transmits in this step. The results shows that lower bound proves an exponential gap between time of deterministic and randomized broadcastings in radio networks.
Original language | English (US) |
---|---|
Pages (from-to) | 870-891 |
Number of pages | 22 |
Journal | SIAM Journal on Computing |
Volume | 33 |
Issue number | 4 |
DOIs | |
State | Published - May 2004 |
Externally published | Yes |
Keywords
- Broadcasting
- Deterministic
- Distributed
- Radio network
ASJC Scopus subject areas
- Computer Science(all)
- Mathematics(all)