Deterministic boundary recongnition and topology extraction for large sensor networks

Abstract

We present a new framework for the crucial challenge of
  self-organization of a large sensor network. The basic scenario can
  be described as follows: Given a large swarm of immobile sensor
  nodes that have been scattered in a polygonal region, such as a
  street network.  Nodes have no knowledge of size or shape of the
  environment or the position of other nodes. Moreover, they have no
  way of measuring coordinates, geometric distances to other nodes, or
  their direction. Their only way of interacting with other nodes is
  to send or to receive messages from any node that is within
  communication range.  The objective is to develop algorithms and
  protocols that allow self-organization of the swarm into large-scale
  structures that reflect the structure of the street network, setting
  the stage for global routing, tracking and guiding algorithms.

  Our algorithms work in two stages: boundary recognition and topology
  extraction. All steps are strictly deterministic, yield fast
  distributed algorithms, and make no assumption on the distribution
  of nodes in the environment, other than sufficient density.