Partial Delaunay triangulations based routing, address configuration and date-centric storage in ad hock network

Abstract

The work of this thesis is based on a recently proposed memoryless Greedy-Face-Greedy (GFG) routing algorithm that guarantees delivery in connected unit disk graphs (where two nodes are connected if and only if their distance is no more than the transmission radius, which is equal for all nodes). The FACE mode 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. We propose to apply recently proposed Partial Delaunay triangulation (PDT) instead of Gabriel Graph (GG) used in the original GFG. PDT is locally defined without any message exchange in addition to those needed to learn the locations of neighbors. Routing is further enhanced by applying dominating set based routing. We consider two solutions for generating IP addresses: each node generates IP addresses following its own scheme, or all addresses are generated at a unique node in the network, called the Addressing Agent (AA). (Abstract shortened by UMI.)