With the growth in the Internet of Things (IoT) products, the number of applications requiring an estimate of range between two wireless nodes in indoor channels is growing very quickly as well. Therefore, localization is becoming a red hot market today and will remain so in the coming years.
One question that is perplexing is that many companies now a days are offering cm level accurate solutions using RF signals. The conventional wireless nodes usually implement synchronization techniques which can provide around level accuracy and if they try to find the range through timestamps, the estimate would be off by
where is the approximate speed of an electromagnetic wave. So how are cm level accurate solutions being claimed and actually delivered?
This is a classic example of the simplest of signals solving the most complex of problems.
In this article, my target is to explain the fundamentals behind this high resolution ranging in the easiest of manners possible. Needless to say, while each product would have its own unique signal processing algorithms, the fundamentals still remain the same.
The Big Picture
For the sake of providing the big picture, remember that there are other methods available, the best of which are based on optical interferometry. Then, there are ultrasound, optical and hybrid options available as well. RF is the cheapest solution though and there is nothing better than getting accurate measurements using the RF waves.
The following techniques are most widely used in RF domain.
- Rx Signal Strength Indicator (RSS)
- Time of arrival (ToA)
- Phase of arrival (PoA) – a special case of ToA
- Time Difference of Arrival (TDoA)
- Angle of Arrival (AoA)
While I do not explain each of the above in detail (Google is your friend), I summarize their pros and cons below (anchors are wireless nodes with known positions).
Technique | Pros | Cons |
RSSI | Simple hardware, no synchronization required, info provided by most PHY chips | Highly inaccurate and environment specific |
ToA | Highly accurate | Time synchronization required among anchors and target node |
PoA | Extremely accurate, low cost | Sensitive to phase noise and impairments |
TDoA | Great accuracy, no target node synchronization | Tight synchronization among all anchors |
AoA | Extra dimension relaxes timing and phase constraints | Expensive hardware and less accurate |
As a final comment, all range estimation methods need a reference point. Anchors provide this reference when an accurate measurement of position is needed. If it is just the range from another node that is of interest, any node can use its own reference. This is the situation we assume in this article.
What is a Timestamp?
A typical embedded device comes with a counter and a register. The value of the counter increments/decrements as driven by an oscillator. When an increment counter reaches the maximum value (0xF…FF), or a decrement counter reaches the minimum value (0x0…00), it overflows and starts counting again. If a desirable event occurs, say a message arrival event driven by a Rx start interrupt, the value of the counter can be captured and stored in a register that can be later accessed to find the time of that event – according to the node’s own reference clock.
As an example, consider the following Figure where
- the timestamp value is captured in Register
- the Counter is an incremental counter
- Tx Start is an event that resets the counter, and
- Rx Start is an event that captures the Counter value to Register.
Figure 1: The counter, register and Tx and Rx start events
If you don’t know much about electronics, it is enough to know that event times can be recorded at a node and accessed for processing later.
If you want to subscribe to my email list below to receive new articles.
Setup
The ranging setup in this discussion consists of two nodes that can exchange timestamps with each other through the wireless medium as shown in Figure below.
Figure 2: Two nodes exchanging timestamps with each other
The distance between the two nodes is while the time of flight from one node to another is . Consequently,
We denote the real time by , Node A’s time by and Node B’s time by . Since each node starts at a random time, there is a clock offset between its time as compared to the real time.
Refer to the next Figure to observe how the chain of events unfolds.
Figure 3: The chain of events with their corresponding timestamps exchanged between Node A and Node B
Any node can start its counter at any given time. So to set a reference point at an arbitrary real time 0, the time offset of Node A is while that of of Node B is .
1. Node A sends its local timestamp to Node B at real time , where
2. Node B receives this packet at real time and records its local time , where
Clearly,
Therefore, we can write
Defining as and as (the clock offset between two nodes),
It is important to write the equation in the above form because all we know is the observation . We do not know , , , and .
3. After a processing delay, Node B sends its local timestamp at real time to Node A.
4. Node A records it at at actual time . Since ,
which can be written in terms of as
Adding Eq (1) and Eq (2) yields the estimate of delay.
Now it is clear that the time base of Node A serves as the reference for estimating this delay. Research literature refers to this approach as a ‘two-way message exchange‘. To pay tribute to Tolkien, I call it ‘There and Back Again‘.
Performance
I performed some ranging experiments with a wireless device with a clock rate of 8 MHz. That implies that one such tick takes . In terms of distance, this is m. Gradually increasing the distance, a divide by two operation and rounding off the results generated the following results.
Figure 4: Results for a ranging experiment with an 8 MHz clock
Assume that a 100x accuracy, say cm, is needed. Then, we need a clock generating timestamps at a rate of 800 MHz. That kind of expense and power, however, is more suited to computing applications and not to an embedded device.
In conclusion, we cannot afford a high rate clock but still desire a high resolution.
In the meantime, if you found this article useful, you might want to subscribe to my email list below to receive new articles.
The Arrival of the Phase of Arrival
In the spirit of time of arrival, this method is known as the phase of arrival. First, observe that we already have access to something similar to a high resolution clock – a continuous wave (CW). Consider a simple sinusoid at GHz frequency and just plot its sign. It looks very much like a very high rate clock.
Figure 5: Sign of a simple continuous wave is similar to a high rate clock
Now again consider two wireless nodes that are exchanging continuous waves instead of timestamps in the following manner.
1. Node A sends a continuous wave of frequency at its time (real time ) to Node B. Using , its phase is given by
where is just a constant and could easily be expressed as a single term . As opposed to timestamps case, it is not required, neither it is easy, to measure the phase explicitly.
2. Node B receives this continuous wave at real time when the phase of its own local reference at frequency at its local time , where , is
Using , Node B employs some signal processing algorithm to measure the phase difference between the two continuous waves as
It is important to write the equation in the above form because all
we know is the phase difference . We do not know anything else.
3. After a processing delay, Node B sends a continuous wave in the reverse direction.
4. Node A measures the phase difference
Adding Eq (3) and Eq (4) yields the estimate of delay.
That was so easy, so fast and so accurate. But the world is not that simple.
The Rollover Problem
The solution to the accuracy problem creates a problem of its own. Remember we said that when an increment counter reaches the maximum value (0xF…FF), or a decrement counter reaches the minimum value (0x0…00), it overflows and starts counting again. So if a clock is very fast, it overflows more quickly and resets again. It might even do so when the signal on the reverse path might not have returned! The same is the case with the sinusoids.
For example, a continuous wave at 2.4 GHz would roll over every cm. Any distance greater than 12.5 cm would be impossible to measure.
Introducing More Carriers
To solve this rollover problem, assume and start with plugging Eq (5) in the range expression.
This can be simplified using as
Now we can break the phase into an integer part and a fractional part because , where is the number of integer wavelengths spanning the distance while is the phase corresponding to the remaining fractional distance. Thus, the above equation can be written as
Writing the fractional phase as a function of range
The rollover unwrapping problem is now reduced to cancelling from the above equation. This can be easily accomplished by sending another tone at frequency that would generate the result
The above two equations can now be solved to cancel and create an effect equivalent to sending a single tone with a very large wavelength or very low frequency .
The range is now found to be
Having eliminated the phase rollover, we are interested in maximum range that can be unambiguously estimated through the above equation. Clearly, this depends on the frequency difference between the two continuous waves. Also, remember that can attain a maximum value of . Then, for example, for a 2 MHz difference, i.e., , the unambiguous range is
The Phase Slope Method
To cover all possible ranges, a number of difference continuous waves can be used and their results can be stitched together to form a precise range estimate. This is plotted in Figure below.
Figure 6: Phase vs frequency plot
After taking a number of measurements, a plot of phases versus frequencies is drawn. Similar to Eq (6), we can write
where the constant term arises instead of as it might not be the same for all frequencies. However, the slope of the curve is still given by
from which the range can be found as
This is why it is known as the Phase Slope method. It is relatively costly to implement due to a number of back and forth transmissions (equal to the number of CWs employed) but it is very accurate because indoor channels are frequently susceptible to interference. A wider range of frequencies ensures resilience against interference through the added redundancy.