El grafo virtual para ruteo geométrico en una red inalámbrica AD-HOC

Abstract

A wireless ad-hoc network is a set of devices equipped with a transmitter and a receiver. Wireless hosts can communicate with each other in the absence of a fixed infrastructure. These networks typically consist of equal nodes that communicate over wireless links without central control. In this thesis the problem of routing data in a wireless ad-hoc network is approached by location aware. The algorithms used by these networks require that the nodes can determine their geographic location, in addition some algorithms require to extract a planar graph, which represents the underlying physical network. The two important contributions in this thesis work are: the Dual of a Plannar Graph and the Virtual Graph. The dual of a planar graph is a structure for routing packages using the greedy algorithm, where always the delivery of packages is guaranteed. At this moment, with some topologies, greedy algorithm fails for sending packages. On the other hand, the virtual graph is an important contribution for those algorithms that require to obtain a planar graph for routing, when the virtual graph is compared with respect to the Gabriel Graph and the Morelia Graph we obtain better results. A simulation study was developed using a proper simulator, it is simple and easy to use.

Una red inalámbrica ad-hoc es un conjunto de dispositivos móviles equipados con un transmisor y un receptor, los cuales se autoorganizan para conectarse cuando no existe una infraestructura que los coordine. En esta tesis se aborda el problema de envío de datos en una red inalámbrica \ad-hoc" basado en la posición del transmisor. Los algoritmos empleados para este tipo de redes requieren que los nodos puedan determinar su ubicación geográfica, además algunos de los algoritmos requieren extraer un grafo plano, el cual represente la red física subyacente. Las dos contribuciones importantes en este trabajo de tesis son: el Dual del Grafo Plano y el Grafo Virtual. El dual del grafo plano es una estructura para encaminar paquetes usando el algoritmo voraz, y donde siempre se garantiza la entrega de paquetes. Actualmente existen algunas topologías en las cuales el algoritmo voraz falla. Por su parte, el grafo virtual es una contribución importante para aquellos algoritmos que requieren obtener un grafo plano para encaminar, ya que comparado con el grafo de Gabriel y el grafo de Morelia se logran mejores resultados. Para comparar los resultados con otros grafos se hizo mediante simulación, para lo cual se creó un simulador con distintas opciones, que lo hacen sencillo y fácil de usar.