Connectivity threshold of Bluetooth graphs |
| |
| Authors: | Nicolas Broutin Luc Devroye Nicolas Fraiman Gábor Lugosi |
| |
| Affiliation: | 1. Projet Algorithms, Inria Paris‐Rocquencourt, , 78153 Le Chesnay, FranceSupported by ANR‐09‐BLAN‐0011.;2. School of Compuer Science, McGill University, , Montreal, Canada, H3A 0E9Supported by NSERC (A3456) and FQRNT (90‐ER‐0291).;3. Department of Mathematics and Statistics, McGill University, , Montreal, Canada, H3A 2K6;4. ICREA and Department of Economics, Pompeu Fabra University, , 08027 Barcelona, SpainSupported by the Spanish Ministry of Science and Technology (MTM2009‐09063) and PASCAL Network of Excellence (506778). |
| |
| Abstract: | We study the connectivity properties of random Bluetooth graphs that model certain “ad hoc” wireless networks. The graphs are obtained as “irrigation subgraphs” of the well‐known random geometric graph model. There are two parameters that control the model: the radius r that determines the “visible neighbors” of each vertex and the number of edges c that each vertex is allowed to send to these. The randomness comes from the underlying distribution of vertices in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters r, c and completely characterize the connectivity threshold (in c) for values of r close the critical value for connectivity in the underlying random geometric graph.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 45–66, 2014 |
| |
| Keywords: | random geometric graph connectivity percolation diameter spanning ratio |
|
|
