Abstract
We 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.
Original language | English (US) |
---|---|
Pages (from-to) | 686-696 |
Number of pages | 11 |
Journal | Journal of Computer and System Sciences |
Volume | 76 |
Issue number | 7 |
DOIs | |
State | Published - 2010 |
Keywords
- Connectivity
- Coverage
- Local algorithm
- Random geometric graphs
- Sensor network models
- Stretch
- Thresholds
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics