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
2142458954 2018861711 2160268831 2951342393 2501645718 2095713941 2048565150
The time-complexity of deterministic and randomized protocols for achieving broadcast (distributing a message from a source to all other nodes) in arbitrary multi-hop radio networks is investigated. In many such networks, communication takes place in synchronous time-slots. A processor receives a message at a certain time-slot if exactly one of its neighbors transmits at that time-slot. We assume no collision-detection mechanism; i.e., it is not always possible to distinguish the case where no neighbor transmits from the case where several neighbors transmit simultaneously. We present a randomized protocol that achieves broadcast in time which is optimal up to a logarithmic factor. In particular, with probability 1 --E, the protocol achieves broadcast within O((D + log n s) ‘log n) time-slots, where n is the number of processors in the network and D its diameter. On the other hand, we prove a linear lower bound on the deterministic time-complexity of broadcast in this model. Namely, we show that any deterministic broadcast protocol requires 8(n) time-slots, even if the network has diameter 3, and n is known to all processors. These two results demonstrate an exponential gap in complexity between randomization and determinism. This paper presents an efficient randomized emulation of single-hop radio network with collision detection on multi-hop radio network without collision detection. Each step of the single-hop network is emulated by O((D + log n e) log Δ) rounds of multi-hop network and succeeds with probability ≥ 1 - e. (n is the number of processors, D the diameter and Δ the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains ≥ e. A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network. 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 faster distributed broadcasting primitive for the classical radio network model. The most basic distributed radio network broadcasting primitive - called Decay - dates back to a PODC'87 result of Bar-Yehuda, Goldreich, and Itai. In any radio network with some informed source nodes, running Decay for O(d log n + log2 n) rounds informs all nodes at most d hops away from a source with high probability. Since 1987 this primitive has been the most important building block for implementing many other functionalities in radio networks. The only improvements to this decades-old algorithm are slight variations due to [Czumaj, Rytter; FOCS'03] and [Kowalski and Pelc, PODC'03] which achieve the same functionality in O(d log n d + log2 n) rounds. To obtain a speedup from this, d and thus also the network diameter need to be near linear, i.e., larger than n1--e. Our new distributed primitive spreads messages for d hops in O(d log n log log log d + logO(1) n) rounds with high probability. This improves over Decay for any super-polylogarithmic d = logω(1) n and achieves near-optimal O(d log log n) running time for d = ne. This also makes progress on an open question of Peleg. A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors, where a processor receives a message in a given step if and only if it is silent in this step and precisely one of its neighbors transmits. In this paper we prove the existence of a family of radius-2 networks on n vertices for which any broadcast schedule requires at least Omega((log n log log n)2) rounds of transmissions. This almost matches an upper bound of O(log2 n) rounds for networks of radius 2 proved earlier by Bar-Yehuda, Goldreich, and Itai. We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in expected time O(D log(n D) + log2 n) in n-node radio networks of diameter D, which is optimal, as it matches the lower bounds of [1] and Kushilevitz and Mansour [14]. Our algorithm improves the best previously known randomized broadcasting algorithm of Bar-Yehuda, Goldreich and Itai [3], running in expected time O(D log n + log2 n). For deterministic broadcasting, we show the lower bound Ω(n(log n) (log (n D)))) on broadcasting time in n-node radio networks of diameter D. This implies previously known lower bounds of Bar-Yehuda, Goldreich and Itai [3] and Bruschi and Del Pinto [5], and is sharper than any of them in many cases. We also give an algorithm working in time O(n log n), thus shrinking -- for the first time -- the gap between the upper and the lower bound on deterministic broadcasting time to a logarithmic factor.