Abstract | Geographic routing is becoming the protocol of choice for
many sensor network applications. The current state of the art is unsatisfactory:
some algorithms are very efficient, however they require a
preliminary planarization of the communication graph. Planarization induces
overhead and is thus not realistic for some scenarios such as the
case of highly dynamic network topologies. On the other hand, georouting
algorithms which do not rely on planarization have fairly low success
rates and fail to route messages around all but the simplest obstacles.
To overcome these limitations, we propose the GRIC geographic routing
algorithm. It has absolutely no topology maintenance overhead, almost
100% delivery rates (when no obstacles are added), bypasses large convex
obstacles, finds short paths to the destination, resists link failure
and is fairly simple to implement. The case of hard concave obstacles
is also studied; such obstacles are hard instances for which performance
diminishes. |