El canto de una rana: algoritmo para redes inalámbricas

¿Cómo se pueden pintar los nodos de una red con el menor número de colores posible y sin que haya dos nodos consecutivos del mismo color? Un equipo de investigadores de la Universitat PolitÁ¨cnica de Catalunya ha encontrado una solución para este problema matemático con la ayuda de unos compañeros muy especiales: las ranas arborícolas japonesas (Hyla japonica).

Los machos de estos anfibios emiten sus cantos para atraer a las hembras, que así reconocen el origen de la llamada y localizan al pretendiente. El problema surge cuando dos machos están demasiado cerca y cantan a la vez.

Las hembras quedan confundidas y no pueden determinar de dónde proceden las llamadas, por lo que los machos han tenido que aprender a ‘desincronizar’ sus cantos, es decir, a no cantar al mismo tiempo para que se los pueda diferenciar.

“Dado que no hay ningún tipo de control central que organice esta ‘desincronización’, el mecanismo se puede considerar como un ejemplo de autoorganización en la naturaleza”, explica Christian Blum. El científico, junto a su compañero Hugo Hernández, se ha inspirado en este comportamiento para “resolver el denominado ‘problema de coloración de grafos’ de forma distribuida”.

Un grafo es un conjunto de nodos conectados, y operar de manera ‘distribuida’ significa que, como en el caso de los cantos ‘desincronizados’ de la rana, no hay ningún tipo de control central que ayude a solucionar el problema con una visión global y con toda la información sobre la situación.

Del mismo modo, los investigadores han ideado un nuevo algoritmo para asignar los colores a los nodos de la red cumpliendo la condición de que cada par de nodos conectados no tengan el mismo color. El objetivo final es generar una solución válida que use el mínimo número de colores.

Aplicación en conexiones WiFi

“Este tipo de coloración de grafos es la formalización de un problema que surge en muchos ámbitos del mundo real –destaca Blum– como en la optimización de las modernas redes inalámbricas, que no tienen un estructura predeterminada, a través de técnicas para reducir pérdidas en los paquetes de información y mejorar la eficiencia energética”.

Esta investigación se enmarca en el campo de la ‘inteligencia de enjambres’, una rama de la inteligencia artificial cuyo objetivo es diseñar sistemas inteligentes con múltiples agentes. Para ello se toma como inspiración el comportamiento colectivo de sociedades animales como las colonias de hormigas, las bandadas de aves, los bancos de peces y las ranas, como en este caso.