Fractured Voronoi segments: Topology discovery for wireless sensor networks

Wireless sensor networks are deployed in various territories executing different tasks. In many applications, it is very useful to understand their topological characteristics. This paper studies the problem of discovering the topological properties of a sensor network such as boundaries and holes. Previous works have revealed that, such a problem could be addressed with knowledge of node locations, measures of inter-distances, or ideal assumptions of particular communication models, e.g., unit disk graph model. In this work, however, we explore the possibility of discovering sensor network topology merely with connectivity information. We propose a virtual Voronoi diagram approach to detect both the inner and outer boundaries of a sensor network. We do not rely on any communication models, yet any geometric knowledge of the network. Compared with previous connectivity based approaches, we further release the assumption of regular wireless signals. Our approach works even for anisotropic network with irregular wireless links. We design our approach to be light-weight, preventing frequent global operations that have been intensively used in previous designs. We conduct intensive simulations in networks of different topologies with multiple holes, with different node degrees and densities, and containing various signal irregularities. The results validate the effectiveness and efficiency of our approach.