Patent Publication Number: US-7215681-B2

Title: Adaptive channel access for carrier sense multiple access based systems

Description:
TECHNICAL FIELD 
     The present invention relates, in general, to network communications using carrier sense multiple access (CSMA). More specifically, the present invention relates to a method of controlling access rate to a CSMA communications channel by adaptively adjusting a time length of a contention interval (CI). 
     BACKGROUND OF THE INVENTION 
     Nodes in a CSMA network do not have a priority sequence for communicating with each other. Instead, any node may transmit at any time with the same priority as any other node in the network. Since nodes may attempt to transmit packets at the same time, the packets may interfere with each other, resulting in collisions. As nodes attempt a retransmission, after detecting a collision, system load in the network is typically increased. 
     Each node using CSMA protocol measures time from a last activity on a shared channel in equal time slots of a contention interval. A transmitting node in the network generates a random number, then counts a corresponding number of time slots until the random number is reached. At that point, the node may attempt to occupy the channel and other nodes may suspend their count until the channel is free again. If two nodes generate the same random number, by chance, and consequently collide, each then may generate a new random number and start counting time slots from zero in the next contention interval. 
     In a CSMA based network, nodes sense the channel before transmitting a data packet to another node. In a CSMA with collision detection (CSMA/CD) based network, nodes detect collision before transmitting, and stop transmitting if noise is sensed in the channel. In a CSMA with collision avoidance (CSMA/CA) based network, nodes listen to any activity and reserve a space in the channel to avoid collision. 
     To reduce the occurrence of collisions in networks, channel reservation may be deployed. Typically, reservation involves two-way communications between a transmitting node and a receiving node. When a data packet arrives from an upper layer (for example an Internet communications application), the transmitting node first reserves channel space for the transmission of the data packet. If the transmitting node detects that channel space is available, the node schedules transmission of a request-to-send (RTS) packet to a receiving node, after a generated random interval is reached. In doing so, the transmitting node informs the receiving node of the pending data packet and allows the receiving node to determine if the transmitting node may transmit the data packet over the available channel space. If the receiving node senses that channel space is available, a clear-to-send (CTS) packet is returned to the transmitting node and the channel space is reserved. After receiving the CTS packet, the transmitting node transmits the data packet over the reserved channel. By allowing the receiving node to determine whether the transmitting node may transmit the data packet, the probability of collision due to hidden nodes is reduced. In addition, collisions of multiple RTS packets, simultaneously transmitted over the channel by neighboring nodes, may also be reduced. 
     In general, the random delay, in number of time slots of a contention interval, is uniformly selected from a range of one time slot up to a maximum number of time slots in the contention interval, where the length of the contention interval is predetermined. 
     Because access rate of a node is fixed by the initial predetermined CI length, channel access rate (CAR) in the network cannot be adjusted, when more nodes than initially expected start to content for limited channel resources. In an IEEE 802.11 protocol standard, the CI length may be temporarily lengthened to lessen channel congestion at the expense of higher channel access rate. IEEE 802.11 protocol resets the CI length to its initial predetermined value, after a channel access attempt is successful. Knowledge of a prior successful channel access is not utilized in a subsequent channel access attempt. As a result, performance of the IEEE 802.11 protocol is limited. 
     What is needed is a system and method of controlling the CAR in a communications network by adaptively adjusting the length of the CI based on previous knowledge of traffic conditions or channel occupancy conditions in the network. This invention addresses this need. 
     SUMMARY OF INVENTION 
     To meet this and other needs, and in view of its purpose, the present invention provides a system and method of adaptively adjusting the length of a contention interval (CI) used for accessing a communications channel in a carrier sense multiple access (CSMA) based network. 
     In a network including multiple nodes communicating on a channel using CSMA protocol, where each node accesses the channel by occupying at least one time slot in a contention interval, an exemplary method of the invention includes transmitting and receiving, in a node, messages on the channel during a first time interval. The method counts, in the node, at least one of the transmitted and received messages during the first time interval. The method determines, in the node, a channel occupancy during the first time interval, after counting the messages, and then adaptively adjusts, in the node, the contention interval based on the channel occupancy. 
     In another embodiment of the invention, a node, communicating on a channel in a network using CSMA protocol and accessing the channel by occupying at least one time slot in a contention interval, includes a transceiver for transmitting and receiving messages on the channel. The node also includes a counter, coupled to the transceiver, for counting the messages transmitted and received by the transceiver and providing output count values. The node further includes a controller, coupled to the counter, for (a) receiving the count values, (b) determining a channel occupancy based on the count values, and (c) adaptively adjusting the contention interval based on the channel occupancy. 
     It is understood that the foregoing general description and the following detailed description are exemplary, but are not restrictive, of the invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWING 
       The invention is best understood from the following detailed description when read in connection with the accompanying drawing. Included in the drawing are the following figures: 
         FIG. 1  is a flow diagram of a method for adaptively adjusting the length of a CI in a CSMA based communications system, in accordance with an embodiment of the present invention; 
         FIG. 2  is a flow diagram of another exemplary method for adaptively adjusting the length of a CI in a CSMA based communications system, in accordance with an embodiment of the present invention; 
         FIG. 3  is a block diagram of a node including a communications module for executing the methods illustrated in  FIGS. 1 and 2 , in accordance with an embodiment of the present invention; and 
         FIG. 4  is an overall block diagram showing multiple nodes communicating in a CSMA based communications system, in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention controls CAR in a CSMA based communications system by adaptively adjusting a length of a contention interval (CI). As will be explained, the invention monitors messages or packets in the channel, determines occupancy conditions of the channel, and adaptively adjusts the length of the CI based on the determined occupancy conditions. 
     Referring to  FIG. 1 , there is shown a method of adaptively adjusting the CI length, generally designated as  100 , in accordance with an embodiment of the invention. As will be explained, the probability of a node successfully transmitting a data packet is calculated and the CI length is adaptively adjusted accordingly. Method  100  starts at step  102  by setting an initial CI length in time slots, and in step  104  by resetting and initializing a timer. Method  100  then enters step  106  and counts messages or packets received and transmitted in the channel. The messages counted may include RTS and CTS packets occurring in the channel (also referred to as RTS and CTS events). A RTS packet may include a point-to-point RTS packet or a broadcast RTS packet. A CTS packet may include a singular CTS packet or a point-to-point CTS packet. 
     The count is performed over a predetermined interval of time. In step  108 , the method determines whether the time interval expired. If the time interval has not expired, the method continues the counting step, by branching back to step  106 . When the count interval expires, method  100  branches to step  110  and determines channel occupancy, or available channel space. As will also be explained, channel occupancy or available channel space is based on the counter values. The resulting channel occupancy or available channel space is then used to compute the probability of a node successfully transmitting a data packet. 
     The computed estimate is used as a basis for adaptively adjusting the CI length of the channel, as performed by step  112 . The CI length may be increased or decreased in step  112  by an integer number of time slots. After adjusting the CI length, the method loops back to step  104  and begins another counting cycle for computing a next CI length. 
     Referring next to  FIG. 2 , there is shown a detailed flow diagram of a method of adaptively adjusting the length of the CI in a CSMA channel, in accordance with an embodiment of the invention. The method, generally designated as  200 , begins at step  202  and sets S=S max , where S is a CI length in number of CSMA contention slots used by a communications node and S max  is a predetermined maximum CI length (for example S max  may be 12, 20, etc. time slots). The method then enters step  204  and sets a timer to expire after W time slots. The timer is initialized and various counters, as shown in step  206 , are each initialized to a value of zero (these counters are discussed below). 
     Step  208  is entered next to allow the method to count RTS reception and transmission events (steps  232 ,  234  and  236 ), as further discussed below. Step  208  is also entered to allow the method to count CTS reception and transmission events (steps  220 ,  222 ,  224 ,  226 ,  228  and  230 ), as further discussed below. Step  208  allows the method to concurrently count these events until the timer expires. When the timer expires after W time slots, the method exits step  208  and branches to step  210  for computing {circumflex over (P)} su , which is an estimate of a probability (denoted as P su (*)) of a local node successfully reserving channel space to transmit a data packet, as further discussed below. The estimate of {circumflex over (P)} su  may be computed once every interval of W time slots (a default value may be W=1000 time slots). 
     After the estimate of probability is computed, the method enters step  212  and compares the difference between the estimate of {circumflex over (P)} su  and a configurable performance level of P′ su  (for example 95%) with a delta value of {circumflex over (P)} ∂ . This delta value may also be configurable value and may include, for example, a default value of 1%. If the difference between the absolute value of {circumflex over (P)} su  and P′ su  is less than P ∂ , as determined by step  212 , the method loops back to step  204  without making any adjustment to the CI length. If the method in step  212 , on the other hand, determines that the difference is greater than or equal to P ∂ , the method branches to step  214 . 
     If step  214  determines that {circumflex over (P)} su  is smaller than P′ su , the method branches to step  216  and increases the length of CI by a value of S up . It will be appreciated that S up  may be a configurable value having a default value of 2 time slots. If step  214 , on the other hand, determines that {circumflex over (P)} su  is greater than or equal to P′ su , the method branches to step  218  and decreases the length of CI by a value of S down . It will be appreciated that S down  may be a configurable value having a default value of 1 time slot. 
     It will be further appreciated that the P′ su  value is a threshold value utilized by the invention to represent a channel access performance level that a user of a communications node desires to maintain. The adaptation rate of the node is determined by the protocol window size (W), the CI length increment (S up ), and the CI length decrement (S down ). In general, a faster adaptation rate may be achieved with a smaller protocol window size, and/or a larger CI length increment or decrement step. 
     In one embodiment, the protocol window size (W) is set larger than 1000 time slots, so that a sufficient number of samples may be collected for the computation of {circumflex over (P)} su . In other embodiments, the protocol window size (W), the CI length increment (S up ), and the CI length decrement (S down ) may be set to other values to achieve better system performance. 
     The computation of {circumflex over (P)} su  (any data packet) depends on a specific implementation of CSMA protocol used by the communications network. An exemplary method of computing {circumflex over (P)} su  (any data packet) will now be described and is based on nodes in a network operating using Small Unit Operation (SUO) radios, manufactured by ITT. The invention, however, is not limited to protocols used by the SUO radios. 
     First, let P BC  be the probability that any packet received by a media access controller (MAC) in a local node ( 304  in  FIG. 3 ), or one of the local node&#39;s neighbors, is a broadcast packet (i.e. local traffic profile). Then {circumflex over (P)} su  may be defined by the following equation:
 
 P   su (any data packet)= P   BC   ·P   su (broadcast packet)+(1 −P   BC )· P   su (pt-to-pt packet)  (1)
 
     Let P u  be the probability of a given CSMA time slot being used by the local node and/or at least one of the local node&#39;s neighbors, then
 
 P   su (broadcast packet)=1 −P   u   (2)
 
                       P   su     (     pt   ⁢     -     ⁢   to   ⁢     -     ⁢   pt   ⁢           ⁢   packet     )     =       (     1   -     P   u       )     ·       ∑     i   =   0       N   -   1       ⁢     P   u   i                 (   3   )               
where N is the maximum allowed number of tries for pt-to-pt (point-to-point) packet transmissions.
 
     When Eqs.(2) and (3) are substituted into Eq.(1), {circumflex over (P)} su  may be computed by the following equation: 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       su 
                     
                     ( 
                     
                       any 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       data 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       packet 
                     
                     ) 
                   
                   = 
                   
                     
                       
                         P 
                         BC 
                       
                       · 
                       
                         ( 
                         
                           1 
                           - 
                           
                             P 
                             u 
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             P 
                             BC 
                           
                         
                         ) 
                       
                       · 
                       
                         ( 
                         
                           1 
                           - 
                           
                             P 
                             u 
                           
                         
                         ) 
                       
                       · 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           P 
                           u 
                           i 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     Simplifying Eq.(4) yields 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       su 
                     
                     ( 
                     
                       any 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       data 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       packet 
                     
                     ) 
                   
                   = 
                   
                     
                       ( 
                       
                         1 
                         - 
                         
                           P 
                           u 
                         
                       
                       ) 
                     
                     · 
                     
                       ( 
                       
                         1 
                         + 
                         
                           
                             ( 
                             
                               1 
                               - 
                               
                                 P 
                                 BC 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               P 
                               u 
                               i 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     Let {circumflex over (P)} BC , and {circumflex over (P)} u  be the estimates of P BC , and P u , respectively. Eq.(5) may be rewritten as follows: 
     
       
         
           
             
               
                 
                   
                     
                       
                         P 
                         ^ 
                       
                       su 
                     
                     ( 
                     
                       any 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       data 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       packet 
                     
                     ) 
                   
                   ≅ 
                   
                     
                       ( 
                       
                         1 
                         - 
                         
                           
                             P 
                             ^ 
                           
                           u 
                         
                       
                       ) 
                     
                     · 
                     
                       ( 
                       
                         1 
                         + 
                         
                           
                             ( 
                             
                               1 
                               - 
                               
                                 
                                   P 
                                   ^ 
                                 
                                 BC 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 P 
                                 ^ 
                               
                               u 
                               i 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     {circumflex over (P)} BC  may be approximated by the follow equation: 
                       P   ^     BC     ≅       C   BRTS         C   BRTS     +     C   PTP_CTS                 (   7   )               
where C BRTS  and C PTP     —     CTS  are the total number of received/transmitted broadcast RTS (BRTS) and pt-to-pt CTS packets, respectively, during a W window size.
 
     Let C av , C PTP     —     RTS , and C singular     —     CTS  be the available space (in number of time slots) for CSMA contention, the total number of received/transmitted pt-to-pt RTS packets, and the total number of received singular CTS packets, respectively, during a W window size, then {circumflex over (P)} u  may be approximated by the following equation: 
                       P   ^     u     ≅     min   ⁡     (           C   BRTS     +     C   PTP_RTS     +     C   singular_CTS         C   av       ,   1     )               (   8   )               
It will be appreciated that the estimate for {circumflex over (P)} u  is limited to 100 percent (certainty) by the value of 1, shown in Eq. (8). It will also be appreciated that a singular CTS packet includes a CTS packet that is not preceded by a corresponding RTS packet.
 
     Let L BC  and L PTP  be the data message length (in number of time slots), indicated in the received/transmitted broadcast RTS and pt-to-pt CTS packets, respectively. 
     Let R BC  be a restricted back-off time interval (in number of time slots) for CSMA channel contention, when a broadcast RTS is received/transmitted. Also, let R PTP  and R PTP     —     RTS  be similar back-off time intervals for the reception/transmission of pt-to-pt CTS and pt-to-pt RTS packets, respectively. 
     In the exemplary embodiment, only one broadcast channel is used. The restricted back-off time interval for the broadcast channel may be computed, as shown in Eq (9), depending on whether an acknowledgement (ACK) is requested or not requested: 
     
       
         
           
             
               
                 
                   
                     R 
                     BC 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               L 
                               BC 
                             
                             + 
                             1 
                           
                         
                         
                           if 
                         
                         
                           
                             ACK 
                             BC 
                           
                         
                         
                           
                             
                               isn 
                               &#39; 
                             
                             ⁢ 
                             t 
                           
                         
                         
                           requested 
                         
                       
                       
                         
                           
                             
                               L 
                               BC 
                             
                             + 
                             2 
                           
                         
                         
                           if 
                         
                         
                           
                             ACK 
                             BC 
                           
                         
                         
                           is 
                         
                         
                           requested 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     In the exemplary embodiment, one or more data channels may be allocated for pt-to-pt message transmissions. As a result, the restricted back-off time interval for pt-to-pt message transmissions, namely R PTP , is equal to 0 if the channel reservation initiated by the received/transmitted pt-to-pt CTS packet does not exhaust all pt-to-pt channel resources, or may have the following value:
         2≦R PTP ≦L PTP +1, if the channel reservation exhausts all the pt-to-pt channel resources.       

     In other embodiments having only one data channel allocated for pt-to-pt message transmissions, or only one data channel allocated for both broadcast and pt-to-pt message transmissions, the restricted back-off time interval for pt-to-pt message transmissions may be computed as follows:
 
 R   PTP   =L   PTP +1  (10)
 
     In the exemplary embodiment, a CSMA time slot is reserved following the transmission/reception of a pt-to-pt RTS packet for a probable transmission of a responding pt-to-pt CTS packet. As a result, R PTP     —     RTS  may be specified as follows:
 
R PTP     —     RTS =1  (11)
 
     Referring flow again to  FIG. 2 , the method in step  206  initializes counters C av , C PTP     —     RTS , C singular     —     CTS , C BRTS  and C PTP     —     CTS  at the start of the timer interval, as follows:
 
 C   av   =W, C   BRTS =0 , C   PTP     —     CTS =0 , C   PTP     —     RTS =0, and  C   singular     —     CTS =0
 
     The method next waits for the W time interval to expire or for a RTS/CTS reception/transmission event to occur. If a CTS reception/transmission event occurs, the method branches to step  220  and determines whether the event includes a point-to-point packet or a broadcast packet. If it is a point-to-point CTS packet, the method branches to step  222 , increases C PTP     —     CTS  by one time slot and decreases C av  by R PTP  (the back-off time interval). These counters are modified as follows:
 
 C   PTP     —     CTS   =C   PTP     —     CTS +1
         C av =max(C av −R PTP ,1), where a minimum time slot may be 1.       

     The method then branches to step  224  to determine whether the pt-to-pt CTS packet is a singular CTS packet. If the pt-to-pt CTS packet is singular, the method branches to step  226  and increases C singular     —     CTS  by one, as follows:
 
 C   singular     —     CTS   =C   singluar     —     CTS +1
 
After increasing this counter by one time slot, the method loops back to step  208 .
 
     If step  220  determines that the packet is not a pt-to-pt CTS packet, on the other hand (i.e. it is a broadcast CTS packet), the method branches to step  228  to check whether the broadcast CTS packet is a singular CTS packet. If it is singular, the method branches to step  230  and decreases C av  by (R BC −1) time slots, wherein R BC  is the back-off time interval (in number of time slots) for CSMA channel contention when a broadcast RTS is received/transmitted. This expression may be written as follows:
 
 C   av =max( C   av   −R   BC +1,1)).
 
     The method next branches to step  226  and increases C singlar     —     CTS  by one time slot, as follows:
 
 C   singular     —     CTS   =C   singular     —     CTS +1
 
If the method determines, in either steps  224  or  228 , that the CTS packet is not singular, the method loops back to step  208 , as shown.
 
     Continuing the description of method  200 , if the reception/transmission event indicates a RTS packet, the method branches to step  232  and determines whether the RTS packet is a broadcast packet. If it is a broadcast packet, the method branches to step  234 , increases C BRTS  by one time slot and decreases C av  by R BC , the back-off time interval (in number of time slots). The counters are modified as follows:
 
 C   BRTS   =B   BRTS +1
 
 C   av =max( C   av   −R   BC ,1)
 
     If the RTS packet is not a broadcast packet, on the other hand (i.e. it is a pt-to-pt packet), the method branches to step  236 , increases C PTP     —     RTS  by one time slot and decreases C av  by R PTP     —     RIS , the back-off time interval (in number of time slots). The counters are modified as follows:
 
 C   PTP     —     RTS   =C   PTP     —     RTS +1
 
 C   av =max( C   av   −R   PTP     —     RTS ,1)
 
Method  200  then loops back to step  208  and either waits for the timer to expire or for another reception/transmission event to occur.
 
     After the timer expires, the method enters step  210  and computes {circumflex over (P)} BC , {circumflex over (P)} u  and {circumflex over (P)} su  (any data packet) using equations (6), (7) and (8), as Previously desired performance threshold value (steps  212  and  214 ), as previously described. Finally, the method loops back to step  204  and begins the process again by setting the timer and initializing the counters. 
     Referring next to  FIG. 3 , there is shown a block diagram of node  300  executing the methods illustrated in  FIGS. 1 and 2 , in accordance with an embodiment of the present invention. As shown, the node includes transceiver  301  for transmitting and receiving packets to/from other nodes or neighbors in the communications network, modem  302 , and communications module  312 . Module  312  includes media access controller (MAC)  304 , adaptive channel access protocol (ACAP) counters  306 , CI controller  308  and link layer module  310 . Although not shown, it will be appreciated that the link layer module provides a communications interface between the MAC and other higher level modules. For example, in an OSI (open system interconnect) environment, the MAC and the link layer module may control reception/transmission of packets received/transmitted between modem  302  and other upper layer modules (not shown) that provide application software for appliances or computers invoking different protocols. On the link layer side, these protocols may include a high level data link control (HDLC) protocol, a point to point protocol (PPP), or an application program interface (API) protocol. On the other MAC side, the protocol may include protocols such as carrier sense multiple access with collision detection (CSMA/CD) or carrier sense multiple access with collision avoidance (CSMA/CA). 
     For the embodiment shown in  FIG. 1 , ACAP counters  306  may provide counters for counting RTS/CTS packets or messages during a predetermined time interval. For the embodiment shown in  FIG. 2 , ACAP counters  306  may include C av , C PTP     —     RTS , C singular     —     CTS , C BRTS  and C PTP     —     CTS— , and may count during a W time interval, as described previously. In response to the counts of ACAP counters  306 , CI controller  308  adaptively adjusts the length of CI based on channel occupancy or computed probability functions, as described previously. MAC  304  may then use each newly adjusted CI length to adaptively control channel access in the CSMA communications network. 
     Referring to  FIG. 4 , there is shown an overall block diagram of multiple nodes communicating in a network. The network, generally designated as  400 , includes nodes  41 ,  42  and  43 , each including communications module  312 . The system includes at least one common communications channel  44  for transmitting and receiving message on the channel. 
     Although illustrated and described herein with reference to certain specific embodiments, the present invention is nevertheless not intended to be limited to the details shown. Rather, various modifications may be made in the details within the scope and range of equivalents of the claims and without departing from the spirit of the invention. For example, the present invention may adaptively adjust a CI of a channel in a CSMA/CA or CSMA/CD communications based network. It will be also be appreciated that the present invention may be implemented in both wireless and wired network systems.