A Novel Voronoi-Driven Optimization Approach for Point-Based Sensor Network Deployment

Sensor Networks (SNs) are gaining more attention in applications such as urban microclimate monitoring, which is a critical input for building energy simulation. Despite extensive research on SN placement, there remains a shortage of studies on efficient solutions that account for realistic sensing models without oversimplifying the environment or search spaces, making current approaches inadequate for large-scale real-world problems. This study relies on a realistic coverage model for point-based sensor networks (e.g., air temperature sensors) and introduces a novel and efficient heuristic Voronoi-based Optimal Sensor Deployment Algorithm (VOSDA). The algorithm estimates the minimum number of sensors needed and their optimal placement. Its performance is evaluated using the root mean square error (RMSE), calculated via an interpolation process that reconstructs the field from sensor positions. VOSDA leverages Voronoi diagram characteristics to manage the sensor network, assess error distribution, and enhance coverage quality through integrated sensor insertion and movement strategies. Several experiments were conducted to evaluate the effectiveness and efficiency of the proposed approach, comparing the results with the Genetic Algorithm (GA) as a reference by calculating the RMSE using Kriging, Thin Plate Spline, and Inverse Distance Weighting methods. In all cases, VOSDA was first used to estimate the required number of sensors, and RMSE was then calculated for both algorithms at that sensor count. Furthermore, in six out of nine different scenarios conducted across different benchmark heatmaps, VOSDA outperformed GA in achieving lower RMSE values. Both algorithms performed significantly better with Kriging and TPS than with IDW.