Indoor Trajectory Tracking Scheme Based on Delaunay Triangulation and Heuristic Information in Wireless Sensor Networks

Yonghong Tian, Ieee Fellow, Junping Qin, Shiwen Sun, Qingxu Deng, Limin Liu, Yonghong TianSensors 2017 · DOI

TL;DR

This paper introduces TTDH, a novel indoor trajectory tracking scheme for wireless sensor networks (WSNs) that leverages Delaunay triangulation and heuristic information derived from RSSI signals. By combining spatial partitioning with temporal signal analysis, TTDH aims to overcome the inherent uncertainties of RSSI-based localization, achieving an average error distance of less than 1.5 meters without accumulating errors across regions.

What Problem Does This Paper Address?

Accurate indoor localization and trajectory tracking are crucial for various WSN applications, from safety monitoring in mines to indoor navigation. While Received Signal Strength Indicator (RSSI) is a cost-effective method for indoor localization, it suffers from significant uncertainties due to multipath propagation, signal reflections, and device inaccuracies. Existing RSSI-based tracking schemes often rely on continuous localization and data mining, but they struggle to effectively utilize the temporal and spatial characteristics of RSSI signals within indoor environments. This paper addresses the challenge of improving indoor trajectory tracking accuracy and robustness in WSNs by developing a scheme that intelligently integrates heuristic information from RSSI time series with spatial partitioning.

Methods

The proposed TTDH (Trajectory Tracking based on Delaunay Triangulation and Heuristic Information) scheme employs a multi-faceted approach:

  • Delaunay Triangulation: The entire indoor environment is partitioned into triangular regions using Delaunay triangulation based on the positions of reference nodes. These triangles form the spatial units for tracking.
  • Heuristic Information Extraction: The core innovation lies in extracting heuristic information from RSSI time series. This includes:
  • Peak Value Phenomenon on Boundaries: When a moving object crosses a boundary (the common side of two adjacent triangles), the RSSI measurements from the two reference nodes defining that boundary exhibit a peak value. This peak is used to identify boundary crossings.
  • Moving Least Squares (MLS): To smooth out noise and identify the peak value more reliably, the boundary RSSI time series is fitted using an MLS method.
  • Delaunay Triangulation Inside/Outside Decision: An Approximate Point-In-Triangulation (APIT) test is adapted to determine if a node is inside or outside a triangular region. By aggregating results from multiple APIT tests, the accuracy of region detection is enhanced, masking individual errors.
  • Dynamic Time Warping (DTW) Position-Fingerprint Matching: Once a trajectory segment is identified within a triangular region, a DTW algorithm is used to match the observed position fingerprints to candidate trajectories within that region. DTW is chosen for its ability to handle time series of different lengths and its robustness to temporal distortions.
  • Constrained Matching: The DTW matching is constrained by three conditions: the start and end points must correspond to boundary heuristic information, the candidate trajectory must be within the triangular region, and the trajectory must be continuous.

Datasets

The paper describes field experiments conducted in a deep foundation pit of a metro station (50m x 30m). Reference nodes were randomly deployed on the roof, and unknown nodes were attached to workers or transporters. The paper does not mention the use of pre-existing datasets for training or evaluation, relying instead on data collected from these experimental setups.

Key Insights and Ideas

  • Heuristic Information is Key: The paper strongly emphasizes that leveraging heuristic information, particularly the temporal patterns in RSSI signals at boundaries, is crucial for improving indoor trajectory tracking accuracy beyond simple localization.
  • Delaunay Triangulation as a Spatial Framework: Using Delaunay triangulation provides a natural and efficient way to partition the indoor space into manageable regions, simplifying the tracking process.
  • Peak Value as a Boundary Indicator: The observation that RSSI exhibits a peak when crossing a boundary is a clever insight that directly links temporal signal behavior to spatial movement.
  • Aggregation for Robustness: The aggregation of multiple APIT test results is a critical mechanism for overcoming the inherent noise and uncertainty in individual RSSI measurements and single-point localization attempts.
  • DTW for Flexible Matching: The application of DTW allows for flexible matching of observed trajectory segments to pre-defined patterns, accommodating variations in movement speed and timing.

Key Results

Field experiments demonstrated the effectiveness of the TTDH scheme:

  • Average Error Distance: The average error distance of the tracked trajectory was less than 1.5 meters.
  • Error Accumulation: A significant finding is that errors do not accumulate among the triangular regions, leading to a more consistently accurate overall trajectory.
  • Improved Accuracy with Node Density: The average region error percentage decreased with increasing node density. With a node density greater than 5, the error was reduced by 8.5% compared to classical APIT.
  • Improved Accuracy with APIT Tests: Increasing the number of APIT tests within a region also improved accuracy. When the number of tests exceeded 5, the region error percentage fell to 4.5%.
  • Robustness to Noise: The scheme showed good performance even with significant RSSI noise, outperforming RADAR (a common position fingerprinting method) in accuracy.

Limitations and Future Work

  • Node Density Requirement: The TTDH scheme performs best with a relatively high node density (greater than 6) and triangular regions of moderate size.
  • Sharp/Narrow Regions: Detecting trajectories in very sharp or narrow triangular regions can be challenging, though continuity of movement and information from adjacent regions can help correct for this.
  • Real-time Performance with Large Triangles: If Delaunay triangles become too large, real-time performance might degrade due to the scheme's reliance on segmenting trajectories by triangular regions. The authors suggest balancing triangle size and shape.
  • Future Work: The paper implicitly suggests that further optimization of node deployment to ensure balanced triangle sizes and shapes would be beneficial. Exploring adaptive window sizes for the sliding window approach could also be a direction for future research.

Summary updated

BibTeX
@article{fellow2017indoor,
  author = {Yonghong Tian, IEEE Fellow and Junping Qin and Shiwen Sun and Qingxu Deng and Limin Liu and Yonghong Tian},
  title = {{Indoor Trajectory Tracking Scheme Based on Delaunay Triangulation and Heuristic Information in Wireless Sensor Networks}},
  journal = {Sensors},
  year = {2017},
  doi = {10.3390/s17061275},
}
Figure