An Overview on Position Location: Past, Present, Future

Abstract

Prior to the 21st century, positioning technologies had limited applications including air traffic control, air and sea navigation, satellite communications and related military uses. Today, positioning technologies have deeply merged with daily life and enabled many novel sensors, systems and services. For example, navigation systems are the enablers of road traffic prediction, assisted and autonomous driving, and several aspects of healthcare. They have also facilitated worldwide services provided by companies such as Uber and Lyft. In fact, in many aspects of modern life, localization systems are deemed essential to day-to-day living and are contributing to our general well-being, the economy, and security. Accordingly, position location technologies have become key components of many worldwide industries. These positioning technologies include the Global Positioning System (GPS), WiFi-based indoor localization, cell-phone based localization (including the fusion of GPS, cell-tower based localization and dead-reckoning), and inertial/dead-reckoning techniques. Tracking technologies are also considered key components for localization, as are the more recently integrated concepts of machine learning and artificial intelligence. This paper provides a review of the history of localization, the main technological enablers of localization and assesses the future directions of localization methods.

1 Introduction

The history of position location goes back to the original needs of mankind for navigation. In the early ages, heavenly bodies were considered a primary means for finding one’s approximate location. Later, a simple compass was used to enable navigation, especially for trade-inspired sea travel. With the emergence of airplanes and the requirements of modern military conflicts (specifically World War II), more precise location information was required. When mid-range airplanes were developed in the late 1930s, scientists of many countries including Germany, Italy, the UK and the US worked hard to develop the first radar systems. Originally, these radars were used for air surveillance, but soon found application in sea and ground surveillance and were installed on ships, airplanes and ground vehicles.

RAdio Detection And Ranging (Radar) was introduced as a system that uses the reflected radio waves from objects to detect those objects and estimate their ranges. While radar was originally considered for the detection and ranging of targets, advanced radars are now capable of extracting a large amount of information from targets such as their size, speed, and even type. These capabilities are essential to both military and civilian applications.

Building high power amplifiers was considered a key requirement for long range passive and active radar localization. Many radar technology historians consider the UK as the first nation to develop the magnetron. The magnetron was next introduced to the US National Research Lab (NRL) which created the first radar.

The earliest localization systems were developed in the early 20th century and were based on direction finding. Transmit beacons (which could include commercial radio stations) were placed at known locations. A plane or ship used a rotating antenna to measure the angle to the beacon and then used the principle of triangulation (see Sect. 2.4) to determine its position.

Another common air navigation method used during the first part of the 20th century is the A/N Beacon. This beacon transmitted morse code for “A” to the east and west while transmitting morse code for “N” to the north and south using an Adcock array. Because of the specific patterns used for those characters in morse code, a constant tone would be heard when the signal is received 45° of north or south [1]. This beacon could thus be used to determine the approximate angle to the beacon and provide an aid for air navigation.

LORAN (LOng RAnge Navigation) was a hyperbolic radio navigation system developed during WWII [2]. This system provided a range of 500 miles with an accuracy of tens of miles using two frequency bands at 1.85 and 1.95 MHz [2]. The system was initially used along the US and Canadian East Coasts. However, it was soon used extensively in the Pacific Theater of World War II. By the end of WWII there were 72 LORAN stations and 75,000 receivers.

LORAN-B was initiated by US Navy, but doesn’t appear to have ever been operational. LORAN-C originated with the US Air Force, taken over by the US Navy and then by the US Coast Guard in 1958. The system was first deployed in 1957 and provided for improved performance (hundreds of feet accuracy) and used a lower frequency band (90–110 kHz) [2]. Development/use of LORAN-C caused surplus LORAN units to be made available causing a rise in its popularity. The LORAN-C system served the 48 continental states, their coastal areas, and parts of Alaska until February 2010.

In 1959 the US Navy built the first satellite navigation system known as Transit [3]. The system used satellites in low polar orbits to locate submarines and used ten satellites. The basic principle was based on the Doppler effect and received signal’s Frequency-of-Arrival. The subs often had to wait hours to receive signals from the satellites due to the small number of satellites and their specific orbits. However, this system paved the way for modern GPS.

More advanced satellite-based navigation was achieved via Global Navigation Satellite System (GNSS) that is a general term for all types of Satellite-based positioning systems. Global Positioning System (GPS) [4], originally Navstar GPS, is a satellite-based radio navigation system owned by the United States government and operated by the United States Space Force [5]. GPS was introduced in 1973 but didn’t became fully operational until 1993 using a constellation of 24 satellites. The Russian Global Navigation Satellite System (GLONASS)—the GPS Russian competitor—became fully operational in mid 2000s. The European Union, India, Japan and China have also introduced similar systems that are set to become operational in near future. Today’s advanced air and sea navigation capabilities, as well as air, ground and sea traffic control systems would have not been possible without the emergence of GPS and radar. The original GPS technology is highly sensitive to jamming and also doesn’t work properly in indoor and downtown areas. Recently, GPS III technology has been introduced by Lockheed Martin that has three times better accuracy and up to eight times improved anti-jamming capabilities [6,7,8]. In addition, there is a new trend of providing positioning services through LEO constellations, which represent a concrete perspective for the new generations of space-based positioning. The European Space Agency is working to develop LEO-based GNSS systems. For example, Germany’s National Aeronautics and Space Research centre (DLR) is conducting R&D on the KEPLER constellation. In addition, numerous private companies are deploying LEO constellations that expected to provide positioning services.

Other devices such as Inertial Navigation Systems (INS) and their integration with GPS have enabled localization in GPS-denied areas such as tunnels or downtown areas. WiFi localization emerged in the 2000s for indoor geolocation and downtown applications and was soon integrated into smart phones [9]. Today, localization continues to advance as there is a desire/need for precise navigation and positioning for devices as diverse as automobiles and video games. Vehicular systems are envisioned to enable automated driving (i.e., self-driving vehicles) and road traffic control. These localization applications will feature technologies well beyond INS, GPS and microwave frequency localization. Key modern location technologies incorporate machine learning and artificial intelligence along with millimeter wave, imaging, and visible light localization to enable RF-free localization, especially in areas with complex propagation environments. RFID localization has enabled new applications and has supported giant suppliers such as Amazon, toll road payments and electronic identification.

Traditional Radio Frequency (RF) localization is based on the use of geometric positioning using measured distances or angles to known geographical markers. Such techniques are generally known as trilateration and triangulation respectively. Accordingly, the three main signal measurements include Received Signal Strength (RSS), Time-of-Arrival (TOA) and Direction-of-Arrival (DOA). RSS techniques don’t require precise and complex signal processing which are needed by TOA and DOA estimation, but typically offer less reliable positioning. Non-geometric localization methods are based on RSS, network localization, visible light, INS, and imaging technologies. Usually, these techniques are integrated with tracking methods such as Kalman Filtering and machine learning. The performance of TOA, DOA and RSS techniques are affected by the availability of line-of-sight (LOS) propagation between anchors and the device to be localized. Thus, non-LOS (NLOS) propagation scenarios must be detected and mitigated [10,11,12]. These scenarios are usually tackled via multi-node, network, or distributed localization methods. In addition, fusion of TOA, DOA and RSS measurements made across multiple nodes help enable localization in NLOS environments [11,12,13].

The emergence and progress of Smart Phones and the development of location-based applications has motivated WiFi localization methods [9]. Various RSS techniques have been developed and progressed by various vendors. The accuracy of RSS based localization depends on the selected path-loss models. This accuracy is improved by integrating RSS localization and Kalman Filtering techniques.

Hybridization or fusion of localization methods increases the localization performance. Fusion techniques introduced in the literature includes GNSS and INS fusion, specifically to offer high performance GNSS localization in urban areas, when line-of-sight with one or higher number of satellites is obstructed by buildings or other obstacles [14]. There are numerous other examples such as multi-node TOA-DOA fusion [15] and fusion Wireless Local Positioning Systems and STAR sensors for satellite localization [16], and multi-sensor data fusion for capsule endoscopy localization [16, 17]. Kalman filtering and its variations are among high performance multi-sensor fusion localization techniques (Chap. 5 of handbook [18]).

Clearly, the estimation accuracy of localization techniques varies with signal and data processing methods. Thus, recent advances in data processing and analysis, as well as machine learning support high localization accuracy. Moreover, the trend in mm-wave communications and massive multi-input multi-output (MIMO) systems is considered another avenue for advancements in localization technologies. This paper intends to review the trend of wireless localization techniques and standards within the last two decades and their impact on localization accuracy. The paper offers a narrative on the emerging trends in geometric and non-geometric based localization technologies.

The paper is organized as follows. Section 2 presents geometric localization via DOA, TOA, and RSS localization methods. The section introduces key measures for comparing these techniques and will highlight the impact of communication parameters on the accuracy of these localization techniques. In addition, this section introduces techniques, standards, and methods and their impact on localization accuracy. Section 3 presents non-geometric localization via fingerprinting. Section 4 reviews signal processing methods for NLOS identification and localization. Section 5 introduces collaborative localization methods. Section 6 summarizes tracking techniques for localization with space, aircraft, maritime, underwater and pedestrian applications. Section 7 presents machine learning methods used for localization. Section 8 reviews radar systems, Sect. 9 reviews RFID, and Sect. 10 reviews visible light localization. Section 11 concludes the paper.

2 Geometric Localization via DOA, TOA and RSS

Geometric localization techniques are mostly based on Radio Frequency localization. They use measured distances and angles to known geographical markers, and are called trilateration and triangulation techniques, respectively [19,20,21,22,23,24,25,26,27]. To enable geometric-based localization, the device to be localized should transmit a signal which is detected and used to estimate channel by multiple receivers at the geographical markers (sometimes called anchors). Alternatively, the anchors could transmit signals which are measured at the device to be localized. In these techniques, the main assumption is the known position of anchor nodes.

The three main signal measurements include RSS, TOA and DOA. Current WiFi localization methods are typically supported by RSS techniques, which require measurements made by at least three nodes, but benefit from additional measurements. RSS techniques don’t require precise and complex signal processing, while TOA and DOA estimation require complex signal processing methods. Since DOA techniques need directional antennas, the hardware component for DOA estimation is also complex. Research on channel estimation for TOA, DOA, and RSS measurement goes back to decades ago. However, research on exploiting trilateration methods goes back to 1990 and was partially triggered by GPS. This section reviews fundamental wireless positioning techniques that include RSS, TOA, and DOA. All these techniques need information extracted from a number of nodes to enable the process of localization. RSS and TOA techniques need the availability of at least three nodes for a process that is called trilateration. DOA method need the availability of at least two nodes. When higher number of nodes are available, more data can be incorporated to improve the positioning accuracy. TOA estimation is very sensitive to the availability of LOS.

2.1 RSS Estimation

Compared to TOA and DOA, RSS estimation is considered the least complex positioning method. However, RSS high performance estimation is hinged upon a good channel pathloss model between all WiFi access points or cell phone towers and any location or spot within the desired areas. Channel pathloss model for a given environment includes both deterministic and random components. The statistics of the random component is determined via numerous field measurements. In addition, the channel varies with time as the position of people and things are time varying. Within the last two decades, many algorithms have been developed to address the problem of random spatial and temporal behavior of channel model that impacts RSS precision. To address the impact of channel inaccurate modeling on the RSS-based position estimation diverse techniques such as fusions of higher number of observations and application of techniques such as Kalman Filtering. While RSS localization is still available in NLOS situations, but it is expected that the localization performance reduces.

In high performance RSS techniques, the transmitted power information is embedded in the transmitted package. This is essential to multiple access communications to avoid near-far problems that increases multi-user interference and reduces the detection performance. A receiver computes the received signal and compares it with the transmitted signal and then uses a pathloss channel model to compute its distance from the transmitter. More information on RSS localization methods have been provided in Sect. 3.

2.2 TOA Estimation

It should be highlighted that TOA estimation is an essential component of channel estimation that is required for all receivers. Without high performance TOA estimation, the detection performance of all receivers reduces. TOA estimation process that is used for the purpose of localization, includes two steps of coarse TOA (required for all receivers) and fine TOA estimation. Coarse TOA estimation is usually attained via a simple match filtering techniques while fine TOA estimation is achievable via advanced methods. Examples of these methods include blind source separation (BSS) such as independent component analysis (ICA), MUSIC or SPIRIT methods (Chaps. 8, 9 of [18]).

TOA estimation allows the measurement of range or distance; thus, enabling localization [28,29,30,31,32,33]. The process incorporates measurements made by multiple base nodes to localize a target node via trilateration [19,20,21,22,23,24,25,26,27]. It is assumed that the positions of all base nodes are known. If these nodes are dynamic, such as satellites in GPS localization, the position of nodes should be precisely computed to allow base-nodes to localize their positions (GPS-TOA positioning). In some circumstances, multiple base nodes may cooperate to find their own position before any attempt to localize a target node.

TOA estimation process would be affected by the availability of the LOS and the homogeneity of medium. Human body and underground are examples of inhomogeneous media. NLOS or obstructed LOS (OLOS) scenario could seriously reduce TOA estimation performance. In addition, TOA estimation process would be very complex in inhomogeneous media. High performance TOA estimation in inhomogeneous media requires proper selection of signal waveforms [16, 17, 29, 34, 35].

2D localization via TOA estimation requires measurements across three nodes. As highlighted in the introductory of the Handbook of Position Location [18], assuming known positions of base nodes, and a co-planar scenario, three base-nodes and three measurements of distances (TOA) are required to localize a target node (see Fig. 1a). In a non-coplanar case, four base-nodes are required. Using the measurement of distance, the position of a target node is localized within a sphere of radius $R_i$ with the receiver i at the center of the sphere (where, $R_i$ is directly proportional to the time-of-arrival $\tau _i$ as shown in Fig. 1a. The localization of the target node can be carried out either by base nodes using a master station or by the target node itself.

Fig. 1

Taken from [Chap. 1: [18]]: a Operation of TOA and RSS, b Operation of TDOA, c Comparison of TOA and TDOA Calculations, d Operation of RTOA, and e Operation of DOA

TOA estimation is the main driver for GPS. TOA estimation accuracy hinges upon fine timing synchronization across multiple nodes. In addition, TOA estimation requires the transmission of a time-stamp. The accuracy of fine timing synchronization as well as time stamp is critical to fine TOA estimation. Furthermore, TOA estimation accuracy is a function of available bandwidth. Higher bandwidths are available at higher frequency ranges such as millimeter wave (mm-wave). Higher frequency ranges allows higher bandwidth and accordingly finer timing estimation. Higher frequency ranges also enable implementation of bigger antenna arrays within smaller areas. Finally, TOA estimation accuracy is a function of hardware processing power and the clock pulse rate. As the clock pulse rate increases, the sampling rate increases and in general a high precision TOA estimation is expected.

2.3 TOA and Related Variations

A variation of TOA estimation is Time-difference-of-arrival (TDOA). We also may consider Round Trip TOA (RTOA) Estimation as a related variation of TOA and it is a solution to cross node synchronization. As the name suggests, TDOA estimation requires the measurement of the difference in time between the signals arriving at two base nodes. Similar to TOA estimation, this method assumes that the positions of base nodes are known [18]. The TOA difference at the base nodes can be represented by a hyperbola. A hyperbola is the locus of a point in a plane such that the difference of distances from two fixed points (called the foci) is a constant. Assuming known positions of base nodes and a co-planar scenario, three base nodes and two TDOA measurements are required to localize a target node (see Fig. 1b). TDOA addresses one drawback of TOA by removing the requirement of synchronizing target node clock with base node clocks. In TDOA, all based nodes receive the same signal transmitted by the target node. Therefore, as long as base node clocks are synchronized, the error in the arrival time at each base node due to unsynchronized clocks is the same.

As shown in Fig. 1c, TOA is the time duration (or the relative time) between the start time (ts) of signal at the transmitter (target node) and the end time (ti) of the transmitted signal at the receiver (base node Bi). However, as shown in Fig. 1c, TDOA is the time difference between the end times (t_i and t_j) of the transmitted signal at two receivers (base nodes B_i and B_j). Thus, in TDOA technique, only base nodes’ clocks need to be synchronized to ensure minimum measurement error. In general, the complexity of target node clock synchronization is higher compared to base node clock synchronization.

In RTOA, the localizing Node 1 transmits a signal that is received by all surrounding nodes, e.g., Node 2. Next, Node 2 responds to the transmitted signal and provides the time of arrival and departure (or time stamp) information of signal to Node 1. Node 1 calculates the distance from Node 2 through a comparison across the time of transmission of its signal to Node 2 and time of reception of the signal from Node 2 along with information received from Node 2 (Fig. 1d). Clock synchronization and time stamp information is needed in this technique. Wireless Local Position Systems (WLPS) is an example of localization systems that incorporate round trip TOA estimation for localization [36,37,38,39,40]. WLPS has diverse applications in security, autonomous driving [41], UAV localization [42], satellite localization [43].

In WLPS, the localizing Node 1 is called Dynamic Base Station (DBS) and the localized Node 2 is called transceiver (TRX). Usually DBS is an expensive component of RTOA and TRX is considered very simple and low cost. Thus, in practice DBS can be installed on limited number of mobiles while TRX can be installed on a large number of mobiles. Installation of TRX on a large number of soldiers in battlefields to enable their localization via vehicles or commanders is an application of WLPS. This specific application avoids bombardments of friendly soldiers in battle field setups. Installation of WLPS on vehicles can be a key components of future self-driving vehicles.

2.4 DOA Estimation

In DOA estimation, base nodes determine the angle of arriving signal (see Fig. 1d). To allow base stations to estimate DOA, they should be equipped with antenna arrays, and each antenna array should be equipped with RF front-end components. However, this incurs higher cost, complexity and power consumption. DOA-based localization requires at least measurements made across two nodes.

DOA estimation usually incorporates an antenna array. However, many tracking Radar systems historically use reflector antennas for DOA estimation. Reflector antennas along with RF feeders enable transmission of high power pulses and accordingly surveillance of longer ranges in space, land or sea. Antenna arrays enable electronic steering of beampattern allowing rapid switching across different directions. Antenna arrays include a number of antenna elements.

Similar to TOA estimation, in DOA estimation, the positions of base nodes should be known. However, unlike TOA and TDOA, for the known position of a base node and a co-planar scenario, only two base nodes along with two DOA measurements are required. For a non-coplanar case, three base nodes are required.

Antenna dimensions are determined by the frequency range: the higher the frequency, the smaller the antenna dimensions could be. DOA estimation has applications in airport Instrument Landing Systems (ILS), and airplane Radio Direction Finding (RDF). DOA estimation is also used in radar-based localization.

2.5 Localization Performance Key Metrics

Two localization error key measures include probability-of-error and Cramer-Rao Lower Bound (CRLB) (Chap. 2 of [18]). Probability-of-error is computed based on the error Probability Density Function. It indicates the probability that the location measurements fall within a specific region, and includes three categories of Linear Error Probability (LEP), Circular Error Probability (CEP) and Spherical Error Probability (SEP). For a one-dimensional location measurement (e.g., range measurements made by a single node), the region is a line and the probability-of-error measure refers to LEP. For a two and three-dimensional (3D) localization, probability-of-error measure refers to CEP and SEP, respectively. CRLB is another measure of localization performance, which represents the minimum possible variance of error in the estimation of a parameter such as TOA or DOA. Based on the nature of localization method, either probability-of-error, CRLB, or both might be used to evaluate the performance. For example, GPS offers the global location in space, thus, SEP can be used to evaluate GPS performance. Moreover, GPS is based on TOA estimation, and CRLB can be used to evaluate GPS TOA estimation error. Tracking radars may also use SEP or CEP (based on the nature of Radar) to evaluate the localization performance.

3 Non-geometric Localization via Fingerprinting

The most natural way to obtain location information is through geometric relationships to anchors using RF signal-based measurements, as discussed in the previous section. However, in this section we present an overview of non-geometric positioning techniques, since geometric techniques are not always feasible. Specifically, we are interested in localization scenarios that cannot rely on geometric techniques due to the high prevalence of non-line-of-sight conditions and heavy multipath propagation [18, 44, 45]. One such scenario is indoor environments. In these scenarios, localization has relied on so called “fingerprinting” techniques in which RF signal parameters (often Wi-Fi based) are measured at known locations and stored in a database. These RF fingerprints and the recorded location are stored in this database for later retrieval. Specifically, a device wishing to determine its position, will measure the RF signals in its local environment and send a query to the database. The database is then used by pattern-matching technique to determine the location of the device [45, 46]. Such techniques have been developed since the early 2000s [44].

There are three primary design aspects to such non-geometric (fingerprinting-based) localization techniques [18]: (a) the measurements used, (b) the database structure employed in which those measurement-location pairs are held, and (c) the position estimation technique employed (e.g., pattern matching). We will discuss each aspect in turn in this section.

3.1 Measurements Used for Fingerprinting

Localization based on fingerprinting usually consists of two phases: (1) the offline portion (creating the database); and (2) the online phase (exploiting the database). The measurements (i.e., fingerprints) taken at each location depend on the type of device that may use the resulting database. For WiFi-based positioning, RSS is the primary measurement, although temporal patterns are also used as is channel state information [45, 47]. However, cellular-based systems fingerprinting techniques can exploit any measurement taken by the mobile or RAN [18]. The key is that the measurement must be unique to a location and relatively constant. If multiple locations have the same fingerprint, the localization technique cannot be certain which location is the true location (although temporal/history data helps here). Further, if the fingerprint changes over time, it will also be difficult for the localization technique to determine position based on the measured fingerprint without constant database re-calibration.

Examples of measurements used for fingerprinting include RSS, round-trip delay, direction-of-arrival, power delay profile, and channel state information. Typically, the mobile records these measurements on signals transmitted by anchors, although location systems can work the other way as well (anchors taking measurements of signals transmitted by the mobile). Additionally, like geometric techniques, performance is improved if the measurements are taken from/at as many anchors as possible.

3.2 Database Structure

A second important aspect of fingerprinting techniques is the database. After offline measurements are taken (along with the location at which they were taken), the measurements are placed into a database for future use. The structure of this database can either be a uniform grid where all reference coordinates are evenly spaced in the (x,y) plane or if that is not possible, in an indexed list [18]. If uniform spacing is used, the spacing dictates the resolution of the localization technique, although interpolation is often used [48]. Note that the location tied to the measurement can be obtained by GPS when available, but more often must be manually entered since the absence of GPS often motivates the need for fingerprinting techniques.

In addition to explicit measurements, propagation models are also often used to populate the database. While measurements are more accurate, they are also very time-consuming and suffer from the drawback that they must be retaken whenever there are major changes to the environment or the anchor upon which the measurement is based. Databases that rely on propagation modeling have an advantage in that they can be updated very quickly. Of course, their accuracy can be poor in complex propagation environments.

Of course, the two modalities can also be mixed [48]. Specifically, propagation models can be used to initially populate the database. Measurements are then taken and used to replace the model-based points and interpolation can be used to smooth out the differences [48].

3.3 Position Estimation

The final aspect of fingerprint-based techniques is the position estimation technique. In other words, as a device is moving through an environment, new measurements are taken and compared to the database in order to determine the position of the device. The specific means for determining that position estimate is crucial in the overall performance. A common approach is to use K-nearest neighbors (KNN). With KNN a weighted average of K locations from the database are used to determine the unknown location. These K locations are weighted with the inverse of the Euclidean distance between the observed RSS measurement and the K-nearest training samples [49].

A second popular approach is the use of support vector machines [50]. A support vector machine uses kernel functions to overcome the incompleteness and inaccuracy of the RSS (or other) measurement values, but suffers from higher computational complexity.

Thirdly, neural networks (including deep neural networks) have also been employed. Neural networks utilize the backpropagation algorithm to train weights relying fingerprint/location pairs (i.e., labeled data) in the training phase as a form of supervised learning [46].

In any pattern-matching approach, some form of search space reduction technique must be applied. This is due to complexity reasons. Consider a database with 40,000,000 measurements. Performing pattern-matching over that entire database would be impractical. Thus, before pattern-matching, we must first reduce the size of the search space. One common approach is known as filtering [18]. The filtering step is often performed in a series of steps. For example, the first step might limit the search space to all fingerprints that contain the anchor with the largest RSS value. If this is the only measurement used, this may be the only filtering step. However, if there are other measurements taken, they can be used to additionally filter the search space. In addition to filtering, the genetic algorithm has also been proposed to reduce the search space.

4 Signal Processing Methods for NLOS Identification and Localization

This section presents algorithms for Non-Line-of-Sight (NLOS) identification and localization [13, 15, 51, 52]. In NLOS scenario, a positive bias is added to TOA or range measurement, and DOA error due to NLOS can be positive or negative, which is not small. The NLOS error greatly degrades the performance of localization algorithms depending on the fusion of TOA and/or DOA measurements [18, 53, 54]. In NLOS scenario, (1) the NLOS measurement(s) can be detected and discarded when LOS measurements are enough for localization [54]; (2) NLOS measurement can be detected and used for localization after calibration [55,56,57], (3) the NLOS impact can be reduced by a weighted summation of multiple estimations obtained using multiple sub-sets of measurements [58], and, (4) the shared reflection points can be localized via DOA fusion and then localize the target with shared reflection points and TOA fusion [11].

The NLOS identification algorithms can be built upon the received signal’s characteristics including TOA statistics [59,60,61,62], RSS statistics [61, 63, 64], root-mean-squared delay spread (RDS) [61, 62], phase statistics with multi-antenna [13, 65], channel diversity [63, 66], and the combination of multiple parameters [61, 63, 67]. Various techniques have been developed for the process of discriminating LOS and NLOS signals.

In NLOS scenario, a positive bias is added on the measured range/TOA. The bias is not a constant value due to the target movement. This leads to a larger TOA standard deviation (or variance) than that of a TOA measured in LOS scenario [53]. TOA standard deviation (or variance) is used in [59] for LOS and NLOS discrimination. In addition, due to the random positive bias in NLOS TOA, the TOA distribution is not symmetric around the true TOA and not as sharp as that is obtained in LOS scenario. Thus, TOA distribution’s Skewness (measure the asymmetry of a probability distribution of a real-valued random variable about its mean) [60] and Kurtosis (measure the sharpness of the peak of a random variable distribution curve) [60, 62] tests can be used for NLOS identification, and Shapiro-Wilk and Anderson-Darling tests can be used to determine if the TOA distribution is a normal distribution with limited number of samples [60]. Ultra-wideband (UWB) signals possess higher temporal resolution, the delay spread of the received signals can be obtained and acts as a parameter for discriminating LOS and NLOS signals [61, 62].

In NLOS case, the received signal’s power is much weaker than the one obtained in LOS scenario, and the statistics of RSS can be applied for NLOS detection. In [61], the RSS distribution parameters are applied to discriminate LOS and NLOS. The Skewness of the dominant path power distribution is applied to detect NLOS signal in [63].

The dispersion of the received signal energy over time by the channel, which is named RDS, can be obtained when the channel sampling rate is high, such as in a wideband system. In the RDS calculation, the multipath components whose amplitudes are within a certain threshold of the strongest component are retained. In LOS case, the LOS component is the strongest one, and some strong NLOS components will be retained. This leads to a small number of retained multipath components and a small RDS. While in NLOS case, the strongest component is much weaker, and a large number of NLOS components will be retained (a large number of multipath components and a large RDS). Thus, RDS can be used for NLOS identification [61, 62].

In LOS only condition, the phase difference between two receiving antennas is a constant. In LOS dominant scenario, the phase difference is contained by multipath signals, but it still centers at the LOS phase difference. While in NLOS condition, the phase difference between two receiving antennas is a random variable. Thus, the statistics of the phase difference between two receiving antennas can be used for NLOS identification [13, 65]. The channel fading is relatively flat in LOS dominant scenarios and more frequency-selective in NLOS dominant scenarios for the richer multipath superposition, especially when the receiver has a position displacement in the data collection process. Thus, the channel diversity [63] and channel correlation [66] can be applied for NLOS identification.

Usually a single parameter for NLOS identification does not perform very well. Thus, multiple parameters are combined to obtain a better performance. In [61], NLOS identification using TOA, RSS, RDS and their combinations are evaluated. When the exact distance information is available, the combination of TOA, RSS and RDS for NLOS identification obtains the best performance, but when the exact distance is not available, the RDS based method is most successful. In [63], when skewness of dominant path power distribution and kurtosis of frequency diversity variation distribution features are combined for NLOS identification, it beats any single feature. RSS and channel state information (CSI) in OFDM system are input to a recurrent neural network (RNN) model for NLOS identification [64]. In [67], statistic parameters computed from RSS and range estimates are taken as input features to the Machine Learning (ML) algorithms for NLOS identification.

The above algorithms apply received signals characteristics to identify NLOS signals. In the localization process, the detected NLOS measurement(s) can be discarded (if there are enough LOS measurements for localization [54]), or used after proper processing including (1) rank the NLOS error and select NLOS measurements with small errors [66] and (2) calibrate the NLOS measurement(s) error [59]. There are also other algorithms to mitigate NLOS impact on localization performance. In [58], it is assumed that there are more than necessary base nodes for localization. The base nodes are divided into multiple subsets, and each subset obtains one estimation of the target position. The range residual (the difference between measured range and calculated range (between estimated target position and base nodes’ positions)) is applied to weight the target position estimations, and the weighted summation of these estimations reduces the NLOS impact. In [11], DOA fusion is first applied to estimate the target position, and then the NLOS measurements is detected using the TOA and estimated target position. If there is no LOS measurement, the shared reflection points (localized via DOA fusion) and TOAs are used to localize the target.

5 Collaborative Localization

While traditional localization techniques rely on measurements between anchors and the device to be located, in recent years, a new paradigm for localization has emerged. This new paradigm, described in this section is termed collaborative (also cooperative or network) localization. In collaborative localization [68,69,70,71], localization is supported by using measurements between nodes requiring localization in addition to measurements between anchors. These additional measurements provide improvements both in terms of localization coverage and accuracy. An interesting aspect of collaborative localization is that while it has been studied for several years, it may take on new importance as it can be directly combined with device-to-device (D2D) LTE and 5G communication [72, 73]. In addition, collaborative GNSS solutions are under research and development [74,75,76].

The benefits of collaboration between nodes requiring localization have been studied both theoretically (via CRLB) and algorithmically in the existing literature. These benefits can be described in terms of both reduced localization error and improved localizability (i.e., coverage). This can be understood through the example shown in Fig. 2. In traditional localization, the source nodes (those seeking to be localized) typically require a minimum of three connections to anchors in order to be localized [18]. In the figure only one of the source nodes (out of nine) has sufficient connections to anchors to perform traditional localization. However, with collaborative localization, nearly every node in the graph is localizable using an appropriate collaborative localization technique, highlighting the coverage benefit. Additionally, even the one node that is localizable without collaborative localization can improve its location estimate through the extra connections (i.e., constraints) highlighting the performance benefit.

Analysis based on Fisher information has shown the general benefit of collaboration between nodes [77], the scaling of the benefits of collaboration with network size [78, 79], the impact of anchor placement [80], and the impact of neighbor selection [81]. In addition to insights based on Fisher information, many localization algorithms have been developed [68, 71]. However, despite the theoretical studies indicating clear benefits of collaborative localization and the development of many practical algorithms, there have been few actual deployments. This is mainly due to the the deployment of ad-hoc networks (which would benefit the most from collaborative localization) is still notoriously hard. This is especially true for techniques which rely on time-based distance measurements.

Fig. 2

Collaborative localization

The basic problem to be solved in collaborative localization can be developed assuming Gaussian noise corrupts the measurements between pairs of nodes $\mathbf{y}$. More specifically, the Maximum Likelihood solution can be shown to be equal to a weighted least squares solution of the following:

$$\begin{aligned} \begin{aligned} \hat{\mathbf{x}} = \arg \min _\mathbf{x} \sum _{i=1}^N&\left\{ \sum _{ j \in \mathcal{A}_i } \frac{1}{\sigma _{ij}^2} \left( y_{ij} - || \mathbf{x}_i - \mathbf{x}_j || \right) ^2 \right. \\ {}&+ \left. \sum _{ k \in \mathcal{N}_i} \frac{1}{\sigma _{ik}^2} \left( y_{ik} - || \mathbf{x}_i - \mathbf{x}_k || \right) ^2 \right\} \end{aligned} \end{aligned}$$

(1)

where $\hat{\mathbf{x}}$ is a vector of the estimates of all node positions $\mathbf{x}$ and $\sigma _{ij}$ is the standard deviation of the noise in the measurement $y_{ij}$ between nodes i and j . Clearly this is a non-linear, non-convex optimization problem and does not have a closed-form solution, although it can be solved using classic gradient descent using either using a centralized or distributed approach [70]. The difficulty to this approach is that in order to find the true global minimum, an appropriate starting point is required. Otherwise a local minimum is reached which may be far from the true solution.

The global minimum can be reached using a branch-and-bound (BB) solution search strategy, coupled with the reformulation linearization technique (RLT) [82]. This however can be highly complex which leads to a desire to find sub-optimal methods such as convex optimization using convex approximations of the original objective function. Other slightly less complex approaches (e.g., stochastic search techniques [83]) which can find the global optimum with high probability have also been developed.

Sub-optimal algorithms for solving this collaborative localization problem can be categorized in several different ways. However, we the following dichotomies are often used [18, 68]: (a) Measurement Type; (b) Centralized vs. Distributed; (c) Sequential vs. Concurrent; and (d) Bayesian vs. One-Shot.

With respect to measurement type, all typical measurements used in traditional localization have been used in collaborative localization . These include received signal strength, angle-of-arrival, and time-of-arrival [18, 68]. Additionally, in high density scenarios connectivity-based localization algorithms have also been proposed [84,85,86]. In addition to measurement type, algorithms are developed as both centralized and distributed approaches. For example algorithms developed in [69, 87, 88] are centralized approaches whereas those in [89,90,91] are distributed. Sequential approaches perform localization sequentially where nodes with sufficient connections determine their positions and then serve as anchors to other nodes [92]. Concurrent approaches can be distributed or centralized, but in either case allow all nodes to simultaneously determine their position [91].

6 Tracking

The target tracking processes has two important procedures: the sensor which could either continuously localizes the target or receives the signal from target, and the algorithm which process the information provided by the sensor and continuously track the movement of the target. Different sensor uses different method for tracking purposes. For example, two-way TOA [93] is being used by active radar, active sonar and laser retro-reflectometer, while TDOA or DOA is being measured via sensor-array such as wireless receiver array or microphone array during the tracking process.

On the other hand, he RSS based target tracking method consists of either directly measuring the received signal power of each sensor [94] or implementing the signal search and fusion algorithms through the sensor array such as multiple signal classification (MUSIC) [95], diagonal unloading (DU) [96] or steered response power (SRP) [97]. Also, video [98] and infrared camera [99] have been used for indoor and outdoor object tracking by integrating the machine learning (ML) algorithm into the target tracking process. In typical, image processing technique is applied into each or multiple video frame(s) for object detection and classification purpose [100], then the object tracking algorithm will be applied.

The history of sensor-based target tracking could be backtracked to early 1900. Before 1960, researchers were focusing on the sensor development and implementation. For example, extensive research and development on submarine detection and tracking methods have been conducted during 1910s, especially via the underwater acoustic sensor [101]. The underwater acoustic sensor, known as hydrophone [102], was successfully developed a decade later.

Similarly, the radar development gains much of researcher attentions during 1920s, because it is capable of providing target detection and tracking, which is located at hundreds of kilometers away from the radar station. During 1935, the first aircraft tracking by radar has been successfully demonstrated [103]. The development of radar continues after the world war 2, because it also serves as an important tool for missile detection and tracking purpose [104]. The superior performance of radar is further verified when Soviet launch their first satellite to space, which the radar could detect and track an object 500km away from the station [105].

The Kalman filter (KF) was introduced by RE Kalman during the early 1960 [106]. Since then, researchers had been focused on the algorithm development for target tracking applications, especially the KF-based algorithm implementation [107, 108]. Over the years, various KF have been introduced in research community for target tracking application. The Generalized KF (GKF) was introduced to address the relationship between estimation error and lateral discontinuity issue in underwater target tracking application. The GKF uses a weighting matrix in loss function evaluation to overcome the particular issue [109]. As the digital computation performance significantly improves over the last two decades, a higher complexity KF, such the unscented KF (UKF) [110] and ensemble (EnKF) [111] become the potential candidate for nonlinear target tracking algorithm. Both UKF and EnKF avoids the linearization process of observation model during the update process. Furthermore, various sigma point transformation methods have been developed for UKF algorithm. These include the spherical simplex transformation method [112], randomized transformation [113], cubature KF [114] and square-root based KF [115]. While the computing technology today allows high complexity KF algorithm, such as UKF and EnKF to be implemented target tracking in application, however, the development of low computational cost KF based algorithm still remains an interest among researcher. Especially for the target tracking application where either high complexity signal processing on received signal is required or limited computation power available in the microprocessor. As such, researchers have introduced several low cost KF, these include weighted measurement fusion based KF [42] and weighted optimization-based distributed KF [116] algorithms.

The tracking algorithm development does not only evolve around the KF based algorithm. Bayesian filter and Gill-Murray Modified Gauss-Newton method have been introduced as an alternative target tracking algorithm since 1989 [117, 118]. On the other hand, $\upalpha$-$\upbeta$ filter is one of the popular tracking algorithms to track the high-speed maneuvering target such as aircraft and missile [119]. In addition, Probability Hypothesis Density filter has been introduced as a tool to simultaneously track multiple targets in real-time [120]. Also, the particle filtering has become a popular tracking algorithm for nonlinear system application. It has been widely implemented in signal processing-based tracking problem [121]. Furthermore, the optimization algorithm and estimation algorithms fusion-based algorithm has been widely considered among researcher. For example, [122] integrates the PF into particle swarm optimization to simultaneously track two speakers in a room.

Also, it is not guarantee that the source will continuously transmits the signal, and outlier could exist in measurement. Therefore, hypothesis-based target tracking algorithm has been introduced since 1986 [123], to determine if the measured data is associated with the particular source. The hypothesis method has been integrated with different estimation algorithm such as interacting multiple model (IMM) KF [124], particle filter [125] and Gaussian mixture filter [126] for various applications which includes the missile and acoustic source tracking.

6.1 Space Object

The global navigation satellite system (GNSS) has been well known as the major positioning system for land, sea and air tracking application. However, the phase array radar remains the primarily instrument for space objects tracking purposes. Currently, the North American Aerospace Defense Command (NORAD) tracks all the natural and man-made satellite in space, and updates the satellite orbit information in space object catalogue daily. The space object catalogue website is accessible by public. The accuracy of satellite orbit provided byin space object catalogue is typically less than 5 km error for prediction near the epoch, and gradually degraded to 15 km error or higher over the 15 days [127]. However, the increment of tracking error up to 15 km has very low impact on the ground station tracking performance for telemetry and telecommand purposes.

A higher tracking accuracy can be achieved via laser retro-reflector device, which is equipped on the satellite. It is achieved by measuring the TOA of laser beam emitted from ground station to the satellite, and reflected back to the ground station. The high accuracy laser tracking is typically provided by International Laser Ranging Service via their satellite laser ranging ground station network [128].

6.2 Aircraft

The radar has been the primary device to track an aircraft. Although the modern aircraft is equipped with GPS receiver, the primary function of GPS receiver is to assist pilot in navigation when the aircraft is out of the radar communication range. To fully utilize the aircraft localization information via the GNSS for tracking purpose, an alternative position and heading broadcasting method, known as the automatic dependent surveillance-broadcast (ADS-B) system was proposed during 1990s. The aircraft is required to periodically broadcast the ADS-B message to surrounding, which the ADS-B message contains both the position and velocity vector of the aircraft. The ADS-B signal was aimed to be received by satellite constellation, in order to achieve global aircraft tracking. However, the ADS-B signal broadcast by aircraft primarily received via terrestrial base station during the past two decades. The first ADS-B space demonstration only achievable in 2013 by PROBA-V [129] while the ADS-B constellation is only achieved via the hosted payload on IridiumNext constellation [130], which was launch between 2017 to 2019.

6.3 Maritime

Radar remains the primary tracking device in maritime application. Alternative tracking method has been considered, which includes the satellite image, synthetic aperture radar (SAR) image and automated identification system (AIS) based tracking method. The AIS is similar to ADS-B but it is specifically designed for maritime application, where the vessel periodically broadcasts its location and heading direction to surrounding. Both radar and AIS are capable of providing the real-time tracking of the maritime vessel. On the other hand, the satellite and SAR images are often used for data matching [131, 132], together with the radar and AIS data [133], to identify and track the maritime vessel which is conducting the illegal activities [134]. Currently, a new location broadcasting system, known as very-high-frequency (VHF) data exchange system (or VDES) [135] is under development and testing. The VDES contains three subsystems which includes the AIS, an application specific message (ASM) channel to reduce the AIS channel’s load, and a high rate communication channel between vessels, satellites and stations.

6.4 Underwater

Submarine tracking is considered to be the first target tracking application in the history. The weaponized submarine during late 19th country becomes a major threat to maritime in each country. Since then, numerous submarine tracking methodology has been proposed, such as buoyancy method [136] and acoustic method (or known as hydrophone) [101]. The first hydrophone in array was successfully test in 1920s [102]. In addition, a similar detection and tracking technique has been applied for torpedo tracking to reduce the threat from underwater during war time. With the introductory of KF during 1960s, it has been shown that it is possible track the underwater torpedo in real-time [137].

The underwater tracking does not limited for military application purpose. Instead, the underwater tracking has been extensively used in marine life research. The marine lives are being tracked to understand their biology behavior such as seasonal movement pattern, growth, survival and etc. In typical, the marine life tracking involves an acoustic tag, which is attached on the marine life itself [138]. In [139], hydrophone array is installed at seafloor to receive and track the signal which is transmitted by the acoustic transmitter. In addition, automated underwater vehicle with hydrophone installed has been utilized for marine life tracking instead of installing the fixed hydrophone at various locations. Although radiofrequency-based fish tracking method has been investigated during 1978 [140], but the acoustic signal remains the major tracking source due to the reason that the electromagnetic wave has a poor performance in underwater environment [141]. On the other hand, the non-destructive tracking method has also been considered among the marine biologist, which is the underwater camera based marine life tracking method [142].

6.5 Pedestrian

Since 1990s, researchers have been exploring the indoor and outdoor pedestrian target tracking problem. Pedestrian (or human) tracking remains the most challenging target tracking topic. Unlike the wireless sensor devices, the human does not broadcast signal with specific ID code and time stamp. Thus, tracking method that requires time-stamp or ID information, such as the TOA (both one-way and two-way) is not applicable. Instead, smart devices, wearable devices or passive-sensor based tracking method have been developed to assist in pedestrian tracking application over the past few decades.

The availability of microelectromechanical systems (MEMS) sensor creates opportunity of smart and wearable devices development for target tracking application. Majority of the wearable devices-based target tracking are focusing on the step-count related tracking. For example, the motion of pedestrian is tracked via the doppler shift of a buzzer’s signal which both transmitter and receiver are installed on the boot [143]. On the other hand, the pedestrian dead reckoning (PDR) system [144] which consists of a MEMS inertia measurement system (IMS) (includes gyroscope, accelerometer, pedometer and magnetometer), is one of the most popular method among the researchers in both indoor and outdoor pedestrian tracking application. For indoor pedestrian tracking, the PDR primarily uses the IMS data to track the pedestrian movement. For outdoor tracking application, the PDR fuses both the GNSS data and IMS data to achieve high tracking accuracy performance [145]. The IMS sensors are used to estimate pedestrian’s step length and heading direction. Due to the fact that the step length varies greatly among each pedestrian [146], the step length is generally estimated based on the velocity measurement output from the IMS [147], which generally contains bias and error. Typically, the zero velocity update (ZUPT) algorithm is implemented in PDR. The ZUPT resets the velocity measurement whenever the pedestrian’s foot is step on ground for short interval. The purpose is to minimize the accumulative tracking error in the PDR system [148].

The passive device is defined as the device that does not actively transmit any signal to the target, and require the target to return a response signal. Instead, it captures any possible signal that is transmitted by the target. Example devices include the video camera, infrared camera [99] and acoustic sensor. The image-based tracking algorithm generally integrated with machine learning algorithm for feature extraction and human recognition [100] purpose. Therefore, the image-based tracking is a multi-step target tracking process. On the other hand, the acoustic sensor consists of either microphone array or acoustic vector sensor (AVS) to capture the speech sound of human. The microphone array could be a linear array [122] or circular array [149] that each microphone collaboratively performs the beamforming to estimate the direction of the sound source. The AVS is a small sensor device that could provide the DOA of the acoustic sound source as measurement [150]. Also, additional signal processing algorithm is often implemented into the single/multi source detection process, such as track before detect [151], Gibbs-generalized labelled multi-Bernoulli filtering [152], random finite set method [153] to achieve a better speech source tracking accuracy performance.

While the primary purpose of target tracking is to continuously locate an object, however, it also serves as the purpose for situation awareness, and aiding in system analysis. The primary purpose of pedestrian and moving object tracking in self-driving car is to predict the possible movement of pedestrian (or the object) to avoid any possible collision [154]. In biomedical field, the tracking of endoscopy capsule movement within human digestive system has been a focus study. Various endoscopy capsule tracking strategy has been study in literature, which include the RSS [155], TOA, TDOA [17] and DOA [16] based tracking method. The successfulness of the endoscopy capsule tracking could lower the required image processing time taken by the medical personal, such that the medical analysis results could be delivered to patient in shorter timer period. On the other hand, acoustic based tracking system has been recently used to track and study the behavior of animal movement in the farm during the feeding and sleeping period [156]. The tracking system could help the farmer to identify any sick animal.

7 Machine Learning/Artificial Intelligence Techniques for Localization

Machine learning (ML) and artificial intelligence (AI) has gained much attention in various research fields in recent years due to its promising performance on complicated problems. Different from the traditional analytic methods, ML first uses massive data to train a model and then applies to localization. This section aims to shed light to the evolution of ML techniques for localization within the last two decades.

ML based localization algorithms can be classified into two categories based on their applications that include: (1) An algorithm incorporates channel measurements to directly determine users’ location, and (2) An algorithm estimates the channel parameters (e.g. channel gain, delay and angle information), which can be applied to localization in a straightforward way [157].

For the first category, the channel fingerprint contains position information, which can be exploited using neural networks (NN) [158], convolutional neural networks (CNN) [159], and Weighted K-Nearest Neighbor (WKNN) [160] to determine user/node localization. For the second category, NN is used to estimate parameters of static MIMO channel [161,162,163] and dynamic MIMO channel [164]. A data-driven deep neural network (DNN) approach is proposed in [165] for node localization via the lower frequency spectrum. Authors in [166] propose a supervised machine learning approach based on Gaussian Process Regression (GPR) for distributed localization in massive MIMO systems.

As mentioned earlier in the paper, many localization techniques are based on triangulation methods in Euclidean geometry. These techniques utilize geometrical properties of sensors to infer locations. ML algorithms can work directly on the natural (non-Euclidean) coordinate systems provided by sensor devices. ML algorithms exploit the topology implicit in sets of sensor readings and locations in the construction of possibly non-Euclidean function spaces for the estimation of unknown user locations, as well as channel parameters, which in turn, are used for localization. Here, a set of beacon (anchor) nodes are used to provide a training data for a learning procedure. Beacon nodes are nodes with known locations. The result of the learning procedure is a prediction model that is used to localize nodes/users with unknown positions. Beacon nodes are also used in non-ML approaches to extrapolate unknown node/user locations.

Mostly, ML algorithms model localization problem as a classification or regression problem [167], namely classification based and regression based localization.

Both approaches include two phases: (1) Training phase, and (2) Prediction phase. In training phase, training data are used for ML algorithm(s) to learn an underlying correlations among training instances. The training data for localization consists of feature vectors associated with beacon nodes, also known as predictor variables, and their known location coordinates, also known as predicted variables. The feature vector of every beacon node includes an n-tuple some measurement such as RSS values for signals received from other nodes or distances to other nodes as measured by that beacon node. Here, n denotes the number of users minus one. During this training phase, an ML algorithm essentially fits a statistical model on the training dataset. This is realized by determining optimum values of a set of parameters defined by the model. This model is used in prediction phase as a trained model. The prediction phase involves estimating location coordinates of nodes/sensors/users via the trained model. Note that a user can be localized if its own feature vector, i.e., its n-tuple measurement, has a same composition with those of nodes in the training phase. This feature vector is used as input for the trained model. The model predicts the location coordinates of the user as its output. Note that the model parametric values remain unchanged as the model estimates location of nodes/users. Thus, the order of nodes/users being localized has no impact on their estimated locations. This feature provides more flexibility compared to traditional trilateration-based progressive localization algorithms that their localization performance depends on the order of users being localized. Trilateration is a geometrical technique that can locate an object based on its Euclidean distances from three or more other objects.

In summary, both classification and regression based localization work as follows:

• (1) Beacon nodes communicate with each other to obtain pairwise N-dimensional vectors, where, N denotes the number of beacon nodes. A pairwise feature is something that can be calculated/obtained based on the system. For instance, for a small network of sensors, it can be signal-strength/distance between two beacon nodes/sensors. Thus, each beacon node build its corresponding pairwise vector whose elements are its signal-strength/distance to other beacon nodes.

• (2) One beacon node is chosen as a head beacon. First, it collects all pairwise vectors from beacon nodes. Next, it runs a learning procedure which is a regression or classification. This procedure leads to a trained model. This trained model will use for prediction of locations. The head beacon broadcasts this trained model to all nodes/users in the network. In addition, each beacon node broadcasts a simple message such as “Hello” to all nodes/users.

• (3) Each sensor/node/user, which is not a beacon node, computes its pairwise distance/signal-strength vector with all beacon nodes as a result of receiving the simple message from beacons. Next, each sensor node applies the prediction/trained model that has been obtained in the previous step to its pairwise distance/signal-strength vector to estimate its location.

We explain classification and regression based localization in detail in the following sub-sections.

7.1 Classification Based Localization

This approach requires the localization problem to be mapped into a classification problem. In order to realize that, a common approach includes two steps: (1) Dividing the deployment area into some geographic regions. These geographic regions are known as cells, and they have rectangular, square, circular, or arbitrary shapes; (2) A classification procedure as an ML algorithm is ran to decide membership of nodes/users with unknown location in these classes. Based on these memberships, ML algorithms localize those users, i.e., each node/user is classified based on its membership to these cells [168].

Different ML algorithms are used in the classification based localization. Common approaches include Support Vector Machine (SVM), K-Nearest Neighbors (KNN), Multi-Layer Perceptron Neural Network (MLP).

7.1.1 Support Vector Machine (SVM)

The Support Vector Machine (SVM) generates hyperplane(s) in multidimensional space to split data points into different classes. Close data points to hyperplane(s) are known as support vectors. SVM aims to provide hyperplane(s) in a way that support vectors of different classes have maximum distance with each other. SVM classifies data point to as many as classes data points are. data points can be linearly and/or non-linearly separated. A hyperplane is obtained as middle points between support vectors of different classes if data points are linearly separable. If that’s not the case, data points are mapped into other spaces for easier separation. Mostly, from a lower dimension space to a higher dimension space via some kernel functions. Common kernels include linear, polynomial, sigmoid and Gaussian functions. The results show that Gaussian kernel has a better performance based on the standard deviation and mean error [169].

SVMs are used in the localization system by training support vectors on a radio map whose consists of a set of grid points. SVMs analyze the relationship between the trained fingerprints and grid points. SVMs consider each grid point as a class and attempt to find a perfect match between user locations and grid points. The tested RSS fingerprints are considered as inputs to SVM and the predicted class to which the fingerprints belongs is the output. In the case of localization problems, the RSS fingerprint vectors are mapped into higher dimensional space using kernel functions because in most cases the location classes are not linearly separable. After this mapping, SVM finds a hyperplane to divide data points into two classes. The maximal margin hyperplane and support vectors are used by SVMs to identify the tested data class.

The measured fingerprint is classified according to the sign of a function f(x). A linear function of the used kernel function for mapping data points into a higher dimension space is considered as f(x). Due to possibility of several locations for users, a localization problem is considered as multi-class classification problems. Common approach is that SVM maps these multi-class classifications into a combination of two-classes, which are labeled as binary classification. An N-class problem is divided into N binary classifier via SVM. Each binary classifier is trained separately to estimate user locations and it separates one class from other classes. A localization process includes two steps: First, outputs of all N binary classifiers are calculated. Next, maximum value of f(x) is the predicted class [169,170,171,172,173,174,175,176,177].

7.1.2 K-Nearest Neighbors (KNN)

KNN algorithm is based on considering a predefined number of calibration points or beacon nodes, i.e., K points. Beacon nodes are nodes with known location. These beacon nodes correspond to RSS fingerprints in the localization. These RSS fingerprints rely on the physical distance between access points in the radio map and users. First, KNN algorithm calculates the distance between the user with unknown location and beacon nodes. Common distances are Manhattan and Euclidean norm-distance. Next, it selects K nearest nodes to the user based on its distance calculation. Estimated location of the user is the average of coordinates of these K nearest nodes (neighbors) [170, 174, 176, 177].

7.1.3 Multi-Layer Perceptron Neural Network (MLP)

MLP is a vigorous tool for many applications mainly nonlinear estimation. Localization is a nonlinear mapping between some available information and desired locations. Thus, MLP is one of common ML approach for localization. In the localization process, different variables/parameters are used in the literature as input for MLP such as received RSS measurements [178,179,180,181] and channel state information (CSI) [46, 182], and output always is an estimated location. For each localization, the trained MLP estimates user’s location for some given inputs [170, 177, 178, 183, 184].

7.1.4 Other ML algorithms for Classification based localization

Decision Trees is used in [176, 177, 183]. Naïve Bayes is used in [176, 183, 185]. Authors in [177, 185, 186] use Random forest. Six machine learning algorithm including Bayesian Network, Sequential minimal optimization (SMO), AdaBoost, and Bagging are compared in [176]. The corresponding results show that KNN is the superior algorithm with respect to other methods based on both the computational time and accuracy to estimate position. In addition, the decision tree provides nearly same performance when used with iterative algorithms, namely Bagging and AdaBoost [176].

7.2 Regression Based Localization

Node/User Localization in an N-dimensional region requires an estimation of N-coordinates for target nodes/users, which generally are real numbers. This can be modeled as a regression problem as well. As explained earlier in the paper, given true Euclidean distances of nodes/users from beacon nodes, trilateration is used for localization. To locate a node/user that we do not know its true Euclidean distances from beacon nodes, we can use a regression tool to learn about these distances via training information such hop-count and/or RSS. The head beacon constructs a linear/non-linear regression function based on a training data such as the location of beacon nodes. Next, the head beacon will broadcast this function to all nodes/users. In addition, other beacon nodes send a Hello massage to all nodes/users. Thus, non-beacon nodes/users compute their distance vector from beacon nodes/users once they receive Hello message from beacon nodes/users. Next, they determine their location via applying the regression function to their distance vector.

Different ML algorithms are used in the regression based localization. They include SVM, NN, etc.

7.2.1 Support vector regression (SVR)

SVM has been modified and denoted as support vector regression (SVR) to apply to nonlinear regression models. RSS values for each antenna element and virtual grid coordinates (x, y) of each reference tag are considered as SVR inputs and SVR outputs, respectively. Thus, a target position is given by spatial coordinates in SVR rather than a region or proximity in SVM. SVR uses the same basic idea as SVM but applies it to predict real values rather than a class. The SVR maps a function f(x) to the training data that has a small deviation from that data, i.e., SVR approximates the training data via f(x). SVR can be used via both linear and nonlinear approximation functions. Kernel-based SVR maps a lower dimensional data into a higher dimensional data in the hope that the data could become more easily separated or better structured [187,188,189].

7.2.2 Artificial Neural Networks (ANN)

Similar to classification based localization, ANN or MLP, are used for regression based localization. Here, ANN estimate spatial coordinates (x, y) of user/target rather than its corresponding class. Here, training input and output are RSS and user coordinates, respectively [190]. Authors in [191] use convolutional neural network (CNN) with regression-based fingerprint model to estimate user position. In theory, ANN can lead to a very accurate localization prediction. However, this accuracy reduces for the real-time applications due to the computational time required to make predictions [190].

7.2.3 Other ML algorithms for regression based localization

Cluster K-nearest Neighbor (CKNN) and Weighted K-nearest Neighbor (WKNN) are used in [192] and [193], respectively. Authors in [194] use Gaussian Process Regression (GPR). Proximity algorithm is used in [195].

8 Radar

Radars can be defined as the general category of remote positioning systems. These systems are divided into two main categories of Passive and Active Target Remote Positioning. Targets in Radars are usually passive and don’t contribute in the process of positioning. Passive target radars are usually called primary radars. However, in secondary radars that are used for Air Traffic Systems, targets (airplanes) are active targets. They are equipped with transponders that communicate with the airport secondary radar and provide information such as their GPS-calculated position and altitude that is key to the air traffic control process.

Primary radars find the position of targets in the surrounding areas via a  transmission of a short burst of energy and processing its reflections [196, 197]. The reflected signal is called echo. TOA and DOA estimation is key to radar localization. Radars that use rotating reflector antennas, find DOA based on the direction of the reflector antenna, and use round trip TOA for TOA estimation. In general, the detection quality of a radar system is characterized by two important metrics: one is the probability-of-detection (p_d) that represents the ability to detect all targets, and the other is the probability-of-false alarms (p_fa) that indicates the probability of falsely treating noise as the desired target. In addition, detecting a passive target always requires a tradeoff between p_d and p_fa: as the former increases, the latter increases, resulting in a low overall performance. Long-range Radar technology require high power amplifiers such as Klystron and Magnetron. Solid state power amplifiers have also been developed for short to mid-range radar applications.

Originally, radars were used for the detection and ranging of targets, but today advanced signal processing along with machine learning methods enable radars to extract more information such as the nature of target, its size, and speed. Radars use tracking techniques to enable them to track targets. Radars (specifically those used in military applications) can track a large number of targets simultaneously.

The ability of traditional radar systems to find the location of targets is usually limited to the targets in free space. Wireless environments such as urban, suburban and even rural areas suffer from variety types of obstacles that are usually called scatterers. The capability of radars to detect the desired targets is hindered by clutters or reflections from undesirable scattereres and interfering radars, which are inevitable in typical indoor and urban areas, rendering radar systems impractical [198]. Moreover, operation of multiple radars in urban areas require multi-user technologies to avoid interference effects.

Vehicle-to-vehicle localization via mm-wave radars are key to autonomous vehicles. These radars are required to operate in rich scattering media. They also should cope with near ground channel effects as they are usually installed on vehicle bumpers [199, 200]. Emerging mm-wave radars, IoT devices, mobiles, along with many traditional radios highly impacted the utilization of spectrum technologies. This has led to the development of new and novel spectrum sharing methods that may involve artificial intelligence to enable coexistence of numerous radio devices [201].

9 RFID Based Localization

At first glance, radiofrequency identification (RFID) technology may not seem like the panacea of radiolocation that it is fast becoming. Passive, far-field RFID tags operating in the UHF bands are short-ranged, requiring enough incident RF power to energize its logic, memory, and communications circuitry. Even if there is enough incident power on the passive RFID tag to power all of its operations, the data rate is extremely low compared to modern, conventional radio communications. The existence of multiple tags in a reader’s field of view slows and hampers communications in ways unfamiliar to any modern cellular air interface.

Yet RFID has, from the beginning, been primarily a location technology. Identification information, by itself, is meaningless; only when the tag is connected by location to its context does RFID become useful. This fact is obscured by the fact that passive RFID tags have such limited range. If passive RFID works, its location is instantly known: the tag is right by the reader! That reader may be a portal to a warehouse, may be hovering above a toll lane on a highway, or may be monitoring a storefront for unauthorized removal of merchandise [202, 203]. In every case, the context of location is at least as important as any unique identifier that an RF tag stores.

However, as passive tags have increased in range, their usefulness in a radiolocation system has become apparent. A landmark accomplishment in RFID localization was achieved, indeed, by LANDMARC (LocAtioN iDentification based on dynaMic Active Rfid Calibration) [204]. The LANDMARC system took advantage of the lossy RFID propagation channel to perform localization with RSS fingerprinting, along with strategically placed reference tags, that achieved 50-percentile accuracy of about 1.0 m [204]. It is well-known that RSS fingerprinting works better in lossier environments, as this effectively adds a stronger dependence on distance to RSS, making it easier for trilateration algorithms to localize a transponder [205]. Passive UHF RFID, by using backscatter communications from reader-to-tag-to-reader, operates with a free space link budget that more closely resembles a radar system, even in an uncluttered, free-space environment.

9.1 The Unique Role of Phase in RFID Localization

There is a hidden strength in using backscatter systems like RFID to localize transponders. Unlike conventional radios, an RFID reader can both transmit and receive signals using the exact same RF oscillator source. RFID tags use load modulation at their antennas to reflect digital signals back to the reader (switching between two different electrical loads, which effectively selects between two different radar cross sections). So the RFID signal experiences a true “round-trip” propagation with zero latency, and the RFID reader can make a true phase-stable measurement on this link. Although it is possible to experience range correlation effects due to oscillator phase noise, modern-day commercial frequency synthesis hardware generates oscillators that are stable enough to avoid range correlation effects in UHF and microwave bands for signals that travel a few kilometers or less.

Arnitz et al. illustrated how phase could be used for precise localization of RFID tags [206]. Nikitin, et. al. demonstrated phase-based measurements on the backscatter link that produced range estimates that consistently predicted in which 60-cm “lane” an RFID tag was traveling through a reader portal [207]. Zhou and Griffin used a 5.8 GHz microwave RFID link to demonstrate how a simple, two-frequency phase measurement can be used to estimate tag range that is typically within 20 mm of the reader at ranges of 1.275 m [208]. Cheng, et. al. demonstrated a multi-frequency phase measuring technique that could further refine range estimates indoors with errors on the order of 10 cm [qi].

The increase in RFID location precision that use phase can be further enhanced by employing sensor fusion techniques. Because inertial-magnetometry units (IMUs) for handsets and portable devices have lowered in both cost and power consumption, power-stingy IMUs are easily incorporated into an RFID tag. Akbar et al. demonstrated that an RFID tag capable of backscattering IMU data is capable of hybrid inertial microwave reflectometry (HIMR) [209]. HIMR uses data backscattered from the RFID tag in addition to measurements on the signal strength and phase of the RF link itself, fusing the two different types of measurement into a location estimate that ends up being far more accurate than using RF link measurements or IMU data alone.

Akbar et. al. demonstrated the ability to track a moving target on a circular track with 2D RMS position error consistently less than 2 cm, in a bounded area surrounded by 3 microwave readers operating up to 20m away from the tag [210]. Yang et. al. later demonstrated a general framework for sensor fusion involving Kalman filtering of the measured backscatter physical parameters as well as IMU data to achieve ranging errors of less than 2 cm [211].

9.2 Boosting the Range of RFID

Despite recent gains in the performance of passive UHF RFID, it is the energy-harvesting circuitry that still limits the usable range. Since UHF RFID operates in unlicensed bands around 900 MHz, readers must abide by the typical industrial-scientific-medical (ISM) regulations in the country of operation. In the US, these restrictions require a maximum of 1 Watt input power to a transmit antenna restricted to a maximum of 6 dBi peak gain. Under these transmit restrictions, Fig. 3 illustrates how tag sensitivity—the minimum input power to a passive tag required to energize its circuitry and conduct communications—has changed over the years. Each data point on Fig. 3 records underneath the maximum range of a passive UHF RFID tag under ideal conditions (peak transmission power and antenna gain, free-space channel, no polarization mismatch).

Fig. 3

Nikitin’s trend for improved sensitivity and range of passive UHF RFID tags is illustrated [212, 213]

As can be seen in Fig. 3, after a surge of improved sensitivity, a period of stagnation exists to this present day. Largely due to the limits of devices in standard silicon CMOS fabrication processes, the ability of RFID tag energy-harvesting circuits to convert RF power to a usable electric form have not improved appreciably between 2015 and 2020. Although the thermodynamics of RF energy-harvesting and suggestive alternative solid-state devices show that improved conversion is possible, an economical alternative has yet to be successfully implemented [213, 214].

However, the device limitations has not stopped researchers from finding new ways to enhance the range of localization for RFID. One popular method involves employing a reflection amplifier at the RFID tag. In this implementation, a small amount of on-board battery power or alternative energy-harvesting power-banking or harvesting scheme is employed by the RF tag to amplify any reflective communications power. This can be accomplished using conventional transistors [215] or more exotic tunnel diodes [216] that use microWatts of power to greatly enhance the range of backscatter communications. In 2017, Amato demonstrated a microwave backscatter link that could retrieve digital data from 1.2 km away (line-of-sight) [217]. Qi et al. later demonstrated the power of this technique to localize indoor and outdoor tags up to 30m away with less than 10 cm RMS error [218].

In all, RFID and its related technologies has shown enormous achievements in recent years for localization. The ultimate prize—a long-ranged radiolocation system capable of cm-scale, motion-capture-grade localization in multipath and/or non-line-sight scenarios—-is getting tantalizingly close to technical reality.

10 Visible Light Positioning

Solid-state light-emitting diodes, photo-diodes, and image sensors are embedded in different devices (smartphones, smartwatches, and tablets, to name a few). LED-based illumination saves power, produces creative fixtures, and smart lighting [219]. Image sensors and particular purpose photo-diodes collect images and other light data for different applications. These facts jointly create a profitable opportunity for the development of pervasive, secure, and low-cost visible light communication (VLC) and visible light positioning (VLP) [220] systems, both for indoor and outdoor uses.

VLC systems offer high bandwidth using illumination devices, thus immune to other electromagnetic sources, favoring a high reuse factor since light does not go across walls. Such technologies have already been proposed for use indoors and in vehicular platforms (ships, airplanes, buses, and cars). Their use may reduce the number of cables and reduce weight, manufacturing cost, and energy consumption. Besides, as light does not interfere with other electromagnetic equipment, it may be safely used in domains where RF interference is undesirable, such as hospitals, mines, gas stations, and aircraft. VLC may also be very cost-effective if installed in existing illumination systems with few changes. As a result, visible light positioning (VLP) technologies aiming at localizing devices using information from (visible) light (communication) sources have also emerged rapidly. The staggering use of the non-licensed RF bands (as the WiFi and Bluetooth bands) and the developments in LED, PDs (photo-diodes), and image sensors technologies throttle the design of VLC and VLP systems.

VLP technology is well suited for self-owned short-range localization systems. Some have pointed VLP as a powerful technology for low-cost IPS (indoor positioning system) for the IoT (Internet of Things) era, leveraging high-accuracy localization-dependent data delivery at high data rates with high availability in consumer applications. The light within a room does not interfere with light in another room, easing VLP systems reuse for indoor applications. The wave-particle nature of light (its very short wavelength/particle size) makes it possible to obtain a very accurate position location. Consequently, VLP arises as a competitive alternative for IPS. Different VLP systems have been proposed and employed for intelligent transportation systems (ITS) as well.

We make an effort to present a historical perspective of VLP, mainly considering the dual use of light sources for communication and position location. Nonetheless, we must undoubtedly make undesired mistakes when searching for the birth of some ideas, concepts, and their use for VLP. In our endeavor, difficulty tracking the onset of using a particular ranging method for VLP comes from the fact that several groups were probably employing similar principles simultaneously. We try to address when and how light sources, LED sources, and VLC systems were employed to locate and track different devices. VLP research and development is ongoing, humanity’s ingeniousness, the delay for some ideas to be publicized, and the thriving technology era we live in also hamper the objective.

10.1 Preceding Technologies

The efforts leading to the first LIDAR (light detection and ranging) systems using laser (light amplification by stimulated emission of radiation) beams succeed already in the 1960s [221, 222]. Since these systems employ optics, they were also called Optical RADARs. A LIDAR irradiates light, and from the reflected light, one computes the distance to objects and surfaces. Such systems were integrated for surface scanning [223]. Satellites convey such optical radar techniques for geodesy, metrology, and geodynamics applications [224]. While the first systems were large and heavy, nowadays they are embarked in drones for many applications to map the most different environments and surfaces.

Optic-electronic systems have provided precision sensing for industrial positioning and alignment applications for a long period [225]. With time the optical-electronic systems replaced several electro-mechanical systems for the precise positioning in industrial applications. The key-technology were optoelectronic position-sensitive detectors using the lateral photo effect. The impinging light produces an electrical current that flows to the detector contacts proportionally to the resistance from the position where light impinges to each contact. To determine the incident spot position, one compares the resulting currents. Such lateral effect position-sensitive devices are capable of rapid response and very high position resolution. Therefore, position-sensitive detectors allow determining the position of a light spot on the receiving optics’ focal plane in real-time. Various types of position-sensitive photo-detectors have been developed [226], from using only one photo-diode sensor to using multiple photo-detectors in multi-sensor arrays. These systems have been used by diverse industrial applications to measure displacement, angle, straightness, object location, height, and center. Such position-sensitive detectors have also being used for optical range sensing [227]. The light (using a laser) emitted and its reflection impinges a position-sensitive detector, and from the resulting current, one computes the range. Using three of such ranges, one resolves the relative position and constructs 3D maps.

Range finding from the projection a known pattern of light (laser) on a surface or scene is also possible [228]. Cameras are employed to capture the projection of the structured light pattern on the surface. The pattern distortion resulting from its projection algorithms compute the distance to points in the scene. The use of visible projected structured light patterns has been a suitable range finding method, using infrared or/and visible light projection.

Smart dust is millimeter-scale sensor nodes with limited computation power, limited sensing capacities, and limited communication capabilities with a base station intended for large scale monitoring tasks for many applications. An approach for a smart dust location position using a rotating parallel laser beam was proposed in [229]. The sensor distance to the lighthouse makes the angular width in which the sensor sees the light change. Thus, each dust sensor measures the time interval that it sees the light and the period it takes for the light to be seen again, i.e., the lighthouse revolution, to compute its distance to the lighthouse.

10.2 Location Position From Light Intensity

The intensity of light in a room depends on each light source’s intensity, arrangement, the light reflection from walls and objects, and the medium itself. Different illumination fixtures and lamps, in general, produce different spatial distributions of light intensity and different rooms have distinct spatial distributions of light intensity. Even if the light intensity may be the same in some specific points in different rooms, the spatial distribution of light intensity will most probably be different over different rooms. The authors of [230] propose to track light intensity changing as data to track user displacement and user activity. Light detectors (wearable solar cells) measure the light condition. An RFID infra-structure offers absolute reference positions, and one employs light intensity change for displacement tracking. Measuring and collecting the light intensity distribution in a room over time may produce a unique distinct illumination energy histogram. The histogram may be fed to scene analysis or fingerprinting methods to obtain the correspondent locality, identifying, for example, the room where the distribution was collected [231].

Light intensity patterns may vary severely depending on light sensor placement in the body or objects and the actual fixtures. Nevertheless, the idea of using light intensity patterns and variations has been embedded in different algorithms trying to exploit conventional luminary infrastructure. For example, in [232], the authors propose to detect the passing under a light spot together with inertial data (using inertial measurement units—IMU) for locating the pedestrian in the floor. The authors of [233] follow a very similar idea. These works also show the relevance of using light intensity as data for multi-modal position location. Another work [234] uses six PDs placed on the faces of the half of a dodecaedron. They capture the light intensity arriving from light fixtures; each light is switched ON and OFF at a particular frequency to allow its identification. The intensity of each surrounding light defines a different geometric locus. The authors find the receiver position location using three of them. One notes that the last work presents a relevant change w.r.t. to the previously mentioned works: the modulation (on-off) of the light, allowing us to identify the sources that come by the different directions, and we need to move back, chronologically speaking.

10.3 Proximity Methods

The above examples show that light/optical range-finding systems have been around previously to the so-called VLP systems. Those ranging optical methods employ light sources and detectors in a known geometry/arrangement to estimate the target’s distance. Differently, VLP systems estimate the range from a visible light source to a detector or their relative position. VLP systems employ light in the most distinct environments to provide a position location for devices, people, and various objects. If one modulates light sources to convey information for localization purposes, one may use different geometrical approaches for VLP. These approaches may require large bandwidth, replacement of older lighting technologies by LEDs satisfies the requirement. They also require different beacons or anchors, which is also easy to accomplish using LEDs (low weight, low cost, high efficiency, large life-expectancy). As a result, VLP systems suing geometrical positioning techniques abound. These VLP systems may use light anchors’ identity (proximity) combined with fingerprinting methods, ranging (distance estimates) for trilateration, triangulation using angle measurements, and others to provide a position fix.

One of the first proposals to transmit specific information for location position was for a vehicle location and navigation system using traffic lights [235]. Assuming that LEDs would replace traffic lights, the authors propose using short-range communication devices for roadside-to-vehicle communications, modulating the LEDs in the traffic lights for broadcasting. One finds location and navigation data within the broadcast information, converting the traffic lights in location beacons. Once the vehicle detects the short-range beacon, it can obtain the junction passing by, a coarse but useful position location. These data can be used in many ways for intelligent transportation systems (ITS). A camera captures the traffic light image augmenting channel capacity, and the partitioning of the light traffic panel into regions encoding different information improves transmission diversity, among other improvements, in [236]. These systems make a simple dual-use of light for positioning (the conveyed location position) and information (stop-caution-go) and other possible data, as traffic information and nearby services.

The above systems modulate especial purpose lights for delivering the location information, while the systems in [230, 231] employ preexisting ambient lighting for location position. Another interesting proposition combines the two principles for assisting the visually impaired [237]. One modulates the light radiated by the fluorescent lamp to convey its position (the building, the floor, the room, and alike, that is the lamp location or identity). Zhang and Zhang [238] uses fluorescent lamps as location landmarks and a smartphone camera as a sensor. The system detects each fluorescent lamp using its inherent characteristic frequency. A set of sampling, signal amplification, and camera optimization mechanisms allow capturing these weak features above 80 Khz. The Visible Light Cell ID (VLID) techniques that return the device position as correspondent to the light source location (the junction, the room, or the lamp, or even the centroid of the correspondent illumination region) provide a locality classification. This coarse location requires only one light beacon, making such VLP systems to scale easy. The light carrying the identification and possibly the position for location purposes is confined within the room where the light fixture is, channel reuse is for free, differently than similar strategies based on RF techniques. One should note that the ranges for outdoor and indoor position location systems depend on the modulated light’s visibility with enough intensity and are thus proximity constrained; therefore, they are proximity-based positioning systems. These systems may present very specialized means for light modulation and processing techniques to extract the beacon identity. For example, in [239] the LED light pulses at a frequency much higher than the camera’s frame capture rate and thus producing a particular band-image pattern due to the interference with the pulse rate and the rolling shutter of the camera.

10.4 Ranging from Light Intensity

One work presenting methods to estimate the distance of optical communication links from the received optical power or the error rate (which depends on the received power) is in [240]. This work provides experiments for ranging in air and underwater. The authors collect data that correlate the necessary transmission power (voltage on the LED) for error-free transmission to the transmitter-detector distance to estimate the distance between the light source and the detector. At short range distances, the error rate of the optical link is expected to be null. Therefore a protocol is employed for the transmitter to reduce its transmission power progressively. Once the voltage applied in the LED for transmission makes the error rate depart from zero, one can estimate the distance from the smallest voltage leading to an error-free optical link using a polynomial regression or lookup table. However, at long distances, transmission error will always occur, demanding a different strategy. The authors propose to employ the current transfer rate at the detector, which depends on the distance (assuming that the transmission power is constant).

After detecting the visible light source identity, one may compute the emitter’s distance to the detector from the received optical power by inverting the free-space-optical model. And, one has the VLP counterpart to RF received signal strength-based (RSS-based) location position methods. Some works use particular curves to fit received signal strength and distance; others use the Lambertian model [241]. Nevertheless, the principle is always obtaining the range from the received signal strength. To obtain ranges to different light emitters [242], time division, frequency division, code division, and other medium sharing techniques that are particular of VLC as color/wavelength multiplexing (using light sources of different colors). It is also possible to employ one light beacon and several optical receivers in a known arrangement [243]. Each of the optical receivers produces a different range. In [244], the authors present a multiple-photo-diode-based indoor positioning that employs photo-diodes in different tilts to measure light intensity. The power received from the different light sources fed the localization algorithm, instead of the range. Instead of computing ranges from the received optical power, one may employ the ratio between the optical power and the RF signal modulating the light [245], the extinction ratio [246] (the ratio (in dB) between the ON and the OFF voltages at the PD) can also be used.

10.5 Angular Information

Using arrangements of sensors or image sensors introduces angular information for resolving the location position. The mixing of range measurements and orientation (angle information) is another alternative [247] using arrangements with multiple emitters and detectors (multiple transceivers optical nodes). The optical link line-of-sight depends on the relative position between the optical nodes. Using multiple transceivers in the optical node allows to now the ones under LOS. This angular information is used together with the range between the optical nodes to find their relative positions. Such an approach is an example of the DOA method in VLP systems. The angular information results from the fact that LED emissions follow Lambert’s cosine law; thus, changes in the alignment between LED and PD lead to changes in the received optical power in a predictable manner. Therefore, one could use the difference between the received power and the received power at a known angle to estimate the incidence angle. Another use of angle-of-arrival for VLP is to resolve the receiver orientation to maximize the throughput of an optical link  [248]. However, the field of view and possible inaccuracies in the Lambertian models limit the conversion from received-optical-power to angle. To mitigate these inaccuracies, PD arrangements composed by multiple receivers is a possibility [249]. Methods mixing the angular information and ranging for location position can be seen in [250, 251].

10.6 Computer Vision Techniques

Trying to track back the history of VLP techniques, we now go back on time and focus on computer-vision-based techniques. One may compute the receiver position knowing the spatial arrangement of LEDs and each LED projection’s positions on the image sensor. Complementary, the LEDs may encode their differential positions w.r.t an arbitrary origin. The image sensor is used to obtain both their relative positions on the image plane and the differential positions they broadcast.

In [252], the authors evaluate the proposal considering LEDs placed in traffic lights or at the roadside. Computer-vision-based VLP methods are using different LED arrangements and detectors. For example, consider the work in [253] that using a ceiling fixture composed of several LEDs emitting light modulated to encode their positions. The device to be located captures their projection in two different image sensors spatially separated with now arrangement. Estimating the receiver’s position requires solving two sets of quadratic equations to find the corresponding spherical geometric loci interception. Suppose different light sources are present in the captured images/video, then one extracts their identities. In that case, one may use the sources’ positions in the image to compute the image sensor’s position. The authors of [254] employ a fish-eye lens equipped camera to provide a 180$^o$ aperture and thus increase the number of detectable LED lights aiming at improving positioning accuracy. The work in [255] employs light beacons modulated using ON-OFF keying to broadcast the beacons’ identities and coordinates. Using a sequence of images, one identifies the beacon, demodulates its data, and obtains its location in the image. From the location of the beacons in the captured image, one extracts the angle information.

10.7 Phase and Time Difference Ranging

Considering ITS, one notes that each vehicle embarks at least two headlights and two taillights. One modulates the lights by tones using different frequencies [256], the second vehicle detects these tones and computes the difference between their phases. This difference depends on the relative position between the vehicles, the LED sources arrangement, and the detector’s disposition. The second vehicle knows its detectors arrangement while the transmitted tones convey the first vehicle’s light disposition. If the two arrangements are known, the second vehicle can obtain its relative position to the first. In [257], the authors present a TDOA VLP scheme aiming at vehicle localization, considering VLC capable LED traffic lights and that the vehicles detect the messages using a pair of photo-diodes. One determines the vehicle’s position from the traffic light position broadcast in the VLC link and the time difference between the traffic light signal’s arrival at the two photo-diodes. Such VLP can work using one or more traffic lights. Such a method requires precise knowledge of the traffic lights positions, and its accuracy reduces with vehicle speed up.

Similar schemes for indoor positioning also exist [258]. One modulates the LED ceiling lamps using different frequencies and computes the position from the phase differences (the TDOAs) at the detector (a PD). These methods employ sinusoidal waves and detect phase differences to compute the difference in light travel time. Such techniques have been called PDOA—phase difference of arrival, position location. In [259], PDOAs using odd multiples of a fundamental frequency is employed.

The work in [260] notes that by modulating the light emitted by different white LEDs, one produces an interference pattern in the detector. The interference amplitude varies with the geometrical arrangement between transmitters and detectors. Then, by measuring the peak-to-peak amplitude of the received sinusoid, one also produces a TDOA measurement. Measuring amplitude rather than phase does not require an absolute time reference at the receiver. VLP systems could use TDOA for trilateration [261]. The techniques to obtain the TDOAs between different beacons/anchors may employ the alignment of encoded data on the beacon burst. Another option is to use simple pulses of arbitrary positions and amplitudes within a frame (a time interval). From the pulses’ received profile within a frame, one obtains the TDOAs to different anchors [262] and computes the position fix. While the above methods for TDOA positioning for VLP are easy to deploy since they do not require synchronization, TOA is more demanding and, therefore, less common for VLP since, in general, the objective of VLP has bee to locate low-cost devices.

10.8 Fingerprinting

Indoor localization using fingerprinting-based VLP is also possible. In [263], each LED beacon emits visible light intensity-modulated by a sinusoidal wave, using a different frequency for each LED. The received signal at the photo-diode is processed to obtain its power spectral density. A pyramidal-like arrangement of five photo-detectors (placing a photo-diode in each face and another in a plane parallel to the pyramid base but above the others) provides reception diversity. The power spectral density is the fingerprint. The scene analysis process compares the power spectral density to be located against a database of power spectral densities utilizing the Euclidean distance and returns the corresponding position. In [264], another example of fingerprinting VLP-IPS is devised for multiple LED transmitters, although infrared. The receiver measures the power and their impulse responses as fingerprints.

Another alternative is to modulate the VLP beacon synchronously using its position [265]. The receiver knows the codes (the beacons addresses) and then computes the received signal’s correlation with them. The larger the correlation is, the closer the receiver is to the correspondent beacon. By training (similar to the construction of a fingerprinting database or map), the authors fit functions to map the correlations to 2D coordinates. In this sense, since the received signal correlation with the known transmitted one provides a measure of received signal strength, this system resembles fingerprinting form received signal strength. The use of a fitting function simplifies scene analysis.

DOA is also a possible fingerprint feature [251]. The detected power varies both with the distance and the angle between emitter and receiver. Using an array of PDs tilted at different angles boosts DOA fingerprinting. Since the light arrives at the different PDs in the arrays at different angles, the detected power also varies accordingly. The resulting received power can be measured and used as a fingerprint.

The capability to extract the features depends on the communication method (modulation scheme, coding, clock/bandwidth) and the nature of transmitted data. Therefore, one may design specific modulation and coding schemes that consider its usability to extract fingerprinting features. For example, [246, 266] use OOK modulation in the VLC; consequently, the fingerprints contain the ratios between the ON and OFF received amplitudes. One finds the most probable location using a database of received ON/OFF amplitudes ratio. Using images as fingerprinting features is also a possibility [267]. The LED beacons blink at high-frequency, and image sensors collect the resulting patterns at different rates. The fingerprints are composed of light intensity plus the image pattern, and then, using a probabilistic approach, the position of the image sensor is determined.

11 Conclusion

This paper summarizes the history of localization techniques. It highlights the initial motivation for basic Radar technology development in World-war II to detect and localize airplanes and warships. Next, it offers an overview of the development of localization technologies through the evolution of wireless communication technologies and signal processing for TOA, DOA, and RSS computation. The paper presents the concept of geometric and non-geometric localization, the problems associated to NLOS localization and the concept of collaborative localization. The paper also presents the development of tracking and Kalman filtering methods that are key to high performance localization. The paper addresses the emergence of artificial intelligence and machine learning for localization as well. In addition, the paper discusses emerging techniques and methods in the field of localization such as visible light, machine learning, RFID, and network localization. Moreover, the paper discusses key localization techniques that have been developed over the last few decades. Furthermore, the paper sheds light on novel localization technologies and key research areas and important topics related to localization.