Geographic routing on Virtual Raw Anchor Coordinate systems

摘要

In this manuscript, we present geographic routing algorithms with delivery guarantees on a virtual coordinate system, namely Virtual Raw Anchor Coordinates (VRAC). Proposed algorithms can be seen as a variant of GFG (Greedy Face Greedy of Bose et al.) algorithm and based on combinatorial and geometric properties derived in the Virtual Raw Anchor Coordinate system. We utilize a local planarization algorithm of a geometric graph, which is based on the Schnyder's characterization of planar graphs. The new approach is combinatorial in the sense that the nodes are ordered with respect to three distinct order relations satisfying suitable properties. The coordinate system that motivated the development of this routing algorithm is VRAC, which localizes the nodes with the raw distances from three fixed anchors. Since the positions of the anchors are not known, the VRAC coordinate system does not correspond to the Euclidean location of nodes, yet leaving sufficient information to define necessary combinatorial and geometric constructs for routing with guaranteed delivery. In particular, the routing algorithm avoids the references to geographical arguments and makes use only of the order relations on the nodes. We expect that our approach will foster further research on building efficient order relations, that will prove to be useful in practical implementation of geographic routing algorithms. In particular, we expect that further work will prove that the geographic routing based on a raw anchor based positioning system is more robust in the presence of distance measurement errors. (C) 2015 Elsevier B.V. All rights reserved.