Deterministic radio broadcasting at low cost
Anders Dessmark, Andrzej Pelc · Networks · 2002
Abstract 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 calledad hoc.) We are concerned with two efficiency measures of broadcasting algorithms: their executiontime(number of rounds) and theircost(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 numbernof nodes and the eccentricityDof 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. © 2002 Wiley Periodicals, Inc.