Pelos de mosca y sensores inalámbricos

Algoritmos basados en animales (II)

Imaginemos la siguiente situación: los administradores de una red social (puedes pensar en Facebook, por ejemplo) pretenden buscar un subconjunto de sus usuarios al que todo el resto esté conectado directamente (como amigos, seguidores, etc). El propósito es que, una vez conocido este subconjunto, si todos sus miembros enviasen el mismo mensaje éste llegaría a todos los usuarios de la red. Obviamente se busca el subconjunto con el menor número de miembros. Tomemos como ejemplo la siguiente red de pequeño tamaño, en la que cada nodo es un miembro de la red social y las aristas unen miembros conectados entre sí por una relación directa de «amistad».

20140618171803843

Fijémonos en los cinco nodos que están marcados en rojo en la siguiente figura, que son una posible solución al problema planteado: cualquiera de los nodos en gris está conectado a uno rojo, y no hay ningún nodo rojo que pueda eliminarse sin que alguno de los nodos de la red se quede sin recibir información directa. Dos nodos rojos tampoco están conectados entre sí.

20140618172114562

A este conjunto de nodos en un grafo que cumple la propiedad de que no están conectados entre sí, y el resto está conectado al menos a uno de ellos se le denomina conjunto independiente maximal (CIM).

El problema del cálculo del CIM es importante, además de en análisis de redes sociales, en redes de sensores inalámbricos. En estas redes algunos de los sensores son los responsables de recoger los datos de los sensores vecinos y transmitirlos a la central. Esta tarea consume mucha energía, por lo que conviene cambiar con frecuencia qué detectores van a realizar este trabajo, y al hacerlo hay que elegir un subconjunto al que estén conectados el resto de sensores. Ese es precisamente el CIM de la red.

Uno de los usos de las redes inalámbricas de sensores es la gestión de desastres medioambientales. En la imagen, los nodos grandes en rojo se encargarían de transmitir la información de los sensores (cámaras, micrófonos, etc) conectados a ellos (fuente).
Uno de los usos de las redes inalámbricas de sensores es la gestión de desastres medioambientales. En la imagen, los nodos grandes en rojo se encargarían de transmitir la información de los sensores (cámaras, micrófonos, etc) conectados a ellos (fuente).

Existen varios algoritmos que permiten calcular el CIM de un grafo, pero la mayoría necesitan conocer la topología del mismo, es decir, saber previamente qué nodos están conectados. Pero hay ocasiones en que esto no puede saberse. Esto ocurre por ejemplo con redes inalámbricas de sensores ambientales o en el control de grupos de robots, donde los movimientos de los sensores varían las posiciones y por tanto las relaciones de vecindad entre nodos. La solución a este problema la podemos encontrar en el desarrollo del sistema nervioso de las moscas.

Pelos de mosca

La mosca de la fruta (Drosophila Melanogaster) tiene en la superficie de su cuerpo un conjunto de pelos que actúan a modo de sensores mecánicos detectores de movimiento. Algunos de estos pelos más pequeños, denominados microsetas, se desarrollan a partir de un grupo de neuronas que son precursores de órganos sensoriales (POS).

microsetas_sm
Detalle de las microsetas en el notum de la mosca de la fruta.

Las células nerviosas que van a desarrollar estos pelos sensoriales se seleccionan durante la fase larvaria de la mosca dentro de grupos de 20-30 células, y la elección se realiza de forma que estos órganos sensoriales estén conectados a otras neuronas pero no directamente entre sí. Al hacer esta elección de neuronas, en la mosca se está resolviendo el problema del CIM. Y de una forma más sencilla y eficiente que algunos de los algoritmos clásicos para resolverlo.

Selección de precursores de órganos sensoriales (POS) en Drosophila Melanogaster durante la fase larvaria. (Inferior) Imágenes obtenidas mediante fluorescencia. Las zonas marcadas son los grupos de neuronas observados. (Superior) Evolución de las células preneurales (gris), POS (azul) y no POS (rojo). Fuente.
Selección de precursores de órganos sensoriales (POS) en Drosophila Melanogaster durante la fase larvaria. (Inferior) Imágenes obtenidas mediante fluorescencia. Las zonas marcadas son los grupos de neuronas observados. (Superior) Evolución de las células preneurales (gris), POS (azul) y no POS (rojo). Fuente.

¿Cómo se consigue este resultado? Parece ser que, en principio, todas las células tienen la capacidad de convertirse en pelos sensoriales. Así que algunas de ellas, por mero azar, se «proponen» como POS. Al hacerlo expresan altos niveles de la proteína transmembranal Delta, que se une a los receptores Notch de las células vecinas, inhibiendo la conversión de estas a POS. Este proceso continúa hasta que todas las células son o bien POS o bien están unidas a uno.

La célula que se convierte en POS (arriba a la izquierda) inhibe mediante la expresión de la proteína Delta la conversión de la célula vecina (abajo a la derecha) al unirse a la proteína Notch.
La célula que se convierte en POS (arriba a la izquierda) inhibe mediante la expresión de la proteína Delta la conversión de la célula vecina (abajo a la derecha) al unirse a la proteína Notch.

Si alguna vez has jugado al buscaminas entenderás mejor este ejemplo con la siguiente figura. Inicialmente podemos seleccionar cualquier casilla del «juego» (en gris). Cuando elegimos como POS una de las células aleatoriamente (en azul) las de su alrededor quedan marcadas (en rojo), porque lo que ya no pueden elegirse en el siguiente paso.

sop

Basándose en esta estrategia, un grupo de investigadores desarrolló un algoritmo para el cálculo del CIM que demostró ser más eficiente que otros algoritmos clásicos y no requería información del grafo, como el número de conexiones de cada nodo. Esto lo hace aplicable a problemas en los que la topología del grafo es variable, como los citados anteriormente de sensores medioambientales o grupos de robots.

Más información

  • Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, and Ziv Bar-Joseph. A Biological Solution to a Fundamental Distributed Computing Problem. Science, 2011; 331 (6014): 183-185 DOI: 10.1126/science.1193210

2 Comentarios

Participa Suscríbete

LucianoLuciano

Muy buen artículo. Se entiende perfectamente y está explicado de forma breve y sencilla, además el ejemplo del buscaminas es muy ilustrativo para visualizarlo.
Me está gustando mucho esta serie de artículos. Desde fuera uno puede pensar que la informática no es más que meter líneas en el ordenador y no se ve todo el trabajo que hay antes.

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>