Finding Locally Unique IDs in Enormous IoT systems

Abstract: The Internet of Things (IoT) is an important and expanding technology used for a large variety of applications to monitor and automate processes. The aim of this thesis is to present a way to find and assign locally unique IDs to access points (APs) in enormous wireless IoT systems where mobile tags are traversing the network and communicating with multiple APs simultaneously. This is done in order to improve the robustness of the system and increase the battery time of the tags. The resulting algorithm is based on transforming the problem into a graph coloring problem and solving it using approximate methods. Two metaheuristics: Simulated annealing and tabu search were implemented and compared for this purpose. Both of these showed similar results and neither was clearly superior to the other. Furthermore, the presented algorithm can also exclude nodes from the coloring based on the results in order to ensure a proper solution that also satisfies a robustness criterion. A metric was also created in order for a user to intuitively evaluate the quality of a given solution. The algorithm was tested and evaluated on a system of 222 APs for which it produced good results.