wiki:802.11/wlan_exp/app_notes/dcf_with_hidden_nodes

Investigating Hidden Nodes and RTS/CTS Access

The Hidden Node Problem is a classic topology studied in wireless networking where the arrangement of nodes prevents traditional carrier sensing from protecting against collisions. In a simple hidden node topology a central node has a high SNR link with two other nodes, but these other nodes are too far apart to detect the other's transmissions. Transmissions by these "hidden" nodes will frequently collide when physical carrier sensing is unable to infer a busy medium at the central node.

Classic Hidden Node Topology

As we have seen in the multiflow app note, carrier sensing plays a crucial role in the DCF's ability deal with contention in a shared wireless medium. In the classic hidden node topology shown above, STA 1 can carrier sense during transmissions by the AP, and vice versa. Likewise STA 2 and the AP can detect each other's transmissions. However STA 1 and STA 2 are out of range of one another and cannot detect each other's transmissions.

The 802.11 MAC design uses virtual carrier sensing and the RTS/CTS handshake to address the hidden node problem. The basic timeline of the RTS/CTS handshake is:

  1. STA 1 wishes to send a data packet (MPDU) to the AP. STA 1 "requests to send" the MPDU by sending a very short RTS frame to the AP. This RTS transmission may still collide with a transmission by STA 2, but the RTS payload is very short, so the cost of losing the RTS is much less than losing the MPDU.
  2. When the AP receives this RTS frame, it checks the medium by looking at its NAV. If the NAV says the medium is clear, it sends the "clear to send" CTS frame in response. This CTS frame contains a duration field that species how long the medium will be occupied for the upcoming MPDU and ACK transmissions. The AP derives this duration value from the duration field in the RTS is received from STA 1.
  3. Since STA 2 is within the transmission range of the AP, it receives this CTS transmission and updates it NAV for the entire duration specified in the CTS frame. The non-zero NAV will prevent STA 2 from transmitting during the subsequent MPDU transmission by STA 1, avoiding an expensive collision.
  4. Finally, STA 1 receives this CTS message and begins the transmission of the actual MPDU. This MPDU is now protected from collisions from anyone who received the RTS or CTS transmissions.

We added support for the standard RTS/CTS handshake in 802.11 Reference Design v1.3. In this application note, we'll use the reference design and its experiments framework to demonstrate the hidden node problem and measure the impact of using the RTS/CTS handshake.

Table of Contents

  1. Experimental Setup
  2. Aggregate Results
  3. Tx/Rx Log Results
  4. A Heuristic Extension
  5. Source Code

Experimental Setup

The experiments described below use 3 Mango WARP v3 kits, each running the 802.11 Reference Design (version v1.3), including the WLAN Experimental Framework. To construct a hidden node topology, we could space nodes apart from one another and lower transmit powers to induce the effect. However, this is not the easiest set up for repeatability of these experiments. Instead, we can artificially "blind" two stations from one another via RF cabling and sufficient attenuation.

Experimental Setup

The above figure shows the wired topology. STA 1 and the AP are suppressed by 50 dB of external attenuation (plus cable loss and 3 dB loss through the power splitter). The same is true for the link between STA 2 and the AP. The link between STA 1 and STA 2, however, involves 100 dB of external attenuation as well as the tens of dB attenuation after leakage between the two input ports of the power splitter. This attenuation is sufficiently large such that neither STA can decode the other's transmissions. Furthermore, it is sufficient attenuation such that neither STA can physically carrier sense each other's transmissions.

Experiment Details

  • Packet Length: 1400 byte payloads (1428 byte MPDUs, with MAC header and FCS)
  • PHY Rate: 12 Mbps (QPSK, code rate 1/2) for data MPDUs
  • Tx Power: 15 dBm
  • 2.4GHz channel 1

We use 2 traffic flows in our experiments:

  • Flow 1: Backlogged traffic from STA 1 to AP
  • Flow 2: Backlogged traffic from STA 2 to AP

In this experiment, we will break up a single trial into three sequential pieces. In the first 30 second phase, we will start Flow 1 all by itself. In the second 30 second phase, we will disable Flow 1 and start Flow 2 by itself. In the third and final 30 second phase, we will enable both Flows 1 and 2. This entire experiment will be performed for both an RTS/CTS disabled case as well as an RTS/CTS enabled case.

Tx/Rx Log Results

In this experiment, we use the Tx/Rx logs in each node to generate Throughput vs. Time results in the same way as the multiflow app note. For brevity, this document will not cover the basics of log processing. Please see the previously mentioned app note as well as the wlan_exp log documentation for more details.

RTS/CTS Disabled RTS/CTS Enabled

In the above plots, we can clearly see the three phases of the experiment over each trial's 90 second duration. There are three fundamental things to notice about RTS/CTS relative to basic access:

  1. During the contention free phases (i.e., the first 60 seconds of each trial), RTS/CTS actually harmed the achieved throughput. We dropped from achieving ~10 Mbps of the 12 Mbps PHY rate to slightly more than 9 Mbps. In the absence of any collisions, RTS and CTS transmissions are purely overhead. Transmitting those frames takes a non-negligible amount of time. That time could have been spent transmitting the actual data MPDUs. The overall cost of this overhead is a function of the duration of each data MPDU. Large sized and low rate transmissions incur a relatively smaller penalty than short and/or high rate transmissions.
  2. During the contention phase (i.e. the last 30 seconds of each trial), we can see the benefit provided by RTS/CTS to overall sum throughput. Without RTS/CTS, the network achieved ~6.5 Mbps. This is a considerable loss over the ideal ~10 Mbps of achievable throughput in the contention-free phases. When RTS/CTS is enabled, however, sum throughput is recovered to 9 Mbps. This is a direct result of the improved virtual carrier sensing ability given to each station when they overhear the AP's CTS to the other station.
  3. In addition to providing a big improvement in sum throughput during the contention, RTS/CTS also radically improves the delay profile of each of the two constituent flows. Notice in the RTS/CTS disabled case that any given slice of time generally sees all throughput from Flow 1 or all throughput from Flow 2 (i.e. the either the red or green line overlaps with the black sum line). This is a result of the binary exponential backoff structure of the DCF. In the event of a collision, contention windows increase and provide a longer window of time to allow another device contention-free access to the medium. The result is an extreme swing of short-term outages for each link. Each STA can potentially be stuck backing off for seconds at a time while the other STA is getting its traffic to the AP. Then, at some point, there is a chance for them to trade places if the STA that was stuck backing off is able to choose a lower slot time than its neighbor. Compare this behavior to the RTS/CTS enabled case. In general, the two stations are splitting the medium and trading off on much smaller timescales.

So, should devices use RTS/CTS? The answer is not obvious. There is clearly an inherent tradeoff between the increased overhead caused by RTS/CTS and the benefits to improved carrier sensing range. Which side wins this tradeoff is dependent on many factors including the size of the payload being delivered, the overall network contention, and the network topology. The 802.11 Standard notes this and defines a "dot11RTSThreshold" that can be specified by equipment manufacturers. Any MPDU above this threshold is considered "long" and the overhead of the RTS/CTS exchange is considered "worth it." Anything lower than this threshold uses basic access without RTS/CTS. However, we have seen from our previous experiment than even fairly long (1400 byte) frames and fairly low rates (12 Mbps) still exhibit a non-obvious tradeoff in the utility of RTS/CTS.

In the next section, we will see if we can do better than simply enabling or disabling RTS/CTS as a function of packet size.

A Heuristic Extension

First, we begin with an important disclaimer. The extension described in this section is not and should not be considered paper-worthy research. It is an obvious, intuitive extension and it is inadequately defended for peer-reviewed publication. The extension is only exposed to this single extreme hidden node example and not exposed to any kind of rigorous empirical study with varied topologies and traffic profiles. This is not the point of this application note. Instead, the purpose of this document is to show how a handful of easy changes to the C-code of the 802.11 Reference Design can radically change the behavior of the MAC protocol. Furthermore, it demonstrates how tools like the wlan_exp framework can be used to study those radical changes in behavior. In short, it is a glimpse at one way the 802.11 Reference Design can be used to study research problems.

One way to resolve the tradeoff is to teach the node to recognize a heavy-contention period from a light-contention period. During the heavy-contention period, the node could enable RTS/CTS to mitigate the effects of collision from hidden nodes. During the light-contention period, the node could disable RTS/CTS to improve efficiency. The DCF already has a parameter that correlates to the amount of contention: the contention window.

Here, we will intuit a small extension to the DCF that allows it to adaptively enable and disable the RTS/CTS structure as a function of the behavior of its contention window. When a contention window increases, this is a piece of evidence that indicates a collision may have occurred and overall contention may be increasing. Conversely, when a contention window resets due to the successful receipt of an ACK, this is a piece of evidence that indicates that we may be entering a light-contention period. Let's define two variables for tracking this behavior: num_consecutive_cw_increases and num_consecutive_cw_resets. num_consecutive_cw_increases will be used to track the number of consecutive times a contention window increases. If a contention window reset occurs, num_consecutive_cw_increases is set back to zero as the chain of increases has been broken. num_consecutive_cw_resets tracks the number of times that contention window resets have consecutively occurred. If a contention window increases, num_consecutive_cw_resets is set back to zero as the chain of resets has been broken.

Finally, we define two parameters RTS_EN_THRESH and RTS_DIS_THRESH. RTS_EN_THRESH defines the number of consecutive contention window increases that must occur before the node decides that enabling RTS/CTS is a good idea. RTS_DIS_THRESH defines the number of consecutive contention window resets that must occur before the node is comfortable disabling RTS/CTS. In this way, RTS_EN_THRESH and RTS_DIS_THRESH can be set to change how aggressively the node reacts to contention window changes with enabling and disabling the RTS/CTS structure. For this example, we will require RTS_EN_THRESH = 5 consecutive CW increases before we enable RTS/CTS and require RTS_DIS_THRESH = 100 consecutive CW resets to disable RTS/CTS.

This simple protocol is easy to add to the existing DCF implementation. The key changes required are:

  1. At the top of wlan_mac.c, we will define some global variables and preprocessor definitions for the parameters described earlier. Namely,
#define RTS_EN_THRESH   5
#define RTS_DIS_THRESH  100
volatile u32                           num_consecutive_cw_increases;
volatile u32                           num_consecutive_cw_resets;

The two global variables should be set to 0 in the main() function of the code to given the algorithm a sane starting point.

  1. We should add a new function to wlan_mac_dcf.c that resets the num_consecutive_cw_increases variable and increments the num_consecutive_cw_resets variable. Furthermore, if the newly increased num_consecutive_cw_resets variable exceeds the RTS_DIS_THRESH, we should disable RTS/CTS.
inline void reset_cons_cw_count(){
    num_consecutive_cw_increases = 0;
    num_consecutive_cw_resets++;
    if(num_consecutive_cw_resets >= RTS_DIS_THRESH){
        gl_dot11RTSThreshold = 2000; //Turns off RTS/CTS since this threshold is larger than an MTU
    }
}
  1. We should call this new reset_cons_cw_count() function in nearly every place that the existing reset_cw() function. The two exceptions to this are in the increment_src_ssrc() and increment_lrc_slrc() functions. Those calls to reset_cw() do not indicate a success, but rather a very specific requirement in the 802.11 standard that is discussed in detail in this document. In every other case, a call to reset_cons_cw_count() should be added just prior to reset_cw().
  1. A small code snippet should be added to the very top of both the increment_src_ssrc() and increment_lrc_slrc() functions:
    num_consecutive_cw_increases++;
    num_consecutive_cw_resets = 0;
    if(num_consecutive_cw_increases >= RTS_EN_THRESH){
        gl_dot11RTSThreshold = 0; //Too many CW increases. Fall back on RTS/CTS
    }

The above small changes to the codebase are enough to implement our new heuristic protocol for adaptively enabling and disabling RTS/CTS. So how does it perform? For completeness and ease of comparison, we will include the previous results when RTS/CTS was permanently disable and permanently enabled.

RTS/CTS Disabled RTS/CTS Enabled RTS/CTS Adaptive

We see that this simple adaptive protocol successfully combines the benefits of RTS/CTS during the contention period with the efficiency of basic access during the contention-free period. The flexibility of the C implementation of the DCF in the Mango 802.11 Reference Design allowed implementing this behavior in about 10 lines of code and wlan_exp allowed us to immediately measure the effects of those changes.


Resources

Python Scripts

Download: hidden_node_python_scripts_v1_00.zip

Zip Contents:

  • hidden_node_experiment.py - This script will run the experiment and write the log files from each board to the directory in which this script is executed.
  • hidden_node_plotter.py - This script will open the generated log files and produce the plots used in the application note.
  • log_analysis_util.py - Utility script that is used by hidden_node_plotter.py. This should not be run directly. Instead, it should be in the same directory as hidden_node_plotter.py
Last modified 9 years ago Last modified on Jun 24, 2015, 10:45:24 AM

Attachments (1)

Download all attachments as: .zip