RE3: Overcoming Device Heterogeneity in Crowdsourced Indoor Localization

TL;DR

The core challenge of Wi-Fi fingerprinting is that different phones "hear" the same signal differently. This paper presents RE3 (REfined RElative RElationship), an algorithm that ignores absolute signal strength in favor of the relative relationship between Access Points (APs). By focusing on the "shape" of the signal environment, RE3 reduces device-induced localization errors from 5 meters down to approximately 1 meter.

Context & Motivation: The Crowdsourcing Dilemma

Fingerprint-based localization is the standard for GPS-denied indoor environments. However, building a fingerprint database is labor-intensive. While Crowdsourcing (collecting data from regular users) solves the labor issue, it introduces Device Heterogeneity.

Different Wi-Fi chipsets (e.g., in a Nexus 5 vs. a Xiaomi 2) report different absolute RSSI values even at the exact same spot. Existing solutions like linear transformation or probability distribution estimation often fail because the "shift" in RSSI is not constant across all Access Points. The authors observed that while the values change, the relative order—which AP is stronger than another—remains remarkably consistent.

Methodology: The RE3 Framework

The RE3 approach moves away from Euclidean distance and embraces a quantitative relative similarity.

1. Relative Structure Definition

For any location, the algorithm identifies an RSSIAnc (Anchor Node) and compares it to other APs to form an RSSILowVec. A threshold $\delta$ is used to filter out APs with signal strengths too close to each other, ensuring the relative relationship is robust against noise.

2. Quantitative Similarity

Instead of a simple "yes/no" rank comparison, RE3 calculates a "shape descriptor" ($\Delta$). It compares the difference between an anchor and its neighbors across two different fingerprints. This allows the system to use a continuous similarity metric, making it compatible with sophisticated clustering algorithms.

Figure 1: The RE3 workflow integrated with clustering-based localization.

3. Clustering via MMC-KNN

The authors combine RE3 with Affinity Propagation Clustering. By grouping fingerprints into logical clusters offline, the online phase only needs to match the user's scan against the most likely clusters (MMC), followed by a K-Nearest Neighbor (KNN) refinement.

Experimental Results & Validation

Testing was conducted across 200 $m^2$ at Shanghai Jiao Tong University using five disparate smartphones (Nexus S, 4, 5, 7, and Xiaomi 2).

Performance Gains

The most striking result is the stability across devices. In traditional models, a database built with a Nexus S worked poorly for a Nexus 4 user (Error > 6m). Using RE3, the "deterioration gap" between different devices was slashed to nearly negligible levels.

Figure 2: The model used to compare clustering results across diverse devices.

Critical Insight: Why Relative Beats Absolute

The "magic" of RE3 lies in its Inductive Bias. It assumes that hardware gain is a nuisance variable, while the spatial geometry of APs relative to the receiver is the ground truth. By quantifying the "shape" of the signal drop-off ($\Delta$), RE3 preserves more information than a simple sort-index (rank) while discarding the hardware-dependent bias of absolute RSSI.

Conclusion

RE3 provides a practical, mathematically sound bridge between high-quality expert-led surveys and noisy user-contributed crowdsourcing. While there are newer deep learning approaches today, the physical intuition of relative signal relationships remains a cornerstone for robust wireless sensing.

Future Directions: Extending this relative logic to handle dynamic environments (where APs are moved or replaced) would be the next logical step for a truly maintenance-free indoor GPS.