Neighborhood-based distributed topological hole detection algorithm in sensor networks

Topological holes in sensor networks usually indicate the region where nodes are depleted or not dense enough due to kinds of reasons. In this paper, we study the problem of detecting topological holes in wireless sensor networks. Those sensor nodes have no geographic location information and have a limited communication range. We present a novel distributed topological holes detection algorithm which is based purely on the logical communication topology graph. By exchanging information with its 1-hop and 2-hop neighbors, each node can independently decide whether it is on the boundary of a hole. Those boundary sensor nodes together could describe the region of the topological hole. Experimental results show that our distributed algorithm is effective in exploiting those characteristics of those nodes on the boundaries of holes. And thus it could identify those holes in sensor networks of moderate node densities.