Wi-Fi positioning system

RSSI localization techniques are based on measuring signal strength from a client device to several different access points, and then combining this information with a propagation model to determine the distance between the client device and the access points. Trilateration (sometimes called multilateration) techniques can be used to calculate the estimated client device position relative to the known position of access points.[11][14]

Though one of the cheapest and easiest methods to implement, its disadvantage is that it does not provide very good accuracy (median of 2-4m), because the RSSI measurements tend to fluctuate according to changes in the environment or multipath fading.[5]

Cisco systems is using RSSI to locate devices through its Access Points. Access points collect the location data and update the location on the Cisco cloud called Cisco DNA Spaces.[16]

Traditional fingerprinting is also RSSI-based, but it simply relies on the recording of the signal strength from several access points in range and storing this information in a database along with the known coordinates of the client device in an offline phase. This information can be deterministic[5] or probabilistic.[7] During the online tracking phase, the current RSSI vector at an unknown location is compared to those stored in the fingerprint and the closest match is returned as the estimated user location. Such systems may provide a median accuracy of 0.6m and tail accuracy of 1.3m.[14][17]

Its main disadvantage is that any changes to the environment, such as adding or removing furniture or buildings, may change the "fingerprint" that corresponds to each location, requiring an update to the fingerprint database. However, integration with other sensors such as cameras can be used in order to deal with a changing environment.[18]

Linear array of antennas receiving a signal. The phase-shift difference of the received signal arriving at antennas equally separated by a "d" distance is used to compute the angle of arrival of the signal. Picture reproduced from [14]

With the advent of MIMO Wi-Fi interfaces, which use multiple antennas, it is possible to estimate the AoA of the multipath signals received at the antenna arrays in the access points, and apply triangulation to calculate the location of client devices. SpotFi,[14] ArrayTrack[10] and LTEye[19] are proposed solutions which employ this kind of technique.

Typical computation of the AoA is done with the MUSIC algorithm. Assuming an antenna array of ${\displaystyle M}$ antennas equally spaced by a distance of ${\displaystyle d}$ and a signal arriving at the antenna array through ${\displaystyle L}$ propagation paths, an additional distance of ${\displaystyle d\sin \theta }$ is traveled by the signal to reach the second antenna of the array.[14]

Considering that the ${\displaystyle k}$-th propagation path arrives with angle ${\displaystyle \theta _{k}}$ with respect to the normal of the antenna array of the access point, ${\displaystyle \gamma _{k}}$ is the attenuation experienced at any antenna of the array. The attenuation is the same in every antenna, except for a phase shift which changes for every antenna due to the extra distance traveled by the signal. This means that the signal arrives with an additional phase of

${\displaystyle -2\pi \cdot d\cdot \sin(\theta )\cdot (f/c)\cdot (2-1)}$

at the second antenna and

${\displaystyle -2\pi \cdot d\cdot \sin(\theta )\cdot (f/c)\cdot (m-1)}$

at the ${\displaystyle m}$-th antenna.[14]

Therefore, the following complex exponential can be used as a simplified representation of the phase shifts experienced by each antenna as a function of the AoA of the propagation path:[14]

$${\displaystyle \phi (\theta _{k})=\exp(-j\cdot 2\pi \cdot d\cdot \sin(\theta _{k})\cdot f/c)}$$

The AoA can then be expressed as the vector ${\displaystyle {\vec {a}}(\theta _{k})\gamma _{k}}$ of received signals due to the ${\displaystyle k}$-th propagation path, where ${\displaystyle {\vec {a}}(\theta _{k})}$ is the steering vector and given by:[14]

$${\displaystyle {\vec {a}}(\theta _{k})=[1,\ \phi (\theta _{k}),\ \dots ,\ \phi (\theta _{k})^{M-1}]^{T}}$$

There is one steering vector for each propagation path, and the steering matrix ${\displaystyle \mathbf {A} }$ (of dimensions ${\displaystyle M\cdot L}$) is then defined as:[14]

$${\displaystyle \mathbf {A} =[{\vec {a}}(\theta _{1}),\dots ,{\vec {a}}(\theta _{L})]}$$

and the received signal vector ${\displaystyle {\vec {x}}}$ is:[14]

$${\displaystyle {\vec {x}}=\mathbf {A} {\vec {\Gamma }}}$$

where ${\displaystyle {\vec {\Gamma }}=[{\vec {\gamma }}_{1}\dots {\vec {\gamma }}_{L}]}$ is the vector complex attenuations along the ${\displaystyle L}$ paths.[14] OFDM transmits data over multiple different sub carriers, so the measured received signals ${\displaystyle {\vec {x}}}$ corresponding to each sub carrier form the matrix ${\displaystyle \mathbf {X} }$ expressed as:[14]

$${\displaystyle \mathbf {X} =[{\vec {x}}_{1}\dots {\vec {x}}_{L}]=\mathbf {A} [{\vec {\Gamma }}_{1}\dots {\vec {\Gamma }}_{L}]=\mathbf {AF} }$$

The matrix ${\displaystyle \mathbf {X} }$ is given by the channel state information (CSI) matrix which can be extracted from modern wireless cards with special tools such as the Linux 802.11n CSI Tool.[20]

This is where the MUSIC algorithm is applied in, first by computing the eigenvectors of ${\displaystyle \mathbf {X} \mathbf {X} ^{H}}$ (where ${\displaystyle \mathbf {X} ^{H}}$ is the conjugate transpose of ${\displaystyle \mathbf {X} }$) and using the vectors corresponding to eigenvalue zero to calculate the steering vectors and the matrix ${\displaystyle \mathbf {A} }$.[14] The AoAs can then be deduced from this matrix and used to estimate the position of the client device through triangulation.

Though this technique is usually more accurate than others, it may require special hardware in order to be deployed, such as an array of six to eight antennas[10] or rotating antennas.[19] SpotFi[14] proposes the use of a superresolution algorithm which takes advantage of the number of measurements taken by each of the antennas of the Wi-Fi cards with only three antennas, and also incorporates ToF based localization to improve its accuracy.

Figure showing a measuring station sending a DATA frame to a client station and waiting until receiving the ACK. ${\displaystyle \delta }$ is the scheduling delay (offset) originated at the target client device, and it depends on how much time it takes for the ACK to be scheduled. T_P is the signal propagation time between transmitter and receiver, and is usually assumed to be the same on the way to the target and back. T_ACK is the time needed to transmit the ACK frame. The time of flight corresponds to the T_MEASURED. Picture reproduced from [21]

Time of flight (ToF) localization approach takes timestamps provided by the wireless interfaces to calculate the ToF of signals and then use this information to estimate the distance and relative position of one client device with respect to access points. The granularity of such time measurements is in the order of nanoseconds and systems which use this technique have reported localization errors in the order of 2m.[14] Typical applications for this technology are tagging and locating assets in buildings, for which room-level accuracy (~3m) is usually enough.[22]

The time measurements taken at the wireless interfaces are based on the fact that RF waves travel close to the speed of light, which remains nearly constant in most propagation media in indoor environments. Therefore, the signal propagation speed (and consequently the ToF) is not affected so much by the environment as the RSSI measurements are.[21]

Unlike traditional ToF-based echo techniques, such as those used in RADAR systems, Wi-Fi echo techniques use regular data and acknowledgement communication frames to measure the ToF.[21]

As in the RSSI approach, the ToF is used only to estimate the distance between the client device and access points. Then a trilateration technique can be used to calculate the estimated position of the device relative to the access points.[22] The greatest challenges in the ToF approach consist in dealing with clock synchronization issues, noise, sampling artifacts and multipath channel effects.[22] Some techniques use mathematical approaches to remove the need for clock synchronization.[15]

More recently, the Wi-Fi Round Trip Time standard has provided fine ToF ranging capabilities to WiFi.