Ad Hoc Wireless Networks & Localised Demand Driven Routing
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. we present a new distributed routing algorithm speciﬁcally 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 ﬂooded 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 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 suﬃcient 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 beneﬁt of this solution is a signiﬁcantly reduced overhead cost, leading to lower power consumption and greater network scalability.
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 ﬁnd that broken routes trigger high cost maintenance reactions because routes are represented using next-hop tables. Each reaction incurs a penalty of O(n2) before stabilisation, which is eliminated in LDDR by trading absolute route accuracy for an approximation of the shortest paths.