Mobile geometric graphs: detection, coverage and percolation

Geometric probability and stochastic geometry (60D05) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Brownian motion (60J65) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Dynamic continuum models (systems of particles, etc.) in time-dependent statistical mechanics (82C21) Time-dependent percolation in statistical mechanics (82C43)

Abstract: We consider the following dynamic Boolean model introduced by van den Berg, Meester and White (1997). At time 0, let the nodes of the graph be a Poisson point process in R^d with constant intensity and let each node move independently according to Brownian motion. At any time t, we put an edge between every pair of nodes if their distance is at most r. We study three features in this model: detection (the time until a target point---fixed or moving---is within distance r from 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.

Review text

The authors consider a dynamic Boolean model introduced by van den Berg, Meester and White. This is a model of a random graph evolving in time. The vertices of the graph are given by points in the \(d\)-dimensional Euclidean space distributed initially according to a Poisson point process with a constant intensity and then moving according to independent standard Brownian motions. Edges are drawn between pairs of vertices that are within distance at most a given constant from each other. The authors study large time asymptotics for the following stopping times: (1) detection time, the first time when an auxiliary point moving independently from the vertices of the graph (called ``target point) gets within a certain distance from the vertex set of the graph, (2) coverage time, the first time when all the points of a given set have been detected, and (3) percolation time, the first time when a target point gets within a certain distance from a vertex in an infinite connected component of the graph. The authors prove the following results. If the movement of the target point is deterministic and continuous, the authors give an explicit expression for the distribution of the detection time. If the movement of the target point is random, the authors prove upper bounds on the tail of the distribution, and if the target point moves according to a standard Brownian motion, they prove complementary lower bounds, which are tight in dimensions 1 and 2. All the expressions involve the expected volume of a Wiener sausage. The authors obtain an explicit asymptotic expression for the expected coverage time of an enlarged bounded set with a well-defined Minkowski dimension as the enlargement factor increases. They also show that the coverage time is asymptotically concentrated around its mean. In the case when the target point is not moving or moves according to a standard Brownian motion, the authors prove an upper bound on the tail of the distribution of the percolation time. Complementary lower bounds come for free from the estimates on the detection time. The bounds are tight up to a logarithmic correction. This is the most technical part of the paper. The proof is based on a multi-scale argument and a coupling of the evolution of the graph with an independent Poisson point process of a slightly smaller intensity. Possible applications of the results may be in the study of mobile ad hoc networks with decentralized transmission rules.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Mobile geometric graphs: detection, coverage and percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1955843)