Radio networks are a long-studied model for distributed system of devices which communicate wirelessly. When these devices are mobile or have limited capabilities, the system is often best modeled by the ad-hoc variant, in which the devices do not know the structure of the network. A large body of work has been devoted to designing algorithms for the ad-hoc model, particularly for fundamental communications tasks such as broadcasting. Most of these algorithms, however, assume that devices have some network knowledge (usually bounds on the number of nodes in the network @math , and the diameter @math ), which may not always be realistic in systems with weak devices or gradual deployment. Very little is known about what can be done when this information is not available. This is the issue we address in this work, by presenting the first broadcasting algorithms for networks in which nodes have no prior knowledge whatsoever. We demonstrate that lack of parameter knowledge can be overcome at only a small increase in running time. Specifically, we show that in networks without collision detection, broadcast can be achieved in @math time, almost reaching the @math lower bound. We also give an algorithm for directed networks with collision detection, which requires only @math time.
A deterministic algorithm for broadcasting in radio networks without parameter knowledge is given in @cite_1 , with a running time of @math , where @math is the range of unique IDs with which nodes are equipped.
@cite_1
1983915440 2153529758 1981696935 1973843421
We consider the problem of broadcasting in an unknown radio network modeled as a directed graph @math , where @math . In unknown networks, every node knows only its own label, while it is unaware of any other parameter of the network, including its neighborhood and even any upper bound on the number of nodes. We show an @math upper bound on the time complexity of deterministic broadcasting. This is an improvement over the currently best upper bound @math for arbitrary networks, thus shrinking exponentially the existing gap between the lower bound @math and the upper bound from @math to @math . In a seminal paper, Bar- (1992) considered broadcasting in radio networks whose nodes know only their own label and labels of their neighbors. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks, by constructing a class of graphs of diameter 3, with the property that every broadcasting algorithm requires linear time on one of these graphs. Due to a subtle error in the argument, this result is incorrect. We construct an algorithm that broadcasts in logarithmic time on all graphs from the work of Bar- Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter o(log log n). On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time spl Omega (4 spl radic n) on one of these graphs. In view of the randomized algorithm, running in expected time O(D log n + log sup 2 n) on all n-node graphs of diameter D, our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting. We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message which can potentially reach all of its neighbors. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbors transmits in this step. Bar-Yehuda, Goldreich, and Itai [J. Comput. System Sci., 45 (1992), pp. 104--126] considered broadcasting in this model. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks of diameter 3. This claim turns out to be incorrect in this model (although it is valid in a more pessimistic model [R. Bar-Yehuda, O. Goldreich, and A. Itai, Errata Regarding "On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization," http: www.wisdom.weizmann.ac.il mathusers oded p .html, 2002]). We construct an algorithm that broadcasts in logarithmic time on all graphs from the Bar-Yehuda, Goldreich, and Itai paper (BGI). Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter @math . On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time @math on these graphs. In view of the randomized algorithm from BGI, running in expected time @math on all @math -node graphs of diameter D (cf. also a recent @math -time algorithm from [D. Kowalski and A. Pelc, Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, Boston, 2003, pp. 73--82; A. Czumaj and W. Rytter, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, 2003, pp. 492--501]), our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting, under the considered model of radio communication. We consider the time of broadcasting in ad hoc radio networks modeled as undirected graphs. In such networks, every node knows only its own label and a linear bound on the number of nodes but is unaware of the topology of the network, or even of its own neighborhood. Our aim is to study to what extent the availability of two important characteristics of a broadcasting algorithm influences optimal broadcasting time. These characteristics are adaptiveness and randomization. Our contribution is establishing upper and lower bounds on optimal broadcasting time for three classes of algorithms: adaptive deterministic, oblivious randomized and oblivious deterministic. In two cases we present tight bounds, and in one case a small gap remains. We show that for deterministic adaptive algorithms time Ω(n) is required even for n-node networks of constant diameter. This lower bound is strongest possible, since linear time algorithms are known, and hence establishes optimal time Θ(n) for this class. For oblivious randomized algorithms we show an upper bound O(n min D, log n ) and a lower bound Ω(n) on optimal expected broadcasting time in n-node networks of diameter D. Finally, for oblivious deterministic algorithms we show matching upper and lower bounds Θ(n min D, √n ) on optimal broadcasting time. Our results imply that enforcing obliviousness has at least as strong negative impact on broadcasting time as enforcing determinism, and that algorithms having both these features are strictly less efficient than those having only one of them.