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 .
More recently, in @cite_2 , it was shown that the time of broadcast depends on the network diameter @math and the smallest geometric distance @math (denoted @math in their paper) between any two nodes. Under the conditional wake-up model network!conditional wake up model , where nodes start transmitting only after hearing a first message, the authors proposed an algorithm that completes broadcasting in time @math . They also proved that, in this context, every broadcasting algorithm requires @math time. Under the spontaneous wake up model network!spontaneous wake up model , where nodes may transmit from the beginning of the communication process, the authors combined two sub-optimal algorithms into one algorithm, which completes broadcasting in optimal time @math . The results in @cite_2 hold under the assumption that nodes can communicate with other neraby nodes. We, on the other hand, consider the communication model where nodes are prevented from communicating with other nodes nearby.
@cite_2
2088895311
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 ( (D g ) ) . 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 ( O ( D + g^2, D g ) ), turns out to be optimal by establishing a matching lower bound.