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.


    Access

    Download


    Export, share and cite



    Title :

    Geographic routing on Virtual Raw Anchor Coordinate systems


    Contributors:

    Publication date :

    2016-01-01


    Remarks:

    ISSN: 0304-3975 ; Theoretical Computer Science, Vol. 621 (2016) pp. 1-13


    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629



    Geographic routing on Virtual Raw Anchor Coordinate systems

    Leone, Pierre / Samarasinghe, Kasun | BASE | 2016

    Free access

    Greedy Routing on Virtual Raw Anchor Coordinate (VRAC) System

    Leone, Pierre / Samarasinghe, Kasun | BASE | 2016

    Free access

    Greedy Routing on Virtual Raw Anchor Coordinate (VRAC) System

    Leone, Pierre / Samarasinghe, Kasun | BASE | 2016

    Free access

    Truck Diversion Routing Using Geographic Information Systems

    Kersh, Erin / Dobbins, James P. / Abkowitz, Mark D. | Transportation Research Record | 2012