Un equipo de investigación norteamericano e israelí acaba de hacer pública una nueva fórmula matemática que permite una distribución mucho más rápida de la información a través de redes autoorganizadas que presentan puntos de estrangulamiento. El método podría acercar el concepto casi utópico del "polvo inteligente" al día a día de la industria informática.


Por Elena Higueras de Tendencias Científicas.

  Del mismo modo que los sensores que detectan el tacto y el movimiento en los teléfonos móviles se hacen cada vez más pequeños, baratos y fiables, los fabricantes de ordenadores están comenzando a tomar en serio la vieja idea del "polvo inteligente" (en inglés, smartdust) , o lo que es lo mismo, una red inalámbrica de minúsculos sensores microelectromecánicos, robots o dispositivos que pueden detectar señales de luz, temperatura, vibraciones, etc. Su colocación dispersa alrededor de un hospital, por ejemplo, podría aportar información sobre la temperatura o la humedad registrada en el interior del edificio o, incluso, seguir los pasos de los pacientes.

 Pero para que tales redes puedan tomar decisiones colectivas, como reconocer que un volcán está cada vez más agitado, necesitan integrar la información recogida por cientos o miles de dispositivos.

 El problema reside en que las redes de sensores baratos dispersos en entornos muy variables son propensas a formar "cuellos de botella", es decir, puntos de escasa conectividad por los que deben pasar todos los datos transmitidos para llegar a la totalidad de la red.

 Sin embargo, el escollo derivado de la existencia de cuellos de botella o puntos de estrangulamiento puede tener los días contados si se materializa la última idea de un grupo de científicos, con representación estadounidense e israelí, presentada el pasado fin de semana en el "2011 ACM-SIAM Simposio sobre algoritmos discretos" celebrado en Nueva Orleans. Según un comunicado del Instituto Tecnológico de Massachusetts, Keren Censor-Hillel, una postdoctorada del Laboratorio de Inteligencia Artificial e Informática del MIT, y Hadas Shachnai, del Instituto Israelí de Tecnología Technion, dieron a conocer un nuevo algoritmo que resuelve el problema de los cuellos de botella de una forma mucho más eficaz que sus predecesores.

 El algoritmo está diseñado para trabajar en las llamadas redes ad hoc, una red inalámbrica descentralizada en la que ningún dispositivo actúa como supervisor de toda la red en su conjunto. En una red de sensores inalámbricos baratos, por ejemplo, cualquier dispositivo podría fallar: su batería podría agotarse o su señal podría ser obstruida. Por ello, la red tiene que ser capaz de adaptarse a la desaparición de cualquier dispositivo, lo que obliga a que no contenga ninguno con demasiada responsabilidad. Sin un supervisor la red no conoce la localización de sus puntos de estrangulamiento, pero eso no es un problema para el nuevo algoritmo, ya que como afirma Censor-Hillel "da igual dónde estén los cuellos de botella, lo importante es hacer frente a su existencia".

 Comunicación ronda a ronda

 El trabajo de los investigadores se basa en la premisa de que la comunicación entre dispositivos de red se lleva a cabo en rondas. En cada una, un dispositivo puede iniciar la comunicación solo con otro, pero puede intercambiar una cantidad ilimitada de información con ese dispositivo. Durante cada intercambio, éste pasa la información que ha recibido de otros dispositivos. Si hablamos de sensores que miden las variables de un volcán, los datos podrían hacer referencia, por ejemplo, a la medición más reciente que ha registrado cada dispositivo de la actividad sísmica en la zona.

 El algoritmo funciona por la alternancia de las estrategias de comunicación ronda a ronda. En la primera, se selecciona un dispositivo vecino al azar al que enviará toda la información que tenemos (puesto que es la primera ronda, se limita a las medidas que él mismo ha realizado). En esa misma ronda, otros dispositivos pueden contactar con él y enviarle su información. Sin embargo, en la segunda ronda no basta con seleccionar un vecino al azar, sino que se elige uno cuya información todavía no se ha recibido. A continuación, en la tercera, vuelve a elegirse un vecino aleatoriamente. Al final de esa ronda, ya que cada dispositivo en la red envía toda la información que tiene, también recibe no sólo las mediciones realizadas por los equipos en contacto, sino las mediciones hechas por los vecinos de sus vecinos, e incluso los vecinos de los vecinos de los vecinos. En la cuarta ronda, de nuevo selecciona un dispositivo cuya información no ha recibido, en la quinta, otra vez un dispositivo al azar, y así sucesivamente.

 "La idea es que los pasos aleatorios que tomo me permiten difundir la información rápidamente dentro de mi propio subconjunto bien conectado", explica la investigadora del MIT. Pero en las rondas alternas, cada dispositivo detecta los dispositivos de los que no ha oído hablar, garantizando que la información llegue rápidamente a todos, incluidos los que se comunican a través del cuello de botella.

 A pesar de que para muchos científicos, como el experto en análisis de redes y profesor de informática en la Universidad Sapienza de Roma Alessandro Panconesi, "el nuevo algoritmo es una contribución interesante", no es la solución definitiva al problema de los cuellos de botella. En su opinión, la versión actual del algoritmo, en la que en cada ronda cada dispositivo envía toda la información que recibió, no sería práctica: "El algoritmo es muy costoso en términos de la gran cantidad de información que necesita intercambiar. Sin embargo, el desarrollo de una versión con menor ancho de banda no es improbable".

 Por su parte, uno de los artífices del sistema, Censor-Hillel, admite que lo esencial en el futuro es obtener el ancho de banda práctico, pero por el momento sigue investigando para hallar el algoritmo que mejor funcione en el caso ideal de ancho de banda ilimitado.

FUENTE :http://www.laflecha.net/canales/blackhats/noticias/un-nuevo-algoritmo-acelera-el-intercambio-de-informacion-en-redes