%\section{Wi-Fi Range Measurements}
%\label{sec:ftm}
%
%Ganz grundsätzlich zwei drei Sätze dazu. Distanzen sind gut für Lokalisierung weil... Kurz die Unterschiede der Beiden.
%
%\subsection{Fine Timing Measurement}
%\begin{itemize}
%	\item New IEEE 802.11mc standard to measure round trip time from client to access point.
%	\item Theory, protocol.
%	\item Expected error behavior 
%\end{itemize}
%
%
%FTM defines a protocol to measure the round trip time between an initiator and a responder, e.g. a smartphone based client and access point.
%For data privacy reasons the responder is always passive and only the initiator can trigger time measurements.
%
%\subsection{Received Signal Strength Indication}
%
%Klassisch RSSI mit Log Distance Modell... 
%steckt die rssi in das log distance modell und bekommt eine distanz raus. baby easy
%
%\subsection{Measurement Pre-Filtering}
%
%<zeige fehlerplots mit range messungen>
%
%wenn man sich die messungen nun ansithet, dann... argumentiere kalmanfilter über diese range messungsplots und begründe warum er die messdaten stabiler macht.
%kalman auf rssi ist erstmal nicht so klug weil kalman linear und rssi nicht linear sind. in LOS konditionen ist rssi logritmisch und in NLOS ganz was anders... nicht-linear halt 
%in den späteren evaluatieren werden wir uns aber dennoch raw vs pre-filtering ansehen, um ein bessere gefühl dafür zu bekommen was es in welcher situation bringt
%
%Filter measurements per AP with simple Kalman filter before localization
%
%RSSI leichter messbar und einfach gegegeben, aber abhänigi von umgebung  - coarsely quantized 
%RTT deutlich komplexer zu messen, daher eigener FTM Standard. Super-resolution?!



\section{Wi-Fi Range Measurements}
\label{sec:ftm}

An obvious approach to estimate a location is to measure the distance between the current unknown position and known positions.
Given multiple measurements to different reference points an absolute position in a local coordinate system can be found.
With ideal distance measurements to several known positions it is straightforward to calculate the current position.
However, in the present of noisy and imperfect measurements estimating a precise position is a challenging problem.
%TODO Harte bruch 
For a smartphone based indoor localization system using the existing Wi-Fi infrastructure is a reasonable choice.
In this work signal strength and signal propagation time based distance measurements are considered.

\subsection{Received Signal Strength Indication}
% TODO dBm vs dB??

Received Signal Strength Indication (RSSI) is a measure of the received RF power and is obtained by the radio hardware at the antenna connector using an analog-to-digital converter.
It's value is usually expressed in \si{\dBm} and quantified to integer values.
For indoor localization RSSI is often used to deduce the distance from a smartphone to the access point, because it is virtually always available on common devices.

In order to calculate the distance from RSSI a appropriate signal strength prediction model needs to be chosen.
The \docLogDistance{} model is commonly used to predict the received signal strength $P_i$ from an AP $i$ at a given distance $d_i$.
Formally given with
\begin{equation}
	P_i = \mTXP - 10 \mPLE \log_{10}{\frac{\mMdlDist_i}{\mMdlDist_0}} + \mathcal{X}_{\sigma_i} \text{,}
	\label{eq:logDistModel}
\end{equation}
where $\mTXP$ denotes the sending power in \si{\dBm} of the AP at reference distance $\mMdlDist_0$ (usually \SI{1}{\meter}), $\mPLE$ is the path loss exponent, which value needs to be empirically chosen for the given environment.
The added zero-mean Gaussian random variable $\mathcal{X}_{\sigma_i}$ with a variance of $\SIm{\sigma^2_i}{\dBm}$ models signal fading and random channel noise.
Hence, the measured RSSI is assumed to follow a normal distribution $P_i \sim \mathcal{N}(P_i^*, \sigma_i^2)$, where $P_i^*$ is the expected RSSI and $\sigma_i^2$ is the variance of the measurement.
%, both given in \si{\dBm}.

The \docLogDistance{} model can be reformulated to compute the distance $d_i$ based on the measured RSSI $P_i$ and assuming $d_0=\SI{1}{\meter}$ with
\begin{equation}
  \log_{10}{d_i} = \frac{\mTXP-P_i}{10\mPLE}  +  \frac{\mathcal{X}_{\sigma_i}}{10\mPLE }
\end{equation}
\begin{equation}
%  d_i = 10^{(\mTXP-P_i) / 10\mPLE} + 10^{\mathcal{X}_{\sigma^2_i}/10\mPLE}
%  d_i = 10^{\sfrac{(\mTXP-P_i + \mathcal{X}_{\sigma_i})}{10\mPLE}}
  d_i = 10^{  (\mTXP-P_i + \mathcal{X}_{\sigma_i}) / 10\mPLE}
\end{equation}

Since $\mathcal{X}_{\sigma_i}$ is a Gaussian random variable, the logarithm of $d_i$ is normally distributed as well.
Consequently, the distance $d_i$ follows a log-normal distribution, $\ln{d_i} \sim \mathcal{N}(d_i^*, \sigma_{i,d}^2)$, where $d_i=\ln(10) \frac{P_0 - P_i}{10\mPLE}$ is the expected distance and $\sigma_{i,d}^2=\left( \frac{\ln(10)\sigma_i}{10\mPLE} \right)^2$ is the variance of the distance.

In free space the value of the path loss exponent is $\mPLE=2$.
In indoor scenarios $\mPLE$ accounts for the architecture around the AP, thus a single global factor is chosen for the whole building.
%This restricts the \docLogDistance{} model to a uniform view on the complete environment and does not allow to differentiate between different types of materials, and ignores  which walls are actually transmitted the signal.

This restricts the \docLogDistance{} model to a uniform view on the whole environment and does not take the actual propagation path of the signal into account.
Therefore, the model does not consider the actual environmental effects or geometry, and thus makes it impossible to differentiate between different types of obstacles or wall materials.

In order to take walls into account the model must include the power loss of every traversed wall, which results in the wall-attenuation factor model \cite{TODO}.
Often the dampening factors of walls are unknown or hard to measure.
Additionally, the computation of the wall-attenuation factor model requires costly intersection tests with the geometry of the environment which can be intractable to perform on a regular smartphone.

%Another approach is to take measurements at known positions distributed throughout the building.
%These fingerprints can then be used in the localization phase to obtain the current position with a nearest neighbour search.
%Given the current RSSI value the most likely position is the one which is closest to other similar RSSI fingerprints.
%This method includes the characteristics of the environment into the prerecorded fingerprints.
%Recording the fingerprints is a time-consuming and tedious process for large buildings and needs to be redone whenever the environment changes significantly.
 
%While fingerprinting can increase the accuracy of the localization computing the distance from the RSSI directly is easier to deploy.
 
%However, RSSI values are often coarsely quantized, depend heavily on the environment, differ from device to device, and are affected by the interferences.

%- free space loss
%- walls
%, also dynamic obstacles like persons can interfere with the signal.


\subsection{Fine Timing Measurement}
%Time-based distance measurements are intuitively based on the delay the signal took to travel from the sender to the receiver.
%Multiplied by the propagation speed of light results in the distance between the two nodes.
%The propagation speed of the signal depends on the propagation medium and is slower in media with higher relative permittivity compared to air, like concrete walls.
%However, for most indoor environments the signal propagation speed can be assumed to be constant, as the total travel distance in non-air media is usually negligible short compared to the travel distance in air \cite{marcaletti2014filtering}.
%For that reason, time-based distance measurements are assumed to be more robust compared to received power measurements, because the propagation path and interaction with the environment is inherent in the measurement.

As mentioned above, time-based distance measurements are intuitively based on the delay the signal took to travel from the sender to the receiver.
A straightforward method to measure the propagation delay of a signal is time of arrival (ToA), where the propagation time of the signal is computed from absolute time values measured at the transmitter and receiver.
This method is used famously in satellite navigation, \eg GPS.
While being precise, ToA requires costly high precision synchronized clocks, which are not suitable for indoor localization.

Two way ranging (TWR) eliminates the requirement for synchronized clocks.
\ieeWifiFTM{} defines the fine timing measurement (FTM) protocol, which implements the TWR method for standard conform WiFi devices.
Note that it is not necessary to implement FTM capabilities to be a \ieeWifiFTM conform device.
This made time-based distance measurements broadly available for WiFi based systems and relevant for smartphone based indoor localization.
Instead of using absolute time, the round trip time is measured based on time differences at the sender and receiver.
As successive time measurements are only done at one site synchronized clocks are not required.
By definition the responder (\eg AP) is passive while the FTM initiator (\eg smartphone) actively requests FTM measurements.
The FTM protocol is shown in \figref{TODO}.

The procedure starts with an initial FTM request frame send by the initiator, which can be rejected or accepted by the responder.
If the responder agrees to the request it sends an acknowledge frame.
Following, the responder stores the current time $t_1$, which represents the start of the measurement, and sends a FTM frame.
At the initiator the time $t_2$ is recored as soon as the incoming signal is detected at the antenna.
After receiving the FTM frame the initiator prepares a ACK frame and sends it to the responder.
However, to account for the signal processing delay of the initiator's hardware it is necessary to record an additional timestamp $t_3$ when the ACK frame is transmitted. % TODO detail wie wird t_3-t_2 übertragen?

When the ACK frame is received at the responder at time $t_4$ the responder can calculate the round trip time of the signal by subtracting $t_1$ from $t_4$.
To exclude the processing delay of the initiator the difference between $t_2$ and $t_3$ is subtracted from the total round trip time, which results in the propagation delay of the signal
\begin{equation}
  \text{ToF} = (t_4-t_1) - (t_3-t_2) \text{.} % TODO besseres Symbol als RTT
\end{equation}

Measuring ToF only once is usually not sufficient. 
While RF power is relatively simple to measure, obtaining accurate ToF values at a small resolution like nanoseconds needs much more caution, as the measurements are sensitive to noise.
Relatively small deviations from the real time value result in a vast error in the distance estimate, \eg a measurement error of \SI{10}{ns} results in a distance error of \SI{3}{m}.
For this reason the above outlined procedure is repeated multiple times to reduce the impact of noise.
In fact, a single FTM measurement or burst instance, consists of many FTM-ACK exchanges and the final value $\text{ToF}^*$ is the average over $n$ measurements
\begin{equation}
  \text{ToF}^* = \frac{1}{n} \sum_{k=1}^{n} \left[ (t_{4,k}-t_{1,k}) - (t_{3,k}-t_{2,k}) \right]
\end{equation}

After calculating the average ToF the responder transfers the result to the initiator where the result can be processed by an application.
With increasing $n$ the impact of noise is lessened, but the delay until the FTM measurement is available for the consuming software increases.
Therefore, the actual choice of the value of $n$ is a trade-off between precision and measurement delay.

Assuming that the signal propagates constantly at the speed of light the distance between initiator and responder is trivially given with
\begin{equation}
  d = \frac{\text{ToF}}{2} \cdot c
\end{equation}
%TODO ToF -> distance ToF/2 * c
%TODO IEEE 802.11-2016 6.3.58.1


The accuracy of distance estimate depends on the ability of the hardware to detect the line-of-sight signal, or direct path.
In an indoor environment it is very common that a signal will reach the receiver from different paths with different lengths.
The prime example is a signal which reaches the receiver via a direct line-of-sight propagation plus two reflected paths of the same length.
As the reflected paths have the same length and phase they constructively interfere at the receiver resulting in a higher receiving power compared to the direct connection.
The difficulty in such multipath scenarios is to distinguish the direct path from the reflected paths \cite{ibrahim2018verification}, or that the direct path signal gets undetected because of interference \cite{TODO}.
Also, if the delay of the reflected paths is near the time resolution of the hardware, the multipath components will degrade the precision of the time of arrival estimate.
This results in an over-estimate of the propagation time of the signal, and consequently in the range estimate.
The limiting factor is the sampling rate of the receiving hardware, which is defined by the channel bandwidth.
Hence, the time resolution is proportional to the inverse of the bandwidth.

In \ieeWifiN the channel bandwidth is \SI{20}{Mhz} in the \SI{2.4}{GHz} range which results in a sampling rate of one sample every \SI{50}{ns}, or one sample every \SI{12.5}{ns} for \SI{80}{Mhz} channels in the \ieeWifiAC \SI{5}{GHz} range.
Assuming that the receiver recognizes the signal at the first sample of the preamble the smallest possible resolution of the range estimate is \SI{15}{m} for \SI{20}{Mhz} bandwidth, and \SI{3.74}{m} for \SI{80}{Mhz}.
To allow much finer resolution the receiver uses super resolution methods to allow sub-sample resolution \cite{TODO}.
%TODO genaue implementierung unbekannt und daher black box
%Therefore, time-based distance estimates can greatly differ from the ideal euclidean distance.

In addition to distance measurements the \ieeWifiFTM standard defines a format to transfer location information about the responder.
This allows to add new access points dynamically to the localization system without updating the initiators, \ie smartphone, as the access point can be configured to know its position and can transmit this information to the smartphone.

%Error sources:
%multipath propagation, noise, finite sample rate

