Initializing sensor networks of non-uniform density in the weak sensor model

Martín Farach-Colton, Miguel A. Mosteiro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

Assumptions about node density in the Sensor Networks literature are frequently too strong or too weak. Neither absolutely arbitrary nor uniform deployment seem feasible in most of the intended applications of sensor nodes. We present a Weak Sensor Model-compatible distributed protocol for hop-optimal network initialization, under the assumption that the maximum density of nodes is some value Δ known by all of the nodes. 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 Problem. We show lower bounds for the Group Therapy Problem in Radio Networks of maximum density Δ, regardless of the use of randomization, and a stronger lower bound for the important class of randomized fair protocols. We also show that even when nodes are distributed uniformly, the same lower bound holds, even in expectation and even for the simpler problem of Clear Transmission.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings
PublisherSpringer Verlag
Pages565-576
Number of pages12
ISBN (Print)3540739483, 9783540739487
DOIs
StatePublished - 2007
Event10th International Workshop on Algorithms and Data Structures, WADS 2007 - Halifax, Canada
Duration: Aug 15 2007Aug 17 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4619 LNCS

Other

Other10th International Workshop on Algorithms and Data Structures, WADS 2007
Country/TerritoryCanada
CityHalifax
Period8/15/078/17/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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