Topological Hole Detection in Wireless Sensor Networks and its Applications

Stefan Funke

The identification of holes in a wireless sensor network is of primary interest since the breakdown of sensor nodes in a larger area often indicates one of the special events to be monitored by the network in the first place (e.g. outbreak of a fire, destruction by an earthquakes etc.). This task of identifying holes is especially challenging since typical wireless sensor networks consist of lightweight, low-capability nodes that are unaware of their geographic location. But there is also a secondary interest in detecting holes in a network: recently routing schemes have been proposed that do not assume knowledge of the geographic location of the network nodes but rather perform routing decisions based on the \emph{topology} of the communication graph. Holes are salient features of the topology of a communication graph. In the first part of this paper we propose a simple distributed procedure to identify nodes near the boundary of the sensor field as well as near hole boundaries. Our \emph{hole detection} algorithm is based purely on the topology of the communication graph, i.e. the only information available is which nodes can communicate with each other. In the second part of this paper we illustrate the secondary interest of our hole detection procedure using several examples.

Proc. of 3rd ACM/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC) 2005, Cologne