Fault-tolerant broadcasting in radio networks

We consider broadcasting in radio networks that are subject to permanent node failures of unknown location. Nodes are spread in a region in some regular 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 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. Faulty nodes do not receive or send any 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.