Design and analysis of a fault-tolerant topology control algorithm for wireless multi-hop networks

Abstract

Topology control is a fundamental problem in wireless multi-hop networks where the goal is to determine a set of wireless links satisfying some desirable properties such as planarity, symmetricity, fault tolerance, minimum energy, bounded power stretch factor etc. Among these, fault tolerance which pro-vides the ability of a topology to maintain connectivity even in the presence of failure of one or more node(s) or link(s) is very hard to achieve. Al-though a number of fault tolerant structures have been proposed recently, they lack any serious mathematical analysis to estimate their performance. Among the topologies derived from the topology control algorithms, the r−neighborhood graph is a significant class of planar topologies. Moreover, it is a generalized structure to two other widely used graph structures, such as the Gabriel Graph and the Relative Neighborhood Graph. However, the r−neighborhood graph does not ascertain any kind of fault tolerance. So, we fill this notable gap in the literature by augmenting the existing algorithm for constructing r−neighborhood graph to provide fault tolerance and flex-ibility. After designing the algorithm we build mathematical model(s) for various performance metrics of the topology created by the algorithm. We also validate the correctness of the built analytical models through extensive simulation results.