Boundary recognition in sensor networks by building relative contours

Wireless sensor networks (WSN) are affected by underlying environments in which sensors are deployed randomly. Inevitably, there are many irregular holes in a WSN because of the existence of obstacles or the death of some sensors. To detect these holes is of great importance to both WSN applications and networking functionalities. Holes are described by a set of sensor nodes on their boundaries. In this paper, we study the problem of identifying boundaries of holes in a WSN. By extracting hidden geometric features in the topology of a WSN, we are able to recognize sensor nodes on both inner and outer boundaries of holes. Methods proposed in this paper relies on neither the knowledge of localization nor the unit-disk communication model. We also propose a distributed algorithm to discover holes and identify nodes on boundaries. Simulation results show that our method works well for WSNs with many inner holes and irregular outer boundaries.