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 .
In @cite_7 , the problem of broadcasting in unknown topology networks was proposed given that nodes do not perceive their location accurately and that they do not know the minimum distance @math between them. Under the spontaneous wake up model, the authors showed a broadcasting algorithm maintaining optimal time complexity @math in these conditions given an upper bound @math on the inaccuracy of node location perception; beyond this upper bound on inaccuracy, the authors showed that broadcasting is impossible. The solution proposed in @cite_7 uses the election of ambassadors that represent a large number of nodes and communicate information to regions of the graph in range. In contrast, we show the impossibility of using this mechanism in the presence of swamping.
@cite_7
1736159137
We study broadcasting time in radio networks, modeled as unit disk graphs (UDG). showed that broadcasting time depends on two parameters of the UDG network, namely, its diameter D(in hops) and its granularityg. The latter is the inverse of the densitydof the network which is the minimum Euclidean distance between any two stations. They proved that the minimum broadcasting time is @math , assuming that each node knows the density of the network and knows exactly its own position in the plane. In many situations these assumptions are unrealistic. Does removing them influence broadcasting time? The aim of this paper is to answer this question, hence we assume that density is unknown and nodes perceive their position with some unknown error margin i¾?. It turns out that this combination of missing and inaccurate information substantially changes the problem: the main new challenge becomes fast broadcasting in sparse networks (with constant density), when optimal time is O(D). Nevertheless, under our very weak scenario, we construct a broadcasting algorithm that maintains optimal time @math for all networks with at least 2 nodes, of diameter Dand granularity g, if each node perceives its position with error margin i¾?= i¾?d, for any (unknown) constant i¾?< 1 2. Rather surprisingly, the minimum time of an algorithm stopping if the source is alone, turns out to be i¾?(D+ g2). Thus, the mere stopping requirement for the special case of the lonely source causes an exponential increase in broadcasting time, for networks of any density and any small diameter. Finally, broadcasting is impossible if i¾?i¾? d 2.