TL;DR
This paper introduces the Link lifetime based Backup Routing (LBR) protocol for Mobile Ad hoc Networks (MANETs) to combat route instability caused by dynamic topologies. LBR establishes a primary shortest path and then creates local backup paths for each link, prioritizing longer link lifetimes to ensure backup path availability and significantly improve route stability, packet delivery, and reduce delay.
What Problem Does This Paper Address?
Mobile Ad hoc Networks (MANETs) are characterized by their dynamic topology, where nodes frequently change their positions due to mobility. This constant movement leads to frequent route failures, which in turn trigger rerouting processes. These rerouting events consume valuable network bandwidth and node energy, degrade communication performance, and increase end-to-end delays. Traditional single-path routing protocols, while aiming for shortest paths, are particularly susceptible to these issues. The core problem this paper addresses is the inherent instability of routes in MANETs and the negative impact this has on network performance, aiming to create more robust and longer-lasting routes.
Methods
The paper proposes a novel multipath routing protocol called Link lifetime based Backup Routing (LBR). LBR operates in an on-demand fashion and has two main components:
- Primary Path Discovery: LBR uses a limited flooding mechanism for route discovery. It floods Route Request (RREQ) packets within a "request zone" determined by the source and destination's locations, reducing control overhead. The destination selects the shortest path (minimum hop count) as the primary path.
- Local Backup Path Setup: For each link in the discovered primary path, LBR establishes a local backup path. This is a crucial innovation. Instead of just finding any backup path, LBR specifically constructs backup paths that are predicted to have a longer lifetime than the corresponding primary link. This is achieved by considering link lifetime calculations and a contention mechanism among potential backup path nodes. The goal is to ensure that when a primary link fails, the local backup path is still available and functional.
Route maintenance in LBR relies on link-layer acknowledgments. If a link fails, data packets are rerouted through the established local backup path. Only if both the primary path and its corresponding local backup path fail does a Route Error (RERR) message get sent back to the source to initiate a new route discovery.
Datasets
Not discussed in the paper. The evaluation is based on simulations using OPNET.
Key Insights and Ideas
- Link Lifetime as a Primary Stability Metric: The paper emphasizes that route stability is not just about shortest paths but critically depends on the lifetime of individual links within that path. By prioritizing longer link lifetimes for backup paths, LBR significantly enhances robustness.
- Proactive Local Backup Path Longevity: The core innovation is the intelligent construction of local backup paths. By ensuring these backup paths have a longer predicted lifetime than the primary link they support, LBR effectively mitigates the problem of backup paths becoming outdated prematurely.
- Balancing Overhead and Stability: LBR attempts to balance the need for stability with control overhead. It uses limited flooding for route discovery and avoids periodic beaconing (unlike some other protocols), but the backup path setup does introduce some overhead (CB packets).
- Reduced Rerouting Frequency: By having readily available local backup paths, LBR drastically reduces the need for full route rediscovery when a single link fails, leading to lower control overhead and improved performance.
Key Results
The paper presents theoretical analysis and simulation results comparing LBR with HARP (a representative stable routing protocol).
- Improved Route Lifetime: LBR demonstrates a significant increase in route lifetime, with theoretical analysis suggesting an 18% improvement over single-path routing. Simulations confirm this, showing LBR's route lifetime is substantially higher, especially under varying mobility velocities.
- Higher Packet Delivery Ratio: LBR consistently achieves a higher packet delivery ratio compared to HARP, particularly as node mobility increases. This is attributed to the reduced packet drops resulting from the availability of backup paths.
- Lower End-to-End Delay: LBR exhibits lower end-to-end delays, especially under higher mobility. This is because it avoids the time-consuming route rediscovery process when a primary link fails, instead using the local backup path.
- Control Overhead: While LBR's control overhead can increase rapidly with higher mobility or traffic load due to RREQ flooding, it is generally competitive, and in some scenarios (like lower mobility), it can be lower than HARP due to the absence of periodic beacons. The paper also theoretically bounds the number of contention packets (CB) during backup path setup to a maximum of 4, suggesting manageable overhead.
Limitations and Future Work
- Control Overhead with High Mobility/Traffic: The paper acknowledges that LBR's control overhead can increase rapidly with increasing node velocity and number of CBR flows due to the flooding nature of RREQ.
- Complexity of Backup Path Setup: The contention mechanism for setting up local backup paths, while designed to be efficient, adds complexity.
- Future Work: The authors suggest exploring Quality of Service (QoS) considerations within the LBR framework as a future research direction. They also mention the need to consider other issues on LBR.
Summary updated