• Calendar

March 13, Tuesday
12:00 – 14:00

We consider broadcasting in radio networks, modeled as unit disk graphs (UDG). Network stations are modeled as points in the plane, where a station is connected to all stations at Euclidean distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning.

It turns out that the running time of deterministic broadcasting algorithms depends on two parameters of the UDG network, namely, its diameter $D$ and its granularity $g$, which is the inverse of the minimum Euclidean distance between any two stations. We present a deterministic broadcasting algorithm which works in time $O(D g)$ under the conditional wake up model. On the negative side, we prove that any deterministic algorithm requires $\Omega(D \sqrt{g})$ time to accomplish broadcasting. For the spontaneous wake up model, we establish a lower bound of $\Omega(\min\{D + g^2, D \log{g}\})$ on deterministic broadcasting time and prove that this is tight. Thus our results yield a provable separation between the two models: for some parameter values, the lower bound in the first model is significantly larger than the upper bound in the second.