| A mobile ad hoc network (MANET) is a dynamically reconfigurable wireless network in which mobile computers (nodes) powered by tiny batteries communicate with each other using short-range packet radios to form an ad hoc or unstructured network without any fixed infrastructure. With the advent of sophisticated wireless technologies, MANETs are increasingly being embedded in complex and safety-critical applications such as emergency warning systems. Such networks are required to operate even under failure conditions caused by node motion or component malfunction, while consuming low power. The overall goal of our research is to develop fault-tolerant methods to improve the dependability of MANETs while minimizing the total transmission power consumed by nodes.; In the applications of interest, a source node should be able to communicate with a destination node reliably. Since the topology of the network often changes due to node motion, fault-tolerant routes linking the source and the destination should be discovered online. We first describe a fault-tolerant route discovery protocol (ALTDSR) that finds a primary path between the source and the destination, and a set of alternative paths. We introduce dominator relationships between primary and non-primary path nodes. Using the dominator concept, we develop distributed algorithms that guarantee finding a 1-FT (1-fault tolerant) route set if such routes exist. We then exploit the guarantee provided by ALTDSR to maintain a fault-tolerant topology under mobility while minimizing the total transmission power consumed. We represent the MANET by an undirected graph G, and introduce a graph transformation model to capture node mobility. Given that G is k-connected and the transmission power of all nodes remain unchanged, the new topology Gm obtained after a node moves to a new location may not be k-connected. We derive necessary conditions for Gm to be k-connected, and develop an algorithm to maintain 2-connectivity under mobility conditions. In some mobile applications including accident warning networks on highways, a mobile node (source) needs to broadcast to all nodes within a geographic region around the source. We call such a communication mechanism "myopic" broadcasting, and we develop a protocol (MYOSBA) that guarantees delivery of a message under idealized conditions such as zero mobility. Using simulation, we show that MYOSBA reliably delivers messages even under moderate mobility conditions. We also describe a software-based technique for online detection of hardware faults. This technique helps to design nodes that prevent the effects of the faults from propagating to other nodes in the network. |
