Geographic Forwarding With Dead-End Reduction in Mobile<i>Ad Hoc</i>Networks

Abstract

The dead-end situation (which is also known as ldquolocal maximumrdquo) is a fundamental problem when performing geographic forwarding in mobile <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ad</i> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">hoc</i> networks. When a packet encounters a dead end, an additional overhead must be paid to route the packet around the dead end. This paper presents a scheme that decreases the risk of a data packet encountering a dead-end situation as it is forwarded to its destination. Under the scheme, the mobile nodes periodically broadcast beacon messages to exchange neighboring node information to detect dead ends along their intended transmission paths. During forwarding, the relaying nodes use this information to avoid delivering data packets to any relays known to be suffering a dead-end situation. The dead-end reduction (DR) scheme and other two baseline algorithms were evaluated using the ns2 simulator. The analytical and simulation results reveal that the DR scheme significantly reduced the number of dead-end occurrences. As a result, the packet delivery ratio and average path length were both improved compared with the conventional greedy perimeter stateless routing (GPSR) scheme. Moreover, the additional control overhead induced by the DR scheme was less than 10% compared with the GPSR scheme, even with a 0.5-s beacon interval. Coarse quantization is also presented to further reduce the control overhead.