Local Voronoi Computation and Sweep Line Intersection for Efficient Voronoi-Based Grouping Test Localization in Wireless Sensor Networks

Abstract

Node localization is a fundamental service in wireless sensor networks (WSNs), and range-free schemes such as the Voronoi diagram-based grouping test localization (VTL) achieve good accuracy without distance measurements. However, VTL repeatedly constructs Voronoi diagrams over all anchor nodes of each group and resolves the intersection of positive regions by an exhaustive grid scan, which limits its scalability. This paper proposes and evaluates two optimizations: (1) a local Voronoi computation that restricts the computation to the k anchors nearest to the strongest-signal anchor (including that anchor itself), and (2) an exact sweep line algorithm that replaces the grid scan in the intersection phase. Both were evaluated in a purpose-built, reproducible simulator through 5184 primary and 464 supplementary simulations spanning 60–1000 nodes, two deployment areas (200 m and 400 m squares) and k = 6–20, with paired Wilcoxon signed-rank tests. The local computation reduced the Voronoi-phase time by 69–83%, with the accuracy penalty falling below 2% for k ≥ 10 on average across network sizes, while the percentage of localized nodes remained unchanged. The sweep line algorithm reduced the intersection-phase time by 7.7–18.1% while producing identical localization results. Combined, the two optimizations reduced the total execution time by 37–61% (up to 4.7-fold at 1000 nodes). The conclusions are robust across anchor densities of 20–70%, ten independent seeds, and log-normal shadowing noise in the anchor selection. We recommend k = 10–12 as the default operating range, whereas k = 6 degrades both accuracy and overall speed.