Scientific article
Open access

Geographic routing on Virtual Raw Anchor Coordinate systems

Published inTheoretical computer science, vol. 621, p. 1-13
Publication date2016

In this paper we present a novel combinatorial approach for geographic routing with delivery guarantees. Proposed algorithm can be seen as a variant of GFG (Greedy Face Greedy of Bose et.al) algorithm, but based on combinatorial properties derived in the Virtual Raw Anchor Coordinate system, which is the localization scheme of interest. 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 (Virtual Raw Anchor Coordinates), which localizes the nodes with the raw distances from three 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 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 combinatorial approach for geographic routing, based on a raw anchor based positioning system is more robust in the presence of distance measurement errors.

  • Geographic Routing
  • Planar Graphs
  • Combinatorics
Citation (ISO format)
LEONE, Pierre, SAMARASINGHE, Kasun. Geographic routing on Virtual Raw Anchor Coordinate systems. In: Theoretical computer science, 2016, vol. 621, p. 1–13. doi: 10.1016/j.tcs.2015.12.029
Main files (1)
Article (Accepted version)
ISSN of the journal0304-3975

Technical informations

Creation09/28/2016 10:13:00 AM
First validation09/28/2016 10:13:00 AM
Update time03/15/2023 12:46:57 AM
Status update03/15/2023 12:46:57 AM
Last indexation01/16/2024 9:53:27 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack