Applications of graph theory to wireless networks and opinion analysis

• Autores: Marino Tejedor Romero
• Directores de la Tesis: David Orden Martín (dir. tes.) , Iván Marsá Maestre (codir. tes.)
• Lectura: En la Universidad de Alcalá ( España ) en 2023
• Idioma: inglés
• Tribunal Calificador de la Tesis: Juan Ramón Velasco Pérez (presid.) , Fabian Maximilian Klute (secret.) , Reyhan Aydoğan (voc.)
• Enlaces
  • Tesis en acceso abierto en:  TESEO  e_Buah 
• Resumen
  • español

    La teoría de grafos es una rama importante dentro de la matemática discreta. Su uso ha aumentado recientemente dada la conveniencia de los grafos para estructurar datos, para analizarlos y para generarlos a través de modelos. El objetivo de esta tesis es aplicar teoría de grafos a la optimización de redes inalámbricas y al análisis de opinión.

    El primer conjunto de contribuciones de esta tesis versa sobre la aplicación de teoría de grafos a redes inalámbricas. El rendimiento de estas redes depende de la correcta distribución de canales de frecuencia en un espacio compartido. Para optimizar estas redes se proponen diferentes técnicas, desde la aplicación de heurísticas como simulated annealing a la negociación automática. Cualquiera de estas técnicas requiere un modelo teórico de la red inalámbrica en cuestión. Nuestro modelo de redes Wi-Fi utiliza grafos geométricos para este propósito. Los vértices representan los dispositivos de la red, sean clientes o puntos de acceso, mientras que las aristas representan las señales entre dichos dispositivos. Estos grafos son de tipo geométrico, por lo que los vértices tienen posición en el espacio, y las aristas tienen longitud. Con esta estructura y la aplicación de un modelo de propagación y de uso, podemos simular redes inalámbricas y contribuir a su optimización. Usando dicho modelo basado en grafos, hemos estudiado el efecto de la interferencia cocanal en redes Wi-Fi 4 y mostramos una mejora de rendimiento asociada a la técnica de channel bonding cuando se usa en regiones donde hay por lo menos 13 canales disponibles.

    Por otra parte, en esta tesis doctoral hemos aplicado teoría de grafos al análisis de opinión dentro de la línea de investigación de SensoGraph, un método con el que se realiza un análisis de opinión sobre un conjunto de elementos usando grafos de proximidad, lo que permite manejar grandes conjuntos de datos. Además, hemos desarrollado un método de análisis de opinión que emplea la asignación manual de aristas y distancias en un grafo para estudiar la similaridad entre las muestras dos a dos.

    Adicionalmente, se han explorado otros temas sin relación con los grafos, pero que entran dentro de la aplicación de las matemáticas a un problema de la ingeniería telemática. Se ha desarrollado un sistema de votación electrónica basado en mixnets, secreto compartido de Shamir y cuerpos finitos. Dicha propuesta ofrece un sistema de verificación numérico novedoso a la vez que mantiene las propiedades esenciales de los sistemas de votación.

  • English

    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.