A hint-based probabilistic protocol for unicast communications in MANETs

Point-to-point transmissions represent a fundamental primitive in any communication network. Despite many proposals have appeared in the literature, providing an efficient implementation of such an abstraction in Mobile Ad Hoc Networks (MANETs) still remains an open issue. This paper proposes a probabilistic protocol for unicast packet delivery in a MANET. Unlike the classical routing protocols, in our proposal packet forwarding is not driven by a previously computed path. Rather, the nodes of the network exploit a set of routing meta-information (called hints) to discover a path to the destination on-the-fly. This assure robustness against topological changes, while requiring a very low overhead. A node gathers hints from the nodes located within a small number of hops (called the protocol's lookahead) from itself. As showed through simulations, very good performance can be obtained with small lookahead. The main statistical properties of hints have been investigated through an analytical model, which is also reported in the paper. © 2005 Elsevier B.V. All rights reserved.