DARP: A new routing algorithm for large communication infrastructures

Abstract

Esta tesis doctoral presenta dos algoritmos, un algoritmo de enrutamiento para redes inalámbricas de sensores basadas en el estándar IEEE 802.15.4 y un algoritmo de auto-selección de enlaces de comunicaciones basado en la calidad del enlace que permite auto-ajustar de forma dinámica el rol que los nodos desarrollan en el algoritmo de enrutamiento. El algoritmo de enrutamiento está diseñado para ofrecer un bajo tiempo de convergencia y un uso reducido de mensajes de control en entornos en los que una baja densidad de nodos hace díficiles las comunicaciones. Con esta motivación, se ha desarrollado esta tesis doctoral, la cual presenta las siguientes aportaciones científicas: La creación de un algoritmo de auto-selección de enlaces de comunicaciones y de auto-ajuste del rol ejecutado por cada nodo en la red cuando se inicializa. Mediante el uso de dicho algoritmo se expande y ajusta la cobertura de la red. La creación de un algoritmo de enrutamiento, el cual permite minimizar el tráfico debido al uso de sub-redes virtuales, así como organizar jerárquicamente la topología de la red. Se ha desarollado un modelo de simulación que permita afinar los diferentes parámetros que caracterizan el algoritmo y su testeo previa implantación. La integración de una versión del algoritmo de enrutamiento en una pila de comunicaciones, de forma que conformen un protocolo de comunicaciones que permita explotar los conceptos de localidad espacial y organización lógica en los que se basa el algoritmo de enrutamiento desarrollado.

This Ph.D. presents two algorithms, one is a routing algorithm for IEEE 802.15.4-based wireless sensor networks. The second is a best-link selection algorithm based on the quality of the links, which allows dynamically adjusting the role of a node in the routing algorithm. The routing algorithm is designed to offer a low convergence time and a reduced use of control messages in low-density environments. Due to these objectives, this Ph.D. provides the following main scientific contributions: The first one is the development of a best-link selection algorithm, which auto-adjusts the role of a node. Using this algorithm, the network’s coverage widens and it is auto adjusted. The second one is the creation of a routing algorithm, which minimizes the traffic due to the use of virtual sub-networks, as well as hierarchically organizes the network topology. A simulation model for the routing algorithm has been developed to be able to tune the different configuration parameters that characterize the routing algorithm and in order to test them before deployments. The third one is the integration of the routing algorithm in a wireless communication stack, so that form a communication protocol, which allows exploting the principle of locality and the logical organization on which the routing algorithm is based.