Probabilistic Models and Algorithms for Energy-Efficient Large and Dense Wireless Sensor Networks

Abstract

The concept of sparsity is fundamental to understanding data collection in foreseeable large scenarios. This intuition is based on the fact that future analytics will only perform efficiently over compact information domains. This scenario is even more critical in Wireless Sensor Networks (WSN), since small sensors suffer from major limitations. Hence, Compressive Data Aggregation (CDA) is required to alleviate the work load of the sensors. This research has proposed a compressed sensing-based protocol which follows a random sensing principle. This principle allows for the characterization of sensor interactions using methods from stochastic geometry. This work will deliver: a) a methodology to jointly analyze the compression and communication aspects of CDA in WSNs and b) a novel protocol that effectively implements compressed sensing with collision avoidance. It is called Stochastic Compressive Data Aggregation (S-CDA). Although there have been great advances, there is a lack of methodologies to jointly analyze the compression and communication aspects of CDA in WSNs. Consequently, this dissertation seeks to bridge this gap.

Resumen: Los futuros sistemas de análisis de datos funcionarán de forma eficiente sólo sobre dominios compactos de información. Las Redes Inalámbricas de Sensores (Wireless Sensor Networks, WSN) necesitan operar en armonía con aquellos dominios. La razón es que los diminutos sensores que conforman una WSN sufren de grandes limitaciones. En este contexto, el concepto de compresibilidad es fundamental para formular modelos y desarrollar soluciones. Aunque hubo grandes progresos en el análisis de recogida de datos en WSNs, hay una falta de metodologías que analicen de forma conjunta los aspectos de compresión y comunicación. La presente tesis busca llenar ese vacío utilizando técnicas de sensado compresivo y geometría estocástica. Concretamente, la tesis tiene como objetivos: primero, explicar, de forma formal, las propiedades que deben de tener las funciones de compresibilidad; segundo, desarrollar métodos para caracterizar, de forma estadística, la potencia de interferencia en redes inalámbricas; y tercero, diseñar un protocolo para la recogida eficiente de datos en WSNs a partir de un modelo probabilístico que considere los aspectos de compresión y comunicación.

Laitteiden internetin ja muiden tietojärjestelmien tuottama erittäin laajat tietomassat aiheuttavat haasteita datan keräämiselle ja analytiikalle. Erityisen haasteellista suurien datamäärien kerääminen on langattomissa anturiverkoissa, antureiden laskentakyvyn, muistin, tiedonsiirron ja energian rajoitteiden takia. Näin ollen langattomissa anturiverkoissa tarvitaan uusia tehokkaita ja luotettavia menetelmiä tiedon kokoamiseksi yhteen. Harvuuden käsite mahdollistaa datan keruuprosessin paremman ymmärryksen sekä uusien kompaktiin esitystapaan perustuvien tehokkaiden datan keruu ja analyysimenetelmien kehittämisen. Pakattu datan kokoaminen (Compressive Data Aggregation, CDA) mahdollistaa työkuorman vähentämisen datan keräys- tai fuusiopisteessä. Tämä puolestaan pidentää akkujen kestoa ja kasvattaa verkon toiminta-aikaa. Tässä työssä esitetään pakattuun mittaukseen perustuva MAC-protokolla radioresurssien jakamiseksi antureiden välillä huomioiden CDA:n tuomat mahdollisuudet. Protokollan satunnaisuus mahdollistaa sen toiminnan mallintamisen käyttämällä hiljattain esitettyjä stokastisen geometrian menetelmiä. Kehitetty MAC-protokolla muistuttaa kantoaallon tunnistukseen perustuvaa CSMA-protokollaa ja sen toiminnalle on todennäköisyyteen perustuvat rajat. Erityisesti tässä työssä esitetään a) metodologia langattomien anturiverkkojen datan pakatun kokoamisen ja tietoliikenteen yhtäaikaiseen analyysiin; b) uusi stokastinen datan kokoaminen (S-CDA) MAC-protokolla, joka tehokkaasti yhdistää pakatun mittauksen ja pakettien törmäyksen välttämisen. Aikaisempi tutkimus on analysoinut CDA:ta epäyhtenäisesti olettaen joko tietoliikenteen tai pakatun mittauksen ideaaliseksi. Tässä työssä tarkastellaan näitä molempia yhdessä.