Frequency assignment for multi-cell IEEE 802.11 wireless networks

Abstract

A frequency planning method for use in an IEEE 802.11 wireless network is described. The frequency planning method obtains traffic load information associated with access points belonging to a multi-cell wireless network and assigns channels to the access points based on the traffic load information.

What is claimed is:  
     
         1 . A method for frequency planning in wireless networks comprising: 
 obtaining traffic load information for access points belonging to a multi-cell wireless network; and    assigning channels to the access points based on the traffic load information.    
     
     
         2 . The method of  claim 1  wherein the step of assigning comprises: 
 determining, for each access point, at least one set of interferers from among the other access points relative to the access point.  
 
     
     
         3 . The method of  claim 2  wherein the step of determining comprises: 
 determining, for each of the other access points, if any co-channel interference by the other access point is greater than or equal to a detection threshold, the detection threshold indicative of a busy channel according to the CSMA protocol; and  
 if it is determined that the co-channel interference is greater than or equal to the detection threshold, identifying the other access point as belonging to the set of interferers for the access point.  
 
     
     
         4 . The method of  claim 3  wherein the co-channel interference is derived from values of signal path loss between the access point and the other access point and transmission power of the other access point.  
     
     
         5 . The method of  claim 3  wherein the at least one set of interferers comprises a second set of interferers, and wherein the step of determining comprises: 
 determining, for each pair of the other access points, if any combined co-channel interference by such pair is greater than or equal to a detection threshold, the detection threshold indicative of a busy channel according to the CSMA protocol; and  
 if it is determined that the combined co-channel interference is greater than or equal to the detection threshold, identifying the other access points in such pair as belonging to the second set of interferers for the access point.  
 
     
     
         6 . The method of  claim 2  wherein the step of assigning further comprises: 
 generating random channel assignments for the access points;  
 determining effective channel utilization values for each access point;  
 modifying the random channel assignment for interferers in the at least one set of interferers such that the highest one of the effective channel utilization values is minimized;  
 repeating such modification until the highest one of the effective channel utilization values cannot be reduced by further modification; and  
 saving the modified random channel assignment as a final assignment.  
 
     
     
         7 . The method of  claim 6  wherein the step of assigning further comprises: 
 providing the final assignment to the access points.  
 
     
     
         8 . The method of  claim 2  wherein the step of assigning further comprises: 
 assigning randomly a channel to each of the access points; and  
 computing, based on the random channel assignment, an effective channel utilization value for each access point, the effective channel utilization value representing the sum of an offered load associated with the access point and total traffic load associated with each set of interferers.  
 
     
     
         9 . The method of  claim 8  wherein the step of assigning further comprises: 
 determining which access point has the highest effective channel utilization value;  
 identifying which channel is assigned to the access point having the highest effective channel utilization value; and  
 for each access point in the first set of interferers, modifying the random channel assignment;  
 recomputing the effective channel utilization value for the modified random channel assignment; and  
 repeating modifying and recomputing for each available channel other than the channel assigned to the access point having the highest effective channel utilization value;  
 determining a minimum effective channel utilization from among the recomputed effective utilization values;  
 comparing the minimum effective channel utilization and the recomputed effective channel utilization values; and  
 replacing the highest effective channel utilization with the determined minimum effective channel utilization and saving the modified random channel assignment as a best solution if the determined minimum effective channel utilization is lower than the highest effective channel utilization.  
 
     
     
         10 . The method of  claim 9  wherein the step of assigning further comprises: 
 with a pre-specified probability, replacing the highest effective channel utilization with the determined minimum effective channel utilization and saving the modified random channel assignment as a best solution if the determined minimum effective channel utilization is equal to the highest effective channel utilization.  
 
     
     
         11 . The method of  claim 6  wherein the step of assigning further comprises: 
 computing an effective utilization value for each access point based on the final assignment; and  
 determining if the effective utilization value for each access point is less than a value of one.  
 
     
     
         12 . The method of  claim 1  wherein the channels comprise non-overlapping channels.  
     
     
         13 . The method of  claim 1  wherein the channels comprise overlapping and non-overlapping channels.  
     
     
         14 . The method of  claim 1  wherein the access points operate in accordance with the IEEE 802.11 standard.  
     
     
         15 . The method of  claim 1  wherein the step of assigning comprises: 
 seeking to minimize effective channel utilization of a most heavily loaded of the access points.  
 
     
     
         16 . The method of  claim 1  wherein the step of assigning comprises: 
 seeking to minimize total effective channel utilization of all access points.  
 
     
     
         17 . The method of  claim 1  wherein the step of assigning comprises: 
 seeking to maximize network throughput.  
 
     
     
         18 . An article comprising: 
 a storage medium having stored thereon instructions that when executed by a machine result in the following: 
 obtaining traffic load information for access points belonging to a multi-cell wireless network; and  
 assigning channels to the access points based on the traffic load information.  
   
     
     
         19 . An apparatus comprising: 
 a processor; and    a memory storing a computer program product residing on a computer-readable medium comprising instructions to cause a computer to: 
 obtain traffic load information for access points belonging to a multi-cell wireless network; and  
 assign channels to the access points based on the traffic load information.  
   
     
     
         20 . An access point for use in a multi-cell wireless network comprising: 
 logic configured to obtain traffic load information for access points belonging to the multi-cell wireless network; and    logic configured to assign channels to the access points based on the traffic load information.