Percolation in a mobile environment

Speaker  Alexandre Stauffer

Host  Yuval Peres

Affiliation  CS Dept, UC Berkeley

Duration  00:36:18

Date recorded  27 May 2010

We study the following model for mobile wireless networks. At time 0, nodes are distributed as a Poisson point process with intensity λ over R2. 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 R2), 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 λ 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 ≥ t] ≤ exp (- c √t) for some constant c. Our upper bound extends to higher dimensions in the form Pr[T ≥ t] ≤ exp (- c t^(d/(d+2))). Joint work with Alistair Sinclair.

©2010 Microsoft Corporation. All rights reserved.
> Percolation in a mobile environment