Beacon - based trilateration
Theory: In terms of trilateration, user position is defined by accurate distance from the user to 3 predefined points. In general, trilateration is a three dimensional task and the user position is defined as a point of interception of three spheres.
But in context of our task, all beacons and the user are approximately at the same altitude, so we can treat spheres as simple circles and use a two-dimensional coordinate system. Unfortunately, beacons provide us with quite a low accuracy, so the circles often have large interception areas or do not have them at all. So in real world we actually have to deal with such cases:
In case of a) and b) the most probable user location is a geometrical centre (green dot) of the triangle (red) produced by internal circle intersections.
In case of c) user is probably situated out of a rectangle, so the location definition accuracy is low
And d) doesn’t suggest any solution at all
Error Correction
In order to get a solution in any case (Note: formally, b) and d) cases do not have any solution). We need to correct the distances in such a way, where all circles have at least some intersections (and common points).
There are generally 3 error sources:
- Environmental issues
- Dynamic obstacles (other people/horses)
- Device hardware accuracy barrier
Environmental
Can be corrected by linear range correction, based on the approximate distance to the beacon (since such an error is probably influencing all beacons proportionally).
Dynamic
We can do nothing about dynamic obstacles, but just define which of beacons are inflated and exclude them from the calculations (such an error isn’t permanent). Additionally the error margin can be decreased by placing the beacons higher. The main drawback of the suggested solution however, is the fact that we’ll have to deal with a 3-dimensional position definition algorithm.
Accuracy
This error usually does have a random structure so it can be corrected simply by calculating the average value for some period of time. The main drawback of such a correction is the “position update lag”, depending on the analyzed timespan. Additionally such an error can be decreased by incrementing the number of beacons analyzed.
Practical experiments
In order to perform tests we’ve made an app, which performs according to 4 stages:
The first stage has 3 alternative approaches:
a) Linear accuracy correction (circles are extended proportionally to their current values). Targeted to resolve environmental error issue
b) Reliability-based correction (here we have implemented a complex reliability criteria for circle values, the algorithm was able to increase or decrease circle radiuses to get the user position region as small as possible.) The algorithm was targeted to resolve environmental and dynamic obstacle issues. Such behaviour allowed us to analyze all beacons available, and not just the nearest 3.
c) Reliability-based correction (simplified). Similar to the previous, but uses a simplified error correction norm definition, which allows for faster calculations and the ability to remove some critical points, yet doesn’t allow for circle-size decreasing. Therefore, it can’t correct decremental errors (such errors are produced by hardware anyway) from the algorithm. Estimated accuracy loss (compared to b)) is minimal.
Note: the current algorithm requires an update to handle circle positioning c) correctly. In all experiments, the beacons (A,B,C) were positioned to form an equidistant rectangular triangle. So that AB = AC. We’ll call it “ds” in future.
Experiment Logs
Indoor Test #1
Positioning returns unstable values. The main cause seems to be high beacon broadcast power (seems that short range tracking provides better accuracy. No low broadcasting power)
Indoor Test #2
Positioning returns reliable data (accuracy about 0.5-1m) in the case when the user is situated on ABC triangle sides. Proximity to the beacons is detected accurately. Some randomness is present. Side spectators (dynamic obstacles) make the algorithm unstable. Position definition outside of the triangle (circle combination c) ) doesn’t work.
Indoor Test #3
Accuracy is slightly better compared to test 2, but spectators increase the error significantly and the beacon is sometimes lost (user position is undefined due to error).
Indoor Test #4
The algorithm can’t find the user position, random data is returned. Algorithm correction is required.
Indoor Test #5
The algorithm can find the user position with an approximate accuracy of 1-1.5m. Proximity to the beacon is defined correctly. Accuracy and stability is lower compared to correction a).
Indoor Test #6
Positioning is showing inaccurate data. User location is often lost. The algorithm requires an update to support more than 3 beacons.
Outdoor Test #1
The algorithm is showing 0.5-1.5m accuracy on ABC triangle sides and in close proximity to the beacon. The position outside of the triangle can’t be defined.
Conclusion
The algorithm might be usable (in context of section definition) in case we decide to track just one further section, which the user has to move into.
Currently, the amount of beacons which can be used, is limited to 3 beacons. However, there is a possibility to overcome this limitation by combining the 3 beacons, analyzing all possible subsets and then choosing the most optimal subset placement. The current implementation might trigger a “user section update” before he actually changes it. And large-scale field test is required.
Hope you have found this article useful, don't forget to leave your comments below the article. If you have a project idea in mind but don't know where to start, we're always here to help you.
SEE ALSO:
