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 question of communication in networks of unknown topology has been widely studied in recent years. In @cite_17 , the authors state that broadcasting algorithms which function in unknown GRNs also function in the resulting fault-free connected components of faulty GRNs. A basic performance criterion of broadcasting algorithms is the time necessary for the algorithm to terminate; in synchronous networks, this time is measured as the number of communication rounds. For networks whose fault-free part has a diameter @math , @math is a trivial lower bound on broadcast time, but optimal running time is a function of the information available to the algorithms (cf., e.g., @cite_5 ). For instance, in @cite_5 , an algorithm was obtained which accomplishes broadcast in arbitrary GRNs in time @math under the assumption that nodes have a large amount of knowledge about the network, i.e. given that all nodes have a knowledge radius larger than @math , the largest communication radius. The authors also show that algorithms broadcasting in time @math are asymptotically optimal, for unknown GRNs when nodes communicate spontaneously and either can detect collisions or have knowledge of node locations at some positive distance @math , arbitrarily small.
@cite_5 @cite_17
2061572891 2042997796
We consider deterministic broadcasting in geometric radio networks (GRN) whose nodes know only a limited part of the network. Nodes of a GRN are situated in the plane and each of them is equipped with a transmitter of some range r. A signal from this node can reach all nodes at distance at most r from it but if a node u is situated within the range of two nodes transmitting simultaneously, then a collision occurs at u and u cannot get any message. Each node knows the part of the network within knowledge radius s from it, i.e., it knows the positions, labels and ranges of all nodes at distance at most s. The aim of this paper is to study the impact of knowledge radius s on the time of deterministic broadcasting in a GRN with n nodes and eccentricity D of the source. Our results show sharp contrasts between the efficiency of broadcasting in geometric radio networks as compared to broadcasting in arbitrary graphs. They also show quantitatively the impact of various types of knowledge available to nodes on broadcasting time in GRN. Efficiency of broadcasting is influenced by knowledge radius, knowledge of individual positions when knowledge radius is zero, and awareness of collisions. We study the completion time of broadcast operations on static ad hoc wireless networks in presence of unpredictable and dynamical faults.Concerning oblivious fault-tolerant distributed protocols, we provide an Ω(Dn) lower bound where n is the number of nodes of the network and D is the source eccentricity in the fault-free part of the network. Rather surprisingly, this lower bound implies that the simple Round Robin protocol, working in O(Dn) time, is an optimal fault-tolerant oblivious protocol. Then, we demonstrate that networks of o(n log n) maximum in-degree admit faster oblivious protocols. Indeed, we derive an oblivious protocol having O(D min n, Δ log n ) completion time on any network of maximum in-degree Δ.Finally, we address the question whether adaptive protocols can be faster than oblivious ones. We show that the answer is negative at least in the general setting: we indeed prove an Ω(Dn) lower bound when D = Θ(√n). This clearly implies that no (adaptive) protocol can achieve, in general, o(Dn) completion time.