The impact of spatial correlation on routing with compression in wireless sensor networks

ABSTRACT

The efficacy of data aggregation in sensor networks is a function of the degree of spatial correlation in the sensed phenomenon. The recent literature has examined a variety of schemes that achieve greater data aggregation by routing data with regard to the underlying spatial correlation. A well known conclusion from these papers is that the nature of optimal routing with compression depends on the correlation level. In this article we show the existence of a simple, practical, and static correlation-unaware clustering scheme that satisfies a min-max near-optimality condition. The implication for system design is that a static correlation-unaware scheme can perform as well as sophisticated adaptive schemes for joint routing and compression.

REFERENCES

• 1: Bonfils, B. and Bonnet, P. 2003. Adaptive and decentralized operator placement for in-network query processing. In Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks (IPSN'03). Palo Alto, CA. Springer-Verlag, 47--62.
• 2: Ciancio, A. and Ortega, A. 2005. A distributed wavelet compression algorithm for wireless multihop sensor networks using lifting. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. Philadelphia, PA.
• 3: Alexandre Ciancio , Sundeep Pattem , Antonio Ortega , Bhaskar Krishnamachari, Energy-efficient data representation and routing for wireless sensor networks based on a distributed wavelet compression algorithm, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127824]
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: Cristescu, R., Beferull-Lozano, B., and Vetterli, M. 2004. On network correlated data gathering. In Proceedings of the 23rd Conference of the IEEE Communications Society (INFOCOM'04). Hong Kong.
• 6: Razvan Cristescu , Baltasar Beferull-Lozano , Martin Vetterli , Roger Wattenhofer, Network correlated data gathering with explicit communication: NP-completeness and algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.41-54, February 2006 [doi>10.1109/TNET.2005.863711]
• 7: Dang, T., Bulusu, N., and Feng, W. 2007. Rida: A robust information-driven data compression architecture for irregular wireless sensor networks. In Proceedings of the 4th European Workshop on Sensor Networks (EWSN). Delft, The Netherlands. IEEE.
• 8: Enrique J. Duarte-Melo , Mingyan Liu, Data-gathering wireless sensor networks: organization and capacity, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.519-537, 15 November 2003 [doi>10.1016/S1389-1286(03)00357-8]
• 9: Enachescu, M., Goel, A., Govindan, R., and Motwani, R. 2004. Scale-free aggregation in sensor networks. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensors'04). Turku, Finland. Springer-Verlag, 71--84.
• 10: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 11: Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 13: Hu, W., Chou, C., Jha, S., and Bulusu, N. 2004. Deploying long-lived and cost-effective hybrid sensor networks. In Proceedings of the 1st Workshop on Broadband Advanced Sensor Networks(BaseNets'04). San Jose, CA. IEEE Communications Society.
• 14: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 15: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 16: Bhaskar Krishnamachari , Deborah Estrin , Stephen B. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.575-578, July 02-05, 2002
• 17: Lee, S., Pattem, S., Shen, G., Tu, A., Krishnamachari, B., Ortega, A., Cheng, M., Dolinar, S., Kiely, A., and Xie, H. 2007. A distributed wavelet approach for efficient information representation and data gathering in sensor webs. In Proceedings of the NASA Science Technology Conference (NSTC). College Park, MD.
• 18: Samuel Madden , Robert Szewczyk , Michael J. Franklin , David Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.49, June 20-21, 2002
• 19: Marco, D., Duarte-Melo, E., Liu, M., and Neuhoff, D. L. 2003. On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data. In Proceedings of the International Workshop on Information Processing in Sensor Networks (IPSN). IEEE/ACM.
• 20: Sundeep Pattem , Bhaskar Krishnamachari , Ramesh Govindan, The impact of spatial correlation on routing with compression in wireless sensor networks, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984627]
• 21: S. Sandeep Pradhan , Kannan Ramchandran, Distributed Source Coding Using Syndromes (DISCUS): Design and Construction, Proceedings of the Conference on Data Compression, p.158, March 29-31, 1999
• 22: Anna Scaglione , Sergio D. Servetto, On the interdependence of routing and data compression in multi-hop sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570663]
• 23: Anna Scaglione , Sergio Servetto, On the interdependence of routing and data compression in multi-hop sensor networks, Wireless Networks, v.11 n.1-2, p.149-160, January 2005 [doi>10.1007/s11276-004-4752-y]
• 24: Godwin Shen , Antonio Ortega, Joint Routing and 2D Transform Optimization for Irregular Sensor Network Grids Using Wavelet Lifting, Proceedings of the 7th international conference on Information processing in sensor networks, p.183-194, April 22-24, 2008 [doi>10.1109/IPSN.2008.24]
• 25: Shen, G. and Ortega, A. 2008b. Optimized distributed 2d transforms for irregularly sampled sensor network grids using wavelet lifting. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). Las Vegas, NV.
• 26: Pascal von Rickenbach , Roger Wattenhofer, Gathering correlated data in sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022640]
• 27: Wang, P., Li, C., and Zheng, J. 2007. Distributed data aggregation using clustered Slepian-Wolf coding in wireless sensor networks. In Proceedings of the IEEE International Conference Communication (ICC). 3616--3622.
• 28: Widmann, M. and Bretherton, C. 1999. 50 km resolution daily preciptation for the pacific northwest, 1949-94. <http://www.jisao.washington.edu/data_sets/widmann>.
• 29: Zhu, Y., Sundaresan, K., and Sivakumar, R. 2005. Practical limits on achievable energy improvements and useable delay tolerance in correlation aware data gathering in wireless sensor networks. In Proceedings of the IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON). Santa Clara, CA.
• 30: Zuniga, M. and Krishnamachari, B. 2004a. Analyzing the transitional region in low power wireless links. In Proceedings of the 1st IEEE International Conference on Sensor and Ad hoc Communications and Networks (SECON). Santa Clara, CA.
• 31: Zuniga, M. and Krishnamachari, B. 2004b. Realistic wireless link quality model and generator. <http://ceng.usc.edu/~anrg/downloads.html>.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Performance

Keywords:
Sensor networks, analytical modeling, correlated data gathering