C-VoNNI: a precise fingerprint construction for indoor positioning systems using natural neighbor methods with clustering-based Voronoi diagrams

Indoor positioning is crucial for everyday life, and received signal strength-based fingerprint localization is the most effective method. However, updating the fingerprint database is laborious, as changes in indoor layout would render the initial radio map outdated. To address this issue, we propose a precise radio map construction method by clustering and interpolating virtual fingerprints. The affinity propagation clustering algorithm and Voronoi diagram are used to group fingerprints with similar characteristics, mitigating the negative effects of multipath fading and shadowing caused by changes in the indoor layout. After generating synthetic reference points using the gradient extrapolation method to expand the convex hull, natural neighbor interpolation can construct accurate virtual fingerprints. Experimental results show that our proposed method outperformed both inverse distance weighting and Kriging interpolation by up to 33% in localization accuracy across diverse environments. This approach enables efficient radio map generation with comparable localization accuracy to the original radio map without extensive site surveys.