Robust Paths in Random Geometric Graphs with Applications to Mobile Networks

Combating connectivity loss due to node movement is of fundamental importance in mobile networks and many routing protocols have been described in the literature to ensure that the delay due to such link breaks is as low as possible. In this paper, we propose a pre-emptive approach towards countering the adverse effects of mobility: Modeling the network as a random geometric graph G, we obtain paths in G from the source to destination that are guaranteed to survive for a target time, in the event of node mobility. We call such paths as robust paths and obtain bounds on the minimum lengths of paths with a given robustness parameter. We also show how such robust paths can be used to create routes with target survival time in mobile wireless networks.