In wireless networks, consisting of battery-powered devices, energy is a costly resource and most of it is spent on transmitting and receiving messages. Broadcast is a problem where a message needs to be transmitted from one node to all other nodes of the network. We study algorithms that can work under limited energy measured as the maximum number of transmissions by a single station. The goal of the paper is to study tradeoffs between time and energy complexity of broadcast problem in multi-hop radio networks. We consider a model where the topology of the network is unknown and if two neighbors of a station are transmitting in the same discrete time slot, then the signals collide and the receiver cannot distinguish the collided signals from silence. We observe that existing, time efficient, algorithms are not optimized with respect to energy expenditure. We then propose and analyse two new randomized energy-efficient algorithms. Our first algorithm works in time @math with high probability and uses @math energy per station for any @math for any graph with @math nodes and diameter @math . Our second algorithm works in time @math with high probability and uses @math energy. We prove that our algorithms are almost time-optimal for given energy limits for graphs with constant diameters by constructing lower bound on time of @math . The lower bound shows also that any algorithm working in polylogaritmic time in @math for all graphs needs energy @math .
The first randomized broadcast protocol (without considering energy-efficiency aspects) presented by Bar-Yehuda al @cite_7 for the model without collision detection works in any multi-hop network in time @math with high probability. It is based on procedure from @cite_9 extensively used also in many other papers. Improved protocols with expected time @math have been independently proposed by Czumaj and Rytter @cite_21 and Kowalski and Pelc @cite_13 . Those results are optimal due to the lower bounds @math shown by Alon al @cite_26 and @math by Kushilevitz and Mansour @cite_5 . Recently Haeupler and Wajc @cite_2 proved that if stations are allowed to make transmissions before receiving the message then broadcast can be completed in time @math which was improved by to @math Czumaj and Davies @cite_0 .
@cite_26 @cite_7 @cite_9 @cite_21 @cite_0 @cite_2 @cite_5 @cite_13
1981696935 2160268831 2951342393 2048113794
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. In this paper we present new randomized and deterministic algorithms for the classical problem of broadcasting in radio networks with unknown topology. We consider directed n-node radio networks with specified eccentricity D (maximum distance from the source node to any other node). Bar- presented an algorithm that for any n-node radio network with eccentricity D completes the broadcasting in O(D log n + log2 n) time, with high probability. This result is almost optimal, since as it has been shown by Kushilevitz and Mansour and , every randomized algorithm requires Ω (D log(n D) + log2 n) expected time to complete broadcasting.Our first main result closes the gap between the lower and upper bound: we describe an optimal randomized broadcasting algorithm whose running time complexity is O(D log (n D + log2 n), with high probability. In particular, we obtain a randomized algorithm that completes broadcasting in any n-node radio network in time O(n), with high probability.The main source of our improvement is a better "selecting sequence" used by the algorithm that brings some stronger property and improves the broadcasting time. Two types of "selecting sequences" are considered: randomized and deterministic ones. The algorithm with a randomized sequence is easier (more intuitive) to analyze but both randomized and deterministic sequences give algorithms of the same asymptotic complexity. We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in undirected networks with n nodes and diameter D, randomized broadcasting requires Omega(D log n D + log^2 n) rounds in expectation, assuming that uninformed nodes are not allowed to communicate (until they are informed). Only very recently, Haeupler and Wajc (PODC'2016) showed that this bound can be slightly improved for the model with spontaneous transmissions, providing an O(D log n loglog n log D + log^O(1) n)-time broadcasting algorithm. In this paper, we give a new and faster algorithm that completes broadcasting in O(D log n log D + log^O(1) n) time, with high probability. This yields the first optimal O(D)-time broadcasting algorithm whenever D is polynomial in n. Furthermore, our approach can be applied to design a new leader election algorithm that matches the performance of our broadcasting algorithm. Previously, all fast randomized leader election algorithms have been using broadcasting as their subroutine and their complexity have been asymptotically strictly bigger than the complexity of broadcasting. In particular, the fastest previously known randomized leader election algorithm of Ghaffari and Haeupler (SODA'2013) requires O(D log n D min loglog n, log n D + log^O(1) n)-time with high probability. Our new algorithm requires O(D log n log D + log^O(1) n) time with high probability, and it achieves the optimal O(D) time whenever D is polynomial in n. We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in O(D + log6 n) rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter D. It improves over the currently best known O(Dlogn D + log2 n) algorithms, due to Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection. We also study distributed algorithms for broadcasting k messages from a single source to all nodes. This problem is a natural and important generalization of the single-message broadcast problem, but is in fact considerably more challenging and less understood. We show the following results: If the network topology is known to all nodes, then a k-message broadcast can be performed in O(D + klog n + log2 n) rounds, with high probability. If the topology is not known, but collision detection is available, then a k-message broadcast can be performed in O(D + klog n + log6 n) rounds, with high probability. The first bound is optimal and the second is optimal modulo the additive O(log6 n) term.