The number of nodes of a network, called its size, is one of the most important network parameters. A radio network is a collection of stations, called nodes, with wireless transmission and receiving capabilities. It is modeled as a simple connected undirected graph whose 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. If @math listens in a round, and two or more neighbors of @math transmit in this round, a collision occurs at @math . Two scenarios are considered in the literature: if nodes can distinguish collision from silence (the latter occurs when no neighbor transmits), we say that the network has the collision detection capability, otherwise there is no collision detection. We consider the task of size discovery: finding the size of an unknown radio network with collision detection. All nodes have to output the size of the network, using a deterministic algorithm. Nodes have labels which are (not necessarily distinct) binary strings. The length of a labeling scheme is the largest length of a label. Our main result states that the minimum length of a labeling scheme permitting size discovery in the class of networks of maximum degree Delta is Theta( Delta).
We establish an O(nlog2n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(n log n). The fastest previously known algorithm for this problem works in time O(n3 2). Using our broadcasting algorithm, we develop an O(n3 2log2n) algorithm for gossiping in the same network model. 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. This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in radio networks with known topology, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network.The first part of the paper examines the two communication primitives in general graphs. In particular, it proposes a new (efficiently computable) deterministic schedule that uses O(D+Δ log n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time O(D+√[i+2]DΔ logi+1 n), for any network with the diameter D=Ω(logi+4n), where i is an arbitrary integer constant i ≥ 0, see [17]. For the broadcast task we deliver two new results: a deterministic efficient algorithm for computing a radio schedule of length D+O(log3 n), and a randomized algorithm for computing a radio schedule of length D+O(log2 n). These results improve on the best currently known D+O(log4 n) time schedule due to Elkin and Kortsarz [12].The second part of the paper focuses on radio communication in planar graphs, devising a new broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on currently best known D+O(log3n) time schedule proposed by Elkin and Kortsarz in [12]. Our new algorithm should be also seen as the separation result between the planar and the general graphs with a small diameter due to the polylogarithmic inapproximability result in general graphs due to Elkin and Kortsarz, see [11]. 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 deterministic gossiping in ad hoc radio networks with large node labels. The labels (identifiers) of the nodes come from a domain of size N which may be much larger than the size n of the network (the number of nodes). Most of the work on deterministic communication has been done for the model with small labels which assumes N = O(n). A notable exception is Peleg's paper, where the problem of deterministic communication in ad hoc radio networks with large labels is raised and a deterministic broadcasting algorithm is proposed, which runs in O(n2log n) time for N polynomially large in n. The O(nlog2n)-time deterministic broadcasting algorithm for networks with small labels given by implies deterministic O(n log N log n)-time broadcasting and O(n2log2N log n)-time gossiping in networks with large labels. We propose two new deterministic gossiping algorithms for ad hoc radio networks with large labels, which are the first such algorithms with subquadratic time for polynomially large N. More specifically, we propose: a deterministic O(n3 2log2N log n)-time gossiping algorithm for directed networks; and a deterministic O(n log2N log2n)-time gossiping algorithm for undirected networks. 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.