Abstract
We address the problem of designing practical, energy-efficient protocols for data collection in wireless sensor networks using predictive modeling. Prior work has suggested several approaches to capture and exploit the rich spatio-temporal correlations prevalent in WSNs during data collection. Although shown to be effective in reducing the data collection cost, those approaches use simplistic corelation models and further, ignore many idiosyncrasies of WSNs, in particular the broadcast nature of communication. Our proposed approach is based on approximating the joint probability distribution over the sensors using undirected graphical models, ideally suited to exploit both the spatial correlations and the broadcast nature of communication. We present algorithms for optimally using such a model for data collection under different communication models, and for identifying an appropriate model to use for a given sensor network. Experiments over synthetic and real-world datasets show that our approach significantly reduces the data collection cost.
This work was supported by NSF Grants CNS-0509220 and IIS-0546136.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Computer Networks 38 (2002)
Arici, T., Gedik, B., Altunbasak, Y., Liu, L.: PINCO: A pipelined in-network compression scheme for data collection in wireless sensor networks. In: IEEE Intl. Conf. on Computer Communications and Networks (2003)
Blair, J.R.S., Peyton, B.: An Introduction to Chordal Graphs and Clique Trees. In: Graph Theory and Sparse Matrix Computation, pp. 1–29. Springer, New York (1993)
Chu, D., Deshpande, A., Hellerstein, J., Hong, W.: Approximate data collection in sensor networks using probabilistic models. In: Proceedings of the International Conference on Data Engineering (ICDE) (2006)
Cormode, G., Garofalakis, M., Muthukrishnan, S., Rastogi, R.: Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In: SIGMOD (2005)
Cristescu, R., Beferull-Lozano, B., Vetterli, M., Wattenhofer, R.: Network correlated data gathering with explicit communication: Np-completeness and algorithms. IEEE/ACM Transactions on Networking 14(1), 41–54 (2006)
Cristescu, R., Beferull-Lozano, B., Vetterli, M.: Networked slepian-wolf: Theory and algorithms. In: Karl, H., Wolisz, A., Willig, A. (eds.) Wireless Sensor Networks. LNCS, vol. 2920, Springer, Heidelberg (2004)
Deshpande, A., Garofalakis, M., Jordan, M.: Efficient stepwise selection in decomposable models. In: UAI (2001)
Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J., Hong, W.: Model-driven data acquisition in sensor networks. In: VLDB (2004)
Edwards, D.: Introduction to Graphical Modeling. Springer, New York (1995)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)
Gupta, H., Navda, V., Das, S., Chowdhary, V.: Efficient gathering of correlated data in sensor networks. In: MobiHoc. (2005)
Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Transactions on Information Theory 46, 388–404 (2000)
Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: HICSS 2000. Proceedings of the 33rd Hawaii International Conference on System Sciences, vol. 8, p. 8020 (2000)
Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed diffusion: A scalable and robust communication paradigm for sensor networks. In: ACM MobiCOM (2000)
Jensen, F.V., Jensen, F.: Optimal Junction Trees. In: Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence, Seattle, Washington (July 1994)
Kotidis, Y.: Snapshot queries: Towards data-centric sensor networks. In: ICDE (2005)
Madden, S.: Intel lab data (2003), http://db.csail.mit.edu/labdata/labdata.html
Madden, S., Franklin, M.J., Hellerstein, J.M., Hong, W.: TAG: A tiny aggregation service for ad-hoc sensor networks. In: OSDI (2002)
Madden, S., Hong, W., Hellerstein, J., Franklin, M.: TinyDB web page, http://telegraph.cs.berkeley.edu/tinydb
Olston, C., Loo, B., Widom, J.: Adaptive precision setting for cached approximate values. In: SIGMOD (2001)
Pattem, S., Krishnamachari, B., Govindan, R.: The impact of spatial correlation on routing with compression in wireless sensor networks. In: IPSN (2004)
Pradhan, S., Ramchandran, K.: Distributed source coding using syndromes (DISCUS): Design and construction. IEEE Trans. Information Theory (2003)
Scaglione, A., Servetto, S.: On the interdependence of routing and data compression in multi-hop sensor networks. In: Mobicom (2002)
Silberstein, A., Braynard, R., Yang, J.: Constraint-chaining: On energy-efficient continuous monitoring in sensor networks. In: SIGMOD (2006)
Slepian, D., Wolf, J.: Noiseless coding of correlated information sources. IEEE Transactions on Information Theory 19(4) (1973)
Su, X.: A combinatorial algorithmic approach to energy efficient information collection in wireless sensor networks. ACM Trans. Sen. Netw. 3(1), 6 (2007)
Whittaker, J.: Graphical Models in Applied Multivariate Statistics. Wiley Series in Probability and Mathematical Statistics. John Wiley, Chichester (1990)
Widmann, M., Bretherton, C.: 50 km resolution daily precipitation for the pacific northwest (2003), http://www.jisao.washington.edu/data_sets/widmann
Wyner, A.D., Ziv, J.: The rate-distortion function for source coding with side information at the decoder. IEEE Transactions on Information Theory (1976)
Xiong, Z., Liveris, A.D., Cheng, S.: Distributed source coding for sensor networks. IEEE Signal Processing Magazine 21, 80–94 (2004)
Yao, Y., Gehrke, J.: Query processing in sensor networks. In: CIDR (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, L., Deshpande, A. (2008). Predictive Modeling-Based Data Collection in Wireless Sensor Networks. In: Verdone, R. (eds) Wireless Sensor Networks. EWSN 2008. Lecture Notes in Computer Science, vol 4913. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77690-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-77690-1_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77689-5
Online ISBN: 978-3-540-77690-1
eBook Packages: Computer ScienceComputer Science (R0)