Topological Hole Detection in Sensor Networks with Cooperative Neighbors

In a wireless sensor network, the regions in which a large percentage of sensor nodes are not available may form holes in the network. In holes, sensor nodes may be depleted or not dense enough to communicate with others. So those holes may degrade some applications¿ performances in sensor networks. In this paper, we study the problem of detecting topological holes in sensor networks with no localization information in any node. We present a distributed cooperative scheme which is only based on the communication topology graph. To identify holes, each node only needs to exchange information with its 1-hop and 2-hop neighbors. With the cooperation of its 2-hop neighbors, each node could independently decide whether it is on the boundary of a hole. Experimental results demonstrate that our algorithm could indeed capture the characteristics of those boundary nodes and describe those holes in sensor networks of moderate node densities.