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.
More recently, Ghaffari, Haupler and Khabbazian @cite_2 showed that collision detection can be used to surpass this lower bound, attaining an @math time algorithm. Work by Haeupler and Wajc @cite_14 demonstrated that even without collision detection, the lower bound could be beaten assuming were permitted; that is, nodes have access to a global clock and are allowed to transmit before receiving the source message. Czumaj and Davies @cite_9 extended this approach and obtained a running time of @math for the setting with spontaneous transmissions. However, these algorithms only work in undirected networks.
@cite_9 @cite_14 @cite_2
2951342393 2048113794
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 study the problem of waking up a collection of @math processors connected by a multihop ad hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. Each node in the network either wakes up spontaneously or gets activated by receiving a wake-up signal from another node. All active nodes transmit the wake-up signals according to a given protocol @math . The running time of @math is the number of steps counted from the first spontaneous wake-up until all nodes become activated. We provide two protocols for this problem. The first one is a deterministic protocol with running time @math . Our protocol is based on a novel concept of a shift-tolerant selector to which we refer as a (radio) synchronizer. The second protocol is randomized, and its expected running time is @math , where @math is the diameter of the network. Subsequently we show how to employ our wake-up protocols to solve two other communication primitives: leader election and clock synchronization. Abstract We address the fundamental distributed problem of leader election in ad hoc radio networks modeled as undirected graphs. A signal from a transmitting node reaches all neighbors but a message is received successfully by a node, if and only if exactly one of its neighbors transmits in this round. If two neighbors of a node transmit simultaneously in a given round, we say that a collision occurred at this node. Collision detection is the ability of nodes to distinguish a collision from silence. We show that collision detection speeds up leader election in arbitrary radio networks. Our main result is a deterministic leader election algorithm working in time O ( n ) in all n -node networks, if collision detection is available, while it is known that deterministic leader election requires time Ω ( n log n ) , even for complete networks, if there is no collision detection. We consider the problem of topology recognition in wireless (radio) networks modeled as undirected graphs. Topology recognition is a fundamental task in which every node of the network has to output a map of the underlying graph i.e., an isomorphic copy of it, and situate itself in this map. In wireless networks, nodes communicate in synchronous rounds. In each round a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node @math hears a message from a neighbor @math in a given round, if @math listens in this round, and if @math is its only neighbor that transmits in this round. Nodes have labels which are (not necessarily different) binary strings. The length of a labeling scheme is the largest length of a label. We concentrate on wireless networks modeled by trees, and we investigate two problems. What is the shortest labeling scheme that permits topology recognition in all wireless tree networks of diameter @math and maximum degree @math ? What is the fastest topology recognition algorithm working for all wireless tree networks of diameter @math and maximum degree @math , using such a short labeling scheme? We are interested in deterministic topology recognition algorithms. For the first problem, we show that the minimum length of a labeling scheme allowing topology recognition in all trees of maximum degree @math is @math . For such short schemes, used by an algorithm working for the class of trees of diameter @math and maximum degree @math , we show almost matching bounds on the time of topology recognition: an upper bound @math , and a lower bound @math , for any constant @math . 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 problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in ( O ( ^3 n) ) time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in ( O ( ^3 n) ) time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in ( O ( ^2 n) ) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in ( O ( ^2 n) ) time. In the distributed all-pairs shortest paths problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity ). The problem admits @math -approximation @math -time algorithm and a nearly-tight @math lower bound [Nanongkai, STOC'14; Lenzen and Patt-Shamir PODC'15] @math , @math and @math hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios LenzenP_podc13,HolzerW12,PelegRT12,Nanongkai-STOC14 . . For the exact case, Elkin [STOC'17] presented an @math time bound, which was later improved to @math [Huang, Nanongkai, Saranurak FOCS'17]. It was shown that any super-linear lower bound (in @math ) requires a new technique [Censor-Hillel, Khoury, Paz, DISC'17], but otherwise it remained widely open whether there exists a @math -time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) @math -time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous @math bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous @math bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in 1, 2, ... poly(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. 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. Practitioners agree that unreliable links, which sometimes deliver messages and sometime do not, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set of links and assume that these links are reliable. This gap between theory and practice motivates us to investigate how unreliable links affect theoretical bounds on broadcast in radio networks. To that end we consider a model that includes two types of links: reliable links, which always deliver messages, and unreliable links, which sometimes fail to deliver messages. We assume that the reliable links induce a connected graph, and that unreliable links are controlled by a worst-case adversary. In the new model we show an Ω(n log n) lower bound on deterministic broadcast in undirected graphs, even when all processes are initially awake and have collision detection, and an Ω(n) lower bound on randomized broadcast in undirected networks of constant diameter. This separates the new model from the classical, reliable model. On the positive side, we give two algorithms that tolerate unreliability: an O(n3 2 √log n)-time deterministic algorithm and a randomized algorithm which terminates in O(n log2 n) rounds with high probability. Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy usage, we define energy complexity to be the number of time slots a device transmits listens; idle time and computation are free. In this paper we investigate the energy complexity of fundamental communication primitives such as broadcast in multi-hop radio networks. We consider models with collision detection (CD) and without (No-CD), as well as both randomized and deterministic algorithms. Some take-away messages from this work include: 1. The energy complexity of broadcast in a multi-hop network is intimately connected to the time complexity of leader election in a single-hop (clique) network. Many existing lower bounds on time complexity immediately transfer to energy complexity. For example, in the CD and No-CD models, we need @math and @math energy, respectively. 2. The energy lower bounds above can almost be achieved, given sufficient ( @math ) time. In the CD and No-CD models we can solve broadcast using @math energy and @math energy, respectively. 3. The complexity measures of Energy and Time are in conflict, and it is an open problem whether both can be minimized simultaneously. We give a tradeoff showing it is possible to be nearly optimal in both measures simultaneously. For any constant @math , broadcast can be solved in @math time with @math energy, where @math is the diameter of the network. We present the communication model, which assumes nodes have minimal knowledge about their environment and severely limited communication capabilities. Specifically, nodes have no information regarding the local or global structure of the network, don't have access to synchronized clocks and are woken up by an adversary. Moreover, instead on communicating through messages they rely solely on carrier sensing to exchange information. We study the problem of , a variant of vertex coloring specially suited for the studied beeping model. Given a set of resources, the goal of interval coloring is to assign every node a large contiguous fraction of the resources, such that neighboring nodes share no resources. To highlight the importance of the discreteness of the model, we contrast it against a continuous variant described in [17]. We present an O(1 @math (T ) @math T @math O( n) @math (T ) @math O( n) @math ( n)$ on the time required to solve interval coloring for this model against randomized algorithms. This lower bound implies that our algorithm is asymptotically optimal for constant degree graphs. The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning. It turns out that broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g, which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O (D g) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than ( (D g ) ) . For the spontaneous wake up model, we design two deterministic broadcasting algorithms: the first works in time O (D + g 2) and the second in time O (D log g). While neither of these algorithms alone is optimal for all parameter values, we prove that the algorithm obtained by interleaving their steps, and thus working in time ( O ( D + g^2, D g ) ), turns out to be optimal by establishing a matching lower bound. This paper considers the issue of broadcasting protocols in multihop radio networks. The objective of a broadcasting protocol is to deliver the broadcasted message to all network nodes. To efficiently achieve this objective the broad- casting protocol in this paper utilizes two basic properties of the multihop radio network. One is the broadcast nature of the radio which allows every single trasmission to reach all nodes that are in line of sight and within range of the transmitting node. The other, spatial reuse of the radio channel, which due to the multihop nature of the network allows multiple simultaneous transmissions to be received correctly. The proposed protocol incorporates these properties to obtain a collision free forwarding of the broadcasted message on a tree. Centralized and distributed algorithms for the tree construction are presented. The obtained trees are unique in incorporating radio oriented time ordering as part of their definition. In this way multiple copies of one or more broadcasted messages can be transmitted simultaneously without collision, requiring only a small number of message transmissions. Consequently, the protocol not only guarantees that the broadcasted message reaches all network nodes in bounded time, but also ensures that the broadcasting activity will use only limited channel bandwidth and node memory. The proposed broadcast protocol thus possesses the advantages of TDM solutions while allowing the channel bandwidth to be shared, concurrently with the broadcast, with other transmission activities as dictated, for instance, by data link protocols. Some NP-completeness proofs are also given. Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical Coupon Collector's Problem . Consequently, we show that each node discovers all its @math neighbors in an expected time equal to @math , for some constant @math . When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a @math improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing @math results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase. This paper proposes and analyzes a distributed MAC protocol that achieves zero collision with no control message exchange nor synchronization. ZC (ZeroCollision) is neither reservation-based nor dynamic TDMA; the protocol supports variable-length packets and does not lose efficiency when some of the stations do not transmit. At the same time, ZC is not a CSMA; in its steady state, it is completely collision-free. The stations transmit repeatedly in a round-robin order once the convergence state is reached. If some stations skip their turn, their transmissions are replaced by idle @math -second mini-slots that enable the other stations to keep track of their order. Because of its short medium access delay and its efficiency, the protocol supports both real-time and elastic applications. The protocol allows for nodes leaving and joining the network; it can allocate more throughput to specific nodes (such as an access point). The protocol is robust against carrier sensing errors or clock drift. While collision avoidance is guaranteed in a single collision domain, it is not the case in a multiple collision one. However, experiments show ZC supports a comparable amount of goodput to CSMA in a multiple collision domain environment. The paper presents an analysis and extensive simulations of the protocol, confirming that ZC outperforms both CSMA and TDMA at high and low load. Wireless ad hoc radio networks have gained a lot of attention in recent years. We consider geometric networks, where nodes are located in a Euclidean plane. We assume that each node has a variable transmission range and can learn the distance to the closest active neighbor at any time. We also assume that nodes have a special collision detection (CD) capability so that a transmitting node can detect a collision within its transmission range. We study the basic communication problem of collecting data from all nodes called convergecast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent delay requirements on the convergecast time. We measure the latency of convergecast, that is the number of time steps needed to collect the data in any n-node network. We propose a very simple randomized distributed algorithm that has the expected running time O(logn). We also show that this bound is tight and any algorithm needs @W(logn) time steps while performing convergecast in an arbitrary network. One of the most important problems in wireless ad hoc networks is to minimize the energy consumption, which maximizes the network lifetime. We study the trade-off between the energy and the latency of convergecast. We show that our algorithm consumes at most O(nlogn) times the minimum energy. We also demonstrate that for a line topology, the minimum energy convergecast takes n time steps while any algorithm performing convergecast within O(logn) time steps requires @W(n logn) times the minimum energy. The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane. In any given time step, a station can either receive or transmit. A message transmitted from station (v) is delivered to every station (u) at distance at most (1) from (v), but (u) successfully hears the message if and only if (v) is the only station at distance at most (1) from (u) that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [11] that the time complexity of broadcasting depends on two parameters of the network, namely, its diameter (in hops) (D) and a lower bound (d) on the Euclidean distance between any two stations. The inverse of (d) is called the granularity of the network, denoted by (g). Specifically, the authors of [11] present a broadcasting algorithm that works in time (O (D g)) and prove that every broadcasting algorithm requires Ω (D √g) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [11], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a (d)-spaced grid. Does the latter (more restricted) setting provides any speedup in broadcasting time complexity? Although the (O (D g)) broadcasting algorithm of [11] works under the (original) arbitrary deployment setting, it turns out that the Ω (D √g) lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We establish a tight lower bound on the time complexity of broadcasting under the arbitrary deployment setting proving that broadcasting cannot be completed in less than Ω ( D √g) time. For the grid deployment setting, we develop a broadcasting algorithm that runs in time O ( D g5 6 log g), thus breaking the linear dependency on (g). This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple-access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually when the processor wakes up. We consider the fundamental problem of waking up all n processors of a completely connected broadcast system. Some processors wake up spontaneously, while others have to be woken up. Only awake processors can send messages; a sleeping processor is woken up upon hearing a message. The processors hear a message in a given round if and only if exactly one processor sends a message in that round. Our goal is to wake up all processors as fast as possible in the worst case, assuming an adversary controls which processors wake up and when. We analyze the problem in both the globally synchronous and locally synchronous models with or without the assumption that n is known to the processors. We propose randomized and deterministic algorithms for the problem, as well as lower bounds in some of the cases. These bounds establish a gap between the globally synchronous and locally synchronous models. Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node sends a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc networks. Our objective is to minimize the latency and the number of transmissions in the broadcast. We show that minimum latency broadcasting is NP-complete for ad hoc networks. We also present a simple distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of transmissions are within O(1) times their re spective optimal values. Our algorithm and analysis extend to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithms perform much better in practice than the analytical guarantees provided for the worst case.