Mobile Geometric Graphs: Detection, Coverage and Percolation
ABSTRACT We consider the following random graph model, which is
motivated by mobile wireless networks. At time 0, take a
Poisson point process over R^2 with constant intensity to be
the nodes of the graph and let each node move independently
according to Brownian motion. At any time t, we have an edge
between every pair of nodes for which their distance at time t
is at most r. We study three fundamental features in this
model: detection (the time until a given target point---which
may be either fixed or moving---is within distance r to some
node of the graph), coverage (the time until all points inside
a finite box are detected by the graph), and percolation (the
time until a given node belongs to the infinite connected
component of the graph). We obtain precise asymptotics for
these features by combining ideas from stochastic geometry,
coupling, and multi-scale analysis. (This is a joint work with
Yuval Peres, Alistair Sinclair and Perla Sousi.)
BIO Alexandre Stauffer is a graduate student in the department
of Computer Science at UC Berkeley. His research centers on
probabilistic models for mobile networks. He is currently an
intern with the Theory group at MSR.