Partial Delaunay Triangulations Based Data-Centric Storage and Routing with Guaranteed Delivery in Wireless Ad Hoc and Sensor Networks

Existing memory-less greedy-face-greedy (GFG) routing algorithm can guarantee the delivery in wireless ad hoc networks modeled by a connected unit disk graph. The FACE mode in GFG routing is a recovery mode used when no neighbor closer to destination exists. Face mode requires extracting a planar sub graph out of the unit disk graph. In this paper, we propose to apply partial Delaunay triangulation (PDT) instead of Gabriel graph (GG) used in the original GFG routing. PDT is locally defined without any message exchange in addition to those needed to learn locations of neighbors. This appears to be the densest known such message free planar graph. PDT can be used instead of GG for storing data in wireless sensor networks, where each datum is stored in the face of PDT containing hashed location of datum. Simulation results show the GFG routing has better performance on a PDT than on a GG, since PDT is denser than GG. Applying dominating set based routing or a shortcut scheme can further enhance the PDT-based routing performance.