The usage of planar graphs in wireless ad-hoc networks

Delaunay triangulation and Voronoi diagrams are well §known expressions in computational geometry. The §present book adopt these methods for the usage in §wireless ad-hoc networks and presents new approaches §for topology control (SDT) and position-based §routing.§The Short delaunay triangulation (SDT) is a powerful §topology based on the construction rules of the §Delaunay triangulation. The Voronoi-aided routing §(VAR) protocol is an efficient implementation of the §well known greedy/perimeter routing approach based §on SDT. The advantage of our approach is efficiency: §Algorithms proposed until today generally separate §topology control and routing, but a joint §development based upon a common efficient data §structure leads to considerably increased §performance.§§The second part of this book is on fault-tolerance §and reliability. Most routing protocols assume a §fault-free environment during message delivery, but §this does not hold in a realistic environment. This §book analyzes greedy/perimeter routing in the §context of crash failures and the reliability of §this algorithm with respect to imprecise position §information and mobile nodes.