Adaptive Routing Protocols for Mobile Ad Hoc Networks

Resumen

Un protocolo de encaminamiento de una red móvil ad hoc necesita proveer un mecanismo que mantenga las rutas hacia los destinos frente al movimiento de los nodos que puede provocar que las rutas se destruyan. Los protocolos convencionales o bien tendrán un rendimiento muy pobre, o bien serán simplemente inaplicables. Como alternativa se desarrollan protocolos específicos de encaminamiento, que logran la adaptabilidad de una forma eficiente y robusta. El Algoritmo de Optimización de la Colonia de Hormigas, abreviadamente ACO, es una rama de la Inteligencia Artificial que usa conceptos de inteligencia colectiva y que se inspira en el comportamiento de las hormigas en la naturaleza. ACO se aplica a una amplia gama de problemas diferentes. Debido a sus propiedades de adaptabilidad y robustez, también se ha convertido en un paradigma para el encaminamiento en redes móviles ad hoc. Los algoritmos ACO trabajan de forma iterativa. En cada paso las hormigas artificiales construyen en paralelo una solución para el problema en cuestión, utilizando la matriz de feromona artificial. A continuación, se actualiza la matriz de feromona sobre la base de las soluciones encontradas. De esta manera, la matriz de feromona refleja información sobre las buenas soluciones que se han encontrado hasta la fecha, y permite a las hormigas de las generaciones posteriores utilizar esta información para crear otras nuevas. En este trabajo se especifica un protocolo de encaminamiento ACO para redes móviles ad hoc basado en AntHocNet. Como su predecesor, este nuevo protocolo llamado AntOR es híbrido, en el sentido de que contiene elementos de encaminamiento tanto reactivos como proactivos. En concreto, combina un proceso reactivo de establecimiento de ruta con un proceso proactivo de mantenimiento y exploración de nuevas rutas. La información de encaminamiento se almacena en tablas de feromona que son similares a las utilizadas por otros algoritmos de encaminamiento ACO. El reenvío de paquetes de datos y de control se realiza de una manera estocástica con el uso de estas tablas. Los fallos de enlace se tratan con mecanismos reactivos específicos, tales como la reparación de ruta local y el uso de mensajes de aviso. Los aspectos clave del protocolo AntOR son la utilización de rutas disjuntas de nodo y disjuntas de enlace, la separación entre la feromona regular y la feromona virtual en el proceso de difusión y la exploración de nuevas rutas, que tiene en cuenta el número de saltos en las mejores rutas. En este trabajo también se especifica una familia de protocolos de encaminamiento ACO basada en AntOR: AntOR disjunto de nodo (Antor-DNR), AntOR disjunto de enlace (DLR), AntOR restrictivo (Antor-RDLR), AntOR unicast (Antor-UDLR), AntOR-v2 y HACOR. Todos estos protocolos son refinamientos sucesivos del protocolo original. En este trabajo también se especifica una versión paralelizada de AntOR, P-AntOR, que hace uso de arquitecturas multiprocesador de programación basado en protocolo de memoria compartida y permite ejecutar tareas en paralelo usando hilos, siendo aplicable esta paralelización en la fase de descubrimiento de ruta, en el proceso de reparación local de rutas y en la notificación de fallos de enlace. Asimismo, se especifica una variante con más de una interfaz (P-AntOR-MI), que paraleliza el envío de mensajes de difusión por interfaz a través de hilos. Las simulaciones se realizaron utilizando la herramienta Network Simulator (NS-3). Los resultados muestran que en la mayoría de los casos este nuevo conjunto de protocolos de encaminamiento ACO tiene menor sobrecarga y mayor tasa de entrega de paquetes que AntHocNet y AODV, siendo HACOR la mejor variante secuencial. Los resultados también indican que las aproximaciones paralelas funcionan mejor que las secuenciales, especialmente en lo relativo al retardo extremo a extremo, al jitter y a la tasa de entrega de paquetes, y que PAntOR-MI es el más adecuado en ambientes altamente dinámicos.