🔢 mathematics

Survey-Free Radio Map Construction via HMM-Based Coarse-to-Fine Inference

This paper proposes a survey-free radio map construction method that utilizes a Hidden Markov Model-based Coarse-to-Fine Inference (HCFI) framework to align unlabeled RSS sequences with known indoor layouts, achieving a mean absolute error of 8.96 dB and enabling accurate KNN localization with an average error of 3.33 meters.

Original authors: Zheng Xing, Weibing Zhao, Guanghui Zhang, Guangjin Pan, Xuhui Zhang, Jinke Ren, Henk Wymeersch, Yuan Wu, Shuguang Cui

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zheng Xing, Weibing Zhao, Guanghui Zhang, Guangjin Pan, Xuhui Zhang, Jinke Ren, Henk Wymeersch, Yuan Wu, Shuguang Cui

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to draw a detailed map of a new office building, but you have a major problem: you don't know where you are when you take your measurements.

Usually, to build a "radio map" (a guide that helps phones find their way using Wi-Fi signals), someone has to walk around with a clipboard, stopping at specific spots to write down the Wi-Fi signal strength and the exact address of that spot. This is like a surveyor walking a construction site, measuring every inch. It's slow, expensive, and boring.

This paper proposes a clever new way to build that map without ever stopping to write down a location.

The Core Idea: The "Blind Hiker" Analogy

Imagine a group of blind hikers walking through a large, multi-room house. They can't see the rooms, and they don't know their exact GPS coordinates. However, they are carrying radios that pick up signals from Wi-Fi routers (Access Points) placed in different rooms.

The Old Way: A guide walks ahead, marking "Room A, 5 steps from the door" on a map.
The New Way (This Paper): The hikers just walk naturally down the hallways. They record a long list of Wi-Fi signal strengths as they move. They don't know where they are, but they know the order in which they passed things.

The researchers' goal is to take that long, confusing list of signal numbers and figure out: "Ah, this chunk of signals must be the kitchen, and that chunk must be the bedroom," and then guess exactly where in the kitchen they were standing.

The Problem: The Signal is Noisy

Wi-Fi signals are messy. Walls, people, and furniture bounce signals around, making them fluctuate wildly. It's like trying to recognize a song by listening to a radio that is full of static and changing stations. If you just look at the static, you can't tell which room you are in.

The Solution: The "Coarse-to-Fine" Detective

The authors created a system called HCFI (Hidden Markov Model-based Coarse-to-Fine Inference). Think of it as a two-step detective process:

Step 1: The "Coarse" Guess (Grouping the Rooms)

First, the system looks at the long walk and tries to group the signals into "chunks" that belong to different physical areas (like "Corridor," "Office 1," "Office 2").

The Trick: They use a mathematical tool called a Hidden Markov Model (HMM). Imagine this as a smart guesser that knows people usually walk in one direction down a hallway and don't instantly teleport back to the start.
The "RNN" Helper: To make sure the signals aren't just random noise, they use a type of AI (a Recurrent Neural Network) that acts like a "sequence checker." It asks, "Does this pattern of signals make sense if I'm walking forward in time?" This helps smooth out the static and correctly identify which "room" the hiker is in, even without knowing the exact address.

Step 2: The "Fine" Guess (Pinpointing the Spot)

Once the system knows, "Okay, this 5-minute chunk of data was in the Kitchen," it zooms in.

Now that it knows the general area, it uses the laws of physics (how Wi-Fi signals get weaker as you get farther away) to guess the exact coordinates of the hiker within that kitchen.
It treats the hiker's movement like a smooth path, ensuring they didn't suddenly jump 10 meters in one second. It iterates back and forth, refining the map until the signals and the guessed locations match up perfectly.

The Results: How Good Was It?

The researchers tested this in a real office building with 27 Wi-Fi routers and 4 people walking around randomly.

The Map: They built a radio map without a single manual survey.
The Accuracy:
- The map they built had an average error of about 9 dB (a measure of signal strength accuracy).
- When they used this map to locate people, the average error was about 3.33 meters (roughly 11 feet).
The Comparison: This is almost as good as maps built by teams of people walking around with expensive, calibrated sensors (which usually get about 2.24 meters error), but it required zero manual labor and no extra hardware like accelerometers or gyroscopes.

Why This Matters

The paper claims this is a "survey-free" solution. It proves that you don't need a human surveyor to walk every inch of a building to make a Wi-Fi map. If you have a floor plan and some Wi-Fi routers, you can just let people walk through naturally, record their Wi-Fi signals, and let this math-heavy "detective" figure out the rest.

In short: It turns a chaotic, noisy walk through a building into a precise map, using only the Wi-Fi signals and the logic of how people naturally move, saving time and money.

Technical Summary: Survey-Free Radio Map Construction via HMM-Based Coarse-to-Fine Inference

Problem Statement
Traditional radio map construction for indoor localization relies heavily on labor-intensive manual site surveys to collect Received Signal Strength (RSS) measurements at precisely labeled Reference Positions (RPs). This process is time-consuming, costly, and requires frequent recalibration due to environmental changes. While crowdsourcing approaches utilizing Inertial Measurement Units (IMUs) have been proposed to reduce manual effort, they introduce significant limitations: reliance on client-side hardware (smartphone IMUs) which suffer from noise and drift, and potential permission barriers to accessing sensor data. Furthermore, existing unsupervised methods struggle to map noisy RSS data to physical regions due to multipath effects, and propagation-based tracking models often fail without ground-truth coordinates. The core challenge addressed is constructing an accurate radio map and recovering user trajectories using only unlabeled RSS sequences, without manual surveys or auxiliary inertial sensors.

Methodology: HMM-Based Coarse-to-Fine Inference (HCFI)
The authors propose the HCFI framework, designed for corridor-guided environments with a dominant unidirectional pedestrian flow. The method operates in two distinct stages:

Coarse Level: Region Label Inference
- Objective: Partition unlabeled RSS sequences into distinct physical regions and align them with the known floor plan.
- Mechanism: The authors employ a Hidden Markov Model (HMM) where the hidden states are region visit sequences and residence times.
- Observation Likelihood: To handle RSS fluctuations and device heterogeneity, raw RSS data is transformed via a Recurrent Neural Network (RNN). A subspace model (Probabilistic PCA) is applied to these embeddings to capture inter-region differences while suppressing noise.
- Priors: The model incorporates a Poisson distribution for residence duration and a transition prior that enforces a unidirectional flow (users do not revisit regions in a single sequence), allowing for occasional region skipping.
- Optimization: A Generalized Expectation-Maximization (EM) framework is used. The E-step utilizes Viterbi decoding to infer region labels. The M-step updates RNN parameters via a self-supervised sequence order verification task (distinguishing chronological from shuffled sequences), updates residence time statistics, and refines subspace parameters.
- Alignment: Virtual clusters generated by the EM process are mapped to physical regions on the floor plan using a bipartite matching algorithm (Hungarian algorithm) based on signal-strength-weighted centroids and known Access Point (AP) locations.
Fine Level: Location Label Inference
- Objective: Estimate precise 2D user coordinates and region-specific propagation parameters within the inferred regions.
- Mechanism: This stage formulates the problem as a sequential Maximum A Posteriori (MAP) estimation. It jointly optimizes user trajectories and region-specific log-distance path loss parameters ( $\alpha, \beta, \sigma$ ).
- Constraints: The search space is strictly bounded by the physical boundaries of the regions inferred in the coarse stage. A spatio-temporal mobility model (Gaussian transition probability) enforces kinematic feasibility (walking speed limits).
- Optimization: An alternating optimization algorithm is employed. Propagation parameters are updated via closed-form least-squares fitting. User trajectories are recovered using a customized Genetic Algorithm (GA) that searches within the constrained region boundaries, balancing RSS likelihood and mobility priors.

Key Contributions

Survey-Free Framework: Introduction of a fully unsupervised, IMU-independent framework for radio map construction using only unlabeled RSS measurements in corridor-guided environments.
HCFI Architecture: Development of a two-stage inference method that combines HMM-based region clustering with constrained trajectory recovery, effectively bridging the gap between raw signal data and physical geography.
Robust Feature Learning: Integration of an RNN-based sequence verification task within the EM loop to learn robust temporal embeddings, preventing feature collapse and ensuring accurate topology recovery.
Constrained Optimization: A trajectory inference algorithm that leverages regional boundaries to reduce the search space, making the joint estimation of coordinates and propagation parameters tractable without ground truth.

Experimental Results
The method was evaluated in a 768 m² office environment with 27 APs and 9 distinct regions, using data from 4 mobile users.

Region Label Inference: The HCFI method achieved a region classification accuracy of 97.8% and a Topology Accuracy of 100%, significantly outperforming state-of-the-art unsupervised clustering baselines (e.g., SPC, LSE) and approaching the performance of fully supervised methods (SVM, KNN).
Radio Map Construction: The estimated radio map achieved a Mean Absolute Error (MAE) of 8.96 dB and a Root Mean Square Error (RMSE) of 15.36 dB.
Trajectory Recovery: The average location label estimation error was 2.08 meters, outperforming other RSS-only methods (e.g., RRM at 3.14 m) and closely trailing the IMU-assisted Leto method (1.92 m).
Localization Performance: Using the constructed radio map with a K-Nearest Neighbor (KNN) algorithm, the system achieved an average positioning error of 3.33 meters across three independent test datasets. This performance is comparable to the IMU-assisted Leto baseline and significantly superior to traditional RSS-only methods (which exceeded 11 meters).

Significance and Claims
The paper claims that the HCFI framework offers a highly viable, zero-overhead solution for continuous radio map construction in environments with sequential topological assumptions. By mathematically embedding sequential mobility probabilities into physical indoor boundaries, the authors demonstrate that the fundamental bottlenecks of lacking ground-truth labels and auxiliary inertial sensors can be overcome. The results suggest that unsupervised, region-constrained inference can approach the performance boundaries previously thought to require labor-intensive manual calibration. The work concludes that exploiting latent spatial correlations in ambient stochastic RF signals provides a low-overhead paradigm for sustaining Location-Based Services (LBS) without the prohibitive costs of site surveys or the hardware dependencies of IMU-based systems. The authors note that the current reliance on unidirectional flow limits applicability to unconstrained open spaces, identifying the relaxation of this topological constraint as a primary direction for future work.