Projecte final de carrera fet en col.laboració amb Ecole Polytechnique Federale de Lausanne

English: Consider a Wireless Sensor Network (WSN) where links can fail and the structure is varying a lot in function of the application implemented. We design a routing and encoding algorithm robust to arbitrary wireless connection. We also need a distributed data gathering in order to be able to reconstruct the signal from any node in the network and make the encoding and routing process independent from each other. We achieve all this requirements by implementing a gossip algorithm. Using this distributed algorithm to disseminate the information we study the problem of data reconstruction from partial observations in a WSN environment. We analyze two different data cases: In the first one, sensor measurements are scalar magnitudes (temperatures). In the second case we extend the model for high dimensional signals (images). For the first case, we want to reconstruct the temperature field values by observing partial sensor network measurements. Sensors disseminate their observation in network to one randomly chosen neighbour sensor by the gossip algorithm. After a certain number of message exchange cycles that is less than the total number of sensors in the network (under-determined system), we want to guarantee the accurate reconstruction of the network data. We compress the original signal in the data gathering stage using compressive sensing techniques. The obtained inverse problem based on node observations can be solved if we in addition introduce a priory data knowledge (smoothness). Our data is discretized so we develop an algorithm to minimize a non convex function, which is the hardest computational case. We propose a Viterbi List algorithm-based, using different techniques of energy regularization. Moreover, when the dimensions of sensed data are higher we treat the problem from another point of view. We assume that all the sensors participate in the data exchanging process; hence we receive observations from all the nodes in the network. Furthermore, each image is compressed before sending it using compressed sensing techniques. To solve the obtained inverse problem we assume a priory data knowledge of the signal (sparsity) and certain correlation amongst neighbour data. We propose two solutions, the first is a joint total variation (JTV) model based on the classical total variation regularization for the minimization of convex-continuous functions. On the other hand we approach the problem with a Joint matching pursuit algorithm (JMP) based on the l1 minimization of a convex function. For both methods we exploit the correlation amongst neighbour?s views to jointly decode each sensor signal, and improve the performance of the classical methods.

Castellano: Consideremos una red de sensores inalámbrica (WNS) donde las conexiones pueden fallar i la estructura de la red varía mucho en función de la aplicación que diseñemos. Hemos implementado un algoritmo para la codificación i enrutamiento de la información que es robusto a las conexiones arbitrarias que se dan en una WNS. Necesitamos también un algoritmo distribuido para recopilación de las distintas medidas de los sensores con el fin de poder reconstruir los datos originales des de cualquier punto de la red i de este modo hacer independientes el proceso de codificación i enrutamiento. Con estos objetivos hemos implementado un algoritmo distribuido para la difusión de los datos a través de la red llamado gossip algorithm. Utilizando este algoritmo distribuido hemos estudiado la reconstrucción de los datos disponiendo solamente de las observaciones de parte de los nodos de la red en un entorno WNS. El estudio se realiza para dos tipos distintos de datos: en el primero las medidas de los sensores son magnitudes escalares (temperaturas) i en el segundo hemos ampliado el modelo para señales multidimensionales (imágenes). En el primer caso, queremos reconstruir los campos de temperatura de todos los sensores teniendo solo parte de las medidas de la red. Los sensores propagan sus datos hacia un sensor vecino elegido aleatoriamente siguiendo el algoritmo gossip. Después de cierto número de ciclos de intercambio de información, que es menor que el número de sensores (sistema indeterminado) queremos garantizar la reconstrucción de todos los datos de la red des de cualquier punto de la misma. Comprimimos los datos en la fase de propagación i adquisición utilizando técnicas de compressive sensing. Se obtiene un problema inverso (inverse problem) que solo se puede solucionar si tenemos algún tipo de información a priori de los datos (variación suave entre vecinos). Las medidas de los sensores son discretizadas por tanto implementamos un algoritmo para minimizar una función no convexa, que es el caso más caro computacionalmente. Proponemos una solución basada en el algoritmo de Viterbi utilizando distintas técnicas de regularización de energía. Por otro lado cuando trabajamos con imágenes abordamos el problema des de otro punto de vista. Asumimos que todos los nodos participan en el proceso de intercambio de datos, por tanto tenemos las observaciones de todos los sensores. Cada imagen es comprimida antes de ser enviada a través de la red utilizando técnicas de compressive sensing. Para solucionar este inverse problem asumimos que los datos son sparse i que existe cierta correlación entre las señales de sensores vecinos. Proponemos dos soluciones, la primera es un modelo de joint total variation (JTV) basado en el modelo clásico de la regularización de la variación total, para la minimización de funciones convexas. La segunda es joint matching pursuit (JMP) basado en la minimización l1 de funciones convexas. Para los dos métodos introducimos la correlación entre sensores vecinos para decodificar conjuntamente cada imagen i así aumentar el rendimiento de los algoritmos clásicos.

Català: Considerem una xarxa de sensors sense fils (WSN) on les connexions poden fallar i la estructura de la xarxa varia molt en funció de la aplicació que dissenyem. Hem implementat un algoritme per a la codificació i enrutament de la informació que es robust a les connexions arbitraries que es donen en una WSN. També necessitem un algoritme distribuït per a la recopilació de les diferents mesures dels sensors per tal de poder reconstruir les dades originals des de qualsevol node de la xarxa i així fer que el procés de codificació i enrutament de les dades siguin independents. Amb aquests objectius hem implementat un algoritme distribuït per a la difusió de les dades a traves de la xarxa anomenat gossip algorithm. Utilitzant aquest algoritme distribuït, hem estudiat el problema de la reconstrucció de les dades disposant nomes les observacions de part dels nodes de la xarxa en un entorn WSN. L'estudi es realitza per dos tipus diferents de dades: en el primer les mesures dels sensors son magnituds escalars (temperatures) i en el segon hem ampliat el model per senyals multidimensionals (imatges). En el primer cas, volem reconstruir els camps de temperatura de tots els sensors tenint nomes part de les mesures de la xarxa. Els sensors propaguen les seves dades cap a un sensor veí triat aleatòriament seguint l'algoritme gossip. Desprès d'un cert numero de cicles d'intercanvi d'informació que es menor que el numero total de sensors (sistema indeterminat) volem garantir la reconstrucció acurada de les dades de tota la xarxa des de qualsevol punt de la mateixa. Es a dir, comprimim les dades en la fase de propagació i adquisició de la informació utilitzant tècniques de compressive sensing. S'obté un problema invers (inverse problem) que només pot ser solucionat si assumim algun tipus de coneixement a priori de les dades (variació suau entre veïns). Les mesures dels sensors son discretitzades per tant hem implementat un algoritme per minimitzar una funció no convexa, que es el cas computacionalment mes car. Proposem una solució basada en l'algoritme de Viterbi utilitzant diferents tècniques per a la regularització d'energia. Per altra banda quan treballem amb imatges abordem el problema des d'un altre punt de vista. Assumim que tots els nodes participen en el procés d'intercanvi de dades, per tant tenim les observacions de tots els sensors. Cada imatge es comprimida abans de ser enviada a traves de la xarxa utilitzat tècniques de compressive sensing. Per solucionar aquest invers problem assumim que les dades son sparse i que existeix certa correlació entre les senyals de sensors veïns. Proposem dues solucions, la primera es un model de Joint total variation (JTV) basat en el model clàssic de la regularització de la variació total, per a la minimització de funcions convexes . La segona es Joint matching pursuit (JMP) basat en la minimització l1 de funcions convexes. Pels dos mètodes introduïm la correlació entre sensors veïns per decodificar conjuntament cada imatge i així augmentar el rendiment dels algoritmes clàssics.