WiFi

 

 

 

Indoor Positioning

 

WiFi Indoor positioning is a way to find out where things or people are located inside a building by looking at how strong the Wi-Fi signals are. It's a part of what we call Indoor Positioning Systems (IPS), which are helpful in places where GPS doesn't work well, like inside buildings.

Every technique on this page answers the same question in a different way: what can a Wi-Fi device measure that depends on its position? The first answer was signal strength, because every device already reports it. The newer answer is time of flight, which Wi-Fi RTT measures directly. Let's go through the techniques first, then look at the numbers behind RSSI ranging and trilateration, and finish with RTT.

Which techniques can locate a device indoors ?

Indoors, a device cannot rely on GPS, so it has to use signals that it can measure inside the building. Wi-Fi is the obvious choice, because access points are already installed almost everywhere.

There are many different ways of implmenting the positioning. Followings are some of the techniques and short descriptons.

  • Signal Strength Measurement:
    • We use how strong a Wi-Fi signal is, something called RSSI, to guess how far away a phone or computer is from a Wi-Fi router.
    • Devices like phones check how strong the Wi-Fi signal is from routers close by and tell this to the system that figures out where they are.
  • Trilateration:
    • Just like GPS uses signals from satellites in space, Wi-Fi positioning uses signals from several routers to find out exactly where a device is inside.
    • The system looks at how strong the signal is from at least three routers and uses where these signals overlap to figure out where the device is.
  • Fingerprinting:
    • This method involves making a map of Wi-Fi signal strengths all over a building.
    • A device's Wi-Fi signal strength is matched to this map to find out where the device is.
  • Dead Reckoning:
    • Some systems also use motion sensors in devices, like accelerometers and gyroscopes, to get even more accurate locations.
    • This works by starting with a known location and then updating this location based on how much and how fast the device has moved since then.

These four techniques are not alternatives in a strict sense. Signal strength measurement produces the raw input, and trilateration and fingerprinting are two ways to turn that input into a position. Trilateration needs a model of how the signal fades with distance. Fingerprinting replaces the model with a survey, so it handles walls and furniture better, but the map has to be rebuilt when the building changes. Dead reckoning works between Wi-Fi fixes. It fills the gaps, while the Wi-Fi fixes stop its error from growing without limit.

  • RSSI is the input, not the method : trilateration and fingerprinting both start from it.
  • A model or a survey : trilateration trusts a path loss model, and fingerprinting trusts a measured map.
  • Dead reckoning drifts on its own : it needs regular Wi-Fi fixes to reset its error.

How does RSSI turn into a position ?

The weak point of RSSI ranging is the step from signal strength to distance. A small error in dB becomes a large error in meters, so let's work one example through with real numbers.

The usual model is the log-distance path loss model. It says that the RSSI falls by 10 x n dB for every tenfold increase in distance, where n is the path loss exponent. In free space n is 2. Indoors it is often closer to 3, because walls and people absorb the signal.

RSSI(d) = RSSI(d0) - 10 x n x log10(d / d0)

Take RSSI(d0) = -40 dBm at d0 = 1 m, and n = 3. A device that reports -70 dBm is then at 1030/30 = 10 m. Now suppose the reading is off by 4 dB, which is a normal amount of fading indoors. At -66 dBm the model gives 7.4 m, and at -74 dBm it gives 13.6 m. So a 4 dB error turns 10 m into a range from 7.4 to 13.6 m.

Trilateration then combines three such distances. Let's place three access points at (0, 0), (20, 0) and (0, 15) in meters, and the device at (8, 6). The true distances are 10, 13.42 and 12.04 m. Subtracting the circle equations from each other removes the squared terms. The result is two linear equations: -40x + 400 = d22 - d12 and -30y + 225 = d32 - d12. With the true distances, they give x = 8 and y = 6 exactly.

Now let the first access point read 2 dB too weak. Its distance grows by a factor of 102/30, from 10 to 11.66 m. The same equations then give (8.90, 7.20), which is 1.5 m away from the true position. So a single 2 dB error on one access point moves the fix by 1.5 m. Real systems use more than three access points and a least squares fit, so that one bad reading has less weight.

  • dB errors grow into meter errors : with n = 3, every 1 dB changes the distance by about 8 percent.
  • The exponent n must fit the building : a wrong n biases every distance in the same direction.
  • More access points help : a least squares fit over many distances reduces the effect of one bad reading.

How does Wi-Fi RTT measure distance ?

RSSI ranging fails because signal strength depends on much more than distance. Time of flight depends on distance only, apart from multipath. Wi-Fi RTT uses the Fine Timing Measurement or FTM procedure, which was added to 802.11 by the 802.11mc work, to measure that time.

The problem is that the two stations do not share a clock. FTM avoids the problem by never comparing timestamps from different clocks. Figure 1 shows the exchange. The responding station sends an FTM frame at t1 by its own clock, and the initiating station receives it at t2 by its clock. The initiating station answers with an ACK at t3, and the responding station receives it at t4. The next FTM frame carries t1 and t4 back to the initiator.

Fine Timing Measurement timestamps Initiating STA Responding STA Initial FTM Request FTM 1 t1 t2 ACK t3 t4 FTM 2 carries t1 and t4 RTT = (t4 - t1) - (t3 - t2)

Figure 1. Each difference in the RTT formula uses one clock only. The responder measures t4 - t1, and the initiator measures t3 - t2, so the clock offset between the stations cancels.

  • t4 - t1 : the whole round trip as the responder sees it, including the time the initiator took to answer.
  • t3 - t2 : the turnaround time inside the initiator. Subtracting it leaves only the two flights over the air.
  • FTM 2 : it delivers t1 and t4, and it also starts the next measurement of the burst.

The distance is then c x RTT / 2. Because the signal travels there and back, each nanosecond of RTT error is only 15 cm of distance error. The limit comes from the bandwidth. A wider channel gives a sharper arrival time. As a rough measure, c / (2 x B) gives about 1.9 m for an 80 MHz channel, and the receiver interpolates below that. This is why RTT reaches the one-meter accuracy that RSSI cannot. Android exposes Wi-Fi RTT to applications, as the Google I/O talk in the YouTube list shows, and both the phone and the access point must support FTM. The 802.11az amendment continues this work as Next Generation Positioning.

  • No shared clock is needed : each station measures only its own time differences.
  • 1 ns of RTT error is 15 cm : the factor of two comes from the round trip.
  • Both ends must support FTM : an ordinary access point gives RSSI only.

Which technique fits which job ?

The choice depends mostly on what you can install and maintain. A venue that cannot replace its access points has RSSI only. A venue with FTM-capable access points can use RTT. Most real systems combine two or more techniques rather than picking one.

The table below compares the techniques by what they measure, what they need, and where their error comes from. It leaves out accuracy figures on purpose, because published values depend strongly on the building and the test method.

 

Technique

Measures

Needs

Main error source

Trilateration on RSSI

Signal strength

Access point positions and a path loss model

A few dB of fading gives meters of error

Fingerprinting

Signal strength

A survey map of the building

The map must be rebuilt when the building changes

Dead reckoning

Motion sensors

A known start point

The error grows with time

Wi-Fi RTT

Time of flight

Access points that support FTM

Multipath and a blocked direct path bias the time

 

A common combination is RTT or fingerprinting for the fix, with dead reckoning between fixes. The Wi-Fi fix removes the drift of the motion sensors. The motion sensors smooth the jumps of the Wi-Fi fix and keep a position when a scan is late.

  • Infrastructure decides first : RTT needs FTM on the access points, and RSSI works with any access point.
  • Combine a fix with a tracker : Wi-Fi gives an absolute position, and dead reckoning fills the time between fixes.

References

YouTube