On the connectivity of dynamic random geometric graphs

Abstract

We provide the first analytical results for the connectivity of dynamic random geometric graphs — a model of mobile wireless networks in which vertices move in random directions, and an edge exists between two vertices if their Euclidean distance is below a given value. We provide precise asymptotic results for the expected length of the connectivity and disconnectivity periods of the network. We believe the formal tools developed in this work could be of use in more concrete settings, in the same manner as the development of connectivity threshold for static random geometric graphs has affected a lot of research done on ad hoc networks. In the process of proving results for the dynamic case we also obtain new asymptotically precise bounds for the probability of the existence of a component of fixed size ℓ, ℓ ≥ 2, for the static case. 1