Thresholding random geometric graph properties motivated by ad hoc sensor networks

S. Muthukrishnan, Gopal Pandurangan

Research output: Contribution to journalArticle

9 Scopus citations

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 languageEnglish (US)
Pages (from-to)686-696
Number of pages11
JournalJournal of Computer and System Sciences
Volume76
Issue number7
DOIs
StatePublished - Feb 1 2010

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Connectivity
  • Coverage
  • Local algorithm
  • Random geometric graphs
  • Sensor network models
  • Stretch
  • Thresholds

Fingerprint Dive into the research topics of 'Thresholding random geometric graph properties motivated by ad hoc sensor networks'. Together they form a unique fingerprint.

  • Cite this