Voronoi Tessellation Based Interpolation Method for Wi-Fi Radio Map Construction

CTN Issue: April 2012 IEEE Communications Letters

With the proliferation of smartphones and Wi-Fi hot spots, localization techiques based on radio fingerprinting is drawing great attention these days. Radio fingerprinting localization can achieve much higher accuracy than triangulation- or proximity-based localization, provided that an accurate radio map is available. Construction of such a radio map (known as calibration) usually requires tremendous time and efforts and new innovative ways to reduce these efforts are widely being pursued.

One way to drastically reduce such efforts is to deploy a large number of reference measurement points at which fingerprints are collected along with spatial interpolation techniques. Good spatial interpolation techniques that could generate a radio map of interpolated fingerprints from sparsely collected fingerprints, would reduce the number of reference points necessary to obtain a certain required accuracy.

A drawback of many existing interpolation methods is that the generated, interpolated fingerprints for a point are not always the same or even similar to those manually collected at that point. The structure of environment should be considered along with Wi-Fi signal fading patterns for the interpolation techniques to generate more accurate radio fingerprints. This paper proposes a new method for interpolating scattered data based on higher-order Voronoi tessellation.

The method improves the conventional methods in two ways. First, unlike other conventional methods that use Gaussian, linear, or spline models, it adopts the Log-Distance Path Loss (LDPL) signal propagation model, which is known to conform well with Wi-Fi signal fading patterns. Second, it further refines the propagation model by estimating signal fading parameters for each cell of a target area tessellated by a higher-order Voronoi diagram. As a result, it can take into account signal fading caused by walls and obstacles more accurately.

According to the experiments conducted in two buildings (COEX in Seoul and the KAIST Library in Daejeon) the proposed method improves accuracy by around 30% compared to other established interpolation methods such as Radial Basis Function (RBF) and Inverse Distance Weighting (IDW). This implies that the proposed method can drastically reduce the calibration efforts for fingerprint based localization without significant deterioration of its accuracy.

Title and author(s) of the original paper in IEEE Xplore:
Title: Voronoi Tessellation Based Interpolation Method for Wi-Fi Radio Map Construction
Author: Minkyu Lee and Dongsoo Han
This paper appears in: IEEE Communications Letters
Issue Date: March 2012

Leave a comment

Statements and opinions given in a work published by the IEEE or the IEEE Communications Society are the expressions of the author(s). Responsibility for the content of published articles rests upon the authors(s), not IEEE nor the IEEE Communications Society.