Efficient Algorithms for Distributed Detection of Holes and Boundaries in Wireless Networks

We propose two novel algorithms for distributed and locationfree boundary recognition in wireless sensor networks. Both approaches enable a node to decide autonomously whether it is a boundary node, based solely on connectivity information of a small neighborhood. This makes our algorithms highly applicable for dynamic networks where nodes can move or become inoperative. We compare our algorithms qualitatively and quantitatively with several previous approaches. In extensive simulations, we consider various models and scenarios. Although our algorithms use less information than most other approaches, they produce significantly better results. They are very robust against variations in node degree and do not rely on simplified assumptions of the communication model. Moreover, they are much easier to implement on real sensor nodes than most existing approaches.

• Publication year

  2011

• Venue

  The Sea

• Publication date

  2011-03-09

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1007/978-3-642-20662-7_33arXiv 1103.1771
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multidimensional Scaling

  2021cited by this paper
• Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods

  2009cited by this paper
• On Boundary Recognition without Location Information in Wireless Sensor Networks

  2008cited by this paper
• Topological Hole Detection in Sensor Networks with Cooperative Neighbors

  2006cited by this paper
• Boundary recognition in sensor networks by topological methods

  2006cited by this paper
• Hole detection or: "how much geometry hides in connectivity?"

  2006cited by this paper
• Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology

  2006cited by this paper
• Deterministic boundary recognition and topology extraction for large sensor networks

  2005cited by this paper
• Coverage and hole-detection in sensor networks via homology

  2005cited by this paper
• Topological hole detection in wireless sensor networks and its applications

  2005influential reference
• A New Approach for Boundary Recognition in Geometric Sensor Networks

  2005cited by this paper
• An Algorithm for Boundary Discovery in Wireless Sensor Networks

  2005cited by this paper
• Fast Distributed Well Connected Dominating Sets for Ad Hoc Networks

  2004cited by this paper
• Distributed Perimeter Detection in Wireless Sensor Networks

  2004cited by this paper
• Locating and bypassing routing holes in sensor networks

  2004cited by this paper
• Neighborhood-Based Topology Recognition in Sensor Networks

  2004influential reference
• Geographic routing without location information

  2003cited by this paper
• Monographs on statistics and applied probability

  1990cited by this paper
• Multidimensional scaling: I. Theory and method

  1952cited by this paper

• Finding the polygon hull of a network without conditions on the starting vertex

  2019cites this paper
• One-class support vector machines: analysis of outlier detection for wireless sensor networks in harsh environments

  2015cites this paper
• Location-Free Detection of Network Boundaries

  2015cites this paper
• Characteristics and classification of outlier detection techniques for wireless sensor networks in harsh environments: a survey

  2015cites this paper
• An Algorithmic View on Sensor Networks - Surveillance, Localization, and Communication

  2014cites this paper
• Parallel Bi-objective Shortest Paths Using Weight-Balanced B-trees with Bulk Updates

  2014cites this paper
• Homology theory for coverage hole detection in wireless sensor networks. (Homologie simpliciale et couverture radio dans un réseau de capteurs)

  2013cites this paper
• Algorithmic Aspects of Communication and Localization in Wireless Sensor Networks

  2012cites this paper
• Perimeter detection in wireless sensor networks

  2012cites this paper