Deterministic radio broadcasting at low cost

We consider distributed deterministic broadcasting in synchronous radio networks. A node receives a message in a given round if and only if exactly one of its neighbors transmits. The source message has to reach all nodes. We assume that nodes do not know the network topology or even their immediate neighborhood. (Such networks are called ad hoc.) We are concerned with two efficiency measures of broadcasting algorithms: their execution time (number of rounds) and their cost (number of transmissions). We focus our study on the execution time of algorithms which have cost close to minimum. We consider two scenarios depending on whether nodes know or do not know global parameters of the network: the number n of nodes and the eccentricity D of the source. Our main contribution Is proving tight lower bounds on the time of low-cost broadcasting which show sharp differences between these scenarios. In each case, we also give broadcasting algorithms whose performance matches these lower bounds. (C) 2002 Wiley Periodicals, Inc.