2016

Distribución de contenidos P2P en redes MANET utilizando conocimiento de redes sociales

 Descargar versión PDF

Profesores: Dra. Elizabeth Pérez Cortés y Dr. Miguel López Guerrero

Resumen: Cerca de 25% del tráfico actual en Internet es causado por usuarios particulares que comparten contenidos digitales (fotografías, videos, música, textos, etc.) y se espera que el volumen de datos transferido por esta razón crezca a un ritmo del 26% anual durante los próximos cinco años. El soporte de tal nivel de actividad es la red par a par (P2P) en donde no hay estaciones con tareas especializadas como sucedería en un esquema cliente-servidor. En un sistema P2P todos los miembros de la red tienen una funcionalidad equivalente y cada uno de ellos puede proveer y descargar contenidos. Como consecuencia, los sistemas diseñados bajo este paradigma son naturalmente escalables y tolerantes a fallas. La manera usual en la que opera la distribución de contenidos en redes P2P es la siguiente. Cuando un usuario desea obtener un contenido, primero utiliza un servicio de localización el cual le indica qué proveedor es capaz de enviárselo. Con esta información, la descarga puede darse involucrando sólo al solicitante y al proveedor. Ésta usualmente se efectúa dividiendo el contenido original en fragmentos y enviando cada uno de éstos al receptor. La eficiencia de este esquema básico de distribución puede mejorarse de diversas maneras. Por ejemplo, posiblemente existan otros nodos interesados en un mismo archivo y en cuanto uno de ellos recibe el primer fragmento, puede comenzar a distribuirlo. De esta forma, un nuevo solicitante podría tener más opciones para descargar al menos parte del archivo y, a su vez, poder distribuirlo. Esto origina la creación de una red de descarga P2P cuyo propósito es que todos los interesados obtengan el contenido completo en el menor tiempo posible. Esquemas de distribución, tal como el descrito anteriormente, se han propuesto considerando que las comunicaciones ocurren sobre redes cableadas. Esto ha dado lugar a un conjunto de condiciones que usualmente se asumen durante el diseño, evaluación e implementación de tales sistemas. Entre algunas de estas suposiciones se puede mencionar que los enlaces se asumen confiables y de alta velocidad. Se considera además que la población de usuarios es de gran tamaño (en el orden de los miles de usuarios) y que durante el tiempo de vida de la sesión de un usuario, éste permanecerá con movilidad limitada o nula. Sin embargo, la popularidad de los dispositivos móviles de comunicación, como el medio preferido de conexión de los usuarios, hace que la mayor parte de las suposiciones anteriores sean inválidas y tenga que replantearse el escenario anteriormente descrito.

El presente proyecto de investigación se enfoca en el estudio de protocolos de descarga que operen eficientemente en redes conformadas únicamente por dispositivos personales de comunicaciones inalámbricas. Estas redes se denominan MANET (del inglés mobile ad hoc network) y pueden definirse como una colección de dispositivos de comunicaciones inalámbricas personales capaz de establecer comunicaciones entre sus miembros sin el uso de infraestructura adicional. En este nuevo contexto las condiciones podrían impedir la descarga completa de un contenido o incrementar considerablemente el tiempo necesario para lograrlo. Para contender con este reto, se propone incorporar en la solución conocimiento sobre la(s) red(es) social(es) de los individuos que portan los dispositivos. Un ejemplo del tipo de conocimiento que se quiere aprovechar se publicó recientemente sobre la red social Facebook, y reveló que:

1. Algunos intereses de los individuos están altamente correlacionados, esto es, dado un par de intereses correlacionados A y B, si una persona tiene el interés A, es muy probable que se interese también en B.
2. Un usuario de una red social no tiene la misma frecuencia de interacción con todos sus contactos (amigos).
3. Los amigos en una red social usualmente tienen relaciones sociales cercanas en la vida real.

Como parte de este proyecto se estudiarán las adaptaciones del protocolo BitTorrent (el protocolo más exitoso para descargar contenido en redes cableadas) para MANET y, se buscará incorporar conocimiento de las redes sociales, como el mencionado anteriormente, para mejorar el porcentaje de descargas exitosas y el tiempo promedio de descarga. La propuesta se evaluará considerando un modelo de movilidad peatonal.

Objetivo general

• Construir estrategias exitosas para la construcción de protocolos de descarga de contenido en MANET

Objetivos específicos

• Identificar las variantes del protocolo de descarga de BitTorrent para MANET
• Identificar el conocimiento sobre el comportamiento de los individuos en redes sociales que sea de utilidad para la descarga de contenidos sobre una MANET
• Construir un protocolo de descarga de contenidos para MANET que incorpore el conocimiento de redes sociales
• Evaluar el protocolo de descarga bajo un modelo de movilidad peatonal

Solución a problemas de coloración clásicos utilizando Coloración de Gráficas Suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Miguel Ángel Gutiérrez Andrade

Resumen: La coloración de grafos es omnipresente en el modelado de aplicaciones del mundo real; por ejemplo, para mostrar asignación de frecuencias en problemas de telecomunicación; asignación de registros en un sistema operativo, programación de tareas; entre otras. La coloración de grafos se presenta en una gran variedad de formas de las cuales, la Coloración de Gráficas Suaves (CGS) es considerada una generalización del problema de coloración de gráficas.  El problema de Coloración de Gráficas Suaves se ha utilizado recientemente en problemas de clasificación y de reconocimiento de patrones en general. En este problema tenemos que, dada una gráfica con ponderaciones en las aristas, el objetivo es encontrar una coloración que minimice la suma de las aristas con el mismo color en ambos extremos; es decir, la suma de las penalizaciones denominada dureza. Asimismo, existen otros parámetros importantes en la Coloración de Gráficas Suaves como lo son la solidez, la cual proporciona un valor promedio de las penalizaciones de la gráfica y resilencia que permite encontrar una cantidad adecuada de colores. Es sabido que este problema es del tipo NP-duro y es necesario el uso de metaheurísticas en instancias mayores a 20 vértices.

Objetivo general

• Desarrollar un algoritmo que resuelva varios problemas clásicos de coloración utilizando el enfoque de coloración de gráficas suaves

Objetivos específicos

• Realizar un estudio del estado del arte de los problemas de coloración clásicos, así como su representación como gráfica suave
• Compilación de instancias benchmark clásicas de cada uno de los problemas que se estudiarán
• Desarrollo de los algoritmos de solución
• Análisis de resultados y conclusiones

Búsqueda dispersa para el problema de coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Sergio Gerardo de los Cobos Silva

Resumen: El problema de coloración de gráficas suaves es una generalización del problema de coloración, en donde un grafo completo, las aristas tienen penalizaciones. Este problema se ha demostrado que puede resolver otros problemas tales como coloración mínima, coloración equitativa, entre otros; y en tiempos recientes, como parte de un trabajo de tesis de maestría, se ha demostrado su utilidad como clasificador no supervisado. Debido a que este modelo es del tipo NP-difícil, se requiere el uso de metaheurísticas para problemas con mas de 20 vértices. En este proyecto se propone realizar un algoritmo de solución utilizando la metaheurística de búsqueda dispersa.

Objetivo general

• Desarrollar un algoritmo de solución para el problema de coloración de gráficas suaves utilizando la técnica metaheurística de búsqueda dispersa

Objetivos específicos

• Revisión del estado del arte de problema a resolver y la técnica de solución
• Planteamiento de instancias apropiadas para verificar la calidad del algoritmo
• Propuesta de un algoritmo de solución
• Implementación del algoritmo en C, FreeBASIC o Python, y su validación en las instancias de prueba seleccionadas anteriormente
• Redacción de la idónea comunicación de resultados

Modelo adaptable de protocolos de comunicación y encaminamiento para el intercambio de información médica mediante dispositivos móviles inteligentes

 Descargar versión PDF

Profesores: Dr. Michael Pascoe Chalke y Dr. Enrique Rodríguez de la Colina

Resumen: Actualmente ha proliferado el uso de la telefonía móvil en el entorno social. Con el surgimiento de teléfonos inteligentes, se ha observado el advenimiento de múltiples aplicaciones móviles. Como consecuencia de los cambios en el ritmo de vida y la actividad de las personas, también se ha observado un incremento en los padecimientos cardiacos y metabólicos. Con la presencia ubicua de este tipo de equipos electrónicos, los cuales cuentan con una mayor cantidad de sensores y dispositivos, han surgido propuestas para aprovecharlos para realizar actividades de adquisición, monitorización y reporte de información médica prioritaria. En este proyecto de investigación se explorarán estrategias de comunicación y encaminamiento de información que puedan ser aplicadas para el envío de información médica con el propósito de reportar alguna condición crítica de salud y poder solicitar el envío de unidades de emergencia médica al lugar donde se encuentre el usuario afectado.

Objetivo general

• Diseñar un modelo adaptable de protocolos de comunicación y encaminamiento de información que operen en dispositivos móviles inteligentes con el propósito de enviar información médica que haya sido adquirida y monitorizada mediante este tipo de equipo electrónico. Esto con el fin de reportar la ocurrencia de un evento que pone en riesgo la vida del usuario y así pueda ser atendido a la brevedad por las unidades de emergencia.

Protocolos para la difusión de información en redes ad hoc vehiculares (VANET)

 Descargar versión PDF

Profesores: Dra. Elizabeth Pérez Cortés y Dr. Miguel López Guerrero

Resumen: Una red VANET (vehicular ad hoc network) es un tipo de red de comunicaciones especializada en el intercambio de información entre vehículos en donde los usuarios finales son usualmente los conductores. Ésta permitirá el desarrollo de sistemas de transportación inteligentes en donde una de las metas relevantes es disminuir el alto número de accidentes automovilísticos que ocurren cotidianamente. En la actualidad existen diversas iniciativas gubernamentales y privadas orientadas al desarrollo y adopción de esta tecnología. En las redes VANET los vehículos pueden comunicarse entre sí o con dispositivos colocados al lado del camino a fin de asistir a los conductores y así mejorar la seguridad durante un viaje. Un ejemplo de la aplicación de estas redes puede ser la notificación acerca de la presencia de algún obstáculo más adelante en el camino, el cual podría no ser visible a simple vista. También pueden usarse para comunicar situaciones de congestión, condiciones del camino, notificar condiciones del clima y en general informar datos de interés. El desarrollo de esta tecnología requiere de la búsqueda de soluciones a diversos retos prácticamente de todo tipo.

Objetivo general

• Identificar las estrategias encaminadas a mantener un alto desempeño en los protocolos existentes para la difusión de información en redes ad hoc vehiculares (VANET).

Objetivos específicos

• Identificar las diferentes estrategias incorporadas en los protocolos encaminadas a lograr altos niveles de eficiencia y eficacia en la difusión de información.
• Conocer los diferentes modelos de movilidad que se han propuesto para la representación del movimiento de automóviles.
• Evaluar la calidad relativa de las diferentes estrategias de difusión de información.
• Proponer un protocolo o una mejora a alguno ya existente basado en el conocimiento adquirido.

Sincronización en redes submarinas de sensores inalámbricos

 Descargar versión PDF

Profesor: Dr. Víctor Manuel Ramos Ramos

Resumen: Las redes inalámbricas de sensores (WSN, por sus siglas en inglés) están desarrolladas ampliamente en la actualidad para una amplia gama de aplicaciones. El objetivo principal de una WSN es colectar información sobre un conjunto de fenómenos. Dicho proceso no es trivial, ya que la vida de las baterías es limitada y, en consecuencia, tanto las transmisiones inalámbricas como las operaciones de cálculo deben minimizarse. Se comenzó a hablar ampliamente de las WSNs en 2004, luego de una conferencia magistral en IEEE Infocom 2004 ofrecida por Jim Kurose. Las UWSNs tienen el potencial de desarrollar aplicaciones antes inexploradas y de mejorar la habilidad de observar y de predecir el comportamiento de los océanos. La naturaleza del medio de transmisión en las UWSNs impone nuevos retos a las comunicaciones en redes de sensores, ya que las ondas de radio se propagan de forma distinta bajo el agua que en el aire. Por otro lado, los fenómenos que podrían ocurrir bajo el agua son definitivamente de una naturaleza muy peculiar y estos deben considerarse para un buen diseño en el despliegue de los sensores submarinos. Un gran número de aplicaciones de UWSNs requiere de métodos eficaces de sincronización de tiempo.

Objetivo general

• Diseñar e implementar un algoritmo de sincronización de tiempo para UWSNs.

Objetivos específicos

• Configurar el escenario de simulación.
• Obtener las muestras de tiempo requeridas para la ejecución del algoritmo de sincronización.
• Trazar gráficas de desempeño de calibración, de la pendiente del tiempo y del error incurrido en las estimaciones.
• Realizar un reporte sobre las UWSNs y sobre los resultados obtenidos con el protocolo propuesto.

Análisis y síntesis de tablas de enrutamiento para el Internet del IPv6

 Descargar versión PDF

Profesores: Dr. Miguel Ángel Ruiz Sánchez y Dr. César Jalpa Villanueva

Resumen: Los enrutadores son equipos fundamentales para el correcto funcionamiento de la Internet puesto que ellos se encargan de hacer llegar los paquetes de información hasta su destino por las mejores rutas y de manera transparente para los equipos terminales. Si el proceso de encaminamiento de los paquetes no se realiza de manera expedita se podrían producir degradaciones en la calidad de servicio que se percibirán como retrasos excesivos o incluso colapso de la red. Dentro de los enrutadores, la parte más crítica  del proceso de encaminamiento es la búsqueda LMP (Longest Matching Prefix) en la tabla de encaminamiento. Para los enrutadores pequeños, que no tienen que atender tráfico de datos elevado, este proceso no representa un gran problema pero para los enrutadores que se encuentran en el núcleo de la Internet, este proceso representa un gran reto porque tienen que soportar el tráfico elevado que les llega a través de sus enlaces de alta velocidad y por que el número de entradas que existe en sus tablas de encaminamiento donde realizan las búsquedas LMP puede ser de varios cientos de miles. El reto se vuelve aún más difícil cuando entra en escena el protocolo IPv6 para el cual las direcciones pasan a ser de 128 bits en vez de los 32 de IPv4 ampliando en varios órdenes de magnitud el espacio potencial de búsqueda.

Objetivo general

• Desarrollar una metodología para sintetizar tablas de enrutamiento IPv6 de gran tamaño que puedan utilizarse para la evaluación del desempeño de los algoritmos de búsqueda LMP en tablas IPv6.

Objetivos específicos

• Profundizar el conocimiento del protocolo IPv6 con énfasis en la estructura de las direcciones, las políticas de asignación y los protocolos de enrutamiento BGP.
• Desarrollar herramientas de programación para analizar la estructura y evolución de las tablas de enrutamiento de enrutadores del núcleo de la Internet tanto de IPv4 como de IPv6.
• Analizar el efecto de las políticas de asignación de direcciones y el progreso de la adopción de IPv6 en la evolución de las tablas de enrutamiento correspondientes.
• Establecer un modelo y los criterios que permitan realizar predicciones realistas de la forma en que evolucionarán las tablas de enrutamiento.
• Proponer una metodología y herramientas de programación para sintetizar tablas de enrutamiento IPv6 de gran tamaño.

Estudio y optimización del encaminamiento de mensajes en redes vehiculares

 Descargar versión PDF

Profesores: Dr. Víctor Manuel Ramos Ramos y Salvador González Arellano

Resumen: Se espera que las redes vehiculares ad hoc (VANETs, Vehicular Ad Hoc Networks) logren ofrecer una amplia variedad de servicios como advertencias sobre alguna violación de las señales de tránsito, asistencia para girar en las intersecciones, prevención cooperativa de accidentes, advertencias en puntos ciegos, control de cruce cooperativo, prevención sobre la velocidad en las curvas, por mencionar algunos. Para que la comunicación pueda ser llevada a cabo, el comité de sistemas de transporte inteligente de la sociedad de tecnología vehicular de la IEEE propuso el estándar para las redes vehiculares IEEE 802.11p, que comprende la capa física y la subcapa de control de acceso al medio. Las capas superiores se encuentran alineadas con la familia de protocolos IEEE 1609. Las aplicaciones que no involucran la seguridad del conductor son llamadas aplicaciones no críticas, las cuales tienen como propósito ofrecer servicios que faciliten la conducción del vehículo. Como ejemplo de estas aplicaciones tenemos el pago de servicios en puntos de cobro, el acceso a Internet, el manejo del tránsito vehicular, la elección de rutas para que el conductor llegue a su destino, entre otras. Para que este tipo de aplicaciones opere, es necesario que éstas transmitan información hacia vehıculos o puntos de acceso determinados.

Objetivo general

• Realizar un profundo estudio y análisis de los protocolos de encaminamiento para redes vehiculares y proponer un protocolo de encaminamiento que ofrezca un alto desempeño en términos de la confiabilidad, escalabilidad y un bajo retardo de extremo a extremo.

Objetivos específicos

• Analizar bajo los mismos escenarios los protocolos de encaminamiento más representativos de las distintas técnicas de encaminamiento presentadas en la literatura, con el fin de detectar sus ventajas y desventajas.
• Presentar una mejora, o un nuevo protocolo de encaminamiento que sea más eficiente que los presentados en la literatura para las redes vehiculares.

Deducción de la trayectoria de un nodo en una red ad-hoc móvil

 Descargar versión PDF

Profesores: Dr. Francisco García Jiménez (UNAM) y Dra. Elizabeth Pérez Cortés

Resumen: Los dispositivos móviles actuales pueden interconectarse de manera descentralizada para formar una infraestructura de comunicación temporal y autónoma conocida como red ad­ hoc móvil. En este tipo de redes los nodos tienen un radio de comunicación limitado y por ello cuando dos o más nodos desean comunicarse es común que un conjunto de nodos intermedios deban retransmitir los mensajes. En otros términos, las prestaciones que una red ad­ hoc móvil puede proveer están basadas en la cooperación entre los nodos que la componen. Para que esta cooperación se establezca es indispensable que cada nodo conozca a aquellos nodos que están en su radio de alcance, llamados nodos vecinos. La técnica básica para lograr esto es un protocolo basado en mensajes “hola” emitidos periódicamente por los nodos para notificar su presencia y, potencialmente, difundir otra información de interés.

Cuando los dispositivos móviles son portados por seres humanos, las trayectorias de dos o más nodos pueden coincidir en zonas de interés común para los usuarios y también mientras se mueven de un punto de interés a otro . En otras palabras, aún cuando un usuario no sea consciente de haber coincidido con otro, los dispositivos pueden registrar esa información y utilizarla, por ejemplo, para determinar si hay nodos con un cierto número de zonas de interés en común, individuos siguiendo la misma trayectoria, individuos con los que frecuentemente nos encontramos en un punto determinado o bien proporcionar esa información para colaborar en la búsqueda de una persona en particular.

Objetivo general

• Contribuir a la solución del problema de deducir la trayectoria de un nodo a partir de la información parcial proporcionada por nodos que fueron sus vecinos en un instante dado.

Objetivos específicos

• Conocer las soluciones al problema planteadas hasta ahora.
• Conocer la relación entre la proporción de nodos que cooperan proporcionando la información de su vecindario y la precisión con la que se deduce la trayectoria completa de un nodo en particular.
• Identificar los mecanismos distribuidos eficientes para colectar la información necesaria para deducir la trayectoria de un nodo en particular.
• Diseñar un algoritmo eficaz y eficiente para resolver el problema.

Distribución de contenidos en redes MANET utilizando el paradigma P2P

 Descargar versión PDF

Profesores: Dra. Elizabeth Pérez Cortés y Dr. Miguel López Guerrero

Resumen: Cerca de 25% del tráfico actual en Internet es causado por usuarios particulares que comparten contenidos digitales (fotografías, videos, música, textos, etc.) y se espera que el volumen de datos transferido por esta razón crezca a un ritmo del 26% anual durante los próximos cinco años. El soporte de tal nivel de actividad es la red par a par (P2P) en donde no hay estaciones con tareas especializadas como sucedería en un esquema cliente-servidor. En un sistema P2P todos los miembros de la red tienen una funcionalidad equivalente y cada uno de ellos puede proveer y descargar contenidos. La manera usual en la que opera la distribución de contenidos en redes P2P es la siguiente. Cuando un usuario desea obtener un contenido, primero utiliza un servicio de localización el cual le indica qué proveedor es capaz de enviárselo. Con esta información, la descarga puede darse involucrando sólo al solicitante y al proveedor. Ésta usualmente se efectúa dividiendo el contenido original en fragmentos y enviado cada uno de éstos al receptor. La eficiencia de este esquema básico de distribución puede mejorarse de diversas maneras.

Objetivo general

• Identificar estrategias exitosas para la construcción de protocolos de descarga de contenido en MANET.

Objetivos específicos

• Identificar las variantes del protocolo de descarga de BitTorrent para MANET.
• Conocer el rendimiento relativo de los protocolos de descarga de BitTorrent para MANET bajo un modelo de movilidad peatonal.