We consider the problem of deterministic broadcasting in radio networks when the nodes have limited knowledge about the topology of the network. We show that for every deterministic broadcasting protocol there exists a network, of radius 2, for which the protocol takes at least @math (n^ 1 4 ) rounds for broadcasting in constant diameter networks. We prove the new lower @math bound for a special family of radius 2 networks. Each network of this family consists of O( n ) components which are connected to each other via only the source node. At the heart of the proof is a novel simulation argument, which essentially says that any arbitrarily complicated strategy of the source node can be simulated by the nodes of the networks, if the source node just transmits partial topological knowledge about some component instead of arbitrary complicated messages. To the best of our knowledge this type of simulation argument is novel and may be useful in further improving the lower bound or may find use in other applications. Keywords: radio networks, deterministic broadcast, lower bound, advice string, simulation, selective families, limited topological knowledge.
@cite_14: In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol II, for any n and for any D ≤ n 2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by H for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors.
@cite_9: We consider the time of broadcasting in ad hoc radio networks modeled as undirected graphs. In such networks, every node knows only its own label and a linear bound on the number of nodes but is unaware of the topology of the network, or even of its own neighborhood. Our aim is to study to what extent the availability of two important characteristics of a broadcasting algorithm influences optimal broadcasting time. These characteristics are adaptiveness and randomization. Our contribution is establishing upper and lower bounds on optimal broadcasting time for three classes of algorithms: adaptive deterministic, oblivious randomized and oblivious deterministic. In two cases we present tight bounds, and in one case a small gap remains. We show that for deterministic adaptive algorithms time Ω(n) is required even for n-node networks of constant diameter. This lower bound is strongest possible, since linear time algorithms are known, and hence establishes optimal time Θ(n) for this class. For oblivious randomized algorithms we show an upper bound O(n min D, log n ) and a lower bound Ω(n) on optimal expected broadcasting time in n-node networks of diameter D. Finally, for oblivious deterministic algorithms we show matching upper and lower bounds Θ(n min D, √n ) on optimal broadcasting time. Our results imply that enforcing obliviousness has at least as strong negative impact on broadcasting time as enforcing determinism, and that algorithms having both these features are strictly less efficient than those having only one of them.
@cite_16: 
Randomized protocols for the broadcasting problem have been studied in @cite_16 , @cite_9 , @cite_14 . In these protocols, the nodes do not know the labels of their neighboring nodes and may in fact have non-unique labels. In @cite_16 , a broadcasting protocol running in @math rounds is given. A lower bound of @math rounds was proved for this problem in @cite_14 . The lower bound of @math rounds for broadcasting protocols also holds for this problem. A broadcasting protocol running in @math , matching the lower bound, was proposed in @cite_9 .