Communication in Random Geometric Radio Networks with Positively Correlated Random Faults

Evangelos Kranakis, Michel Paquette and Andrzej Pelc

We study the feasibility and time of communication in random geometric radio networks, where nodes fail randomly with positive correlation. We consider a set of radio stations with the same communication range, distributed in a random uniform way on a unit square region. In order to capture fault dependencies, we introduce the ranged spot model in which damaging events, called spots, occur randomly and independently on the region, causing faults in all nodes located within distance s from them. Node faults within distance 2s become dependent in this model and are positively correlated.We investigate the impact of the spot arrival rate on the feasibility and the time of communication in the fault-free part of the network. We provide an algorithm which broadcasts correctly with probability 1 − ε in faulty random geometric radio networks of diameter D in time O(D + log 1/ε ).

Keywords: Fault-tolerance, dependent faults, broadcast, crash faults, random, geometric radio network.