Date Added: Aug 2009
Mobile Ad-hoc NETworks (MANETs) usually contain sparse or even empty regions called holes. The local optimum problem will occur when routing packets meet holes in the network. This paper proposes a novel Hole-Reshaping Routing protocol (HRR) in large-scale MANETs. It effectively solves the hole problem by regularizing a hole with an ellipse, and then locally broadcasting the hole information away from the hole. Simulation results show that the proposed protocol guarantees finding a short routing path with a small routing delay, which is a prerequisite to achieve scalability in large-scale networks.