mca 13(3): e2

Research Article

The Prohibitive Link between Position-based Routing and Planarity

Download253 downloads
  • @ARTICLE{10.4108/mca.1.3.e2,
        author={David Cairns and Marwan Fayed and Hussein T. Mouftah},
        title={The Prohibitive Link between Position-based Routing and Planarity},
        journal={EAI Endorsed Transactions on Mobile Communications and Applications},
        volume={1},
        number={3},
        publisher={ICST},
        journal_a={MCA},
        year={2013},
        month={12},
        keywords={position-based routing, geographic routing, face routing, wireless routing},
        doi={10.4108/mca.1.3.e2}
    }
    
  • David Cairns
    Marwan Fayed
    Hussein T. Mouftah
    Year: 2013
    The Prohibitive Link between Position-based Routing and Planarity
    MCA
    ICST
    DOI: 10.4108/mca.1.3.e2
David Cairns1, Marwan Fayed1,*, Hussein T. Mouftah2
  • 1: Computing Science and Math, University of Stirling, Stirling, UK
  • 2: SITE, University of Ottawa, Ottawa, Canada
*Contact email: mmf@cs.stir.ac.uk

Abstract

Position-based routing is touted as an ideal routing strategy for resource-constrained wireless networks. One persistent barrier to adoption is due to its recovery phase, where messages are forwarded according to leftor right-hand rule (LHR). This is often referred to as face-routing. In this paper we investigate the limits of LHR with respect to planarity.We show that the gap between non-planarity and successful delivery is a single link within a single configuration. Our work begins with an analysis to enumerate all node configurations that cause intersections in the unit-disc graph. We find that left-hand rule is able to recover from all but a single case, the ‘umbrella’ configuration so named for its appearance. We use this information to propose the Prohibitive Link Detection Protocol (PLDP) that can guarantee delivery over non-planar graphs using standard face-routing techniques. As the name implies, the protocol detects and circumvents the ‘bad’ links that hamper LHR. The goal of this work is to maintain routing guarantees while disturbing the network graph as little as possible. In doing so, a new starting point emerges from which to build rich distributed protocols in the spirit of CLDP and GDSTR.