| Wireless sensor networks stand to enable data collection from a multitude of environments on unprecedented scales through ease of deployment and measurement automation. Sensor nodes transmit readings to an offline base station via radio. Nodes are energy-constrained, with radio dominating consumption. It is crucial to develop methods for processing queries over the network that minimize radio transmission. This thesis develops and evaluates such methods.; Environmental modeling applications motivate focus on continuously collecting all data. Processing this query in relational databases is straightforward; the naive approach in sensor networks is prohibitively expensive. The novel model-encoding suppression scheme exploits correlations present in the measured readings to produce continuous query results without continuous messaging, whose accuracy is guaranteed within prescribed bounds, even if the model proves inaccurate. The most effective models are those incorporating temporal and spatial correlations. While building schemes to leverage these individually is straightforward, combining them is not. The proposed CONCH scheme demonstrates their coupling by temporally monitoring spatial constraints, and determines the set of constraints that minimizes reporting cost.; Sensor networks are vulnerable to failure, a problem detrimental to suppression schemes; suppressed reports cannot be distinguished from failed ones. Schemes can be made robust to failure through redundant constraints and/or redundancy piggybacked on existing constraints. The proposed BAYS AIL framework uses Bayesian analysis to infer missing data, whether from failure or suppression, exploiting the suppression scheme and redundancy to constrain possible settings.; Other query types provide unique opportunities for efficient processing. This thesis additionally discusses the following queries: continuous extreme-value, ad-hoc top-k, and many-to-many aggregation. The solutions presented continue to exploit correlation, but also the ideas that not all data is needed to answer a query, that nodes should encode as much application logic as possible, that samples can be used to indirectly optimize over models, and that a set of queries with multiple shared sources and destinations can leverage a combination of multicast and in-network aggregation.; The methods presented are evaluated analytically and experimentally through simulation, and demonstrate energy cost improvement over existing methods, and provide general insight into sensor network query processing. |
