Research Abstracts - 2007

Introduction

Bit errors occur over wireless channels when the signal isn't strong enough to overcome the effects of interference and noise [1]. Current wireless protocols may use forward error correction (FEC) to correct for some (small) number of bit errors, but generally retransmit the whole packet if the FEC is insufficient. We observe that current wireless mesh network protocols retransmit a number of packets and that most of these retransmissions end up sending bits that have already been received multiple times, wasting network capacity. To overcome this inefficiency, we develop, implement, and evaluate a partial packet recovery (PPR) system [2].

Figure 1: Partial packet reception during two concurrent transmissions: codeword correctness (triangle indicators) and each codeword's associated Hamming distance (curves). Despite uncertainty in PHY symbol timing recovery and SINR, Hamming distance indicates the correct parts of these packets to higher layers.

PPR incorporates three new ideas: (1) SoftPHY, an expanded physical layer (PHY) interface to provide hints to the higher layers about how ``close'' the actual received symbol was to the one decoded, (2) a postamble scheme to recover data even when a packet's preamble is corrupted and not decodable at the receiver, and (3) PP-ARQ, an asynchronous link-layer retransmission protocol that allows a receiver to compactly encode and request for retransmission only those portions of a packet that are likely in error.

The SoftPHY interface

In the abstract, the SoftPHY interface is simple: annotate each group of bits propagated to the higher layer with a confidence metric. The details of how the confidence metric is calculated and what it actually means, however, depend on how the PHY works. However, most demodulation and decoding methods maintain this information.

Although the SoftPHY interface can be provided for a variety of PHY implementations, the semantics of the delivered information is intimately tied to the details of the PHY. One of the benefits of protocol layering is that higher layers are shielded from the details of the lower ones, and SoftPHY has the potential danger of violating this abstraction barrier in the interest of performance. Here, we argue that it is possible to implement higher layers without violating the abstraction boundary.

To do that, the higher layers must not be aware of exactly how the information is calculated. Instead, they should adapt their threshold or other decisions to label groups of bits as ``good'' or ``bad'' to actual observation. For example, the link/MAC layer could observe the correlation between a particular threshold and the correctness of the hint, and adapt the threshold dynamically. This approach can be used as long as the PHY simply provides a ``monotonicity'' contract; i.e., given any two hint values, h₁ and h₂, h₁ < h₂ always implies that the PHY has a higher confidence in the bits associated with h₁ than with h₂ (or vice versa). Implementing such a contract is straightforward for the PHY, at least for the three options we laid out above.

Postamble detection

When errors occur in the preamble due to collisions or noise, the receiver will not be able to synchronize to the incoming transmission and decode any bits. In that case, the benefits of SoftPHY will go unrealized: we need a way to cope with preamble loss.

Figure 2: a packet is composed of symbols, which may be organized into codewords of B symbols each by channel coding or direct-sequence spread spectrum. Each codeword encodes b data bits.

Our approach to synchronizing on packets without an intelligible preamble is simple: add a postamble to the end of each packet on which a receiver can also synchronize. Like the preamble, the postamble has a well-known sequence attached to it that uniquely identifies it as the postamble, and differentiates it from a preamble. In addition, we add a trailer near the postamble at the end of the packet, as shown in Figure 2. The trailer contains the packet length, source, and destination addresses. Just as with the header data, the receiver uses a CRC fragment or PHY-layer confidences to check the correctness of the trailer so that it can request a partial retransmission from the sender.

To recover payload symbols (and bits) after hearing just a postamble, the receiver maintains a circular buffer of samples of previously-received symbols even when it has not heard a preamble. In our implementation of postamble decoding in MSK, we keep as many samples of previously-received symbols as there are symbols in one maximally-sized packet in the system. When the receiver detects a preamble, the behavior is the same is in the status quo. When the receiver detects a postamble, it takes the following steps:

1. ``Roll back'' as many symbols as are in the packet trailer.
2. Decode and parse the trailer to find the start of the entire packet, source, and destination addresses.
3. Verify the trailer's checksum.
4. ``Roll back'' in time as many symbols as are in the entire packet, to decode as much of the packet as possible.

PP-ARQ: Retransmissions Using Partial Packet Recovery

SoftPHY and the postamble scheme together allow higher layers to discover which received codewords are likely to be correct and which are not. We now examine the problem of how the receiver should most efficiently communicate this information back to the sender, to form the full partial packet recovery protocol.

Figure 2: Architecture of the PP-ARQ system; dark blocks and the SoftPHY interface are our contributions. PPR sits above one of many different types of receiver structure. The SoftPHY interface passes up hints from the receiver to PP-ARQ, the partial packet retransmission layer Postamble decoding increases the number of opportunities for recovering partial packets from the receiver.

The naive way to provide feedback is for each receiver to send back the bit ranges of each chunk believed to be wrong. Unfortunately, doing that takes up a large number of bits, since encoding the start of a range and its length can take up between log S and 2 log S bits for a packet of size S (depending on the details of the encoding; compression might improve this number, but it is still potentially large). Hence, we develop an bit-efficient feedback scheme, PP-ARQ.

This problem can be solved using dynamic programming. We show that any set of bad runs the receiver asks for can be assigned a cost function, and that the problem itself exhibits the ``optimal substructure'' property in that the cost for the entire packet is easily derived from the cost of two suitably divided portions. The result is a series of segments that the receiver requests the sender to retransmit. Each of those segments will of course have ``bad'' codewords in them, but may also have some ``good'' codewords (for otherwise there might have been too many segments to ask for). On the other hand, no segment that is not asked for will have any ``bad'' codewords. When the sender responds to this carefully constructed requests for segment retransmissions, it also sends the CRCs of the segments not asked for, so that the receiver can verify that all those codewords have been correctly recovered.

Experimental results

Our experimental results from a 27-node 802.15.4 testbed that includes Telos motes with 2.4 GHz Chipcon radios and GNU Radio nodes implementing the Zigbee standard (802.15.4) show that PPR increases the frame delivery rate by a factor of two under moderate load.

Acknowledgements

This work was supported by the National Science Foundation under Award Numbers CNS-0520032 and CNS-0205445.

References:

[1] A. Goldsmith. Wireless Communications. Cambridge Univ. Press, New York, NY, 2005.

[2] K. Jamieson, H. Balakrishnan. PPR: Partial Packet Recovery for Wireless Networks. MIT CSAIL Technical Report TR-2007-008, 2007.