Greedy face routing with face identification support in wireless networks

Abstract

Geographic face routing protocols planarize the connectivity graph of a wireless network in a distributed manner and forward packets on the resulted planar topology with high reliability and low overhead. A preferable face routing protocol should provide both guaranteed packet delivery and efficient routing paths, which requires a flexible face switch algorithm adaptive to the network complexity. In this paper, we present a new face routing algorithm named GFRIS that offers both features by performing active probe to measure the face size and generate a unique face identification sequence - face ID. In GFRIS, face switch occurs only if the outgoing edge intersects the local minimum-destination line at a progressive location and the crossing edge is shared between two different faces. To avoid the severe performance penalty when an inefficient face traversal direction is selected on large faces, GFRIS uses the face size to trigger the bounded face traversal procedure as proposed earlier in GOAFR+. As multiple local minimum locations on a face will trigger bounded search repetitively, GFRIS employs a fast forward mode to bypass bidirectional search on the face, which leads to significantly improved path stretch performance. This paper provides a detailed performance comparison between GFRIS and the existing face routing algorithms including GFG, GPSR, GOAFR+ and GFG2. Simulation results show that, by using face ID to assist face switch and adaptively applying the normal and bounded face traversal rules according to the face size, GFRIS can achieve better routing efficiency with low control overhead compared to other protocols evaluated across a wide node density range. © 2010 Elsevier B.V. All rights reserved.