Thresholding random geometric graph properties motivated by ad hoc sensor networks

AbstractWe study the emerging phenomenon of ad hoc, sensor-based communication networks. The communication is modeled by the random geometric graph model G(n,r,ℓ) where n points randomly placed within [0,ℓ]d form the nodes, and any two nodes that correspond to points at most distance r away from each other are connected. We study fundamental properties of G(n,r,ℓ) of interest: connectivity, coverage, and routing-stretch. We use a technique that we call bin-covering that we apply uniformly to get (asymptotically) tight thresholds for each of these properties. Typically, in the past, random geometric 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. The technique also yields algorithmic benefits as illustrated by a simple local routing algorithm for finding paths with low stretch. Our specific results should also prove interesting to the sensor networking community that has seen a recent increase in the study of random geometric graphs motivated by engineering ad hoc networks