We consider the well-studied radio network model : a synchronous model with a graph G = (V, E) with |V | = n where in each round, each node either transmits a packet, with length B = Ω(log n) bits, or listens. Each node receives a packet iff it is listening and exactly one of its neighbors is transmitting. We consider the problem of k-message broadcast, where k messages, each with Θ(B) bits, are placed in an arbitrary nodes of the graph and the goal is to deliver all messages to all the nodes. We present a simple proof showing that there exist a radio network with radius 2 where for any k, broadcasting k messages requires at least Ω(k log n) rounds. That is, in this network, regardless of the algorithm, the maximum achievable broadcast throughput is O( 1 log n ). We consider the well-studied radio network model, first intoruced by Chlamtac and Kutten [2] . This connections in this model are presented by a graph G = (V, E) with |V | = n. Moreover, the model is synchronous, i.e., the executions proceed in lock-step rounds. In each round, each node either transmits a packet, with length B = Ω(log n) bits, or listens. Each node receives a packet iff it is listening and exactly one of its neighbors is transmitting a packet. We consider the k-message broadcast problem, where k messages, each consisting of Θ(B) bits, are placed in an arbitrary subset of the nodes of the graph and the goal is to deliver all of these messages to all the nodes. We do not require that the packets that nodes transmit (over the channel) are one of these messages. In other words, we do not restrict the algorithm to be a routing algorithm, and in particular, it can be a network coding algorithm [4] , where each of the transmitted packets is a combination of some of the messages. We show the following theorem. Theorem 2.1. There exist a radio network with radius 2 where for any k, broadcasting k messages requires at least Ω(k log n) rounds. The main approach of our proof is similar to that of the proof of the Ω(log 2 n) lower bound of Alon, Bar-Noy, Linial and Peleg [1] on the time to broadcast a single message in radio networks with radius 2. We remark that Theorem 2.1 also follows from the Ω(n log n) gossip lower bound proof of Gasienec and Potapov [3], which itself is achieved by a reduction to the Ω(log 2 n) lower bound of [1]. Our proof is direct and considerably shorter and simpler than the proof of [1] . In order to prove Theorem 2.1, we first work with bipartite networks G = (V, E) where V = S ∪ R, S ∩ R = ∅, and there is no edge between two nodes of S, or between two nodes of R. We call the nodes in S senders and the nodes in R the receivers. We show the following theorem about bipartite radio networks. Lemma 2.2. There exists a bipartite network H with less than n nodes such that in each round, regardless of which nodes transmit, at most O( 1 log n ) of receivers receive a packet.
Ghaffari et al. REF showed a lower bound of Ω(k log n) for this problem, even when network coding is allowed, which holds even for centralized algorithms.
A Bound on the Throughput of Radio Networks
ArXiv
ArXiv
Computer Science