Revisiting Planarity in Position-Based Routing for Wireless Networks

Citation

Cairns D, Fayed M & Mouftah HT (2013) Revisiting Planarity in Position-Based Routing for Wireless Networks. In: Zheng J, Mitton N, Li J & Lorenz P (eds.) Ad Hoc Networks: 4th International ICST Conference, ADHOCNETS 2012, Paris, France, October 16-17, 2012, Revised Selected Papers. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, 111. 4th International ICST Conference, ADHOCNETS 2012, Paris, France, 16.10.2012-17.10.2012. Berlin Heidelberg: Springer, pp. 87-102. http://link.springer.com/chapter/10.1007/978-3-642-36958-2_7#; https://doi.org/10.1007/978-3-642-36958-2_7

Abstract
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.

Keywords
position-based routing;geographic routing;face routing;wireless routing; Sensor networks; Wireless LANs;