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.
All of these results also , and algorithms that do not require such knowledge have been little studied. The closest analogue in the literature is the work of Jurdzinski and Stachowiak @cite_11 , who give algorithms for wake-up in single-hop radio networks (those in which the underlying graph is a clique, i.e. @math ) under a wide range of node knowledge assumptions. Their Use-Factorial-Representation algorithm is the most relevant; the running time is given as @math for high-probability wake-up with a global clock (a slightly stronger task than broadcasting) in single-hop networks, but a similar analysis as we present here would demonstrate that the algorithm also performs broadcasting in multi-hop networks in @math time.
@cite_11
1990661532
The unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh characteristics of initially deployed wireless adhoc and sensor networks. In this paper, assuming such a practical model, we study a fundamental problem of both theoretical and practical interests--the local broadcasting problem. Given a set of nodes V where each node wants to broadcast a message to all its neighbors that are within a certain local broadcasting range R, the problem is to schedule all these requests in the fewest timeslots. By adopting the physical interference mode land without any knowledge on neighborhood, we give a new randomized distributed approximation algorithm for the local broadcasting problem with approximation ratio O (log n) where nis the number of nodes. This distributed approximation algorithm improves the state-of-the-art result in [22] by a logarithmic factor. In this paper we improve the deterministic complexity of two fundamental communication primitives in the classical model of ad hoc radio networks with unknown topology: broadcasting and wake-up. We consider an unknown radio network, in which all nodes have no prior knowledge about network topology, and know only the size of the network @math , the maximum in-degree of any node @math , and the eccentricity of the network @math . For such networks, we first give an algorithm for wake-up, based on the existence of small universal synchronizers. This algorithm runs in @math time, the fastest known in both directed and undirected networks, improving over the previous best @math -time result across all ranges of parameters, but particularly when maximum in-degree is small. Next, we introduce a new combinatorial framework of block synchronizers and prove the existence of such objects of low size. Using this framework, we design a new deterministic ... Broadcasting is a basic network communication task, where a message initially held by a source node has to be disseminated to all other nodes in the network. Fast algorithms for broadcasting in radio networks have been studied in a wide variety of different models and under different requirements. Some of the main parameters giving rise to the different variants of the problem are the accessibility of knowledge about the network topology, the availability of collision detection mechanisms, the wake-up mode, the topology classes considered, and the use of randomness. The paper reviews the literature on time-efficient broadcasting algorithms for radio networks under a variety of models and assumptions. 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 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. We present an improved algorithm to wake up a multi-hop ad-hoc radio network. The goal is to have all the nodes activated, when some of them may wake up spontaneously at arbitrary times and the remaining nodes need to be awoken by the already active ones. The best previously known wake-up algorithm was given by Chrobak, Gasieniec and Kowalski [11], and operated in time O(n5 3 log n), where n is the number of nodes. We give an algorithm with the running time O(n3 2 log n). This also yields better algorithms for other synchronization-type primitives, like leader election and local-clocks synchronization, each with a time performance that differs from that of wake-up by an extra factor of O(log n) only, and improves the best previously known method for the problem by a factor of n1 6. A wake-up algorithm is a schedule of transmissions for each node. It can be represented as a collection of binary sequences. Useful properties of such collections have been abstracted to define a (radio) synchronizer. It has been known that good radio synchronizers exist and previous algorithms [17,11] relied on this. We show how to construct such synchronizers in polynomial time, from suitable constructible expanders. As an application, we obtain a wake-up protocol for a multiple-access channel that activates the network in time O(k2 polylog n), where k is the number of stations that wake up spontaneously, and which can be found in time polynomial in n. We extend the notion of synchronizers to universal synchronizers. We show that there exist universal synchronizers with parameters that guarantee time O(n3 2 log n) of wake-up. We present a method for solving the shortest transshipmen problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of @math in undirected graphs with polynomially bounded integer edge weights using a tailored gradient descent algorithm. An important special case of the transshipment problem is the single-source shortest paths (SSSP) problem. Our gradient descent algorithm takes @math iterations, and in each iteration it needs to solve the transshipment problem up to a multiplicative error of @math , where @math is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. As a consequence, we improve prior work by obtaining the following results: (1) Broadcast congest model: @math -approximate SSSP using @math rounds, where @math is the (hop) diameter of the network. (2) Broadcast congested clique model: @math -approximate transshipment and SSSP using @math rounds. (3) Multipass streaming model: @math -approximate transshipment and SSSP using @math space and @math passes. The previously fastest algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in @math ; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs, running times scale with the maximum ratio between the costs of both directions over all edges. Radio networks model wireless communication when processing units communicate using one wave frequency. This is captured by the property that multiple messages arriving simultaneously to a node interfere with one another and none of them can be read reliably. We present improved solutions to the problem of waking up such a network. This requires activating all nodes in a scenario when some nodes start to be active spontaneously, while every sleeping node needs to be awaken by receiving successfully a message from a neighbor. Our contributions concern the existence and efficient construction of universal radio synchronizers, which are combinatorial structures introduced in [6] as building blocks of efficient wake-up algorithms. First we show by counting that there are (n,g)-universal synchronizers for @math . Next we show an explicit construction of (n,g)-universal-synchronizers for @math . By way of applications, we obtain an existential wake-up algorithm which works in time @math and an explicitly instantiated algorithm that works in time @math , where n is the number of nodes and @math is the maximum in-degree in the network. Algorithms for leader-election and synchronization can be developed on top of wake-up ones, as shown in [7], such that they work in time slower by a factor of @math than the underlying wake-up ones. Ad-hoc radio networks and multiple access channels are classical and well-studied models of distributed systems, with a large body of literature on deterministic algorithms for fundamental communications primitives such as broadcasting and wake-up. However, almost all of these algorithms assume knowledge of the number of participating nodes and the range of possible IDs, and often make the further assumption that the latter is linear in the former. These are very strong assumptions for models which were designed to capture networks of weak devices organized in an ad-hoc manner. It was believed that without this knowledge, deterministic algorithms must necessarily be much less efficient. In this paper we address this fundamental question and show that this is not the case. We present deterministic algorithms for blind networks (in which nodes know only their own IDs), which match or nearly match the running times of the fastest algorithms which assume network knowledge (and even surpass the previous fastest algorithms which assume parameter knowledge but not small labels). We consider the problem of waking up n processors in a completely broadcast system. We analyze this problem in both globally and locally synchronous models, with or without n being known to the processors and with or without labeling of the processors. The main question we answer is: how fast we can wake up all the processors with probability 1 - ? in each of these eight models? In [12] a logarithmic waking algorithm for the strongest set of assumptions is described, while for weaker models only linear and quadratic algorithms were obtained. We prove that in the weakest model (local synchronization, no knowledge of n or labeling) the best waking time is O(n log n). We also show logarithmic or polylogarithmic probabilistic waking algorithms for all stronger models, which in some cases gives an exponential improvement over previous results. We consider the problem of waking up n processors of a completely broadcast system. We analyze this problem in both globally and locally synchronous models, with or without n being known to processors and with or without labeling of processors. The main question we answer is: how fast we can wake all the processors up with probability 1 - ? in each of these eight models. In [10] a logarithmic waking algorithm for the strongest set of assumptions is described, while for weaker models only linear and quadratic algorithms were obtained. We prove that in the weakest model (local synchronization, no knowledge of n or labeling) the best waking time is O(n log n). We also show logarithmic or poly-logarithmic waking algorithms for all stronger models, which in some cases gives an exponential improvement over previous results. 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). We study broadcasting time in radio networks, modeled as unit disk graphs (UDG). showed that broadcasting time depends on two parameters of the UDG network, namely, its diameter D(in hops) and its granularityg. The latter is the inverse of the densitydof the network which is the minimum Euclidean distance between any two stations. They proved that the minimum broadcasting time is @math , assuming that each node knows the density of the network and knows exactly its own position in the plane. In many situations these assumptions are unrealistic. Does removing them influence broadcasting time? The aim of this paper is to answer this question, hence we assume that density is unknown and nodes perceive their position with some unknown error margin i¾?. It turns out that this combination of missing and inaccurate information substantially changes the problem: the main new challenge becomes fast broadcasting in sparse networks (with constant density), when optimal time is O(D). Nevertheless, under our very weak scenario, we construct a broadcasting algorithm that maintains optimal time @math for all networks with at least 2 nodes, of diameter Dand granularity g, if each node perceives its position with error margin i¾?= i¾?d, for any (unknown) constant i¾?< 1 2. Rather surprisingly, the minimum time of an algorithm stopping if the source is alone, turns out to be i¾?(D+ g2). Thus, the mere stopping requirement for the special case of the lonely source causes an exponential increase in broadcasting time, for networks of any density and any small diameter. Finally, broadcasting is impossible if i¾?i¾? d 2. A newly deployed multi-hop radio network is unstructured and lacks a reliable and efficient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multi-hop quasi unit disk graph and allow nodes to wake up asynchronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed efficiently. Our algorithm efficiently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings. 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 broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size @math can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized @math -approximation algorithm to compute all pairs shortest paths (APSP) in time @math on weighted graphs, where we use the convention that @math is essentially @math polylog @math and @math is essentially @math polylog @math . We complement this result by proving that any randomized @math -approximation of APSP and @math -approximation of the diameter of a graph takes @math time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a @math -approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST CLIQUE model and contrasts a recent @math -approximation for APSP that runs in time @math in the unicast version of the CONGEST CLIQUE model. On the positive side we provide a deterministic version of Nanongkai's @math -approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model presented by Lenzen and Peleg at PODC'13. 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. In order for the large-scale realization of vehicular networks to be feasible, the problem of congestion control must be addressed to ensure the reliability of safety applications. The latter rely on single-hop broadcasts of safety packets in the control channel to acquire up-to-date knowledge of the local neighbourhood. However, high transmission ranges of onboard radios and the highly dynamic mobility of vehicles may result in fast-forming pockets of high node density in the network. Subsequently, the excessive load caused by safety packets broadcasts may degrade the network performance and subsequently reduce the level safety provided by applications. Existing congestion control schemes in the literature aim to reach a fair rationing of available channel resources throughout the network. However, a particular vehicle, depending on its distance and relative velocity with respect to its neighbours may require less or more network resources than another vehicle to achieve the same level of safety benefit. We examine the problem of adapting the probability of transmission of each node under a slotted p-persistent vehicular broadcast medium access control (MAC) scheme. A network utility maximization (NUM) problem is formulated, in which utility incorporates both the expected delay and a notion of safety benefit. A distributed algorithm is proposed to solve this problem in a decentralized manner and its performance is studied through simulations. During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering even the most basic network coordination problems difficult. Before any reasonable communication can take place, nodes must come up with an initial structure that can serve as a foundation for more sophisticated algorithms. In this paper, we consider the problem of obtaining a vertex coloring as such an initial structure. We propose an algorithm that works in the unstructured radio network model. This model captures the characteristics of newly deployed ad hoc and sensor networks, i.e. asynchronous wake-up, no collision-detection, and scarce knowledge about the network topology. When modeling the network as a graph with bounded independence, our algorithm produces a correct coloring with O(Δ) colors in time O(Δ log n) with high probability, where n and Δ are the number of nodes in the network and the maximum degree, respectively. Also, the number of locally used colors depends only on the local node density. Graphs with bounded independence generalize unit disk graphs as well as many other well-known models for wireless multi-hop networks. They allow us to capture aspects such as obstacles, fading, or irregular signal-propagation.