Ultra-wideband Concurrent Transmissions for Ranging and Localization

(1)

Ultra-wideband Concurrent Transmissions

for Ranging and Localization

Pablo Corbal´an Pelegr´ın

Advisor Prof. Gian Pietro Picco

University of Trento, Italy

Committee Prof. Davide Dardari

University of Bologna, Italy

Prof. Anthony Rowe

Carnegie Mellon University, USA

Prof. Neal Patwari

Washington University in St. Louis, USA

University of Trento Trento, Italy

(2)

(3)

(4)

(5)

Abstract

Global navigation satellite systems (GNSS) have radically changed business, industry, and society, shaping the way we transport, navigate, and generally live every day. After all these years, however, GNSS location information remains only valuable outdoors, leaving indoor environments where people dwell most of the time without proper localization support. Many technologies and systems have approached this problem including optical, inertial, ultrasonic, and radio-frequency (RF), to name a few; yet the problem remains.

In this thesis, inspired by the indisputable success of GNSS and the re-emergence of ultra-wideband (UWB) radios to the forefront of technology, we aim to change the state of affairs in RF localization by proposing novel clean-slate UWB ranging and lo-calization schemes based on concurrent transmissions. These are generally considered harmful for communication but become a rich source of localization information when combined with knowledge of the channel impulse response (CIR).

Our first novel contribution lies in the concept of concurrent ranging, which allows mobile nodes to simultaneously measure the distance to multiple devices—hereafter, called responders—removing the need for the wasteful long packet exchanges tra-ditionally used for ranging and localization. Different from conventional schemes, which spread responder transmissions over time, we force responders to transmit concurrently and let their signals “fuse” in the wireless channel; the resulting im-pulse response, as measured by commercial UWB radios, contains all the necessary timing information to extract the desired distance to all responders. This first contri-bution, however, also serves us to realize the many challenges ahead to unlock the real power of concurrent transmissions for localization.

We address these challenges along the way, starting with Chorus, our second contri-bution. Chorus exploits an anchor infrastructure that transmits packets concurrently. Mobile nodes listen for these transmissions and measure from the CIR the time differ-ence of arrival (TDoA) of the concurrent signals, privately computing their own posi-tion at a high rate using hyperbolic localizaposi-tion. This reverse TDoA scheme, although simple in concept, is extremely powerful in that it enables passive self-localization of infinitely many targets at once, a feature largely missing in the RF literature. In Cho-rus, we address the difficult challenges to reliably detect and identify the signal from the different responders. Yet, the limited transmission precision of commercial UWB transceivers constrains the many benefits of Chorus.

In this context, we i) contribute a model to ascertain the impact of the transmission uncertainty on concurrent transmissions, and ii) address the issue with a compen-sation mechanism that fine-tunes the local oscillator frequency of responders while

(6)

they prepare to transmit, allowing us to simultaneously tackle the impact of clock drift on distance estimation. We demonstrate in our evaluation that with this com-pensation mechanism we can schedule transmissions with<1 ns error, removing the need to share timestamps to precisely measure distance. We rebuild concurrent rang-ing around this mechanism, obtainrang-ing decimeter-level rangrang-ing and localization at a fraction of the cost of conventional schemes. These results turn concurrent ranging into an immediately applicable technique that new systems can now exploit, benefiting from a different set of trade-offs hitherto unavailable. Further, the TX compensation mechanism can be directly applied to Chorus, similarly making fast and accurate passive self-localization a tangible reality.

We continue our endeavor with a systematic characterization of the conditions under which UWB concurrent transmissions succeed to provide reliable ranging and com-munication across different complex channels. The results we put forth empower developers to fully exploit concurrent transmissions in their designs, potentially in-spiring a new wave of ranging, and also communication, primitives that can bring to UWB the same striking benefits found in low-power narrowband radios.

The thesis is completed by looking at other challenges preventing the wide adoption of UWB localization systems, namely, large-scale operation, energy efficiency, and the complexity to install anchor deployments. We tackle these aspects in the last part of the thesis with three additional contributions. First, we propose Talla, a TDoA system that provides seamless large-scale localization for many tags across cells of time-synchronized anchors. Secondly, we fuse UWB ranging with odometry information and build an uncertainty model that only triggers new UWB estimates if and when needed, reducing consumption and channel utilization while satisfying the application-specific demands in terms of accuracy. And thirdly, we build state-of-the-art mechanisms to automatically compute the positions of all anchors deployed across large areas based on ranging information, facilitating anchor network deploy-ment for the many UWB-based real-time location systems (RTLS) to come.

Overall, this thesis changes the landscape of UWB localization with a new set of potentially disruptive schemes and systems that exploit the peculiar benefits of con-current transmissions and that consequently redefine the trade-offs of the technology.

Keywords:

Ultra-wideband, Wireless Localization, Concurrent Transmissions, Ranging, TDoA, RTLS, Concurrent Ranging, Low-power Wireless, Internet of Things, Cyber-physical Systems

(7)

Acknowledgements

I had the pleasure to share this research journey with many people to whom I owe my deepest gratitude.

First and foremost, I would like to thank my advisor Gian Pietro Picco for giving me the enticing opportunity to do a Ph.D. under his guidance. Every day he has transmitted me his relentless passion, enthusiasm, and ambition, encouraging me to explore the ideas that now form the core of this thesis. He has been patient, flexible, and understanding, and has supported me when I lacked the necessary resilience to cope with adversity. I feel truly fortunate to work with and learn from him.

I want to thank Davide Dardari, Anthony Rowe, and Neal Patwari for reviewing my work and for their positive comments. I am honored to have them on my committee. A special thank you goes to Tiina Harmaala, without her support I would not have dared to start a new life in Italy. I am deeply grateful to Ramona Marfievici, who encouraged me to follow my path and taught me the foundations that now mark the way I carry out research, and to Timofei Istomin, who persistently provided me support and advice throughout these years.

A significant part of this thesis is the result of collaborations. Enrico Varriale and Thales Alenia Space motivated our work on UWB. Davide Vecchia was the driving force for the work in Chapters 6 and 7 and helped me with the implementation in Chapter 5. The collaboration with Valerio Magnago, Danielle Fontanelli, and Luigi Palopoli introduced me to the world of robotics and led to the work in Chapter 8. Davide Molteni provided help and advice developing many tools that were invalu-able to test our ideas. Sameera Palipana helped me develop some Chorus techniques. My M.Sc. students, Francesco Giopp and Matteo De Martin, gave me many insights that are now captured in the thesis. Thank you all very much! It’s been wonderful working with you.

I would also like to thank the members of the Wireless Connectivity group at Bosch RTC for the incredibly rich professional and personal experience I had in California. It was a dream come true.

I am indebted as well to Rajeev Piyare, Nikola Janicijevic, and Roberta Guidolin for keeping me sane in Trento and taking me out from the lab into the wild. I thank Matteo Tr¨obinger for giving me company late at night in the university and our endless discussions about life and research. I also thank Silvia Demetri, Oana Iova, Amy L. Murphy, Diego Lobba, Dmitrii Kirov, Velu P. Kumaravel, Elia Leoni, Mattia Di Gangi, and Manuel L´opez for their valuable feedback, help, discussions, and good times along the way. I am also grateful to David Rojas and Alejandro Esquiva with whom I shared my very first research steps.

(8)

I am truly thankful to my friends from the Vamos Cop´on group, who gave me life when I needed it most. I can’t help but smile thinking about the many concerts, trips, parties, and, in general, experiences we’ve shared during these years, including the brilliant ones I can’t remember.

I also thank Luc´ıa Asensi for cheering me up with her wide smile and positive atti-tude the days before the defense of this thesis.

Finally, I am very grateful to my family for their unconditional love and unlimited support, help, and advice throughout my entire life. I am extremely fortunate to have them in my life.

¡Muchas gracias!

Callosa de Segura, Spain Pablo Corbal´an Pelegr´ın

29 April 2020

(9)

List of Publications

Journals

1. P. Corbal´an and G. P. Picco. “Ultra-wideband Concurrent Ranging”. Submitted to ACM Transactions on Sensor Networks (TOSN). 2020. arXiv: 2004.06324 [cs.NI]. (Chapter 3 & 5)

International Conferences

1. P. Corbal´an and G. P. Picco. “Concurrent Ranging in Ultra-wideband Radios: Experimental Evidence, Challenges, and Opportunities”. In Proc. of the 15th _Int. Conference on Embedded Wireless Systems and Networks (EWSN). 2018. Best Paper

Award. (Chapter 3)

2. P. Corbal´an, G. P. Picco, and S. Palipana. “Chorus: UWB Concurrent Transmis-sions for GPS-like Passive Localization of Countless Targets”. In Proc. of the 18th Int. Conference on Information Processing in Sensor Networks (IPSN). 2019. doi: 10.1145/3302506.3310395. (Chapter 4)

3. D. Vecchia, P. Corbal´an, T. Istomin, and G. P. Picco. “Playing with Fire: Explor-ing Concurrent Transmissions in Ultra-wideband Radios”. In Proc. of the 18th IEEE Int. Conference on Sensing, Communication and Networking (SECON). 2019. doi: 10.1109/SAHCN.2019.8824929. (Chapter 6)

4. D. Vecchia, P. Corbal´an, T. Istomin, and G. P. Picco. “TALLA: Large-scale TDoA Localization with Ultra-wideband Radios”. In Proc. of the 10th _{Int. Conference on} Indoor Positioning and Indoor Navigation (IPIN). 2019. doi: 10.1109/IPIN.2019. 8911790. Best Paper Award. (Chapter 7)

5. V. Magnago, P. Corbal´an, G. P. Picco, L. Palopoli, and D. Fontanelli. “Robot Localization via Odometry-assisted Ultra-wideband Ranging with Stochastic Guarantees”. In Proc. of the IEEE/RSJ Int. Conference on Intelligent Robots and Systems (IROS). 2019. doi: 10.1109/IROS40897.2019.8968019. (Chapter 8)

Posters and Demos

1. N. Janicijevic, P. Corbal´an, T. Istomin, G. P. Picco, and E. Varriale. “Demo: Small PLaNS Towards Mars: Exploiting Ultra-wideband for Self-localizing Rover Nav-igation”. In Proc. of the 15th _{Int. Conference on Embedded Wireless Systems and} Networks (EWSN). 2018.

2. P. Corbal´an, T. Istomin, and G. P. Picco. “Poster: Enabling Contiki on Ultra-wideband Radios”. In Proc. of the 15th _{Int. Conference on Embedded Wireless} Systems and Networks (EWSN). 2018.

(10)

Non-peer reviewed publications

1. E. Varriale, P. Corbal´an, T. Istomin, and G. P. Picco. “PLaNS: An Autonomous Local Navigation System”. In Proc. of the 31st_{Int. Technical Meeting of the Satellite} Division of The Institute of Navigation (ION GNSS+). 2018. doi: 10.33012/2018. 15898.

Other publications not included in this thesis

1. R. Marfievici, P. Corbal´an, D. Rojas, A. McGibney, S. Rea, and D. Pesch. “Tales from the C130 Horror Room: A Wireless Sensor Network Story in a Data Cen-ter”. In Proc. of the 1st _{ACM Int. Workshop on the Engineering of Reliable, Robust,} and Secure Embedded Wireless Sensing Systems (FAILSAFE). 2017. doi: 10.1145/ 3143337.3143343.

(11)

8.3.1 Measurement System . . . 136 8.3.2 Stochastic Guarantees . . . 137 8.4 Simulation-based Evaluation . . . 137 8.5 Experimental Results . . . 141 8.6 Conclusions . . . 143 9 Anchor Self-Localization 145 9.1 Related Work . . . 147 9.2 Problem Statement . . . 148 9.3 Distance Estimation . . . 149

(14)

Contents

9.4 Anchor Self-Localization Algorithm . . . 150

9.5 Evaluation . . . 151 9.5.1 Deployments . . . 152 9.5.2 Implementation . . . 152 9.5.3 Metrics . . . 153 9.5.4 Simulation-based Evaluation . . . 153 9.5.5 System-based Evaluation . . . 159 9.6 Conclusions . . . 167 10 Conclusions 169 Bibliography 171 x

(15)

List of Figures

2.1 UWB pulse. . . 10

2.2 UWB frame: the SHR is encoded in single pulses, while the data part ex-ploits BPM-BPSK modulation. Preamble codes determine the preamble symbol sequence and the time-hopping code (arrows) for data transmis-sion. Image by Davide Vecchia [140]. . . 11

2.3 Single-sided two-way ranging (SS-TWR) scheme. . . 16

2.4 SS-TWR ranging error vs. the response delay TRESP. . . 17

2.5 Double-sided two-way ranging (DS-TWR) scheme. . . 18

2.6 Cost function error and estimated positions in a 3-anchor (black crosses) deployment with a NLS solver and two initial positions p0. White circles denote the position estimate at each algorithm iteration from the initial p0 to the final estimate ˆp. For the algorithm to converge to the true position p (red cross), p0needs to be carefully selected. . . 21

3.1 Concurrent ranging: the initiator sends a broadcast poll to which respon-ders in range reply concurrently. . . 30

3.2 Concurrent ranging, idealized. With narrowband (3.2a) it is basically infea-sible to recover the timing information of the signals from the individual responders. With UWB radios (3.2b), instead, the different distance from the initiator to responders R1 and R2 produces a time shift ∆t between their signals. By measuring ∆t, we can determine the distance difference ∆d=_|d1−d2|between responders. . . 33

3.3 Experimental setup to investigate the reliability and accuracy of concur-rent ranging (§3.4.1–§3.4.2). I is the initiator, R1and R2 are the responders. 35 3.4 Packet reception rate (PRR) vs. initiator position d1, with two concurrent transmissions. . . 36

3.5 Normalized histogram of the SS-TWR ranging error with responders in isolation (3.5a) and two concurrent responders (3.5b). When using con-current responders, sometimes the initiator receives the packet from the farthest responder, while it estimates the first path for ranging from the closest responder, increasing the absolute error. . . 37

3.6 Zoomed-in views of Figure 3.5b. Note the different y-axis scale. . . 37

3.7 Ranging error vs. initiator position. . . 38

3.8 Experimental setup to analyze the CIR resulting from concurrent ranging (§3.4.3). . . 38

3.9 Average amplitude and standard deviation of 500 CIR signals for an iso-lated responder at d1 =4 m. . . 39

(16)

List of Figures

3.11 Average amplitude and standard deviation of 500 CIR signals for two con-current responders at distance d1 =4 m and d2=9.6 m from the initiator.

. . . 40

3.12 Normalized histograms of the time offset ∆t and corresponding distance offset ∆d between the leading CIR pulses from R1 and R2. . . 41

3.13 Normalized histograms of the concurrent ranging error per responder. . . 41

3.14 Experimental setup to analyze the CIR resulting from five concurrent re-sponders (§3.4.4). . . 43

3.15 Impact of the relative distance di among 5 responders, analyzed via the corresponding CIR. . . 44

3.16 CDF of the absolute ranging error for different inter-node distances di among 5 concurrent responders. . . 44

3.17 Power boundary to distinguish the first paths introduced by concurrent transmissions from multipath. . . 46

3.18 Cross-correlation of the two CIR signals in Figure 3.10. The maximum peak directly identifies the first responder when using concurrent trans-missions. . . 47

4.1 Basic localization schemes and concurrent transmission variants. Solid (dashed) lines denote unicast (broadcast) transmission; numbers denote temporal ordering. . . 50

4.2 Anchor identification (§4.2.2) and ToA estimation from concurrent responses after reordering the CIR array (§4.2.3). . . 57

4.3 CDF of σn. . . 57

4.4 Anchor clock drift over time w.r.t. a synchronization reference (#1). . . 59

4.5 Prototype, model, and evaluation toolchain. . . 59

4.6 Comparison of the estimated CIR ˆh(t) vs. the real h(t) measured in an indoor environment with two concurrent responders at d1 = 4 m and d2 = 8 m from the receiver. . . 61

4.7 Model amplitude error for different time shift TID values. . . 61

4.8 Evaluation deployments with fixed tag positions. Black lines represent walls and the grey line the metallic balustrade in Terrace. . . 63

4.9 ToA algorithm estimation comparison. . . 64

4.10 Chorus localization accuracy for different set of tag positions in Indoor (4.10a) and Terrace (4.10b). . . 65

4.11 Localization error in Indoor after aggregating the TDoA samples of M CIR signals. . . 66

4.12 Chorus localization success rate per tag position. Note that in Terrace we only have 18 tag positions. . . 67

4.13 TDoA and localization errors using T = 128 ns and K = 3 iterations in Indoor for different simulated transmission scheduling precisions e. . . 68

4.14 Localization error using T = 128 ns and K = 3 in Terrace for different TX scheduling precisions e. . . 68

4.15 Localization error with the IEEE 802.15.4 UWB channel model [99]. . . 70 xii

(17)

List of Figures

5.1 CFO in ppm between a transmitter and a set of six receivers as a function of the transmitter trim index. . . 76 5.2 Power decay profile in different environments according to the IEEE 802.15.4a

radio model [99]. . . 78 5.3 CIR rearrangement. The DW1000 measured the FP INDEX as the direct

path of R5 in the raw CIR (top). After finding the CIR sub-array with the lowest noise, we rearrange the CIR (bottom) setting R1’s response at the beginning and the noise-only portion at the end. . . 79 5.4 Threshold comparison. . . 80 5.5 Concurrent ranging time of flight τi computation. To determine the

dis-tance di =c×τi to responder Ri, we need to accurately measure the actual response delay T_RESP,i= T_RESP+δ_i+A_TX and the round-trip time T_RTT,i of each responder based on our ToA estimation. . . 83 5.6 Average CIR amplitude and standard deviation per time delay across 500

signals with the initiator in the left center position of Figure 5.9. . . 86 5.7 Time difference deviation from the mean across 500 CIRs. . . 86 5.8 Normalized histogram of the concurrent ranging distance estimation error

ˆdi−di across all 18 static positions in Indoor compared to SS-TWR. . . 88 5.9 3σ error ellipses with concurrent ranging and six concurrent responders.

Blue dots represent individual position estimates, brown crosses are an-chors. The dashed light red square denotes the Center positions of interest. 90 5.10 Localization error with concurrent ranging vs. SS-TWR across all 18 fixed

positions (5.10a) and only the Center positions of interest (5.10b). . . 91 5.11 Localization with concurrent ranging across four trajectories using the S&S

algorithm with K =3 iterations. . . 92 5.12 Normalized histograms of the ranging error across multiple mobile

trajec-tories with concurrent ranging using the threshold-based (5.12a) and S&S

(5.12b) ToA algorithms compared to SS-TWR with clock drift compensa-tion (5.12c). . . 93 5.13 Localization error CDF of concurrent ranging vs. SS-TWR with drift

com-pensation across multiple mobile trajectories. . . 94 6.1 Network topology of our experiments. M, Si, and Ri are the master,

sender, and receiver (responder), respectively. All nodes are in commu-nication range. The arcs represent the links under study: weak (dashed line) and strong (solid). . . 100 6.2 PRR with different PRFs (channel 4). Concurrent transmissions exploiting

different PRFs are very likely to be received correctly, especially with PRF64.102 6.3 Concurrent ranging with different PRFs. Despite interference, both PRFs

perform accurate ranging reliably. . . 102 6.4 CIR with concurrent transmissions using different PRFs and ∆t=−20.513 µs.103 6.5 PRR on the weak links (channel 4) and different preamble codes for PRF16

(6.5a) and PRF64 (6.5b). Concurrent transmissions with different preamble codes introduce significant packet loss, especially for the late transmission. 104 6.6 PRR on the strong links (channel 4) and different preamble codes for PRF16

(18)

List of Figures

6.7 CIR for various time shifts ∆t with concurrent transmissions using

differ-ent preamble codes. . . 105

6.8 Concurrent ranging with different preamble codes. Significant outliers appear especially with PRF16. Many ranging rounds are lost due to inter-ference and RX errors. . . 106

6.9 PRR with the same RF configuration (channel 4, PRF64, code 17). . . 107

6.10 PRR in a single-receiver scenario (channel 4, PRF64, code 17). . . 107

6.11 Zoom-in of 6.10. . . 107

6.12 PRR vs. number of concurrent senders (ch.4, PRF64, code 17). . . 108

7.1 Example time-slotted schedule including n dedicated anchor slots for time synchronization and k slots for tag localization beacons. . . 117

7.2 Prototypes and evaluation toolchain. . . 119

7.3 Impact of packaging on clock drift. . . 120

7.4 Measured (reference) and simulated clock drift curves. . . 121

7.5 Anchor deployments. A dark blue square denotes a stationary anchor attached to the ceiling, an orange square stands for a portable anchor, and an X represents a ground-truth landmark. . . 122

7.6 Localization error vs. synchronization rate in Hall (6 anchors). . . 124

7.7 Localization error vs. synchronization rate in real Hall experiments with boxed (left) and naked (right) nodes. The external black crosses are an-chors, the internal red ones are landmarks. Error ellipses denote the 3×standard deviation for a given rate. Black dots are individual samples. . 124

7.8 Localization error vs. synchronization rate in Corridor (6 anchors, boxed only). Note the different x-axis scale w.r.t. Figure 7.6. . . 125

7.9 Effect of the number of anchors on the error distribution with a 3.3 Hz synchronization rate in simulation. . . 126

7.10 Grid: ground truth (blue) vs. estimated position (yellow). . . 127

7.11 Grid: Number of anchors and localization accuracy. . . 128

7.12 Estimated trajectories in the Corridor. The color gradient represents time, axis values are in meters. . . 129

8.1 Platform model represented as a rigid body B moving on the Xw×Yw plane with an attached reference frame_hB_i. . . 133

8.2 Unicycle-like vehicle adopted in the experiment and representation of the reference system. UWB anchors are depicted as well. . . 136

8.3 Time evolution of the marginal PDF of fk(e) for a robot moving along a straight line parallel to Xw. Both, the actual (dashed line) and estimated (solid line) trajectories are reported. At the fourth depicted position, the integral in (8.13) exceeds the given confidence ψ due to dead-reckoning, hence the UWB system is triggered and the PDF narrows down (fifth de-picted PDF). . . 138 xiv

(19)

List of Figures

8.4 Localization accuracy under different (ψ, λ, k, ν). Our solution adapts the CDFs (left) to the user-defined threshold λ and confidence ψ, highlighted with crossed circles on each plot. Changing the encoder or ranging uncer-tainty for λ=0.3 m and ψ=0.8 (right) barely affects the resulting local-ization error. . . 139 8.5 Velocity profile. . . 140 8.6 UWB sampling pseudo-frequencies distribution. . . 140 8.7 Comparison between periodic and adaptive UWB sampling with the robot

moving at 1 m/s (left) and 1.5 m/s (right). Our adaptive mechanism satisfies the user requirements despite changes in the robot velocity. . . 141 8.8 Comparison with the state of the art (SoA) for different (ψ, λ). SoA

tech-niques based on the eigenvalue [38] are conservative, over-provisioning UWB measurements, increasing consumption, and decreasing scalability. . 141 8.9 UWB ranging (left) and positioning (right) error. . . 142 8.10 Localization error with periodic UWB sampling at different frequencies. . . 142 8.11 Localization tracking across three trajectories with ψ = 0.9 and different

threshold λ. Each black cross represents a UWB anchor. The UKF output (orange) follows accurately the ground truth measurements (blue). As we increase λ, the number of UWB measurements (brown) needed decreases. 143 8.12 Localization error with dynamic UWB sampling and ψ=0.9 for different

thresholds λ. The only measurements considered are taken just before triggering UWB ranging (i.e., worst-case scenario). . . 144 8.13 UWB localization rate with m = 5 ranging exchanges for different

confi-dence intervals ψ and thresholds λ over all trajectories. . . 144 9.1 Anchor self-localization architecture. After deploying the wireless nodes,

a distance acquisition system (e.g., UWB TWR or BLE RSSI) measures the distance di,j between neighboring nodes, optionally storing received (RX) signal diagnostics (Figure 9.1a). The distance estimates together with the known node positions are used in a weighted multi-dimensional scaling (MDS) solver to determine the unknown anchor positions (Figure 9.1b). To enhance performance, RX diagnostics can be optionally used for LOS/N-LOS detection and error mitigation. . . 146 9.2 Positioning performance with 4 known anchor positions (green circles)

selected randomly (9.2a and 9.2b) and in the boundary of the deploy-ment area (9.2c). Grey lines denote available wireless links, blue circles unknown anchors, and orange crosses estimated anchor positions. . . 155 9.3 Anchor positioning error boxplots as a function of the ranging standard

deviation σ. Small dots represent samples outside the 1.5× inter-quartile range of the distribution. . . 156 9.4 Average node degree (i.e., number of links per node) and standard

devia-tion as a funcdevia-tion of the communicadevia-tion range in Plant. . . 157 9.5 Maximum positioning error as a function of the communication range and

the number of known anchors across 10 iterations per configuration with a random (9.5a) and boundary (9.5b) known anchor selection. . . 157

(20)

List of Figures

9.6 Simulated 3D anchor self-localization performance with 8 known anchors and 20 m communication range. . . 159 9.7 Normalized histogram and CDF of the ranging error accross all

measure-ments in the three studied deploymeasure-ments. . . 160 9.8 Ranging error vs. distance, CFO, FPPL, RSS, and |RSS - FPPL|difference

across more than 163k and 111k ranging estimates in Department and Reception, respectively. The error does not present any clear correlation with the measured features and more complex techniques based on CIR analysis would be required to identify NLOS links and mitigate large errors.161 9.9 Positioning performance with 4, 6, and 8 known anchor positions (green

circles) in the boundary of the deployment area. Grey lines denote avail-able wireless links, blue circles unknown anchors, and orange crosses esti-mated anchor positions. . . 163 9.10 Network connectivity heatmap in Department and Reception. In the

former, nodes are deployed in long and narrow corridors where each node generally has between 3 to 12 good neighbors. In Reception, we have two clearly distinguished open areas, poorly connected between themselves. . . 164 9.11 Anchor self-localization in our two large university testbeds. Grey lines

denote available wireless links for ranging. . . 165 9.12 Position estimation of a mobile node using the true anchor coordinates vs.

the estimated coordinates in the Reception deployment. . . 166 9.13 CDF of the positioning error in Figure 9.12 using the true anchor

coordi-nates vs. the estimated coordicoordi-nates. . . 166

(21)

List of Tables

2.1 DW1000 current consumption comparison with the TI CC2650 BLE SoC [58] and the Intel 5300 WiFi card [20]. Note that consumption depends on ra-dio configuration, the CC2650 includes a 32-bit ARM Cortex-M3 processor

and the 5300 can support multiple antennas. . . 13

2.2 UWB localization comparison. The update rate and resulting scalability are approximate estimations with N =4 anchors. In practice, these rates will be lower to include necessary time for processing, peripheral commu-nication, logging, scheduling, location computation, etc. . . 24

3.1 Concurrent ranging performance with two responders R1 at a fixed dis-tance d1 =4 m and R2 at different distances d2 =d1+∆d. . . 42

4.1 Localization errors in Terrace for different time shifts TID with K = 3 iterations and e=0. . . 69

5.1 Main parameters of concurrent ranging with default values. . . 84

5.2 Deviation percentiles for the absolute time difference ∆tj,1 variations. . . . 87

5.3 Ranging error comparison across the 18 static positions considered. . . 88

5.4 Ranging error comparison across the 9 Center positions considered. . . 89

5.5 Ranging error comparison across multiple mobile trajectories. . . 93

6.1 RX errors on a misconfigured link. . . 104

6.2 PRR for 2 colocated networks with different PRFs. . . 109

6.3 Summary of findings. . . 110

7.1 Localization error for Figure 7.6–7.8 with a 3.3 Hz synchronization rate. . . 126

7.2 Impact of the number of anchors on localization error (cm). . . 127

8.1 Anchor positions expressed inhWi. . . 138

8.2 Frequency of UWB triggering as a function of the uncertainty e_k and η_k. . . 139

9.1 Execution time and positioning error as a function of the number of initial X0 _{values considered in the algorithm with a ranging error σ}₌_{15 cm, 15} iterations with different random errors, and the 4 known anchor positions in Figure 9.2c. . . 158

(22)

(23)

1

Introduction

The ever-increasing curiosity of mankind has led the human species to explore Earth, even in its most hidden and inaccessible corners. Over centuries we have developed countless navigation systems and tools from simple compasses to complex radio satellites that have either guided us to our desired destination or to find ourselves lost, leading to the discovery of new territories.

Today, we can hardly imagine what our life would be like without using location information obtained from global navigation satellite systems (GNSS), let it be GPS, GALILEO, or GLONASS. GNSS are arguably the most successful localization systems to date as they provide free, world-wide, and continuous position and velocity infor-mation to literally hundreds of millions of users every day [64]. As a result, GNSS have had a profound impact on markets and society, changing the way we move, transport, navigate, or travel. In fact, every modern car and phone now includes (at least) a GPS receiver, allowing their users, e.g., to efficiently travel to a different place or share their location with family and friends anticipating their expected time of arrival. Similarly, almost every smartphone application requests us permission to share our location, pointing out the economic value of positioning information. Among the key features leading to such success is the capability of GNSS to seam-lessly support an unlimited number of users simultaneously, as users only need to passively listen for the satellite signals and do not ever have to transmit. This makes GNSS infinitely scalable. To this end, GPS satellites concurrently broadcast ranging information exploiting low cross-correlation codes that allow receivers to estimate the propagation time of the signal from each satellite, and in turn distance. This, together with transmitted navigation information sharing the precise location of the satellites, enables the receivers to determine their own position.

Unfortunately, GNSS cannot provide precise-enough location information in many so-called GPS-denied environments, especially indoors, where people work and dwell most of the time. Over the last 20 years, this has led to a myriad of indoor localization

(24)

Chapter 1. Introduction

systems employing all sort of technologies, yet no mainstream solution has arisen that can satisfy the very diverse, demanding, and specific requirements of each potential application [66, 92]. Applications include robot/drone navigation [5, 50, 94, 96, 119], asset tracking in hospitals or industrial warehouses [37, 104], and behavior tracking of supermarket customers or museum visitors [153, 159], to name a few. We discuss the particular applications motivating our work together with necessary background in Part I. Among other factors, requirements vary significantly depending on the expected accuracy, update rate, and battery lifetime together with the number and density of targets to be located. For instance, navigation requires high-rate position-ing at the user to reach a destination, while trackposition-ing demands locatposition-ing possibly many targets across large spatial areas for long periods of time. Application domains span logistics, retail, healthcare, automotive, aerospace, and manufacturing [131], making indoor positioning a multi-billion dollar market engaging new customers by the day. Scalability and accuracy together with the lack of awareness from consumers are identi-fied as major roadblocks towards the adoption of indoor positioning systems [8]. The monetary costs and difficulties to deploy and set up these systems further prevent wider adoption [92].

RF Localization. Among the various technologies proposed for real-time location

systems (RTLS), radio-frequency (RF) has arguably become the leading one, espe-cially due to i) the pervasiveness of wireless communications and ii) the ability of radio signals to propagate through walls and obstacles. RF systems either use time, angle, or power as a means to determine position. Bluetooth Low Energy (BLE) and WiFi systems have traditionally exploited the latter, taking advantage of the attenua-tion of the received signal strength (RSS) with distance. RSS measurements, however, suffer strongly from temporal fluctuations due to multipath propagation and shad-owing [109], yielding large localization errors that are unaffordable for many applica-tions. Systems based on angle of arrival (AoA) can achieve sub-meter accuracy, but require large and expensive antenna arrays with sophisticated signal processing tech-niques at the infrastructure [70, 151]. Further, angular accuracy is limited [14] and decreases with larger distances [79]. Time-based techniques exploit the propagation time of the signal to either estimate the time of flight between devices or the time-difference of arrival (TDoA) at a set of time-synchronized known anchor positions. These techniques generally offer very high accuracy, but require precise clocks and large bandwidths to increase time resolution [40, 109], unavailable in the widespread narrowband WiFi and BLE technologies.

The Rise of Ultra-wideband (UWB) Technology. UWB radios have recently

re-emerged from oblivion to the forefront of technology, rapidly gaining attention from industry and academia thanks to the commercial availability of standard-compliant, cheap, tiny, and extremely precise transceivers like the DecaWave DW1000 [86] we use in this thesis. The DW1000 provides cm-level ranging accuracy at a lower cost than predecessor UWB transceivers (e.g., [27]), becoming a powerful asset to build the RTLS already hitting the market. UWB radios have now arrived at an inflection point reaching—for the first time—the pocket of millions of people through the new iPhone 11 from Apple. Hence, now is the defining time for UWB to either shine and stay or leave by the back door.

(25)

As we discuss in Part I, UWB operation is based on the transmission of very nar-row pulses in time, spreading the signal’s energy across a very large bandwidth (≥ 500 MHz). This provides several advantages over the common narrowband ra-dios, including i) large channel capacity, ii) enhanced propagation characteristics, increasing the signal capability to penetrate through obstacles and walls [154], and iii) excellent time resolution, allowing UWB radios to resolve the unavoidable multi-path components and precisely determine the time of arrival (ToA) of the signal [40, 109, 154]. These advantages make UWB an ideal choice to build accurate and robust localization systems. Nevertheless, it is not all about accuracy and UWB systems still face serious challenges to meet the applications demands to support high-rate and energy-efficient ranging and localization for large number of users, across large-scale operational areas.

Ch1. Inefficient distance estimation. Many UWB localization systems are based on

distance measurements, which are useful per se for several applications, e.g., proxemics or wildlife monitoring. Distance is acquired via two-way ranging (TWR) packet exchanges between two nodes: an initiator and a responder. The initiator first sends a ranging request to which the responder replies. By mea-suring the TX and RX timestamp of each packet, we can accurately estimate distance. The key problem here is that TWR involves pairwise packet exchanges between nodes. Hence, for a mobile node to determine its distance to N nodes, at least 2×N packets are required, in the simplest scheme [57]. More accurate schemes [62, 67, 69, 103] employ even more packets, making matters worse and resulting in inefficiently long packet exchanges that dramatically reduce the potential update rates that can be supported.

Ch2. High energy consumption. The consumption of current UWB transceivers [86],

although lower than WiFi chips providing channel state information [20], is sig-nificantly higher than other low-power wireless technologies such as BLE [58]. The high consumption together with the need for long ranging exchanges re-stricts the use of UWB radios in battery-operated devices and long-term de-ployments. While this is not necessarily a concern for the anchor infrastructure, often mains-powered, it significantly limits the operation of mobile tags, forc-ing applications to decrease the desired update rate to meet the battery lifetime goals.

Ch3. Multi-user support. The long packet exchanges required for ranging diminish

the number of users that can be located at a given update rate. UWB TDoA sys-tems address this challenge together with Ch2 by enabling position estimation based on a single transmission from mobile nodes. However, location informa-tion remains at the anchor infrastructure. Moreover, TDoA systems require strict (sub-ns) time synchronization across anchors, either achieved via expen-sive wired infrastructures or wireless mechanisms with frequent transmissions. Regardless of the technique employed, user and anchor transmissions must be properly scheduled to avoid collisions and therefore performance degradation. The higher the scheduling overhead, the lower the number of users supported.

(26)

Ch4. Large-scale operation. A large number of UWB systems are limited in scope

to single-hop networks, providing accurate localization within a small confined environment, e.g., a room or research lab. To provide real value for decision making whether it refers to navigation purposes or asset tracking, UWB sys-tems must provide seamless and continuous support across large operational areas beyond the reach of the limited UWB communication range, spanning multi-hop wireless networks, yet retaining the same accuracy. This requires ef-ficient networking support to synchronize and schedule the reliable localization operation of multiple users without disruption across multiple cells of anchors.

Contributions. In this thesis, inspired by the design choices that led to the irrefutable

success of GNSS, we aim at advancing the state of the art of RF localization in general and UWB in particular. In a few words, our goal is to enable accurate, high-rate, and energy-efficient UWB ranging and localization to satisfactorily support indoor applica-tions as effectively as GNSS have done so outdoors.

Towards this goal, we address Ch1–Ch3 in Part II with two novel and disruptive UWB ranging and localization schemes based on concurrent transmissions. These have tradi-tionally been considered harmful for wireless communication as they generally cause packet—and therefore, information—loss [43]. Consequently, wireless systems tend to avoid them with complex mechanisms. In this thesis, instead, we demonstrate that if combined with knowledge of the channel impulse response (CIR)—generally measured by UWB transceivers—concurrent transmissions become an extraordinar-ily rich source of information for localization. Thence, rather than avoiding concur-rent transmissions, we employ them as a fundamental building block for the design of our proposed techniques.

Our first contribution, presented in Chapter 3, lies in the newly introduced concept of concurrent ranging. In essence, concurrent ranging is similar to TWR, but instead of spreading responder transmissions over time, it makes them overlap. The transmit-ted signals purposely mix in the wireless channel; the measured impulse response at the ranging initiator contains all the necessary timing information to efficiently derive the distance to each and every responder in a single packet exchange. Thus concurrent ranging enables mobiles nodes to simultaneously measure the distance to multiple responders, slashing the total number of packets exchanged from (at least) 2×N in conventional ranging schemes to just two. This directly translate to imme-diate benefits in latency, energy consumption, and channel utilization. On the one hand, this first contribution helps us develop a thorough understanding of how to exploit concurrent transmissions for localization. On the other, it elicits the numerous challenges ahead to unlock their full potential.

We address most of these challenges as we continue our journey with Chorus, our second contribution in Chapter 4. Chorus embraces concurrent transmissions, but in a different scheme with an anchor infrastructure. In Chorus, a set of anchors transmit a packet concurrently. Mobile nodes listen for these concurrent transmissions and measure the signals’ time-difference of arrival (TDoA) from the CIR, allowing them to privately determine their own position using hyperbolic localization [137]. To this end, we tackle the challenges to i) identify anchor transmissions from the CIR and 4

(27)

ii) estimate the time of arrival (ToA) of each anchor signal, and consecutively the TDoA differences. This makes mobiles nodes completely passive as in GNSS because there is no need for them to transmit. Chorus therefore enables indoor passive self-localization of infinitely many targets at once. This comes with a series of advantages hitherto unavailable in any other indoor RF localization system, including privacy, scalability, and high-rate positioning.

At this point, our two proposed schemes enable distance and location estimation at a much lower cost than conventional schemes, either facilitating multi-user support by reducing channel utilization or directly providing passive self-localization. However, they are constrained in terms of accuracy, reducing their practical application, due to the limited transmission scheduling precision of commercial UWB transceivers. Notably the popular DW1000 we use can schedule transmissions with_≈ 8 ns granu-larity. In conventional ranging schemes this is not a problem as responders include the RX/TX timestamps in the packet payload. Using concurrent transmissions, as we cannot successfully decode each packet transmission, this translates to a high TX uncertainty and larger ranging and localization errors.

To understand the impact of this uncertainty, we model in Chapter 4 how concur-rent transmissions fuse on the CIR. This allows us to fully ascertain the potential decimeter-level accuracy of our proposed schemes if forthcoming UWB transceivers were to reduce the uncertainty. Further, it becomes a useful tool to easily find out the expected performance of our schemes if anchors were deployed in a different man-ner or in another environment, facilitating the necessary planning and preparation before deployment.

In Chapter 5 we tackle (and finally solve) the issue by using a compensation mech-anism. The key principle behind it is to carefully tune the local oscillator frequency of anchor responders while they prepare to transmit. For instance, if an anchor is going to transmit slightly in advance, we simply slow down the oscillator frequency, putting the transmission off until the desired time. The same principle also allows us to simultaneously tackle the frequency offset between transmitters and receivers, reducing the impact of clock drift on distance estimation—the highest source of error in the conventional single-sided TWR scheme—and improving CIR estimation under concurrent transmissions. We rebuild concurrent ranging around this mechanism and demonstrate in our evaluation that we can schedule concurrent transmissions with<1 ns error. This removes the need to share timestamps between nodes for pre-cise distance estimation and dramatically enhances the reliability of concurrent rang-ing as we solely need the measured CIR and a RX timestamp—provided by the radio even if RX errors occur. We evaluate our new concurrent ranging implementation in two indoor deployments with fixed node positions and mobile trajectories in an OptiTrack motion capture facility. Our results confirm decimeter-level ranging and localization accuracy, achieving comparable performance to conventional approaches but at a fraction of their cost. These results turn concurrent ranging into a practical scheme that new systems can now exploit. Moreover, the compensation mechanism proposed is also applicable to Chorus, adding high accuracy to the many benefits of our passive self-localization approach.

(28)

We continue our endeavor with a systematic evaluation ascertaining the conditions under which UWB concurrent transmissions succeed. In this context, we learn from the tremendous progress that concurrent transmissions have provided low-power narrowband radios for energy-efficient, fast, reliable, and dependable time synchro-nization, data collection, and dissemination [35, 36, 59, 72], and make a first step towards bringing similar benefits to UWB. We do so with a characterization on a small-scale testbed of the performance on concurrent transmissions across three par-ticular UWB dimensions: i) different pulse repetition frequencies (PRF), ii) different preamble codes, and iii) exact same RF configuration. The findings we set forth em-power protocol designers with knowledge of the conditions under which concurrent transmissions provide reliable results for ranging, but also communication, poten-tially inspiring a new wave of UWB protocols benefiting from them.

Beyond Concurrent Transmissions. We complete the thesis in Part III with three

additional contributions enabling large-scale operation (Ch4), further reducing con-sumption (Ch2), and lowering the installation complexity of anchor deployments. In Chapter 7, we propose Talla, a new TDoA localization system that seamlessly enables large-scale operation with multi-user support (Ch3) across large multi-hop UWB networks. Talla is based on a simple yet effective TDMA scheme that fol-lows a periodic schedule, allowing anchors to time synchronize with sub-ns level granularity and providing transmission opportunities for mobile nodes to track their position at the infrastructure. Our evaluation results in simulated and real-world setups show continuous and accurate localization across small and large operational areas. Further, the TDMA scheme proposed is also applicable to our schemes based on concurrent transmissions, laying the first stone to extend concurrent ranging and Chorus for large-scale operation.

Next, we look in Chapter 8 at how to further reduce the energy consumption in robotic applications while satisfying the specific requirements of mobile navigation. To this end, we fuse UWB TWR with odometry information—typically available on mobile robots—using an Unscented Kalman Filter [63] to build an uncertainty model of the robot state. We rely on the model to trigger UWB distance estimates only if and when needed to keep the uncertainty under the given requirements. This dynamically adapts the ranging rate without detriment to localization accuracy, reducing energy consumption and increasing scalability. Further, the proposed approach could be easily tailored to exploit concurrent ranging or Chorus, providing even greater re-ductions in consumption while scaling up the number of robots.

Lastly, we reduce the complexity to install and set up new anchor deployments in Chapter 9. Towards this goal, we build state-of-the-art algorithms to automatically compute the anchor positions based on ranging information obtained in situ. We evaluate our implementations in three real-world deployments, providing quantita-tive evidence of the performance of the algorithms and guidelines to facilitate the anchor network deployment of the many UWB-based location systems to come. Finally, we conclude in Chapter 10 by reflecting on the contributions and progress achieved during this thesis and with an outlook on follow up research inspired by the results described here.

(29)

Part I

Understanding Ultra-wideband

Localization

(30)

(31)

2

Ultra-wideband Ranging and

Localization: Principles and

State of the Art

Over the last decades, the need for precise indoor localization for countless appli-cations [5, 37, 50, 94, 96, 119, 153, 159] has led to a myriad of localization systems employing all sort of technologies, including optical [106, 142], ultrasonic [74, 75, 115], inertial [5], and radio-frequency (RF). Here, we focus on the latter. RF systems have become ubiquitous, arguably thanks to the pervasiveness of wireless communi-cations in every aspect of our daily life. Unfortunately, RF-based indoor localization systems have not yet received such adoption due to the very challenging and diverse requirements of the many potential applications [66].

Within RF localization systems, there are two main categories: i) device-based and ii) device-free. Device-based techniques aim to locate a target with an attached device (e.g., a UWB tag or a WiFi-enabled smartphone) that may actively or passively par-ticipate in the localization process. In contrast, device-free techniques aim to locate the target without the help of any attached device, exploiting RF phenomena such as absorptions, reflections, scattering, and diffractions to detect and locate the tar-get [1, 2, 3, 7]. Device-free techniques have seen much progress in recent years, yet they typically suffer to detect a static target or to distinguish between different target identities. In our case, we center our attention on device-based techniques, specifi-cally those based on ultra-wideband (UWB), which are more suitable to enable our motivating applications and satisfy their requirements, discussed in §2.3.

UWB communications have been originally used for military applications due to their very large bandwidth and interference resilience to mainstream narrowband radios. In 2002, the FCC approved the unlicensed use of UWB under strict power spectral masks, boosting a new wave of research from industry and academia.

(32)

Nonethe-Chapter 2. Ultra-wideband Ranging and Localization: Principles and State of the Art

less, this research mainly focused on high data rate communications, and remained largely based on theory and simulation, as most UWB radios available then were bulky, energy-hungry, and expensive, hindering the widespread adoption of UWB. In 2007, the IEEE 802.15.4a standard amendment included a UWB PHY layer based on impulse radio (IR-UWB), aimed at providing accurate ranging with low-power consumption.

In this chapter, we provide the necessary background on UWB radios and review the state-of-the-art UWB ranging and localization schemes. We start with a concise description of impulse radio in §2.1, which exploits very short duration pulses to achieve large bandwidths. Then, we introduce the UWB PHY layer based on im-pulse radio specified by the IEEE 802.15.4-2011 standard followed by the DW1000, a standard-compliant UWB transceiver that has taken by storm the indoor localization domain. We pay special attention to the key features of the standard and the DW1000 we use in our work such as CIR estimation.

After discussing motivating applications and their requirements, we switch our atten-tion to the main UWB ranging and localizaatten-tion techniques, categorized in ToA (§2.4) and TDoA (§2.5) approaches. The former uses distance estimates to compute posi-tions. The latter cannot directly measure distance and exploits, instead, the measured distance difference across a set of anchors for localization. We focus on state-of-the-art techniques commonly used by systems in the literature and give intuition about potential errors and how to address them.

Finally, we provide a qualitative comparison in §2.6 matching the discussed ToA and TDoA techniques with the application requirements in §2.3, and take the opportunity to put into perspective the novel schemes we propose in the following chapters.

2.1 Ultra-wideband and the IEEE 802.15.4a PHY Layer

According to the FCC, UWB signals are characterized by a bandwidth ≥ 500 MHz or a fractional bandwidth ≥20% during transmission. To achieve such a large band-width, UWB systems based on impulse radio (IR-UWB) use very narrow pulses in time (_≤2 ns), as illustrated in Figure 2.1, that translate to a large bandwidth.

0 0.2 0.4 0.6 0.8 1 Time [ns] 0

1

Amplitude

Figure 2.1: UWB pulse. Impulse Radio. IR-UWB spreads the signal energy

across a very large bandwidth by transmitting data through a time-hopping sequence of ns-level pulses [146]. This reduces the power spectral density (PSD), the in-terference produced to other wireless technologies, and the impact of multipath components (MPC). Further, it enhances the capability of UWB signals to propa-gate through obstacles and walls [154] and simplifies

transceiver design. The large bandwidth also provides excellent time resolution, en-abling UWB receivers to precisely estimate the time of arrival (ToA) of a signal and distinguish the direct path from multipath components (MPC), especially by mea-suring and analyzing the channel impulse response (CIR). Time-hopping codes [148] 10

(33)

2.1. Ultra-wideband and the IEEE 802.15.4a PHY Layer SHR Preamble SFD PHR and payload (BPM-BPSK) 0 1 Data symbol

Preamble symbol Pulse train (burst)

Figure 2.2: UWB frame: the SHR is encoded in single pulses, while the data part

exploits BPM-BPSK modulation. Preamble codes determine the preamble symbol se-quence and the time-hopping code (arrows) for data transmission. Image by Davide Vecchia [140].

can be used to provide multiple access to the medium. These features make IR-UWB ideal for ranging and localization and also for low-power communication.

IEEE 802.15.4 UWB PHY Layer. The IEEE 802.15.4-2011 standard [57] specifies an

UWB PHY layer based on impulse radio. An UWB frame (Figure 2.2) is composed of i) a synchronization header (SHR) and ii) a data portion. The SHR is encoded in single pulses and includes a preamble for synchronization and the start frame delim-iter (SFD), which delimits the end of the SHR and the beginning of the data portion. Instead, the data portion exploits a combination of burst position modulation (BPM) and binary phase-shift keying (BPSK), and includes a physical header (PHR) and the data payload. The duration of the preamble is configurable and depends on the number of repetitions of a predefined symbol. A preamble symbol (Figure 2.2) consists of a sequence of elements drawn from a ternary alphabet {+1, 0,−1}, i.e., positive, absent, and negative pulse. This sequence is determined by the preamble code. The standard defines preamble codes of 31 and 127 elements, which are then interleaved with zeros according to a spreading factor. This yields a (mean) pulse repetition frequency (PRF) of 16 MHz or 64 MHz, respectively; hereafter PRF16 and PRF64 for readability. Preamble codes also define the pseudo-random sequence used for time-hopping in the transmission of the data part. The standard defines a complex channel as the combination ofhfrequency, codeiand provides (at least) two codes per channel and PRF combination. Preamble codes were thus envisaged as a mechanism to provide multiple non-interfering access to the wireless medium. According to DecaWave [81], however, frames that overlap in different complex channels may still interfere with each other unless their codes have different PRFs. We analyze these aspects in Chapter 6. The highest frequency at which a compliant device shall emit pulses is 499.2 MHz (fundamental frequency), which defines the standard chip dura-tion of≈2 ns. Finally, the standard also specifies a couple of two-way ranging (TWR) schemes (SS-TWR and DS-TWR) to measure the distance between devices. We study these schemes in §2.4.1–§2.4.2. All the timestamps required for ranging are measured in a packet at the ranging marker (RMARKER), which marks the first pulse of the PHR after the SFD.

(34)

Chapter 2. Ultra-wideband Ranging and Localization: Principles and State of the Art

Channel Impulse Response (CIR). The perfect periodic autocorrelation of the

pream-ble code sequence enapream-bles coherent receivers to determine the CIR [88], which pro-vides information about the multipath propagation characteristics of the wireless channel between a transmitter and a receiver. The CIR allows UWB radios to dis-tinguish the signal’s leading edge (first path) from MPC and accurately estimate the ToA of the signal at the RMARKER. Throughout this thesis, we exploit CIR infor-mation for ranging and localization as well as to analyze the interference created by concurrent transmissions under different RF configurations.

RX Errors. The PHR and data payload employ several mechanisms to detect and

correct errors, enhancing the robustness of the PHY layer. The PHR includes a 6-bit parity check SECDED (single error correct, double error detect) field. The data payload, instead, employs a Reed-Solomon (RS) encoder that appends 48 parity bits every 330b of data. Hence, uncorrectable bit errors in the PHR or the data payload trigger SECDED and RS errors, respectively. Moreover, UWB radios can also trigger an SFD timeout when a preamble is detected and the SFD is not received within the expected SHR duration. In Chapter 6, we analyze the appearance of these RX errors to understand the reasons behind packet loss.

2.2 The DecaWave DW1000

The DecaWave DW1000 [86] is a commercially available low-power low-cost UWB transceiver compliant to the IEEE 802-15.4-2011 standard. The DW1000 supports both PRF16 and PRF64, frequency channels {1, 2, 3, 4}in the low band and {5, 7}in the high band, and three data rates 110 kbps, 850 kbps, and 6.8 Mbps. Channels {4, 7}have a larger 900 MHz bandwidth, while the others are limited to 499.2 MHz. We introduce next some key aspects and features of the DW1000 that we use through-out this thesis to build our newly proposed techniques as well as the conventional techniques we compare against.

CIR Estimation. The DW1000 measures the CIR upon preamble reception with a

sampling period Ts=1.0016 ns. The CIR is stored in a large internal buffer of 4096B accessible by the firmware developer. The time span of the CIR is the duration of a preamble symbol: 992 samples for a 16 MHz pulse repetition frequency (PRF) or 1016 for a 64 MHz PRF. Each sample is a complex number ak+jbk whose real and imaginary parts are 16-bit signed integers. The amplitude Ak and phase θk at each time delay t_k is A_k = qa2_k+b2_k and θ_k = arctanbk_ak. Even when reception (RX) errors do occur, the DW1000 measures the CIR. Therefore, we can extract timing information from the CIR even if we are unable to successfully decode the response packet payload.

RX Timestamp. The DW1000 measures the received signal timestamp (RMARKER)

marking the end of the preamble and the beginning of the PHY header (PHR). This timestamp is measured in radio units (≈15.65 ps). The DW1000 first makes a coarse timestamp estimation and then adjusts it based on the RX antenna delay and esti-mated first path in the CIR according to an internal leading edge detection (LDE) algorithm. The CIR index that the LDE algorithm has determined to be the first or di-12

(35)

2.3. Applications Requirements

Table 2.1: DW1000 current consumption comparison with the TI CC2650 BLE

SoC [58] and the Intel 5300 WiFi card [20]. Note that consumption depends on radio configuration, the CC2650 includes a 32-bit ARM Cortex-M3 processor and the 5300 can support multiple antennas.

DW1000 TI CC2650 [58] Intel 5300 [20] State 802.15.4a BLE 4.2 & 802.15.4 802.11 a/b/g/n

Deep Sleep 50 nA 100–150 nA N/A

Sleep 1 µA 1 µA 30.3 mA

Idle 12–18 mA 550 µA 248 mA

TX 35–85 mA 6.1–9.1 mA 387–636 mA

RX 57–126 mA 5.9–6.1 mA 248–484 mA

rect path (FP INDEX) is stored together with the RX timestamp in the RX TIME register. LDE detects the direct path as the first sampled amplitude that goes over a dynamic threshold based on i) the noise standard deviation σn and ii) the noise peak value. Similar to the CIR, the RX signal timestamp is measured despite RX errors, unless there is a rare PHR error [89, p. 97].

Delayed Transmissions. The DW1000 provides the capability to schedule delayed

transmissions at a specified timestamp in the future [89, p. 20]. This timestamp corresponds to the time at which the RMARKER is transmitted. To this end, the DW1000 internally computes the start time at which to start sending the preamble, considering as well the transmission antenna delay [84], so that the RMARKER is transmitted at the specified time. This makes the transmission timestamp predictable, which is key for ranging as we discuss in §2.4–§2.5.

DW1000 Power Consumption. A key aspect of the DW1000 is its low-power

con-sumption w.r.t. previous UWB transceivers (e.g., [27]). Table 2.1 compares the current consumption of the DW1000 with other commonly-used technologies (BLE and WiFi) for localization. The DW1000 consumes significantly less than the Intel 5300 [20], which provides channel state information. However, it consumes considerably more than low-power widespread technologies such as BLE. Hence, to operate battery-operated UWB devices and provide long battery lifetime it is essential to reduce the necessary radio activity to meet the ranging or localization rate required by the applications.

2.3 Applications Requirements

Our work on UWB localization started with the ongoing PLaNS project aiming to provide navigation support for one or more rovers to explore harsh environments in general and the Mars surface in particular [44, 60, 138]. To this end, as a rover moves slowly in Mars, it communicates and performs ranging with a network of battery-operated anchors deployed across a large operational area, either computing its own position locally or offloading the computation to another—more powerful—device, i.e., the lander. Hence, PLaNS requires energy-efficient operation to cope with the

(36)

Chapter 2. Ultra-wideband Ranging and Localization: Principles and State of the Art

tight energy budget of the envisaged devices, and accurate ranging and localization to successfully achieve the goals of the exploration mission.

Our projects and interests later significantly expanded towards applications such as i) autonomous robot and drone navigation for home and industrial use-cases [94, 96, 119] ii) proxemics [46, 53] and wildlife monitoring [112] iii) asset tracking in indus-trial warehouses [37, 104] iv) supermarket client and museum visitor tracking [153, 159] and v) personal navigation in large exhibitions, shopping centers, or museums. Each application comes with a completely different set goals and requirements and, even within the same type of applications, requirements may vary significantly, e.g., from one warehouse to another. We can summarize the requirements of the vast application space, along the following dimensions:

R1. Ranging vs. Positioning. Depending on the application goals, the distance

be-tween targets or their absolute position may need to be measured. For instance, proxemics or wildlife monitoring may not require positioning, rather energy-efficient distance estimation (ranging) from one subject to another at a sufficient rate to capture the nature of interactions. In these applications, there may not even be an anchor infrastructure for positioning. Asset tracking or navigation, indeed, requires positioning within a reference coordinate system.

R2. Accuracy. The ranging and location accuracy required varies significantly from

one application to another, and even from one target environment to another. For example, to guide the navigation of a robot indoors or asset tracking in a manufacturing plant decimeter- or even cm-level localization accuracy is key for the success of the operation. In contrast, for user navigation or wildlife monitoring a meter-level error may be sufficient.

R3. Update rate. Many assets are either slow-moving or remain static most of the

time [107]. Hence, to track them there is no need to support high update rates. In contrast, to support the navigation of a fast robot or drone an update rate ≥ 10 Hz per device is required. Similarly, to study customer behavior in su-permarkets the update rate needs to be sufficient to capture typical mobility patterns.

R4. Scalability (#Users). The number of users supported is directly related to the

lo-calization update rate above. However, adding multi-user support also requires additional mechanisms for medium access and the need for time synchroniza-tion to schedule the correct operasynchroniza-tion of users and anchors. Applicasynchroniza-tions aiming to locate large number of assets or provide navigation support need to be highly scalable and reduce the necessary radio activity per location estimate.

R5. Energy-efficiency. Battery-operated devices require energy-efficient operation

to extend battery life. This is key, e.g., to support the many mobile tags to be located in tracking applications and avoid the inconvenience and costs to frequently replace batteries.

R6. Large-scale Operation. To provide real value and enhance the operational

ef-ficiency of hospitals, supermarkets, or warehouses, localization systems need to provide location information across large operational areas. Other applica-tions, however, may only require localization within a small confined area, e.g., a robotic lawnmower or vacuum cleaner only needs to operate within the limits 14