Single and Multi-Hop ARQ in Sensor Networks

We present a novel error-correction scheme for sensor networks called Multi-hop Hybrid ARQ (MHARQ). Rather than immediately discard a received corrupt packet, a node buffers it. When two corrupt versions of a packet have been received, a procedure attempts to recover the original packet from the corrupt copies. In addition to improving single-hop communications, MHARQ exploits the spatial diversity arising from the broadcast, multi-point nature of a sensor network. MHARQ therefore also impacts multi-node interactions such as multi-hop routing or broadcasting, unlike point-to-point forward error correction (FEC). Furthermore, our scheme does not transmit redundant overhead on good links and does not require costly probes to estimate channel conditions. We have implemented the scheme in TinyOS; it is transparent to upper layer protocols and has low memory and CPU footprints. We evaluate performance through a combination of trace-driven simulation, indoor and outdoor testbed micro-benchmarks, and macro-benchmarks. The results show that MHARQ can offer significant 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.