Carleton University - School of Computer Science Honours Project
Fall 2020
Minimum Beacon Nodes for Graph Localizability
Cameron Jones
SCS Honours Project Image
ABSTRACT
Determining the location of various sensors in a wireless sensor network is important to the network’s functionality. However, for some sparsely populated graphs, even if all possible distances between nearby nodes are gathered, there is no way to use that information to determine the unique position of the nodes. Various algorithms exist to determine whether or not a graph can be localized to unique positions given its set of nodes and known distances. This paper aims to discuss potential algorithms to instead determine what is the minimum number of nodes whose positions need to be manually “fixed” for the rest of the graph to be localizable. Various simulations will be done to compare the efficiency of the algorithms.