Apparatus and method for non-regular channel assignment in wireless communication networks
First Claim
1. In a wireless communications system having service areas partitioned into a plurality of substantially contiguous cells, a method of assigning radio channels to the cells:
- comprising the steps of;
determining the available cells and frequencies;
determining interference and system constraints for the cells;
determining existing traffic patterns for the cells;
inputting the cells, frequencies, interference and system constraints, including blocking requirements, and traffic into a computing device;
programming the computing device to optimize the assignment of radio channel sets to the cells wherein the improvement comprises;
decomposing a calculation for optimizing the radio channel set assignment into a Master Program and a Subprogram,initially solving the Master Program in order to determine values for a capacity factor, channel set sizes, a first simplex multiplier vector corresponding to the channel assignment constraints for each cell, and a second simplex multiplier vector corresponding to the radio channels availability constraint;
wherein the capacity factor represents a bottle neck capacity ratio of a number of radio frequencies assigned to a cell over the number of radio frequencies needed to meet blocking requirements;
solving the Subprogram to generate additional channel sets using output values from the Master Program which include channel set sizes and the simplex multiplier vector;
byheuristically providing new values of channel set sizes and the first simplex multiplier vector to replace for calculation purposes these values for values initially determined by the initially solving of the master program, andresolving the Subprogram to generate further channel sets;
resolving the Master Program using channel sets determined by solving and resolving the subprogram to maximize the capacity factor and for selecting channel sets and for determining new sizes of the channel set;
checking the resulting assignments for optimality by evaluating the second simplex multiplier;
terminating when optimality is achieved;
transmitting the assignments to the respective base stations; and
tuning the radios of the base stations to the appropriate frequencies.
1 Assignment
0 Petitions
Accused Products
Abstract
A channel assignment system assigns channels to various cells by the optimal partitioning of the available radio frequencies into non-overlapping sets, the optimal grouping of co-user cells, and the best assignment of the former to the latter. The objective is the maximization of traffic handling capacity which, given the multitude of cells, is expressed as the maximization of a bottleneck capacity ratio. The capacity ratio for a cell is defined as the ratio of the number of radio frequencies assigned to the cell over the number of radio frequencies needed to meet blocking probability requirements. The solution to attain an optimal non-regular channel assignment is decomposed into two mathematical programs designated a Master Program and a Subprogram. These are solved iteratively with assistance from a channel set augmentation technique impelmented between solutions of the Master and Subprogram.
91 Citations
8 Claims
-
1. In a wireless communications system having service areas partitioned into a plurality of substantially contiguous cells, a method of assigning radio channels to the cells:
-
comprising the steps of; determining the available cells and frequencies; determining interference and system constraints for the cells; determining existing traffic patterns for the cells;
inputting the cells, frequencies, interference and system constraints, including blocking requirements, and traffic into a computing device;programming the computing device to optimize the assignment of radio channel sets to the cells wherein the improvement comprises; decomposing a calculation for optimizing the radio channel set assignment into a Master Program and a Subprogram, initially solving the Master Program in order to determine values for a capacity factor, channel set sizes, a first simplex multiplier vector corresponding to the channel assignment constraints for each cell, and a second simplex multiplier vector corresponding to the radio channels availability constraint;
wherein the capacity factor represents a bottle neck capacity ratio of a number of radio frequencies assigned to a cell over the number of radio frequencies needed to meet blocking requirements;solving the Subprogram to generate additional channel sets using output values from the Master Program which include channel set sizes and the simplex multiplier vector;
byheuristically providing new values of channel set sizes and the first simplex multiplier vector to replace for calculation purposes these values for values initially determined by the initially solving of the master program, and resolving the Subprogram to generate further channel sets; resolving the Master Program using channel sets determined by solving and resolving the subprogram to maximize the capacity factor and for selecting channel sets and for determining new sizes of the channel set; checking the resulting assignments for optimality by evaluating the second simplex multiplier; terminating when optimality is achieved; transmitting the assignments to the respective base stations; and tuning the radios of the base stations to the appropriate frequencies. - View Dependent Claims (2, 3)
-
-
4. In a wireless telephone communication system, having a plurality of substantially contiguous cells;
- apparatus for assigning radio channels to cells comprising;
input apparatus for storing in a memory information concerning available radio channel constraints, cell identifications, interference and system assignment constraints and existing traffic patterns for the cells; a computer including programmed instructions for developing radio channel assignments in response to data stored in the memory; means for assigning to the cells the radio channel sets developed by the computer to enable radio transceivers at the cells to tune to frequencies in accordance with the channel assignments; wherein the programmed instructions carry out the process of; selecting a first collection of channel sets; for the first collection of channel sets, determining values for a capacity factor representing a bottleneck capacity ratio of a number of radio frequencies assigned to a cell over the number of radio frequencies needed to meet blocking requirements, set sizes, a first simplex multiplier vector corresponding to channel assignment constraints for each cell, and a second simplex multiplier corresponding to the available radio channels constraint; generating additional channel sets to improve the capacity factor using values obtained from the step of determining; heuristically computing new values of channel set sizes and new values of simplex multiplier vectors; repeating the step of generating a selected a selected number of times each time including the heuristically selected new values in the generating process; and returning to the step of determining as long as a selected criteria is not met. - View Dependent Claims (5, 6, 7)
- apparatus for assigning radio channels to cells comprising;
-
8. In a wireless communication system in which a service area is partitioned into a plurality of non-regular contiguous cells;
- a method of dynamically altering assignments of radio channels to the cells comprising the steps of;
initially determining interference constraints, system constraints and available channel frequencies and entering the information into a memory of a computer; storing an existing assignment of radio channels into the memory; determining existing traffic patterns of mobile radio telephone usage within the service area and entering the existing traffic pattern into the memory of the computer; developing an improved assignment of radio channels to the cells; and communicating the improved assignment of radio channels to the cells, causing radio transceivers at the cells to operate at frequencies representing the improved channel assignments; wherein the improvement comprises programming the computer to solve a calculation for optimizing radio channel assignments to the cells by decomposing the calculation into a Master Program and a Subprogram, and by; initially solving the Master Program to determine values for a capacity factor representing a ratio of radio frequencies assigned to a cell to radio frequencies needed to meet blocking requirements, channel set sizes, a first simplex multiplier vector corresponding to interference and system constraints for each cell and a second simplex multiplier vector corresponding to available channel frequencies; solving the Subprogram to generate additional channel sets using output values from the Master Program; heuristically generating new values for use by the Subprogram of the first simplex multiplier vector and of channel set sizes; and resolving the Subprogram using the new values to generate further channel sets; resolving the Master Program using results of the Subprogram for selecting additional channel sets to maximize the capacity factor; checking resulting channel set sizes of the master program for optimally; and terminating when optimality is achieved.
- a method of dynamically altering assignments of radio channels to the cells comprising the steps of;
Specification