Protocolo de encaminamiento en origen con identificadores no únicos para redes Ad-Hoc de dispositivos con recursos limitados

Zusammenfassung

Si deseamos que cualquier dispositivo pueda conectarse a una red global, es muy conveniente que disponga de un identificador único. Para los equipos de recursos limitados (sensores, juguetes, dispositivos desechables, micro-robots, etc.) el tamaño de ese identificador puede suponer una sobrecarga inabordable, porque con las técnicas convencionales se manejan direcciones íntegras en la transmisión, proceso y almacenamiento de los datos necesarios para el encaminamiento. Esto se hace notar especialmente en DSR, un protocolo de encaminamiento en origen para redes Ad-Hoc, donde cada paquete de datos debe almacenar las direcciones de todas las estaciones por las que debe pasar hasta llegar a su destino. En este tipo de dispositivos la solución típica es limitar el espacio de direccionamiento a uno o dos octetos, sacrificando por tanto la unicidad global de los identificadores. O más drásticamente, prescindir del encaminamiento. Presentamos en esta tesis una propuesta que permite mantener direcciones que identifiquen globalmente a las estaciones, porque en las tareas de encaminamiento empleamos lo que denominamos dirección discriminante para el encaminamiento o dirección abreviada. Serán no únicas, es decir, dos o más estaciones diferentes podrán compartir la misma dirección abreviada, hecho al que denominamos colisión. No evitaremos las colisiones, sino que desarrollaremos técnicas que toleren sus consecuencias. Desarrollaremos esta idea en un protocolo en particular al que denominaremos ADSR, una modificación del protocolo DSR para que maneje direcciones abreviadas. Por otro lado, las redes Ad-Hoc normalmente requieren de los protocolos de nivel de enlace la fiabilidad de la que el medio físico inalámbrico carece. Empleando direcciones abreviadas como hace ADSR, una única dirección de red se corresponde con varias direcciones de enlace, por tanto es necesario el envío fiable a varios destinatarios, característica de la que no disponen los protocolos de enlace habituales. Para satisfacer este requerimiento hemos desarrollado el protocolo al que denominamos LLRB (Link Layer Reliable Broadcast), basado en IEEE 802.11. LLRB consta de tres módulos, cada uno de los cuales desarrolla un algoritmo novedoso: 1. Extensión del mecanismo MACA, en la que se reemplaza la secuencia de tramas de control RTS-CTS-dato-ACK por una trama RTS, varias tramas CTS, una trama de datos y varias tramas ACK. 2. Algoritmo de contienda limitada mediante máscaras de elección de slot (LCSEN, Limited Contention by means of Slot Election Masks) mecanismo por el que el nodo emisor coordina el envío de tramas CTS y ACK por parte de los destinatarios de los datos. Para ello emplea un único octeto, que los destinatarios compondrán con su propia dirección. 3. Algoritmo ligero de estimación de vecindario o algoritmo del maestro ciego (LANE, Low-Cost Algorithm for Neighborhood Estimation), que proporciona una estimación de los nodos contiguos al nodo emisor, sin emplear más tramas que los CTS y ACK de la extensión MACA. Este algoritmo detecta la ausencia de respuestas CTS y ACK y las atribuye bien a colisiones en el acceso al medio, bien a cambios en la topología de la red. En esta tesis se presenta tanto el diseño de los protocolos ADSR y LLRB como la implementación de los mismos sobre el simulador de red ns-2. También se analiza el rendimiento de ambos en simulador en diversas condiciones, se obtienen algunas condiciones de uso y se introducen las líneas futuras de trabajo.