# Estimation de distances distribuée FTM-BC par UWB sur systèmes embarqués

Stéphane d'Alu, Hervé Rivano, Olivier Simonin

► To cite this version:

Stéphane d'Alu, Hervé Rivano, Olivier Simonin. Estimation de distances distribuée FTM-BC par UWB sur systèmes embarqués. CORES 2025 - 10èmes Rencontres Francophones sur la Conception de Protocoles, l'Evaluation de Performances et l'Expérimentation des Réseaux de Communication, Jun 2025, Saint Valery-sur-Somme, France. pp.1-4. hal-05007991

HAL Id: hal-05007991

https://hal.science/hal-05007991v1

Submitted on 27 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Estimation de distances distribuée FTM-BC par UWB sur systèmes embarqués

Stéphane D'Alu¹ et Hervé Rivano¹ et Olivier Simonin¹

¹INSA Lyon, Inria, CITI, UR3720, 69621 Villeurbanne, France

La mesure de distance dérivée du temps de vol d'une transmission radio est traditionnellement réalisée en point à point entre chaque paire de noeuds par une technique de Two-Way Ranging (TWR). Dans [2], un algorithme distribué FTM-BC a été proposé afin d'exploiter la nature broadcast du medium radio, réduisant ainsi le nombre de paquets échangés nécessaires. Dans cet article nous regardons comment réaliser une implémentation efficace de ce protocole dans un environnement contraint sur un micro-controlleur et une puce Ultra-Wide Band DW1000 : la taille des paquets UWB 802.15.4 est limitée et la couche MAC est très simple, sans mécanisme de type CSMA/CA. Nous établissons le nombre maximum de noeuds supportés et modifions FTM-BC pour compenser la dérive d'horloge réelle des équipements en mettant en oeuvre une estimation SDS-TWR plus robuste, avec un surcoût faible en transmissions. Nous évaluons notre implémentation expérimentalement et en émulation. Nous mettons en évidence les pertes de paquets dues au fonctionnement half-duplex du DW1000 et au remplacement de CSMA/CA par ALOHA.

**Mots-clefs** : FTM, broadcast, ranging, clock drift, Ultra-Wide Band

## 1 Introduction

Accurate positioning and distance measurement are critical in logistics, healthcare, automotive systems, multi-robot navigation (swarms), ... Having accurate localisation information is a significant challenge, as GPS signals are often inaccessible indoors or can be degraded by the surrounding environment. Ultra Wide Band (UWB) communications are particularly suitable for estimating a distance between two nodes by measuring the Time of Flight (ToF) of the radio signal with the Two Way Ranging (TWR) technique. Fine Time Measurement (FTM) [7] is a similar mechanism in WiFi. Recently, FTM-BC [2] has been proposed to compute the ToF between all pairs of a wireless network efficiently.

In this paper, we provide a real implementation of FTM-BC on a constrained system with a microcontroller and a DW1000 UWB radio chip. Section 2 details the protocol specification, Section 3 explains how practical constraints have been handled. Performances are evaluated in Section 4 with experiments and emulation.

## 2 FTM-BC protocol overview

The core idea of FTM-BC is to leverage the medium's broadcast nature to compute ToF for all pairs of connected devices in a network. It works in successive rounds (Fig. 1). Each round starts with an initiator broadcasting a packet. All its neighbours reply. These replies initiate the same behaviour to nodes that are not reached by the first packet, creating a wave that crosses the whole network. A packet includes the current round id, the timestamp of the last transmission by the sender and its corresponding round id, and all timestamps of the last packets previously received from neighbors, with the associated node address and the corresponding round id.

<figure><img src="image_2.png" /><figcaption>Figure 1: FTM-BC round</figcaption></figure>
Figure 2 depicts the state automata of a node. When it receives a packet, it schedules a reply after a random delay. If another packet is received before the reply is emitted, it is rescheduled to incorporate the information extracted for the newly received packet in its payload. The node's behaviour is slightly different regarding resolving distances and starting a new round, depending on whether it is the initiator.

FTM-BC requires two rounds to collect the timestamps needed for ToF calculation using the TWR formula (see Section 3.2). We slightly modified the original algorithm by systematically transmitting the last known timestamps, allowing us to use the two rounds as a sliding window. This makes the implementation easier and allows successive ToF calculations at each round after the second one, instead of every two.

<figure><img src="image_3.png" /><figcaption>Figure 2: FTM-BC automata</figcaption></figure>

# 3 Constraints of micro-controller and Decawave UWB chip

The original paper uses the CSMA/CA mechanism of an ideal 802.11 MAC layer to avoid collisions and randomly order the communications. The UWB MAC layer of the DW1000 chipset has no CSMA/CA. It could be possible to implement a Clear Channel Assessment (CCA), by sampling the medium for a short period of time, and wait for the medium to be idle before transmitting, but the DW1000 chip limits it to the preamble. For this first implementation, we opt for an unslotted ALOHA-like mechanism with a waiting time composed of a fixed part (delay) (covering the time needed by the micro-controller and the chip to process the packet) and a random part drawn i.i.d. in $[0, timeout]: t_{Tx} = t_{now} + delay + random(timeout)$.

The initiator is selected using an election process that avoids assigning specific roles to nodes before deployment, and increases the reliability if a node disappears. It can change at each round.

## 3.1 Packet size and limitations

Fig. 3 depicts a UWB frame with an FTM-BC packet.

The UWB MAC header (MHR) is kept small: Personal Area Network id (PAN Id) is common to source and destination addresses, source (Src) and destination (Dst) addresses are 2-byte encoded, and auxiliary security (Aux Sec) is left to the implementer (so it can take from 0 up to 9 bytes), for a total of 20 bytes.

The payload is classically decomposed in a packet type identifier (type) followed by the corresponding payload. The FTM-BC

payload includes the current round (Round), a set of flags (Flgs) indicating in particular if the packet is emitted from an initiator (1 byte each), information about the Tx timestamp (round id Round Tx and transmission time Timestamp Tx), and finally, the information about all last receptions from neighbours (Src Rx, Round Rx, and Timestamp Rx).

<figure><img src="image_4.png" /><figcaption>Figure 3: FTM-BC pkt in UWB frame</figcaption></figure>
DW1000 timestamps are coded over 40 bits. A classic technique for compressing timestamps is to encode only a delta from the start of the algorithm. This technique cannot be applied since the timestamps are exchanged and the clocks are not synchronized. Another technique would be to truncate the timestamps to 32 bits. Considering the high definition of UWB clocks, 32 bits would represent only 67ms, which might be a too short timespan for a completed round. Each information about a neighboring transmission hence takes 8 bytes and the information about the sender plus the FTM-BC header 6 bytes.

The size of a standard 802.15.4 UWB is 127 bytes†. The maximum number of neighbours (i.e. the maximum degree of the connectivity graph) that can be supported is therefore $\frac{127-29}{8} = 12$.

Our implementation is limited to 10 neighbours; hence, 11 nodes in a fully connected network, to leave room to transmit extra information about the node itself (position, speed, ...).

Another practical limit of the system is the memory available on the microcontroller. Only strictly useful information will be stored: transmission and reception times and neighbor ids, for a limited number of rounds. The number of rounds needed in memory depends on the ranging method used to compute ToF: Two-Way Ranging or Symmetrical Double-Sided Two-Way Ranging.

## 3.2 Time of Flight calculation

With ideal clocks, Two-Way Ranging allows the computation of ToF even if the clocks are desynchronized.

$$ToF_{TWR} = \frac{(round_1 - reply_1)}{2} = \frac{(T_{RA} - T_{SP}) - (T_{SA} - T_{RP})}{2}$$

Real clocks are however subject to drift, measured in ppm. It induces errors when computing a duration as the difference between two timestamps. The longer the duration, the larger the error [3, 4]. In this regard, FTM-BC is less robust to clock drift as classic TWR since the duration of a round is much larger than a point-to-point packet exchange. The impact of the clock drift on TWR is shown in the following section.

Symmetrical Double-Sided Two-Way Ranging (Fig. 4) has been introduced to compensate for the clock drift [6]. It requires an extra packet exchange and computes the ToF as follows.

$$ToF_{SDS-TWR} = \frac{(round_1 \times round_2) - (reply_1 \times reply_2)}{round_1 + round_2 + reply_1 + reply_2}$$

To adapt FTM-BC to SDS-TWR, an extra round of information is kept in memory. Since the ToF computations are made in sliding windows, there is still a result at each round after the third one.

# 4 Experimental evaluation

In this section, we analyze the performance of our modified protocol using a hardware testbed (Fig. 5) and a low-level emulator, both running the same implementation‡. The emulator uses a Unix process to encapsulate a node, and the DW1000 is emulated at the SPI register level, with UWB communication being carried through Unix sockets.

We show how TWR fails while SDS-TWR is robust against clock drifts and investigate the cost of using an ALOHA-based MAC layer and a half-duplex UWB chipset in terms of packet loss.

<figure><img src="image_5.png" /><figcaption>Figure 4: SDS-TWR packet exchanged</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Testbed, 6 nodes configuration</figcaption></figure>

<footnote>† The DW1000 chipset allows a proprietary 1023-byte packet that we don't consider for compatibility reasons.</footnote>

<footnote>‡ Code available at https://gitlab.inria.fr/dalu/strand/-/tree/ftm-bc</footnote>
<table><caption>Table 1: Measurement error with clock drift between 2 nodes 2 metres apart.</caption><thead><tr><th rowspan="2">Method</th><th rowspan="2">Expected</th><th colspan="3">Emulator</th><th colspan="2">Testbed</th><th rowspan="2">Required rounds</th></tr><tr><th>PPM</th><th>Mean</th><th>Stddev</th><th>Mean</th><th>Stddev</th></tr></thead><tbody><tr><td>TWR</td><td>2 m</td><td>2</td><td>8.05 m</td><td>1.74 m</td><td>5.81 m</td><td>0.13 m</td><td>2</td></tr><tr><td>SDS-TWR</td><td>2 m</td><td>2</td><td>1.99 m</td><td>0 m</td><td>2.23 m</td><td>0.02 m</td><td>3</td></tr></tbody></table>

## 4.1 Clock drift impact

Table 1 shows the impact of the clock drift with 2 nodes 2 metres apart, measured on the testbed and estimated on the emulator. The specifications of the DWM1000 indicates a clock with a 20 ppm drift, which can be reduced to 2 ppm using the manufacturing-time pre-calculated trim value. The testbed experiment shows a 3.8 m distance error with TWR. The emulator computes the maximum possible effect of the drift, considering that the amplitude of all drifts are added: a 2-ppm drift on each node is equivalent to a 4-ppm drift on one node and 0 on the other. Fig. 6c shows that off-the-shelf dwm1000 modules have, in our case, a clock drift of 1.25 ppm in the emulator, which is in the expected margin of error of the specifications. SDS-TWR computation is robust to the drift with error around 10% on the hardware and 1% in the emulator.

Fig. 6c shows that the error of distance estimation when using TWR is, as expected, proportional to the drift [1, 5]. The error is rapidly unsustainable for short-distance estimation.

## 4.2 Packet loss estimation

Since we are using an ALOHA-based MAC layer, packet losses are expected because of collisions, but also because the DW1000 is half-duplex and takes time to switch to transmitting and receiving modes. It is sometimes in a non-programmed mode, denoted IDLE. Fig. 6a and 6b show the percentage of packet loss when a node is in TX state (when there is a collision) and in IDLE state (when the radio could not switch quickly enough in the RX state) when the number of nodes in a fully connected network increases.

With our emulation settings, with large delays, the collisions are quite rare, and most of the loss happens in the IDLE state. The system being static, it doesn't impact the overall quality of distance estimation. In the case of a moving network, it would be a problem. Double buffering techniques could avoid this loss.

<figure><img src="image_7.png" /><figcaption>Figure 6: Packet loss vs cluster size, TWR errors vs drift, emulation with delay = 5 ms and timeout = 10 ms</figcaption></figure>

# 5 Conclusion

We have produced a practical implementation of FTM-BC on a constrained system made of a microcontroller and a DW1000 UWB chipset. The protocol has been modified to compensate clock drifts with SDS-TWR at the cost of a round of packets. A sliding window memory management allows to compute ToF at each round, hence reducing measurement latency. The memory and frame size constraints limit the size of the network to 10 nodes and the ALOHA MAC layer induces packet loss that could be avoided with a more complex implementation. Further work will include a testbed experiment on a fullsize network and to assess practical performances of relative geolocalization of FTM-BC compared to point-to-point TWR.
References

[1] DecaWave. *Sources of error in DW1000 based two-way ranging (TWR) schemes*. Tech. rep. APS011. Version 1.0. DecaWave, 2014.

[2] Yann Busnel and Hervé Rivano. "FTM-Broadcast: Efficient Network-wide Ranging". In: *IPIN 2023: 13th International Conference on Indoor Positioning and Indoor Navigation*. 13th International Conference on Indoor Positioning and Indoor Navigation (IPIN 2023). Nuremberg, Germany: IEEE, Sept. 2023, pp. 1–6. DOI: 10.1109/IPIN57070.2023.10332504.

[3] Ioan Domuta and T. Palade. "Two-Way Ranging Algorithms for Clock Error Compensation". In: *IEEE Transactions on Vehicular Technology* 70 (2021), pp. 8237–8250. DOI: 10.1109/TVT.2021.3096667.

[4] Cung Lian Sang et al. "Numerical and Experimental Evaluation of Error Estimation for Two-Way Ranging Methods". In: *Sensors* 19 (Feb. 2019), p. 616. DOI: 10.3390/s19030616.

[5] M. Pelka et al. "Evaluation of time-based ranging methods: Does the choice matter?" In: *2017 14th Workshop on Positioning, Navigation and Communications (WPNC)*. Oct. 2017, pp. 1–6.

[6] Nezo Ibrahim Fofana et al. "An Original Correction Method for Indoor Ultra Wide Band Ranging-based Localisation System". In: *International Conference on Ad Hoc Networks and Wireless (AdHoc-Now 2016)*. Lille, France, July 2016, pp. 79–92.

[7] *Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification*. Piscataway, NJ: IEEE, 2016.