Indoor Positioning in Large Environments: Ultrasonic and UWB Technologies David Gualda1, José Manuel Villadangos1, Jesús Ureña1, Antonio Jiménez2, Fernando Seco2 and Álvaro Hernández1 1 Department of Electronics, University of Alcalá, Spain 2 Centre for Automation and Robotics (CAR), Spanish Council for Scientific Research (CSIC-UPM) 28500 Arganda del Rey, Spain jesus.urena@uah.es, antonio.jimenez@csic.es Abstract. This work describes and compares two positioning systems, based respectively on ultrasonic (US) and on ultra-wide band radio (UWB) technologies, which can be used in large indoor areas, such as medium-sized warehouses. The ultrasonic positioning system involved is based on the measurement of times-of-arrival for the ultrasonic signals, emitted from a set of beacons at known positions to the mobile receiver. In this setup, time synchronization is provided by an infrared link, and spherical trilat- eration is used to estimate the mobile node´s position. The UWB system is a commercial product by Decawave, and it is based on the measurement of round-trip times between emitters and receivers. Both positioning systems are evaluated in an uncluttered warehouse environment (24x14 m), where there is line-of-sight from emitters to receiver at most locations. Emitters are placed on the walls, covering most of the evaluation area with suitable geometric conditions. The performed evaluation shows that both systems achieve an accuracy even below decimeters, and, in a certain way, they can be considered complementary, since they are affected by different propagation phenomena and types of noise. Even though the UWB technology is becoming increasingly popular, the lower cost of ultrasonic systems, as well as the confinement of signals in rooms and the corresponding high level of security related to the positioning process, can also make it attractive. Keywords: Indoor Positioning, Ultrasounds, UWB, Trilateration, Navigation. 1 Introduction In recent years there has been a growing demand for proven technologies that provide location-based ser- vices to people, mobile robots (MRs) or other devices across large indoor areas of buildings and surround- ing outdoor spaces. For example, location-aware applications (e.g., navigation aids), ubiquitous computing, or augmented reality require positioning data. In contrast to the high degree of implementation of Global Navigation Satellite Systems (GNSS) outdoors, there is still no consolidated technology at the same level for indoor environments. Positioning technologies are usually classified according to the accuracy and coverage area that can be achieved in certain applications [1]. The main technologies are: optical, mechanical, magnetics, acoustic and radio frequency. An overview of the coverage and accuracy that can be achieved is shown in Fig. 1 (based on R. Mautz’s one in [2]). A booming sector today is e-commerce, which has put warehouses under great pressure to reduce costs, human resources and delivery times. Warehouse managers are often interested in optimizing the picking process as workers walk in the warehouse fulfilling orders. For that purpose, it is necessary to have available real-time location data about mobile assets, such as working staff, order trays and forklifts (or other vehi- cles). About 77% of industrial warehouses plan to use real-time location system (RTLS) technology by 2020, but the adoption of current technologies, such as long-range radio frequency identification (RFID) for real-time inventory, mobile devices and robotics, has been compromised by the inaccuracy, high cost and complexity of their use and maintenance [3]. Two location technologies with the requested positioning accuracy (centimeter/decimeter) and suitable to be deployed in large environments are those based on ultrasounds (US) and on ultra-wide band radio (UWB). Both technologies are already highlighted in Fig. 1, where their coverage and accuracy ranges can be observed. In both cases, these are indoor positioning solutions based on beacons, where it is necessary their installation, usually as transmitters, whereas the reception is carried out by a receiver on board the object or user, whose position should be estimated. Ultrasonic systems can reach accuracies even close to one centimeter under conditions of suitable signal-to-noise ratio, calm air, and using transducers with enough bandwidth; but at long distances, typical in warehouses or large indoor spaces, these conditions 2 easily degrade [1]. In addition, the absorption by air reduces the useful propagation range of ultrasonic signals to a few tens of meters, so the coverage of US signals is limited by the number of beacons installed and the hurdles in the line-of-sight (LOS) caused by obstacles in the environment. Coverage Rural 1 km Outdoors Mechanical Inertial navigation systems Urban 100 m Acoustic Magnetic WLAN 10 m Indoors Room Sound Optical Magnetic UWB system Ultrasound RFID RF Sub-room 1 m Infrared Cameras 0.1 mm 1 mm 1 cm 1 dm 1m 10 m 100 m Accuracy Fig. 1. Overview of the accuracy for indoor positioning and outdoor transition technology (ultrasounds and RF-UWB based technologies highlighted). Image based on R. Mautz’s one in [2]. Generally speaking, UWB positioning systems are less accurate than ultrasonic ones in reduced areas (about 0.2m for UWB and centimetric errors for US), but they are complementary since they have greater coverage and range capacity (more than 100 m in optimal LOS conditions). UWB emissions can partially penetrate walls and obstacles, and they are more robust to multipath effect due to their large bandwidth. However, it remains a challenge to use UWB indoors with enough accuracy and coverage. The accuracy of UWB dis- tance measurement and the maximum range in practice significantly degrade when operating indoors, es- pecially due to the NLOS (Non-Line of Sight) effect and the influence from metal obstacles and equipment. Therefore, this work carries out a comparison about positioning results between these technologies (UWB and US), evaluating them in an uncluttered warehouse environment (336 m2) and in different cir- cumstances and configurations: receivers fixed at several positions; estimation of a mobile robot position that follows a black line; and estimation of a person walking that follows a known path. These experimental tests provide the possibility of determining the behavior of both technologies under several conditions re- lated to the movement of receivers and NLOS effect. The rest of the document has been organized as fol- lows: Section II describes the involved ultrasonic system; similarly, Section III details the UWB-based system; Section IV shows the comparative results obtained in a real environment; and, finally, conclusions are discussed in Section V. 2 Global Overview of the Ultrasonic LPS On the ultrasounds side, all the analysis and experiments described hereinafter are based on the LOCATE- US prototype, developed by the GEINTRA-US/RF research group from the University of Alcalá [4] [5]. This system mainly consists of two modules. On one hand, there is a unit of beacons (or emitters), in charge of transmitting certain ultrasonic signals into the environment; and, on the other hand, the system provides a portable ultrasonic receiver capable of acquiring the incoming signal and process it, in order to search for the corresponding ultrasonic transmissions. The unit of beacons is actually formed by five transducers, installed in a certain geometrical distribution, so they can provide a common coverage area. All the five transducers have a signal FPGA-based (Field- Programmable Gate Array) digital control architecture, which means all of them are perfectly synchronized from the point of view of the ultrasonic transmissions. It is worth noting that, when the system is deployed in large environments, it is necessary to install several units of beacons, so most of the area can be suitably covered. In these cases, all the ultrasonic transmissions, even those coming from different units of beacons, can be synchronized by using an infrared link, which is fired by a master unit and, consequently, followed by all the other slave units. This same IR link can also be involved at the receiver in order to synchronize the acquisition of the incoming signals. This feature is key, since this synchronism allows to choose between 3 spherical and hyperbolic positioning. When the synchronism link is used, it is possible to determine times- of-Arrival (TOA) between the beacons and the receiver, which leads to the implementation of spherical positioning algorithms. Otherwise, if the synchronism link is not available, then time-differences-of-arrival (TDOA) can be measured for hyperbolic algorithms. The Prowave 238ST160 has been used as emitter in the ultrasonic system. This device provides an ap- proximated bandwidth of 18 kHz and a central frequency around 40 kHz. Furthermore, the unit also in- cludes an amplifier (based on the OPA552), as well as a digital-analog converter (DAC). Note that the five existing DACs are controlled from a single FPGA device available in the digital control module. This mod- ule also allows to set up certain parameters in each ultrasonic transmission, such as the modulation scheme, the sequences used in the coding, or the carrier and sampling frequencies, thus providing a high configura- bility to the system. The architecture described so far presents a significant drawback: the five beacons inside a unit are actually placed quite close one to each other, thus constraining the final coverage area. Because of that, the unit of beacons have been recently split into modules with only one beacon. This implies that every bea- con/transmitter requires its own digital control system, but it allows to considerably separate the five bea- cons, previously in one single unit, increasing the flexibility significantly, and enhancing the final perfor- mance of the positioning system in large environments without requiring more beacons to be installed. It is worth noting that the features of the proposal are still the same, since the IR link is able to synchronize all the transmissions carried out in the environment. This IR synchronization now also allows the beacons to be separated effectively and flexibly, so that their location can be better adapted to the needs of the envi- ronment, with the consequent simplification of hardware and reduction of costs. Fig. 2 shows the block diagram of the recent ultrasonic beacon developed in the LOCATE-US system. Since the new digital control system only is in charge of one beacon, it has been reduced and based on a single Cortex M-3 microcontroller, which detects the synchronism signal from an IR receiver, and provides the coded transmission that identifies that beacon, through the internal DAC and an amplifier. Note that the ultrasonic transducer remains the same as before, the 328ST160. It is convenient to highlight that, herein- after, when considering only spherical positioning, it will be necessary to have available only three beacons to estimate the receiver’s position. IR receiver (TSOP7000) Cortex M-3 Synchronism microcontroller (LPC1768) US transducer (328ST160) 255-bit Kasami sequences DAC BPSK modulated 8 bits (flash memory) fS=12·fc fc=500kHz Timer interrupts Fig. 2. General block diagram of the recent ultrasonic beacon with infrared synchronization (left). View of the beacon prototype (right). With regard to the receiver, it is based on a previous version already described in [4], where the IR link has been recently added. Fig. 3 depicts its block diagram. As can be observed, it consists of a low-cost STM32F103 microcontroller, as well as of a MEMS (microelectromechanical) microphone, a high-band- width amplifier, and a configurable high-pass filter (SPU0414HR5H-S). Finally, a programmable gain am- plifier allows the received signal level to be dynamically adjusted to the input range of the A/D converter (ADC). Furthermore, the receiver also has an USB acquisition module (also capable of storing the samples on an SD card autonomously). This module is capable of acquiring a 10000 samples data window at a sampling rate of 100 kHz, and transferring it through the USB link (or storing it on the SD card). This acquisition length is fixed afterwards to ensure that at least one complete transmission from all the beacons is available in the buffer, according to the features of the ultrasonic transmissions (types of sequences, length, modulation scheme, etc.). 4 Summing it up, for the comparison purpose involved here, it is considered that a set of independent ultrasonic beacons are placed at any point in the environment under study, providing simultaneous trans- missions synchronized by means of the IR link. Such transmissions are detected by any receiver in the environment, also in a synchronized way; and, after the corresponding signal processing to search every encoded transmission carried out by the beacons, it is possible to determine the TOAs, by applying corre- lation techniques and match filtering. These TOAs are used by the spherical positioning algorithm to esti- mate the receiver’s position. IR receiver (TSOP7000) Micro-SD card Synchronism SPI link MEMS microphone (SPU0414HR5H-SB) ADC RAM DMA 8 bits (buffer) fS=100kHz USB connection Microcontroller USB inteface SMT32F103 Fig. 3. Block diagram of the proposed ultrasonic receiver with infrared synchronism (left). General view of the receiver prototype (right). 3 Description of the UWB System The UWB positioning system operates in a conceptually similar way to the US system just presented, i.e., by measuring distances between several individual nodes and estimating the position of a mobile node. The UWB system presents, in theory, the advantage that it can operate at longer distances (more range), have a more omnidirectional emission, and be able to distinguish or better resolve the ranges that arrive by direct path (LOS) from those that arrive secondarily by bounces on objects, or another type of multipath [6,7,8]. UWB positioning systems, therefore, have the potential to be used as reference systems, to evaluate other positioning systems with lower robustness or coverage, such as ultrasonic LPSs. Nevertheless, in practice, it is necessary to be aware of the limitations of UWB technology. In past works, different UWB positioning systems have been studied and compared, to analyze their performance in office environments [9] and in industrial environments [10]. They have also been applied to object finding solutions [11]. To carry out the positioning performance comparison described in this work, a commercial equipment from Decawave (TREK1000 development kit) has been used. This equipment has been chosen because it provides the best performance compared to other commercial solutions, as shown in [9, 10, 11]. The UWB equipment that has been deployed consists of eight nodes: six configured as nodes at fixed locations, an- other is mobile, and the last one is connected by USB to a PC in order to record all ranging measurements. Each TREK1000 development kit contains only four UWB nodes, so two of these kits have been combined to create the final setup. Each node of the development kit, called EVB1000 (see Fig. 4), contains a DW1000 UWB chip, an STM32F105 ARM Cortex M3 processor and an omnidirectional antenna. The nodes are able to connect to each other automatically and estimate the distance between nodes. Decawave's DW1000 modules are com- patible with the IEEE 802.15.4-2011 UltraWideBand (UWB) standard. They are able to measure distances with an accuracy of ±10cm using the Round Trip Time (RTT) method. The maximum measuring range is 300 m, but this is only possible under ideal conditions with no obstacles and with the antennas placed high enough above the ground to avoid destructive interference. Each UWB node can be configured as an anchor or mobile node by changing the DIP-switches available on the PCB card. Using these switches, it is also possible to select between two channels (2 and 5), respec- tively, with central frequencies (4 GHz and 6.48 GHz), and two data rates (110 kbps and 6.8 Mbps). The default configuration settings are: 4 GHz as central frequency and 110 kbps of data rate. This rate is the recommended value for the maximum measurement distance, and it is the one considered hereinafter. 5 Fig. 4. Decawave EVB1000 individual module, used for both fixed beacons and mobile nodes. According to the manufacturer, an average update rate of 3.5 Hz is expected for a moving object. The update rate decreases as the number of nodes increases, due to the time multiplexing scheme adopted (TDMA). The experimental update rate obtained is 3.3 Hz. The set of measured distances between the different nodes is transmitted to the node connected to a PC by USB, which collects and interprets them. Some delays about a few tenths of a second may exist between different pairs of nodes, but they are not significant for the type of static tests performed. The integration of these distances in the estimation of the position is done in a quite standard way by means of a Kalman filter, in the same way as the measured distances of the ultrasonic LPS. The state vector is given by the 3D position and speed shown in equation (1). 𝐗 = [𝑥 𝑦 𝑧 𝑣𝑥 𝑣𝑦 𝑣𝑧 ]𝑇 (1) The process and measure noises are Gaussian with standard deviation values of 𝜎𝑣 = 0.02 𝑚/𝑠 2 and 𝜎𝑟 = 0.2 𝑚, respectively. 4 Experimental Results Some experimental tests have been carried out in a 336 m2 warehouse, whose description is detailed in Fig. 5. As can be observed, there are six UWB nodes (T0-T6, purple squares), as well as six yellow stars to indicate the approximated positions of other six ultrasonic beacons. Nertheless, during the results shown hereinafter, only the three beacons denoted with a red circle are actually installed and working. Available US beacons Fig. 5. Map of the indoor environment where experimental tests have been carried out. Firstly, measurements have been carried out without any movement at certain known points with a fixed height of 1.5 m and at the center of the environment, where the ultrasonic and UWB coverages are high. 6 Fig. 6.a) shows the US and UWB position estimates in 2D for a known mobile node height, obtained for a hundred measurements at each point, solving the non-linear equation system by using a Gauss newton and Taylor iteration for US and UWB, respectively. It is possible to check that estimates from both technologies are very close to the real points, with a low uncertainty represented by the corresponding ellipses that cover 95% of estimates. On the other hand, Fig. 6.b) plots a Cumulative Distribution Function (CDF) for the Euclidean distance error between all the estimates and the actual point. From these results, it can be derived that the distance error is less than 20 cm in the 80% of cases for both systems, yet several centimeters better in the case of UWB with six nodes and also considering only three nodes (T2, T3 and T4), the same number of nodes than US. Note that, even in the case of only using three nodes for the UWB system in this case the results are better than with US, mainly due to the better distribution that can be achieved with UWB as the directionality of US imposes more constraints. b) a) Fig. 6. a) Experimental position estimates for both US and UWB (using six and three nodes for the last one); b) CDF for the Euclidean distance error for the same estimates. Thereafter, another experiment has been carried out with a line-follower robot, which the ultrasonic recep- tion card and the UWB receiver module were incorporated to, as can be observed in Fig. 7. During the test, the robot traveled approximately 7.2 m along a black line located in the center of the environment. US receiver UWB receiver Fig. 7. Line-follower robot with US and UWB reception cards used during experimental tests. Fig. 8.a) shows the real trajectory followed by the robot (green line), as well as the trajectories estimated with the ultrasonic LPS (blue line) and UWB (red and magenta lines, for six and three nodes respectively). An Extended Kalman Filter (EKF) was used to estimate the positions for both technologies, by using the measurements of distances obtained from the transmitters to the receivers, considering a mobile height of 10 cm for the robot. It can be verified that both estimates, US and UWB for six and three nodes, are very close to the real trajectory, being still possible to appreciate a better result for UWB in both cases. On the 7 other hand, Fig. 8.b) shows a CDF for the Euclidean distance error existing between the estimates and the closest point of the real trajectory, where in the 80% of cases the position error using the ultrasonic posi- tioning system is 20 cm maximum, whereas, for the same percentage of cases and the UWB system with six nodes, the error is lower than 8 cm. Moreover, if the number of UWB nodes is three, the error increases to a maximum of 12 cm. a) b) Fig. 8. a) Real trajectory followed by the mobile robot and the estimated trajectories with the US and UWB LPSs; b) CDF for the Euclidean distance error of the positions in that trajectory. An additional test involved a person walking along a certain path, carrying in their hand US and UWB receivers. The approximated trajectory followed by the person, as well as the corresponding estimated ones from US and UWB, are shown in Fig. 9.a). Larger errors for both estimates (US and UWB) are observed qualitatively, in comparison with the test carried out with the robot. This is due to the fact that the receivers do not present a direct LOS with all the emitters at certain points, as a consequence of the interposition of the person who carries the receivers, thus implying higher uncertainty. In Fig. 9.b) the magnitude of these errors can be evaluated in the CDF for the distance error. Concerning the ultrasonic LPS, this error is less than 0.65 m in 80% of the cases, whereas it is the half (0.35 m) for the UWB system with six nodes. Nevertheless, if the number of UWB nodes is equal to the US system, the error in the 80% of cases increases to more than 0.50 m. Also for both, US and UWB (3 nodes), the CDF representation follows a similar shape. Nonetheless, the UWB system still performs better, since it is important to remark that NLOS situ- ations may be more critical for the US system. a) b) Fig. 9. a) Approximated walking trajectory and the estimated ones from the US and UWB systems; b) CDF for the Euclidean distance error of the position estimates related to the walked trajectory. 8 5 Conclusions This work has presented two indoor positioning systems, capable of being deployed in large indoor envi- ronments, or even in transition to outdoors, already with GNSS coverage. On one hand, the ultrasonic sys- tem is an ad hoc development, adapted for spherical trilateration by means of an infrared synchronization. On the other hand, the other positioning system is a commercial DECAWAVE UWB system. Both systems have been installed in a 24 x 14 m building, covered by six UWB beacons and, partially, by three ultrasonic beacons. Positioning results, both at fixed points and following the trajectories of a mobile robot and a person, have yielded results in the range of decimeters, somewhat better in the UWB cases than in the ultrasonic one in this case of large spaces (note that in reduced spaces of few meters US systems report errors in the range of centimeters). It is worth noting that when the number of US and UWB nodes are the same and the test are performed in movement, the errors are similar for both systems. More test will be conducted in the future with a higher number of ultrasonic beacons and new arrays of receivers. Both systems can be complementary, in range and type of signals and interfering effects (which affects the availability in a different way). This is particularly interesting for certain applications, such as ware- houses used in e-commerce logistics, where it is necessary to estimate the position of people and autono- mous vehicles to achieve the degree of automation often required by this sector. Acknowledgment. This work has been possible thanks to the University of Alcalá (project UAH-AE2017- 4), Junta de Comunidades de Castilla La-Mancha (FrailCheck project, SBPLY/17/180501/000392), and the Spanish Ministry of Science, Innovation and Universities (RTI2018-095168-B, TEC2015-64835-C3-2-R, TIN2015-71564-C4-1-R and TEC2017-90808-REDT). References 1. Ureña J., Hernández, A., García, J. J., Villadangos, J. M., Pérez, M. C., Gualda, D., Álvarez, F., Aguilera, T.: Acoustic Local Positioning with Encoded Emission Beacons. Proceedings of the IEEE 106(6), 1042–1062 (2018). 2. Mautz, R.: Overview of current indoor positioning systems. Geodesy and Cartography, 35(1), 18–22 (2009). 3. Zebra Technologies, http://seemore.zebra.com/buidingthesmarterwarehouse, last accessed 2019/05/03. 4. Hernandez, A., Garcia, E., Gualda, D., Villadangos, J. M., Nombela, F., Ureña, J.: FPGA-Based Architecture for Managing Ultrasonic Beacons in a Local Positioning System. IEEE Transactions on Instrumentation and Meas- urement 66(8), 1954–1964 (2017). 5. Hernandez, A., Urena, J., Villadangos, J. M., Mannay, K.: SoC Architecture for an Ultrasonic Receiver applied to Local Positioning Systems. In: Proceedings of the XXXIII Conference on Design of Circuits and Integrated Sys- tems (DCIS), pp. 1–5, Lyon, France (2018). 6. Tiemann, J., Schweikowski, F., Wietfeld, C.: Design of an UWB indoor-positioning system for UAV navigation in GNSS-denied environments. In: Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), pp. 1–7, Alberta, Canada (2015). 7. Guvenc, I., Chong, C. C., Watanabe, F.: NLOS Identification and Mitigation for UWB Localization Systems. In: Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), pp. 1573–1578, Hong Kong (2007). 8. Zwirello, L., Schipper, T., Jalilvand, M., Zwick, T.: Realization Limits of Impulse-Based Localization System for Large-Scale Indoor Applications. IEEE Transactions on Instrumentation and Measurement (TIM) 64(1), 39–51 (2015). 9. Jimenez, A. R., Seco, F.: Comparing Decawave and Bespoon UWB location systems: Indoor/outdoor performance analysis. In: Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), pp. 1–8, Alcalá de Henares, Spain (2016). 10. Jimenez Ruiz, A. R., Seco Granja, F.: Comparing Ubisense, BeSpoon, and DecaWave UWB Location Systems: Indoor Performance Analysis. IEEE Transactions on Instrumentation and Measurement (TIM) 66(8), 2106–2117 (2017). 11. Jimenez, A. R., Seco, F.: Finding objects using UWB or BLE localization technology: A museum-like use case. In: Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), pp. 1–8, Sapporo (2017).