Percolation in a mobile environment

Опубликовано 17 августа 2016, 21:19

We study the following model for mobile wireless networks. At time 0, nodes are distributed as a Poisson point process with intensity \lambda over R^2. We let nodes move independently in continuous time according to Brownian motion, and assume that at any time two nodes can exchange message iff their current distance is at most 1. In contrast with the case of static networks, where the network is usually required to be connected (and therefore limited to a finite region of R^2), in a mobile network nodes can communicate even if there is no path between them at any given time. We then focus on the less restrictive case where \lambda is above the percolation threshold so that at any given time there exists an infinite cluster with probability 1, and consider T to be the first time that a node initially placed at the origin belongs to the infinite cluster. Our result shows that Pr[T \geq t] \leq \exp(- c \sqrt{t}) for some constant c. Our upper bound extends to higher dimensions in the form Pr[T \geq t] \leq \exp(- c t^(d/(d+2))). Joint work with Alistair Sinclair.