Fault-tolerant broadcasting in radio networks

We consider broadcasting in radio networks that are subject to permanent no de failures of unknown location. Nodes are spread in a region in some regul ar way. We consider two cases: nodes are either situated at integer points of a line or they are situated in the plane, at grid points of a square or hexagonal mesh. Nodes send messages in synchronous time-slots. Each node v has a given transmission range of the same radius R. All nodes located with in 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. Faulty nodes do not receive or send a ny messages. We give broadcasting algorithms whose worst-case running time has optimal order of magnitude, and we prove corresponding lower bounds. In the case of nonadaptive algorithms this order of magnitude is Theta (D + t ) and for adaptive algorithms it is Theta (D + log(min(R, r))), where t is an upper bound an the number of faults in the network and D is the diameter of the fault-free part of the network that can be reached from the source as a result of those faults. (C) 2001 Academic Press.