Ad hoc networks are constructed from a fabric of mobile nodes interconnected by temporary wireless links. Nodes located beyond a single hop are reached using intermediate neighbours to forward messages over long distances. As there is no supporting infrastructure, the task of routing is distributed between the network participants. The problem with this method of communication is that mobility causes the network topology to be unstable.
Traditional solutions maintain routes by exchanging information each time the network topology changes. Using traditional methods to maintain routes in highly mobile environments creates a high cost overhead which prohibits scalability. In this thesis we present a new distributed routing algorithm specifically designed to support highly dynamic networks with the aim of minimising the cost overhead and therefore saving power.
The proposed solution is a hybrid between active/table-driven and reactive/on-demand systems called Localised Demand Driven Routing (LDDR). The aim of LDDR is to reduce the number of cost advertisements flooded onto the network by creating routes on demand. Unlike pure table driven algorithms, our solution does not explicitly discover the next hop to reach the destination. Instead, routes are represented by labelling intermediate nodes to create a chain which links the source and destination together.
The main observation of this thesis is that mobile nodes only remain in range for short periods of time. In this type of situation it is futile to construct a next-hop route table. Ad hoc networks require many nearby neighbours to form sufficient connectivity. These neighbours can be used to repair broken routes using localised maintenance at a cost of O(n). The frequency of route maintenance is related to the rate at which the network topology changes. The benefit of this solution is a significantly reduced overhead cost, leading to lower power consumption and greater network scalability.
The major contribution of this thesis is the proposal and evaluation of the Localised Demand Driven Routing algorithm. Other contributions include the development of new autonomous simulation tools capable of modelling highly realistic motion and feedback stimulus at very high resolution.
A method is provided for analytically comparing the overhead cost of different solutions. Our analysis breaks down the cost of each algorithm into route construction and maintenance. This is done because although some ad hoc routing algorithms do not explicitly perform maintenance, disconnection provokes an equivalent reaction.
In our analysis we find that broken routes trigger high cost maintenance reactions because routes are represented using next-hop tables. Each reaction incurs a penalty of O(n^2) before stabilisation, which is eliminated in LDDR by trading absolute route accuracy for an approximation of the shortest paths.