OPEN Wireless localization with diffusion maps

The Internet of Things (IoT) envisions a vast network of interconnected devices and sensors for various applications. Wireless sensor networks (WSNs) are a crucial component, requiring accurate location identification for data analysis. While GPS is an option, its cost, power consumption, and limitations in indoor/underground environments necessitate alternative methods. Existing RF-based localization techniques (database, range-based, range-free, angle-based) suffer from errors due to noise, path loss, shadowing, and multipath fading, often requiring empirical model retuning. This paper addresses these limitations by focusing on the WLMP, where sensor nodes must be matched to known positions. The challenge lies in effectively using noisy Received Signal Strength Indicator (RSSI) measurements to make accurate assignments. This problem arises in various scenarios, such as installing devices in specific locations (e.g., smart lights) or tracking air-dropped sensors after a disaster. Previous work using spectral embedding methods requires knowledge of several node locations, limiting its practicality. This research proposes a diffusion map-based solution to overcome these limitations.

Existing literature on wireless localization encompasses several methods: database methods rely on comparing signal features to a pre-existing database; range-based methods estimate distances from known anchors to locate the target device; range-free methods leverage network topology and hop counts; and angle-based methods utilize angle of arrival measurements. Each method faces challenges related to noise and environmental factors. While Keller and Gur proposed using spectral embedding for localization, it requires knowing the locations of multiple nodes. The current work addresses the WLMP, a specific incarnation of the localization problem, focusing on the efficient matching of sensor nodes to known positions using only RSSI measurements and position coordinates.

The proposed method uses diffusion maps to address the WLMP. This approach involves three main steps: (1) mapping the position coordinates and noisy sensor node coordinates into a new space using diffusion maps, (2) projecting the data onto the first few coordinates to approximate the new coordinates, and (3) performing bipartite matching in the new space using the Hungarian algorithm. The process begins by constructing a distance matrix (D) from the RSSI measurements (R) using a propagation model (e.g., inverse square law or log-distance path loss model). A similarity matrix (C) is then created using a Gaussian kernel. The row-normalized Laplacian matrix (L) is constructed from the similarity matrix. The eigenvectors of L, corresponding to the smallest non-zero eigenvalues, are used as coordinates in the new space. The same process is applied to the known positions to obtain corresponding coordinates. The matching algorithm finds the assignment that minimizes the sum of Euclidean distances between node and position coordinates in the new space. The Hungarian algorithm is employed for this efficient minimum weight matching. In cases without anchor nodes, multiple matching attempts with different coordinate sign configurations are performed, selecting the best match based on the lowest assignment cost. The algorithm's computational complexity is primarily determined by the Hungarian algorithm, making it efficient for large systems.

The proposed method demonstrates high accuracy in various scenarios. In a realistic factory floor simulation with 58 positions and using the inverse square law propagation model, near-perfect matching was achieved at signal-to-noise ratios (SNRs) greater than 5. Experiments with different layouts (grid, random 2D, uniform biaxial, random biaxial) showed consistently good accuracy at moderate SNRs, even with intentionally difficult configurations. Analysis of a strip layout highlighted the potential influence of harmonic eigenvectors; using higher-order eigenvectors proved necessary for accurate matching in this case. However, small shifts in the layout mitigated this issue, demonstrating the practical robustness of the method. Three-dimensional simulations (grid and random layouts) also showed accurate results at low SNRs. Tests using a log-distance path loss model with different node configurations (hexagonal lattice, Koch curve) further confirmed the method's effectiveness. The accuracy in these simulations was affected by the range of length scales in the node layout, with the more uniform lattice layout showing higher accuracy.

The results demonstrate the effectiveness of the proposed diffusion map-based method for solving the WLMP. The method's robustness to noise and its low computational complexity make it suitable for practical applications. By embedding the data into a new coordinate space, the method successfully addresses the challenges associated with using RSSI measurements and different coordinate systems. The use of the Hungarian algorithm for efficient bipartite matching further contributes to its practicality. The observed accuracy surpasses that of brute-force or maximum likelihood methods, which are often computationally expensive. The findings address the limitations of existing methods by providing a computationally efficient and accurate solution to the WLMP, especially beneficial in scenarios with large numbers of sensors.

This paper presents a novel and efficient solution to the Wireless Localization Matching Problem using diffusion maps. The method's robustness to noise, low computational complexity, and high accuracy make it a promising approach for diverse applications. Future research could investigate improved propagation models and incorporate thresholding techniques to further enhance performance. Physical experiments would validate the numerical findings and potentially reveal further implementation details. The proposed approach holds significant potential for advancing the field of wireless localization in the context of the Internet of Things.

While the method demonstrates high accuracy in various scenarios, certain limitations exist. The accuracy is influenced by the SNR; lower SNRs can lead to reduced accuracy, particularly in layouts with closely spaced positions. Also, the choice of appropriate eigenvectors for the matching needs careful consideration, requiring a preprocessing step to identify suitable eigenvectors. This preprocessing step, however, can be easily integrated into software. The performance is also sensitive to the presence of harmonic eigenvectors in specific layouts but is mitigated by small positional shifts.