Ranging and Positioning with UWB

Abstract

Indoor location is one of the key use cases enabled by UWB for navigation and asset tracking. The 802.15.4a and 802.15.4z standards describe several techniques for determining the distance between a mobile device client and a set of static anchors. Two of them (SS-TWR and DS-TWR) use a bidirectional exchange between the client and the anchor, with the resulting distance being calculated on the initiating side (SS-TWR) or both sides (DS-TWR). OWR does not require an exchange and simply relies on the comparison of arrival times of signals (TDoA). With UL-TDoA, the time of arrival of the client signal is compared on several anchors, drawing distance hyperbolae from which the client location is deduced. With DL-TDoA, the reverse happens: the client compares the time of arrival of signals from several anchors and deduces its position. A third family of techniques is not described in the Standard but is commonly implemented in the field: AoA, where a comparison of the phase of the signal among two or more antennas is used to compute the direction of the sender. From these elements, a location engine computes the mobile device’s position. This chapter examines these techniques in detail.

1. Introduction

It is often said that outdoor localization is on its way to being solved, thanks to the progress of the fusion of GPS, dead reckoning, and cellular techniques. Indoor, however, the challenge remains. Although they vary widely, all indoor localization uses cases revolve around the idea of determining the position of a known object about known landmarks, like room numbers or other locally significant markers. Sensing techniques allow for the detection of a moving body, but the accuracy of such determination is limited. Precision can greatly increase if the object incorporates a radio frequency (RF) technology, that allows it to interact with other RF objects whose location is known. These conditions bring the problem closer to its outdoor counterpart, and many technologies attempt to solve it.

Among them, Ultra-Wide Band (UWB) technologies have emerged as solutions of choice. “Ultra-wide” is a term characterizing any radio transmission occurring over a large channel (> 500 MHz). In most cases, these technologies face the risk of interfering with other transmitters and are allowed to transmit this type of large signal in exchange for the signal to be very low power (thus limiting the interferences they cause to others).

There have been many proposals for UWB communications, in many forums. However, one of them, first defined in the IEEE 802.15.4a Standard in 2007 [1], then refined in the IEEE 802.15.4z Standard in 2020 [2], has emerged as a key player for indoor localization, because of its claim of high accuracy. Experiments in controlled environments report localization accuracy down to 3 cm (1 inch), and commercial deployments now claim less than 30 cm (1 foot) error. This precision is made possible by the characteristics of the UWB transmission, as defined in the IEEE 802.15.4 family of standards, and augmented by industry-wide certifications like FiRa. This chapter examines the principles and components that guide UWB-ranging and make it the de facto solution for indoor ultra-precise localization.

2. Ranging with UWB

2.1 UWB ranging claim to accuracy

UWB may appear as just one of many radio frequency-based (RF) technologies interested in the localization use case. However, its design makes it particularly well-adapted for accurate ranging. Most radio technologies have attempted, in one way or another, to measure the distance between a sender and a receiver but have found the endeavor to be challenging.

A simple approach is to translate the received signal strength value into a distance estimation, using standard free path loss equations. One obvious limitation of such a technique is that obstacles may cause the received signal to be weaker than it would be, traveling in an unobstructed path. Reflections and multipath in general may also cause the received signal to be stronger (constructive interferences) or weaker (destructive interferences) than it would be in an open space. For these reasons, signal strength-based techniques for distance estimation are used, but not preferred, as they have the reputation of being flawed with large inaccuracy.

Other techniques measure the angle of the received signal on multiple receivers (or the angle from multiple transmitters, which positions are known). By using these combined angles, the transmitter or the receiver location can be deduced with standard geometrical tools. UWB allows for this technique as we will see later in this chapter, and its accuracy compares to that of other technologies. One requirement of this approach is the cooperation between several senders or several receivers to construct a geometrical object before the location can be found (while the signal strength-based techniques directly translate the signal at a single receiver into a distance).

A third family of techniques attempts to measure the time-of-flight (ToF), that is the time taken by a signal to travel between the transmitter and the receiver. This approach has received the favor of many radio technology families, including IEEE 802.11 Fine Timing Measurement (FTM), Bluetooth Low Energy (BLE) High-Accuracy-Distance-Measurement (HADM), and UWB, because it can lead to very accurate results. However, it requires the protocol designers and implementers to solve several technical difficulties. In addition to the challenge of agreeing on a common time reference between the transmitter and the receiver, which we will examine further in the next section, ToF requires that the receiver should be able to precisely determine the time of arrival of the signal. For UWB, just like for most other techniques, this time is the precise time of arrival of the beginning of the signal, often referred to as the first pulse of the first symbol of the header of a PPDU (Physical Protocol Data Unit). The PPDU includes the physical layer of the transmitted frame, which typically starts with a form of the preamble (called the SYNC field in 802.15.4), a simple rhythmic structure that precedes the body of the frame, where the real data will be found. The preamble serves three core purposes:

• In an environment where some form of RF noise is always expected, the preamble allows the receiver to recognize that the amount of energy reaching the antenna is strong enough that it is likely that some form of intentional transmission is occurring (and thus the receiver should attempt to measure that energy to recognize the transmission)

• Even if the receiver has missed the very beginning, the known structure of the preamble soon allows the receiver to catch up, recognizing the preamble for what it is, and deducing the part it missed from the parts it recognizes

• The preamble indicates how the rest of the frame should be interpreted (how it is encoded or modulated).

Determining the exact time of the arrival of the first part of the preamble is more challenging than it would seem to the untrained eye. The receiver needs to measure the energy over a range of interesting frequencies (the channel to which the receiver is set) at regular intervals. To measure the rise and fall of energy of a signal that follows the structure of a sinusoid wave, the sampling typically needs to occur (at least) twice as fast as the channel bandwidth. For example, if the channel is 1 Hertz wide (one peak and one trough per second), measuring the energy twice per second is sufficient. Similarly, if the channel is 80 MHz wide (e.g., with IEEE 802.11 ac), sampling the channel 160 million times per second is needed. This second case represents taking a sample once every 6.25 nanoseconds (ns). Practically, this method means that the receiver takes a sample at a time t₀ and measures no notable energy beyond the noise floor. Then at time t₁, 6.25 ns later, another sample is taken, and this time significant energy is detected (and thus a preamble is likely arriving at the antenna). However, the preamble may have started arriving at any time between t₀ and t₁. Light and any other RF energies travel at approximately 299,792,458 m per second in the air and therefore travel a bit more than 1.80 m (or 6 ft) in a 6.25 ns interval. This sampling method makes it would be difficult to measure a distance with a precision greater than 1.80 m over our example 80 MHz-wide channel. Technologies leveraging channels mechanically obtain better-ranging accuracy with the ToF technique, because they sample more often, reducing the time of arrival uncertainty. UWB commonly uses ultra-wide channels, 500 MHz or wider, and thus benefits from a clear advantage in this domain.

Technologies that focus on high data rates need to implement a rich modulation structure, where many symbols are sent in parallel over the width of the channel. The advantage is data transmission speed, but the downside is another challenge for efficient ToF. To receive the data part of the signal properly, the receiver needs to measure the energy of each segment of interest (where each symbol may be found) over the entire channel width. However, segments with a strong energy peak may overwhelm neighboring segments with low energy. One important requirement for these types of technology is therefore to mandate a low Peak to Average Power Ratio (PAPR), to ensure that no segment blinds its neighbors by being much over or below the average energy of all segments taken together. This necessity makes that many of these complex modulations allow for sidelobes of energy on each segment, that smoothen the average energy value of the segment. Unfortunately, a side effect of this structure is that the sidelobe may reach the receiver before the useful part of the segment. This event is inconsequential for proper reception of the data associated with the segment (the receiver can recognize the peak and demodulate its associated symbol), but it may lure the receiver into believing that the signal started being received before it was, causing the system to conclude on unrealistically short distances. ToF is challenging for these modulation-rich technologies.

UWB was designed to avoid both the sidelobe and the bandwidth issues. In the time domain, the UWB signal is composed of very short pulses (2 ns each). The sequence of pulses encodes the message to transmit. The interval between each pulse (usually represented by the term pulse repetition frequency [PRF]) determines how much data can be sent by the unit of time (Figure 1). Because each pulse is very short, it can easily be recognized (no issue of sidelobe confusing the receiver). Because the receiver recognizes the pattern of the preamble, it can recompose the first pulse (and its exact arrival time) even if the receiver did not sample perfectly at the right point in time. This structure gives UWB the claim of a range accuracy of the order of 2 inches, or 6 cm [3]. We will see below that there are still some technical issues to solve to get to that level.

Figure 1.

UWB pulse structure.

Another advantage of the UWB transmission structure is that the pulse is sent, in the frequency domain, over the large 500-MHz channel. The amount of energy transmitted is large enough that the receiver can recognize each pulse. However, the amount of energy per unit of bandwidth is very small (e.g., in the domains regulated under the American Federal Communications Commission [FCC], −41.3 dBm per MHz maximum; by contrast, some channels for 802.11 transmissions allow 11 dBm/MHz, i.e., a signal one hundred thousand times more powerful per MHz of bandwidth than UWB). This spread of the energy transmitted makes those narrower systems (for example, an 802.11 device listening to “only” 80 MHz of the 500 MHz-wide transmissions) will barely detect the UWB signal in the general noise. However, the UWB receiver, capturing the full 500 MHz, will read each pulse with ease.

2.2 Single-sided two-way ranging

2.2.1 Ranging terminology

The UWB system of short pulses allows for good-ranging precision. The UWB ranging frame itself is not very special. What distinguishes it from any other UWB frame is that one bit of the Physical (PHY) Layer (the ranging bit) is set. The rest of the header, and the rest of the frame, can be of any of the formats allowed by the 802.15.4a or 802.15.4z Standards. If the frame is solely intended for ranging purposes, it is in most cases as short as possible (to limit the amount of airtime consumed by each ranging frame). In its simplest expression, when the frame is built for ranging between 2 devices, it only contains the header (no payload, no source or destination addresses). In more complex environments (multiple possible senders and receivers), additional fields are added as needed.

The simplest ranging process then consists of an exchange of two frames between 2 ranging-capable devices (RDEVs when implementing 802.15.4a, or enhanced ranging capable-devices - ERDEVs, when implementing improved modes defined in 802.15.4z and described below). The two-frame exchange is simply called Two-Way Ranging (TWR) in 802.15.4a and was renamed Single-Sided Two-Way Ranging (SS-TWR) in 802.15.4z (SS is added in that revision of the Standard to avoid any confusion with another mode, DS-TWR, described in the next session).

One of the devices is called the initiator (in 802.15.4.z, or the originator in 802.15.4a, but the functions are the same in both Standards for the basic TWR case), and the other is the responder.

2.2.2 Basic SS-TWR mode

At time t₀, the initiator (A in Figure 2) sends a ranging frame and starts its ranging counter.

Figure 2.

SS-TWR choreography.

The frame travels to the responder (B in Figure 2), consuming a time-of-flight t_p that is proportional to the distance between both devices.

Upon receiving the first pulse of the preamble, at time t₁, the responder starts its ranging counter. The responder then receives the rest of the frame, interprets it, and realizes that it is a ranging frame and that it should respond. It then builds a ranging response frame and sends it to the initiator, at time t₂. The responder indicates in the frame a payload value called $t_{\mathit{\text{replyB}}}$, which indicates the time between the reception of the first pulse at the responder antenna (time t₁, at which the responder ranging counter was started) to the time at which the first pulse of the responder’s ranging frame is set to leave the responder’s antenna (t₂). The responder stops its ranging counter upon sending the response frame.

The frame travels to the initiator, consuming the same time of flight t_p as the first ranging frame (in UWB, one assumption is that devices do not move fast enough from each other for their distance to have significantly changed during the exchange).

The initiator receives the first pulse of the preamble, notes the time from its ranging counter (t₃), then receives the rest of the frame.

At this point (Figure 2), the initiator has the time it took to perform the entire round of exchange ($t_{\mathit{\text{roundA}}}=t_3-t_0$), and the time consumed by the responder’s activity ($t_{\mathit{\text{replyB}}}$). As frames traveled both ways, the ToF between devices is simply estimated as:

$$\widehat{\mathit{ToF}}=\frac{1}{2}\left(t_{\mathit{\text{roundA}}}-t_{\mathit{\text{replyB}}}\right).$$E1

Eq. (1) supposes that both devices’ crystals count time at the same speed, as the initiator subtracts $t_{\mathit{\text{replyB}}}$ from $t_{\mathit{\text{roundA}}}$. But $t_{\mathit{\text{roundA}}}$ is measured by A, while $t_{\mathit{\text{replyB}}}$ is measured by B. In most cases, crystals are imperfect and there is a time offset, or drift, between devices. There are multiple proprietary and many common methods to reconcile these differences. For example, one may notice that the PHY header indicates the PRF, and that the duration of each pulse is also known. Therefore, the responder could simply measure each pulse duration and the PRF in the frame received from the initiator, find that they do not perfectly align with its interpretation of the pulse duration and the PRF, and deduce the time offset between its clock and the clock of the initiator.

2.2.3 802.15.4z reply time improvements

802.15.4z allows B to make good use of finding the time offset difference, regardless of how B made that determination. When both A and B support these refinements, they are called ERDEVs.

In an efficient embodiment (SS-TWR with fixed reply time), A sends a ranging frame as in the SS-TWR mode, but A and B agreed in advance (through out-of-band or previous UWB messages) to a specific $t_{\mathit{\text{replyB}}}$ value. B receives A’s ranging frame and waits for $t_{\mathit{\text{replyB}}}$, then replies. In a sound implementation, B uses the pulse duration and PRF estimation as detailed above to estimate A’s clock speed and adjust its $t_{\mathit{\text{replyB}}}$ value based on that understanding, therefore attempting to determine $t_{\mathit{\text{replyB}}}$ the way A would have calculated it (i.e., “in A’s time”). This common understanding limits the effect of the drift.

In another form (SS-TWR with embedded time result, Figure 3, left), A, in its ranging request frame, inserts a Ranging Request Measurement and Control Information Element (RRMC IE), that sets a Reply Time Request bit. B then understands that it must compute the drift directly. Then, in its response frame, B adds a Ranging Reply Time Instantaneous Information Element (RRTI IE), that expresses the calculated time offset. A can then choose to incorporate this drift in its calculation. In the real world, it is unlikely that B would be able to make such drift determination on the fly, but it could compute the offset with better accuracy at each new round. Then, the distance accuracy increases as more rounds are performed between the devices.

Figure 3.

802.15.4z SS-TWR with embedded time result (left) and 802.15.4z SS-TWR with deferred time result (right).

In the third and last form (SS-TWR with deferred reply time result, Figure 3, right), B would want to provide the offset value in near real-time but does not have the computing capability to calculate its value on the fly. Therefore, upon receiving the ranging request from A, with the Reply Time Request bit set in the RRMC IE, B responds with an acknowledgment frame that allows A to compute $t_{\mathit{\text{roundA}}}$. Then, in a subsequent frame, B sends a Ranging Measurement Information (RMI) Information Element, that includes both $t_{\mathit{\text{replyB}}}$ and the estimated offset. The offset between A and B, $C_{\mathit{\text{offs}}}$, is then incorporated into Eq. (1), which becomes:

$$\widehat{\mathit{ToF}}=\frac{1}{2}\left(t_{\mathit{\text{roundA}}}-t_{\mathit{\text{replyB}}}-\left(1-C_{\mathit{\text{offs}}}\right)\right).$$E2

These improvements allow the ranging exchange to complete with a time error well below 1 ns (often in the 100-picosecond range), allowing a ranging accuracy in the order of 3 cm.

2.3 Double-sided two-way ranging

One limitation of SS-TWR is that responder B does not benefit from the exchange. Its role is merely to respond to A. In the days of 802.15.4a, there was also a concern that clock drifts could not be properly accounted for. The 802.15.4a Standard then devised an additional mode, called Symmetric Double-Sided Two-Way Ranging (SDS-TWR). In this mode, A starts with a ranging frame, as in the SS-TWR basic mode, and B responds with its ranging frame that includes $t_{\mathit{\text{replyB}}}$, but keeps its ranging counter running. Upon receiving the response, A, instead of directly computing the ToF, responds with its ranging frame and processing time ($t_{\mathit{\text{replyA}}}$). B receives that response measures its arrival time and stops the ranging counter. B also measures its own $t_{\mathit{\text{round}}\mathit{B}}$, which starts when B sends its ranging response frame and stops when it receives A’s response. The ToF value is now present 4 times (Figure 4): twice in $t_{\mathit{\text{roundA}}}$, measuring the interval from the departure of the first frame from A, and the arrival of the response from B, and twice in $t_{\mathit{\text{roundB}}}$, measuring the interval from the departure of the response frame from B, and the arrival of the response from A.

Figure 4.

802.15.4a SDS-TWR.

In this configuration, A can still compute its interpretation of the ToF using Eq. (1). B can also compute its interpretation of the ToF, with the additional advantage, that the error is now reduced as B can compare $t_{\mathit{\text{replyA}}}$ to its measurements, and therefore estimate the relative drifts. The estimation remains precisely that, an estimation. However, the process reduces the error. Even with a crystal accurate at 80 ppm, the error in the ToF estimated by B commonly drops well below 10 picoseconds.

802.15.4z added an enhancement to this mode (Figure 5), called Double-Sided Two-Way Ranging (DS-TWR, thus without the “symmetric” word in the 802.15.4.a version). In this variation, well adapted to scenarios where the conditions of the channel or other parameters cause $t_{\mathit{\text{reply}}}$ to be large on either or both sides (with the consequence that the drift is more difficult to evaluate), A first sends a ranging request, including the RRMC IE and its support for the DS-TWR exchange. B responds with an Acknowledgement frame, allowing A to measure $t_{\mathit{\text{roundA}}}$. But then, after the round, B initiates its TWR exchange, indicating in the RRMC IE that this is a continuation of the previous exchange. A response with an Acknowledgement frame, allowing B to measure $t_{\mathit{\text{roundB}}}$. Then, in a subsequent frame, A sends another frame to B, that includes the RMI IE and the value for $t_{\mathit{\text{roundA}}}$ and $t_{\mathit{\text{replyA}}}$. From all these elements, B can minimize the effects of the drifts and compute the ToF. B can then, in turn, sends a frame to A with the RMI IE that contains $t_{\mathit{\text{roundB}}}$ and $t_{\mathit{\text{replyB}}}$. A can then also compute its estimation of the ToF. In both cases, the estimation becomes:

Figure 5.

802.15.4z DS-TWR with deferred reply time result (left), DS-TWR with embedded ranging information (right).

$$\widehat{\mathit{ToF}}=\frac{\left(t_{\mathit{\text{roundA}}}{t}_{\mathit{\text{roundB}}}\right)-\left(t_{\mathit{\text{replyA}}}{t}_{\mathit{\text{replyB}}}\right)}{t_{\mathit{\text{roundA}}}+t_{\mathit{\text{replyA}}}+t_{\mathit{\text{roundB}}}+t_{\mathit{\text{replyB}}}}$$E3

Here again, the error is reduced to less than 10 picoseconds in most cases, and both sides compute the ToF estimate. The main downside of this method is that it requires up to 6 frames to complete. A reduced version of this method is also allowed by 802.15.4z and is called DS-TWR with embedded ranging information. In this variation, B does not respond to A’s ranging request frame with an Acknowledgement frame, but directly with a ranging request frame, that includes the RRMC IE to show that the response is a continuation of the exchange. A then responds with a ranging frame that includes the RMI IE and the value of $t_{\mathit{\text{roundA}}}$, but also an RRTI IE that includes the value of $t_{\mathit{\text{replyA}}}$. B can then directly compute its estimation of the ToF. If A also wants to perform this computation, it can set, in the RRMC IE, a field called ToF Request. This causes B, at the end of its ToF estimation, to share the calculated value in a new frame with A (carrying the ToF estimate in the RMI IE).

2.4 Time difference of arrival

All the techniques associated with TWR variants suppose a form of initial configuration between devices, so they know their respective role and place in the sequence of messages. This requirement raises the natural question of the final goal of such a ranging exercise. In many cases, the purpose of the measurement is not to find the relative distance between two objects, but to determine the location of one of them. The use case may then be navigation (a mobile device needs to establish its location, and commonly display it on the local screen over a local map), or asset tracking (a backend management platform needs to record and/or display the location of assets, for example, parts on a factory floor). If the purpose is solely navigation or solely asset tracking, then it becomes practical to deploy a set of devices (now called anchors) at static, known positions, and configure them permanently for navigation or tracking purposes. In this case, the ranging messaging structure can be transformed so that only one side (the mobile device or the static anchors) sends the ranging messages.

This possibility is lightly described in 802.15.4a, and more formally specified in 802.15.4z (under the umbrella name One-Way Ranging [OWR]).

2.4.1 TDoA for navigation

For navigation purposes, the mobile device needs to establish its distance to each known anchor and deduce its location by comparing these distances. In 802.15.4a, the anchors would be statically configured for this purpose. Then, at regular intervals, they would send a message with the Ranging bit set, the Acknowledgement bit not set [so the mobile device knows not to answer], and the identifier of the sending anchor (Figure 6). All anchors would send the ranging message at the same time. Because the anchors would be at different distances, the mobile device would receive the messages at different times and would use the time difference of arrival (TDoA) to deduce its location. We will look at this last step in the next section.

Figure 6.

802.15.4a TDoA Mode 1.

Practically, however, this technique (called TDoA mode 1) made several assumptions that were not always realized:

• The distance between anchors and the mobile device would be different enough that their message would not collide. In the real world, one anchor may be a few meters closer or farther than the other, and the message from one anchor may still be in the process of being received while the message from the other starts arriving at the mobile antenna, causing collisions (resulting in no distance to either anchor).

• Sending the messages at the same time supposes a highly accurate synchronization technique between anchors. 802.15.4a recognized this need but did not propose a mechanism for such synchronization.

802.15.4z describes a variation of this method. In this version, the anchors send their message one after the other, with a precise (and known) offset between transmissions (Figure 7). This difference avoids message collisions.

Figure 7.

802.15.4z downlink TDoA.

The anchor’s clocks still need to be carefully synchronized, and the standard suggests an over-the-wire or over-the-air method, without further details. There are certainly many possible proprietary methods for such exchanges. A practice long established in the industry consists in designating one primary anchor that sends intervals (e.g., every 100 ms) a broadcast message (called a ‘sync’ message) that includes its time. The others (called the secondary anchors) receive this message and, knowing their distance to the primary anchor (and anchors are static in position and configured by a network administrator), re-align their clock to the primary’s time. After a few of these exchanges, the secondary anchors can learn their mean drift over the sync message intervals and re-align their clocks also between sync messages. In stable conditions (e.g., no brutal change of temperature or other operating conditions), the system can reach an accuracy in the 20 to 50 picosecond range. The sync message may also include an ordered list of anchors and an interval. Using that information, the receiving anchors would know which anchor is supposed to send the ranging message first, and how long each next anchor needs to wait before sending its ranging frame. In the real world, as the list of anchors is static, and as one anchor may disappear for any reason, it is common for the network administrator to simply configure each anchor with a time offset (“send your ranging frame X$\mathit{\mu s}$ after detecting anchor i’s ranging frame, and/or Y$\mathit{\mu s}$ after detecting anchor j’s ranging frame”). Such a static configuration avoids consuming airtime to repeat a sequence that is unlikely to change. It also avoids the chain rupture effect of the next anchor never sending a ranging frame, because it is waiting for the previous anchor to send, while that previous anchor was disconnected for some reason.

2.4.2 TDoA for asset tracking

Both 802.15.4a and 802.15.4.z, describe the asset tracking case with similar methods (802.15.4.a calls this case TDoA method 2, 802.15.4.z simply describes it as a second case of TDoA utilization). In this scenario, the mobile device (called the initiator) sends ranging messages (called ‘blinks’) at regular intervals (Figure 8). The header has the Ranging bit set and the Acknowledgement bit not set (no response needed), and the frame can be limited to carrying a form of identifier for the initiator (a MAC address or a simpler identifier), along with a message number. Each anchor individually receives the message, notes the time of arrival, then forwards the message number, initiator identifier, and time of arrival to an external system (usually a Real-Time Location Service [RTLS] server). The server collects such messages from all detecting anchors and uses the time difference of arrival to compute the initiator location.

Figure 8.

802.15.4a TDoA Mode 2, 802.15.4z uplink TDoA.

802.15.4a does not assume the anchors’ clocks, but 802.15.4.z recognizes that they must still be synchronized. This is because they need to mention the time of arrival of each blink. If the clocks are not set to the same time reference, these times of arrival cannot be compared. Thus, the asset tracking case still often leverages sync messages sent from a primary anchor to the secondary anchors. A conceptual difficulty associated with this requirement is that the sync messages serve no direct location purpose. They are just part of the necessary mechanic to keep the clocks aligned. Yet they consume airtime, which is not available for the blink messages. Therefore, more frequent sync messages increase the accuracy of the TDoA measurement, but also reduce the possible density of blink messages (thus the number of devices tracked in each space, or the frequency of their blink updates). In most scenarios, an arbitration is made to limit the sync messages to match the inaccuracy tolerance of the location calculation derived from the clock drifts.

2.4.3 TDoA hybrid modes

The binary opposition between asset tracking (the mobile device is the one sending frames used for ranging, the anchors send messages to synchronize their clocks, but are otherwise passively receiving the ranging frames) and navigation (the anchors are the ones sending frames used for ranging, the mobile device is potentially entirely passive and thus invisible to the infrastructure) makes sense in a specialized scenario. However, the real world is often more complex. A department store, for example, may want to offer ultra-accurate navigation services for its customers, but also track goods and staff in the store. A smartphone might be in the hands of either side (customer or staff). Additionally, the store may want to ensure customer anonymity or may request permission to identify the users using the navigation service. This is where the Standards (802.15.4a and 802.15.4z) stop and where other organizations, like FiRa, define common use cases and specifications among vendors so that the anchors and the mobile device can recognize their operating scenario in the field.

In most cases, the specifications can recognize that UWB is one component of a more complex system, that includes an operating system and possibly other radio technologies (e.g., Wi-Fi or BLE). There is therefore a possibility of signaling (possibly out-of-band, e.g., with BLE or Wi-Fi) between the infrastructure (where the anchors reside) and the mobile device to indicate the scenario:

In the case of anonymous navigation, the infrastructure merely needs to signal the operating parameters (channel and others).

In the case of asset tracking, the infrastructure may provide a form of identifier (this is store X), preferably verifiable by the mobile device (e.g., a hash), and the tracking parameters (interval between frames and others). The mobile device operating system can then parse the message, compare the request to its configuration, and start emitting ranging frames if it is an asset of the store (while a customer mobile device would simply ignore the request).

In a hybrid case, the infrastructure may want to track the device while offering navigation services. Tracking may be a generic analytic need, to observe general movements in the store, without identifying any specific device, or be more specific by tracking individual devices (for example because some customers with a store-specific app may request coupons when in proximity to some type of merchandise). Here again, the infrastructure can signal one or both scenarios. Some mobile devices may then be configured to ignore the request. Others may be configured to only provide anonymous ranging. In that case, the device may (passively) perform navigation, and at random intervals send short series of ranging frames with a temporary (randomized) identifier. As the series is short, sporadic and the identifier randomized, the infrastructure would not obtain more than small snippets of directions, which would not be very useable individually, but would be sufficient, at scale, to provide an understanding of the general movements of people through the store. Other devices may have a specific store app and be configured by the user to provide an accurate location.

There may also be some cases where device tracking becomes mandatory, for example in hazardous areas. Here again, the infrastructure can signal such zones, requesting all devices in the zone to signal their presence. Mobile devices may then be configured to either respond to such requests or ignore them.

2.5 Angle of arrival (AoA)

802.15.4a, published in 2007, did not consider angles. However, several proprietary implementations leveraged the angle of arrival of the signal to deduce its likely direction [2, 3]. This determination has several advantages:

Triangulation or multiangulation (leveraging three, or multiple angles) can complement trilateration, or multilateration (leveraging three, or multiple distances). This point will be explained further in the next section.

When the distance to a single device is evaluated over multiple samples, the observation of the matching angles allows the system to calculate if the signal direction is stable. In an LoS ideal scenario, the source is sending a series of frames (and associated pulses), that all reach the receiver with the same intensity and from the same direction. In an indoor nLoS scenario, some frames may reach the receiver through an LoS path (and their power level and angle can be measured). Others will reflect on obstacles, the LoS signal may be too weak to be detected, and the frames may therefore reach the receiver with different power levels and angles. By comparing the angles of the pulses, from one frame to the next, it is possible to conclude if the channel is stable and LoS, or unstable and/or nLoS. Although leveraging this piece of information in real-time may be difficult, a properly designed system may relate the change of angle with the change in the calculated range value and deduce what is the most likely angle of arrival for the LoS component, if it can be found.

While UWB implementations started leveraging the angle of arrival (under the name Phase Difference of Arrival, PDoA) as soon as 802.15.4.a was published, other radio technologies also started at the same period to consider the angle of arrivals, either at the protocol-definition level (e.g., BLE) or in practical implementations (e.g., Wi-Fi).

This uncoordinated development led to an imprecise terminology that still confuses researchers today. In its most common implementation, UWB (along with BLE or Wi-Fi) considers the angle of a single signal received on two (or more) antennas of a single receiver. The frequency of the signal is known, and consequently its wavelength. For example, UWB channel 9 has its center frequency f set to 7987.2 MHz, and its wavelength (1/f, usually written $\lambda$) is therefore approximately 0.0375 m. By observing the point in the wave cycle (the phase) at which one antenna receives the signal and comparing it to the phase at which another antenna (whose distance to the first antenna is known) receives the same signal, it is then a matter of basic trigonometry to deduce the incident angle of that signal (Figure 9).

Figure 9.

The angle of arrival determination.

Several radio technologies call this angle the “signal angle of arrival”. Some UWB experts, however, call it “Phase difference of arrival” (pDoA), because it is obtained by comparing the phase between antennas. Unfortunately, several other technologies call pDoA the observation of a signal on a single antenna, comparing the phase of one primary component to the phase of one or more other components (e.g., subcarriers, reflections, etc.) [4]. Other technologies call pDoA the differences in phase of two different signals received on a single antenna [5]. This variability in terminology makes the term pDoA no longer preferred, and AoA may be a safer choice, when in doubt.

Because the consideration of the angle became, in the 2010 decade, an active contributor to many radio technologies seeking location accuracy, 802.15.4z integrates the values. The standard does not define how to measure the angle and merely observes that a system may be able to calculate its value. In all the two-way ranging techniques considered in 802.15.4z, the initiator can request, as an option in the ranging frame, to request for the AoA (azimuth and elevation) at which the frame was received by the responder. The responder indicates these elements (in radians, with a possible range of $\left[-\pi ,\pi \right]$ for the azimuth, and $\left[-\pi /2,\pi /2\right]$ for the elevation) in the RMI IE in the response.

2.6 Protection of UWB exchanges

The UWB frames are not encrypted, and an observer could read the timestamps they carry. When observing the full TWR exchange, the observer may be able to deduce the distance between two ranging UWB devices. The issue is not critical in many settings where the use case is the navigation or asset tracking. However, UWB is also used with TWR for accurate ranging, for example, to automatically open a door when a user is near or unlocking a car. In these cases, an attacker could replay or hijack one side’s ranging frames, lead the other side to conclude on a distance shorter than the real physical distance between the initiator and the responder, and thus open the door or unlock the car while the user’s device is still far.

802.15.4z designed two mitigation techniques for such an attack. The first form is a mutual authentication between the initiator and the responder, which leads to encrypted exchanges. This mechanism protects from eavesdropping and is well-adapted for scenarios where the initiator and responder know each other (e.g., a car and its key fob). However, an attacker can still hijack the exchanged frames at the PHY level and lure the receiver to conclude on a short ToF. A second mechanism was designed to mitigate this risk, in the form of a Scrambled Timestamp Sequence (STS) field. The STS can be inserted in the physical header of the ranging frames and consists of pseudo-randomized pulses organized in blocks (one to four blocks of 512 chips each [$\sim 1\mu ],$or 128 bits, separated by silences, or ‘gaps’). The STS relies on keys that are exchanged in advance between the initiator and the responder, and nonces (numbers used once), from which the transmitter generates a unique value used as the STS to timestamp the ranging frame. The receiver, having the same information, generates the same value, and accepts the ranging frame only if its STS matches the receiver’s generated value. Because of the large number of pulse sequences that can be generated for the STS field, the probability that an attacker could generate the right sequence and thus lure the receiver to conclude that the relayed frame did originate from the expected sender, at the expected distance, is minuscule.

Although the STS scheme is not expected to be impossible to attack, it has proven to be robust [6].

3. Finding a location with UWB

Once an estimation of the distance (and possibly angle) between a mobile device and several anchors has been found, the next step is to compare the values and deduce the location of the object. The terminology in this field tends to distinguish the position, which is the conclusion of the comparison of distances (or angles) to known points, from the location, which is the position projected on a known set of references. Thus, for example, one would say that the position of a particular object is at the intersection of three circles of radii 5.7, 8.1, and 7.4 meters from anchors A, B, and C respectively. Then, once the position of the object and the anchors have been projected onto a map, one could declare that the location of the object is on the second floor of the hotel, in the upper left corner of room 242.

Finding the location of the mobile object thus supposes that the location of the anchors is known. For the asset tracking use case, the RTLS server can be configured with such information. In the navigation case, the 802.15.4 Standard does not describe how the mobile object should learn the anchors’ location. Conceptually, such information may be embedded in the UWB frame payload. However, the anchors and the mobile device would need to agree on the location format. Industry certifications like the one driven by FiRa define a common format and suggest that the location information should be expressed out-of-band (for example using Bluetooth Low Energy [BLE]).

Regardless of the use case, the first step toward determining location is to compute a position.

3.1 Establishing a position from ranges

3.1.1 Localization in the TWR case

In the TWR cases, ranges are evaluated between a mobile device and a set of anchors. Without angle information, determining that the mobile is x meters away from an anchor places the mobile on a circle of radius x, centered on that anchor. On a plane (i.e., supposing an ideal 2D environment), 2 circles intersect on two points (when they intersect), and 3 anchors are needed to hope for a unique solution (if all three circles intersect). The action of finding the position from three distances is called trilateration. In 3 dimensions, the circles become spheres, and 3 spheres intersect on two points, thus causing position uncertainty. If all anchors are on the same plane, then intersection points are typically above each other. When the position then needs to be projected onto a 2D map, this uncertainty may be acceptable. When 3D representations are needed, and no assumption can be made about the object height, 4 anchors or more are needed to hope to obtain a single intersection point (multilateration).

In an ideal world, the intersection can be simply calculated by solving a set of equations representing the distance of the object to each anchor. If m is a mobile object of unknown coordinates $m=\left(x_m,y_m,z_m\right)$, and $a_i$ is an anchor of known coordinates $a_i=\left(x_i,y_i,z_i\right)$, the distance between the mobile and the anchor is expressed by the straightforward Euclidean distance equation:

$$d_i^2={\left(x_i-x_m\right)}^2+{\left(y_i-y_m\right)}^2+{\left(z_i-z_m\right)}^2$$E4

Eq. (4) can be re-written in an alternate form:

$$\left(x_m^2+y_m^2+z_m^2\right)-2\left(x_i{x}_m+y_i{y}_m+z_i{z}_m\right)=d_i^2-\left(x_i^2+y_i^2+z_i^2\right)$$E5

As more anchors (j, k, etc.) are added, it becomes possible to obtain linear equations in x_m, y_m and z_m by subtracting equations pairwise. When 4 such equations are available, the system is overdetermined and a single solution can be found, however, even if UWB allows for high-ranking precision, each measurement is not mathematically perfectly accurate (the experimenter observes an estimation of the range, ${\widehat{d}}_i$, that differs from the true range by an unknown factor ${ϵ}_i$ so that ${\widehat{d}}_i=d_i+{ϵ}_i$) and in the real world, a perfect solution cannot be found.

3.1.2 Localization in the TDoA case

The same type of issue can be observed in the TDoA case. With OWR, the detecting side never measures distances directly. Instead, the observation is mere that a given mobile signal arrives on an anchor n us earlier than on another anchor (or equivalently that the mobile received the signal from one anchor n us earlier than the signal from another anchor). As the speed of light and RF signals are known, this observation is translated into the conclusion that one anchor is x cm closer than the other one, but the distance itself is not known. This relationship translates into a hyperbolic line between anchors (Figure 10). TDoA measurements between two anchors form one hyperbola.

Figure 10.

Hyperbolae formed from OWR measurements.

Conceptually, three anchors result in 3 hyperbolae. However, in the real world, the TDoAs are compared against a primary anchor (e.g., anchor 1) and the hyperbola that compares anchor 2 to anchor 3 is unusable. Therefore, three anchors result in 2 usable hyperbolae, which intersect at a single point on a 2D plane. For 3D determination, at least 4 anchors are therefore needed. The comparison is then translated into a matrix of compared distances, from which the true Euclidean distance can be found iteratively [4]. Here again, distances in the real world are noisy, and no perfect solution can be found. TDoA also suffers from the additional difficulty that, contrary to circles, hyperbolae are asymptotic to a line. Practically, this fact translates into the issue that, as the observed compared distance deviates from the ground truth, it worsens faster (up to infinity) than its TWR counterpart.

3.2 Least square solutions

To solve the issue of reconciling noisy distances, a natural approach is to attempt to determine the measurement errors and minimize them. Mathematically, with N anchors, this requirement is expressed as

$$\underset{m}{min}\sum _{i=1}^N{\left(\left|\left|m-a_i\right|\right|-{\widehat{d}}_i\right)}^2$$E6

Naturally, the experimenter does not know m but can find the coordinates iteratively, with techniques like gradient descent where the derivative of Eq. (6) for each component of $m\left(x_m,y_m,z_m\right)$ is calculated, then an iterative process tests the values of each component until the m that minimizes that derivative is found.

This least square (LS) method has been well established for noisy distance resolution when the errors to all anchors are comparable. In some environments, however, some anchors are in direct LoS to the measuring mobile device, while some others are behind obstacles. In this type of scenario, fusion techniques appear, where LS is complemented with steps that either estimate the nLoS deviation [7] to allow anchor-to-anchor comparison or use fingerprinting techniques [8] to place the mobile at the position of best likelihood.

3.3 Bayesian framework solutions

One key aspect of the LS approaches is that they examine each measurement set individually. However, it may be tempting to reason that a mobile device is by nature moving, and that the position at time t_n+1 may be related to the position at time t_n. Therefore, localization determination often borrows from Bayesian filtering techniques, where the state of a dynamic system is evaluated from noisy measurements and compared to the conclusion of previous measurements. There are naturally many techniques falling into that family, and this chapter only underlines the most used.

3.3.1 Kalman filter

Among the techniques leveraging the Bayesian framework, the most common is the Kalman filter (KF). The technique has been used successfully since the 1960s for trajectory and position estimation. In essence, the standard KF approach compares the estimation at time t_n with the prediction built from past observations and predictions [9]. When the new observation is noisy, the algorithm trusts more (affects a higher weight to) the prediction. When the new observation noise is small, the algorithm affects a higher weight to that observation than to the prediction.

One key requirement of the KF is that the underlying equations must be linear. The noise statistic also must have a Gaussian distribution. For location estimation, the distance equations are commonly not linear, and researchers have proposed several extensions to the KF for these cases. The most common variants are the unscented Kalman filter (UKF) and the extended Kalman filter (EKF). Both models solve the non-linearity by approximating the nonlinearity with Taylor expansions, then estimating their derivatives (which then become linear equations), EKF with the first derivative, and UKF with the second derivative. EKF is commonly used when the noise figure is small (variance differences are not large, mostly in LoS environments). UKF appears often in scenarios where the noise is high (environments dominated by nLoS scenarios).

The KF family has received the favor of implementers of indoor localization algorithms because, despite its complexity, the KF relies on matrix operations that most operating systems integrate natively. Thus, the computation can be done efficiently on most systems, in near real-time, and KF techniques are widely successful for UWB-based localization [10, 11, 12]. However, you should be aware of several limitations:

The KF methods require an initial position estimation, which in most cases is not available (and thus a random or arbitrary value is fed into the system). The algorithm then converges as more observations are made. The pace of these observations has a direct influence on the convergence speed. In other words, if your UWB method observes one position per second, the convergence to an accurate-enough position will be much slower than if your system generates 50 measurements per second. A common implementation practice is therefore to ignore the first n estimations to give time for the system to converge.

The KF methods are sensitive to sudden changes. By their very nature, they affect a low weight for measurements that are very far from the estimated positions. But these positions are based on past observations. A direct consequence is that the trajectory is linear, and the mobile device suddenly changes direction (for example, the user turns a corner in a corridor), the KF methods tend to overshoot, estimating that the new observation is likely inaccurate. On a map, you would then see the device trajectory continuing for a little while (possibly through a wall) before slowly turning and catching up to the user’s real position. Here again, the pace of the sampling dictates the duration and span of this negative effect.

3.3.2 Particle filters

Particle filter (PF) is the name given to a family of techniques that implement the Monte Carlo approach within the Bayesian framework [13]. It is well adapted for non-Gaussian, non-linear estimations, and thus often used for indoor ranging problems. This is because, in LoS conditions, the observations may display some noise value forming a Gaussian distribution around some value, but in nLoS conditions, walls and multipath tend to inflate the observed values, causing a long tail of distance overestimations that negates the Gaussian condition.

At its core, the PF incorporates two models. A motion model reads a set of values and deduces a possible state. In the case of indoor location, this first set may be obtained for example from odometry (readings from the device’s internal sensors) to estimate the device’s new position. In most cases, this technique alone is not sufficient to compute the path, because the sensors operate at a small scale and their accuracy suffers at a larger scale. For example, suppose a smartphone gyroscope estimates an 81-degree left turn, but the user turned 92 degrees left. After walking 10 more meters, the system sees the device 2 meter right of its real position. As the user moves, the gyroscope, accelerometer, and all the other sensors get multiple and frequent inputs, and their errors tend to build on one another, making that odometry can be quite accurate at a small scale (it is called a local technique), for small movements, but is not a great tool to compute trajectory at a large scale if the real position of the mobile is not rectified at intervals, using another source of truth (called a global technique), that may not be very accurate at small scale but may provide better visibility at these larger scales. Outdoor, that source can be GPS. Indoor, a ranging method is a great second source.

PF, therefore, includes, in addition to the motion model, a sensor model that measures the distance to some reference points, with the goal of re-positioning the mobile device from this second source. Naturally, the second source alone is not sufficient (otherwise there would be no need for the first model), as measurements are also noisy. So, PF operates by collecting a set of observations (in our case, distances to anchors), that are called particles, and establishing their probability density function (PDF) to determine which of the observations are most likely to be correct. PF is not very well-adapted to high-dimension problems, but works well for indoor localization, and is therefore widely used with UWB TWR [14, 15], either alone, or in combination (or in comparison) with KF [16, 17].

3.3.3 Machine learning methods

The methods examined so far rely on the laws of physics to find the best range estimation for each anchor and deduce the best position from the combination of ranges available. With multiple samples from multiple anchors, the number of parameters becomes large enough that statistical methods can be successfully substituted for physical methods. These complementary approaches help address two types of issues:

nLoS detection: LoS measurements are closer to the ground truth distance than nLoS measurements. Detecting nLoS conditions (and the stretch they induce to the measured distance) has been an active field of research, where unsupervised techniques can dramatically help group alike nLoS scenarios [18, 19] and reduce the effect of the stretch they induce.

Insufficient contributions: when there are not enough anchors to range against, or when they are all nLoS, supervised techniques allow the operator to sample measurements in different known locations, then deduce the location matching a new set of measurements by comparing it to the sample values. This technique is commonly called fingerprinting and is used on its own [20], or in combination with other techniques [21].

4. Conclusion

This chapter examined the evolution of UWB Standards for ranging. First defined in the IEEE 802.15.4a amendment in 2007, at a time when other groups also claimed ultra-wideband transmissions, UWB initially focused on the simple case of TWR, where one initiator would range against one responder. The integration into a larger localization solution implied a static configuration of roles and relied on implementers to fill the elements undefined in the Standard.

As UWB proved an efficient technology for accurate ranging, multiple proprietary implementations appeared that leveraged the basic tools defined in the protocol, but also added improvements and new modes to better fulfill the different location use cases. In 2020, IEEE 802.15.4z integrated many of these elements, to better address the challenges of TWR implementation, and account for the most popular augmentations, namely TDoA and AoA.

The Standard defines elements of the Physical and the Data Link layers and is silent on how UWB should be used in an end-to-end localization solution. It is therefore not sufficient for practical implementation. Organizations like FiRa integrate the IEEE protocol into a larger landscape, addressing the various use cases and the required communication structure above the two bottom layers.

This combination has made UWB very successful for localization with ultra-high accuracy. The techniques of converting a series of ranges, angles, or time of arrival differences into a position are not specific to UWB. However, the precision allowed by the structure of the UWB signal makes it a prime candidate to solve complex indoor navigation and asset localization problems, especially in the world of robotics and the Internet of Things (IoT).

The journey is far from over. IEEE 802.15.4z assumes that many elements required by the ranging exchange are sent out-of-band or consume in-band airtime that could be used to perform more or better ranging. There is therefore still a need to refine the technique and integrate it with the standard more tools to simplify the communication or perfect the accuracy of the range obtained. The IEEE 802.15ab task group has been formed to tackle this task, with the ambition to complete its work by the end of 2025.