Pozyx

Accurate positioning

Home > Documentation > How does positioning work

How does positioning work

Introduction

In general, you only need two things to perform positioning:

  • Measurements. In a sense, almost everything you can measure will depend on the position and could be used for positioning. However, it's the most sensible to measure things that are very sensitive to the position. For example, measuring the temperature might tell you in what continent you are but that's not very accurate. Measuring the distance or the angle to some point will probably be more accurate.
  • Reference points. It is only possible to describe a position relative to some reference points. Reference points can be 'your home', the north star or some satellites in the sky. For us, we will be using anchors. With 3 anchors it is possible to describe a two-dimensional coordinate system in which we will find our position. For three-dimensional positioning we need 4 anchors.

Here are some examples:

Positioning System Measurements Reference points
GPS (pseudo-)distances*: satellites
Pozyx distances anchors
camera based video image camera (with orientation specified)
WiFi or BLE fingerprinting Received signal strength (RSS) the fingerprints in the database
digital compass magnetic field vector the magnetic north
dead reckoning acceleration and angular velocity (from the gyroscope) your initial position and direction


Trilateration. Hover this image to see
the mathematical definitions.

Trilateration

The most commonly used method of positioning uses basic geometry to estimate the position. By measuring the distance to a number of anchors with a known position it is possible to obtain your own position. If we measure a certain distance, then we know we will be in a circle of that radius around the anchor. If we make distance measurements with 3 anchors we see that our position is uniquely determined by the intersection of the three circles. This method is called trilatteration (or multilatteration if more than 3 anchors are used).

The difficulty of this approach lies in the fact that the measurements are not perfect. There will always be some noise on the measurements and because of this, the circles will not intersect at exactly one point. To circumvent this issue, we try to find the point that is closest to all circles.


Watch out, mathematics ahead!
You can choose to skip the description of the algorithm and go directly to the next article: How does ultra-wideband work?


A basic algorithm

In this section, we will explain a simple algorithm to compute the position from a number of range measurements. This basic algorithm is by no means optimal but when the range measurements are sufficiently accurate it will work quite well.

We will explain the algorithm for 2D positioning. The user position $\mathbf{p}$ is given by the coordinates $x$ and $y$. The position of the $i$th anchor is given by $\mathbf{p}_i$ with coordinates $x_i$ and $y_i$ which are assumed to be known in advance. In total we have $N$ anchors so $i$ goes from $1$ to $N$.

Now the distance between the user and the $i$th anchor is denoted by $d_i$ and is given by the following formula:

$$ \begin{equation} d_i = \sqrt{ (x-x_i)^2 + (y-y_i)^2 } \end{equation} $$

We now take the square of this equation on both sides:

$$\begin{eqnarray} d_{i}^{2} & = & (x-x_{i})^{2}+(y-y_{i})^{2}\\ & = & x^{2}-2xx_{i}+x_{i}^{2}+y^{2}-2yy_{i}+y_{i}^{2}\label{eq-distances} \end{eqnarray}$$

The problem with equation $\ref{eq-distances}$ is the non-linear terms $x^2$ and $y^2$. We can eliminate these by subtracting $d_N^2$ from $d_i^2$ resulting in $N-1$ equations:

$$\begin{eqnarray} d_{i}^{2}-d_{N}^{2} & = & x^{2}-2xx_{i}+x_{i}^{2}+y^{2}-2yy_{i}+y_{i}^{2}-(x^{2}-2xx_{N}+x_{N}^{2}+y^{2}-2yy_{N}+y_{N}^{2})\\ & = & -2x(x_{i}-x_{N})+x_{i}^{2}-x_{N}^{2}-2y(y_{i}-y_{N})+y_{i}^{2}-y_{N}^{2} \end{eqnarray}$$

Now we have a number of equation that are linear in the unknown coordinates $x$ and $y$. That's great because linear equations are easy to solve. Let's write this in a matrix form:

$$ \begin{equation} \mathbf{b} = \mathbf{A}\left[\begin{array}{c}x\\y\end{array}\right] \end{equation} $$

with

$$ \begin{equation} \mathbf{b}=\left[\begin{array}{c} d_{1}^{2}-x_{1}^{2}-y_{1}^{2}-d_{N}^{2}+x_{N}^{2}+y_{N}^{2}\\ d_{2}^{2}-x_{2}^{2}-y_{2}^{2}-d_{N}^{2}+x_{N}^{2}+y_{N}^{2}\\ \vdots\\ d_{N-1}^{2}-x_{N-1}^{2}-y_{N-1}^{2}-d_{N}^{2}+x_{N}^{2}+y_{N}^{2} \end{array}\right] \end{equation} $$

and

$$ \begin{equation} \mathbf{A}=-2\left[\begin{array}{cc} x_{1}-x_{N} & y_{1}-y_{N}\\ x_{2}-x_{N} & y_{2}-y_{N}\\ \vdots & \vdots\\ x_{N-1}-x_{N} & \, x_{N-1}-x_{N} \end{array}\right] \end{equation} $$

We can now solve this system of equations:

  • if we have exactly 3 anchors: $N=3$, we will have exactly 2 equations to find the two unknowns and we can find the position as follows:
    $$ \begin{equation} \mathbf{p} = \mathbf{A}^{-1}\mathbf{b} \end{equation} $$
  • if we have more than 3 anchors: $N>3$, we will have more equations than unknowns and the inverse of $\mathbf{A}$ will not exist. To deal with this situation we can use the pseudo-inverse to compute the position. This results in the following equation:

    $$ \begin{equation} \mathbf{p} = (\mathbf{A}^{\top}\mathbf{A})^{-1} \mathbf{A}^{\top}\mathbf{b} \end{equation} $$

    where $\mathbf{A}^{\top}$ is the transpose of matrix $\mathbf{A}$. Note that the above formula will try to fit the coordinates $x$ and $y$ as much as possible to all the different equations (see here for more information). Because of this, the method will have an increased accuracy when more anchors are used.

The algorithm described above is called the linear least squares algorithm. 'Linear' because we linearize the equations (by taking the square), and 'least squares' because the (pseudo-)inverse of the matrix will result in a minimization of the squared error of all equations.

Going further

The algorithm described above is a very simple and low-complex algorithm. In the pozyx system, you will be able to select from a number of different algorithms; the least-squares algorithm will be one of them. If you want to learn more about advanced positioning techniques it is recommended to look for the following topics: non-linear least squares, Kalman filter, particle filter, belief propagation, ..

Next: How does ultra-wideband work?

Home > Documentation > How does positioning work

Comments section