DIMACS TR: 2003-39

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.

Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-39.ps.gz

DIMACS Home Page