Introduction

An important requirement in the design of indoor wireless local area networks (WLAN) is loss resilience. However, wireless communication channels have notoriously time-varying characteristics, where the quality of received signals changes dramatically even over time durations lasting just milliseconds. The complex behavior of wireless signal propagation, particularly indoors and in presence of mobility, leads to bursty frame corruptions at the link-layer that can last over tens of milliseconds. The detrimental link-layer effects are manifested in the higher layers as packet losses and higher and more variable packet latencies that can severely impact the performance of many WLAN applications such as bulk file transfer, telephony, video streaming and other wireless applications. Figure 1 shows a sample constant rate User Datagram Protocol (UDP) data trace that reflects the magnitude and frequency of losses and delay that can occur in a 802.11b network.

Figure 1: A 15-minute trace of packet transmissions from two access points. Burst loss count is defined as an event where 2 or more packets are lost consecutively in the transmission. (Click image for full resolution figure.)

Traditional approaches to increase loss resilience in WLANs are retransmission and rate adaptation. Retransmission works well when the period of channel degradation is short. But when the channel quality deteriorates for a long period, retransmission becomes ineffective and wasteful. Rate adaptation, on the other hand, can work well even when the wireless channel experiences severe deterioration. However, efficient rate adaptation is difficult to achieve because channel conditions vary quickly and are often unpredictable. Furthermore, both strategies can significantly increase the delay of packet delivery, which could drastically impact the perceived quality of many interactive and delay sensitive applications.

Approach

Typically, a WLAN is a system composed of many access points (AP) that relay packets for a WLAN client. In today's WLAN (e.g., 802.11), each AP operates independently and each WLAN client can communicate with only one AP. When the channel quality of the transmission path deteriorates, the transmitter must either repeat retransmissions until the channel quality improves or reduce the transmission rate to compensate for the poor channel. The net result is increased transmission delay or a loss due to exhausting the retransmission limit or queue overflow.

In practice, APs with overlapping coverage can provide alternate transmission paths for the same client. The observations illustrated in the next section suggest that 1) successful wireless transmissions depends on the physical path traversed by the transmitted signal and 2) the channel quality of different transmission paths varies independently. When both conditions hold, there is a good chance that transmissions will succeed through at least one of the available transmission paths. Based on these observations, we propose to design a new WLAN system, called TR-MAP, which---in contrast to today's WLANs---coordinates packet transmissions and receptions via multiple access points in the effort of recovering lost packets in the wireless medium. TR-MAP exploits the path diversity that is inherent in the physical infrastructure by integrating two path diversity data transmission techniques, fine-grained path selection and spatial packet combining, to reduce path-dependent packet losses and delays in the wireless network.

Design of TR-MAP

Figure 2 shows TR-MAP's system architecture. Each AP offers a different physical transmission path with uncorrelated loss characteristics, and the most reliable communication path between the AP infrastructure a client may change rapidly over time. Our research will explore two path diversity techniques that can be implemented within the TR-MAP architecture using existing WLAN standards such as 802.11 and its variants (11a, 11b, 11g, etc.). The first technique is called fine-grained AP selection. In this technique, the Diversity Monitor (DM) obtains the current channel conditions at each AP and feeds them to the Diversity Controller (DC), which selects the best communication path for downlink transmissions. The DC can switch paths on a frame-by-frame basis, which allows the system to adapt to varying channel conditions quickly and effectively.

Figure 2: TR-MAP's system architecture. (Click image for full resolution figure.)

The main challenge of fine-grained AP selection is designing an efficient and effective algorithm for choosing the appropriate AP for data transmission. In theory, a path-selection algorithm should select the best path for each data frame transmission to reduce loss and delay. To do so, a system must acquire accurate knowledge of the wireless channel condition of each available path within a few milliseconds, which is difficult to implement in practice.

Our hypothesis is that selecting the best path for every data frame is unnecessary to achieve good results. We observe that frame losses usually occur in bursts, especially when the receiver is mobile, and different transmission paths often exhibit weakly correlated channel conditions. Therefore, we develop a path selection heuristic that monitors only the current transmission path. When the current transmission path has fallen into a bad state, the system can avoid burst losses in the original path by diverting the subsequent transmissions to an alternate path.

We develop a second path diversity technique called spatial packet combining. In this technique, we configure multiple APs to listen on the same radio frequency, allowing multiple APs to receive a copy of the client's uplink transmission. The Diversity Controller gathers all received copies of the same transmission and forwards the data on to the rest of the network if any one packet copy is received correctly.

In many cases, corrupted data frames contain a large number of correct data bits, which may be salvaged for error recovery. Thus, when none of the APs receive a correct copy of the transmitted data frame, the Diversity Controller can save the corrupted data frames and perform error recovery by combining the data bits from different corrupted copies of the same transmitted frame. Table 1 illustrates how the packet combining algorithm works.

Because different APs receive a copy of the transmitted data frame simultaneously, the Diversity Controller can often recover a packet immediately without requiring a retransmission from the client. When needed, the Diversity Controller can also perform combining with retransmitted data frames to increase its effectiveness of recovering corrupt packets.

However, the main challenge behind spatial packet diversity is the complexity of the algorithm. The packet combining algorithm locates bit differences between the received copies of the same packet and flips the unmatched bits until the payload passes the data checksum. The combinatorial search in this algorithm has a computational complexity that grows exponentially with respect to the number of corrupt bits in a data frame.

We exploit the observation that bit errors in a frame often occur in bursts. Thus, instead of operating at the bit level, we bound the computational complexity by subdividing a packet into fixed-size blocks and combining packets in the block level.

Experimental Results

We design and implemented TR-MAP as a fully functional WLAN infrastructure optimized for 802.11 WLANs. We deployed a small scale indoor testbed to evaluate the performance of fine-grained path selection and spatial packet combining. Our experimental results show that fine-grained path selection can reduce frame loss rates for mobile clients by as much as 26% compared to a fixed-path scheme that uses the best available transmitter. Spatial packet combining posted gains of up to 55% over single radio communication schemes using a fixed link rate and packet delivery delays were bounded to 20 ms for 99% of the successfully delivered packets. Please refer to our references for a detailed description of TR-MAP's design and analysis of our experimental results.

References

[1] Allen Miu and Hari Balakrishnan. Achieving Loss Resilience through Multi-Radio Diversity in Wireless Networks. In submission.

[2] Allen Miu, Godfrey Tan, Hari Balakrishnan, and John Apostolopoulos. Divert: Fine-grained Path Selection for Wireless LANs. In The Proceedings of the 2nd International Conference on Mobile Systems, Applications and Services (Mobisys 2004), Boston, MA, June 2004.

[3] Allen Miu, John Apostolopoulos, Wai-tian Tan, and Mitchell Trott. Low-Latency Wireless Video Over 802.11 Networks Using Path Diversity. In The Proceedings of the International Conference on Multimedia & Expo, Baltimore, MD, July, 2003.