Introduction

The Event-Participation-Trends project attempts to generate heat-maps of an event’s space, representing the positions of participants in that event space. This is done by predicting the positions of participant’s Wi-Fi devices based on the distance of the device relative to sensors around it. To do this accurately, a positioning method with sufficient accuracy and performance is needed to survive the high amounts of data that would need to be computed.

Considerations

Many methods exist for positioning systems based on distance. Here are few that were considered, as well as the reason they were not sufficient for our goals.

Nearest-Sensor-Clustering

In Nearest-Sensor-Clustering, the device’s position is estimated to be the known position of the sensor with the least distance to the device.

Problems

While this method is very performant, it does not deliver the required accuracy and therefore was not accepted as the final method.

Neural Network

A neural network would take the x- & y coordinates of each of the three chosen sensors, as well as the distance from each of these sensors to output an x- & y coordinate pair, which would represent the coordinates of the target device. To achieve sufficient accuracy in simulated tests, preprocessing was needed to normalize the data in a geometrically complex manner to achieve the expected result.

Problem

This reprocessing and the reverse processing of the result in combination with the neural network’s predictions lead to a very slow prediction function, with only 20 predictions/s, which was not sufficient for our goals of accommodating more than 200 participants at a time.

Trilateration

The trilateration algorithm is one used by most positioning services in working today. It takes the distance from each sensor to the device and creates a circle around each sensor with a radius equal to the distance to the device. Where three or more circles intercept is our estimation point.

Problems

Inaccuracies in the distance estimation due to interference with the sensors would lead to an over- or under-estimation of the distance to the device. This would cause the circles drawn to over- or undershoot the device position, giving us an area instead of an intersection. Using this area to estimate positions is not only inaccurate, but very complex to implement.

Ratio-Based Trilateration

To solve for the problems of the trilateration method, a ratio-based trilateration method was used. This method was first published in a scientific journal in 2019 and is not yet widely used. This method uses the ratios of the distances from the sensors to the device instead of the raw distances themselves.

What this accomplishes is twofold:

1. It ignores environmental factors in the actual space, since if the same environmental factor acts on all signals, the distances will be affected the same and the ratios will remain constant.
2. It always leads to an intersection of the circles, making the calculation of an estimate device position simpler and faster.

Kalman Filter

The Kalman-Filter is used, along with a history of device locations, to better estimate the next position of the device. What the Kalman-Filter does, is use the previous location of the device, along with information known about the device (velocity & acceleration) to predict the next location of the device.

Then, using the next position estimated by the ratio-based trilateration method, will be able to more accurately estimate the next position of the device.

Conclusion

Using the ratio-based trilateration method along with the Kalman-Filter, we were able to achieve metrics acceptable to us and allowed us to choose this method as our positioning service, which was afterward implemented in TypeScript.

References

• Author : Shixun Wu, Wenxian Huang, Min Li and Kai Xu,
• Title : A Novel RSSI Fingerprint Positioning Method Based on Virtual AP and Convolutional Neural Network,
• Journal : IEEE SENSORS JOURNAL, VOL. 22, NO. 7,
• Year : APRIL 1, 2022,
• Link : https://ieeexplore.ieee.org/abstract/document/9718215,