Wifi Trilateration

Location-finding with wifi

The idea behind trilateration

The basic idea behind trilateration is to use wireless network observations for direction-finding applications.

There are two ways to approach this, although both will boil down to the same algorithm:

• Observing a single wireless network/device from multiple locations, to determine the location of the single wireless network/device
• Observing multiple wireless networks/devices from a single location, to determine that particular location

In the first case, we rely on knowing the positions of the observations being made. These are used to determine the location of the router/device being observed.

In the second case, we rely on knowing the positions of the wireless networks/devices being observed. These are used to determine the location of the observations.

Trilateration vs Triangulation

Triangulation uses only angles to assemble triangles and determine positions. (Think surveying)

Trilateration uses known distances from a point to determine the location.

Multilateration uses differences in time-of-arrival of a single signal at different locations to determine a distance.

The Maths

Okay, time for some maths behind the problem.

Suppose we have a number of observations $N$, each at a unique location on a 2D Cartesian grid $(x_{i},y_{i})$.

We intend to utilize $N$ observations of the received signal strength indicator (RSSI) at the $N$ known points $(x_{i},y_{i})$ as a proxy for distance to the unknown location. This allows us to convert RSSI associated with each observation into a distance, which gives us the magnitude of a vector from the unknown location to the observation location. But to form the complete vector we also need a direction. We can approximate the direction from the unknown location to the observation point by using the distance-weighted average location of the remaining observations as a proxy for the unknown location.

(Picture)

First Pass Implementation

A first-pass approach might say, compute an average x and y, for each observation location, using the distance to the unknown location as a weighting factor. Thus the average x and y locations could be written:

${\overline {x}}=\sum _{i}w_{i}x_{i}$

${\overline {y}}=\sum _{i}w_{i}y_{i}$

and the weights are given by a normalized measure of the RSSI:

$w_{i}={\dfrac {RSSI_{i}}{\sum _{j}RSSI_{j}}}$

HOWEVER, this approach ignores the fact that signal strength drops off with the square of distance, and is not linear with distance:

$RSSI\sim {\dfrac {1}{r^{2}}}$

or,

${\dfrac {1}{r}}\sim {\sqrt {RSSI}}$

Second Pass Implementation

To try again, let's revisit how we defined those weights. We were looking for a distance-averaged location:

${\overline {x}}=\sum _{i}w_{i}x_{i}$

${\overline {y}}=\sum _{i}w_{i}y_{i}$

and we let the weights be proportional to RSSI. But really, we want the weights to be proportional to distance from the unknown location - actually, we want the weights to be inversely proportional to the distance to the unknown location. That is, if $d_{i}$ represents the approximate distance from the observation point to the unknown location (based on using RSSI), then we want to define the weights as follows:

$w_{i}={\dfrac {\frac {1}{d_{i}}}{\sum _{j}{\frac {1}{d_{j}}}}}$

or, to put it in terms of the RSSI,

$w_{i}={\dfrac {\sqrt {RSSI_{i}}}{\sum _{j}{\sqrt {RSSI_{j}}}}}$