Exchanging Transmitter Maps in Multipath Assisted Positioning
Markus Ulmschneider, German Aerospace Center (DLR), Germany; David Calvo Luz, Universidad Politecnica de Madrid (UPM), Spain; Christian Gentner, German Aerospace Center (DLR), Germany
The positioning performance of global navigation satellite systems (GNSSs) is sufficient for many applications in scenarios with a clear view to the sky. In environments like indoors or in urban canyons, effects such as multipath propagation, a low received signal power or signal blockage decrease the positioning performance of GNSSs drastically, and the precise localization of a user remains a challenge. Nevertheless, other radio frequency signals are often available in such scenarios, and they can be used as signals of opportunities for localization. For example, cellular signals are available in nearly all populated areas. Hence, for localization using cellular signals, no additional infrastructure for transmission or reception has to be installed.
Positioning approaches using signals of opportunity suffer from multipath propagation as well when standard methods to combat multipath propagation are used. In particular in scenarios such as urban canyons or indoors, a high multipath propagation can be expected. Instead of trying to combat multipath propagation, the spatial information from multipath components (MPCs) can be exploited. Such an approach is called multipath assisted positioning. In multipath assisted positioning, each MPC is regarded as a signal transmitted by a virtual transmitter in a line-of-sight (LoS) condition, and the virtual transmitters can be used for localizing a user.
Some approaches in multipath assisted positioning assume the geometry of the environment, for example as a floorplan, and the physical transmitter locations to be known in advance. Based on this information, the locations of the virtual transmitters can be calculated. Our approach does not rely on such prior knowledge. Hence, the locations of both the physical and the virtual transmitters are unknown. Instead, we estimate the states of the physical and virtual transmitters simultaneously with the user position in a simultaneous localization and mapping (SLAM) scheme. Therefore, we named our approach Channel-SLAM. In Channel-SLAM, we do not differentiate between physical and virtual transmitters: each signal component arriving at the receiver is regarded as being transmitted from some transmitter in a LoS condition. Hence, we use the term transmitter generally for physical and virtual transmitters in the following.
For robust long-term SLAM, a reliable data association method is crucial. Data association describes which of the transmitters correspond as a user walks through a scenario. We have studied data association among previously visible and newly initialized transmitters in Channel-SLAM in a previous paper.
In many GNSS denied environments such as in urban canyons, a high fluctuation of users can be expected. In other words, many users move through a scenario on the same or on different trajectories. These users can cooperate by exchanging maps of observed transmitters either directly, or via some local entity. Such an entity could be a base station in a cellular network. A user entering a scenario can use a map from one or multiple previous users as prior knowledge on the transmitter locations. We call such a map a prior map, and a map estimated by a user a user map. Each map consists of a set of transmitters whose states are represented by probability density functions (PDFs). A PDF can be parametrized, e.g. a normal distribution, or unparametrized, e.g., a particle cloud.
However, since Channel-SLAM is a relative localization approach, the user map and a prior map from another user are in different coordinate systems with an unknown offset and an unknown rotation. In addition, the correspondences among the transmitters in the two maps are not known. Hence, we define finding a match among the two maps as both estimating the relative offset and rotation among the two coordinate systems, and finding correspondences among the transmitters in the two maps. Only when a reliable match among user and prior map is found, the information in the prior map can be exploited by the user with a data association method.
When initializing a new transmitter, the uncertainty on this transmitter’s state tends to be high, since the measurement is two-dimensional, assuming time-of-arrival (ToA) and angle-of-arrival (AoA) measurements, whereas a transmitter’s state is of three dimensions, which are the two-dimensional location and a clock offset. Hence, the variance in the state PDF of a newly initialized transmitter is high. It decreases as the user moves through the scenario taking measurements of the transmitter from different locations. For finding a match among user map and prior map, we regard only a subset of transmitters in the user map and the prior map. In particular, we choose transmitters whose state PDFs are of low variances to increase the robustness of the scheme.
Our approach is to first obtain the correspondences among the transmitters in the two maps and afterwards the corresponding offset and rotation of the coordinate systems. We assume no dilation or skew among the two maps.
In the beginning, we have no information on the relation of the transmitters in the two maps, since the maps are in different coordinate systems. However, the relative positions of the transmitters within the maps can be exploited. In particular, we can calculate the relative distances among any two transmitters within each of the two maps. Since the actual shapes of the PDFs of the transmitters’ states estimated by different users may differ considerably depending on the user trajectory, we do not apply measures tailored to PDFs such as the Kullback–Leibler divergence. Instead, we define the distance between two transmitters as the Euclidean distance between the means of the transmitter state PDFs.
If we assume to have N transmitters in each map, there are N(N-1)/2 relative distances among the transmitters within each map, and N! possibilities to associate the transmitters in the user map with the transmitters in the prior map.
For each of the N! possible associations, we can calculate an error for the relative distances. The error is the sum of the N(N-1)/2 squared differences between the distance of two transmitters in the user map and the corresponding distance of two transmitters in the prior map.
Having obtained the error for all possible associations of transmitters, we chose the one with lowest error. If this error exceeds a threshold, we assume not to have found a correspondence.
Finding no correspondence may occur when the estimate for one or more transmitters has a high bias or variance, or if there is no actual correspondence among the transmitters in the two maps. This can happen when two users travel on different trajectories, and one or more transmitters observed by one user are never observable from another user’s positions. For small N, ambiguities in the correspondences can arise depending on the relative geometry of the transmitters. On the other hand, the complexity increases with increasing N.
Based on the correspondence among transmitters, the rotation and translation of the two maps need to be calculated. In the literature, there are various ways to find the rotation and translation parameter, for example using minimum mean square error approaches for the extended orthogonal Procrustes problem. In addition, the variances of the transmitter PDFs may be taken into account.
We have started to perform simulations to evaluate our algorithm. We regard the root mean square error (RMSE) of a user in Channel-SLAM when we use prior maps and compare it to the case where we do not use prior maps. As expected, our first preliminary results show that the RMSEs of the user position when using and when not using prior maps are the same in the beginning when no match among the prior map and the user map has been found yet. Once the estimates for the transmitters in the user map have converged far enough, a match among user and prior map can be found. From this moment on, the user RMSE decreases for the case when we use prior maps, and it stays considerably far below the RMSE when no prior map is used.
The possibility of exchanging maps of physical and virtual transmitters among users extends Channel-SLAM from a single user to a cooperative radiolocation algorithm. Users can cooperate by exchanging their estimates for physical and virtual transmitter states. Once a match has been found among the user map and the prior map, the transmitters in the prior map can be used as prior information when a new transmitter is initialized. The high uncertainty of transmitters that are initialized, i.e., the high variance in the transmitter PDFs, can therefore be avoided, and the user position estimate can be corrected. This increases the performance of Channel-SLAM in terms of both accuracy and computational complexity. The first preliminary results of our simulations show that such cooperation considerably decreases the RMSE for the users as prior information from transmitter maps can be used for initializing transmitters. In particular for long-term Channel-SLAM, we expect that the user RMSE can be decreased drastically. In addition, if the relation of a prior map to global coordinates is known, the user position can be determined on a global scale. This extends Channel-SLAM from a relative to a global localization algorithm.