The impact of information on broadcasting time in linear radio networks

AbstractWe consider the problem of distributed deterministic broadcasting in radio networks whose nodes are located on a line. Nodes send messages in synchronous time-slots. Each node v has a given transmission range. All nodes located within this range can receive messages from v. However, a node situated in the range of two or more nodes that send messages simultaneously, cannot receive these messages and hears only noise. Each node knows only its own position and range, as well as the maximum of all ranges. Broadcasting is adaptive: nodes can decide on the action to take on the basis of previously received messages, silence or noise. We prove lower bounds on broadcasting time in this model and construct broadcasting protocols whose performance nearly matches these bounds for the simplest case when nodes are situated on a line. We also show that if nodes do not even know their own range, every broadcasting protocol must be hopelessly slow. While distributed randomized broadcasting algorithms, and, on the other hand, deterministic off-line broadcasting algorithms assuming full knowledge of the radio network, have been extensively studied in the literature, ours are the first results concerning broadcasting algorithms that are distributed and deterministic at the same time. We show that in this case, information available to nodes influences the efficiency of broadcasting in a significant way