# The Big Picture of Localization

Digital Signal Processing (DSP) enables us to find the range of a device transmitting a wireless signal with a particular structure under some conditions. To understand how this process works, we need to look at the big picture of a localization process. Localization implies locating the unknown position of a source which can be computed in a straightforward manner if its ranges from some reference nodes can be found.

Various techniques are employed for this purpose, some of which are Received Signal Strength Indicator (RSSI), time of arrival, time difference of arrival and angle of arrival. Phase of arrival is a special case of time of arrival scheme which is extremely accurate due to the high frequency carrier resembling a high resolution clock. This method works even in the absence of synchronization among nodes. Here, I will discuss various arrangements under which finding the range and/or position of the device becomes feasible for time of arrival technique. It is worth noting that since phase is just another manifestation of time, the underlying principles stay the same.

## One Way Transmission

Let us start with a transmitter Tx whose signal is received by a receiver Rx. The electromagnetic signal travelling at a speed of $c=3\cdot 10^8$ m/s takes a finite amount of time $\tau$ to arrive at the Rx. This is shown in the figure below and from basic physics, the range $R$ is given by
\begin{equation*}
R = c\tau
\end{equation*}

This propagation delay $\tau$ is our main target for ranging purpose. However, since each node starts at a random time, there is a clock offset between its time as compared to the real time. At an arbitrary real time 0, the time offset of the Tx is $\theta_{\text{Tx}}$ while that of of the Rx is $\theta_{\text{Rx}}$.
\begin{equation*}
\begin{aligned}
T_{\text{Tx}} &= t + \theta_{\text{Tx}} \\
T_{\text{Rx}} &= t + \theta_{\text{Rx}}
\end{aligned}
\end{equation*}
where $t$ is the real time. What happens at the Rx side if we implement one way transmission in which the Tx emits the wave at real time $t_{\text{Tx}}$ received by the Rx at real time $t_{\text{Rx}}$?
\label{eq1WayTransmission1}
t_{\text{Rx}}-\theta_{\text{Rx}} = t_{\text{Tx}} – \theta_{\text{Tx}} + \tau

We can reduce three unknowns to two by combining the individual phase offsets into one entity $\theta$.
\begin{equation*}
\theta = \theta_{\text{Rx}} – \theta_{\text{Tx}}
\end{equation*}
Then, Eq (\ref{eq1WayTransmission1}) can be written as
\label{eq1WayTransmission2}
t_{\text{Rx}} = t_{\text{Tx}} + \theta + \tau

This equation still has two unknowns $\theta$ and $\tau$. As a side remark, notice in the above figure that unique range can only be found if the distance between the Tx and Rx is within one wavelength only. At high carrier frequencies, e.g., 2.4 GHz where the wavelength is just 12.5 cm, the phase of arrival method seems impractical due to $2\pi$ phase ambiguity. Nevertheless, transmissions at multiple carrier frequencies solve this range ambiguity problem in frequency domain.

To summarize, we get only one equation from this procedure and hence it becomes impossible to separate the phase offset $\theta$ from propagation delay $\tau$ in time domain. There are several ways in which one or more extra equations can be provided to this system for range determination.

## Solution 1: Synchronization

We can synchronize the two nodes which implies that $\theta$ becomes zero. From Eq (\ref{eq1WayTransmission2}), we can write

\begin{equation*}
t_{\text{Rx}} = t_{\text{Tx}} + \tau
\end{equation*}

This leaves us with one equation and one unknown, i.e., delay $\tau$. Synchronizing the Tx and Rx is not straightforward however and consumes resources either in terms of cost or computations.

## Solution 2: Back and Forth Transmission

Realizing that two unknowns can be solved through a system of two equations, we can provide an extra independent equation through back and forth transmission between the Tx and Rx. The original timestamps or phases at the Tx and Rx during the forward transmission can now be denoted with the subscript 1 while the subscript 2 can be used for the backward transmission from the Rx to the Tx.
\begin{equation*}
\begin{aligned}
t_{Rx,1} &= t_{Tx,1} + \theta + \tau \\
t_{Tx,2} &= t_{Rx,2}~ – \theta + \tau
\end{aligned}
\end{equation*}

In this scenario, the phase offset $\theta$ appears with a negative sign in the second equation because timing or phase measurement is done at the transmitter (known as the initiator here). If you are unsure about this sign change, start with the basic definitions of phase offsets mentioned before. Now we have two equations that can solve the two unknowns $\theta$ and $\tau$. Multiple carrier phases can also be utilized for ranging purpose in multipath channels.

## Solution 3: Motion

The above system of equations provides a second independent equation in terms of a negative sign with the phase offset $\theta$ where the first equation contains $+1$ as the coefficient for both $\theta$ and $\tau$. This concept can be generalized to provide a second equation to this system with any other coefficient to either $\theta$ or $\tau$. This is difficult to accomplish this with the phase offset $\theta$. On the other hand, we can always move one node around that changes the coefficient that appears with $\tau$ without affecting the phase offset $\theta$.

For example, if the Rx moves twice as far as compared to the original range, we get

\begin{equation*}
\begin{aligned}
t_{Rx,1} &= t_{Tx,1} + \theta + \tau \\
t_{Rx,2} &= t_{Tx,2} + \theta + 2\tau
\end{aligned}
\end{equation*}

Note that both transmissions in this case are in the same direction from the Tx to the Rx, as opposed to the back and forth solution. A subtle but really important point here is to come up with a strategy to produce a known coefficient for delay $\tau$ which in general is not easy due to $\tau$ itself being unknown. Researchers have come up with several smart algorithms for this purpose, one of which was very well explained by Marcus Müller during a short discussion with me on discuss-gnuradio archive.

Imagine a receiver with knowledge of the transmitted signal. While lacking a common time base, a receiver can infer distance from the development of the phases of entries of a sufficiently large (in both number of OFDM symbols and number of subcarriers) OFDM frame.

The idea is simple: assume you know the symbols at the transmitter. The speed-of-light induced delay is constant across all subcarriers. The resulting phase shift, thus, is proportional to the subcarrier frequency, and hence the subcarrier number. Therefor, when you observe linear channel phase change over subcarrier, you can get a distance estimate. Phase being a linear function of index implies we’re dealing with a sinusoid – and a DFT in subcarrier direction will give us a range plot.

Same idea for Doppler, but with phase on the same subcarrier, but for consecutive and hence constant-interval OFDM symbols; do another DFT for each subcarrier across OFDM symbols, and get a doppler plot.

Overall: Write down your received OFDM symbols as column vectors of a matrix, point-wise divide by the transmitted symbols (normalize amplitude if helpful); the result is a matrix full of complex numbers with the channel phase for each subcarrier at each symbol time. Do an appropriate 2D-DFT, get a range/doppler plane “image”. Find the peak; use clever interpolation / post-processing to increase resolution and/or reduce estimate variance. See Ref. [1] for details.

## Extra Reference Nodes

All three solutions above are applicable to a Tx and a Rx only. To obtain extra equations for this system, we can place extra anchor nodes around the Tx with known positions. The problem here is that exactly the same number of extra phase offsets appears in the set. To alleviate this problem, these anchor nodes can be synchronized which is how a GPS Rx finds its position through a synchronized network of satellites. Assuming perfect synchronization among them, the receiver phase offset $\theta$ is the same for all received satellite signals.

Another option is that after the Tx signal is received by all surrounding nodes, one node can respond with a reply message which makes the phase offsets appear with negative signs making the system solvable. This is usually known as ranging through one-way transmission (or blink mode) because target node has to transmit only once.