COVID-19
Book a meeting

K-Nearest Neighbours Positioning Algorithm

Navigine - K-Nearest Neighbours Positioning Algorithm
29 JAN 2022 · 13 MIN

Aside from the Zone localization algorithm, there is another one often used for defining user location. The KNN positioning algorithm requires special radiomap data measurement that can be performed using a procedure called Radiomap Measurement. This procedure includes measuring the target location's radiomap on foot via an Android device with the Navigine Application installed.

Requirements:

  • infrastructure deployed
  • maps (locations) implemented
  • radiomap data collected

 

Measurements & context

The algorithm relies on processing the previously collected RSSI data into a searchable structure. Then, with real-time observations from the user's device, we match the data to the given structure and obtain user location from it.

The preparation measurement implies collecting data in numerous points across the location, thus providing map coverage. For the multiple points with known coordinates, we stay and record the static logs from available devices (transmitters) in location. Then the recorded radio data is processed in radiomap - graph data structure with a fast search option. This radiomap is used further for KNN queries.

As in Zone positioning, we only assume that the signal propagation model is a simple function, e.g. the closer transmitter to a receiver, the stronger a signal.

 

What is the access point in the KNN positioning context

We measure incoming RSSI in several points of the building for a long enough time. After several minutes of collecting the signal, we perform averaging of signals. After that, we have precise measurements for a single point. Decent radio-map consists of several access points mapped to a building map.

In the context of KNN algorithm for indoor location, we don't know the true positions of all transmitters. Instead, we know the points from which we recorded the observations. This is the principal difference between Zone and KNN positioning. 

The "access point" or reference point in this algorithm is the point (position in space) with known coordinates and history of observations from each beacon in the visible range. The example of a map with corresponding reference points is shown on the image below:

Fig.1 Map and reference points example

We show the reference of the map with access points (circles). Approximately, we could say that the example log will consist of 20-100 access point locations and 10000 RSSI observations from 20-50 detected beacons for a single location.

All observations from multiple positions we call a radio map. From a radiomap, we can estimate user position by measuring similarity between observations and observations measured from a known prior location.

Navigine SDK

Professional real-time Indoor Positioning solutions for mobile apps.

More

The basic concept of localization algorithm using the KNN:

  • calculate the distance metric from the current pose (query point) to all other points of interest - measure the similarity between observations and access points data
  • return the first K items
  • calculate position from the first K items

If we want to use a geometrical approach as in the picture above, the position estimation will have an error during reconstructing distance from the radiomap. Instead, we just average the points.

We measure the similarity between points and then take the weighted average from the selected subset. This approach is called centroid estimation. 

When the target node communicates with all the anchors, i.e., all anchors are visible, the centroid results in the center of the anchors’ coordinates. 

The main assumption in this model, as in most geometrical algorithms, is that all transmitters are visible.

In the example where a signal is reflected from walls, the radio-based methods will be prone to error sometimes. KNN approach allows us to deal with this error source if number K is tuned correctly. 

If there are multiple signal reflections, we may want to localize only on the 3 most strong signals and reject all noisy information.

For accurate positioning in high reflecting environments, we need to both tune algorithm settings and collect more data to provide coverage.

Any questions about the article?
Leave a request

On KNN POSITIONING algorithm’s usage

From all the factors we know about the KNN positioning algorithm, it can be used for cases where we know the user position during the record stage and need to reconstruct transmitters' positions. Then we may use the much smaller map of transmitters with any positioning algorithm (Zone algorithm, for example). 

We also may want to use this algorithm if the location is complicated and we can’t reconstruct the true positions of beacons. So we choose the more complicated algorithm for better accuracy.

The modification of this algorithm is to use mesh triangulation, so we can easily extract the 3 closest points for the KNN solution. Alternatively, this fast search can be done using the KD tree.

Demo video for KNN

The feature map for this algorithm is relatively big compared to the usual transmitter map. Approximately, we have 20-50 beacons in a single location. For the Zone algorithm, we have only 50 records and level geometry. For KNN, we have 100 access point locations and 10000 RSSI observations from all detected beacons in a single location. Having 10000 records, we extract the locations of 100 access points by averaging observations.

The KNN algorithm has accuracy better than the Zone positioning algorithm if the data collection procedure was performed correctly. 

To conclude, the algorithm has a complicated procedure of data collection, this factor limits methods usage for big locations; we choose the KNN algorithm for operating with no known location of a transmitter - primarily to work with existing infrastructure such as WiFi access points.

 

Navigine -
Published:
Vlad de Armas
CONTACT US