[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Trimming the Tree: Tailoring Adaptive Huffman Coding to Wireless Sensor Networks

  • Conference paper
Wireless Sensor Networks (EWSN 2010)

Part of the book series: Lecture Notes in Computer Science ((LNCCN,volume 5970))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Pottie, G.J., Kaiser, W.J.: Wireless Integrated Network Sensors. Communications of the ACM 43 (2000)

    Google Scholar 

  2. 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

  3. 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)

    Google Scholar 

  4. Vitter, J.S.: Design and Analysis of Dynamic Huffman Codes. Journal of the Association for Computing Machinery 34(4) (1987)

    Google Scholar 

  5. 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)

    Google Scholar 

  6. 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)

    Google Scholar 

  7. 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)

    Google Scholar 

  8. 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)

    Google Scholar 

  9. 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)

    Google Scholar 

  10. 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)

    Google Scholar 

  11. 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)

    Google Scholar 

  12. 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)

    Google Scholar 

  13. 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)

    Google Scholar 

  14. 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)

    Chapter  Google Scholar 

  15. 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)

    Google Scholar 

  16. Annamalai, V., Gupta, S.K.S., Schwiebert, L.: On Tree-Based Convergecasting in Wireless Sensor Networks. IEEE Wireless Communications and Networking 3 (2003)

    Google Scholar 

  17. 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)

    Google Scholar 

  18. 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)

    Google Scholar 

  19. 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)

    Google Scholar 

  20. 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)

    Google Scholar 

  21. 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)

    Google Scholar 

  22. 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)

    Google Scholar 

  23. 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)

    Google Scholar 

  24. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics