Contribución a la teoría de redes de interconexión y de radiocomunicación

Resum

Las redes multisalto constan de un conjunto de nodos distribuidos en una determinada área geogràfica, que intercambian paquetes mediante enlaces de radio, En la mayoría de redes de comunicación entre dos nodos se emplea un único camino, que se elige según un criterio de optimización, p. ej.: mínimo número de saltos, máxima calidad de los enlaces, etc. Además, el proceso de selección del camino está usualmente distribuido. Por otra parte, el nivel de la señal recibida no es suficiente, lo cual implica errores en la recepción, y tener que corregir los errores; a menudo mediante la retransmisión de paquetes. Estos mecanismos fundamentan todo protocolo de comunicación de paquetes. Dos importantes ejemplos de redes de radio multisalto son la ad-hoc y la mallada. Dos destacadas características en la transmisión via radio son: La potencia de transmisión y la diversidad de receptores. Aquella es la que lleva una mayor parte del presupuesto en la transmisión. Cabe saber que los protocolos de encaminamiento propuestos para redes ad-hoc o para las de mallas no emplean la ventaja de transmisión por radio: Diversidad de receptores. Es decir, que no tienen en cuenta que cuando el transmisor envía una información, ésta suele llegar a más de un receptor. Además, muchos protocolos son a priori, es decir, se tiene el camino de la transmisión desde el principio. Por otra parte, una transmisión es a posteriori cuando tras cada transmisión se elige el siguiente nodo retransmisor de entre los que han recibido bien el paquete. El coste de transmisión entre dos nodos es el número esperado de transmisiones para que un paquete enviado llegue de uno al otro. Aquí se propone el encaminamiento a posteriori denominado mínimo salto máxima diversidad (MHMD) en el cual se elige el siguiente nodo retransmisor de entre los que han recibido bien el paquete y tenga menor coste de transmisión. Para evaluar la propuesta se han estudiado las características de parámetros relacionados en, por ejemplo, redes compuestas de cuadrados (grids). Se ha obtenido que la probabilidad de éxito en la transmisión en el caso a posteriori MHMD sin retransmisiones es mayor que la probabilidad de éxito en la transmisión en el caso a priori sin retransmisiones y que la probabilidad de éxito en la transmisión en el caso a posteriori pero cuando el nodo retransmisor es elegido aleatoriamente. Asimismo, se ha calculado el coste explícito de la transmisión en los nodos y el Tráfico que soportan los nodos. En cuanto a la segunda parte, se consideran los requisitos exigidos a la topología de las redes de interconexión. Como son, -Valor reducido de enlaces conectados a cada nodo -Diámetro mínimo -Existencia de algoritmos eficaces y sencillos de encaminamiento de los mensajes a través del sistema -Tráfico uniforme -Fiabilidad frente a posibles fallos Algunos de los problemas derivados de tales requisitos en términos de grafos son: -Diseño de grafos y dígrafos densos, es decir, con elevado número de vértices para diámetro y grado dados -Diseño de diseño de grafos y dígrafos densos vértice simétricos -Diseño y evaluación de grafos densos fiables En esta parte se han presentado -Diversas técnicas que han permitido mejor la tabla de mayores grafos conocidos para diámetros 3,6,7 y 10. -Varias construcciones de grafos bipartitos obteniéndose nuevas mejoras. -Diferentes construcciones de grafos densos para valores asintóticos del diámetro. -Una familia de digrafos bipartitos de Moore no isomorfa a la ya conocida para los mismos diámetros. -Una nueva composición de dígrafos vértice simétricos y una familia general de dígrafos simétricos, obteniéndose importantes mejoras en la tabla de los mayores dígrafos vértice simétricos densos conocidos. -Diversos resultados sobre vulnerabilidad, conectividad y superconectividad de grafos y de dígrafos.