07-06 Lateration Strategy

In literature there are many ways that RSSI can be transformed into a position. Some of them are non-range based such as fingerprinting. Others are range based but rely on different calculation algorithms.

One of these ranged based positioning methods is trilateration. It calculates the coordinates of a target by drawing circles around anchors with known positions. The radii of the circles are equal to the distance between the anchors and target. The target lies at the intersection point of the three circles. In algebraic terms the 2D coordinates of the target are the solution of a system of three linear equations with one solution.

Problem

With noisy distance estimations the system of linear equations will almost certainly not have a single solution anymore. There are three equations (distances) that are linearly independent and only two variables (coordinates). Algebraically speaking there is no single solution anymore to the equation system. In geometrical terms the circles can have many intersection points between two or three circles and form a "target area" in between. Or the circles possibly do not intersect because the radii are too small or the perimeter of one circle is contained within another one.

{ width=60% }

Source{ width=60% }

Solution

Ordinary Least Squares / Maximum Likelihood Estimation

In linear regression the residuals for a beacon of index is the difference in the "actual" distance and the estimated distances based on RSSI measurements. The goal is to find a set of points so that the sum of the residuals is at a minimum (least squares). Depending on the reliability of the beacon one can set a weigth for each residual. This source suggests that it is enough to just take the three closest beacons, so the weighting factor is either 1 or 0.

Sometimes this method was also explained as the maximum likelihood estimation. But since the residuals are more or less normally distributed the probability density function for the MLE makes it basically the same as ordinary least squares regression.

Therefore

Centroid / Independent Case Handling

Another way of going about this would be to define handling of every single possible combination of distance estimation error. When there is a target surface with overshooting distance such as above, then the centroid (middle of a triangle) of the three intersection points can be defined as the solution. The same can be for cases where only two circles overlap or none. This seems like a very cumbersome and error prone way of solving the issue because it every situation needs to be handled differently.

Next steps

Now I will just move forward with statistical methods for trilateration as opposed to more direct range based trilateration approaches such as intersection centroids or independent case handling. More often than not the research papers would contradict eachother regarding the performance and accuracy of the methods. Therefore I am making the decision to go with the least complex version, it seems to be the least complex of all things I could find in research papers. My main concern is that this might be a waste of time, since the way I understand the extended kalman filter, I might not even use trilateration unless I use it only to remove noise. In the situation outlined here, a velocity vector is estimated which already implicitly defines the displacement and thus also the position.