Abstract
Nodes in wireless sensor networks are generally designed to operate on a limited energy budget, and must consciously use the available charge to allow for long lifetimes. As the radio transceiver is the predominant power consumer on current node platforms, the minimization of its activity periods and efficient use of the radio channel are major targets for optimization. Data compression is a viable option to increase the packet information density, resulting in reduced transmission durations and thus allowing for an optimized channel utilization. The computational and memory demands of many current compression algorithms however hamper their applicability on sensor nodes.
In this paper, we present a novel variant of the adaptive Huffman coding algorithm, operating on reduced code table sizes and thus significantly alleviating the resource demands for storing and updating the code table during runtime. An implementation for tmote sky hardware proves its adequacy to the capabilities of sensor nodes, and we present its achievable compression gains and energy requirements in both simulation and real world experiments. Results anticipate that overall energy savings can be achieved when transferring packets of reduced sizes, even when increased CPU utilization is incurred.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Pottie, G.J., Kaiser, W.J.: Wireless Integrated Network Sensors. Communications of the ACM 43 (2000)
Texas Instruments Inc.: CC2420: 2.4 GHz IEEE 802.15.4 / ZigBee-Ready RF Transceiver, Rev. B (2007), http://www.ti.com/lit/gpn/cc2420
Polastre, J., Hill, J., Culler, D.: Versatile Low Power Media Access for Wireless Sensor Networks. In: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, SenSys (2004)
Vitter, J.S.: Design and Analysis of Dynamic Huffman Codes. Journal of the Association for Computing Machinery 34(4) (1987)
Guitton, A., Trigoni, N., Helmer, S.: Fault-Tolerant Compression Algorithms for Delay-Sensitive Sensor Networks with Unreliable Links. In: Proceedings of the 4th IEEE international conference on Distributed Computing in Sensor Systems, DCOSS (2008)
Sadler, C.M., Martonosi, M.: Data Compression Algorithms for Energy-Constrained Devices in Delay Tolerant Networks. In: Proceedings of the 4th International Conference on Embedded Networked Sensor Systems, SenSys (2006)
Ju, H., Cui, L.: EasiPC: A Packet Compression Mechanism for Embedded WSN. In: Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA (2005)
Tsiftes, N., Dunkels, A., Voigt, T.: Efficient Sensor Network Reprogramming through Compression of Executable Modules. In: Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON (2008)
Chou, J., Petrović, D., Ramchandran, K.: A Distributed and Adaptive Signal Processing Approach to Reducing Energy Consumption in Sensor Networks. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM (2003)
Reinhardt, A., Hollick, M., Steinmetz, R.: Stream-oriented Lossless Packet Compression in Wireless Sensor Networks. In: Proceedings of the 6th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON (2009)
Reinhardt, A., Christin, D., Hollick, M., Steinmetz, R.: On the Energy Efficiency of Lossless Data Compression in Wireless Sensor Networks. In: Proceedings of the 4th IEEE International Workshop on Practical Issues in Building Sensor Network Applications, SenseApp (2009)
Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., Anderson, J.: Wireless Sensor Networks for Habitat Monitoring. In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, WSNA (2002)
Juang, P., Oki, H., Wang, Y., Martonosi, M., Peh, L.S., Rubenstein, D.: Energy-Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with Zebranet. In: Proceedings of the 10th Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS (2002)
Tseng, Y.C., Kuo, S.P., Lee, H.W., Huang, C.F.: Location Tracking in a Wireless Sensor Network by Mobile Agents and Its Data Fusion Strategies. In: Zhao, F., Guibas, L.J. (eds.) IPSN 2003. LNCS, vol. 2634, pp. 625–641. Springer, Heidelberg (2003)
Beutel, J., Gruber, S., Hasler, A., Lim, R., Meier, A., Plessl, C., Talzi, I., Thiele, L., Tschudin, C., Woehrle, M., Yuecel, M.: PermaDAQ: A Scientific Instrument for Precision Sensing and Data Recovery in Environmental Extremes. In: Proceedings of the 8th ACM/IEEE International Conference on Information Processing in Sensor Networks, IPSN (2009)
Annamalai, V., Gupta, S.K.S., Schwiebert, L.: On Tree-Based Convergecasting in Wireless Sensor Networks. IEEE Wireless Communications and Networking 3 (2003)
Martinez, K., Ong, R., Hart, J.: Glacsweb: A Sensor Network for Hostile Environments. In: Proceedings of the 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, SECON (2004)
Van Laerhoven, K., Gellersen, H.W., Malliaris, Y.G.: Long-Term Activity Monitoring with a Wearable Sensor Node. In: Workshop on Wearable and Implantable Body Sensor Networks, BSN (2006)
Bentley, J.L., Sleator, D.D., Tarjan, R.E., Wei, V.K.: A Locally Adaptive Data Compression Scheme. Communications of the ACM 29(4) (1986)
Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D., Pister, K.: System Architecture Directions for Network Sensors. In: Proceedings of the 10th Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS (2000)
Dunkels, A., Grönvall, B., Voigt, T.: Contiki – a Lightweight and Flexible Operating System for Tiny Networked Sensors. In: Proceedings of the 1st IEEE Workshop on Embedded Networked Sensors, Emnets-I (2004)
Eriksson, J., Österlind, F., Finne, N., Tsiftes, N., Dunkels, A., Voigt, T., Sauter, R., Marrón, P.J.: COOJA/MSPSim: Interoperability Testing for Wireless Sensor Networks. In: Proceedings of the 2nd International Conference on Simulation Tools and Techniques For Communications, Networks And Systems, Simutools (2009)
Dunkels, A., Österlind, F., Tsiftes, N., He, Z.: Software-based On-line Energy Estimation for Sensor Nodes. In: Proceedings of the 4th Workshop on Embedded Networked Sensors, EmNets (2007)
Szewczyk, R., Polastre, J., Mainwaring, A., Culler, D.: Lessons from a Sensor Network Expedition. In: Karl, H., Wolisz, A., Willig, A. (eds.) EWSN 2004. LNCS, vol. 2920, pp. 307–322. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Reinhardt, A., Christin, D., Hollick, M., Schmitt, J., Mogre, P.S., Steinmetz, R. (2010). Trimming the Tree: Tailoring Adaptive Huffman Coding to Wireless Sensor Networks. In: Silva, J.S., Krishnamachari, B., Boavida, F. (eds) Wireless Sensor Networks. EWSN 2010. Lecture Notes in Computer Science, vol 5970. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11917-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-11917-0_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11916-3
Online ISBN: 978-3-642-11917-0
eBook Packages: Computer ScienceComputer Science (R0)