research-article

On the connectivity of dynamic random geometric graphs

Authors:

Dieter Mitsche,

Xavier Pérez-GiménezAuthors Info & Claims

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 601 - 610

Published: 20 January 2008 Publication History

Abstract

We provide the first analytical results for the connectivity of dynamic random geometric graphs --- a model of mobile wireless networks in which vertices move in random directions, and an edge exists between two vertices if their Euclidean distance is below a given value. We provide precise asymptotic results for the expected length of the connectivity and disconnectivity periods of the network. We believe the formal tools developed in this work could be of use in more concrete settings, in the same manner as the development of connectivity threshold for static random geometric graphs has affected a lot of research done on ad hoc networks. In the process of proving results for the dynamic case we also obtain new asymptotically precise bounds for the probability of the existence of a component of fixed size l, l ≥ 2, for the static case.

References

[1]

M. Appel, and R. P. Russo, The connectivity of a graph on uniform points on {0, 1} ^d, Statistics & Probability Letters, 60(4):351--357, 2002

[2]

B. Bollobás, Random Graphs, (2nd edition), Cambridge Univ. Press, 2001.

[3]

T. Camp, J. Boleng, and V. Davies. Mobility models for ad-hoc network research. Mobile Ad Hoc Networking: Research, Trends and Applications, 2(5):483--502, 2002.

[4]

J. Díaz, X. Pérez, M. Serna, and N. Wormald. Walkers on the cycle and the grid. STACS, Lecture Notes in Computer Science 3404, 353--363. Springer, 2005.

[5]

L. Guibas, J. Hershberger, S. Suri, and Li Zhang, Kinetic Connectivity for Unit Disks. Discrete and Computational Geometry, 25:591--610, 2001.

[6]

R. A. Guerin, Channel Occupancy Time Distribution in a Cellular Radio System. IEEE Transactions on Vehicular Technology, 36(3):89--99, 1987.

[7]

P. Gupta, and P. R. Kumar, Critical power for asymptotic connectivity in wireless networks. In: Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming. 547--566, 1999. Ed. by W. McEneaney, G. G. Yin, and Q. Zhang. Birkhäuser.

[8]

R. Hekmat, Ad-hoc Networks: Fundamental Properties and Network Topologies, Springer. 2006

Digital Library

[9]

X. Hong, M. Gerla, G. Pei and C. Chiang. Group mobility model for Ad hoc wireless networks. Proc. ACM/IEEE MSWIM, Seattle, 1999.

Digital Library

[10]

A. Jardosh, E. Belding-Royer, K. Almeroth and S. Suri. Towards Realisitic Mobility Models for Mobile Ad hoc Networks. ACM Mobicom, San Diego, 2003.

Digital Library

[11]

A. Nain, D. Towsley, B. Liu and Z. Liu. Properties of random direction models. ACM MobiHoc, San Diego, 2005.

[12]

F.-X. Plarre, and P. R. Kumar. Scaling Laws for Ad Hoc Wireless Networks: An Information Theoretic Approach. NOW Publishers, The Netherlands. 2006.

[13]

M. Penrose, The longest edge of the random minimal spanning tree, The Annals of Applied Probability, 7(2):340--361, 1997.

[14]

M. Penrose, On k-connectivity for a geometric random graph, Random Structures and Algorithms, 15:145--164, 1999.

Digital Library

[15]

M. Penrose, Random Geometric Graphs, Oxford Studies in Probability. Oxford U.P., 2003.

[16]

P. Santi, and D. M. Blough. An Evaluation of Connectivity in Mobile Wireless Ad Hoc Networks. Proc. Int. Conference on Dependable Systems and Networks, 89--98, 2002.

Digital Library

Cited By

Lujak MBillhardt HOssowski S(2012)On mobile target allocation with incomplete information in defensive environmentsProceedings of the 6th KES international conference on Agent and Multi-Agent Systems: technologies and applications10.1007/978-3-642-30947-2_4(4-13)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-30947-2_4
Clementi ASilvestri R(2011)Parsimonious flooding in geometric random-walksProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075066(298-310)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2075029.2075066
Lujak MGiordani SOssowski S(2011)Value of incomplete information in mobile target allocationProceedings of the 9th German conference on Multiagent system technologies10.5555/2050592.2050602(89-100)Online publication date: 6-Oct-2011
https://dl.acm.org/doi/10.5555/2050592.2050602
Show More Cited By

Index Terms

On the connectivity of dynamic random geometric graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Large Connectivity for Dynamic Random Geometric Graphs

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 ...
Mixed Connectivity of Random Graphs
Combinatorial Optimization and Applications
Abstract
For positive integers k and $λ$ , a graph G is $(k, λ)$ -connected if it satisfies the following two conditions: (1) $| V (G) | \geq k + 1$ , and (2) for any subset $S \subseteq V (G)$ and any subset $L \subseteq E (G)$ with $λ | S | + | L | < k λ$ , $G - (S \cup L)$ is connected. For positive integers k and $ℓ$ , a ... $\overset{}{} {(_{})}_{}^{}$ $(\begin{matrix} \end{matrix})$ $_{}$ $_{}$
On the connectivity of random graphs from addable classes

A class A of graphs is called weakly addable (or bridge-addable) if for any G@?A and any two distinct components C"1 and C"2 in G, any graph that can be obtained by adding an edge between C"1 and C"2 is also in A. McDiarmid, Steger and Welsh (2006) ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

January 2008

1289 pages

Program Chair:
Shang-Hua Teng
Boston University and Akamai Technologies, Inc.

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

Research-article

Conference

SODA08

Sponsor:

SIGACT

SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms

January 20 - 22, 2008

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
564
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lujak MBillhardt HOssowski S(2012)On mobile target allocation with incomplete information in defensive environmentsProceedings of the 6th KES international conference on Agent and Multi-Agent Systems: technologies and applications10.1007/978-3-642-30947-2_4(4-13)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-30947-2_4
Clementi ASilvestri R(2011)Parsimonious flooding in geometric random-walksProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075066(298-310)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2075029.2075066
Lujak MGiordani SOssowski S(2011)Value of incomplete information in mobile target allocationProceedings of the 9th German conference on Multiagent system technologies10.5555/2050592.2050602(89-100)Online publication date: 6-Oct-2011
https://dl.acm.org/doi/10.5555/2050592.2050602
Lujak MGiordani S(2011)On the communication range in auction-based multi-agent target assignmentProceedings of the 5th international conference on Self-organizing systems10.5555/1964607.1964612(32-43)Online publication date: 23-Feb-2011
https://dl.acm.org/doi/10.5555/1964607.1964612
Clementi AMonti ASilvestri R(2010)Modelling mobilityProceedings of the 37th international colloquium conference on Automata, languages and programming: Part II10.5555/1880999.1881053(490-501)Online publication date: 6-Jul-2010
https://dl.acm.org/doi/10.5555/1880999.1881053
Clementi AMonti ASilvestri RRicha AGuerraoui R(2010)Fast flooding over ManhattanProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835784(375-383)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835784
Cai HEun DChiang MRoy R(2009)Stochastic link-level dynamics in mobile ad-hoc networksProceedings of the 2009 MobiHoc S3 workshop on MobiHoc S310.1145/1540358.1540364(17-20)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.1145/1540358.1540364

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten