PRIMAL: Page Rank-Based Indoor Mapping and Localization Using Gene-Sequenced Unlabeled WLAN Received Signal Strength

Mu Zhou, Qiao Zhang, Kunjie Xu, Zengshan Tian, Yanmeng Wang, Wei HeSensors 2015 · DOI

TL;DR

This paper introduces PRIMAL, a novel indoor Simultaneous Localization and Mapping (SLAM) approach that leverages WLAN Received Signal Strength (RSS) without requiring manual labeling or motion sensors. By analyzing human movement patterns and applying gene sequencing to RSS data, PRIMAL constructs a signal graph that is then mapped to a mobility graph using PageRank, achieving accurate indoor localization while significantly reducing the cost and effort of traditional methods.

What Problem Does This Paper Address?

Indoor localization is crucial for various location-based services, but GPS signals are unreliable indoors. While WLAN-based RSS localization is promising due to widespread infrastructure, existing methods like trilateration suffer from signal propagation inaccuracies, and location fingerprinting is labor-intensive and costly due to the need for extensive manual data collection (radio map construction). This paper aims to overcome these limitations by proposing a cost-effective and accurate indoor SLAM system that doesn't rely on pre-collected fingerprints or explicit motion tracking.

Methods

PRIMAL employs a multi-stage approach:

  • Mobility Graph Construction: It uses the Allen logic to model the temporal relationships between observed human movement events (e.g., "walk into," "wait") to create a graph representing connectivity between different areas of interest.
  • Signal Graph Construction: Gene sequencing principles are applied to unlabeled WLAN RSS sequences. These sequences are treated as "genes," and their transitions are analyzed to build a "signal graph" that reflects the relationships between different RSS patterns.
  • Graph Drawing: A graph drawing technique is used to visualize both the mobility and signal graphs, making them more interpretable.
  • PageRank-Based Mapping: The PageRank (PR) algorithm is employed to map the signal graph onto the mobility graph. This step aligns the signal patterns with the physical layout and movement behaviors, enabling localization.
  • Target Localization: Finally, Kullback-Leibler (KL) divergence is used to compare the distribution of newly collected RSS data with the distributions in each area of the mapped mobility graph, identifying the area with the smallest divergence as the target's location.

Datasets

The paper describes experiments conducted in a target environment (layout shown in Figure 1). It mentions collecting 94 WLAN RSS sequences and constructing 4371 scoring matrices. No specific public datasets are mentioned; the data appears to be collected by the authors within their experimental setup.

Key Insights and Ideas

  • Unlabeled Data is Sufficient: The core innovation is demonstrating that accurate indoor localization and mapping can be achieved using unlabeled RSS data, bypassing the significant overhead of traditional fingerprinting.
  • Movement Patterns as a Proxy for Location: By analyzing human movement patterns with Allen logic, the system infers the connectivity and structure of the indoor environment, which is then used to contextualize RSS data.
  • Gene Sequencing for RSS Correlation: Applying gene sequencing concepts to RSS sequences provides a novel way to identify correlations and group similar signal patterns, effectively creating "clusters" of signal behavior.
  • PageRank for Graph Alignment: Using PageRank to map the signal graph to the mobility graph is a clever way to bridge the gap between raw signal data and the physical environment, effectively identifying "hot areas" where people frequently move.
  • Cost Reduction: The entire approach significantly reduces the time and labor costs associated with building and maintaining indoor localization systems.

Key Results

  • The proposed PRIMAL approach achieves satisfactory localization accuracy.
  • For specific areas, correct area localization probabilities approach 100% (Area 1), 85% (Area 2), 64% (Areas 3 & 4), and 80% (Area 6).
  • When localization errors occur, the estimated areas are typically physically adjacent to the correct area, indicating a robust and localized error pattern.
  • The system effectively identifies "hot areas" that are frequently visited by people, which is a valuable byproduct of the mapping process.
  • The method avoids the intensive time and labor costs of conventional location fingerprinting.

Limitations and Future Work

  • Area-Level Localization: The current system provides area-level localization, not precise coordinate-level localization.
  • Parameter Sensitivity: The paper notes that the parameter $\theta$ (probability factor) has a slight impact on the rank of PR values, suggesting that the performance is significantly influenced by the observation of motion patterns.
  • Large-Scale Environments: The authors suggest that exploring people's motion patterns in a large-scale environment is a topic for future work.
  • Coordinate-Level Localization: Locating the target at the coordinate level is also identified as a future research direction.

Summary updated

Abstract

Due to the wide deployment of wireless local area networks (WLAN), received signal strength (RSS)-based indoor WLAN localization has attracted considerable attention in both academia and industry. In this paper, we propose a novel page rank-based indoor mapping and localization (PRIMAL) by using the gene-sequenced unlabeled WLAN RSS for simultaneous localization and mapping (SLAM). Specifically, first of all, based on the observation of the motion patterns of the people in the target environment, we use the Allen logic to construct the mobility graph to characterize the connectivity among different areas of interest. Second, the concept of gene sequencing is utilized to assemble the sporadically-collected RSS sequences into a signal graph based on the transition relations among different RSS sequences. Third, we apply the graph drawing approach to exhibit both the mobility graph and signal graph in a more readable manner. Finally, the page rank (PR) algorithm is proposed to construct the mapping from the signal graph into the mobility graph. The experimental results show that the proposed approach achieves satisfactory localization accuracy and meanwhile avoids the intensive time and labor cost involved in the conventional location fingerprinting-based indoor WLAN localization.
BibTeX
@inproceedings{zhou2015primal,
  author = {Mu Zhou and Qiao Zhang and Kunjie Xu and Zengshan Tian and Yanmeng Wang and Wei He},
  title = {{PRIMAL: Page Rank-Based Indoor Mapping and Localization Using Gene-Sequenced Unlabeled WLAN Received Signal Strength}},
  booktitle = {Sensors},
  year = {2015},
  doi = {10.3390/s151024791},
}
Figure