Method and techniques for penalty-based channel assignments in a cellular network

Abstract

A cellular network configuration tool is described that performs frequency assignments for use in a cellular network. The channels are assigned in accordance with input configuration data such as a channel separation matrix, geographic data, and requested channel assignments for each sector included in the cellular network being configured. The configuration is performed in accordance with predetermined constraints and criteria and quality of service input. The tool uses frequency assignment techniques to perform the channel assignments in accordance with varying constraints and criteria. A penalty function is used to determine a figure of merit for a particular set of frequency assignments.

1. A method executed in a computer system for determining a channel assignment comprising:
 performing an initial channel assignment, said initial channel assignment including associating one or more channels with each sector included in a cellular network;  
 calculating a penalty value representing a quantification of cost associated with said channel assignment if said initial channel assignment does not satisfy predetermined constraints; and  
 modifying said initial channel assignment in accordance with said penalty function if said initial channel assignment does not satisfy predetermined constraints.  
 
     
     
       2. The method of  claim 1 , further including:
 determining if a maximum number of predetermined iterations is exceeded.  
 
     
     
       3. The method of  claim 2 , further including:
 determining if said initial channel assignment satisfies predetermined constraints; and  
 accepting said initial channel assignment as said final channel assignment if said predetermined constraints are satisfied.  
 
     
     
       4. The method of  claim 3 , wherein said predetermined constraints include channel separation information indicating a minimum channel separation requirement between pairs of sectors. 
     
     
       5. The method of  claim 4 , further including modifying said channel separation information in accordance with additional predetermined constraints including carrier to interference values representing strength of a signal transmitted at a frequency if first and second sectors included in a cellular network are both assigned the same frequency, said carrier to interference values considering the strength of the signal from the first sector operating at a first channel in conjunction with interference generated by the second sector also operating at the first channel. 
     
     
       6. The method of  claim 1 , wherein said modifying said initial channel includes:
 performing penalty-based adjustment for each frequency associated with each sector in said initial channel assignment tagged for readjustment.  
 
     
     
       7. The method of  claim 6 , further including making one or more iterative adjustment to said each frequency in accordance with penalty costs. 
     
     
       8. A method executed in a computer system for determining a total penalty value for use in performing channel assignments in a cellular network the method comprising:
 determining a penalty function for each pair of sectors, i and j, included in said cellular network, sector i being associated with a frequency k, denoted f ik , and sector j being associated with a frequency l, denoted f ji , said penalty function being represented as: 
             P     k   ⁢           ⁢   l       i   ⁢           ⁢   j       =       (     1   -       S     i   ⁢           ⁢   j           f     i   ⁢           ⁢   k       -     f     j   ⁢           ⁢   l             )       2   ⁢   n         )       2   ⁢   m         
 
 
       where n and m, are integers greater than or equal to 1, and Sij denotes a constraint for sectors i and j representing a required channel separation;
 determining a potential representing a summation of the penalty function between two sectors i and j represented as: 
         V     i   ⁢           ⁢   j       =       ∑     k   =   1       d   i       ⁢           ⁢       ∑     l   =   1       d   i       ⁢           ⁢     P     k   ⁢           ⁢   l       i   ⁢           ⁢   j               
 
 
       and
 determining a total penalty value, V, for all sectors and channels included in said cellular network represented as: 
       V   =       ∑   i   N     ⁢           ⁢       ∑   p   N     ⁢           ⁢       V     i   ⁢           ⁢   j       .             
 
 
     
     
       9. The method of  claim 8 , wherein a single value is used for “n”. 
     
     
       10. The method of  claim 9 , wherein said S ij  represents a maximum separation constrain for said sectors “i” and “j” of all channel separation constraints specified for sectors “i” and “j”. 
     
     
       11. The method of  claim 8 , wherein a different value for “n” is used for each sectors “i” and “j”. 
     
     
       12. A method executed in a computer system for determining color codes comprising:
 selecting a channel for use in a cellular network;  
 identifying one or more sectors included in said cellular network and being associated with said channel;  
 using a channel assignment technique to perform color code assignments to said sectors using said channel, wherein said channel assignment technique uses a penalty function in evaluating said color code assignments.  
 
     
     
       13. The method of  claim 12 , further including:
 determining a subset of an original constraint matrix and using said subset to determine a final color code assignment to said sectors using said channel, said original constraint matrix representing color code separation constraints.  
 
     
     
       14. The method of  claim 13 , further including:
 modifying a portion of said original constraint matrix by replacing each entry representing that two sectors may be assigned the same frequency with an updated entry indicating that two sectors may not use the same color code.  
 
     
     
       15. The method of  claim 14 , wherein said each entry representing that two sectors may be assigned the same frequency is indicated by an entry value of zero, and said updated entry indicating that said two sectors may not use the same color code is indicated by a non-zero value. 
     
     
       16. A method executed in a computer system for determining a channel assignment comprising:
 performing an initial channel assignment, said channel assignment including associating one or more channels with each sector included in a cellular network;  
 calculating a penalty function representing a quantification of cost associated with said channel assignment if said channel assignment does not satisfy predetermined constraints, said predetermined constraints including channel separation information;  
 modifying said initial channel assignment in accordance with said penalty function if said initial channel assignment does not satisfy predetermined constraints; and  
 modifying said channel separation information in accordance with additional predetermined constraints including carrier to interference values representing strength of a signal transmitted at a frequency if first and second sectors included in a cellular network are both assigned the same frequency, said carrier to interference values considering the strength of the signal from the first sector at a first channel in conjunction with interference generated by the second sector also operating at the first channel.  
 
     
     
       17. An apparatus for determining a channel assignment comprising:
 machine executable code for performing an initial channel assignment, said initial channel assignment including associating one or more channels with each sector included in a cellular network;  
 machine executable code for calculating a penalty value representing a quantification of cost associated with said channel assignment if said initial channel assignment does not satisfy predetermined constraints; and  
 machine executable code for modifying said initial channel assignment in accordance with said penalty function if said initial channel assignment does not satisfy predetermined constraints.  
 
     
     
       18. The apparatus of  claim 17 , further including:
 machine executable code determining if a maximum number of predetermined iterations is exceeded.  
 
     
     
       19. The apparatus of  claim 18 , further including:
 machine executable code for determining if said initial channel assignment satisfies predetermined constraints; and  
 machine executable code for accepting said initial channel assignment as said final channel assignment if said predetermined constraints are satisfied.  
 
     
     
       20. The apparatus of  claim 19 , wherein said predetermined constraints include channel separation information indicating a minimum channel separation requirement between pairs of sectors. 
     
     
       21. The apparatus of  claim 20  further including machine executable code for modifying said channel separation information in accordance with additional predetermined constraints including carrier to interference values representing strength of a signal transmitted at a frequency if first and second sectors included in a cellular network are both assigned the same frequency, said carrier to interference values considering the strength of the signal from the first sector operating at a first channel in conjunction with interference generated by the second sector also operating at the first channel. 
     
     
       22. The apparatus of  claim 17 , wherein said modifying said initial channel includes:
 performing penalty-based adjustment for each frequency associated with each sector in said initial channel assignment tagged for readjustment.  
 
     
     
       23. The apparatus of  claim 22 , further including machine executable code for making one or more iterative adjustment to said each frequency in accordance with penalty costs. 
     
     
       24. An apparatus for determining a total penalty value for use in performing channel assignments in a cellular network, the apparatus comprising:
 machine executable code for determining a penalty function for each pair of sectors, i and j, included in said cellular network, sector i being associated with a frequency k, denoted f ik , and sector j being associated with a frequency l, denoted fjl, said penalty function being represented as: 
             P     k   ⁢           ⁢   l       i   ⁢           ⁢   j       =       (     1   -       S     i   ⁢           ⁢   j           f     i   ⁢           ⁢   k       -     f     j   ⁢           ⁢   l             )       2   ⁢   n         )       2   ⁢   m         
 
 
       where n and m are integers greater than or equal to 1, and S ij  denotes a constraint for sectors i and j representing a required channel separation;
 machine executable code for determining a potential representing a summation of the penalty function between two sectors i and j represented as: 
         V     i   ⁢           ⁢   j       =       ∑     k   =   1       d   1       ⁢           ⁢       ∑     l   =   1       d   1       ⁢           ⁢     P     k   ⁢           ⁢   l       i   ⁢           ⁢   j               
 
 
       and
 machine executable code for determining a total penalty value, V, for all sectors and channels included in said cellular network represented as: 
       V   =       ∑   i   N     ⁢           ⁢       ∑   p   N     ⁢           ⁢       V     i   ⁢           ⁢   j       .             
 
 
     
     
       25. The apparatus of  claim 24 , wherein a single value is used for “n”. 
     
     
       26. The apparatus of  claim 25 , wherein said S ij  represents a maximum separation constraint for said sectors “i” and “j” of all channel separation constraints specified for sectors “i” and “j”. 
     
     
       27. The apparatus of  claim 24 , wherein a different value for “n” is used for each pair of sectors “i” and “j”. 
     
     
       28. An apparatus for determining color codes comprising:
 means for selecting a channel for use in a cellular network;  
 means for identifying one or more sectors included in said cellular network and being associated with said channel;  
 means for using a channel assignment technique to perform color code assignments to said sectors using said channel, wherein said channel assignment technique uses a penalty function in evaluating said color code assignments.  
 
     
     
       29. The apparatus of  claim 28 , further including:
 means for determining a subset of an original constraint matrix and using said subset to determine a final color code assignment to said sectors using said channel, said original constraint matrix representing color code separation constraints.  
 
     
     
       30. The apparatus of  claim 29 , further including:
 means for modifying a portion of said original constraint matrix by replacing each entry representing that two sectors may be assigned the same frequency with an updated entry indicating that said two sectors may not use the same color code.  
 
     
     
       31. The apparatus of  claim 30 , wherein said each entry representing that two sectors may be assigned the same frequency is indicated by in entry value of zero, and said updated entry indicating that said two sectors may not use the same color code is indicated by a non-zero value. 
     
     
       32. An apparatus for determining a channel assignment comprising:
 a computer program product for performing an initial channel assignment, said channel assignment including associating one or more channels with each sector included in a cellular network;  
 a computer program product for calculating a penalty function representing a quantification of cost associated with said channel assignment if said channel assignment does not satisfy predetermined constraints, said predetermined constraints including channel separation information;  
 a computer program product for modifying said initial channel assignment in accordance with said penalty function if said initial channel assignment does not satisfy predetermined constraints; and  
 a computer program product for modifying said channel separation information in accordance with additional predetermined constraints including carrier to interference values representing strength of a sign transmitted at a frequency if first and second sectors included in a cellular network are both assigned the same frequency, said carrier to interference values considering the strength of the signal from the first sector at a first channel in conjunction with interference generated by the second sector also operating at the first channel.