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.
