Static wireless networks are by now quite well understood mathematically through the random geometric graph model. By contrast, there are relatively few rigorous results on the practically important case of mobile networks. In this paper we consider a natural extension of the random geometric graph model to the mobile setting by allowing nodes to move in space according to Brownian motion. We study three fundamental questions in this model: detection (the time until a given target point-which may be either fixed or moving-is detected by the network), coverage (the time until all points inside a finite box are detected by the network), and percolation (the time until a given node is able to communicate with the giant component of the network). We derive precise asymptotics for these problems by combining ideas from stochastic geometry, coupling and multi-scale analysis. We also give an application of our results to analyze the time to broadcast a message in a mobile network. Detection. Consider a "target" particle u which is initially placed at the origin, and whose position at time s is given by g(s), which is a continuous process in R d . We are interested in the time it takes for u to be detected by the mobile geometric graph, namely how long it takes until a node of Π 0 has come within distance at most r 412 Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. from u. More formally we define where the union is taken over all the nodes {X i } of Π 0 and B(x, r) denotes the ball of radius r centered at x. The following theorem, which we prove in Section 3, describes the asymptotic behavior of T det rather precisely. Theorem 1.1. In two dimensions, for any fixed λ and any g independent of the motions of the other nodes, we have that ( 1 + o(1) ) . In addition, if g is an independent Brownian motion then the above bound is tight, i.e., ( 1 + o(1) ) . Remark 1.1. In higher dimensions d ≥ 3, the same argument used to prove Theorem 1.1 yields the pure exponential tail P [T det > t] ≤ exp(−ct) for some constant c = c(d). This bound is also tight up to the value of the constant, yielding the result P [T det > t] = exp(−Θ(t)) (see [32, Theorem 1.1]). Note that the behavior in two dimensions is qualitatively different, a phenomenon that is related to the fact that random walk is recurrent in d = 2 and not in dimensions d ≥ 3. This holds when u is non-mobile or moves according to an independent Brownian motion. Remark 1.3. The power 3 + 6/d in the logarithm is presumably not tight; in light of the lower bounds from detection, the true value lies between 1 and 6 for d = 2 and between 0 and 3 + 6/d for d ≥ 3. Theorem 1.3 is the main technical contribution of the paper; we briefly mention some of the ideas used in the proof. The key technical challenge is the dependency of the G s 's over time. To overcome this, Proof. Let Φ be the set of points of Π 0 that have detected u by time t, that is Φ = {X i ∈ Π 0 : ∃s ≤ t s.t. g(s) ∈ B(X i + ζ i (s), r)}. 415
In REF , three fundamental measures detection, coverage, and percolation time were studied under the assumption that nodes are initially placed according to a Poisson point process in R d , and move according to a discrete-time brownian motion model.
Mobile geometric graphs: detection, coverage and percolation
SODA '11
Mathematics Computer Science