Simple robotic routing in ad hoc networks

Position-based routing protocols in ad hoc networks combine a forwarding strategy with a recovery algorithm. The former fails when there are void regions or physical obstacles that prevent transmission. Then, the recovery algorithm is used to detour the obstacles. To explore the obstacles and find a path around them, the earlier recovery approaches construct a planar graph to avoid routing loops. Distributed algorithms that find planar graphs require accurate knowledge on the location of nodes. The number of nodes on a recovery path increases as the node density increases. Our novel recovery technique operates on a grid model of a network. Obstacles are approximated by adjacent grid elements. We adopt the right-hand rule, which is common in robotics, to follow the perimeter of the discretized obstacle. We do not construct a planar graph. The grid structure reduces the positional accuracy required for nodes, and the recovery path length is independent of the node density