Fast Approximate Algorithms for Wireless Sensor Networks

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Sensor networks are one of the fastest growing network technologies. At the same time, however, they present new challenges. On the one hand, the sensors are given ambitious tasks of computing global properties using constantly changing and geographically distributed data. On the other hand, the sensors are significantly limited in their storage space, computation power, and communication bandwidth. To achieve their goals, sensornets need new theoretical foundations that integrate storage, computation, and communication, and enable the sensornet to pull its various resources together and funnel them toward its tasks. This project aims to create a formal framework for integrating storage, computation, and communication in sensornets. The proposed research assimilates three theories (sketching, property testing and network coding), into a synergetic design that greatly improves the communication throughput, while allowing for cheap computation and reduced storage space. Specifically, the proposed research consists of two components: - Network Sketching: a new architecture for sensornets that performs on-demand in-network compression of the data. This approach enables (lossy) compression of spatially correlated data at multiple sensors; manages network congestion by reducing data resolution as opposed to dropping some of the measurements; and naturally combines wireless network coding with sketching to boost the throughput of the wireless network. - Temporally Coherent Property Testing: a new computational model that extends the theory of property testing to a stream of temporally correlated data. This new paradigm enables quantifying the complexity of repeatedly checking for a particular property, and reduces the computational needs of sensor networks.