Indoor Positioning: Beacon & WiFi Fingerprinting Pipelines

The moment a user walks through a building’s front door their GPS fix collapses: satellite signals are attenuated by the roof and reflected off structural steel, and the horizontal error balloons from a few metres to tens of metres or drops out entirely. Indoor positioning exists to fill that gap — to estimate a moving person’s (x, y, level) from whatever signals do survive indoors (WiFi RSSI, Bluetooth advertisements, inertial motion) and hand that estimate to the wayfinding engine so a blue dot tracks reliably down a corridor. This is one of the hardest problems in the indoor stack because the raw ingredients are hostile: received signal strength is noisy, multipath-corrupted, and wildly device-dependent; radio maps drift the moment furniture moves or an access point is swapped; and a naive fix that lands two metres inside a concrete wall is worse than useless to a router that expects positions on its graph. This overview walks the full positioning pipeline — signal ingestion, reference modelling, position estimation, sensor fusion, and routing-graph binding — and shows how each stage earns the accuracy the one downstream depends on.

Layered Pipeline Architecture #

A production positioning system decomposes into five stages, each owning a single responsibility and passing a typed artifact to its neighbour. The decoupling matters operationally: you can swap a WiFi fingerprint estimator for a BLE trilateration estimator at stage three without touching the fusion filter, re-survey one floor’s radio map without disturbing the rest, and reason about a “blue dot jumps through walls” bug by pinning it to exactly one stage.

1. Signal ingestion & calibration. The device streams three heterogeneous sources: WiFi RSSI scans (a list of {bssid: rssi} per sweep), BLE advertisements (each carrying a beacon identity and measured signal strength), and IMU samples from the accelerometer, gyroscope, and magnetometer. These arrive at different rates and clocks, so the stage timestamp-aligns them onto a common timeline and applies a per-device RSSI calibration offset — an iPhone and a mid-range Android read the same access point five to ten dBm apart, and uncorrected that error dominates everything downstream.
2. Reference model. Estimation needs ground truth to compare against. For WiFi that is a radio map: a database of reference points, each a surveyed (x, y, level) labelled with the vector of access-point strengths measured there. For BLE it is a beacon geometry model: the surveyed anchor position and calibrated transmit power of every deployed beacon. Both live in the building’s local metric frame defined by the indoor coordinate reference system.
3. Position estimation. The live sample is turned into a raw fix. Fingerprinting runs a k-nearest-neighbour search over the radio map, returning the spatial centroid of the closest reference points in signal space. Ranging instead converts each beacon’s RSSI to a distance through a path-loss model, then solves a least-squares trilateration for the intersection of those distance circles. Either path emits an (x, y, level) plus an accuracy estimate — a covariance or a scalar radius — that honestly reflects how confident the match was.
4. Sensor fusion & filtering. A single radio fix jitters by metres between consecutive scans. A particle filter (or a Kalman variant for the linear-Gaussian case) fuses the noisy radio fix with a dead-reckoning motion model derived from the IMU and, critically, with the building geometry: particles that would cross a wall are killed, so the estimate can never teleport between rooms. The output is a smoothed, physically plausible trajectory.
5. Map-matching & routing-graph binding. A filtered fix is still a free-floating coordinate; the wayfinding engine wants a location on the network. This stage snaps the fix to the routing graph — the nearest routable edge or node on the correct level — and hands a clean, graph-anchored location to the router. That routing graph is the one built from the parsed floor plan geometry, so positioning and navigation share a single spatial truth.

Three hazards thread through every stage: signal noise (RSSI variance of several dBm even standing still), reference drift (the radio map ages the instant the building changes), and device heterogeneity (no two phones report the same strength for the same signal). The delivery artifact that leaves stage five is a PositionFix: x, y, level, an accuracy or covariance, a source tag of wifi, ble, or fused, and the snapped_edge_id the router consumes.

Core Data Model & Spatial Schema #

Positioning reuses the site’s GeoJSON envelope so that a radio map, a beacon inventory, and the routing graph all speak the same schema. Reference points and beacons are Point features carrying the standard indoor properties — feature_id, space_class, level, is_routable — extended with the positioning fields each source needs. A WiFi reference point nests an ap_vector mapping each access point’s BSSID to the RSSI observed during survey; a BLE beacon carries its beacon_id, calibrated one-metre tx_power, and physical anchor coordinates. Keeping the envelope identical means the same loader, validator, and CRS transform that handle floor-plan geometry also handle the positioning layer.

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "geometry": { "type": "Point", "coordinates": [12.4, 8.1] },
      "properties": {
        "feature_id": "L2-fp-0231",
        "space_class": "corridor",
        "level": 2,
        "is_routable": true,
        "ap_vector": { "a4:2b:8c:11:0f:e2": -58, "a4:2b:8c:11:0f:e3": -71, "9c:1c:12:aa:04:5d": -83 },
        "accessibility_rating": "step_free",
        "topology_hash": "7c1a9e04"
      }
    },
    {
      "type": "Feature",
      "geometry": { "type": "Point", "coordinates": [6.0, 2.0] },
      "properties": {
        "feature_id": "L2-beacon-0007",
        "space_class": "service",
        "level": 2,
        "is_routable": false,
        "beacon_id": "f7826da6-4fa2-4e98-8024-bc5b71e0893e:1:7",
        "tx_power": -59,
        "accessibility_rating": "restricted",
        "topology_hash": "b30d5f18"
      }
    }
  ]
}

Reference-point and beacon coordinates live in the floor level’s local metric frame, never in raw signal units or pixels — the calibration stage is what makes the radio map’s (x, y) and the routing graph’s (x, y) mean the same thing.

Fingerprint Store & kNN Position Estimation #

The workhorse of WiFi positioning is a nearest-neighbour search in signal space, not physical space. At survey time you record, at each reference point, the vector of RSSI values across every visible access point. At query time you build the same vector from a live scan and find the reference points whose signal vectors sit closest to it; their weighted spatial centroid is your fix. The subtlety is missing dimensions — an access point seen at survey but not at query, or vice versa — which must be imputed to a floor value (say −100 dBm) rather than dropped, or the distance metric silently rewards sparsity. The choice between plain and distance-weighted kNN is what turns a coarse room-level guess into a sub-three-metre fix.

# WiFi fingerprint kNN position estimate over an in-memory radio map.
import logging
import numpy as np

logger = logging.getLogger("positioning.fingerprint")

FLOOR_DBM = -100.0  # imputed strength for an access point absent from a scan


def estimate_position_knn(
    scan: dict[str, float],
    ref_vectors: np.ndarray,
    ref_coords: np.ndarray,
    bssid_index: dict[str, int],
    k: int = 4,
) -> tuple[np.ndarray, float]:
    """Estimate (x, y) from a live WiFi scan via distance-weighted kNN.

    ref_vectors is (N, M) RSSI over N reference points and M known BSSIDs;
    ref_coords is (N, 2) metric coordinates; bssid_index maps BSSID -> column.
    Returns the estimated coordinate and a one-sigma accuracy radius in metres.
    """
    if ref_vectors.shape[0] != ref_coords.shape[0]:
        raise ValueError("ref_vectors and ref_coords disagree on reference-point count")

    query = np.full(ref_vectors.shape[1], FLOOR_DBM, dtype=np.float64)
    for bssid, rssi in scan.items():
        col = bssid_index.get(bssid)
        if col is None:
            continue  # AP not in the radio map; ignore rather than distort the metric
        query[col] = rssi

    try:
        dists = np.linalg.norm(ref_vectors - query, axis=1)
    except ValueError as exc:  # dimension mismatch between scan vector and map
        logger.exception("Signal-space distance failed: %s", exc)
        raise

    nn = np.argsort(dists)[:k]
    weights = 1.0 / np.maximum(dists[nn], 1e-6)
    est = np.average(ref_coords[nn], axis=0, weights=weights)
    spread = float(np.sqrt(np.average(np.sum((ref_coords[nn] - est) ** 2, axis=1), weights=weights)))
    logger.info("kNN fix at (%.2f, %.2f) from %d neighbours, spread=%.2f m", est[0], est[1], k, spread)
    return est, spread

The returned spread is not decoration: it is the accuracy estimate the fusion stage weights the radio fix by. When the nearest neighbours disagree spatially — the query sits in an ambiguous signal valley between two corridors — spread widens and the particle filter correctly leans harder on the motion model.

Path-Loss Ranging & Trilateration #

Beacon positioning takes the opposite route: instead of matching against a surveyed map, it models physics. The log-distance path-loss model converts a beacon’s RSSI to an estimated range, d = 10 ** ((tx_power - rssi) / (10 * n)), where n is the environmental attenuation exponent. Three or more ranges from beacons at known anchor positions define overlapping distance circles, and a least-squares trilateration finds the point that best satisfies them all. Trilateration is only as good as beacon geometry allows — collinear or clustered anchors produce a degenerate solution — which is why beacon placement is a first-class design problem, not an afterthought.

# Least-squares trilateration from BLE ranges to anchored beacons.
import logging
import numpy as np
from scipy.optimize import least_squares

logger = logging.getLogger("positioning.trilaterate")


def path_loss_distance(rssi: float, tx_power: float, n: float = 2.2) -> float:
    """Convert a BLE RSSI reading to an estimated range in metres (log-distance model)."""
    return float(10.0 ** ((tx_power - rssi) / (10.0 * n)))


def trilaterate(
    anchors: np.ndarray,
    ranges: np.ndarray,
    seed: np.ndarray | None = None,
) -> tuple[np.ndarray, float]:
    """Solve for (x, y) minimizing the residual between measured and geometric ranges.

    anchors is (K, 2) beacon coordinates; ranges is (K,) estimated distances.
    Returns the fix and the RMS range residual as an accuracy proxy.
    """
    if anchors.shape[0] < 3:
        raise ValueError("Trilateration needs >= 3 anchored beacons")

    x0 = seed if seed is not None else anchors.mean(axis=0)

    def residual(p: np.ndarray) -> np.ndarray:
        return np.linalg.norm(anchors - p, axis=1) - ranges

    try:
        sol = least_squares(residual, x0, method="lm", max_nfev=200)
    except ValueError as exc:  # degenerate/collinear anchor geometry
        logger.exception("Trilateration solve failed on %d anchors: %s", anchors.shape[0], exc)
        raise

    rms = float(np.sqrt(np.mean(sol.fun ** 2)))
    logger.info("Trilaterated fix at (%.2f, %.2f), rms residual=%.2f m", sol.x[0], sol.x[1], rms)
    return sol.x, rms

The RMS residual again doubles as an accuracy estimate: a tight residual means the distance circles agreed and the fix is trustworthy; a large one signals multipath or a stale tx_power calibration and tells the fusion stage to distrust this reading.

Sensor Fusion & Snapping to the Graph #

A raw fix — from either estimator — is a noisy point sampled a few times a second. Consecutive fixes can sit metres apart even when the user is standing still, and nothing in the estimator forbids a fix inside a wall. The fusion stage fixes both problems at once. A particle filter maintains a cloud of hypotheses about the true position, propagates them forward with an IMU-derived motion model between radio fixes, weights each particle by how well it agrees with the latest radio observation, and — the step that makes indoor filtering special — assigns zero weight to any particle whose step crossed a wall. Impossible jumps die on contact with the geometry. The deep implementation lives in the particle-filter companion guide; the essential move afterwards is binding the smoothed estimate to the network.

# Snap a filtered fix to the nearest routable edge on the correct level.
import logging
import numpy as np
from shapely.geometry import Point, LineString
from shapely.ops import nearest_points
from rtree import index

logger = logging.getLogger("positioning.snap")


def snap_to_graph(
    fix: np.ndarray,
    level: int,
    edges: dict[str, tuple[LineString, int]],
    edge_index: index.Index,
    max_snap: float = 4.0,
) -> tuple[str, np.ndarray] | None:
    """Snap a (x, y) fix to the closest edge whose level matches, within max_snap metres.

    edges maps edge_id -> (LineString, level); edge_index is an R-tree over edge bounds.
    Returns (snapped_edge_id, snapped_point) or None when nothing is in range.
    """
    p = Point(float(fix[0]), float(fix[1]))
    best_id, best_pt, best_d = None, None, float("inf")

    try:
        candidates = list(edge_index.intersection((p.x - max_snap, p.y - max_snap,
                                                    p.x + max_snap, p.y + max_snap)))
    except Exception as exc:  # corrupt or empty spatial index
        logger.exception("Edge index query failed near (%.2f, %.2f): %s", p.x, p.y, exc)
        raise

    for raw_id in candidates:
        edge_id = str(raw_id)
        geom, edge_level = edges[edge_id]
        if edge_level != level:
            continue  # never snap onto another floor
        d = geom.distance(p)
        if d < best_d:
            best_d, best_id = d, edge_id
            best_pt = np.asarray(nearest_points(geom, p)[0].coords[0])

    if best_id is None or best_d > max_snap:
        logger.warning("No routable edge within %.1f m of fix on level %d", max_snap, level)
        return None

    logger.info("Snapped fix to edge %s at %.2f m offset", best_id, best_d)
    return best_id, best_pt

The level guard is doing quiet but critical work: it refuses to snap a fix onto an edge on the wrong floor even if that edge is geometrically closer in the horizontal plane, which is exactly the trap a stairwell or an atrium sets. Floor detection therefore has to resolve before snapping, against the level-mapping and Z-axis logic that governs vertical connectivity across the building.

Validation & Failure Modes #

Positioning failures are insidious because they surface as a misbehaving blue dot in a shipped app, far from the stage that caused them, and they rarely throw exceptions — they just quietly point at the wrong place. The discipline is the same as the rest of the stack: know exactly what breaks when each stage is skipped or misconfigured, and instrument for it.

• Skip per-device calibration → every phone model reads RSSI with its own offset, so a radio map surveyed on one device systematically mislocates users on another; matches land in the wrong corridor with a confident-looking accuracy.
• Skip fusion/filtering → the marker teleports. Raw fixes jitter metres between scans and nothing forbids a fix inside a wall, so the blue dot jumps through partitions and hops between rooms the user never entered.
• Skip map-matching → routes start off-graph. An unsnapped fix floats in free space, the router can’t find an edge to begin from, and turn-by-turn guidance either fails to initialize or snaps unpredictably mid-route.
• Stale radio map → systematic position bias. Once furniture, occupancy, or an access point changes, the surveyed fingerprints no longer describe the live signal environment and every fix in the affected zone drifts in the same direction — a bias no amount of filtering removes.
• Wrong floor detection → the user is routed on the wrong level entirely. A fix snapped to level 2 when the user is on level 3 produces confident, fluent, completely wrong directions, and the failure is invisible until the user hits a wall where a door should be.

The corrective loop mirrors validation elsewhere on the site: ground-truth walk tests along known paths produce a per-zone error distribution, fixes whose accuracy estimate exceeds a threshold are held back rather than shown, and a positioning outage degrades gracefully into the fallback routing architecture — last-known-good position plus dead reckoning — instead of freezing or lying.

# Reject a PositionFix that fails accuracy, floor-consistency, or continuity checks.
import logging
import numpy as np

logger = logging.getLogger("positioning.validate")


def accept_fix(
    fix: np.ndarray,
    accuracy: float,
    level: int,
    prev_fix: np.ndarray | None,
    dt: float,
    max_accuracy: float = 8.0,
    max_speed: float = 2.5,
) -> bool:
    """Gate a fix on accuracy and plausible walking speed before it reaches the router."""
    try:
        if accuracy > max_accuracy:
            logger.warning("Rejecting fix on level %d: accuracy %.1f m > %.1f m", level, accuracy, max_accuracy)
            return False
        if prev_fix is not None and dt > 0:
            speed = float(np.linalg.norm(fix - prev_fix) / dt)
            if speed > max_speed:
                logger.warning("Rejecting fix: implied speed %.1f m/s exceeds %.1f m/s", speed, max_speed)
                return False
    except (TypeError, ValueError) as exc:  # malformed fix vector or dt
        logger.exception("Fix validation error: %s", exc)
        return False
    return True

Operational Considerations #

Radio maps are perishable, so re-survey cadence is a running operational cost, not a one-time setup. A stable, low-traffic floor might hold accuracy for a quarter; a retail space that re-merchandises monthly needs a matching survey rhythm, and crowd-sourced background scans from consenting devices can keep the map fresh between formal walks. Every re-survey bumps the reference record’s topology_hash, which is the same signal the delivery layer keys cache invalidation on — positioning data ages into the deployment pipeline the same way geometry does.

Device heterogeneity is the second permanent tax. Because RSSI offsets are per-model, production systems either maintain per-device-class calibration tables or normalize each scan against a reference access point before matching. Floor detection deserves its own attention: barometric pressure deltas, the level tag of the strongest beacon, and the WiFi map’s own level label vote together, because getting the floor wrong invalidates everything the horizontal estimator does. Privacy is not optional — WiFi and BLE scans are behavioural traces — so scan data is minimized, hashed where identity isn’t needed, retained briefly, and gathered under explicit consent; the positioning telemetry that survives feeds accuracy dashboards and re-survey triggers rather than user tracking. Finally, the clean fixes this pipeline emits are consumed by the client through the SDK integration patterns, so the PositionFix contract — coordinates, accuracy, source, snapped edge — is the interface the whole navigation experience is built on.

Frequently Asked Questions #

Related #

• WiFi RSSI Fingerprinting
• BLE Beacon Positioning
• Sensor Fusion & Particle Filters
• Positioning to the Routing Graph
• Fallback Routing Architectures

This page is the overview for the Beacon & WiFi Positioning section, part of the wider Indoor Mapping & Wayfinding Automation reference, which connects to floor plan parsing and vectorization upstream and production-ready map deployment downstream.