Frequency assignment in wireless networks

• US 6,023,459 A
• Filed: 12/04/1996
• Issued: 02/08/2000
• Est. Priority Date: 12/04/1996
• Status: Expired due to Term

• Current Assignee: Lenovo Innovation Company Limited Hong Kong (Lenovo Group Ltd.)
• Original Assignee: Northern Telecom Limited (Nortel Networks Corporation)
• Inventors: Smith, George David, Clark, Timothy Ian James
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US08/760,381
• Time in Patent Office: 1,161 Days
• Field of Search: 370/319, 370/321, 370/327, 370/329, 370/330, 370/337, 370/341, 370/344, 455/450, 455/452, 455/453, 455/464, 455/509, 455/513, 455/447, 455/449, 455/62, 455/63, 701/117, 701/20
• US Class Current: 370/329
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 28/16 Central resource management; Negotiation of resources or communication parameters, e.g. negotiating bandwidth or QoS [Quality of Service]

Abstract

The disclosure relates to wireless networks, and particularly a method and apparatus for assigning carrier frequencies to base station antenna sites.

Base stations are represented as a matrix of interconnected nodes and links, the nodes representing carrier frequency sites and the links being dimensioned in accordance with disallowed frequency slots. A first algorithm is used to assign carrier frequencies to the carrier frequency sites in a non-interfering manner resulting in a partial frequency assignment plan. A second algorithm assigns carrier frequencies to the remaining vacant carrier sites in a manner which seeks to minimise the amount of interference. The order in which the carrier sites are assigned carrier frequencies is determined by either a random ordering, an order generated by simulated annealing, or an ordering generated by a genetic algorithm. A quality measure is generated from the resultant frequency plan and is used to modify the order in which the frequencies are assigned to carrier site nodes in subsequent iterations.

Claims

1. A method for assigning a set of communications frequencies to a plurality of network elements, each operating at least one frequency, the method comprising the steps of:

representing each said network element as a corresponding respective set of at least one frequency site node;

linking said plurality of frequency site nodes together by a plurality of dimensioned links, each said dimensioned link representing a constraint on the assignment of a communications frequency to at least one said node;

determining at least one order in which to assign said plurality of communications frequencies to said plurality of nodes;

for each node of the plurality, where possible assigning a frequency which does not interfere with frequencies assigned to other said nodes; and

for each node for which a non interfering frequency cannot be assigned, assigning to said node a frequency which causes a minimum interference with frequencies assigned to other said nodes,

wherein during said step of assigning a non-interfering frequency said nodes are selected in a first order and said frequencies are assigned to said nodes taken in said first order, and during said step of assigning a minimally interfering frequency, said nodes are selected in a second order and said frequencies are assigned to said nodes taken in said second order.

2. The method as claimed in claim 1, wherein said step of assigning a frequency which does not interfere with frequencies assigned to other nodes comprises;

assigning said frequency according to a first assignment algorithm which assigns said frequencies to as many nodes as possible without co-site first order inter cell, or second order inter cell interference.

3. The method as claimed in claim 1, wherein said step of assigning a frequency which does not interfere with frequencies assigned to other nodes comprises;

assigning said frequencies according to first assignment algorithm which assigns frequencies in layers, in which an attempt is made to assign a single frequency to every cell in a network before an attempt is made to assign an additional frequency to any single cell.

4. The method as claimed in claim 1, further comprising the step of:

producing a quality measure representing a quality of said substantially interference-free assignment, said quality measure comprising a number of vacant nodes to which a carrier frequency remains unassigned in a partial frequency plan produced at an end of said step of assigning a frequency which does not interfere with frequencies assigned to other nodes.

5. The method as claimed in claim 1, wherein said step of assigning frequencies in a minimally interfering way comprises;

selecting a node according to said second order;

selecting a frequency which is minimally interfering with frequencies assigned to other nodes linked in said selected node; and

assigning said selected minimally interfering frequency to said node selected according to said second order.

6. The method as claimed in claim 1, further comprising the step of;

evaluating a result of said assignment of a minimally interfering frequency to said selected node; and

producing a quality measure determined from a level of interference produced by said assignment of said minimally interfering frequency.

7. A method according to claim 1, wherein a said step of assigning comprises:

maintaining a table of node data and frequency data in which each said node has listed a corresponding set of available frequencies and a corresponding set of linked nodes;

selecting a node in accordance with said order;

revising said table on assignment of a said frequency to a selected node by deleting said assigned frequency from said set of available frequencies corresponding to said selected node; and

deleting said assigned frequency from said sets of available frequencies corresponding to other nodes of the plurality each of which are linked to the selected node.

8. The method as claimed in claim 1, wherein said step of determining an order comprises modifying said order in response to a quality measure determined as a result of said assignment of frequencies.

9. A method for assigning a plurality of communications frequencies to a communications network comprising a plurality of network elements, the method comprising of steps of;

representing said communications network as a matrix of a plurality of node data and a plurality of dimensioned link data in which each said network element is represented by a corresponding respective set of said node data, and said dimensioned link data represents a set of constraints on the assignment of communications frequencies to said plurality of node data;

representing said set of communications frequencies as a set of frequency data;

determining an order data representing a first and a second order in which to assign said set of frequencies to said nodes;

assigning said frequency data representing said set of frequencies to said node data representing said nodes in said first order, in an interference free manner across said whole matrix until no more interference free assignments can be made;

assigning said frequency data to said node data representing any remaining vacant nodes according to said second order, in a way which causes minimum interference; and

generating a quality measure data of said assignment of frequencies to nodes, wherein said step of determining an order data representing a first and second order comprises modifying said order data according to said generated quality measure data of said assignment of frequencies to said nodes.

10. The method as claimed in claim 9, wherein said step of determining an order data representing an order comprises applying a simulated annealing algorithm to generate an order of node data.

11. The method as claimed in claim 9, wherein said step of determining an order data comprises generating an order of node data by a genetic algorithm.

12. The method as described in claim 9, wherein said step of determining an order data comprises generating a random order of node data.

13. A data processing apparatus for processing data describing a plurality of communications frequencies and data describing a plurality of network elements comprising a communications network, the apparatus comprising a processor and a memory configured into the following elements:

an interference matrix data generating means for generating an interference matrix data in which each said network element is represented by a corresponding respective plurality of nodes each representing a frequency site, said nodes being linked by a plurality of links, each said ink representing a dimensioned constraint on an assignment of at least one frequency to at least one said node;

an order data generating means for generating an order data specifying a first order and a second order in which to select said nodes for assignment of said frequencies;

a frequency assignment data generating means for generating a frequency assignment plan data specifying an assignment of frequencies to said nodes; and

an evaluation data generating means for evaluating said assignment plan data and producing an evaluation data describing a quality of said assignment plan data, wherein

said order data generating means operates to receive said evaluation data and create a new order data selection of said nodes, in response to said evaluation data;

wherein said frequency assignment data generating means generates a new assignment plan data in response to said new order data, by assigning said nodes to said nodes in a manner in which each frequency assigned does not interfere with frequencies assigned to other said nodes, said first assignment selecting said nodes in a first said order, and in a second assignment, assigning said frequencies to each node for which a non-interfering frequency cannot be assigned, in a manner which causes a minimum interference with existing frequencies assigned to other said nodes, and in said second assignment selecting said nodes according to said second order.

14. The apparatus as claimed in claim 13, wherein said new order data comprises a modification of said order data.

15. An apparatus for assigning a plurality of frequencies to a plurality of network elements comprising a communications network, said apparatus comprising:

an interference matrix generation means for generating an interference matrix in which each said network element is represented by a corresponding respective plurality of nodes, each said node representing a carrier site, said nodes being linked by a plurality of links, each said link representing a dimensioned constraint on an assignment of at least one frequency to at least one said node;

an ordering means for determining a first order and a second order in which to assign said frequencies to said network elements;

an assignment means for assigning said plurality of frequencies to said plurality of network elements in an order specified by said ordering means;

an evaluation means for evaluating a result of said assignment of frequencies and for generating an evaluation data signal in accordance with said result, wherein

in said step of assignment, said assignment means operates to assign frequencies to said set of nodes in a manner in which each frequency assigned does not interfere with frequencies assigned to other said nodes, said first assignment made to said nodes selected according to a first said order, and for each remaining node for which a non-interfering frequency cannot be assigned, making a second assignment in which a said frequency is selected which causes a minimum interference with frequencies assigned to other said nodes, said second assignment of frequencies carried out selecting said nodes according to a second said order.

16. A machine readable medium containing control signals for causing a data processing apparatus to function as an apparatus for assigning a plurality of frequencies to a plurality of nodes representing network elements comprising a communications network, said control signals configuring said data processing apparat us into the following elements:

an interference matrix generation engine for generating an interference matrix data in which each said network element is represented by a corresponding respective plurality of nodes each representing a frequency site, said nodes being linked by a plurality of links, each said link representing a dimensioned constraint on an assignment of at least one frequency to at least one said node;

an order generating engine for generating an order data specifying a plurality of orderings in which to select said nodes for assignment of said frequencies;

a frequency assignment engine for assigning frequency data describing an assignment of said frequencies to said nodes; and

an evaluation engine for evaluating a result of said assignment of frequencies to nodes, and for producing a quality data in response to said evaluation, wherein

in said step of assignment, said assignment means operates to assign frequencies to said set of nodes in a manner in which each frequency assigned does not interfere with frequencies assigned to other said nodes, said first assignment made to said nodes selected according to a first order, and for each remaining node for which a non-interfering frequency cannot be assigned, making a second assignment in which a said frequency is selected which causes a minimum interference with frequencies assigned to other said nodes, said second assignment of frequencies carried out by selecting said nodes according to a second order.

17. The method as claimed in claim 16, wherein each said dimensioned link represents a frequency slot spacing between at least a pair of carrier frequencies.