Local geometric routing algorithms for edge-augmented planar graphs
Date
2013-09-20
Authors
Wahid, Mohammad Abdul
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Given a geometric graph G = (V,E), where V is the set of vertices and E is the set of edges and a source-target pair {s,t} is a subset of V, a local geometric routing algorithm seeks a route from s to t using only local neighborhood relationships. This thesis proposes a local geometric routing algorithm that uses only a single state bit as message overhead and guarantees delivery of messages in three different classes of edge-augmented planar graphs: convex subdivisions, quasi planar convex subdivisions (allow some augmented edges on a spanning convex subdivision) and 2-augmented triangulations (allow some augmented edges on a spanning triangulation). The proposed algorithm is origin oblivious (does not require the knowledge of the origin vertex s) and predecessor oblivious (does not require the knowledge of the predecessor vertex).
Description
Keywords
online routing algorithm, local routing algorithm, geometric routing algorithm, distributed routing algorithm, oblivious routing algorithm, 1-bit memory local routing algorithm, predecessor-oblivious routing, origin-oblivious routing