Efficient linear computation on wireless sensor networks

Resumen

La rápida proliferación de las Redes Inalámbricas de Sensores (RIS) ha animado a la comunidad científica a diseñar y desarrollar algoritmos rápidos y eficientes para estas redes. Las RIS se caracterizan por tener unas características muy restrictivas, de las cuales es importante resaltar la limitada capacidad de cálculo y escasos recursos energéticos. En muchos casos, las RIS carecen de una entidad central que regule la comunicación dentro de la red y, por tanto, el conocimiento que tiene cada nodo sobre el resto de la red es muy limitado. Calcular la proyección de una señal observada y muestreada espacialmente sobre un subespacio de dimensión menor es esencial en diversas aplicaciones, especialmente a la hora de reducir la distorsión introducida durante la medición en cada sensor. En general, la medición de un único sensor puede ser poco fiable debido al ruido o a fallos. No obstante, si el entorno que se está monitorizando no varía abruptamente, la proyección sobre un subespacio mejorará la fiabilidad de la medida gracias a la interacción entre nodos. Calcular esta proyección es un problema de interés en varias aplicaciones donde existen subespacios de interés bien definidos (por ejemplo, mapas espectrales en radio cognitiva). Por un lado, en esta tesis diseñamos una estrategia energéticamente eficiente para RIS para obtener, de una forma distribuida, la proyección de una señal observada y muestreada espacialmente sobre un subespacio de dimensión menor. A diferencia de los algoritmos gossip tradicionales donde se separan la codificación de canal y la computación, nuestra estrategia combina códigos computacionales y un nuevo algoritmo de estilo gossip con ciertas reglas de comunicación, de forma que obtenemos una disminución tanto en el tiempo de cálculo necesario como en el consumo energético con respecto a un sistema de separación. También calculamos una cota superior del número de iteraciones necesarias para calcular la proyección de forma distribuida, así como el tiempo $\epsilon$-promedio cuando la proyección que buscamos es simplemente la media. Por otro lado, desarrollamos una nueva estrategia para obtener la matriz de transición del problema de la proyección en un subespacio de forma distribuida a través de algoritmos de estilo gossip en RIS. Hasta ahora, la matriz de transición tenía que calcularse fuera de la red por un tercero y después ésta se comunicaba a la red. Aunque el cálculo exacto de la matriz de transición óptima no es factible de forma distribuida, desarrollamos un algoritmo basado en resultados bien conocidos del álgebra lineal y de algoritmos genéticos para obtener una aproximación de la matriz de transición óptima con la precisión deseada. Por último, presentamos parte de un simulador de sistemas de comunicaciones que ha sido parcialmente desarrollado para esta tesis.