Tack: Crowdsourcing the "Ephemeral" Indoor Map with BLE and CRFs

TL;DR

Indoor localization at temporary events (like conferences) shouldn't require weeks of site surveying. Tack is a mobile framework that achieves 2-4m accuracy by turning every participant's smartphone into a "virtual beacon." By combining sparse physical beacons with a sophisticated Conditional Random Field (CRF) model, it corrects past trajectories and propagates location confidence across a moving crowd.

The Problem: The High Cost of "Knowing Where You Are"

Current indoor positioning systems face a binary struggle:

1. High-Precision/High-Cost: Systems requiring antenna arrays or proprietary hardware.
2. Fingerprinting-Heavy: Systems like WiFi-based RSSI mapping that require "war-driving" the entire venue before the event.

For a 3-day conference, the ROI on manual fingerprinting is near zero. Consequently, event organizers need a system that is ephemeral (works only for the duration) and contextual (uses available data from the crowd).

Methodology: From Particles to Global Inference

Tack's architecture moves through three layers of probabilistic sophistication to solve the "drift" problem inherent in smartphone sensors.

1. The Local View (Particle Filters)

Each phone runs an Augmented Particle Filter. It samples possible locations based on:

• Dead Reckoning: Steps and headings from the accelerometer and magnetometer.
• Beacon Correction: Drastic weight adjustments when a user passes a fixed $10 iBeacon.

2. The Social View (Virtual Beacons)

Unlike traditional systems, Tack uses BLE Dual Mode. Your phone broadcasts as a "virtual beacon" while simultaneously scanning for others. When User A (who just passed a beacon) meets User B (who is lost), the encounter acts as a "moving landmark" to reset User B’s error.

3. The Global & Spatio-Temporal View (HMM & CRF)

The true innovation lies in the Conditional Random Field (CRF) representation. Unlike a standard Markov model that only looks at the "now," the CRF "unrolls" the trajectory over time.

Figure: The CRF Model. Note how state nodes $Z$ (positions) are linked across time and across users via observation nodes $D$.

This allows for Backward Propagation: If you reach a beacon at $t=10$, Tack can look back at your path at $t=5$ and say, "Wait, if you're here now, your estimated position 5 minutes ago must have been wrong," and correct it—as well as the positions of everyone you bumped into along the way.

Experiments: Real-World Latency & Accuracy

The authors tested Tack on iOS devices in a large venue.

• Accuracy: Achieved 2-4 meters consistently.
• Efficiency: By using the iOS Accelerate Framework (SIMD vectorization), they processed 1,000+ particle interactions in under 1ms, preventing the computation from draining the battery.
• The "Cold Start": Even if no one starts with a known position, the global view allows the system to converge much faster than local filters.

Figure: Comparative error reduction. The Global View (CRF/HMM) significantly outperforms local resampling.

Critical Insight: Why it Works

The "Secret Sauce" is the Confidence Feature. Each user maintains a "weight account." Passing a fixed beacon refills the account; every step taken away from it slowly depletes it. In the CRF, "rich" nodes (high confidence) influence "poor" nodes (high drift), creating a reliable flow of spatial information through the crowd.

Conclusion & Future Outlook

Tack proves that the "noise" of BLE and PDR isn't a dealbreaker if you have enough participants. While it currently suffers at very high crowd densities (45+ users) due to error propagation, it offers a blueprint for self-deploying navigation. In the future, this could be extended to large-scale disaster response or smart city environments where fixed infrastructure has been compromised.

Takeaway for Devs: If you're building for events, stop trying to map the building. Map the people.