The development of wireless networks allowing precise time-stamping of emitted/received packets paves the way to precise localization, which can be used for communication and coordination inside a lfeet of Unmanned Aerial Vehicles (UAV). In this paper, we present the limit of Ultra-Wide Band (UWB) to perform relative positioning and UAV navigation, and we propose an architecture based on Time Diference of Arrival (TDoA), which doesn't depend on deploying external equipment, as receivers will be embedded on the UAV itself. Results from simulation campaigns reveal that even if distance measurements lack precision to be useful, direction measurement on the other hand has enough precision, and this information allows us to reduce the number of packets exchanged to perform relative positioning.
FoV LiDAR Scanner – CH64W at $ 4400), and would require several of them to cover the whole ifeld of view.
Since most of recent devices are wirelessly connected, in particular in the rising Internet
of Things, it is natural to try and leverage the communication devices to provide localization
or, at least, ranging, that is estimating distances. As first order model of path loss is directly
bound to the distance, it is tempting to use the received signal strength of communications to
estimate the distance between the source of the transmission and the receiver. It was however
experimentally and theoretically shown that the precision of such estimate is very low, even
for static devices [
The physical layer of WiFi is the main reason of the (comparatively) low precision of
802.11mc. This explains the recent interest in Ultra-Wide Band (UWB) technology for ranging.
It has been widely exploited for indoor localization [
In this paper, we investigate how UWB communications can be exploited to compute relative positions in a swarm (Figure 1). Our contribution is threefold: • we thoroughly describe the main factor of localization errors and the practical limits implied by the use of UWB communications • we propose an architecture of UAV localization system based on Time Diference of Arrival multilateration that does not require distributed clock synchronization between UAVs and uses a very low number of transmissions • we evaluate in details the nature and geometry of localization errors, paving the way to an eficient control mechanism of UAVs.
The roadmap of the paper is as follows. In Sec. 2, we go into the specific and practical limitations imposed by the use of UWB in the settings of swarms. In particular, we show that clock synchronization issues introduce a trade-of between the size of the swarm, the frequency at which localization is updated, and the multilateration techniques that are used. We then propose in Sec. 3 a pure TDoA-based architecture that alleviates distributed clock synchronization requirements between UAVs and theoretically achieves relative positioning with a very low number of transmissions, hence making it possible to address large swarms. Finally, in Sec. 4, we evaluate the performances of this architecture through extensive simulations.
Working with a swarm of UAVs, fast and eficient computations of positions is a key challenge. In this section, we investigate the limits due to the Ultra-Wide Band technology in distance estimation used for multilateration.
Computing each UAV position needs at least four distance measurements. Several packets have to be exchanged, which may lead to collisions or network saturation. It is therefore crucial to investigate the trade-of between the limits on precision and those on the size of the swarm that can be achieved, which depends on the multilateration and measurement techniques.
Using a classic Time of Arrival (ToA) approach theoretically allows us to compute the position
of a UAV with a single transmission received by at least four reference anchors. It however
requires strong clock synchronization among all devices: as we are dealing with propagation
time close to the speed of light, 1 cm of precision requires roughly 33 ps of synchronization.
Clocks variations also afect distance measurement and positioning. An analysis of the induced
error due to the clock drift on common positioning methods is described in [
A widely studied way to compensate the lack of strong synchronization is to use algorithms
of the Two-Way Ranging (TWR) family (e.g. SDS-TWR [
Despite data transfer rates up to 6.8 Mbps for the UWB, the transmission frame rate is not
very high and constrains the scalability of the swarm for localization. An analysis for indoor
localization [
Indeed, a UWB configuration well-suited for distance measurement [
Depending on the underlying MAC protocol (ALOHA, TDMA, ...) the actual achievable frame rate will then be between 1338 (non slotted ALOHA) and 7278, which will limit the number of distance/localization measurement according to the selected method (TWR, TDoA, ToA, ...) as it could require more than one frame per measurement.
To control its flight, a UAV needs to acquire its position frequently enough. A _
of the order of 10 Hz is considered the minimum requirement for a stable flight [
Computing each position requires performing one or more transmissions, their number being
denoted in the following. 3D positioning requires at least 4 distances, that
can be obtained with 1 (ToA/TDoA) to 4 (SDS-TWR) transmissions each. In these examples
∈ [
Then the maximum achievable swarm size is related to these quantities and the available _ of the implemented UWB protocol is as follows:
_ ≤ · _
A 10Hz sampling using SDS-TWR with 4 reference anchors has been experimented using
Crazyflie, STM32F405 on small scale systems [
Using SS-TWR instead and taking into account the clock ofset information available in the
DW1000 chipset it is possible to have the same precision as with SDS-TWR [
TDoA and ToA approaches only require 1 transmission to get each position measured, which allows much larger swarm sizes, as summarized in table 1. Moreover, this number is decorrelated from the number of anchors, since the same transmission is used by all anchors.
All the distance and position measurements are performed by identifying the moment of the
packet emission/reception, so it is important to have a precise and coherent timestamp of
these moments. Besides clock synchronization issues, timestamping is also a source of loss of
precision. In the following, we consider a system built on an NRF52840 micro-controller and
the Decawave DW1000 chipset, which has a Cortex M4 running at 64MHz. The timestamping
process runs a Leading Edge Detector algorithm, which is influenced by signal reception power
(as well as voltage and temperature that can impact oscillators and antennas). This influence can
SDS-TWR
SS-TWR with initial packet broadcasted
SS-TWR with initial packet broadcasted and with altimeter
TDoA
ToA
Anchors
4
4
3
5
4
be partly mitigated using internal chip information (e.g. ofset register and CIR register) [
Ideally, if all UAVs share a common clock, there wouldn’t be any clock synchronization issues. Of course, that cannot be achieved for ToA localization without costly hardware. There is however a way to implement that with TDoA, which only requires synchronization among receivers while imposing no condition on the emitter. Another significant advantage of TDoA (and ToA) compared to TWR methods is its ability to estimate the position using a single packet, making it immune to UAV movements.
The base idea is to reverse the classic TDoA approach and consider that all the receivers are embedded on the UAV that wants to localize an emitter. In such a setup, the receivers are close enough to each other to actually synchronize with the same physical clock (using wires).
Figure 2 depicts the theoretical set-up of UWB receivers on a UAV. They are distributed on a sphere , as a solution to the Thomson problem, the UAV being the center of the sphere. The UAV computes the relative localization of an emitter (which can be an anchor or another UAV).
The additional benefit of using TDoA is that localization can be done theoretically with only one transmission from the reference anchor. The movements of the UAVs are not degrading the distance estimation between successive transmissions. Moreover, unlike TWR, there is no information to transmit in the packets’ payload which is available for other tasks. In particular, localization can be performed for each transmission useful to the application.
From a mathematical aspect, with an infinite precision on time measurements, this architecture
achieves the localization of our UAVs. However, the aforesaid errors in timing measurements are
unavoidable. Consequently, the localization is an estimation provided by solving an optimization
algorithm, such as the Nelder-Mead algorithm [
In the configuration yielded by our architectures, the emitter is outside of the convex hull formed by the receivers. This is the worst case scenario for solving TDoA localization.
The localization is indeed the intersection of hyperbolas, but when there are errors in the measurements, the estimation of localization is in the intersection of the shaded areas depicted in Figure 3. The size of this area is an upper bound on the localization error. Unfortunately, as the emitter gets further away from the convex hull formed by the receivers, the area increases in an oblong shape. This can lead to large errors in the estimation of the distance between the emitter and the UAV. The estimation of the angle is on the contrary more robust since the intersection is aligned with the vector between the emitter and the UAV as shown in Figure 4,
In the next section, we investigate the sensitivity of our architecture to a UWB chipset precision and error measurements.
2
Suppose that a UAV , carrying our TDoA architecture, estimates the position of a UAV emitting a packet as depicted in Figure 5).
2 4
1 3
Our simulation will only need to consider fixed UAVs as the position estimation using ToA/TDoA is done using a single packet, making the UAV movement negligible compared to the packet propagation speed.
We consider the DW1000 UWB chipset, where timestamps are 40-bit values at a nominal 64 GHz resolution. The timestamp precision is approximately 15 ps, denoted as a tick. Considering that radio signals travels at the speed of light, a tick represents about 5 mm of precision for distance estimation. Timestamping errors are measured as a number of ticks. They are intrinsic to the UWB chipset and hardware.
The receivers of our architecture are supposed to be installed at the extremities of the UAV, roughly at half the wingspan of the UAV to its center.
The following parameters describe a test configuration of the architecture, denoted aXsYSZ.
O
E err err • , the timestamping error (in ticks) occurring in the time stamping process. • , the number of receivers (4, 5, or 6) in the architecture.
• , the distance of the receivers to the center of the UAV center.
The number of receivers and the wingspan describe the UAV characteristics, while timestamping errors represent an external source of errors. In this paper, unless stated otherwise, we will report the results of the four following configurations, which include diferent timestamping errors, number of receivers, and wingspans.
configuration max error receivers
wingspan Two components of the position estimation errors are evaluated, the distance and the angle as depicted in Figure 6. We consider indoor settings. UAV is at a distance ranging from (almost) 0 to 10 m at all possible angles. We report in the following the average overall positions 0 at distance ∈]0, 10], of the errors in distance and angle estimations.
We also consider that UAV is allowed to explore various positions around a position 0 within a small radius . () being the error for the position , we define the minimal achievable will face. error (for distance or angle) around 0 as min(0, ) = min‖− 0‖< (). It represents the most precise localization estimations a UAV could get by achieving small movements around its position. We report in the following the maximum minimal achievable errors (figure 7) within the 10 m radius sphere ℬ around UAV , with respect to . It represents the worst case a UAV min( ) = max
min 0∈ℬ ∈ℬ,‖− 0‖< 0 As a baseline, we first evaluate the performances of our architecture in the theoretical case where ToA is possible and report them in Figure 8. It would give very good performances, but requires that the emitter and the receivers are synchronized. This is technically achievable using chip scale atomic clock (such as Microchip CSAC-SA45S) calibrated to a known distance. It is however very expensive, between 2000 $ and 5000 $ per receiver and emitter. (a) Average angle and distance errors (b) maximum minimal achievable errors
For configuration a0s5S25, with no timestamping error, 5 receivers and 50 cm wingspan, the minimum achievable error is depicted in Figure 8b.
Figure 9a shows the minimum achievable errors obtained on configuration a0s5S25 with no timestamping error, 5 receivers and 50 cm wingspan. Even without comparing to ToA performances, one can see that the distance estimation is too approximate to be useful, in particular in indoor settings : the worst case exceeds 4 m even for = 10 cm. As expected, however, the angle estimation is well constrained to 0.5°.
As a matter of fact, it happens that the position estimation computed by the Nelder-Mead algorithm fails. It can diverge, and provide no values, or converge to absurd distance values while providing a correct angle value. These points are respectively reported as "non-converging" for both angle and distance, or for distance only.
Figure 10 depicts what happens in the sphere of radius around a non-converging position; a layered structure emerges. Yellow layers are the non-converging positions, while other layers are diferent level of errors. Therefore, if the UAV does small movements around its position, in the radius sphere, while repeating its measurements, it will always have a solution and be able to reach the minimum error, at least for the angle. As a matter of fact, this is naturally the case of a drone that tries to remain stationary. It will certainly undergo small random variations in its position.
The distance between the receivers is a strong factor of sensitivity to errors in the TDoA estimation. Figure 9b shows the errors for configuration ( a5s5S40) with a timestamping error of 5 ticks, a wingspan of 80 cm, and the same 5 receivers. For ToA, the timestamping errors degrades the precision compared to (a0s5S25). For TDoA however, the wider wingspan makes the architecture more robust and the errors are much lower. The maximum minimal achievable error becomes practical when > 5cm.
The average errors of all aforesaid configurations are summarized in Figure 11. Configuration (a4s4S25) with only 4 receivers is mathematically under determined and theoretically leads to two solutions. However, the initial search position of the Nelder-Mead algorithm chooses the most likely valid solution.
At close range, the impact of timestamping errors ((a4s4S25) and (a5s5S40) configurations) on both angle and distance error makes the architecture unsuitable even for preventing collisions.
On larger distances, the average angle error is reasonable: under 5 ° with about 15 % of non-converging measurements.
The average distance error seems much less practical, with a linear growth as expected from the geometry of hyperbolas intersection. These average results even look contradictory with the maximum minimal achievable errors described in the previous section: the average distance errors of (a5s5S40) are worse than those of (a0s5S25). This can be explained by the larger proportion of non-converging positions, strongly impacted by the timestamping errors (the a parameter). The better results of the maximum minimal achievable errors show that the exploration over the small radius sphere around a position allow us to circumvent the non-convergence issue. Whatever the position of the UAV, it is close to a converging and low error position estimation.
(a) Angle (b) Distance
Our TDoA architecture which embeds receivers on the UAV is a promising way to build a cost-efective solution for relative localization within a large swarm using Ultra-Wide Band transmissions. Our simulations show that the precision of angle measurement is practical in all configurations, even when timestamping is prone to large errors. The average precision of distance measurement cannot however be exploited without further improvements because of the specific geometry of intersection of hyperbolas underlying TDoA errors. Local exploration seems to mitigate eficiently the TDoA distance problem. It however yields further issues to be investigated. First, it would require several transmissions. Even if the payload of the packets is still available for the application, the network load should be put compared to TWR-like protocols as it has been identified as a limitation of the size of the swarm. Then, being able to identify the minimal error in the exploration sphere is not trivial and should be carefully analyzed. Another interesting direction to explore is to fuse information from other sensors (telemeter, altimeter, relative speed, ...) to further increase the precision.
This work was supported by the European Commission under the H2020 project23 BugWright2 (871260): Autonomous Robotic Inspection and Maintenance on Ship Hulls and Storage24 Tanks.