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, speciﬁcally 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 inﬂuenced by weights that can be functions of signal strength or distances of each node.
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.
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).
Fingerprinting is a scene analysis-based positioning method which relies on the ﬁngerprints 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 ﬁelds, visual information from images7 and combination of multiple observations from surroundings8 are also the quantities used for ﬁngerprints. This method generally has two phases. First, is the calibration phase which is performed ofﬂine, meaning before deployment of the system. In this phase, a map is created using the measurements of the ﬁngerprints over the operational area of the system. The second phase is online positioning phase. During this phase real time measurement of the ﬁngerprint is compared with the ofﬂine 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 ﬁngerprint 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 ﬁeld 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 ﬁnd 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 ﬁeld 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.