Soluciones locales para problemas globales en redes inalámbricas



Soluciones locales para problemas globales en redes inalámbricas

Dr. Jorge Urrutia

9 de Febrero de 2015

12:00 hrs.

Auditorio de Ingeniería Eléctrica

Texto completo de la plática           Video del evento          

 

Resumen

En esta plática haremos un resumen de una clase de algoritmos de ruteo que resuelven problemas de tipo global en redes ad-hoc unitarias mediante algoritmos de tipo local. En una red unitaria, los nodos son representados por puntos, y cualquiera dos de ellos son adyacentes si la distancia entre ellos es a lo mas uno. Un algoritmo local es un algoritmo en el que cada nodo solo conoce información de nodos a distancia k de él mismo, donde k es una constante. No permitimos que la información contenida en un nodo se disperse por la red. Esta última condición obedece a restricciones reales en redes como INTERNET que son muy dinámicas, y en las cuales no se conoce en cualquier momento la topología de las mismas.

Presentaremos algoritmos para resolver problemas como los siguientes: dada una red inalámbrica unitaria, queremos calcular (con un algoritmo local) una subgráfica plana de la misma, o calcular una aproximación a una subred cuyo peso, este cerca del peso de un árbol generador de peso mínimo. Estos algoritmos se utilizan actualmente en muchas aplicaciones de ruteo en redes como las de telefonía celular, y en diversas aplicaciones en redes de sensores y redes ad-hoc.

 

Breve semblanza biográfica

 

 

 

El Dr. Jorge Urrutia Galicia estudió la licenciatura en matemáticas en la Facultad de Ciencias de la UNAM de 1971 a 1974, y la maestría y el doctorado en matemáticas en la Universidad de Waterloo, Canadá de 1976 a 1980. Ha trabajado en la Universidad Autónoma Metropolitana-Iztapalapa, el CIMAT, La Universidad de Carleton, la Universidad de Ottawa de 1984-1998, donde fue "full professor", y desde 1998 en el Instituto de Matemáticas de la UNAM. Ha publicado mas de 270 artículos en memorias de congresos y revistas de investigación en matemáticas y computación, los cuales han recibido más de 6,000 citas. Ha impartido más de 40 conferencias plenarias en congresos internacionales en Geometría Computacional. Fue editor en jefe de "Computational Geometry, Theory and Applications" de 1990 al 2000. Ha supervisado más de 55 tesis de licenciatura, maestría y doctorado.

El año pasado, recibió el premio "Universidad Nacional en Investigación en Ciencias Exactas" en la UNAM. Es miembro del Sistema Nacional de Inves- tigadores, Nivel 3. Ha organizado y participado en los comités organizadores de varios congresos nacionales entre los que se encuentran el "Coloquio Victor Neumann-Lara de Teoría de Gráficas y sus Aplicaciones", la "Canadian Conference on Computational Geometry", la "Japan Conference on Discrete and Computational Geometry" y los "Encuentros de Geometría Computacional" (España).