Mobile geometric graphs: detection, coverage and percolation. (English) Zbl 1273.82060
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.
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.
Reviewer: Artem Sapozhnikov (Leipzig)
MSC:
| 82C43 | Time-dependent percolation in statistical mechanics |
| 60G55 | Point processes (e.g., Poisson, Cox, Hawkes processes) |
| 60D05 | Geometric probability and stochastic geometry |
| 60J65 | Brownian motion |
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 82C21 | Dynamic continuum models (systems of particles, etc.) in time-dependent statistical mechanics |
Keywords:
Boolean model; Brownian motion; Poisson point process; random graph; percolation; Wiener sausage; Minkowski dimension; coupling; mobile ad hoc networkReferences:
| [1] | Alon N., Spencer J.H.: The Probabilistic Method, 3rd edn. Wiley, New York (2008) · Zbl 1148.05001 · doi:10.1002/9780470277331 |
| [2] | Berezhovskii A.M., Makhovskii Yu.A., Suris R.A.: Wiener sausage volume moments. J. Stat. Phys. 57, 333-346 (1989) · doi:10.1007/BF01023647 |
| [3] | van den Berg J., Meester R., White D.G.: Dynamic boolean model. Stoch. Process. Appl. 69, 247-257 (1997) · Zbl 0911.60083 · doi:10.1016/S0304-4149(97)00044-6 |
| [4] | Ciesielski Z., Taylor S.J.: First passage times and sojourn times for Brownian motion in space and the exact Hausdorff measure of the sample path. Trans. Am. Math. Soc. 103, 434-450 (1962) · Zbl 0121.13003 · doi:10.1090/S0002-9947-1962-0143257-8 |
| [5] | Clementi, A., Pasquale, F., Silvestri, R.: MANETS: high mobility can make up for low transmission power. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP) (2009) · Zbl 1248.68108 |
| [6] | Drewitz, A., Gärtner, J., Ramírez, A.F., Sun, R.: Survival probability of a random walk among a poisson system of moving traps (2010). arXiv:1010.3958v1 · Zbl 1267.60109 |
| [7] | Gupta, P., Kumar, P.R.: Critical power for asymptotic connectivity in wireless networks. In: McEneany, W.M., Yin, G., Zhang, Q. (eds.) Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, pp. 547-566. Birkhäuser, Boston (1998) · Zbl 0916.90101 |
| [8] | Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Transactions on Information Theory, 46, 388-404 (2000) [correction in IEEE Transactions on Information Theory 49, p. 3117 (2000)] · Zbl 0991.90511 |
| [9] | Kesidis, G., Konstantopoulos, T., Phoha, S.: Surveillance coverage of sensor networks under a random mobility strategy. In: Proceedings of the 2nd IEEE International Conference on Sensors (2003) |
| [10] | Kesten H., Sidoravicius V.: The spread of a rumor or infection in a moving population. Ann. Probab. 33, 2402-2462 (2005) · Zbl 1111.60074 · doi:10.1214/009117905000000413 |
| [11] | Konstantopoulos, T.: Response to Prof. Baccelli’s lecture on modelling of wireless communication networks by stochastic geometry. Comput. J. Adv. Access (2009) |
| [12] | Lam, H., Liu, Z., Mitzenmacher, M., Sun, X., Wang, Y.: Information dissemination via random walks in d-dimensional space (2011). arXiv:1104.5268 · Zbl 1422.68224 |
| [13] | Liu, B., Brass, P., Dousse, O., Nain, P., Towsley, D.: Mobility improves coverage of sensor networks. In: Proceedings of the 6th ACM International Conference on Mobile Computing and Networking (MobiCom) (2005) · Zbl 0932.05083 |
| [14] | Mattila P.: Geometry of Sets and Measures in Euclidean Spaces. Cambridge University Press, Cambridge (1995) · Zbl 0819.28004 · doi:10.1017/CBO9780511623813 |
| [15] | Meester R., Roy R.: Continuum Percolation. Cambridge University Press, Cambridge (1996) · Zbl 0858.60092 · doi:10.1017/CBO9780511895357 |
| [16] | Moreau, M., Oshanin, G., Bénichou, O., Coppey, M.: Lattice theory of trapping reactions with mobile species. Phys. Rev. E 69 (2004) · Zbl 1031.80007 |
| [17] | Mörters P., Peres Y.: Brownian Motion. Cambridge University Press, Cambridge (2010) · Zbl 1243.60002 · doi:10.1017/CBO9780511750489 |
| [18] | Penrose M.: The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7, 340-361 (1997) · Zbl 0884.60042 · doi:10.1214/aoap/1034625335 |
| [19] | Penrose M.: On k-connectivity for a geometric random graph. Random Struct. Algorithms 15, 145-164 (1999) · Zbl 0932.05083 · doi:10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G |
| [20] | Penrose M.: Random Geometric Graphs. Oxford University Press, Oxford (2003) · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001 |
| [21] | Penrose M., Pisztora A.: Large deviations for discrete and continuous percolation. Adv. Appl. Probab. 28, 29-52 (1996) · Zbl 0853.60085 · doi:10.2307/1427912 |
| [22] | Pettarin, A., Pietracaprina, A., Pucci, G., Upfal, E.: Infectious random walks (2010). arXiv:1007.1604 |
| [23] | Sinclair, A., Stauffer, A.: Mobile geometric graphs, and detection and communication problems in mobile wireless networks (2010). arXiv:1005.1117v1 |
| [24] | Spitzer F.: Electrostatic capacity, heat flow, and Brownian motion. Z. Wahrscheinlichkeitstheorie verw. Geb. 3, 110-121 (1964) · Zbl 0126.33505 · doi:10.1007/BF00535970 |
| [25] | Stoyan D., Kendall W.S., Mecke J.: Stochastic Geometry and its Applications, 2nd edn. Wiley, New York (1995) · Zbl 0838.60002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
