Randomized routing algorithms in mobile ad hoc networks

Position-based routing is a well-known paradigm for routing in mobile ad hoc networks. We give several new randomized position-based strategies for routing in mobile ad hoc networks. Our algorithms combine the greedy heuristic of minimizing the distance remaining to the destination and the directional heuristic of staying close to the direction of the destination with the use of randomization to retain some flexibility in the chosen routes. Our experiments show that randomization gives a substantial improvement in the delivery rate over the deterministic greedy and directional routing algorithms. For some of the algorithms we propose, this improvement comes at the expense of only a small deterioration in the stretch factor of the routes.