Connectivity of sparse Bluetooth networks. (English) Zbl 1319.05114

Broutin, Nicolas; Devroye, Luc; Lugosi, Gabor

Electron. Commun. Probab. 20, Paper No. 48, 10 p. (2015).

Summary: Consider a random geometric graph defined on \(n\) vertices uniformly distributedin the \(d\)-dimensional unit torus. Two vertices are connected if their distance is less than a “visibility radius” \(r_n\). We consider Bluetooth networks that are locally sparsified random geometric graphs. Each vertex selects \(c\) of its neighbors in the random geometric graph at random and connects only to the selected points. We show that if the visibility radius is at least of the order of \(n^{-(1-\delta)/d}\) for some \(\delta > 0\), then a constant value of \(c\) is sufficient forthe graph to be connected, with high probability. It suffices to take \(c \geq \sqrt{(1+\epsilon)/\delta} + K\) for any positive \(\epsilon\) where \(K\) is a constant depending on \(d\) only. On the other hand, with \(c\leq \sqrt{(1-\epsilon)/\delta}\), the graph is disconnected, with high probability.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C40	Connectivity
68R10	Graph theory (including graph drawing) in computer science
68M10	Network design and communication in computer systems
60C05	Combinatorial probability

Keywords:

random geometric graph; connectivity; irrigation graph