Abstract:
A method for performing frequency selection escape in wireless communications is disclosed. The method includes receiving an activation trigger, determining whether the activation trigger has persisted for a predetermined period of time, determining a list of candidate channels; selecting a channel from the candidate list, and evaluating the selected channel against predetermined criteria, the predetermined criteria being related to the activation trigger. If the selected channel meets the predetermined criteria, then an access point (AP) is disassociated from all stations communicating with the AP; and the AP is changed to the selected channel. If the selected channel does not meet the predetermined criteria, then the selected channel is removed from the candidate list; and the selecting of a channel is repeated if there are additional candidate channels.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
   This application is a continuation of U.S. patent application Ser. No. 10/942,576, filed Sep. 16, 2004, which claims the benefit of U.S. Patent Application No. 60/535,429, filed Jan. 8, 2004, both of which are incorporated by reference as if fully set forth herein. 

   FIELD OF INVENTION 
   The present invention relates to wireless local area networks (WLANs) and, more particularly, to a method for alleviating congestion and interference levels in a WLAN by changing the channel currently in use. 
   BACKGROUND 
   A frequency selection algorithm is used to automatically select the most appropriate operating frequency for an access point (AP) in a WLAN. Frequency selection (FS) is typically composed of three distinct processes: initial FS, optimization FS, and escape FS. The initial FS process determines the best operating channel upon AP startup. The optimization FS process dynamically determines the optimal operating channel during system operation, without service disruption to associated wireless terminals (stations) in the basic service set (BSS). The process waits until there is no activity in the BSS for a certain period of time before changing the operating channel to a less loaded one. 
   The escape FS process is used to alleviate extreme congestion situations or intolerable interference levels. The escape FS process will only be invoked if the service degradation due to congestion or interference is worse than the harm resulting from service disruption to all associated stations, because all associated stations must first be disassociated from the AP prior to escaping to a different channel. The present invention relates to the escape FS process. 
   SUMMARY 
   A method for performing frequency selection escape in wireless communications is disclosed. The method includes receiving an activation trigger, determining whether the activation trigger has persisted for a predetermined period of time, determining a list of candidate channels; selecting a channel from the candidate list, and evaluating the selected channel against predetermined criteria, the predetermined criteria being related to the activation trigger. If the selected channel meets the predetermined criteria, then an access point (AP) is disassociated from all stations communicating with the AP; and the AP is changed to the selected channel. If the selected channel does not meet the predetermined criteria, then the selected channel is removed from the candidate list; and the selecting of a channel is repeated if there are additional candidate channels. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more detailed understanding of the invention may be had from the following description of a preferred embodiment, given by way of example, and to be understood in conjunction with the accompanying drawings wherein: 
       FIGS. 1A and 1B  show a flowchart of a method for an escape FS process in accordance with the present invention. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   The inputs and parameters used by an escape FS process in accordance with the present invention are listed in Table 1. 
   
     
       
             
           
             
             
             
             
           
         
             
               TABLE 1 
             
           
           
             
                 
             
             
               Inputs and parameters of the escape FS process 
             
           
        
         
             
                 
                 
                 
               Default 
             
             
               Symbol 
               Description 
               Type 
               Value 
             
             
                 
             
             
               ACS 
               Allowable channel set. 
               Configuration 
               {1, 6, 11} 
             
             
                 
                 
               parameter 
             
             
               op_chan 
               Index of the current operating 
               Internal 
               NA 
             
             
                 
               channel within the ACS. 
               parameter 
             
             
               T Last   
               The minimum elapsed time since the 
               Configuration 
               300 seconds 
             
             
                 
               last invocation of any of the FS 
               parameter 
             
             
                 
               algorithms for triggering escape FS. 
             
             
               BO MIN   
               The lower bound on the random 
               Configuration 
               10 seconds 
             
             
                 
               persistence timer for triggering 
               parameter 
             
             
                 
               escape FS. 
             
             
               BO MAX   
               The upper bound on the random 
               Configuration 
               100 seconds 
             
             
                 
               persistence timer for triggering 
               parameter 
             
             
                 
               escape FS. 
             
             
               DR MAX   
               Deferral Rate triggering threshold. 
               Configuration 
               30% 
             
             
                 
                 
               parameter 
             
             
               PER MAX   
               Transmitted packet error rate 
               Configuration 
               6% 
             
             
                 
               triggering threshold. 
               parameter 
             
             
               CU MAX   
               Out-of-BSS channel utilization 
               Configuration 
               40% 
             
             
                 
               triggering threshold. 
               parameter 
             
             
               DR 
               Deferral rate. This is a measurement 
               Measurement 
               NA 
             
             
                 
               that represents the percentage of time 
             
             
                 
               that the AP is carrier locked (i.e., is 
             
             
                 
               not receiving any packets) and has at 
             
             
                 
               least one packet to transmit. The DR 
             
             
                 
               measurement is calculated as the 
             
             
                 
               total amount of time that the AP 
             
             
                 
               deferred transmission over the last 
             
             
                 
               T MEAS  seconds, divided by T MEAS   
             
             
                 
               seconds. DR is calculated every T MEAS   
             
             
                 
               seconds. 
             
             
               PER 
               Transmitted Packet Error Rate. This 
               Measurement 
               NA 
             
             
                 
               measurement is a ratio of the number 
             
             
                 
               of transmission failures (i.e., 
             
             
                 
               transmitted packets for which an 
             
             
                 
               ACK is not received) to the total 
             
             
                 
               number of transmitted packets 
             
             
                 
               including retransmissions, calculated 
             
             
                 
               over T MEAS  seconds. PER is calculated 
             
             
                 
               every T MEAS  seconds. 
             
             
               C(k) 
               The average channel utilization of 
               Measurement 
               NA 
             
             
                 
               channel k. C(k) is a moving average 
             
             
                 
               of the latest channel utilization 
             
             
                 
               measurement on each channel. The 
             
             
                 
               channel utilization measurement 
             
             
                 
               corresponds to the percentage of time 
             
             
                 
               that the receiver is carrier locked. The 
             
             
                 
               channel utilization estimates can be 
             
             
                 
               obtained by intermittently listening 
             
             
                 
               to these frequency channels for short 
             
             
                 
               periods of time (referred to as Silent 
             
             
                 
               Measurement Periods (SMP)), so that 
             
             
                 
               normal communications associated 
             
             
                 
               with the AP are not substantially 
             
             
                 
               disrupted. C(k) consists of an average 
             
             
                 
               over N SMP  SMP measurements. 
             
             
               I[ ] 
               The set of external interference 
               Measurement 
               NA 
             
             
                 
               measurements recorded during a 
             
             
                 
               given measurement period of T MEAS . 
             
             
                 
               The external interference 
             
             
                 
               measurement consists of the received 
             
             
                 
               signal power in the absence of “carrier 
             
             
                 
               lock” by the receiver. All external 
             
             
                 
               interference measurements that are 
             
             
                 
               provided by the chipset are recorded 
             
             
                 
               during a given measurement period. 
             
             
               I SMP (k) 
               The average external interference 
               Measurement 
               NA 
             
             
                 
               level measured on the channel k. 
             
             
                 
               I SMP (k) is measured as the average 
             
             
                 
               received signal power in the absence 
             
             
                 
               of “carrier lock” by the receiver (i.e., 
             
             
                 
               the receiver is not receiving any 
             
             
                 
               packets). I SMP (k) consists of an 
             
             
                 
               average over N SMP  SMP 
             
             
                 
               measurements. 
             
             
               L 
               L represents the own-BSS load, 
               Measurement 
               NA 
             
             
                 
               observed over a measurement period 
             
             
                 
               of T MEAS  seconds. The own-BSS load 
             
             
                 
               consists of the sum of the medium 
             
             
                 
               usage time of successfully transmitted 
             
             
                 
               packets and successfully received 
             
             
                 
               packets from associated stations 
             
             
                 
               (own-BSS). L is calculated every 
             
             
                 
               T MEAS  seconds. 
             
             
               T MEAS   
               Measurement period over which DR 
               Configuration 
               1 second 
             
             
                 
               and PER measurements are 
               parameter 
             
             
                 
               calculated. 
             
             
               N SMP   
               Number of SMPs over which C(k) is 
               Configuration 
               5 
             
             
                 
               averaged. 
               parameter 
             
             
               RNG base   
               Baseline Range (set by the Path Loss 
               Internal 
               NA 
             
             
                 
               Discovery process). 
               parameter 
             
             
               RNG adj   
               Range Adjustment (set by the Load 
               Internal 
               NA 
             
             
                 
               Balancing process). 
               parameter 
             
             
               (C/I) req     —     high   
               Minimum required carrier power to 
               Configuration 
               10 dB 
             
             
                 
               interference ratio to support the 
               parameter 
             
             
                 
               planned data rate at the coverage 
             
             
                 
               bound. 
             
             
               P MAX   
               Maximum AP transmission power. 
               Configuration 
               20 dBm 
             
             
                 
                 
               parameter 
             
             
               I MAX   
               The maximum allowed interference 
               Internal 
               NA 
             
             
                 
               on any given channel determined 
               parameter 
             
             
                 
               based on baseline range. 
             
             
               M I   
               Interference margin used in the 
               Configuration 
               3 dB 
             
             
                 
               calculation of the maximum allowable 
               parameter 
             
             
                 
               interference level, I MAX.   
             
             
               M L   
               Load margin used in the interference 
               Configuration 
               1.0 
             
             
                 
               trigger of the algorithm. 
               parameter 
             
             
               Δ 
               The amount, in dB, by which the 
               Configuration 
               3 dB 
             
             
                 
               maximum allowed interference, I MAX,   
               parameter 
             
             
                 
               is increased if there are no candidate 
             
             
                 
               channels for which I &lt; I MAX . 
             
             
               H C   Esc   
               Hysteresis criterion for channel 
               Configuration 
               10% 
             
             
                 
               utilization. The difference between 
               parameter 
             
             
                 
               the channel utilization of the current 
             
             
                 
               channel and the new channel must 
             
             
                 
               exceed this threshold. 
             
             
               H I   Esc   
               Hysteresis criterion for measured 
               Configuration 
               3 dB 
             
             
                 
               interference level. The difference 
               parameter 
             
             
                 
               between the interference on the 
             
             
                 
               current channel and the new channel 
             
             
                 
               must exceed this threshold. 
             
             
               N RT     x     
               Number of retransmissions of the 
               Configuration 
               1 
             
             
                 
               Disassociate message to a particular 
               parameter 
             
             
                 
               station before abandoning. 
             
             
                 
             
           
        
       
     
   
   The transmit packet error rate, PER, is calculated over all medium access control (MAC) protocol data units (MPDUs) containing data, i.e., all fragments in the case of fragmentation, and all retransmissions. Moreover, a request to send (RTS) message for which a clear to send (CTS) message is not received should be included in the calculation of the transmitted packet error rate. In the event that zero packets were transmitted during the T MEAS  measurement period, the PER is set to zero. 
   Triggering (Start Stage) 
   The escape FS process is executed only during excessively high congestion situations or when interference is intolerable. Either one of the following triggering criteria, evaluated every T MEAS  seconds, must be satisfied to invoke the escape FS process. 
   The first triggering criterion is a channel congestion criterion, in which the following three conditions are satisfied: 
   1) C(op_chan)&gt;CU MAX ; 
   2) DR&gt;DR MAX ; and 
   3) PER&gt;PER MAX . 
   The out-off-BSS channel utilization measurement, the AP deferral rate, and the transmitted packet error rate must exceed their respective triggering thresholds. It is noted that the out-of-BSS channel utilization measurements can be obtained by intermittently listening to the different frequency channels for short periods of time, i.e., Silent Measurement Periods (SMP), so that normal communications associated with the AP are not substantially disrupted. 
   These three metrics were carefully chosen to ensure that the escape FS algorithm only triggers when a change of channel is required and beneficial. First, the out-of-BSS channel utilization metric is used to ensure that the channel congestion is caused, at least in part, by out-of-BSS WLAN traffic. If the congestion were caused only by in-BSS traffic, a change of channel would not alleviate the congestion situation because all of the traffic would be moved to the new channel. Second, the deferral rate measurement is considered to ensure that the AP effectively perceives the congestion; a high deferral rate indicates that the AP has a significant amount of data to transmit and is experiencing significant delays for channel access. Third, the packet error rate must exceed its triggering threshold. 
   The second triggering criterion corresponds to an intolerable interference level. Many external interference sources, such as a microwave oven, exhibit intermittent interference patterns. As a result, the effect of the interference source depends on the proportion of time that the intolerable interference persists, as well as the traffic load of the AP. 
   Let PI represent the proportion of time that the external interference level is intolerable over a given measurement period: 
   
     
       
         
           
             
               
                 PI 
                 = 
                 
                   
                     Size 
                     ⁡ 
                     
                       ( 
                       
                         
                           I 
                           [ 
                           ] 
                         
                         &gt; 
                         
                           I 
                           MAX 
                         
                       
                       ) 
                     
                   
                   
                     Size 
                     ⁡ 
                     
                       ( 
                       
                         I 
                         [ 
                         ] 
                       
                       ) 
                     
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
   
   where the determination of I MAX  is described later. 
   The following triggering criterion is defined:
 
(1 −CU ( op   —   chan ))×(1 −PI )≦( L×M   L )  Equation (2)
 
   The left-hand side of Equation (2), (1−CU(op_chan))×(1−PI), effectively represents the “good bandwidth” that is available for own-BSS transmission, whereas the right-hand side represents the BSS load. The escape FS algorithm will only trigger if the intolerable interference occupies so much bandwidth that there is not enough interference-free bandwidth for the AP to serve its load. 
   Along with the triggering criteria described above, at least T Last  seconds must have elapsed since the last execution of either initial FS, optimization FS, or escape FS; otherwise, the triggering condition is ignored. The value of T Last  is the same as for the optimization FS algorithm. Once T Last  has expired since a channel change, the two triggering conditions are evaluated periodically over T MEAS . 
   Moreover, the triggering criteria must persist for at least T Trigger  seconds in order to allow a frequency change. The duration of the required persistence time, T Trigger , is generated as a random variable that is uniformly distributed between BO MIN  and BO MAX , in discrete steps of T MEAS . The use of a random timer results in a back-off procedure, which ensures that two competing BSSs on the same channel do not escape at the same time. 
   Both triggering criteria, along with BO MIN , should be carefully set to avoid premature channel changes. The escape FS process is considered as a last resort, because all associated stations must first be disassociated prior to changing the channel, resulting in an interruption of service. The channel should only be changed if the current external loading and/or external interference are unsupportable, in which case it is worth interrupting service to all stations. Finally, BO MAX  should be set high enough to yield a small probability of having multiple APs simultaneously escaping, and low enough to ensure a quick response by the escape FS process. 
   A flowchart of the escape FS process  100  is illustrated in  FIGS. 1A and 1B . The escape FS process  100  can be performed by an AP. The components of the AP performing the escape FS process  100  can be an integrated circuit (IC), such as an application specific IC (ASIC), multiple ICs, discrete components, or a combination of discrete components and IC(s). Upon triggering the escape FS process, a set of candidate channels is first determined, followed by channel selection and channel update (if required). 
   Determining Candidate Channels 
   The set of candidate channels does not consist of the all channels in the allowable channel set (ACS). Only channels for which the interference measurement, I, lies below the maximum allowed interference level, I MAX , are considered; those with interference levels above I MAX  are ignored. The escape FS process  100  begins by retrieving data from power control and then calculating the value I MAX  (step  102 ). The initial maximum allowed interference level is calculated as:
 
 I   MAX   =P   MAX −( RNG   base   +RNG   adj )−( C/I ) req     —     high   −M   I   Equation (3)
 
where (RNG base +RNG adj ) represents the range covered by the AP and (C/I) req     —     high  is set to the required carrier power to interference ratio of a packet at the planned rate at BSS range (i.e., 5.5 or 11 Mbps). A margin, M I , is subtracted to eliminate channels with interference levels too close to the actual maximum allowed level.
 
   The current channel is removed from the ACS (step  104 ), because the process is looking to escape from the current channel. The first channel from the ACS is selected (step  106 ). The interference measured on the selected channel is compared to the maximum allowed interference (step  108 ). If the interference on the current channel is less than the maximum interference, then the current channel is recorded in the candidate channel list (step  110 ). 
   If the interference on the current channel exceeds the maximum interference (step  108 ) or if the channel is recorded in the candidate list (step  110 ), a determination is then made whether there are more channels in the ACS (step  112 ). If there are more channels in the ACS, then the next channel is selected (step  114 ) and is evaluated at step  108  as described above. 
   If there are no more channels in the ACS (step  112 ), a determination is made whether there are any channels in the candidate list (step  116 ). If there are no channels in the candidate list, i.e., I(k)&gt;I MAX  for all k, then the value of I MAX  is increased by a predetermined amount (Δ dB; step  118 ), and a new list of candidate channels is generated by re-running the process starting at step  106 . The process is continued until a candidate list containing at least one channel is found. Δ should be set such that all channels with similar interference levels are considered as candidates; any value for Δ greater than zero is acceptable. 
   If there are channels in the candidate list (step  116 ), then the process continues with the channel selection and channel update stages. 
   Channel Selection and Channel Update 
   From the candidate list, the channel with the lowest average channel utilization C(k) is selected (step  120 ). Channel selection amongst candidate channels is primarily based on recent channel utilization measurements. The channel utilization of channel k, C(k), is an average of the latest channel utilization measurements on each channel. Channel utilization measurements are performed during the silent measurement periods (SMPs) and correspond to the percentage of time that the receiver is carrier locked. Since channel utilization is observed during SMPs, all packets that cause the AP to carrier lock originate from neighboring BSSs. The channel utilization measurement represents the out-of-BSS channel usage. 
   A decision is made to determine which of the trigger criteria was met to activate the process  100  (step  122 ). If the trigger was (1; channel congestion), then a determination is made whether the channel utilization of the selected channel is lower than the channel utilization of the current channel by a predetermined amount (step  124 ). Based on the triggering criterion, a hysteresis criterion is verified. For trigger (1), the hysteresis criterion is defined as:
 
 C ( op   —   chan )− C (new_channel)&gt; H   C   Esc   Equation (4)
 
   The channel utilization of the new channel must be lower than the channel utilization of the current channel by at least H C   Esc %. If this condition is met, then the BSS channel is updated with the new channel. All of the stations associated with the AP are disassociated (step  126 ). The AP first sends a Disassociation message to each associated station, and then change its frequency to the new frequency. In the case where a Disassociation message is sent to a station and no ACK is received, the AP will retransmit the message up to N RTx  times before abandoning the disassociation of this particular station. It is noted that the likelihood of transmission failure of a Disassociation message should be high given the severity of conditions under which the escape FS process is triggered. 
   The AP changes to the new channel (step  128 ), and the process terminates (step  130 ). The disassociated stations will then reassociate with the AP, per known procedures. 
   If the channel utilization of the selected channel is not lower than the channel utilization of the current channel by a predetermined amount (step  124 ), then the selected channel is removed from the list of candidate channels (step  132 ). Next, a determination is made whether there are any more channels in the candidate list (step  134 ). If there are more candidate channels, then the process continues with step  120  as described above. If there are no more candidate channels (step  134 ), then no change of channel is made (step  136 ) and the process terminates (step  130 ). This process continues until a candidate channel that satisfies the hysteresis criterion is found or there are no remaining candidate channels. 
   If the escape FS algorithm  100  was activated by trigger (2; intolerable interference) (step  122 ), then a determination is made whether the interference on the selected channel is lower than the interference on the current channel by a predetermined amount (step  138 ). For trigger (2), the hysteresis criterion is defined as:
 
 I ( op   —   chan )− I (new_channel)&gt; H   I   Esc   Equation (5)
 
   The interference level of the new channel must be lower than the interference level of the current channel by at least H I   Esc  dB. The hysteresis criterion is used to ensure that change of channel will be beneficial enough to justify the service interruption to associated stations. 
   If this condition is met, then the process  100  continues with step  126 , as described above. If this condition is not met, then the process  100  continues with step  132 , as described above. 
   The following features need to be supported by the AP in order to perform the escape FS process  100 : 
   1) Transmitted packet error rate measurement with configurable averaging window size. Alternatively, the AP can provide an indication for each successful and failed packet transmission. 
   2) Received packet error rate measurement with configuration averaging window size. Alternatively, the AP can provide an indication for each successful and failed packet reception. 
   3) The Deferral Rate measurement, which corresponds to the percentage of time that the AP is carrier locked by an out-of-BSS packet and has at least one packet to transmit. 
   4) Channel utilization during a silent measurement period, which corresponds to the percentage of time that the receiver is carrier locked. 
   5) External interference measurement, which corresponds to the average received signal power in the absence of carrier lock by the receiver. 
   6) Number of retransmissions of a particular packet. 
   7) Dynamic setting/update of the operating channel. 
   In other embodiments, additional modifications could be made to the present invention to better alleviate congestion and high interference levels in the WLAN. For example, the AP can inform stations of a change of operating frequency to eliminate the need for disassociating them. The optimization FS process can thus run periodically, without any concern for activity on the channel, eliminating the need for a separate escape FS process. Another modification would be to employ a centralized scheme, where channel assignment is determined on a network basis rather than independently for each BSS, which improves overall system performance. Furthermore, inter-AP communication would allow APs to share load information and notification of a change in frequency. In some WLAN settings, such as a MESA setting, the WLAN does not support inter-AP communication. 
   Although the features and elements of the present invention are described in the preferred embodiments in particular combinations, each feature or element can be used alone (without the other features and elements of the preferred embodiments) or in various combinations with or without other features and elements of the present invention. While specific embodiments of the present invention have been shown and described, many modifications and variations could be made by one skilled in the art without departing from the scope of the invention. The above description serves to illustrate and not limit the particular invention in any way.