In *Algosensors'04, Lecture Notes in Computer Science 3121*, volume 3121, pages 123–136, July, 2004. Springer.

abstract bibtex

abstract bibtex

We consider a crucial aspect of self-organization of a sensor network consisting of a large set of simple sensor nodes with no location hardware and only very limited communication range. After having been distributed randomly in a given two-dimensional region, the nodes are required to develop a sense for the environment, based on a limited amount of local communication. We describe algorithmic approaches for determining the structure of boundary nodes of the region, and the topology of the region. We also develop methods for determining the outside boundary, the distance to the closest boundary for each point, the Voronoi diagram of the different boundaries, and the geometric thickness of the network. Our methods rely on a number of natural assumptions that are present in densely distributed sets of nodes, and make use of a combination of stochastics, topology, and geometry. Evaluation requires only a limited number of simple local computations.

@inproceedings{fekete04neighborhoodbased, abstract = {We consider a crucial aspect of self-organization of a sensor network consisting of a large set of simple sensor nodes with no location hardware and only very limited communication range. After having been distributed randomly in a given two-dimensional region, the nodes are required to develop a sense for the environment, based on a limited amount of local communication. We describe algorithmic approaches for determining the structure of boundary nodes of the region, and the topology of the region. We also develop methods for determining the outside boundary, the distance to the closest boundary for each point, the Voronoi diagram of the different boundaries, and the geometric thickness of the network. Our methods rely on a number of natural assumptions that are present in densely distributed sets of nodes, and make use of a combination of stochastics, topology, and geometry. Evaluation requires only a limited number of simple local computations.}, author = {S\'{a}ndor P. Fekete and Alexander Kr{\"o}ller and Dennis Pfisterer and Stefan Fischer and Carsten Buschmann}, booktitle = {Algosensors'04, Lecture Notes in Computer Science 3121}, month = jul, number = 3121, pages = {123--136}, publisher = {Springer}, title = {Neighborhood-based topology recognition in sensor networks}, volume = 3121, year = 2004 }

Downloads: 0