The different indoor location algorithms

Reading time

10min

Level

Expert
algorithmes-localisation-interieure

The development of Global Navigation Satellite System (GNSS) has been a game changing step for navigation and geofencing applications. Available for civilian uses since 1983, personal navigation system has widened its access to the general public since 2004. But it is the adoption by smartphone manufacturer since 2007 that has made this technology ubiquitous. Today, it is indeed, the most used smartphone functionality after the internet access. 

However, GNSS based localization applications stop at the doorsteps of building: GNSS signal gets poorer, and the localization precision is too poor to find real life application. Whereas it is to find personal object at home, track assets within a factory, find your way in airport or secure and control access to restricted areas, indoor localization scenarios are becoming more, and several technologies have been developed to take up the challenge. None of them have taken over although some are currently being democratized in smartphone and it can be difficult to choose among the currently plethoric offer. Every year, researcher and engineers compete within the “Microsoft Indoor Localization Competition” to size up performances of their systems, observation of the wide variety of the chosen technological options gives a taste of the engineering complexity.  

Two main classes of solution exists whether or not it requires fixed hardware (anchors network) to which the system to be localized reference its position. Network-less solution are of course the cheapest to deploys but usually does not provide the best accuracy. Network base solution can provide centimeter level precision but are expensive for deployment and maintenance. As a general matter, the tradeoff between costs, precision and latency is backbone of the technological challenge. In this article we will review the different technologies available today, to help to understanding and choosing among the different solutions.

In this article, we will review the different indoor location algorithms available today, to help you understand and choose from the different solutions.

1. Proximity detection

Proximity based positioning methods estimate the position of the target by determining whether the target object is in the proximity to the reference point or not. This is achieved with the help of sensing mechanism, placed either at the reference point or at the target, specifically aimed at detecting the presence. Proximity detection is the simplest positioning method used for applications that do not require very high accuracy. 

2. Centroid Determination 

Position estimation using centroid determination method involves the calculation of the geometric center using the positions of multiple reference nodes within the detection range of the target node. This low complexity positioning method is easy to implement but it offers low accuracy as it only takes the proximity data into account and simply performs averaging of the coordinates to obtain the position of the target. Weighted Centroid Localization (WCL) is an improvement to the centroid determination method in which centroid calculation is influenced by weights that can be functions of signal strength or distances of each node. 

3. Lateration

Lateration is a position determination method using simultaneous distance measurements of the target from three or more reference nodes with known positions. Lateration based positioning method can utilize distance measurements from various ranging methods. After the distance measurements are available, the position of the target can be determined as the intersection of the circles or spheres formed with radii representing the respective distance measurement for each reference node and the geometric centers of the circles or spheres coinciding with the positions of reference nodes (Fig. 1). When the distance estimation is accurate, lateration offers very high positioning accuracy. 

schema tri-lateralisation method interior localisation algorithms
Figure 1 : Lateration method

4. Angulation

Angulation is similar positioning method to lateration, except it determines the position of the target by using the angle measurements relative to multiple reference points (Fig. 2) instead of distance measurements. Phased array antennas with direction detection capabilities are popular for angle measurements in the case of wireless signals. The position of the target is estimated at the intersection point of the lines formed using the angle measurements and passing through respective reference points (Fig. 2). Error in each angle measurement determines the error in positioning using this method as the lines formed using the angle measurements will not intersect at a single point (Fig. 2). 

diagram tri-angulation method indoor location algorithms
Figure 2: Tri-Angulation Method

5. Fingerprinting

Fingerprinting is a scene analysis-based positioning method which relies on the fingerprints obtained by the environmental survey. Fingerprinting is most often performed using Received Signal Strength Indicator (RSSI) of Radio Frequency (RF) signals5, although audio signals6, magnetic fields, visual information from images7 and combination of multiple observations from surroundings8 are also the quantities used for fingerprints. This method generally has two phases. First, is the calibration phase which is performed offline, meaning before deployment of the system. In this phase, a map is created using the measurements of the fingerprints over the operational area of the system. The second phase is online positioning phase. During this phase real time measurement of the fingerprint is compared with the offline measurements to predict the position of target. Buildings with an already existing infrastructure for technologies such as Wi-Fi and Bluetooth are examples where the fingerprint is interesting as a location method with low cost and low accuracy.  

6. Dead Recknoning

Dead reckoning is the process of estimating position of the target with the help of previously known or estimated positions and known or estimated speeds and sometimes accelerations over the elapsed time. Inertial Measurement Units (IMU), with motion sensors and rotation sensors are generally used for dead reckoning. IMUs can determine the position and speed of the target without external inputs. Inertial sensors can be designed in a Microelectromechanical Sensors (MEMS) technology and thus can be embedded in lightweight devices such as smartphones. The inaccuracy of the dead reckoning process is cumulative, thus the estimated position drifts from the actual position with increasing deviation as the time increases. The term Pedestrian Dead Reckoning (PDR) is often used in the field of indoor applications to indicate that the accelerometers have been attached to the body of the user. 

7. Map Matching

In the absence of positioning update due to reasons such as bad signal reception, the position estimated by an indoor navigation system, can be controlled, corrected, or updated using a map database. To find a correct representation of target’s position, certain elements of the map are associated with the characteristics of the target’s trajectory, which is called as Map Matching (MM). MM algorithms associate current positioning data with spatial map data to establish an accurate link between them, thereby improving positioning accuracy.  

8. Combination of Positioning Methods 

In the case of some positioning system architectures, more than one measuring principles or positioning techniques are used. For example, angulation can be used in combination with lateration to reduce the angle measurements required for estimating the position of the target or to improve the positioning accuracy. In addition to angle and distance measurements, other information such as proximity or various kinds of sensor data can be used to enhances the performance of a positioning system. Recently, positioning methods utilizing heterogeneous information1 and data fusion techniques21 are focus of research in the field of indoor positioning. 

How to choose the right indoor tracking algorithm?

Today, there are many indoor localisation algorithms offering more or less accuracy and requiring more or less costly investments depending on the network infrastructure. In order to choose the most suitable solution for your needs, it is important to define the level of accuracy you require in advance.

Vighnesh
Vighnesh Gharat
Software engineer
Specialized in indoor positioning at ELA Innovation in Montpellier, Vighnesh studied at Institut supérieur d’électronique de Paris (ISEP) where he received his Master’s degree in Electronics and Telecommunication in 2014. He received his PhD degree from Université Paris-Est in 2021. He completed his PhD under a CIFRE contract in a research collaboration with ELA Innovation, ESYCOM (UMR 9007 CNRS) and AlliansTIC on a Magneto-Inductive technology based ranging and positioning system. He is now in charge of research and development of interoperable RTLS solutions and is particularly interested in data fusion and machine learning techniques for indoor positioning.
Latest posts

Boost your
telematic project!

Discover how to monitor, track and secure vehicle fleets using Bluetooth sensors and beacons.

brochure transport et télématique mockup

ELA Innovation • All rights reserved

Contactez-nous directement en utilisant le formulaire ou cliquez sur le bouton ci-dessous pour faire une demande de devis :