Estudio estadístico de la dilación de los grafos de proximidad: grafos Theta y Yao.

Abstract

Construir y mantener una estructura de red eficiente es una tarea muy importante en todas aquellas redes de sensores inalámbricos. En lo que se refiere a consumo eléctrico, uno de los puntos más importantes a tener en cuenta es la potencia de transmisión que necesita cada sensor para enviar la información al siguiente nodo de la red. Con una solución donde cada sensor es capaz de reconocer a sus vecinos más próximos, estos mismos se encargarían de decidir y escoger la cantidad de potencia que desean emplear para trasmitir la información al siguiente punto. Por este motivo, el estudio y análisis de la conectividad que ofrecen los grafos de proximidad resulta muy interesante, dado que dar con una buena solución repercute en el ahorro de una cantidad enorme de recursos (tanto de tiempo cómo de dinero). En este documento se estudia y comparan dos construcciones de grafos de proximidad a priori muy similares, Yao-grafos y Theta-grafos, poniendo el foco del estudio en los valores de dilación obtenidos de un mismo conjunto de grafos aleatorios. El objetivo consiste en contrastar los resultados obtenidos y determinar si uno de ellos resulta mucho mejor que el otro, o dictaminar un empate técnico entre ellos.---ABSTRACT---Design and maintain an efficient network structure is a very important task in all wireless sensor networks. In terms of power consumption, one of the most important points to consider is the transmission power that each sensor needs to send the information to the next node in the network. With a solution where each sensor is able to recognize its closest neighbors, they will be in charge of deciding and choosing the amount of power they want to use to transmit the information to the next point. For this reason, the study and analysis of the connectivity offered by proximity graphs is very interesting, since finding a good solution has an effect on saving a huge amount of resources (both time and money). In this paper we study and compare two very similar graph constructions, Yao-graphs and Theta-graphs, placing the focus of the study on the delay values obtained from the same set of random points. The objective is to compare the results obtained and determine if one of them is much better than the other, or to dictate a technical tie between them.