Techniques de localisation en Environnement Intérieur utilisant les Réseaux WiFi
Sujet proposé par
Directeur de thèse:
Unité de recherche
Laboratoire de recherche d'EURECOM
Domaine: Sciences et technologies de l'information et de la communication
When GPS (or GNSS) is not available, location estimation can be based on wireless communication infrastructure. One prime technology candidate is WiFi since it is generally ubiquitously present indoors and it uses a microcellular layout that should be beneficial for indoor location estimation precision. The open character of WiFi leads to a fairly straightforward development of basic location estimation apps in smartphones as mentioned in , which also illustrates an important use case in hospitals, where navigation aid in complex building structures can be quite helpful. See also  for a WiFi based location estimation and services app developer and various application scenarios. In recent years, the integration of location estimation in cellular standards such as GSM, 3G and LTE has spilled over to other wireless standards such as WiFi and Bluetooth . The explosion of the importance of location estimation and mapping technology is also illustrated by the number of acquisitions by Apple of startups specialized in these techniques .
Indoor location estimation however is significantly more difficult than in the outdoor case, due to the typically much more pronounced multipath and the frequent Non Line of Sight (NLoS) configuration, see e.g.  for a study in the context of Bluetooth. This difficult context leads to another problem, which is that of reproducible research. Whereas most wireless system performance depends heavily on the environment, this is particularly true for indoor positioning where the location accuracy can depend enormously on the particular indoor environment. This issue is tackled in the EU project EVARILOS . The
study in  on the other hand, which in the context of GSM data, illustrates though that precise indoor location estimation is possible if enough data is available.
State of the Art Technical Ingredients
1 Propagation Law Based Techniques
Geometric techniques include Time-of Arrival, (ToA), Time Difference-of-Arrival (TDoA), and Direction-of-Arrival (DoA) based methods. Those methods combine measurements from different Access Points (Aps) in order to obtain an estimate of the Mobile Terminal (MT) location.
In the TOA-based radiolocation technique, the distance between an MT and an AP is obtained by finding the one-way (or two-way) propagation time between that MT and that AP and multiplying it by the propagation velocity (i.e. speed of light). Geometrically, this provides a circle, centered at the AP, on which the MT must lie. By using multiple APs, the location of the MT can be resolved by triangulation . The ToA technique requires accurate synchronization between the AP and MT clocks so that the measurements are adequate for the actual distances. Many of the current standards only mandate tight timing synchronization among APs. In addition, the MT clock itself might have a drift which directly generates an error in the location estimate.
The TDoA-based radiolocation technique relies on the measurement of the time difference of arrival of a signal sent by the MT and received by several APs. The constant time difference between two APs defines a hyperbola, with foci at the APs, on which the MT must lie. The intersection of two hyperbolic loci will define the 2D position of the MT. An important issue for TDoA systems is that they are not affected by errors in the MT clock time as this latter cancels out when subtracting two ToA measurements. However the need for the synchronicity of the is still needed. This may require additional equipment that is called Location Measurement Units.
DoA techniques assume that at least one AP is equipped with an antenna array, so that transmit and receive signals are beamformed. Only 2 APs are required for MT location estimation. However an ambiguity region does exist on the line in between both APs. Therefore a 3rd AP is preferred. An alternative is 2 APs plus a measurement of another type. One DoA and one ToA or TDoA measurement can ensure location estimation.
E.g.  discusses and illustrates possibilities and fundamental limitations associated with mobile positioning based on available wireless network measurements. This article does not address a specific communication technology, but instead compares in a generic way the performance of different measurement categories based on the Cramer-Rao Lower Bound (CRLB) or its approximations. The article discusses RSS, ToA, TDoA, DoA, digital map information, and position estimates as measurement types. Specific issues on accuracy limitation in each measurement, such as synchronization and multipath problems, are only briefly commented upon. The paper not only considers static positioning solutions, but also dynamic positioning taking into account a mobility model and an adaptive filter. Mobility models addressed in the paper are random walk, velocity sensor, random force and inertial sensor models. The paper considers the LMS, RLS, EKF and PF adaptive filters.
1.4 Non Line of Sight (NLoS) Techniques
Propagation law based approaches for NLoS are mostly based on the Single Bounce Model, as e.g. studied in . The idea here is that after the LoS path, the strongest multipath components tend to be those paths that underwent a single scattering (reflection, diffraction), hence the term “single bounce” path. When exploiting such paths, one also has to consider the estimation of the scatterer position. Hence, for a single bounce path to bring net information, it needs to be characterized by a number of independent parameters (e.g. DoA, ToA, Direction of Departure (DoD)) that exceeds the number of scatterer coordinates (2 in the case of 2D). In some recent developments, an indoor variant of these techniques considers that the scatterers are necessarily positioned on the walls, ceiling or floor, reducing the number of (continuous) unknowns in the scatterer position (but adding
discrete unknowns (which wall)). This approach in principle also allows to handle multibounce.
2 Fingerprinting Techniques
As described in , fingerprint-based techniques consist of two phases: an offline training phase and an online localization phase    . . In the offline phase, a radio map is built by tabulating RSS measurements received from signal transmitters at predefined locations in the area of interest. These values comprise a radio map of the physical region, which is compiled into a deterministic or probabilistic model for online localization. In the online localization phase, the real-time RSS (Received Signal Strength) samples received from signal transmitters are used to search the radio map to estimate a user’s current location based on the learned model.
In the offline phase, a learned location-estimation model is essentially a mapping function between the signal space and the location space. Deterministic techniques build such a mapping by simply storing the average RSS values at a collection of known locations, and use the nearest neighbour method to locate a client. Probabilistic techniques, on the other hand, construct the mapping by storing the RSS distributions as the content of a radio map. The distributions are then used in a maximum likelihood calculation for localization. With sufficient training data, probabilistic methods are typically more accurate than their deterministic counterparts by directly handling the uncertainty of RSS measurements.
More powerful fingerprints than RSS are possible. E.g. in  we studied the Power Delay Profile fingerprint, which may allow localization in Non Line of Sight scenarios, and even with the channel response of a single link.
3 Information Fusion and Side Information
Other approaches consider the fusion of information from several links, information of different nature (e.g. ToA and DoA), and the exploitation of side information such as inertial sensors and compass (in smartphones) and maps (as in Simultaneous Localization and Mapping (SLAM)).
The interest of RivieraWaves is to constitute Intellectual Property that can be of interest for WiFi and Bluetooth clients.
1 More refined RSS modeling
More precise statistical models are required for the RSS, that take into account NLoS and multipath propagation. One approach is to consider modeling the whole Power Delay Profile (PDP), starting from distance based attenuation that induces a delay profile mask. E.g. the curvature of this mask (a PDP upper bound) provides information on the range, and is parameterized by the attenuation exponent. Such finer statistical models should allow improved Maximum Likelihood distance and position estimation.
2 Joint RSS and DoA Techniques
Here we consider extensions to multiple antennas. The joint modeling of RSS and DoA may lead to improved statistical models. The focus will not only be on the LoS but also on multipath components. In the multi-antenna case, the RSS and power delay profile can be considered on beamformed channels, which have particular characteristics.
The MIMO (multi input multi output) scenario also leads to perspectives for improved DoA estimation on the access point side. Even though the antenna array response on the mobile terminal may not be parameterized in terms of angles, the presence and estimation of a (non-parametric) array response on the mobile side should allow better resolution of the antenna arrays responses at the access point side, and hence better DoA estimation.
An important aspect for DoA estimation is calibration. Here the channel feedback from the terminal to the access point could be exploited usefully.
One aspect of interest to RivieraWaves also is to exploit as much the existing building blocks in e.g. the WiFi standard, with for instance the channel estimation in the frequency domain. This poses a particular constraint on the algorithms to be developed.
3 Database Techniques
Fingerprinting techniques may also be considered. In this case the building of the database needs to be explored, the required resolution needs to be studied and also its sensitivity to the presence of people and other perturbations needs to be investigated.