Voronoi-based relay placement scheme for wireless sensor networks

Energy consumption is a crucially important issue in battery-driven wireless sensor networks (WSNs). In most sensor networks, the sensors near the data collector (i.e. the sink) become drained more quickly than those elsewhere in the network since they are required to relay all of the data collected in the network to the sink. Therefore more balanced data paths to the sink should be established in order to extend the lifetime of the sensor network. Accordingly, a novel relay deployment scheme for WSNs based on the Voronoi diagram is proposed. The proposed scheme is applicable to both two-dimensional and three-dimensional network topologies and establishes effective routing paths that balance the traffic load within the sensor network and alleviate the burden on the sensors around the sink. Simulation results indicate that the number of relays deployed in the proposed scheme is similar to that deployed in the predetermined location scheme and is significantly less than that deployed in the minimum set cover scheme. Furthermore, the lifetime of the sensor network containing relay nodes deployed using the current scheme is longer than that achieved using either the predetermined location scheme or the minimum set cover scheme.