Algorithm

Proposed Approach:

The primary goal of this project was to develop new media access layer techniques that works efficiently in the wireless multihop environment, i.e., preserve battery power and bandwidth, provide QoS support and adhere to legacy standards, i.e., IEEE 802.11. We introduced a new MAC protocol, denoted by CSMA/CA2. The proposed scheme automatically adapts each node transmission rate to the bandwidth usage and the number of active nodes in the network. Our analysis and simulation studies demonstrate that the proposed CSMA/CA2 scheme has the following advantages:

1.               it achieves significant power and bandwidth savings with reduced medium access delay compared to IEEE 802.11 CSMA/CA.

2.               it is easy to implement, i.e., CSMA/CA2 has low computational complexity and does not require additional control packets or buffers. 

3.               it provides fair channel sharing with fast convergence

4.               it is compatible with the IEEE 802.11 standard, i.e., nodes with both CSMA/CA and CSMA/CA2 can coexist in the same network.

5.               it can provide quality of service (QoS) support to different traffic classes. 

We investigated in depth the following aspects of the proposed protocol:  

1.               Theoretical analysis: Stability of a linearized model ensures smooth and efficient rate control. Our analysis demonstrated system stability based on a linear model of the channel collisions and the node maximum sending rate. Moreover, we also studied the quantitative relationship between system convergence speed and the CSMA/CA2 parameters.

2.               QoS support: Adjusting (increasing/decreasing) the control parameters allows the system to provide different QoS support to different senders.  Our analysis indicates that while stability for systems with homogeneous nodes is easily achievable, greater care is needed for obtaining stability in networks with heterogeneous nodes that require QoS support. Through thorough analysis, both theoretical and experimental, we have determined the relationship between these parameters and the QoS achieved.

3.               CSMA/CA2 impact on higher layer protocols and end-to-end application performance: Various higher layer traffic control protocols have been proposed in recent years to improve the current CSMA/CA performance and to provide QoS support. Although the smoothness of our proposed protocol should improve the interactions between the layers, there is a need to understand such interactions under various scenarios.  Our control theoretical models for the proposed CSMA/CA2 protocol enable a fruitful study of the end-to-end performance issues.

4.               Simulation model development: We have used OPNET [3] for the simulation study. Using the OPNET modeler have been able to provide an accurate description of the proposed CSMA/CA2 scheme. We  used this model for validating our analysis.

A Graceful Control Protocol - CSMA/CA2

The inefficiency of CSMA/CA in handling multimedia and multihop traffic results from the following three factors. First, doubling the contention window upon collision is an overreaction and may result in inefficient channel utilization. Second, restoring the contention window to the minimum after a successful transmission maybe too aggressive and may result in many collisions. Such strategy is suitable only for relatively low loads. Third, the back-off interval of each competing node progresses only when the channel is idle. Such behavior causes nondeterministic effect on rate regulation and channel collisions.  

This motivated us to propose a more graceful regulation protocol. The transmission rate of each node will be adjusted using an additive increase multiplicative decrease (AIMD) scheme. Notice that such an AIMD based mechanism is also implemented in the Internet TCP suite in order to control the network congestion and provide fairness to competing traffic streams. However, the use of an AIMD scheme in TCP was shown not to be always fair due to the variability in the round trip times. More importantly, the significant feedback delay in the Internet TCP congestion control loop leads to inefficiency in bandwidth usage. In our case, since we control the transmissions of a local area network where the feedback is obtained within a very short period of time, the proposed AIMD based control mechanism is very effective. In the remaining part of this section we describe the proposed algorithm. 

2.1 CSMA/CA2 Algorithm

The difference between CSMA/CA2 and CSMA/CA lies in the following two factors:

1.                            computation of the backoff interval: CSMA/CA2 uses a small fixed contention window size CW while CSMA/CA uses an exponentially increasing contention window size. This small contention window in CSMA/CA2 is used to avoid sender synchronization on the channel competition when the channel status changes from busy to idle.

2.                            use of a gapping interval: in CSMA/CA2 a gapping interval, generated from the uniform distribution between [0, G], is inserted between two consecutive packet transmissions. This gapping regulates the sending rate of the node. Note that, unlike the back-off interval, the progress of the gapping interval duration will not be suspended when the channel is busy. 

By default, the value of CW is set to CWmin as defined in IEEE 802.11 standard and the value of G is set to 0 when the node does not have packets to send. We observe that as long as no collision occurs, there is no need for rate control and our CSMA/CA2 functions exactly the same as CSMA/CA. With the existence of channel collision, CSMA/CA2 gracefully adjusts the gapping interval duration G to reach the system equilibrium point where the network performance is optimized. We describe next this adaptation mechanism.

Figure 1: CSMA/CA2 vs CSMA/CA  

As shown in Figure 1, the transmission rate of each node i is regulated by inserting a gapping interval of duration  between consecutive packet transmission attempts. The normalized sending rate  for each CSMA/CA2 node is given by:

                                                                            (1)

where B is the estimated duration of the CSMA/CA2 ON period, which is defined as the interval of time it takes to make one packet transmission. We will provide the estimated duration B below.

We observe that by controlling  we can adaptively control  between 1 and 0. To provide fair sharing of the channel and adapt to environmental changes, we regulate the normalized sending rate  using the Additive Increase Multiplicative Decrease (AIMD)  scheme as follows:

1. in case of transmission failure, each node decreases the normalized sending rate  by ratio :

                                                                     (2)

2. in case of a successful transmission, the node increases the normalized sending rate by a constant rate :

                                                                          (3)

By adjusting the gap duration , our scheme seeks for the equilibrium point of the network so that the normalized sending rate  of each competitor is optimized for high channel utilization and fair sharing. CSMA/CA2’s gap adjustment procedure is shown in Figure 2 below:

                               

Procedure update_gap ( )   /* called after each transmission attempt *

                                             Begin

                                                                            if (Ack received)  /* successful transmission */

                                                                                            /* additive increase normalized rate by */

                                                            else /* transmission failure*/

                                                            /* multiplicative decrease normalized rate by  */

                                                           if (< 0) /* the minimum value of gapping is 0*/

                                             = 0

                                                             end

Figure 2: CSMA/CA2 gap adjustment procedure

 

As shown in Figure 2, the duration of the ON period, B, will influence our rate control. In the calculation of the ON period duration we differentiate between two modes of operation of CSMA/CA2:

Case 1: In case there is no RTS/CTS exchange B is given by:

 

           (4)

 

where C is the node data rate, is the duration of a time slot,  is the short inter-frame spacing interval,  is the distributed inter-frame spacing interval,  is the minimum contention window size,  is the average packet size at the MAC layer and  is the time interval that the sender waits for the MAC layer acknowledgement. The values of these parameters are determined by the IEEE 802.11 standard.

 

Case 2: If RTS/CTS control packets are used before data transmission, we have (see Figure 3): 

                 (5)

 

In such case,  is used instead of B in the calculations.

Figure 3: CSMA/CA2 with RTS/CTS

 

Unlike TCP feedback control, our CSMA/CA2 scheme has the advantage of instant feedback to the senders with similar round-trip times. Thus, the convergence, stability, variance and fairness of the system are much more sensitive to the control parameters used.