Minimum interference path preserving and fault tolerant wireless AD hoc networks

Abstract

Interference is one of the major challenges in wireless networks. A wireless node a is snid to interfere node b if transmission from node a unintentionally covers node b. Interference of a link is defined as the number of nodes disturbed while nodes are communicating t.hrollgh a bi-directional link. Increased level of interference may increase number of collisions resulting increased energy consumption and high delay due to retransmissions needed. Approaches have been proposed to reduce interference by dropping more int.erfered links. However, dropping links make a network more susceptible to node faillm,/ depart.ure, which is frequent in ad hoc networks. Thlls dropping more interfered links while keeping t.he network significant.ly connected is an important goal in wireless network research. In t.his thesis, we formulate the problem of constructing minimum interference pat.h preserving and falllt tolerant. wireless ad hoc networks and t.hen provide algorithms, ; ::. ! 1'~'i: ., ,i both centralized and distributed with local information, to solve the problem. That. is, we const.ruct a sl1b graph of a given communication graph such that, for every pair of nodes (H, v) in t.he original graph, more than one path is preserved and there is one path which incurs minimnl11 interference while u and v are communicating. Moreover, for the f1rst. t.ime in the literat.ure, we conceive the concept. of interference spanner and provide a local algorithm to construct fault tolei.ant interference of a given communication graph.