On the Occurrence of Dead-End Nodes in Geographic Forwarding

In geographic forwarding routing for ad hoc packet networks, if the source of a data packet cannot reach the destination directly, it transmits to the neighbor that is closest to the destination. The process then repeats, terminating when the destination is a neighbor of the last repeater. However, delivery is not guaranteed even when a route exists, because forwarding fails at repeater nodes that are closer to the destination than any of their neighbors. Algorithms to bypass such local minimum nodes have been proposed by a number of authors, but are complex and may significantly increase the hop-count of the route whenever a local minimum node is encountered. We analyze the statistical properties of this event, and its relationship to other network parameters, for an ad hoc packet network whose nodes are points of a homogeneous Poisson process, and the wireless propagation channels exhibit attenuation with distance and log-normal fading.