Packet combining in sensor networks

ABSTRACT

This paper presents the Simple Packet Combining (SPaC) error-correction scheme for wireless sensor networks. Nodes buffer corrupt packets, and when two or more corrupt versions of a packet have been received, a packet combining procedure attempts to recover the original packet from the corrupt copies. Packet combining exploits the broadcast medium and spatial diversity of a multi-hop wireless network by using packets overheard at any node, in addition to the next-hop destination of the packet itself. Unlike point-to-point forward error correction (FEC), packet combining therefore helps multi-node interactions such as multi-hop routing or broadcasting as well as to hop-by-hop communication. Also, SPaC does not transmit redundant overhead on good links and does not require costly probes to estimate channel conditions.We have implemented SPaC as a link-layer extension on sensor nodes; it is transparent to upper layer protocols and has low memory and CPU footprints. We evaluate performance through a combination of analysis, trace-driven simulation, indoor and outdoor testbed micro-benchmarks, and deployment on a live network. The results show significant performance gains, even when accounting for the energy cost of CPU processing. We also present detailed bit-level link measurements and the design and evaluation of a new preamble detection scheme motivated by these measurements.

REFERENCES

• 1: T. H. A. Nosratinia and A. Hedayat. Cooperative communication in wireless networks. IEEE Communications Magazine, 42(10):68--73, Oct 2004.
• 2: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 3: F. Braun and M. Waldvogel. Fast incremental CRC updates for IP over ATM networks. In 2001 IEEE Workshop on High Performance Switching and Routing (HPSR 2001), pages 48--52, Dallas, TX, USA, May 2001.
• 4: R. E. Blahut. Theory and Practice of Error Control Coding. Addison-Wesley, 1983.
• 5: A. Cerpa, N. Busek, and D. Estrin. Scale: A tool for simple connectivity assessment in lossy environments. In CENS Technical Report 0021, 2003.
• 6: Chipcon. CC1000 transceiver datasheet. http://www.chipcon.com.
• 7: L. de Alfaro and A. R. Meo. Codes for second and third order GH-ARQ schemes. IEEE Trans. on Communications, 1994.
• 8: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 9: Bret Hull , Kyle Jamieson , Hari Balakrishnan, Mitigating congestion in wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031512]
• 10: 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]
• 11: A. Köpke. Uses of channel codes and checksums to improve energy efficiency in sensor networks. Technical Report TKN-03-008, Technische Universität Berlin, May 2003.
• 12: J. N. Laneman, D. N. C. Tse, and G. W. Wornell. Cooperative diversity in wireless networks: Efficient protocols and outage behavior. IEEE Trans. on Information Theory, 50, 2004.
• 13: P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor network. In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004), 2004.
• 14: Shu Lin , Daniel J. Costello, Error Control Coding, Second Edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 2004
• 15: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 16: Allen Miu , Hari Balakrishnan , Can Emre Koksal, Improving loss resilience with multi-radio diversity in wireless networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080832]
• 17: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 18: T. Schmid, H. Dubois-Ferrière, and M. Vetterli. SensorScope: Experiences with a Wireless Building Monitoring Sensor Network. In Workshop on Real-World Wireless Sensor Networks (REALWSN'05), 2005.
• 19: 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]
• 20: P. Sindhu. Retransmission error control with memory. IEEE Transactions on Communications, 1977.
• 21: 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]
• 22: Tijs van Dam , Koen Langendoen, An adaptive energy-efficient MAC protocol for wireless 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.958512]
• 23: W. Ye, J. Heidemann, and D. Estrin. An energy-efficient mac protocol for wireless sensor networks. In Proceedings of the IEEE Infocom, pages 1567--1576, New York, NY, USA, June 2002. USC/Information Sciences Institute, IEEE.
• 24: B. Zhao and M. C. Valenti. Practical relay networks: A generalization of hybrid-ARQ. IEEE JSAC (Special Issue on Wireless Ad Hoc Networks), 23, 2005.
• 25: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless 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.958493]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
bit error, channel coding, cooperative diversity, error correction, packet combining, sensor networks, wireless networks