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

Martín Farach-Colton, Miguel A. Mosteiro

    Research output: Contribution to journalArticlepeer-review


    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
    Issue number1
    StatePublished - Sep 2 2015


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

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


    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