Approximate Continuous Aggregation via Time Window Based Compression and Sampling in WSNs

ABSTRACT

In many applications continuous aggregation of sensed data is usually required. The existing aggregation schemes usually compute every aggregation result in a continuous aggregation either by a complete aggregation procedure or by partial data update at each epoch. To further reduce the energy cost, we propose a sampling-based approach with time window based linear regression for approximate continuous aggregation. We analyze the approximation error of the aggregation results and discuss the determinations of parameters in our approach. Simulation results verify the effectiveness of our approach.

In many applications continuous aggregation of sensed data is usually required. The existing aggregation schemes usually compute every aggregation result in a continuous aggregation either by a complete aggregation procedure or by partial data update at each epoch. To further reduce the energy cost, we propose a sampling-based approach with time window based linear regression for approximate continuous aggregation. We analyze the approximation error of the aggregation results and discuss the determinations of parameters in our approach. Simulation results verify the effectiveness of our approach.

Cite this paper

nullL. Yu, J. Li and S. Cheng, "Approximate Continuous Aggregation via Time Window Based Compression and Sampling in WSNs,"*Wireless Sensor Network*, Vol. 2 No. 9, 2010, pp. 675-682. doi: 10.4236/wsn.2010.29081.

nullL. Yu, J. Li and S. Cheng, "Approximate Continuous Aggregation via Time Window Based Compression and Sampling in WSNs,"

References

[1] S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong, “The Design of an Acquisitional Query Processor for Sensor Networks,” Proceedings of International Conference on Management on Data, California, 2003, pp. 491-502.

[2] S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong, “TAG: A Tiny Aggregation Service for Ad Hoc Sensor Networks,” Proceedings of the 5th Symposium on Operating Systems Design and Implementation, New York, 2002, pp. 131-146.

[3] J. Considine, F. Li, G. Kollios and J. Byers, “Approximate Aggregation Techniques for Sensor Databases,” International Conference on Data Engineering, Boston, 2004, pp. 449-460.

[4] S. Nath, P. B. Gibbons, S. Seshan and Z. R. Anderson, “Synopsis Diffusion for Robust Aggregation in Sensor Networks,” Sensys, 2004, pp. 250-262.

[5] G. Cormode, M. N. Garofalakis, S. Muthukrishnan and R. Rastogi, “Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles,” Proceedings of International Conference on Management on Data, 2005, pp. 25-36.

[6] A. Deligiannakis, Y. Kotidis and N. Rossopoulos, “Processing Approximate Aggregation Queries in Wireless Senor Networks,” Information Systems, Vol. 31, No. 8, 2006, pp. 770-792.

[7] A. Manjhi, S. Nath and P. B. Gibbons, “Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams,” ACM SIGMOD, ACM Press, 2005, pp. 287-298.

[8] S. Y. Cheng, J. Z. LI, Q. Q. Ren and L. Yu, “Bernoulli Sampling Based (epsilon, delta)-Approximate Aggregation in Larger-Scale Sensor Networks,” IEEE International Conference on Computer Communications, California, 2010, pp. 1181-1189.

[9] S. Lin, B. Arai, D. Gunopulos and G. Das, “Region Sampling: Continuous Adaptive Sampling on Sensor Networks,” IEEE International Conference on Data Engineering, Cancun, 2008, pp. 794-803.

[10] B. Bash, J. Byers and J. Considine, “Approximately Uniform Random Sampling in Sensor Networks,” Proceedings of 1st Workshop on Data Management in Sensor Networks, August, 2004.

[11] C. Guestrin, P. Bodik, R. Thibaux, M. Paskin and S. Madden, “Distributed Regression: An Efficient Framework for Modeling Sensor Network Data,” ACM/IEEE IPSN, 2004, pp. 1-10.

[12] W. Xue, Q. Luo, L. Chen and Y. Liu, “Contour Map Matching for Event Detection in Sensor Networks,” SIGMOD, New York, 2006, pp. 145-156.

[13] H. Gupta, V. Navda, S. R. Das and V. Chowdhary, “Efficient Gathering of Correlated Data in Sensor Networks,” MobiHoc, New York, 2005, pp. 402-413.

[14] A. Sen and M. Srivastava, “Regression Analysis: Theory, Methods, and Applications,” Springer-Verlag, New York, 1990.

[15] Z. Govindarajulu, “Elements of Sampling Theory and Methods,” Prentice Hall, New Jersey, 1999.

[1] S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong, “The Design of an Acquisitional Query Processor for Sensor Networks,” Proceedings of International Conference on Management on Data, California, 2003, pp. 491-502.

[2] S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong, “TAG: A Tiny Aggregation Service for Ad Hoc Sensor Networks,” Proceedings of the 5th Symposium on Operating Systems Design and Implementation, New York, 2002, pp. 131-146.

[3] J. Considine, F. Li, G. Kollios and J. Byers, “Approximate Aggregation Techniques for Sensor Databases,” International Conference on Data Engineering, Boston, 2004, pp. 449-460.

[4] S. Nath, P. B. Gibbons, S. Seshan and Z. R. Anderson, “Synopsis Diffusion for Robust Aggregation in Sensor Networks,” Sensys, 2004, pp. 250-262.

[5] G. Cormode, M. N. Garofalakis, S. Muthukrishnan and R. Rastogi, “Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles,” Proceedings of International Conference on Management on Data, 2005, pp. 25-36.

[6] A. Deligiannakis, Y. Kotidis and N. Rossopoulos, “Processing Approximate Aggregation Queries in Wireless Senor Networks,” Information Systems, Vol. 31, No. 8, 2006, pp. 770-792.

[7] A. Manjhi, S. Nath and P. B. Gibbons, “Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams,” ACM SIGMOD, ACM Press, 2005, pp. 287-298.

[8] S. Y. Cheng, J. Z. LI, Q. Q. Ren and L. Yu, “Bernoulli Sampling Based (epsilon, delta)-Approximate Aggregation in Larger-Scale Sensor Networks,” IEEE International Conference on Computer Communications, California, 2010, pp. 1181-1189.

[9] S. Lin, B. Arai, D. Gunopulos and G. Das, “Region Sampling: Continuous Adaptive Sampling on Sensor Networks,” IEEE International Conference on Data Engineering, Cancun, 2008, pp. 794-803.

[10] B. Bash, J. Byers and J. Considine, “Approximately Uniform Random Sampling in Sensor Networks,” Proceedings of 1st Workshop on Data Management in Sensor Networks, August, 2004.

[11] C. Guestrin, P. Bodik, R. Thibaux, M. Paskin and S. Madden, “Distributed Regression: An Efficient Framework for Modeling Sensor Network Data,” ACM/IEEE IPSN, 2004, pp. 1-10.

[12] W. Xue, Q. Luo, L. Chen and Y. Liu, “Contour Map Matching for Event Detection in Sensor Networks,” SIGMOD, New York, 2006, pp. 145-156.

[13] H. Gupta, V. Navda, S. R. Das and V. Chowdhary, “Efficient Gathering of Correlated Data in Sensor Networks,” MobiHoc, New York, 2005, pp. 402-413.

[14] A. Sen and M. Srivastava, “Regression Analysis: Theory, Methods, and Applications,” Springer-Verlag, New York, 1990.

[15] Z. Govindarajulu, “Elements of Sampling Theory and Methods,” Prentice Hall, New Jersey, 1999.