IV Carnaval de Matemáticas: Homología, redes de sensores inalámbricos y otras aplicaciones de la topología algebraica

Por Francisco R. Villatoro, el 14 mayo, 2010. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Science ✎ 1

Esta semana se celebran dos eventos en paralelo que no puedo obviar correlacionar entre sí. Por un lado, la IV Edición del Carnaval de Matemáticas, cuyo anfitrión es el blog Zurditorium (ya he escrito una entrada). Y por otro lado, la celebración en Málaga de la «Spring School on Applied and Toric Topology,» del 10 al 14 de mayo de 2010, organizada por la Red Española de Topología, que incluye un curso interesantísimo del genial Robert Ghrist, «Applications of algebraic topology to science and engineering,» que nos presenta aplicaciones de la topología en robótica, teoría de redes, procesamiento de señales, etc. Voy a destacar una de ellas, donde Ghrist ha hecho importantes contribuciones, la aplicación de la homología al diseño de redes de sensores inalámbricos y antenas de telefonía móvil.

Para muchos, la topología es la rama de las matemáticas más alejada de las aplicaciones prácticas. Nada más lejos de la realidad, tiene múltiples aplicaciones en ciencia e ingeniería, incluso aplicaciones industriales. Para la mayoría de los lectores de este blog, «homología» es un «palabro» excesivamente técnico, sin significado alguno. La homología es una rama de la topología algebraica. La topología algebraica utiliza herramientas del álgebra (básicamente grupos) para estudiar las propiedades de espacios topológicos (superficies e hipersuperficies en varias dimensiones). Por ejemplo, la clasificación de todas las superficies (bidimensionales) cerradas que se pueden sumergir en un espacio de tres dimensiones se puede realizar en base al número de agujeros que presentan, un resultado clásico y ampliamente conocido de la topología algebraica (obtenido en el s. XIX). Las superficies son topológicamente equivalentes a una esfera (no tiene agujeros), a un donut (tiene un agujero), a un doble toro (tiene dos agujeros), etc. El proceso de contar los agujeros de una superficie es una asignación de una propiedad algebraica a la superficie. La homología utiliza las herramientas del álgebra homológica para asociar una sucesión de grupos abelianos a un objeto matemático dado, por ejemplo, una superficie. Los grupos de homología permiten calcular muchas propiedades de un espacio topológico (superficie), que a veces lo caracterizan completamente o al menos ayudan a clasificarlo.

La homología más famosa y utilizada es la homología simplicial, que asocia una malla triangular a una superficie (una malla de n-símplices a una n-hipersuperficie). La homología simplicial permite generalizar el famoso teorema de la característica de Euler a hipersuperficies. En tres dimensiones, para una superficie con dos dimensiones, la característica de Euler-Poincaré es un invariante topológico que se calcula mediante χ = CA + V donde C, A y V son los números de caras, de aristas y de vértices, respectivamente, de la triangulación (en el caso más sencillo de un poliedro, o politopo en n dimensiones). Si el poliedro no tiene agujeros, es decir, es topológicamente equivalente (u homeomorfo) a una esfera, tenemos que χ(S²) = CA + V = 2 (que es la famosa fórmula de Euler). Por ejemplo, para un cubo tenemos 6 – 12 + 8 = 2, o para un tetraedro tenemos 4 – 6 + 4 = 2. La característica de Euler-Poincaré es aplicable a cualquier triangulación de una superficie y nos permite simplemente contando (caras, aristas, y vértices) determinar si dos superficies son equivalentes entre sí o no.

Los elementos de una triangulación de una superficie (vértices, aristas y caras) están relacionados entre sí por la operación «ser borde de» de tal forma que los bordes de las caras son aristas y los bordes de las aristas son vértices. Este procedimiento define un complejo de cadenas donde el conjunto vacío es borde del espacio de todos los vértices, que son borde del espacio de todas las aristas, que son borde del espacio de todos las caras. Los grupos de homología se definen a partir de estos complejos de cadena, asociando un grupo a cada operación «ser borde de» y gracias a la propiedad de que el borde de un borde es el conjunto vacío. Sin entrar en detalles matemáticos basta pensar un poco para generalizar este procedimiento a «triangulaciones» de superficies en 3D basadas en tetraedros y en general en n dimensiones basadas en n-símplices (el análogo n-dimensional de un tetraedro). Una superficie se caracteriza homológicamente describiendo la sucesión de los grupos de homología de sus triangulaciones. Lo sorprendente es que estos grupos de homología no dependen de la triangulación concreta utilizada para calcularlos sino de las propiedades topológicas de la superficie misma. En este sentido los grupos de homologías son fáciles de calcular. Por todo ello son una herramienta muy poderosa para describir las propiedades topológicas de una superficie lo que los hace muy útiles en la práctica.

Un sensor es un dispositivo que mide alguna característica de un entorno, retornando información sobre ella. Para explorar con detalle un entorno podemos utilizar pocos sensores muy complejos y costosos, o utilizar muchos sensores muy sencillos y baratos. La segunda opción es la preferida en la actualidad, pero requiere resolver el problema de integrar la información «local» de cada sensor en una representación «global» del entorno. El cuerpo humano contiene varios ejemplos de sistemas (o redes) de sensores, por ejemplo, la retina de nuestros ojos que está formada por células fotosensibles (sensores) de tipo cono y bastón, que se conectan gracias a neuronas (nervios) con el cerebro. Somos capaces de ver gracias a que el cerebro es capaz de integrar la información individual de cada cono y bastón obteniendo una representación abstracta de nuestro entorno (que elimina puntos ciegos, pero que sufre ciertas paradojas visuales).

Las técnicas matemáticas necesarias para analizar una red de sensores e integrar la información que proveen en una representación abstracta del entorno requieren realizar una transición entre información local y global. Esta transición es lo que logra la homología (simplicial) con una triangulación de una superficie, transformando números de vértices, aristas y caras (propiedades de carácter local) en propiedades globales (como ser equivalente a una esfera o a un dónut, o el número de agujeros que tiene la superficie). Pongamos un ejemplo, el problema de la cobertura en una red de sensores. Cada sensor recibe información de un región a su alrededor, supongamos que es un círculo de cierto radio. Queremos recibir información de una región grande. ¿Cúantos sensores necesitamos? ¿Cómo hay que distribuirlos para garantizar que no haya huecos sin cubrir? ¿Cómo podemos diseñar esta red de tal forma que sea robusta a los fallos en algunos sensores? Estos problemas se pueden describir matemáticamente como problemas homológicos en redes y grafos, lo que permite diseñar algoritmos por ordenador eficientes para su resolución que se apoyan en las herramientas de la homología.

¿Realmente son necesarias estas técnicas matemáticas? La mayoría de los ingenieros pensará que no, que tener que aprender topología algebraica para resolver este tipo de problemas no merece la pena. Sin embargo, la homología tiene varias ventajas relacionadas con el análisis matemático del algoritmo que se utilice. Las herramientas topológicas son muy abstractas pero permiten realizar cálculos matemáticos, como determinar la complejidad computacional de un algoritmo, que sin ellas se tornan muy difíciles. Un ingeniero puede diseñar un algoritmo que parece eficiente, pero un topológo (o un ingeniero con conocimientos de topología) puede llegar a demostrar que el algoritmo es eficiente. Por supuesto, hoy en día, este trabajo está más en manos de los topólogos que de los ingenieros, limitándose estos últimos ha «copiar y usar» el algoritmo eficiente descubierto por los primeros, sin preocuparse por más detales. Aún así, como estos algoritmos utilizan el lenguaje de la homología, el ingeniero se ve obligado a aprender dicho lenguaje para poder entenderlo y aprovecharse de todas sus ventajas.

Ya hay algoritmos eficientes para muchos problemas, como el problema de la cobertura. Todos hemos padecido el problema de que nuestro teléfono móvil se quede sin cobertura. Las antenas de los móviles que son instaladas en el tejado de ciertos edificios de nuestras ciudades, tienen un cono de cobertura (en función de la potencia que pueden radiar). Nuestro teléfono móvil tiene cobertura si es capaz de alcanzar («ver» o «sentir») al menos una de las antenas que se encuentran en su entorno. Las antenas se diseñan de forma estática para garantizar que la cobertura de una cierta región sea completa (no haya «agujeros» sin cobertura). Este diseño es costoso pero se realiza solamente una vez. Los algoritmos utilizados no pueden ser usados de forma eficiente para el diseño de una red de sensores inalámbricos, en la que los pequeños sensores se comunican los unos con los otros y transmiten así la información que obtienen del entorno a través de la red hasta alcanzar un punto en el que es almacenada y procesada. Los algoritmos de comunicación han de ser muy eficientes y al mismo tiempo poco costosos. Por ello, los ingenieros tienen que lidiar con las herramientas matemáticas más avanzadas para poder utilizar los mejores algoritmos disponibles. Hay muchos problemas que le quitarían el sueño a un ingeniero, como las redes de sensores dinámicas, en la que los pequeños sensores son móviles, o las redes de sensores en entornos agresivos que provocan fallos reiterados en muchos de los sensores. Para estos problemas los topólogos algebraicos (computacionales) están diseñado nuevos algoritmos eficientes. Lo abstracto, aún lo más abstracto, acaba siendo útil, siempre.

Los interesados en más detalles disfrutarán del artículo de Vin de Silva y Robert Ghrist, «Homological Sensor Networks,» Notices of the AMS 54: 10-17, January 2007. También os recomiendo el breve apunte de Barry A. Cipra, «Homology:An IdeaWhose Time Has Come,» SIAM News 42, December 2009. Para los amantes de cosas un poco más técnicas recomiendo los artículos de Vin de Silva, Robert Ghrist, Abubakr Muhammad, «Blind Swarms for Coverage in 2-D,» y de Erin W. Chambers, Vin de Silva, Jeff Erickson, Robert Ghrist, «Rips Complexes of Planar Point Sets.» Además, podéis buscar los artículos de Ghrist en ArXiv.



1 Comentario

  1. Muy interesante el artículo, solo un apunte menor, el algebra homologica no es una rama de la topologia algebraica. Aunque si es cierto que se descubriera en el contexto de la topologia algebraica, el algebra homologica se utiliza en muchos otros campos (cohomologia singular,simplicial,de deRham… para la topologia; cohomologia de haces, de Czech, de esquemas para geometria algebraica; cohomologia de grupos, etale, l-adica para teoria de numeros; y directamente teoria de delta-funtores para algebra homologica pura y dura).

Deja un comentario