On Constructing Interference-Aware k-Fault Resistant Topologies for Wireless Ad Hoc Networks
Md. Ehtesamul Haque and Ashikur Rahman
The most fundamental problem in wireless ad-hoc networks is to determine a connected communication subgraph that satisfies desirable topological properties by assigning appropriate transmission power to each node. Some of the properties considered by a vast majority of researchers include minimum-energy, fault tolerance, minimum interference, and bounded node degree. However preserving two or more combination of these properties at the same time is harder to achieve and often overlooked by the research community. In this paper, we propose a topology control algorithm that preserves connectivity and combines two other important properties, e.g, (a) minimum interference, and (b) fault tolerance. Interestingly, these two properties create a fundamental trade-off by running against each other. In one end, interference can be reduced by dropping links that create high interference. On the other end, dropping too many links make a network more susceptible to node failure/departure. Thus dropping high interference links while keeping the network significantly connected is an important goal to achieve. We achieve such goal by formulating the problem of constructing minimum interference path preserving and fault tolerant wireless ad hoc networks under the same framework and then provide algorithms, both centralized and distributed with local information, to solve the problem. Moreover, for the first time in literature, we conceive the concept of fault tolerant interference spanner and provide a local algorithm to construct such spanner of a communication graph.
Keywords: Graph theory, network topology, interference, fault tolerance, wireless ad hoc networks, interference-aware topology, stretch factor, sparse topology.