Randomized routing algorithms in mobile ad hoc networks

We consider the problem of finding a path from a source to a destination node in a set of mobile wireless nodes. Many solutions to this problem proposed in the literature fall into the position-based routing paradigm, where in each step, the decision of which node to go to next is based only on the position or geographic coordinates of the current node c, its neighboring nodes N(c), and the destination node d. We propose several new randomized position-based algorithms 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. We classify our randomized algorithms based on the strategy they use to define a subset of neighboring nodes as the candidate nodes. The sector-based algorithms select the candidate nodes from a specified sector, whereas the AB (above-below) algorithms choose two candidate nodes, one from above and the other from below the line between the current node and the destination. On convex subdivisions, a sub-class of AB algorithms can be shown to deliver packets to their destinations with probability 1. Our experiments on unit disk graphs, and their associated Yao graphs, Gabriel graphs, and Planarized Local Delaunay Triangulations, show that the delivery rates of all the randomized algorithms we study are significantly better than the deterministic greedy and directional routing algorithms. For some of the algorithms we propose, this improvement comes at the price of only a small deterioration in the stretch factor of the route. Thus, some of our algorithms obtain a good balance between the delivery rate and the stretch factor.