Broadcasting in UDG radio networks with unknown topology

• Published in: Distributed computing 2009-02, Vol.21 (5), p.331-351
• Main Authors: Emek, Yuval, Ga̧sieniec, Leszek, Kantor, Erez, Pelc, Andrzej, Peleg, David, Su, Chang
• Format: Article
• Language: English
• Subjects: Computer Communication Networks; Computer Hardware; Computer Science; Computer Systems Organization and Communication Networks; Software Engineering/Programming and Operating Systems; Theory of Computation
• ISSN: 0178-2770; 1432-0452
• DOI: 10.1007/s00446-008-0075-z

The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at 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 broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g , which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O ( D g ) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than . For the spontaneous wake up model, we design two deterministic broadcasting algorithms: the first works in time O ( D + g 2 ) and the second in time O ( D log g ). While neither of these algorithms alone is optimal for all parameter values, we prove that the algorithm obtained by interleaving their steps, and thus working in time , turns out to be optimal by establishing a matching lower bound.