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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Geographic routing on Virtual Raw Anchor Coordinate systems


    Beteiligte:

    Erscheinungsdatum :

    01.01.2016


    Anmerkungen:

    unige:87831
    ISSN: 0304-3975 ; Theoretical computer science, vol. 621 (2016) p. 1-13


    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Geographic routing on Virtual Raw Anchor Coordinate systems

    Leone, Pierre / Samarasinghe, Kasun | BASE | 2016

    Freier Zugriff

    Greedy Routing on Virtual Raw Anchor Coordinate (VRAC) System

    Leone, Pierre / Samarasinghe, Kasun | BASE | 2016

    Freier Zugriff

    Greedy Routing on Virtual Raw Anchor Coordinate (VRAC) System

    Leone, Pierre / Samarasinghe, Kasun | BASE | 2016

    Freier Zugriff

    Truck Diversion Routing Using Geographic Information Systems

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