Design and Analysis of a Fault-Tolerant Topology Control Algorithm for Wireless Multi-hop Networks

摘要

In wireless multi hop networks, topology control (TC) is known to be a fundamental research problem where the objective is to deduce a set of wireless links satisfying some desirable properties such as planarity, symmetricity, fault tolerance, minimum energy, bounded power stretch factor, etc. Among those, planarity and fault tolerance are two important properties that have great impact on network performance. The r-neighborhood graph [8] is a set of planar graph structures that is specially suitable for wireless multi hop networks due to its flexibility in design and simplicity in construction. However, the r-neighborhood graph structure removes too many links to make it planar which significantly degrades the fault tolerance capacity of the network. In this research work, we devise algorithms that provide simple augmentation to the r-neighborhood graph to create fault tolerant topologies on-the-fly with the help of some tunable parameters. We also build mathematical model(s) for various performance metrics of the topology created by the proposed algorithm. Finally, we validate the correctness of the derived analytical models through extensive simulation results.