BLE Beacon Trilateration Engine

BLE Beacon Trilateration Engine

animation
location

BLE Beacon Trilateration Engine

This Python implementation computes indoor position from BLE beacon RSSI measurements using the trilateration method from the worked example above. It applies RSSI-to-distance conversion, least-squares trilateration, and RSSI averaging to smooth noisy readings:

import math

class BLETrilateration:
    """Estimate indoor position from BLE beacon RSSI measurements.

    Uses the log-distance path loss model to convert RSSI to distance,
    then solves the trilateration system via least-squares.
    """
    def __init__(self, tx_power=-59, path_loss_exp=2.5):
        self.tx_power = tx_power      # RSSI at 1 meter (dBm)
        self.n = path_loss_exp         # Indoor path loss exponent
        self.beacons = {}              # {id: (x, y)}
        self.rssi_history = {}         # {id: [recent RSSI values]}
        self.history_size = 5          # Average last N readings

    def add_beacon(self, beacon_id, x, y):
        """Register a beacon at known coordinates (meters)."""
        self.beacons[beacon_id] = (x, y)
        self.rssi_history[beacon_id] = []

    def rssi_to_distance(self, rssi):
        """Convert RSSI (dBm) to estimated distance (meters)."""
        if rssi >= self.tx_power:
            return 0.1  # Very close
        return 10 ** ((self.tx_power - rssi) / (10 * self.n))

    def update_rssi(self, beacon_id, rssi):
        """Record an RSSI measurement, maintaining rolling average."""
        if beacon_id in self.rssi_history:
            history = self.rssi_history[beacon_id]
            history.append(rssi)
            if len(history) > self.history_size:
                history.pop(0)

    def _averaged_rssi(self, beacon_id):
        """Return smoothed RSSI from recent measurements."""
        history = self.rssi_history.get(beacon_id, [])
        if not history:
            return None
        return sum(history) / len(history)

    def estimate_position(self):
        """Compute position via least-squares trilateration.

        Requires at least 3 beacons with recent RSSI data.
        Returns (x, y, mean_absolute_range_residual_m) or None if insufficient data.
        """
        measurements = []
        for bid, (bx, by) in self.beacons.items():
            avg_rssi = self._averaged_rssi(bid)
            if avg_rssi is not None:
                dist = self.rssi_to_distance(avg_rssi)
                measurements.append((bx, by, dist))

        if len(measurements) < 3:
            return None

        # Least-squares: linearize by subtracting last equation
        # from all others: 2(xi-xn)x + 2(yi-yn)y = dn^2 - di^2 + xi^2 - xn^2 + yi^2 - yn^2
        ref = measurements[-1]
        A_rows, b_rows = [], []
        for bx, by, d in measurements[:-1]:
            A_rows.append([2 * (bx - ref[0]), 2 * (by - ref[1])])
            b_rows.append(ref[2]**2 - d**2 + bx**2 - ref[0]**2 + by**2 - ref[1]**2)

        # Solve via pseudo-inverse (A^T A)^-1 A^T b
        # Manual 2x2 for simplicity
        a11 = sum(r[0]**2 for r in A_rows)
        a12 = sum(r[0] * r[1] for r in A_rows)
        a22 = sum(r[1]**2 for r in A_rows)
        b1 = sum(A_rows[i][0] * b_rows[i] for i in range(len(b_rows)))
        b2 = sum(A_rows[i][1] * b_rows[i] for i in range(len(b_rows)))

        det = a11 * a22 - a12 * a12
        if abs(det) < 1e-10:
            return None

        x = (a22 * b1 - a12 * b2) / det
        y = (a11 * b2 - a12 * b1) / det

        # Compute mean absolute range residual; this is not position accuracy
        residuals = []
        for bx, by, d in measurements:
            est_d = math.sqrt((x - bx)**2 + (y - by)**2)
            residuals.append(abs(est_d - d))
        mean_range_residual = sum(residuals) / len(residuals)

        return round(x, 2), round(y, 2), round(mean_range_residual, 2)

# Example: Museum indoor wayfinding
tri = BLETrilateration(tx_power=-59, path_loss_exp=2.5)
tri.add_beacon("entrance", 0, 0)
tri.add_beacon("gift-shop", 10, 0)
tri.add_beacon("cafe", 5, 8)

# Simulate visitor walking near entrance
for rssi in [-64, -65, -66, -65, -64]:  # 5 readings from entrance beacon
    tri.update_rssi("entrance", rssi)
for rssi in [-82.3, -82.3, -82.3, -82.3, -82.3]:  # gift-shop beacon
    tri.update_rssi("gift-shop", rssi)
for rssi in [-81.6, -81.6, -81.6, -81.6, -81.6]:  # cafe beacon
    tri.update_rssi("cafe", rssi)

result = tri.estimate_position()
if result:
    x, y, residual = result
    print(f"Estimated position: ({x}, {y}) meters")
    print(f"Mean absolute range residual: {residual} meters")

# Show RSSI-to-distance conversion
for bid in tri.beacons:
    avg = tri._averaged_rssi(bid)
    dist = tri.rssi_to_distance(avg)
    print(f"  {bid}: RSSI={avg:.0f} dBm -> {dist:.2f}m")
# Output:
# Estimated position: (1.49, 0.80) meters
# Mean absolute range residual: 0.01 meters
#   entrance: RSSI=-65 dBm -> 1.74m
#   gift-shop: RSSI=-82 dBm -> 8.55m
#   cafe: RSSI=-82 dBm -> 8.02m

The reported mean absolute range residual summarizes the fitted ranges; it is not coordinate error or a confidence bound. Quantify position error with calibrated site measurements. The path_loss_exp parameter must be calibrated on-site because it changes the estimated ranges and position.

Back to the chapter