Revisiting planarity in position-based routing for wireless networks

David Cairns, Marwan M. Fayed, Hussein T. Mouftah

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


In this paper we investigate the limits of routing according to left- or right-hand rule (LHR). Using LHR, a node upon receipt of a message will forward to the neighbour that sits next in counter-clockwise order in the network graph. When used to recover from greedy routing failures, LHR guarantees success if implemented over planar graphs. This is often referred to as face-routing. In the current body of knowledge it is known that if planarity is violated then LHR is guaranteed only to eventually return to the point of origin. Our work begins with an analysis to enumerate all node configurations that cause intersections. A trace over each configuration reveals 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.

Original languageEnglish
Title of host publicationAd Hoc Networks - Fourth International Conference, ADHOCNETS 2012
Number of pages16
Publication statusPublished - 2 Sept 2013
Event4th International Conference on Ad Hoc Networks, ADHOCNETS 2012 - Paris, France
Duration: 16 Oct 201217 Oct 2012

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
ISSN (Print)1867-8211


Conference4th International Conference on Ad Hoc Networks, ADHOCNETS 2012


  • Face routing
  • Geographic routing
  • Position-based routing
  • Wireless routing


Dive into the research topics of 'Revisiting planarity in position-based routing for wireless networks'. Together they form a unique fingerprint.

Cite this