Method and apparatus for assigning channels to transmitters in a radio communication system

Claim 3

The method of claim 1, wherein the defining step comprises the steps of: determining values for co-channel and adjacent-channel transmitter exclusion tables based upon interference levels between each pair of transmitters; and selecting an exclusion value threshold beyond which a transmitter interference constraint is violated.

Claim 4

The method of claim 1, wherein the measuring step comprises the step of dynamically determining the channel capacity required in response to the traffic queued for each of the plurality of transmitters.

Claim 5

The method of claim 1, wherein the measuring step comprises the step of estimating the channel capacity required from demographic data available for an area served by the radio communication system.

Claim 6

A controller for assigning a plurality of channels to a plurality of transmitters in a radio communication system, the controller comprising: a processing system for directing operations of the controller; a network interface coupled to the processing system for receiving messages from message originators; and a transmitter interface coupled to the processing system for controlling the plurality of transmitters to send the messages, wherein the processing system is programmed to: define interference constraints for the plurality of transmitters; measure a channel capacity required to handle traffic for each of the plurality of transmitters; apply a linear programming technique to minimize a total number of channels assigned in the system, consistent with the interference constraints and the channel capacity required, which can result in a fractional solution of channel-to-transmitter assignment values; and generate an integer solution based upon values of the fractional solution by performing a process selected from a group of processes consisting of process (a), process (b), and process (c), wherein process (a) programs the processing system to time-share the channel-to-transmitter assignment values in proportion to values of the fractional solution, and wherein process (b) programs the processing system to randomly round the fractional solution periodically, wherein a probability of rounding a channel-to-transmitter assignment value to unity is equal to a fractional solution value corresponding to the channel-to-transmitter assignment value before rounding, and wherein process (c) programs the processing system to: sort by transmitter the traffic queued for the plurality of transmitters during a predetermined period; select a transmitter having a highest channel capacity required that is not yet processed; sort the channel-to-transmitter assignment values associated with the transmitter selected; choose a highest non-zero one of the channel-to-transmitter assignment values that has not yet been processed; round up the highest non-zero one to unity when no interference constraint is violated as a result; round down the highest non-zero one to zero when an interference constraint would be violated by rounding to unity; check how much accumulated channel capacity has been accumulated for the transmitter by the rounding up and rounding down steps; continue to choose, round up and round down when the accumulated channel capacity is less than the channel capacity required for the transmitter; and otherwise, select another transmitter for processing until all transmitters have been processed.

Claim 7

A controller for assigning a plurality of channels to a plurality of transmitters in a radio communication system, the controller comprising: a processing system for directing operations of the controller; a network interface coupled to the processing system for receiving messages from message originators; and a transmitter interface coupled to the processing system for controlling the plurality of transmitters to send the messages, wherein the processing system is programmed to: define interference constraints for the plurality of transmitters; measure a channel capacity required to handle traffic for each of the plurality of transmitters; apply a linear programming technique to minimize a total number of channels assigned in the system, consistent with the interference constraints and the channel capacity required, which can result in a fractional solution of channel-to-transmitter assignment values; and generate an integer solution based upon values of the fractional solution by performing a process selected from a group of processes consisting of process (a), process (b), and process (c), wherein process (a) programs the processing system to time-share the channel-to-transmitter assignment values in proportion to values of the fractional solution, and wherein process (b) programs the processing system to randomly round the fractional solution periodically, wherein a probability of rounding a channel-to-transmitter assignment value to unity is equal to a fractional solution value corresponding to the channel-to-transmitter assignment value before rounding, and wherein process (c) programs the processing system to: sort by transmitter the traffic queued for the plurality of transmitters during a predetermined period; select a transmitter having a highest channel capacity required that is not yet processed; sort the channel-to-transmitter assignment values associated with the transmitter selected; choose a highest non-zero one of the channel-to-transmitter assignment values that has not yet been processed; round up the highest non-zero one to unity when no interference constraint is violated as a result; round down the highest non-zero one to zero when an interference constraint would be violated by rounding to unity; check how much accumulated channel capacity has been accumulated for the transmitter by the rounding up and rounding down steps; continue to choose, round up and round down when the accumulated channel capacity is less than the channel capacity required for the transmitter; and otherwise, select another transmitter for processing until all transmitters have been processed.

Claim 8

The controller of claim 5, wherein the processing system is further programmed to: determine values for co-channel and adjacent-channel transmitter exclusion tables based upon interference levels between each pair of transmitters; and select an exclusion value threshold beyond which a transmitter interference constraint is violated.

Claim 9

The controller of claim 5, wherein the processing system is further programmed to dynamically determine the channel capacity required in response to the traffic queued for each of the plurality of transmitters.

Claim 10

The controller of claim 5, wherein the processing system is further programmed to estimate the channel capacity required from demographic data available for an area served by the radio communication system.