Routing with Guaranteed Delivery in ad hoc Wireless Networks

Routing with Guaranteed Delivery in ad hoc Wireless Networks

1999 | Prosenjit Bose, Pat Morin, Ivan Stojmenović, Jorge Urrutia
This paper presents distributed routing algorithms for ad hoc wireless networks modeled as unit graphs, where nodes are points in the plane and communication is possible if the distance between nodes is less than a fixed unit. The algorithms ensure guaranteed delivery of packets without requiring packet duplication or memory at the nodes. They can be extended to broadcasting and geocasting without packet duplication. A byproduct is a simple distributed protocol for extracting a planar subgraph of a unit graph. Simulation results are also presented. The paper considers routing in mobile ad hoc networks (MANETs), where nodes communicate if their distance is less than their broadcast range. Routing may require intermediate nodes. The paper assumes that the source knows the destination's location. The unit graph U(S) is a geometric graph where an edge exists if the distance between two nodes is less than or equal to 1. The algorithms do not require global information about U(S) and use only local information. The paper describes algorithms for routing, broadcasting, and geocasting in planar graphs. It shows how to extract a connected planar subgraph of U(S) in a distributed manner. The GABRIEL algorithm is used to extract a connected planar subgraph by eliminating edges not in the Gabriel graph. The resulting graph is connected and planar. For routing, the paper describes FACE-1 and FACE-2 algorithms. FACE-1 traverses faces of the graph to find a path to the destination, while FACE-2 improves performance by avoiding full face traversal. The paper also describes BROADCAST and GEOCAST algorithms for broadcasting and geocasting. BROADCAST visits all vertices of the graph, while GEOCAST visits all vertices in a query region. The paper compares the performance of these algorithms with the GEDIR algorithm, a greedy routing algorithm. The results show that GEDIR has a low average dilation but a low delivery rate in sparse graphs. FACE-1 and FACE-2 have higher delivery rates but higher average dilation. Hybrid algorithms combining GEDIR with FACE-2 or GFG (a modified version of GEDIR) show improved performance, achieving guaranteed delivery in sparse graphs and low average dilation in dense graphs. The paper concludes that the proposed algorithms guarantee delivery without packet duplication or memory at nodes, and they can be used in conjunction with simpler algorithms that do not guarantee delivery. However, the BROADCAST and GEOCAST algorithms are not practical due to their quadratic message count and delivery time. The paper also suggests future research directions, including dynamic networks, 3D space, unequal transmission ranges, and power-aware routing.This paper presents distributed routing algorithms for ad hoc wireless networks modeled as unit graphs, where nodes are points in the plane and communication is possible if the distance between nodes is less than a fixed unit. The algorithms ensure guaranteed delivery of packets without requiring packet duplication or memory at the nodes. They can be extended to broadcasting and geocasting without packet duplication. A byproduct is a simple distributed protocol for extracting a planar subgraph of a unit graph. Simulation results are also presented. The paper considers routing in mobile ad hoc networks (MANETs), where nodes communicate if their distance is less than their broadcast range. Routing may require intermediate nodes. The paper assumes that the source knows the destination's location. The unit graph U(S) is a geometric graph where an edge exists if the distance between two nodes is less than or equal to 1. The algorithms do not require global information about U(S) and use only local information. The paper describes algorithms for routing, broadcasting, and geocasting in planar graphs. It shows how to extract a connected planar subgraph of U(S) in a distributed manner. The GABRIEL algorithm is used to extract a connected planar subgraph by eliminating edges not in the Gabriel graph. The resulting graph is connected and planar. For routing, the paper describes FACE-1 and FACE-2 algorithms. FACE-1 traverses faces of the graph to find a path to the destination, while FACE-2 improves performance by avoiding full face traversal. The paper also describes BROADCAST and GEOCAST algorithms for broadcasting and geocasting. BROADCAST visits all vertices of the graph, while GEOCAST visits all vertices in a query region. The paper compares the performance of these algorithms with the GEDIR algorithm, a greedy routing algorithm. The results show that GEDIR has a low average dilation but a low delivery rate in sparse graphs. FACE-1 and FACE-2 have higher delivery rates but higher average dilation. Hybrid algorithms combining GEDIR with FACE-2 or GFG (a modified version of GEDIR) show improved performance, achieving guaranteed delivery in sparse graphs and low average dilation in dense graphs. The paper concludes that the proposed algorithms guarantee delivery without packet duplication or memory at nodes, and they can be used in conjunction with simpler algorithms that do not guarantee delivery. However, the BROADCAST and GEOCAST algorithms are not practical due to their quadratic message count and delivery time. The paper also suggests future research directions, including dynamic networks, 3D space, unequal transmission ranges, and power-aware routing.
Reach us at info@study.space