Optimal Path Based Geographic Routing in Ad Hoc Networks

Routing in ad hoc networks is still a difficult problem by now because of the energy and bandwidth restriction. Using location information, routing can only be based on local information. But concave problem often emerges in the geographical routing algorithms. By analysis of concave-node problem in geographic routing in ad hoc networks, a new algorithm called PGA as well as its improveed versions. In this method, the concept of optimal path is used in all phase of routing, including path construction, routing based on optimal path and routing recovery. The mechanism is very effective to handle the concave node problem. The routing needs only some local path information. The path construction and routing algorithm can be proved to no loop, i.e. the algorithm guarantees the routing can't cause loop path, so the routing is stateless. All of them lead to the algorithm scalability and maintainability. Experiments demonstrate that even in large network, the algorithm is able to achieve high packet delivery success rate, short path length, acceptable routing size and controllable protocol communication cost. In the meanwhile, the routing algorithm is robust enough in dynamic environments. So it can be widely applied in ad hoc or sensor networks.