The Bin-Covering Technique for Thresholding Random Geometric
Graph Properties
Authors: S. Muthukrishnan, Gopal Pandurangan
ABSTRACT
We study the emerging phenomenon of ad hoc, sensor-based
communication networks. The communication is modeled by the
geometric random graph model $G(n,r,\ell)$ where $n$ points
randomly placed within $[0,\ell]^d$ form the nodes, and any two
nodes that correspond to points at most distance $r$ away from
each other are connected. The more widely studied $G(n,r)$ model
where $\ell$ is held fixed at unity and $n\rightarrow \infty$
applies for dense ad hoc networks, but the $G(n,r,\ell)$ model is
more detailed, and more generally applicable to modeling
communication networks, sparse or dense.
We study fundamental properties of $G(n,r,\ell)$ of interest:
connectivity, coverage, and routing-stretch. Our main contribution
is a simple analysis technique we call {\em bin-covering} that we
apply uniformly to get {\em (asymptotically) tight} thresholds for
each of these properties. Typically, in the past, geometric random
graph analyses involved sophisticated methods from continuum
percolation theory; on contrast, our bin-covering approach is
discrete and very simple, yet it gives us tight threshold bounds.
Our specific results should also prove interesting to the
networking community that has seen a recent increase in the study
of geometric random graphs motivated by engineering ad hoc
networks.
DIMACS Home Page