A Robust Wireless Sensor Network Localization Algorithm in Mixed LOS/NLOS Scenario

Bing Li, Wei Cui, Bin WangSensors 2015 · OpenReview

TL;DR

This paper introduces GMDS, a novel algorithm for robust wireless sensor network localization in indoor environments with mixed Line-of-Sight (LOS) and Non-Line-of-Sight (NLOS) conditions. By employing a Gaussian Mixed Model (GMM) to estimate accurate RSSI values and then using non-metric Multidimensional Scaling (MDS) for coordinate estimation, GMDS achieves higher accuracy and reduces reliance on prior knowledge of propagation models.

What Problem Does This Paper Address?

Accurate localization is crucial for many applications of Wireless Sensor Networks (WSNs). In indoor environments, however, radio signals often encounter obstacles, leading to Non-Line-of-Sight (NLOS) conditions. NLOS propagation introduces significant errors in Received Signal Strength Indication (RSSI) measurements, which are commonly used for localization due to their ease of implementation. These errors lead to unreliable distance estimations and, consequently, low localization accuracy. Existing methods often struggle with NLOS conditions, requiring complex prior knowledge about signal propagation models or yielding inaccurate results. This paper aims to address this challenge by developing a robust and accurate localization algorithm that can effectively handle mixed LOS/NLOS scenarios without requiring extensive prior information.

Methods

The proposed GMDS algorithm comprises three main steps:

  1. RSSI Estimation using Gaussian Mixed Model (GMM): The core of the approach is to refine raw RSSI measurements, which are prone to NLOS errors. The authors model RSSI measurements in both LOS and NLOS scenarios using a GMM. This statistical model allows for a more accurate estimation of the true RSSI values by effectively mitigating the fluctuations and biases introduced by NLOS conditions. The GMM parameters (weights, means, and covariances) are estimated using the Expectation-Maximization (EM) algorithm, with K-means clustering and Particle Swarm Optimization (PSO) used for initialization and optimization.
  2. Dissimilarity Matrix Construction and Non-metric MDS: Instead of converting RSSI to distance (which can introduce further errors), GMDS directly uses the GMM-estimated RSSI values to construct a dissimilarity matrix. The sign of the RSSI values is inverted to create this matrix, as a smaller distance generally corresponds to a larger RSSI. This dissimilarity matrix is then fed into a non-metric Multidimensional Scaling (MDS) algorithm. Non-metric MDS is chosen because it doesn't require a strict quantitative relationship between dissimilarity and distance, making it suitable for the noisy RSSI data. It aims to preserve the monotonic relationship between the estimated dissimilarities and the derived relative coordinates.
  3. Coordinate Transformation: Once the relative coordinates of the nodes are obtained through MDS, a plane four-parameter coordinate transformation model is used to convert these relative coordinates into absolute coordinates, leveraging the known positions of anchor nodes.

Datasets

The paper describes an experimental setup for evaluation. The experiments were conducted in a 10m x 6m indoor environment at Northeastern University. Five anchor nodes (AN1-AN5) were deployed with known coordinates. A mobile iRobot served as the target node, following a predefined track. RSSI data was collected at various points along this track. The authors simulated NLOS errors by manually introducing obstructions during data collection. No specific public datasets were used; rather, a custom experimental setup and data collection were performed.

Key Insights and Ideas

  • Direct RSSI Utilization: The most significant insight is the decision to directly use estimated RSSI values for localization via MDS, bypassing the error-prone step of converting RSSI to distance using propagation models. This simplifies the process and avoids introducing additional inaccuracies.
  • GMM for NLOS Error Mitigation: Employing a GMM to model and estimate RSSI is a powerful way to handle the inherent noise and bias introduced by NLOS conditions. It allows for a more robust estimation of the underlying signal strength.
  • Non-metric MDS Suitability: The choice of non-metric MDS is crucial. It relaxes the strict quantitative requirements of metric MDS, making it more resilient to the noisy and non-linearly related RSSI measurements, and focusing on preserving the order of relationships.
  • No Prior Knowledge Required: A key advantage highlighted is that the algorithm does not require prior knowledge of specific propagation model parameters, making it more adaptable to different indoor environments.

Key Results

The experimental verification demonstrates the effectiveness of the GMDS algorithm:

  • Reduced NLOS Error: GMM estimation effectively reduces the error in measured RSSI values, leading to more accurate distance estimations compared to using raw average RSSI.
  • Higher Accuracy: GMDS consistently outperforms other compared algorithms (Least Square, Rwgh, and CMDS) in terms of localization error, especially in NLOS scenarios.
  • Scalability: The algorithm shows good performance even when extended from single NLOS to multiple NLOS conditions.
  • Quantitative Performance: Table 2 shows average localization errors (in meters) for different numbers of NLOS nodes:
  • Nnlos = 1: GMDS (1.2057m) vs. CMDS (2.6223m), LS (3.2646m), Rwgh (2.7367m).
  • Nnlos = 2: GMDS (1.3028m) vs. CMDS (2.9836m), LS (3.4515m), Rwgh (2.6401m).
  • Nnlos = 3: GMDS (1.3111m) vs. CMDS (3.4741m), LS (3.7053m), Rwgh (2.8519m). GMDS consistently achieves the lowest average error across these scenarios.

Limitations and Future Work

  • Computational Complexity: While MDS reduces computation compared to some methods, the GMM parameter estimation (EM algorithm) can still be computationally intensive, especially with a large number of nodes or complex GMM configurations.
  • Initialization Sensitivity: The EM algorithm's performance can be sensitive to initialization. The paper addresses this with K-means and PSO, but further research into more robust initialization strategies could be beneficial.
  • Extensibility to 3D: The paper mentions that the algorithm can be extended to 3D by simply setting r=3 in the MDS step, but the experimental validation is limited to 2D. Future work could explore and validate its performance in 3D environments.
  • Dynamic Environments: While the algorithm aims to be robust, the performance in highly dynamic indoor environments with rapidly changing propagation conditions might require further investigation.

Summary updated

Abstract

Localization algorithms based on received signal strength indication (RSSI) are widely used in the field of target localization due to its advantages of convenient application and independent from hardware devices. Unfortunately, the RSSI values are susceptible to fluctuate under the influence of non-line-of-sight (NLOS) in indoor space. Existing algorithms often produce unreliable estimated distances, leading to low accuracy and low effectiveness in indoor target localization. Moreover, these approaches require extra prior knowledge about the propagation model. As such, we focus on the problem of localization in mixed LOS/NLOS scenario and propose a novel localization algorithm: Gaussian mixed model based non-metric Multidimensional (GMDS). In GMDS, the RSSI is estimated using a Gaussian mixed model (GMM). The dissimilarity matrix is built to generate relative coordinates of nodes by a multi-dimensional scaling (MDS) approach. Finally, based on the anchor nodes’ actual coordinates and target’s relative coordinates, the target’s actual coordinates can be computed via coordinate transformation. Our algorithm could perform localization estimation well without being provided with prior knowledge. The experimental verification shows that GMDS effectively reduces NLOS error and is of higher accuracy in indoor mixed LOS/NLOS localization and still remains effective when we extend single NLOS to multiple NLOS.
BibTeX
@inproceedings{li2015robust,
  author = {Bing Li and Wei Cui and Bin Wang},
  title = {{A Robust Wireless Sensor Network Localization Algorithm in Mixed LOS/NLOS Scenario}},
  booktitle = {Sensors},
  year = {2015},
  url = {https://openreview.net/forum?id=zCFY0_0S8N},
}
Figure