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.

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.

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.

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.

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.

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 T_header, 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.

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.

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):

where, T_ReTx is the time taken for legacy retransmission, and T_Timeout is the predetermined time for the ACK timeout.

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

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

In this ideal case, the expectation of collision probability E[P_CW] ？ 8, the time interval between collisions T_C = T_DATA/2 and the timeout T_Timeout = T_S + T_ACK. 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.

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.

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.