Bootstrapping a hop-optimal network in the weak sensor model

Martín Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro

    Research output: Contribution to journalConference articlepeer-review


    Sensor nodes are very weak computers that get distributed at random on a surface. Once deployed, they must wake up and form a radio network. Sensor network bootstrapping research thus has three parts: one must model the restrictions on sensor nodes; one must prove that the connectivity graph of the sensors has a subgraph that would make a good network; and one must give a distributed protocol for finding such a network subgraph that can be implemented on sensor nodes. Although many particular restrictions on sensor nodes are implicit or explicit in many papers, there remain many inconsistencies and ambiguities from paper to paper. The lack of a clear model means that solutions to the network-bootstrapping problem in both the theory and systems literature all violate constraints on sensor nodes. For example, random geometric graph results on sensor networks predict the existence of subgraphs on the connectivity graph with good route-stretch, but these results do not address the degree of such a graph, and sensor networks must have constant degree. Furthermore, proposed protocols for actually finding such graphs require that nodes have too much memory, whereas others assume the existence of a contention-resolution mechanism. We present a formal WEAK SENSOR MODEL that summarizes the literature on sensor node restrictions, taking the most restrictive choices when possible. We show that sensor connectivity graphs have low-degree subgraphs with good hop-stretch, as required by the WEAK SENSOR MODEL. Finally, we give a WEAK SENSOR MODEL-compatible protocol for finding such graphs. Ours is the first network initialization algorithm that is implementable on sensor nodes.

    Original languageEnglish (US)
    Pages (from-to)827-838
    Number of pages12
    JournalLecture Notes in Computer Science
    StatePublished - 2005
    Event13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain
    Duration: Oct 3 2005Oct 6 2005

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Bootstrapping a hop-optimal network in the weak sensor model'. Together they form a unique fingerprint.

    Cite this