HDAR: Hole detection and adaptive geographic routing for ad hoc networks

Geographic routing for wireless ad-hoc networks has a well known "local minimum" problem, which is caused by a "hole" that blocks the greedy forwarding process. Existing geographic routing algorithms use perimeter routing strategies to find a long detour path when such a situation occurs. In this paper, we propose a heuristic hole detecting algorithm which can identify the hole in advance and advertise the hole information to those nodes that may be affected. Our work differs from existing hole detection algorithms in its simplicity and efficiency. We study the tradeoff between the area of hole annoucement and the routing path improvement. In addition, we propose a simple representation of hole information and develop a routing scheme based on it. Simulation results illustrate that our approach can reduce the average length and number of hops of routing paths, and is computationally more efficient than other hole detection algorithms.