Data compression algorithms for energy-constrained devices in delay tolerant networks

ABSTRACT

Sensor networks are fundamentally constrained by the difficulty and energy expense of delivering information from sensors to sink. Our work has focused on garnering additional significant energy improvements by devising computationally-efficient lossless compression algorithms on the source node. These reduce the amount of data that must be passed through the network and to the sink, and thus have energy benefits that are multiplicative with the number of hops the data travels through the network.Currently, if sensor system designers want to compress acquired data, they must either develop application-specific compression algorithms or use off-the-shelf algorithms not designed for resource-constrained sensor nodes. This paper discusses the design issues involved with implementing, adapting, and customizing compression algorithms specifically geared for sensor nodes. While developing Sensor LZW (S-LZW) and some simple, but effective, variations to this algorithm, we show how different amounts of compression can lead to energy savings on both the compressing node and throughout the network and that the savings depends heavily on the radio hardware. To validate and evaluate our work, we apply it to datasets from several different real-world deployments and show that our approaches can reduce energy consumption by up to a factor of 4.5X across the network.

REFERENCES

• 1: T. Arici, B. Gedik, Y. Altunbasak, and L. Liu. PINCO: a Pipelined In-Network Compression Scheme for Data Collection in Wireless Sensor Networks. In IEEE Intl. Conf. on Computer Communications and Networks, 2003.
• 2: ATMEL. AT45DB041B, 4M bit, 2.7-Volt Only Serial-Interface Flash with Two 264-Byte SRAM Buffers data sheet. http://www.atmel.com/, June 2003.
• 3: ATMEL. 8-bit AVR Microcontroller with 128K Bytes In-System Programmable Flash Datasheet. http://www.atmel.com/, 2004.
• 4: S.J. Baek, G. de Veciana, and X. Su. Minimizing Energy Consumption in Large-Scale Sensor Networks Through Distributed Data Compression and Hierarchical Aggregation. IEEE Journal on Selected Areas in Communications, 2004.
• 5: Kenneth Barr , Krste Asanović, Energy aware lossless data compression, Proceedings of the 1st international conference on Mobile systems, applications and services, p.231-244, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066123]
• 6: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 7: M. Burrows and D.J. Wheeler. A Block-sorting Lossless Data Compression Algorithm. Digital Systems Research Center Research Report, 124, 1994.
• 8: Chipcon AS. Chipcon SmartRF CC1000 Datasheet rev. 2.3. http://www.chipcon.com/, Aug. 2005.
• 9: Chipcon AS. Chipcon SmartRF CC2420 Datasheet rev. 1.3. http://www.chipcon.com/, Oct. 2005.
• 10: J. Chou, D. Petrovic, and K. Ramchandran. A Distributed and Adaptive Signal Processing Approach to Reducing Energy Consumption in Sensor Networks. In Proc. INFOCOM, 2003.
• 11: J.G. Cleary and I.H. Witten. Data Compression using Adaptive Coding and Partial String Matching. IEEE Transactions on Communications, COM-32(4):396--402, April 1984.
• 12: Crossbow Technology, Inc. Mica2 Datasheet. http://www.xbow.com/, 2005.
• 13: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 14: Deepak Ganesan , Ben Greenstein , Denis Perelyubskiy , Deborah Estrin , John Heidemann, An evaluation of multi-resolution storage for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958502]
• 15: D.A. Huffman. A Method for the Construction of Minimum-Redundancy Codes. In Proceedings of the I.R.E., 1952.
• 16: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 17: Haris Lekatsas , Jörg Henkel , Venkata Jakkula, Design of an one-cycle decompression hardware for performance increase in embedded systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513929]
• 18: Chang Hong Lin , Yuan Xie , Wayne Wolf, LZW-Based Code Compression for VLIW Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.30076, February 16-20, 2004
• 19: Markus Oberhumer. LZO Real-Time Data Compression Library. http://www.oberhumer.com/opensource/lzo/, Oct. 2005.
• 20: Maxstream, Inc. XTend OEM RF Module: Product Manual v1.2.4. http://www.maxstream.net/, Oct. 2005.
• 21: Moteiv Corp. Tmote Sky: Low power Wireless Sensor Module Datasheet. http://www.moteiv.com/, Mar. 2005.
• 22: M. Nelson. Data Compression with the Burrows-Wheeler Transform. Dr. Dobbs Journal, Sept. 1996.
• 23: E. Netto, R. Azevedo, P. Centoducatte, and G. Araujo. Mixed Static/Dynamic Profiling for Dictionary Based Code Compression. In Proc. Intl. Symposium on System-on-Chip, 2003.
• 24: Sundeep Pattem , Bhaskar Krishnamachari , Ramesh Govindan, The impact of spatial correlation on routing with compression in wireless sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984627]
• 25: D. Petrovic, R.C. Shah, K. Ramchandran, and J. Rabaey. Data Funneling: Routing with Aggregation and Compression for Wireless Sensor Networks. In SNPA Workshop, ICC 2003 Intl. Conf. on Communications, 2003.
• 26: S.S. Pradhan, J. Kusuma, and K. Ramchandran. Distributed Compression in a Dense Microsensor Network. IEEE Signal Processing Magazine, pages 51--60, March 2002.
• 27: W. Qin. SimIt-ARM. http://simit-arm.sourceforge.net/, Mar. 2003.
• 28: B.M. Sadler. Fundamentals of Energy-Constrained Sensor Network Systems. IEEE Aerospace and Electronics Systems Magazine, Tutorial Supplement, 2005.
• 29: 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]
• 30: T. Schmid, H. Dubois-Ferriere, and M. Vetteri. SensorScope: Experiences with a Wireless Building Monitoring Sensor Network. In Proc. of the Workshop on Real-World Wireless Sensor Networks (RealWSN), 2005.
• 31: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 32: James A. Storer , Thomas G. Szymanski, Data compression via textual substitution, Journal of the ACM (JACM), v.29 n.4, p.928-951, Oct. 1982 [doi>10.1145/322344.322346]
• 33: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 34: C. Tang, C.S. Raghavendra, and V.K. Prasanna. Power Aware Coding for Spatio-Temporally Correlated Wireless Sensor Data. In IEEE Intl. Conf. on Mobile Ad-Hoc and Sensor Systems, 2004.
• 35: Texas Instruments. MSP430x161x Mixed Signal Microcontroller Datasheet. http://www.ti.com/, Mar. 2005.
• 36: TinyOS Community Forum. TinyOS. http://www.tinyos.net/.
• 37: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. In Technical Report CS-200006, Duke University, Apr. 2000.
• 38: Yong Wang , Sushant Jain , Margaret Martonosi , Kevin Fall, Erasure-coding based routing for opportunistic networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.229-236, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080140]
• 39: T.A. Welch. A Technique for High-Performance Data Compression. IEEE Computer, 17(6):8--19, June 1984.
• 40: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 41: WxWiki. Z File Format. http://www.wxwidgets.org/wiki/index.php/ Development: Z File Format.
• 42: Pei Zhang , Christopher M. Sadler , Stephen A. Lyon , Margaret Martonosi, Hardware design experiences in ZebraNet, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031522]
• 43: J. Ziv and A. Lempel. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, 23(3):337--343, 1977.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Performance, Reliability

Keywords:
data compression, energy efficient communications, mobile ad hoc networks, wireless sensor networks