CHAPTER 3
Heuristics for Solving Fixed-Channel
Assignment Problems
HARILAOS G. SANDALIDIS and PETER STAVROULAKIS
Telecommunication Systems Institute, Chania, Crete, Greece
3.1 INTRODUCTION
The tremendous growth of the mobile users’ population coupled with the bandwidth re-
quirements of new cellular services is in contrast to the limited spectrum resources that
have been allocated for mobile communications. The objective of channel allocation is to
assign a required number of channels to each cell such that efficient frequency spectrum
utilization is provided and interference effects are minimized. A fixed-channel assignment
problem models the task of assigning radio spectrum to a set of transmitters on a perma-
nent basis. The formulation of this problem as a combinatorial one in the beginning of the
1980s led a number of computer scientists and operations research scientists to try and
find optimal solutions. Heuristic techniques can give near-optimal solutions at a reason-
able computational cost for algorithmically complex or time-consuming problems such as
channel assignment. An overview of the most basic heuristic fixed-channel assignment
schemes in the literature is the subject of this study.
3.2 RESOURCE MANAGEMENT TASKS
Cellular radio systems rely on a subsequent allocation and reuse of channels throughout a
coverage region. Each cell is allocated a group of radio channels. Neighboring cells are
given channel groups that contain completely different channels. By limiting the coverage
area within the boundaries of a cell, the same group of channels may be used to cover dif-
ferent cells that are separated from one another by some distance.
Cellular mobile communication systems are characterized by their high degree of ca-
pacity. Consequently they have to serve the maximum possible number of calls, though
the number of channels per cell is limited. On the other hand, cells in the same cluster
must not use the same channel because of the increased possibility of various kinds of in-
terference that appear mainly during the busy hours of the system. Hence the use of tech-
niques that are capable of ensuring that the spectrum assigned for use in mobile communi-
cations will be optimally utilized is gaining ever-increasing importance. This makes the

new calls may be queued, etc.
ț Power control. In cellular networks, it is desirable to maintain bit error rates above a
chosen minimum. This would require the carrier to interference ratio of the radio
links be maintained above a corresponding minimum value for the network. Power
control is a specific resource management process that performs this task.
It is evident that an integrated radio resource management scheme can make necessary
trade-offs between the individual goals of these tasks to obtain better performance and in-
crease system capacity within specified quality constraints. However, a combination of in-
dividual radio resource management tasks is also possible. For example, handoff and
channel assignment tasks, or power control assisted admission schemes can be combined
to provide interesting results [55].
3.3 INTERFERENCE IN CELLULAR SYSTEMS
The major factor that determines the number of channels with a predetermined quality is the
level of received signal quality that can be achieved in each channel. This level strongly de-
52
HEURISTICS FOR SOLVING FIXED-CHANNEL ASSIGNMENT PROBLEMS
pends on the interference effects. Some possible sources of interference may be another car-
rier in the same cell, a call in progress in a neighboring cell, other base stations operating in
the same frequency band, or any noncellular system that radiates in the same frequency
band. Interference on voice channels causes crosstalk—the subscriber hears interference in
the background due to another call. On control channels, interference leads to missed calls
and blocked calls. Interference is more severe in urban areas, due to industrial interference
and a large number of base stations and mobiles in the proximity. It has been recognized as
a major bottleneck in increasing capacity. Interference to a channel that serves a particular
call occurs mainly when a user in an adjacent cell uses the same channel (cochannel inter-
ference), a user in the same region uses an adjacent channel (cosite interference), or a user
in an adjacent region uses an adjacent channel (adjacent channel interference) [28].
3.3.1 Cochannel Interference
Frequency reuse increases the system’s spectrum efficiency, but interference due to the
common use of the same channel may occur if the system is not properly planned. This

R
3.3 INTERFERENCE IN CELLULAR SYSTEMS
53
interference). It should be noted that the adjacent channel here is not the close neighboring
channel in a strict communication sense, but rather the nearest assigned channel in the
same cell and can be several channels apart.
Cosite and adjacent channel interference result from equipment limitations, mainly
from imperfect receiver filters that allow nearby frequencies to leak into the passband.
The problem can be particularly serious if one adjacent channel user is transmitting in
close range to a receiver that is attempting to receive a weaker signal using a neighbor-
ing channel. Several techniques can be used in order to solve this problem. The total fre-
quency spectrum is usually split into two halves so that the reverse channels that com-
pose the up-link (mobile to base station) and the forward channels that compose the
down-link (base station to mobile) can be separated by half of the spectrum. If other ser-
vices can be inserted between the two halves, then a greater frequency separation can be
attained [19].
Cosite and adjacent channel interference can also be minimized through careful chan-
nel assignments. By keeping the frequency separation between each channel in a given
cell as large as possible, these types of interference may be reduced considerably. Some
designers also prevent a source of adjacent channel interference by avoiding the use of ad-
jacent channels in geographically adjacent cell sites. This strategy, however, is dependent
on the cellular pattern. For instance, if a seven-cell cluster is chosen, adjacent channels are
inevitably assigned to adjacent cells.
3.3.3 Intermodulation
Intermodulation distortion (IMD) is a nonlinear phenomenon that occurs when some mul-
tiplexed frequency channels go through a nonlinear device such as a power amplifier. The
nonlinear characteristic of such a device generates several undesired cross-modulation
terms, mainly at frequencies 2f
i
– f

quency division, the spectrum is divided into frequency bands. In time division, the us-
age of the channel is divided into time slots that are disjoint time periods. Finally, in
code division, the channel separation is achieved by using different modulation codes.
54
HEURISTICS FOR SOLVING FIXED-CHANNEL ASSIGNMENT PROBLEMS
Moreover, other techniques based on the combination of the above methods can be used
[28].
Since the radio spectrum is finite in mobile radio systems, the most significant chal-
lenge is to use the radio-frequency spectrum as efficiently as possible. Geographic loca-
tion is an important factor in the application of the frequency reuse concept in mobile cel-
lular technology to increase spectrum efficiency. The techniques for increasing the
frequency spectrum can be classified as [37]:
ț Increase the number of radio channels
ț Improve spatial frequency spectrum reuse
ț Use proper frequency management and channel assignment techniques
ț Improve spectrum efficiency in time
ț Reduce the load of invalid calls (call forwarding, queuing, etc.)
The function of frequency management is to divide the total number of available chan-
nels into subsets that can be assigned to each cell either in a fixed fashion or dynamically.
The terms frequency management and channel assignment are often confused. Frequency
management refers to designating set-up channels and voice channels, numbering the
channels, and grouping the voice channels into subsets (done by each system according to
its preference). Channel assignment has to do with the allocation of specific channels to
cell sites and mobile units. A fixed channel set that consists of one or more subsets is as-
signed to a cell site on a long-term basis. During a call, a specific channel is assigned to a
mobile unit on a short-term basis [37].
Frequency planning is therefore one of the most challenging tasks in designing a cellu-
lar mobile network. An accurate radio planning tool is essential for calculating predicted
signal strength coverage and interference levels and satisfying the overall grade of service.
The allocation of frequency channels to cells in a cellular network is a critical element of

avoid unwanted mobile receiver outputs resulting from interference, implementation of at
least third-order compatible frequency plans is highly desirable.
3.5 CHANNEL ASSIGNMENT
Channel assignment is a fundamental task of resource management that increases the fi-
delity, capacity, and quality of service of cellular systems by assigning the required num-
ber of channels to each cellular region in such a way that both efficient frequency spec-
trum utilization is provided and interference effects are eliminated. The channel allocation
strategy can be seen as a method of assigning available channels to calls originating in the
cells. If the strategy is unable to assign a channel, the call is blocked. The basic goal to be
achieved by channel allocation techniques under the prism of the rapidly growing demand
for cellular mobile services is to efficiently utilize the available spectrum so as to achieve
optimum system performance.
The main focus on research concerning channel assignment is to find strategies that
give maximal channel reuse without violating the constraints so that blocking is minimal.
Constraints can be classified into three categories [14]:
1. The frequency constraint specifies the number of available frequencies (channels)
in the radio spectrum. This constraint is imposed by national and international regu-
lations.
2. The traffic constraints specify the minimum number of frequencies required by
each station to serve a geographic area. These constraints are empirically deter-
mined by the telecommunications operators.
3. The interference constraints are further classified as:
ț The cochannel constraint—the same channel cannot be assigned to certain pairs
of radio cells simultaneously.
ț The adjacent channel constraint—frequencies adjacent in the frequency domain
cannot be assigned to adjacent radio cells simultaneously.
ț The cosite constraint—any pair of channels assigned to a radio cell must occupy
a certain distance in the frequency domain.
56
HEURISTICS FOR SOLVING FIXED-CHANNEL ASSIGNMENT PROBLEMS

gence, and mobile communication fields [34].
3.6 FIXED-CHANNEL ASSIGNMENT PROBLEM
A lot of existing systems are operating with fixed-channel assignment, in which channels
are permanently assigned to cells for exclusive use. Cells that have the same reuse dis-
tance can use the same channels. This uniform channel distribution is efficient if the traf-
fic distribution of the system is also uniform. However, for nonuniform traffic environ-
ments, a uniform channel distribution results in poor channel utilization. Cells in which
traffic load is high may not have enough channels to serve calls, whereas spare channels
may exist in some other cells with low traffic conditions. It is, therefore, appropriate to
use nonuniform channel distribution. In this case, the number of nominal channels as-
signed to each cell depends on the expected traffic profile in that cell. Hence, heavily
loaded cells are assigned more channels than lightly loaded ones.
3.6 FIXED-CHANNEL ASSIGNMENT PROBLEM
57
FCA is also shown to be sensitive to temporal and spatial traffic variations and hence is
not able to attain a high degree of channel efficiency. However, this scheme is very simple
in design and is very efficient for stationary, heavy traffic loads. In fact, the greatest ad-
vantage of FCA is the low call service time. Due to the already assigned channels among
cells, the process of finding a channel to serve a call does not require elaborate control.
Hence, calls do not have to wait and are either served or blocked.
In order to achieve better performance in mobile networks operating with the FCA,
proper frequency planning is required. The available frequency band is usually partitioned
into a set of channels having the same bandwidth of frequencies, and channels are num-
bered from 1 to a given maximum N. In fact, a mobile user needs two channels—the first
one for the mobile-to-base station link and the second for the base-to-mobile station link.
However, as these two channels are assigned together, a lot of studies consider a channel
to contain only one link.
A cellular network can be described by a weighted graph in which the nodes corre-
spond to the cells or the transmitters and the edges join nodes that correspond to adjacent
cells or transmitters in the network. The weight of the edges (0, 1, 2) represents the sepa-

c
ij
= 1 there is cochannel constraint
c
ij
Ն 2 there is adjacent channel constraint
c
1N
c
2N
Ӈ
c
NN
...
...
.
.
.
...
c
12
c
22
Ӈ
c
N2
c
11
c
21