Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model

Martin Farach-Colton, Miguel A. Mosteiro

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Assumptions about node density in the sensor networks literature are frequently too strong. Neither adversarially chosen nor uniform random deployment seem realistic in many intended applications of sensor nodes. We define smooth distributions of sensor nodes to be those where the minimum density is guaranteed to achieve connectivity in random deployments, but higher densities may appear in certain areas. We study basic problems for smooth distribution of nodes. Most notably, we present a Weak Sensor Model-compliant distributed protocol for hop-optimal network initialization (NI), a fundamental problem in sensor networks. In order to prove lower bounds, we observe that all nodes must communicate with some other node in order to join the network, and we call the problem of achieving such a communication the group therapy (GT) problem. We show a tight lower bound for the GT problem in radio networks for any class of protocols, and a stronger lower bound for the important class of randomized uniform-oblivious protocols. Given that any NI protocol also solves GT, these lower bounds apply to NI. We also show that the same lower bound holds for a related problem that we call independent set , when nodes are distributed uniformly, even in expectation.

Original languageEnglish (US)
Pages (from-to)87-114
Number of pages28
JournalAlgorithmica
Volume73
Issue number1
DOIs
StatePublished - Sep 2 2015

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Network initialization
  • Radio networks
  • Sensor networks
  • Topology control
  • Weak sensor model

Fingerprint Dive into the research topics of 'Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model'. Together they form a unique fingerprint.

  • Cite this