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

Abstract

Las Redes Ad Hoc Inalámbricas gozan de un gran auge hoy en día 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, capaces de superar las restricciones impuestas por la variabilidad en la topología y el canal y la ausencia de infraestructura. Entre el elevado número de aspectos que se ven alterados por este nuevo planteamiento de las redes de comunicación, 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, hasta donde alcanza nuestro conocimiento, ambas aproximaciones al conocimiento se tratan de forma absolutamente independiente hasta la fecha. El planteamiento integral permite que se establezcan fuertes interrelaciones con otras interpretaciones de este campo de estudio 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 con el ánimo de caracterizar el encaminamiento en Redes Ad Hoc Inalámbricas de forma completa, genérica, única y medible. De esta forma, todos los factores involucrados son reunidos bajo un solo parámetro que representa cualquier escenario posible, mediante un valor numérico. El ambicioso objetivo de dotar al modelo teórico de las cualidades anteriores 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 conecta una y otro. Esta capacidad es descrita mediante la llamada eficiencia de encaminamiento, expresada como el cociente entre la distancia entre fuente y destino y la longitud de la ruta que los une. Así, se persiguen 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. 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 de diseño creada al efecto de asegurar la corrección de los resultados así como su reproducibilidad. Esta metodología es especialmente relevante para establecer un marco común de experimentación de tal forma que, por una parte, sea posible la comparación directa de los resultados obtenidos y, por otra, éstos sean representativos del fenómeno bajo análisis. Asimismo, la confirmación del modelo teórico se realiza mediante la comprobación de que las medidas experimentales recogidas son caracterizadas por un valor concreto del radio de persistencia. Por este motivo, se crea 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 sobre una base sólida, objetiva y equitativa. En el mismo, 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 las condiciones específicas del caso analizado. 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-, lo que permite futuros desarrollos en este campo de investigación. ____________________________________________

Wireless Ad Hoc Networks give response to current requirements regarding the establishment of networks that fulfill communication needs in a flexible -in time and space- and autonomous -autoconfiguration and independence from a fixed structure- way. These features imply important challenges in design that force the development of new proposals which overcome the restrictions that are imposed by the presence of variability in the topology and channel and the absence of an infrastructure. This novel approach of a communication network impacts on different aspects. Among them, routing is one of the most affected. This is especially significant due to the fact that, at the same time, routing is responsible of a relevant piece of the final level of performance of the network. This thesis faces the study of routing in Wireless Ad Hoc Networks from a theoretical and practical perspective that describes it globally. This outlook produces a significant innovation in this field, where, to the best of our knowledge, both approximations are seen in a completely separate way. The integral approach allows establishing strong relationships with other interpretations in this area under the scope of the Information Theory, Communication Theory, Control Theory or Graph Theory. 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 included factors are collected under a single parameter that represents any possible scenario by means of a numeric value. This ambitious aim of providing the theoretical model with the previous qualities starts from the most essential level of routing: its ability to establish paths from source to destination which are as close as possible to the straight line that connects both. This ability is described through the so called routing efficiency, which is expressed as the ratio between the Euclidean distance between source and destination and the actual length of the route. Thus, the completeness and generality features are reached. The set of every permitted value of the routing efficiency in a specific scenario is present in its statistical distribution, which is characterized by a single variable named persistence radius. Consequently, the desired properties of uniqueness and measurability are added. Furthermore, the theoretical model points out the existence of a direct relation between the spatial knowledge of the nodes regarding the network and the routing efficiency, which in addition depends on the dimension of the network. Therefore, the expression of the statistical distribution of the routing efficiency in D dimensions is included. The theoretical model is validated through simulation. The set of experiments that are carried out follow a methodology for their design created in order to assure the correction of the results and its reproducibility. This methodology is especially relevant to establish a common experimental framework. With this framework, the obtained results can be directly compared and are representative of the object under analysis. Additionally, the validation of the theoretical model is implemented verifying that the collected empirical measures are characterized by a particular value of the persistence radius. Because of this, a specific procedure is created to fit the experimental to the theoretical statistical distributions. 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 from a solid, objective and equitable basis. 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 complete -theoretical and practical- and integral -that considers every factor involved in it- point of view, which empowers future developments in this research field.