In this paper, we address the problem of broadcasting in a wireless network under a novel communication model: the swamping communication model. In this model, nodes communicate only with those nodes at geometric distance greater than @math and at most @math from them. Communication between nearby nodes under this model can be very time consuming, as the length of the path between two nodes within distance @math is only bounded above by the diameter @math , in many cases. For the @math -node lattice networks, we present algorithms of optimal time complexity, respectively @math for the lattice line and @math for the two-dimensional lattice. We also consider networks of unknown topology of diameter @math and of a parameter @math ( granularity ). More specifically, we consider networks with @math the minimum distance between any two nodes and @math . We present broadcast algorithms for networks of nodes placed on the line and on the plane with respective time complexities @math and @math , where @math .
The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane. In any given time step, a station can either receive or transmit. A message transmitted from station (v) is delivered to every station (u) at distance at most (1) from (v), but (u) successfully hears the message if and only if (v) is the only station at distance at most (1) from (u) that 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 on 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 (D g)) and prove that every broadcasting algorithm requires Ω (D √g) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [11], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a (d)-spaced grid. Does the latter (more restricted) setting provides any speedup in broadcasting time complexity? Although the (O (D g)) broadcasting algorithm of [11] works under the (original) arbitrary deployment setting, it turns out that the Ω (D √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 on the time complexity of broadcasting under the arbitrary deployment setting proving that broadcasting cannot be completed in less than Ω ( D √g) time. For the grid deployment setting, we develop a broadcasting algorithm that runs in time O ( D g5 6 log g), thus breaking the linear dependency on (g).