Fast Retransmission Scheme for Overcoming Hidden Node Problem in IEEE 802.11 Networks

  • cc icon
  • ABSTRACT

    To avoid collisions, IEEE 802.11 medium access control (MAC) uses predetermined inter-frame spaces and the random back-off pro-cess. However, the retransmission strategy of IEEE 802.11 MAC results in considerable time wastage. The hidden node problem is well known in wireless networks; it aggravates the consequences of time wastage for retransmission. Many collision prevention and recovery approaches have been proposed to solve the hidden node problem, but all of them have complex control overhead. In this paper, we propose a fast retransmission scheme as a recovery approach. The proposed scheme identifies collisions caused by hidden nodes and then allows retransmission without collision. Analysis and simulations show that the proposed scheme has greater through-put than request-to-send and clear-to-send (RTS/CTS) and a shorter average waiting time.


  • KEYWORD

    Medium access control , Collision , RTS/CTS , High data rate , Preamble correlation

  • I. INTRODUCTION

    Distributed coordination function (DCF) is the random medium access mechanism in IEEE 802.11[1]. In DCF, a trans-mitter sends data after waiting for the distributed inter-frame space (DIFS) time and an additional random back-off time to avoid collisions. If the sender does not receive an ACK within a predetermined time, the transmitter starts the retransmission mechanism. To avoid another transmission failure, the node uses a binary exponential back-off algorithm (Fig. 1) to choose a new random back-off number in the doubled Contention Win-dow (CW). This strategy results in inefficient retransmission, because it increases the medium access time.

    The hidden node problem is a well known problem that occurs in wireless networks. For retransmission, it aggravates the consequences of time wastage [2]. Nodes that are hidden from one another may not be able to sense the carrier signal, so that their transmissions result in frequent collisions. Therefore, the hidden node problem significantly degrades network throughput because there will be numerous collisions and retransmissions.

    It has been suggested that the use of the Request-To-Send and Clear-to-Send (RTS/CTS) control frame exchange solves the hidden node problem [1]. Although RTS/CTS can reduce collisions between hidden nodes, it results in control overhead. This control overhead degrades the network throughput, especially in high-speed wireless networks [3]. Some variants [4-7] based on RTS/CTS will be discussed later.

    In this paper, we propose a fast retransmission scheme to solve the hidden node problem. In the proposed scheme, the receiver can use preamble correlation to identify collisions caused by hidden nodes. We introduce a new control frame called Negative-acknowledgement (N-ACK), which the access point uses to identify collisions caused by hidden nodes. When the victim node receives the N-ACK, it is allowed to retransmit data without contention. The offending node also recognizes collisions by overhearing the N-ACK, and tries to retransmit data after the victim node’s retransmission.

    Unlike previous retransmission methods, the victim node is assured to be collision free, because of the N-ACK’s duration field. Moreover, the offending node does not require back-off time, thus, collided frames can be rapidly retransmitted. Analy-sis and simulations show that compared to RTS/CTS, the pro-posed scheme has greater throughput and the transmission time of a single data frame at high data rates is shorter.

    The remainder of this paper is organized as follows: Section II presents related work and Section III describes our proposed scheme. In Section IV, a comparison of the throughput and waiting time is made between the proposed scheme and the DCF scheme that uses RTS/CTS. The comparison is based on analysis and simulation results. Finally, Section V presents a discussion and the conclusion.

    II. RELATED WORK

    Two kinds of approaches have been used to solve the hidden node problem: collision prevention and recovery.

    Collision prevention schemes avoid collisions by reserving the channel for the duration of the transmission. Most of these schemes utilize control frames or out-of-band busy tones. The Floor Acquisition Multiple Access (FAMA) protocol [4] avoids data collisions by using RTS/CTS frame exchange. In wireless networks, RTS/CTS frame exchanges cannot eliminate colli-sions owing to variations in propagation time, thus, the FAMA protocol uses dynamic carrier sensing to allow a node to get control of the channel before data transmission. Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) is a kind of FAMA protocol having a sufficiently long carrier sens-ing time.

    The RTS Collision Avoidance (RCA) MAC protocol [5] is another collision prevention scheme. It announces the control frame transmission to two-hop neighbors in advance. It prevents collisions by using a transmitting pulse and tone signals at the beginning and end of the last time slot. These approaches may reduce hidden node collisions, but they have large control over-head and involve the additional cost of using an out-of-band channel.

    The Dual Busy Tone Multiple Access (DBTMA) MAC pro-tocol [8] uses two radio devices for two channels: a data chan-nel for data transmission and a narrow-band tone channel for interference protection. The sender simultaneously transmits the tone signal and control frame through the tone channel and data channel, respectively. When the receiver receives the tone sig-nal and RTS frame, to prevent transmission from hidden nodes, it sends the tone signal through the tone channel until data trans-mission is completed.

    Collision recovery schemes alleviate the effect of collisions. ZigZag decoding [9] can recover collided frames even when multiple frames collide. Using iterative decoding, collided frames can be decoded. Although this is a new method, to ensure correct decoding, every frame should have the same size.

    CSMA with Collision Notification (CSMA/CN) [10] recov-ers from collisions by using two antennas, transceiver and receiver, to quickly inform the transmitter that a collision has occurred. When the receiver detects the collision, it immedi-ately transmits a unique signature to the sender’s listener antenna. When the transmitter receives the collision notification, it aborts data transmission and releases the channel for other transmit-ters. However, the transmitter may miss collision notifications, because the listener antenna can be overwhelmed by its trans-mitting signal.

    Fast retransmission is another collision recovery approach that induces a very small retransmission delay. Dynamically Adaptive Retransmission (DAR) [6] is a retransmission scheme based on the RTS/CTS frame exchange. In DAR, the receiver sends control frames, including additional information on the transmission status of the unacknowledged frame. Then, the transmitter determines the retransmission requirement by refer-encing the information on the control frames.

    Efficient and Fast Retransmission (EFR) [7] is another fast retransmission scheme in which a duplicated CTS triggers immediate retransmission without competition. Though both DAR and EFR provide fast retransmission, they also have high control overhead. Moreover, in general, schemes based on RTS/CTS frame exchange are designed for collision avoidance.

    Our proposed method is a fast retransmission scheme that facilitates fast sequential retransmission in transmitters. The proposed scheme is simple but reduces the retransmission delay without using RTS/CTS frame exchange.

    III. FAST RETRANSMISSION

    This section describes the proposed scheme, which is a fast retransmission mechanism. We refer to collisions caused by hidden nodes as hidden collision. We assume that if node A is hidden from nodes B and C, then the latter are not hidden from each other. Based on this assumption, only hidden collision cases are possible (Fig. 2). We focus on a single Basic Service Set (BSS). In such a case, hidden collisions can only occur at an access point (AP) that has no hidden nodes, because all nodes are in the AP’s transmission range. In the following subsections, we explain how to detect collisions at the AP and then present

    the details of the proposed fast retransmission mechanism.

      >  A. Collision Detection

    In wireless networks, a sender cannot transmit and receive simultaneously, because its own signal strength at its antenna is much stronger than signals from any other nodes. Thus, a receiver can only detect collisions by using Cyclic Redundancy Checking (CRC), which may fail because of channel noise, identical back-off time and hidden nodes. Because failures that have different causes will have different solutions, it is impor-tant that the receiver identifies the reason for the failure of CRC. However, the receiver does not differentiate between different types of failures in wireless networks. The AP discards the packet and does not transmit an ACK.

    To increase the accuracy of hidden collision detection, we propose that the AP exploits the PLCP preamble in the physical layer packet. The PLCP preamble is associated with Pseudo-Random Noise (PRN) in wireless communications, which con-sists of a predetermined sequence of pulses. It is an optimal deterministic periodic signal with statistical properties similar to those of Gaussian White Noise [11]. Theoretically, the PLCP preamble is independent of other signals owing to the properties of PRN. Thus, the PLCP preamble can be detected even when it overlaps with other signals. When the receiver receives a signal, it performs preamble correlation to check whether the signal is a packet [9, 10]. If the correlation exceeds a threshold, the receiver signals packet detection by setting the flag value to 1, and subsequent symbols are considered as data frames [12] (Fig. 3). Therefore, the AP can identify hidden collisions if a preamble is detected while a packet is being received.

    In our system, the AP tries to decode the collided frame despite hidden collision. When the 2nd frame has arrived after the MAC header of the 1st frame is successfully received, the AP can obtain information about the MAC address, the frame type and the duration of the first frame. The proposed scheme exploits this information to provide fast retransmission to the collided nodes.

      >  B. Fast Retransmission Mechanism

    We define a new control frame called N-ACK for the pro-posed scheme. Nodes at which a hidden collision has occurred at the AP overhear the N-ACK and use it to determine the fast retransmission requirement. In the MAC frame, 6 bits of type and subtype fields are defined to distinguish the frames. The control frames are defined by type 01, and these are sub-divided into several subtypes. In the 802.11 MAC, the subtype value for the control frame is small and we can define a new control frame without any modification (Table 1). The N-ACK used for the notification of hidden collisions has the subtype field 1001, and the rest of the frame structure is the same as the ACK. Nodes that overhear the N-ACK may not start transmission because of the duration field of the N-ACK.

    After a hidden collision occurs and there is sufficient time to decode the MAC header of the first packet, the AP detects the hidden collision and extracts information from the MAC header of the first frame. Then the AP sends the N-ACK to the first sender, however, every node including the hidden nodes over-hears the N-ACK. After receiving the N-ACK, the first sender tries to retransmit after waiting for a point coordination function-IFS (PIFS). The first sender immediately begins fast retransmis-sion, even if it has already started legacy retransmission. Note that if the node is given an SIFS or PIFS, it can have higher pri-ority access to the channel and guarantee lack of collision in 802.11 MAC. After the first sender completes retransmission, the AP responds by sending an ACK frame to it. The second sender overhears the ACK and then tries retransmission after waiting for a DIFS with no back-off time. Because there is no

    back-off time, the second sender can transmit data without con-tention. Sometimes, the retransmission of the second sender may collide with another transmission, because there is not just one second sender (Fig. 4). In this case, the second senders suf-fer from successive collisions. However the probability of this scenario is very low. Moreover, even if multiple hidden colli-sions occur, at least the first sender retransmits successfully.

    We believe that the proposed fast retransmission scheme is simple and reduces the retransmission time. The following pseudo-code describes the proposed algorithm.

    image

    For example, assume that two transmitters N1 and N2 are hidden from each other and are associated with an AP (Fig. 5). In the proposed scheme, when a hidden collision occurs after time Theader, the AP detects it and sends a N-ACK to N1, which

    retransmits data without contention. When N2 overhears the ACK corresponding to the retransmission of N1, it retransmits the data.

    IV. ANALYSIS AND SIMULATION

    In this section, we discuss the theoretical analysis and the simulation used to compare the performance of the proposed scheme with that of the 802.11 DCF and RTS/CTS schemes.

      >  A. Theoretical Analysis

    For simplicity, we assume an ideal environment in which two nodes that are hidden from each other want to transmit a single frame to an AP. We analyze the time required for transmission in this case.

    The total time taken by the 802.11 DCF scheme, the 802.11 DCF scheme with RTS/CTS, and the proposed scheme can be obtained easily (symbols: Table 2):

    image
    image

    where, TReTx is the time taken for legacy retransmission, and TTimeout is the predetermined time for the ACK timeout.

    image
    image
    image

    where, TControl is the time taken for exchange of control frames, and TTx is the time taken for a single data transmission.

    image
    image

    where, TFastReTx is the time taken for the proposed scheme.

    In this ideal case, the expectation of collision probability E[PCW] ? 8, the time interval between collisions TC = TDATA/2 and the timeout TTimeout = TS + TACK. This implies that the nodes start retransmission after waiting for a duration that is equal to the sum of the SIFS and the transmission time of the ACK frame. We focus on high data rate networks, thus, we analyze

    the performance on the basis of 802.11g, in which the maximum data rate is 54 Mbps.

    The total time taken in the proposed scheme sharply decreases as the data rate is increased, because the data transmission time is reduced according to the increase in the data rate (Fig. 6). However, RTS/CTS causes time wastage owing to the large control overhead in high data rate wireless networks. Therefore, the proposed scheme is less time-consuming than the 802.11 DCF and RTS/CTS schemes.

      >  B. Simulation and Results

    In this subsection, we discuss the simulation used to compare the performance of the proposed scheme with the 802.11 DCF and RTS/CTS schemes. The simulation is based on 802.11g and the simulation environment consists of a single AP and the nodes within its transmission range. All nodes always have data to transmit, and the network is saturated. The simulation param-eters (Table 3) are identical to those specified for IEEE 802.11g [13].

    In the simulation, the metrics used are as follows: the throughput is the ratio of the data transmission time to the total simulation time, and the average waiting time is the average waiting time for a data transmission.

    The normalized throughput of the proposed scheme was higher than those of the 802.11 DCF and RTS/CTS schemes (Fig. 7). Because the overhead for exchanging control frames is large and the probability of hidden collisions is low for high

    data rates, RTS/CTS has low throughput. Over many iterations of the simulation, the proposed scheme had a throughput that was greater than RTS/CTS. However, the throughput of the pro-posed scheme sharply decreased as the number of nodes increased, because it cannot perfectly resolve the hidden node problem.

    We also compared the average waiting time of the proposed scheme with that of RTS/CTS. The average waiting time for a data transmission is the sum of the IFSs and the back-off time. If a collision occurs, the previous transmission time is added to the waiting time. The proposed scheme had a shorter waiting time than that of RTS/CTS (Fig. 8). Because the waiting time is strongly dependent on the back-off time and the proposed scheme has no back-off time when a hidden collision occurs, its

    average waiting time is low.

    V. DISCUSSION AND CONCLUSION

    In the IEEE 802.11 MAC, the hidden node problem significantly degrades the network throughput. It has been suggested that the use of RTS/CTS helps avoid collisions due to hidden nodes. However, exchanging control frames results in large overhead in high data rate WLANs. We proposed a fast retransmission scheme to alleviate the hidden node problem. This scheme uses a newly-defined control frame called a N-ACK to compensate for hidden collisions. In our system, the receiver detects collisions caused by hidden nodes and then uses the N-ACK to notify nodes. In an ideal environment where there is no channel noise and nodes want to send a single data frame, the total time taken in the proposed scheme is less than that in RTS/CTS. Moreover, the probability of hidden collisions is low when the data rate is high, so RTS/CTS has low throughput. Simulation data show that the proposed scheme has greater throughput than RTS/CTS and a shorter average waiting time.

  • 1. 2007 IEEE Std 802.11-2007 (Revision of IEEE Std 802.11-1999), IEEE Standard for Information Technology-Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications google
  • 2. Khurana S, Kahol A, Jayasumana A. P 1998 “Effect of hidden terminals on the performance of IEEE 802.11 MAC protocol” [Proceedings of the 23rd Annual Conference on Local Computer Networks] P.12-20 google
  • 3. Xu K, Gerla M, Bae S 2002 “How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks” [Proceedings of the IEEE Global Telecommunications Conference] P.72-76 google
  • 4. Garces R, Garcia-Luna-Aceves J. J 1996 “Floor acquisition mul-tiple access with collision resolution” [presented at Proceedings of the 2nd Annual International Conference on Mobile Comput-ing and Networking] P.187-197 google
  • 5. Shih K. P, Liao W. H, Chen H. C, Chou C. M 2009 “On avoid-ing RTS collisions for IEEE 802.11-based wireless ad hoc net-works” [Computer Communications] Vol.32 P.69-77 google doi
  • 6. Wang H. L, Miao J, Chang J. M 2003 “An enhanced IEEE 802.11 retransmission scheme” [Proceedings of the IEEE Wire-less Communications and Networking] P.66-71 google
  • 7. Tseng H. W, Pang A. C, Kuo C. F, Sheu S. T 2006 “Efficient and fast retransmission for wireless networks” [Computer Com-munications] Vol.29 P.2964-2974 google doi
  • 8. Haas Z. J, Deng J 2002 “Dual busy tone multiple access (DBTMA)-a multiple access control scheme for ad hoc net-works” [IEEE Transactions on Communications] Vol.50 P.975-985 google doi
  • 9. Gollakota S, Katabi D 2008 “Zigzag decoding: combating hid-den terminals in wireless networks” [Proceedings of the ACM SIGCOMM Conference on Data Communication] P.159-170 google
  • 10. Sen S, Choudhury R. R, Nelakuditi S 2010 “CSMA/CN: carrier sense multiple access with collision notification” [Proceedings of the Sixteenth Annual International Conference on Mobile Com-puting and Networking] P.25-36 google
  • 11. Desain P, Farquhar J, Blankespoor J, Gielen S 2008 “Detecting spread spectrum pseudo random noise tags in EEG/MEG using a structure-based decomposition” [Proceedings of the 4th Interna-tional Brain-Computer Interface Workshop and Training Course] google
  • 12. Blossom E 2004 “GNU Radio: tools for exploring the radio fre-quency spectrum” [Linux Journal] P.4 google
  • 13. 2003 IEEE Std P802.11g/D8.2, Draft Supplement to Standard [for] Information Technology Telecommunications and information exchange between systems Local and metropolitan area networks Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Further Higher Data Rate Extension in the 2.4 GHz band (Amendment to IEEE Std 802.11, 1999 Edition) google
  • [Fig. 1.] Retransmission mechanism of IEEE 802.11 medium access control (MAC). To avoid collisions the node selects the back-off time from a double-sized CW; the CW of B2 is twice as long as that of B1. DIFS: distributed inter-frame space SIFS: shortest inter-frame space.
    Retransmission mechanism of IEEE 802.11 medium access control (MAC). To avoid collisions the node selects the back-off time from a double-sized CW; the CW of B2 is twice as long as that of B1. DIFS: distributed inter-frame space SIFS: shortest inter-frame space.
  • [Fig. 2.] Hidden collision from nodes A and B. If B’s packet arrives at the access point (AP) after it has successfully received the medium access control (MAC) header of A’s packet the AP can obtain the information on node A.
    Hidden collision from nodes A and B. If B’s packet arrives at the access point (AP) after it has successfully received the medium access control (MAC) header of A’s packet the AP can obtain the information on node A.
  • [Fig. 3.] GNU Radio receiver system. All signals received from the antenna must be examined to detect preambles. MAC: medium access control.
    GNU Radio receiver system. All signals received from the antenna must be examined to detect preambles. MAC: medium access control.
  • [Table 1.] Type and subtypes of control frames
    Type and subtypes of control frames
  • [Fig. 4.] Multiple hidden collisions resulting from the same back-off time. In this case the frames from nodes B and C collide again. AP: access point.
    Multiple hidden collisions resulting from the same back-off time. In this case the frames from nodes B and C collide again. AP: access point.
  • [Fig. 5.] Example of fast retransmission. The nodes N1 and N2 experience a hidden collision and the AP informs them about it by sending the N-ACK frame. The victims of the hidden collision retransmit their data frames without contention and collisions (AP: access point D: distributed inter-frame space S: shortest inter-frame space P: PCF inter-frame space B: back-off time).
    Example of fast retransmission. The nodes N1 and N2 experience a hidden collision and the AP informs them about it by sending the N-ACK frame. The victims of the hidden collision retransmit their data frames without contention and collisions (AP: access point D: distributed inter-frame space S: shortest inter-frame space P: PCF inter-frame space B: back-off time).
  • [Table 2.] Summary of notation
    Summary of notation
  • [Fig. 6.] Total single frame transmission time. The frame size is 500 bytes and the remaining parameters are identical to those specified for IEEE 802.11g. DCF: distributed coordination function RTS/CTS: request-to-send and clear-to-send.
    Total single frame transmission time. The frame size is 500 bytes and the remaining parameters are identical to those specified for IEEE 802.11g. DCF: distributed coordination function RTS/CTS: request-to-send and clear-to-send.
  • [Table 3.] Simulation parameters
    Simulation parameters
  • [Fig. 7.] Normalized throughput of the three schemes. DCF: distributed coordination function RTS/CTS: request-to-send and clear-to-send.
    Normalized throughput of the three schemes. DCF: distributed coordination function RTS/CTS: request-to-send and clear-to-send.
  • [Fig. 8.] Average waiting time in the proposed scheme (filled circles) and the 802.11 DCF scheme with RTS/CTS (empty circles) DCF: distributed coordination function RTS/CTS: request-to-send and clear-to-send.
    Average waiting time in the proposed scheme (filled circles) and the 802.11 DCF scheme with RTS/CTS (empty circles) DCF: distributed coordination function RTS/CTS: request-to-send and clear-to-send.