Hardware Acceleration of Real-Time Angle of Arrival Positioning
Abstract
Sanntids-lokasjonssystemer har blitt viktig i en rekke bransjer da de muliggjør for effektiv utstyrskontroll og optimalisert logistikk. I 2019 forbedret Bluetooth sin BLE teknologi, slik at det ble mulig med presisjon på centimeternivå for innendørs posisjoneringssystemer (IPS), en undergruppe av RTLS. Ved å støtte AoA og AoD teknologi tilbyr BLE høy presisjon med lav kompleksitet og strømforbruk. I denne sammenhengen ble et system utviklet som en del av TFE4580 - Fordypningsprosjekt for å demonstrere den nye teknologien. Denne oppgaven har som mål å videre forbedre dette systemet ved å akselerere AoA-beregninger.MUSIC algoritmen er en populær algoritme og brukes ofte for å estimere AoA i RTLS. I denne oppgaven blir arbeidet fra flere versjoner av MUSIC-algoritmen kombinert og ytterligere optimalisert for en spesifikk antennekonfigurasjon og for bruk i BLE-applikasjoner. Under optimaliseringen utforskes nye metoder for å utlede en reell-MUSIC algoritme for ikke-uniforme antennestrukturer. En transformasjon av MUSIC-algoritmen, hvor målet er å gjøre alle verdier reelle, blir utforsket, slik at den implementerte akseleratoren kan oppnå høyere grad av parallellitet. Implementeringen av algoritmen er delt inn i to masteroppgaver, der denne oppgaven hovedsakelig setter søkelys på det siste trinnet i MUSIC-algoritmen, der et søk utføres for å finne AoA. For søket er to alternativer implementert og sammenlignet med hverandre og med en serie av høy-nivå modeller, skrevet i Python og C. En flersøk-tilnærming er utviklet, som reduserer kompleksiteten for søkningen uten å redusere presisjonen vesentlig.Effekt- og tidsforbruket er målt for alle implementerte versjoner, noe som gjør det mulig å sammenligne den akselererte algoritmen med høy-nivå modellene. Sammenlignet med Python, som er språket som ble brukt til å implementere MUSIC-algoritmen i det tidligere implementerte systemet, ble det observert betydelig tidsreduksjon, med en kjøretid som ble redusert fra 154 ms til 5,34 μs. Det akselererte søket er også betydelig mer energieffektivt sammenlignet med høy-nivå modellene. Energieffektivitet er viktig ved implementering av lavenergisystemer, og med de oppnådde resultatene vil det akselererte søket ytterligere forbedre det allerede eksisterende systemet når det gjelder hastighet og energieffektivitet, samtidig som omtrentlig samme presisjon blir opprettholdt.Søket som er implementert er en del av et større design, hvor alle stegene i MUSIC algoritmen er implementert på en FPGA. De gjenværende stegene av algoritmen er implementert av Tommy A. Opstad, og mer informasjon om de stegene kan bli funnet i hans masteroppgave [1]. Resultatene fra de to oppgavene er satt sammen for å sørge for at designene er kompatible med hverandre, og et estimat på den totale ytelsen av den totale akselerasjonen er gitt. Real-Time Locating Systems (RTLS) have become vital across industries as they allow for effective resource management and optimized logistics. In 2019, Bluetooth enhanced the Bluetooth Low Energy (BLE) technology, allowing for centimeter-level precision for Indoor Positioning Systems (IPS), a subset of RTLS. Allowing for Angle of Arrival (AoA) and Angle of Departure technology (AoD), BLE offers high precision with low complexity and power usage. In this context, a system was developed as a part of TFE4580 – Specialization Project to demonstrate the improvements. This thesis aims to further improve this system by implementing a hardware accelerator for the AoA computations.The Multiple Signal Classification (MUSIC) algorithm is a popular algorithm, and it is widely used for estimating the AoA in RTLS. In this thesis, the work from multiple versions of the MUSIC algorithm is combined, and further optimized for a specific antenna structure and for use in BLE applications. During the optimizations, new methods for deriving a real-valued MUSIC algorithm is explored for non-uniform antenna arrays.A real-valued transformation of the MUSIC algorithm is explored, allowing the implemented hardware accelerator to achieve greater level of parallelism. The implementation of the algorithm is divided into the work of two theses, where this thesis mainly focuses on the final step of the MUSIC algorithm, where a search is performed, and the goal is to find the AoA. For the search, two options are implemented and compared to each other, and to a series of high-level models, written in Python and C. A multiple-search approach is derived, reducing the complexity for the search, without reducing the search precision significantly.The power- and time consumption is measured for all implemented versions, allowing us to compare the hardware accelerated search to the high-level models. Compared to Python, which is the language used for implementing the MUSIC algorithm in the previously implemented system, significantly time reduction is observed, reducing the execution time from 154 ms to 5.34 μs. The hardware accelerated search is also significantly more energy efficient when compared to the high-level models. Energy efficiency is essential when implementing low-power systems, and with the obtained results, the hardware accelerated search would further improve the already existing system in terms of speed and energy efficiency while maintaining approximately the same level of precision. Some errors are introduced when specific AoAs are present, and the reason for this is due to the values used in the search being limited in terms of decimal precision.The implemented search is a part of a larger design, where all steps of the MUSIC algorithm are implemented on an FPGA. The implementation of the remaining parts of the algorithm can be found in the thesis written by Tommy A. Opstad [1]. The two designs are merged to confirm that the two designs are compliant with each other, and an estimation of the total performance is given.