Teoría del encaminamiento en redes ad hoc inalámbricas

Abstract

Las Redes Ad Hoc Inalámbricas gozan de un gran auge debido a que dan respuesta a las exigencias actuales referentes al establecimiento de redes que cubran necesidades de comunicación de forma flexible -en tiempo y espacio- y autónoma -autoconfiguración e independencia de una estructura fija-. Estas características suponen importantes retos de diseño que obligan a desarrollar propuestas novedosas que sean capaces de superar las restricciones impuestas. Entre todos los aspectos que se ven alterados por este nuevo planteamiento, el encaminamiento es uno de los más afectados. Este hecho es especialmente significativo debido a que, al mismo tiempo, una parte importante del nivel de las prestaciones finales ofrecidas por las Redes Ad Hoc Inalámbricas recae sobre el mismo.

La presente tesis aborda el estudio del encaminamiento en Redes Ad Hoc Inalámbricas desde un punto de vista teórico-práctico que lo describe de forma global. Esta perspectiva que aúna teoría y experiencia supone una innovación significativa en este ámbito, donde ambas aproximaciones al conocimiento se tratan de forma independiente hasta la fecha. El planteamiento integral permite establecer interrelaciones con otras interpretaciones con origen en la Teoría de la Información, de la Comunicación, del Control o de Grafos.

En lo concerniente al aspecto teórico, la presente tesis desarrolla un modelo que caracteriza el encaminamiento en Redes Ad Hoc Inalámbricas de una forma completa, genérica, única y medible. De esta forma, todos los factores involucrados son reunidos bajo uno solo que representa cualquier escenario posible, mediante un valor numérico. Este objetivo parte del nivel más esencial del encaminamiento: su capacidad para establecer caminos entre fuente y destino que se ajusten a la línea recta que une una y otro. Esta capacidad es descrita mediante la llamada eficiencia de encaminamiento, que se expresa como el cociente entre la distancia entre fuente y destino y la longitud de la ruta que los conecta. Así, se alcanzan los rasgos de completitud y generalidad. El conjunto de todos los valores posibles de la eficiencia de encaminamiento para un escenario determinado es recogido en su distribución estadística, que se representa por la magnitud de una sola variable denominada radio de persistencia. Por consiguiente, se añaden las deseadas unicidad y mensurabilidad al modelo propuesto.

A su vez, el modelo teórico denota la existencia de una relación directa entre el conocimiento espacial de los nodos acerca de la red y la eficiencia de encaminamiento, así como la dependencia de ésta con la dimensión de la red. En este sentido, se aporta la expresión de la distribución estadística de la eficiencia de encaminamiento en D dimensiones.

El modelo propuesto es validado de forma empírica. El conjunto de experimentos que se lleva a cabo obedece a una metodología que establece un marco común de experimentación para posibilitar la comparación directa de los resultados obtenidos y la representatividad del fenómeno bajo análisis.

Asimismo, se propone un procedimiento específico para el ajuste de la distribución estadística experimental a la teórica que produce tanto la magnitud absoluta representativa como su rango de variación.

El desarrollo teórico y empírico aportado por la presente tesis genera un marco de estudio y evaluación del encaminamiento en Redes Ad Hoc Inalámbricas. Sus prestaciones son definidas de forma absoluta mediante la medida de su radio de persistencia, abandonando la mera comparación relativa de ciertos aspectos particularizados a unas condiciones específicas.

Por consiguiente, a través del mismo, es posible el estudio del encaminamiento en Redes Ad Hoc Inalámbricas desde un punto de vista completo -teórico y experimental- e integral -que considera todas las contribuciones de los distintos factores involucrados en el mismo-, que permite futuros desarrollos en este campo de investigación.

This thesis approaches the study of routing in Wireless Ad Hoc Networks from a combined theoretical and practical perspective. This combined perspective constitutes a significant innovation in the field, where, to the best of our knowledge, to date all theoretical and practical analyses have been undertaken in completely independent ways.

Regarding the theoretical aspect, the present thesis develops a model that characterizes routing in Wireless Ad Hoc Networks in a complete, generic, unique and measurable way. Hence, all the relevant factors are collected under a single parameter that represents any possible scenario by means of a numeric value. This goal arises from the most essential level of routing: its ability to establish paths from source to destination that are as close as possible to the straight line. This ability is described through the so-called routing efficiency, expressed as the ratio between the Euclidean distance between source and destination and the actual length of the route.

The theoretical model is validated through simulation. The set of experiments carried out follow a methodology which establishes a common experimental framework within which the obtained results can be directly compared and are representative of the object under analysis.

Additionally, a specific procedure is created to fit the experimental statistical distribution to the theoretical one. This fitting generates both the absolute magnitude and its range of variation.

The theoretical and empirical development included in this thesis builds a framework for the study and evaluation of routing in Wireless Ad Hoc Networks. The routing performance is defined in an absolute way through the measure of its persistence radius, thus avoiding the relative comparison of several aspects particularized by the specific conditions of the analyzed case.

Consequently, this framework allows the study of routing in Wireless Ad Hoc Networks from a point of view that is both complete (theoretical and practical) and integral (treating all relevant factors), laying the foundations for future developments in this field of research.