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. While several data aggregation (i.e., routing with data compression) techniques have been proposed in the literature, an understanding of the performance of various data aggregation schemes across the range of spatial correlations is lacking. We analyze the performance of routing with compression in wireless sensor networks using an application-independent measure of data compression (an empirically obtained approximation for the joint entropy of sources as a function of the distance between them) to quantify the size of compressed information, and a bit-hop metric to quantify the total cost of joint routing with compression. Analytical modeling and simulations reveal that while the nature of optimal routing with compression does depend on the correlation level, surprisingly, there exists a practical static clustering scheme which can provide near-optimal performance for a wide range of spatial correlations. This result is of great practical significance as it shows that a simple cluster-based system design can perform as well as sophisticated adaptive schemes for joint routing and compression.

REFERENCES

• 1: 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]
• 2: Ashish Goel, Deborah Estrin, "Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk," SODA 2003, p. 499--505.
• 3: 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
• 4: 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
• 5: 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]
• 6: 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
• 7: B. Bonfils and P. Bonnet, "Adaptive and Decentralized Operator Placement for In-Network Query Processing," Workshop on Information Processing in Sensor Networks (IPSN), April 2003.
• 8: P. Bonnet, J. Gehrke, P. Seshadri, " Querying the Physical World," IEEE Personal Communications Special Issue on Networking the Physical World, October 2000.
• 9: 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
• 10: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 11: 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
• 12: Martha Steenstrup, Cluster-based networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 13: M. Widmann and C. Bretherton, "50 km resolution daily preciptation for the Pacific Northwest, 1949-94," Cimate Data Archive, Joint Institute for the Study of the Atmosphere and the Ocean, 1999. Online data-set located at http://www.jisao.washington.edu/data sets/widmann

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
analytical modeling, sensor networks, simulations