Applications of graph theory to wireless networks and opinion analysis

Abstract

Graph theory is an important field of discrete mathematics. It has been widely used lately thanks to the rise of data science as a discipline, since it is useful for structuring, analyzing and generating data through models. The objective of this thesis is to employ graph theory for the optimization of wireless networks and opinion analysis. The first set of contributions is related to graph theory applied to wireless networks. Performance of these networks depends on the appropriate distribution of their frequency channels in a shared physical space. In order to optimize these networks, several techniques had been proposed, from heuristics like simulated annealing to automatic negotiation. All these techniques require a model behind it. We developed a Wi-Fi network model using geometric graphs. Nodes represent devices, both clients and access points, and edges represent desired or undesired signal between two devices. These graphs are geometric. Consequently, vertices have a position in the space, and edges have a length. Including these parameters and a propagation model, we are able to simulate wireless networks and contribute to optimize them. Using this graph-based model, we studied the effect of cochannel-interference in Wi-Fi 4 networks and showed that channel-bonding offers a performance gain when used in regions where 13 channels or more are available. On the other hand, we have applied graph theory to opinion analysis along the line of SensoGraph, which is a method enabling efficient sensory analysis of a set of items by means of proximity graphs, allowing to handle large input datasets. In addition, we have developed a new opinion analysis method, which uses manual edge assignment and distances in a graph to study pairwise similarity between different samples. Finally, we have explored themes outside of graph theory but still inside the frame of mathematics applied to a telematics engineering problem. A novel e-voting system based on mixnets, Shamir’s secret sharing and finite fields is proposed. This proposal offers a new verification system and complies with the essential properties of voting systems.