Fault tolerant spanners for ad hoc sensor networks

A spanner for ad hoc networks is a network graph containing attractable geometric properties which are useful for efficient communication. The existing spanners degrade their performance in resource constrained ad hoc network, as as sensor network, because of frequent node failures. The spanner do not preserve its geometric properties when the nodes are off. In addition, the heavy packet loss occur when a failed node exists in the routing path. In this paper, we propose two new geometric spanners called fault tolerant relative neighborhood graph (FTRNG) and fault tolerant Gabriel graph (FTGG), which provide better performance at even frequent node failure conditions. The fault tolerant spanners FTRNG and FTGG consider only a subset of nodes in their graph construction. The ns2.28 simulation results show that the performance of the proposed spanners are better than the existing spanners RNG and GG.