| Common Principle Of Channel Allocation |
The large array of possible channel allocation systems can become cumbersome.
However, all channel allocation methods operate under simple, common principles.
Throughout this report we have touched on three points which an efficient
channel allocation scheme should address:
- Channel allocation schemes must not violate minimum frequency reuse
conditions.
- Channel allocation schemes should adapt to changing traffic conditions.
- Channel allocation schemes should approach (from above) the minimum
frequency reuse constraints so as to efficiently utilize available
transmission resources.
As the first requirement suggests, all channel allocation schemes adhere to
condition 1. From a frequency reuse standpoint, a fixed channel allocation
system distributes frequency (or other transmission) resources to the cells in
an optimum manner; i.e., common channels are separated by the minimum frequency
reuse distance. Thus, a fixed channel allocation scheme perfectly satisfies
condition 3 as well. However, a fixed allocation scheme does not satisfy
condition 2.
Philosophically, any dynamic channel allocation scheme will meet the
requirements of all of the above three conditions to some degree. At the system
architecture level dynamic channel allocation schemes may differ widely, but
fundamentally, their only difference is in the degree to which they satisfy
condition 3. Different DCA schemes attempt to satisfy condition 3 (in addition
to conditions 1 and 2) by approaching the minimum frequency reuse constraint
arbitrarily closely, and by doing so in as short a time period as possible. The
above three conditions point to the fact that design of dynamic channel
allocation schemes falls within the general class of optimization problems.
Furthermore, since we can always assume that the available number of base
stations is finite and the transmission resources will always be countable (due
to FCC requirements if nothing else) then our problem can be reduced to the
subclass of combinatorial optimization problems. As with all combinatorial
optimization problems, there will exist a solution space and a cost function [Aarts
& Korst]. A typical element of the solution space could be a particular layout
of frequency channels among the base-stations. The cost function can be loosely
characterized as the difference between the frequency reuse of an arbitrary
solution and the frequency reuse of the optimized solution. The error associated
with a non-optimized cost is realized as a future increased blocking probability
or an otherwise unwarranted lack of channel availability. It is typically
assumed that the solution to the wireless dynamic channel allocation problem is
NP-complete [Yue, Cox - 1971]. The definition of np-completeness follows from
the conjecture made in the late 1960's that there exists a class of
combinatorial optimization problems of such inherent complexity that any
algorithm, solving each instance of such a problem to optimality, requires a
computational effort that grows superpolynomially with the size of the problem.
In the case of dynamic channel allocation, the complexity is generally
attributed to the required inclusion of cochannel interference in any analysis
of dynamic channel allocation schemes [Yue]. The author is aware of one
published article to date offering an analytical method (approximate) for
calculating the performance of dynamic channel allocation [see Yue]. Recently,
several approximation techniques have been proposed as methods for solving
condition 3 of the dynamic channel allocation problem. In particular there has
been interest in applying simulated annealing techniques [Duque-Anton] and
neural network methods [Chan, Kunz, Funabiki] to dynamic channel allocation.
|
