The in–network aggregation paradigm in sensor networks provides a versatile approach for evaluating aggregate queries. Traditional
approaches need a separate aggregate to be computed and communicated for each query and hence do not scale well with the number
of queries. Since approximate query results are sufficient for many applications, we use an alternate approach based on summary
data–structures. We consider two kinds of aggregate queries:
location range queries that compute the sum of values reported by sensors in a given location range, and
value range queries that compute the number of sensors that report values in a given range. We construct summary data–structures called
linear sketches, over the sensor data using in–network aggregation and use them to answer aggregate queries in an approximate manner at the
base–station. There is a trade–off between accuracy of the query results and lifetime of the sensor network that can be exploited
to achieve increased lifetimes for a small loss in accuracy. Most commonly occurring sets of range queries are highly correlated
and display rich algebraic structure. Our approach takes full advantage of this by constructing linear sketches that depend
on queries. Experimental results show that linear sketching achieves significant improvements in lifetime of sensor networks
for only a small loss in accuracy of the queries. Further, our approach achieves more accurate query results than the other
classical techniques using Discrete Fourier Transform and Discrete Wavelet Transform.
Keywords Sensor networks - In–network aggregation - Linear sketching - Approximate query answering
This work was supported in part by NASA under Cooperative Agreement NCC5–315.