On the Effect of the Deployment Setting on Broadcasting in Euclidean Radio Networks

The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane. In any given time step, a station call either receive or transmit. A message transmitted from station nu is delivered to every station it at distance at, most 1 from v, but u successfully hears the message if and only if nu, is the only station at distance at most 1 from u that t, transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [11] that the time complexity of broadcasting depends oil two parameters of the network, namely, its diameter (in hops) D and a lower bound d on the Euclidean distance between any two stations. The inverse of d is called the granularity of the network, denoted by g. Specifically, the authors of [11] present a broadcasting algorithm that works in time O(Dg) and prove that, every broadcasting algorithm requires Q (D root g) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [11], in which stations call be placed everywhere, in the plane, and the new grid deployment setting, in which stations are only allowed to be placed oil a d-spaced grid. Does the latter (more restricted) setting provides any speedup in broadcasting time complexity? Although the O(Dg) broadcasting algorithm of [11] works under the (original) arbitrary deployment setting, it turns out that the Q (D root g) lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We, establish a tight lower bound ()it the time complexity, of broadcasting under the arbitrary deployment setting proving that broadcasting cannot be completed in less than Omega(Dg) time. For the grid deployment setting, we develop a broadcasting algorithm that runs in time O(Dg(5/6) log g) thus breaking the linear dependency on g.