Probabilistic Path Discovery with Snakes in Ad Hoc Networks

Many routing protocols for wireless ad hoc networks proposed in the literature use flooding to discover paths between the source and the destination node. Despite various broadcast optimization techniques, flooding remains expensive in terms of bandwidth and energy consumption. In general, O(N) nodes are involved to discover a path. In this thesis, we prove through a theoretical model that probabilistic path discovery is possible by involving O(sqrt(N)) nodes only. The constant factor depends on the desired path discovery probability. Using a novel network primitive that we call snakes, we introduce practical and cheap probabilistic path discovery algorithms. These algorithms rely on the same network model and assumptions as its flooding counterparts, i. e., that the network is unstructured and that nodes only know their immediate (one-hop) neighbors. Numerical simulations in a static network show that these algorithms achieve path discovery probabilities close to the theoretical optimum. We further present a snake-based algorithm for mobile ad hoc networks and several techniques to enhance the performance in some specific networks.