Titre de la dissertation: « High density and large scale Ultra Wideband indoor positioning infrastructure ».

Promoteur de thèse: Monsieur Bruno QUOITIN

Résumé de la dissertation: This thesis focuses on indoor positioning systems based on the Ultra Wideband (UWB) radio communication technology, that is having a bandwidth wider than 500 MHz. Initially proposed for military applications, then for high capacity networks, UWB has been standardized in 2007 for low-power and low-rate wireless sensor networks under the IEEE 802.15.4a standard. In this application domain, the standard UWB physical layer (PHY) and Medium Access Control (MAC) layer allow communications between devices as well as accurate time-of-arrival estimation. The latter forms the basis for localization systems be it of the ranging or Time Difference of Arrival (TDoA) types. Precise indoor localization can be used in a plethora of applications such as safety (geofencing, proximity alert), manufacturing (object tracking, quality assessment) and entertainment (audio guide, positioning in laser game).At the beginning of this thesis, UWB-based Indoor Positioning System (IPS) were still in their infancy and their scale was limited. Off-the-shelf systems could only accommodate a few anchors and mobile devices or they would rely on burdensome cable deployment for the stringent clock synchronization required by TDoA protocols. Since then, the awareness of UWB among industry and scientists has grown, spawning a lot of research. Consortiums have emerged with the goal of improving the standard (UWB alliance) and interoperability (FiRa consortium) from the physical to the application layers. So far, these consortiums have led to the introduction of a new generation of UWB transceivers that are interoperable and now integrated in high-end smartphones or wireless key fobs.The main objective of this thesis is to build UWB-based IPS that would scale to a large number of anchors, covering large areas such as industry halls or museums, accommodate large tag densities, and at the same time allow for high positioning rates. Some of these objectives are contradictory, so the thesis also explores the trade-offs among them. The thesis brings three contributions. First, to allow researchers to design their custom ranging protocols and MAC layers, we provide the first integration for UWB into a widely accepted Real-Time Operating System (RTOS) used for research on low-cost embedded systems, namely Contiki-OS. We also design a prototype platform based on  MSP430 and ARM micro-controllers combined with a DWM1000, an off-the-shelf transceiver module from Decawave. Based on this platform and RTOS integration we provide a preliminary performance assessment of achievable bitrate, packet delivery ratio and discuss some of the systems limitations such as limited SPI bus speed.Second, we propose UWB-TSCH a new MAC layer derived from the Time Slotted Channel Hopping (TSCH) mode of operation of the IEEE 802.15.4 MAC originally designed for narrowband PHY. Our proposal allows to obtain more deterministic channel access than with ALOHA used in most UWB solutions at that time. Indeed, TSCH arranges communications in separate time slots, avoiding collisions. At the same time, it allows devices to save energy by going to sleep during their inactive time slots. Moreover, several communications can take place within the same time slot on different, non-overlapping channels or using orthogonal preamble codes. We designed two types of time slots, respectively for carrying data plus acknowledgement frames and for performing multiple messages exchanges, as required by Double-Sided Two-Way Ranging (DS-TWR) protocols. We implemented UWB-TSCH on a variation of our prototype platform to allow its experimental characterization in a testbed. More specifically, we quantified the reliability of concurrent communications and the reliability of the global temporal synchronization required by TSCH with a UWB PHY.In our third and final step, we design a centralized scheduling algorithm to organize the communications in a UWB-TSCH IPS. Our algorithm is derived from Traffic-Aware Scheduling Algorithm (TASA) a greedy scheduling heuristic for collect traffic. It aims at minimizing the slotframe length by maximizing frequency re-use thanks to a graph coloring heuristic. To adapt TASA to our context, we divide the target network in cells which are groups of anchors responsible for performing ranging measurements within a certain area. Mobile tags are then assigned to a cell through a dynamic registration process. This approach makes it possible to avoid re-scheduling when tags move from cell to cell. In addition, to the contrary of TASA, we support two types of time slots : ranging exchanges and data forwarding. As a result, our network model is a directed acyclic graph rather than a tree. We evaluate our algorithm through an ad-hoc simulator. We explore the trade-offs between network size, number of channels and positioning rate. To further make our approach scalable we perform in-network aggregation and deploy multiple sinks. The former reduces drastically the number of messages to be transmitted while the latter reduces the forwarding path length, hence the number of required transmissions. We show that with this approach positioning rates as high as 10 Hertz are within reach even in networks of hundreds of anchors covering thousands of squared meters.