Large Connectivity for Dynamic Random Geometric Graphs

被引：25

作者：

Diaz, Josep ^{[1
]}

Mitsche, Dieter ^{[1
]}

Perez-Gimenez, Xavier ^{[2
]}

机构：

[1] Univ Politecn Cataluna, Dept Llenguatges & Sistemes Informat, ES-08034 Barcelona, Spain

[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

来源：

IEEE TRANSACTIONS ON MOBILE COMPUTING | 2009年 / 8卷 / 06期

关键词：

Mobile communication systems; dynamic random geometric graphs; connectivity period; NETWORKS;

D O I：

10.1109/TMC.2009.42

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We provide the first rigorous analytical results for the connectivity of dynamic random geometric graphs-a model for mobile wireless networks in which vertices move in random directions in the unit torus. The model presented here follows the one described in [11]. We provide precise asymptotic results for the expected length of the connectivity and disconnectivity periods of the network. We believe that the formal tools developed in this work could be extended to be used in more concrete settings and in more realistic models, in the same manner as the development of the connectivity threshold for static random geometric graphs has affected a lot of research done on ad hoc networks.

引用

页码：821 / 835

页数：15

共 50 条

[1] On the Connectivity of Dynamic Random Geometric Graphs
Diaz, Josep
Mitsche, Dieter
Perez-Gimenez, Xavier
PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2008, : 601 - +
[2] CONNECTIVITY OF SOFT RANDOM GEOMETRIC GRAPHS
Penrose, Mathew D.
ANNALS OF APPLIED PROBABILITY, 2016, 26 (02): : 986 - 1028
[3] On Connectivity Thresholds in Superposition of Random Key Graphs on Random Geometric Graphs
Krishnan, B. Santhana
Ganesh, Ayalvadi
Manjunath, D.
2013 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT), 2013, : 2389 - +
[4] Algebraic Connectivity of Keyhole Random Geometric Graphs
Georgiou, Orestis
IEEE COMMUNICATIONS LETTERS, 2016, 20 (10) : 2079 - 2082
[5] PERCOLATION AND CONNECTIVITY IN AB RANDOM GEOMETRIC GRAPHS
Iyer, Srikanth K.
Yogeshwaran, D.
ADVANCES IN APPLIED PROBABILITY, 2012, 44 (01) : 21 - 41
[6] k-connectivity of Random Graphs and Random Geometric Graphs in Node Fault Model
Takabe, Satoshi
Wadayama, Tadashi
PROCEEDINGS OF 2018 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA2018), 2018, : 252 - 256
[7] Connectivity of Soft Random Geometric Graphs over Annuli
Alexander P. Giles
Orestis Georgiou
Carl P. Dettmann
Journal of Statistical Physics, 2016, 162 : 1068 - 1083
[8] Connectivity of Soft Random Geometric Graphs over Annuli
Giles, Alexander P.
Georgiou, Orestis
Dettmann, Carl P.
JOURNAL OF STATISTICAL PHYSICS, 2016, 162 (04) : 1068 - 1083
[9] Zero-One Law for Connectivity in Superposition of Random Key Graphs on Random Geometric Graphs
Tang, Y.
Li, Q. L.
DISCRETE DYNAMICS IN NATURE AND SOCIETY, 2015, 2015
[10] CONNECTIVITY OF RANDOM GEOMETRIC GRAPHS RELATED TO MINIMAL SPANNING FORESTS
Hirsch, C.
Neuhaeuser, D.
Schmidt, V.
ADVANCES IN APPLIED PROBABILITY, 2013, 45 (01) : 20 - 36

← 1 2 3 4 5 →