IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO.

5, SEPTEMBER 2003 939

Planning UMTS Base Station Location: Optimization

Models With Power Control and Algorithms
Edoardo Amaldi, Antonio Capone, Member, IEEE, and Federico Malucelli

Abstract—Classical coverage models, adopted for second-gen- criterion [1], [3], [4]. In the coverage planning phase, BSs are
eration cellular systems, are not suited for planning universal mo- placed so that the signal strength is high enough in the area to be
bile telecommunication system (UMTS) base station (BS) location served [5]–[9]. This step only makes use of propagation models,
because they are only based on signal predictions and do not con-
sider the traffic distribution, the signal quality requirements, and such as for instance Hata’s model, to predict the signal levels
the power control (PC) mechanism. In this paper, we propose dis- (see, e.g., [10]). In the frequency planning phase, a set of chan-
crete optimization models and algorithms aimed at supporting the nels has to be assigned to each BS [11], [12], taking into account
decisions in the process of planning where to locate new BSs. These the traffic requirements and the service quality measured as the
models consider the signal-to-interference ratio as quality measure signal-to-interference ratio (SIR).
and capture at different levels of detail the signal quality require-
ments and the specific PC mechanism of the wideband CDMA air With the wideband code-division multiple access
interface. Given that these UMTS BS location models are nonpoly- (W-CDMA) air interface of UMTS, this two-phase ap-
nomial (NP)-hard, we propose two randomized greedy procedures proach is not appropriate mainly because the bandwidth is
and a tabu search algorithm for the uplink (mobile to BS) direction shared by all active connections and no actual frequency
which is the most stringent one from the traffic point of view in the
presence of balanced connections such as voice calls. The different assignment is strictly required. The access scheme allows for a
models, which take into account installation costs, signal quality more flexible use of radio resources and the capacity of each
and traffic coverage, and the corresponding algorithms, are com- cell (e.g., the number of connections) is not limited a priori
pared on families of small to large-size instances generated by using by a fixed channel assignment as in TDMA systems, but it
classical propagation models.
depends on the actual interference levels which determine
Index Terms—Code-division multiple access (CDMA), optimiza- the achievable SIR values. As these values depend on both
tion algorithms, optimization models, planning, power control traffic distribution and BS positions, BS location in UMTS
(PC), universal mobile telecommunication system (UMTS).
networks cannot only be based on coverage but it must also be
capacity driven [3]. Indeed, interference levels are functions
I. INTRODUCTION of the emitted powers which, due to a power control (PC)
mechanism, depend on the mobile station positions. Since the
W ITH THE extraordinary success of mobile communica-
tion services, service providers have been affording huge
investments for network infrastructures. Due to the high costs
power available for transmission is limited, mobile stations
that are far away from the BS may not reach the minimum
and the scarcity of radio resources, an accurate and efficient SIR when the interference level is too high. Therefore, the area
mobile network planning appears of outmost importance. With actually covered by each BS is heavily affected by the traffic
the rapid growth of network size and number of users, efficient distribution and its size can vary when the interference level
quantitative methods to support decisions for base station (BS) changes (this is the so-called cell breathing effect). It is worth
location have become essential. This need is now even more emphasizing that, since interference levels depend both on the
acute with the advent of third-generation systems, such as uni- connections within a given cell and on those in neighboring
versal mobile telecommunication system (UMTS), due to the cells, the SIR values and the capacity are highly affected by the
increased complexity of the system and the number of parame- traffic distribution in the whole area.
ters that must be considered [1]–[3]. The planning phase of cellular networks usually takes as
The problem of planning second-generation cellular systems input the following kind of information related to the service
adopting a time-division multiple access (TDMA)-based access area: 1) a set of candidate sites where BSs can be installed;
scheme has usually been simplified by subdividing it into a 2) the traffic distribution estimated by using empirical pre-
coverage planning problem and a frequency planning problem diction models; and 3) the propagation description based on
which are driven by a coverage and, respectively, a capacity approximate radio channel models or ray tracing techniques.
The main purpose of planning is then to select the sites where
Manuscript received August 7, 2001; revised January 31, 2001; accepted to install the BSs taking into account different aspects such as
March 11, 2002. The editor coordinating the review of this paper and ap- costs, signal quality, and service coverage.
proving it for publication is M. Zorzi. This work was supported by Progetto
Cofinanziato MURST 1999–2001, Optimization Models and Methods for
As we shall see in Section II, there has been so far little work
Telecommunication Network Design and Management. on optimizing BS locations for UMTS networks and, to the best
The authors are with the Dipartimento di Elettronica e Informazione, of our knowledge, none of the proposed models considers the
Politecnico di Milano, 20133 Milan, Italy (e-mail: [email protected];
[email protected]; [email protected]). impact of traffic distribution, signal quality requirements, and
Digital Object Identifier 10.1109/TWC.2003.817438 PC mechanism at an adequate level of detail. In this paper, we
1536-1276/03$17.00 © 2003 IEEE
940 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO. 5, SEPTEMBER 2003

propose and investigate discrete optimization models aimed at where is the received power of the signal, is the
supporting the decisions in the process of planning where to lo- total interference due to the signals transmitted by the same BS
cate new BSs. Our models differ in how closely they capture the (intracell interference), that due to the signals emitted by
peculiarities of the signal quality constraints and the PC mech- the other BSs (intercell interference), is the orthogonality loss
anism of the UMTS W-CDMA air interface. The focus here is factor , and the thermal noise power. In the uplink
on the uplink direction (mobile to BS), which turns out to be the case, no orthogonality must be accounted for and .
most stringent one from the system capacity point of view in the Since the quality of the received signal, usually expressed in
presence of full-duplex balanced connections such as voice calls terms of bit error rate, mainly depends on the SIR, it is common
(see, e.g., [13] and [14]). Models for the downlink direction are to consider quality constraints requiring that the SIR exceeds a
presented in [15] and [39]. minimum value which may vary according to the communi-
In Section II, we discuss the main radio network planning cation service considered (voice, video, packet data, etc.). For
issues pertaining to UMTS BS location and comment on the sake of simplicity, in the sequel, we refer to the minimum
previous work. In Section III, we propose and analyze mathe- SIR before despreading as .
matical programming formulations of this general problem for A simplified and commonly adopted model [20] assumes that
the W-CDMA setting considering the two most common ways the interference due to the neighboring cells can be ex-
to model the PC mechanism. In Section IV, we describe three pressed as a fraction of the interference due to the other trans-
heuristics: randomized greedy and reverse greedy procedures missions in the same cell, so that the SIR can be expressed as
as well as a tabu search (TS) algorithm. Computational results
(2)
obtained with realistic instances are reported and discussed in
Section V. Finally, Section VI contains some concluding re-
where the thermal noise is omitted since it is assumed to be
marks. Preliminary versions of part of this work were presented
much smaller than the interference. This simplified model is ac-
in [16] and [17].
curate when the traffic distribution among cells is homogeneous,
while it is inappropriate in all the other cases where the contri-
II. RADIO PLANNING ISSUES FOR UMTS bution to intercell interference is different for each cell. Values
of in the 0.3–0.5 range are usually considered.
UMTS [18] is the third-generation mobile communication
system standardized by ETSI, the European Telecommunica- A. PC and Capacity Constraints
tions Standard Institute, and is also considered by ITU (Inter-
As mentioned above, the SIR depends on the received powers
national Telecommunication Union) among the standards for
of the considered signal and of the interfering ones. These in
the International Mobile Telephone standard 2000 (IMT-2000)
turn depend on the transmitted powers and the attenuation of the
family.
radio link between sources and receivers. According to propa-
One of the two access schemes to be used in the assigned
gation conditions, the transmitted power can be adjusted by the
spectrum is based on W-CDMA and frequency-division du-
PC mechanism so as to minimize interference and guarantee
plexing. The main characteristic of CDMA is its flexibility in
quality. Two PC mechanisms are commonly considered: one
the use of radio resources. In particular, there is no a priori
based on the received power and the other one on the estimated
limit on the number of simultaneous connections per cell (hard
SIR. In the first one, the transmitted power is adjusted so that the
capacity) as with TDMA systems, and resources are dynam-
power received on each channel is equal to a given target value
ically assigned according to interference levels and traffic
. Similarly, in the second one, the transmitted power is
distribution (soft capacity) [13]. However, this clearly implies
set so that the SIR is equal to a target value . The
an increased complexity in the network planning process and
latter mechanism, adopted for UMTS dedicated channels [18],
more involved access control procedures. Ad hoc planning and
is more complex since the power emitted by each station de-
optimization strategies for the CDMA technology are, thus,
pends on that emitted by all the others, but more efficient since it
needed to actually exploit this additional flexibility [3].
allows for the use of lower powers [21]. Therefore, from a plan-
Spreading codes used for signals transmitted in downlink by
ning prospective, assuming a power-based PC mechanism in-
the same BS are mutually orthogonal, while codes used for sig-
stead of an SIR-based one leads to a conservative dimensioning
nals emitted by different stations (base or mobile) can be consid-
which may allocate more radio resources than necessary.
ered as pseudorandom due to the scrambling sequence [19]. In
Both in the case of power-based or SIR-based PC mecha-
an ideal environment, the despreading process performed at the
nisms, the transmitted powers are adjusted considering some
receiving end can completely avoid interference of orthogonal
power limits. In particular, a limit on the maximum power used
signals and reduce that of nonorthogonal ones by the spreading
for each radio channel must be considered both for uplink and
factor (SF), which is the ratio between the spread signal rate and
downlink. Moreover, for the downlink case only, a constraint on
the user rate. In wireless environments, due to multipath prop-
the total power emitted by the BS must be added. Therefore, the
agation, the interference of orthogonal signals cannot be com-
actual power emitted on a channel is the minimum between that
pletely avoided and the SIR is given by
provided by the PC mechanism and the maximum value.
From a planning point of view, the effect of the power bounds
and SIR constraints is to limit the capacity of the system. In
(1) the presence of power-based PC, as new users are added to the
AMALDI et al.: PLANNING UMTS BS LOCATION: OPTIMIZATION MODELS WITH PC AND ALGORITHMS 941

system, the SIR values of all the other users decrease until one III. BS LOCATION MODELS
falls below the lowest acceptable quality level . No ad- Since, to the best of our knowledge, some crucial issues of
ditional user can then be served. In the presence of SIR-based the planning problem for CDMA-based UMTS networks have
PC, signal quality is guaranteed by keeping the SIRs at a con- not yet been captured, we propose and investigate different
stant target value . When new users are
mathematical programming models for the UMTS BS location
added, the emission powers required to keep the SIRs equal to
problem that account for intercell interference in the SIR con-
increase until the power limit is exceeded and, hence,
straints and for the PC mechanism. As previously mentioned,
the SIR falls below the target value. In both power-based and
the focus here is on the uplink direction with power-based as
SIR-based cases, the capacity is affected by user positions and
well as SIR-based PC mechanism.
propagation conditions. Indeed, the capacity depends on the in-
In this work, we make two simplifying assumptions. First, we
terference generated by user-BS transmissions which, in turn,
assume that each connection is assigned to a single BS. There-
depends on the emitted powers, which are strongly related to the
fore, we do not explicitly account for soft-handover which al-
relative positions and the radio link propagation factors. Since
lows a mobile terminal to be simultaneously connected with a
each user-BS transmission generates interference not only in its
set of BSs. It is worth noting, however, that our assumption is
own cell but also toward all the other cells, it is as if each user in-
on the conservative side from a planning point of view since
volved in a connection “absorbs” a fraction of the capacity from
soft-handover tends to increase the SIR values. A simple way
all BSs.
to account for this feature is that of including an additional
margin on the SIR constraints (i.e., of selecting a lower ).
B. Related Work Second, we assume that the number of available spreading codes
is higher that the number of connections assigned to any BS.
Classical coverage optimization models do not consider SIR This assumption is clearly satisfied in the uplink direction since
constraints but only constraints on the received power levels in there is a very large number of nonorthogonal codes.1
the service area. In [22], the traffic distribution is described by
means of demand nodes which represent the center of an area A. Basic Model
characterized by a given traffic demand (usually expressed in
Consider a territory to be covered by a UMTS service. As-
Erlang). Using the demand node characterization, the coverage
sume that a set of candidate sites where a BS
problem is then defined by considering the signal level in each
can be installed, is given and that an installation cost is as-
node from all BSs and requiring that at least one level is above
sociated with each candidate site . A set of test points
a fixed threshold. A common objective of the optimization
(TPs) is also given. Each TP can be con-
process is that of finding the smallest set of BSs covering all
sidered as a centroid where a given amount of traffic (in Er-
demand nodes (see, e.g., [6] and [7]). In [23] and [24], traffic lang) is requested and where a certain level of service (measured
capacity constraints are also added for each BS. A different in terms of SIR) must be guaranteed [6]. The required number
coverage model is adopted in [5], where the position of trans- of simultaneously active connections for TP , denoted by ,
mitters is selected from continuous three-dimensional space turns out to be a function of the traffic demand, i.e., .
so as to minimize the sum of path losses of the links to all The actual definition of the function is a degree of freedom
receivers. of the planning process. It can simply correspond to the average
A few recent works address network planning problems for number of active connections or to the number of simultaneous
CDMA systems and, in particular, for UMTS. However, some connections not exceeded with a given probability . The con-
of them still rely on a classical coverage approach: In [25], a nection activity factor can be considered as well.
simple model based on the minimum dominating set problem is The propagation information is also supposed to be known. In
considered while in [26], the traffic capacity is also taken into particular, let be the propagation factor of the
account and the resulting classical capacitated facility location radio link between TP and a candidate site
problem is tackled with a TS algorithm. In [27], a different ap- . The propagation gain matrix is
proach is adopted: A maximum independent set of vertices is estimated according to approximate propagation models such as
searched for in a graph in which vertices represent candidate those proposed by Hata or to more precise but computationally
sites and edges correspond to pairs of sites whose BSs would intensive ray tracing techniques (see, e.g., [10]).
have coverage areas with too much overlap. In the W-CDMA UMTS BS location problem, one wishes
In [28], a simplified model for locating BSs in CDMA-based to select a subset of candidate sites within the set where to
UMTS networks, which partially takes into account interfer- install BSs, and to assign the TPs to the available BSs taking
ence, is proposed and a polynomial time approximation scheme into account the traffic demand, the signal quality requirements
is presented. However, only intracell interference is considered in terms of SIR and the installation costs.
while the crucial aspect of the interference among BSs (inter- Let us define the two following classes of decision variables:
cell one) is neglected. As we shall see in Section III-A, even
if the intercell interference is assumed to be a nonzero fraction if a BS is installed in
of the intracell interference, in the uplink case, each interference otherwise
constraint amounts to impose a simple upper bound on the max- 1In the downlink direction, where at most SF orthogonal codes are used, stan-
imum number of active connections with the corresponding BS. dard cardinality contraints can be easily added to the model.
942 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO. 5, SEPTEMBER 2003

for and it is equal to and the quality constraint amounts to im-

posing an upper bound on the number of connec-
test point is assigned to
tions that can be assigned to that BS [20]. Specifically, we have
otherwise
for and . The core of the basic integer programming (10)
model that we propose for the uplink case is the classical unca-
pacitated facility location model
For the typical values and dB
used in the literature, we obtain an upper bound of 23.97 on
(3) the maximum number of connections that can be served by any
single BS. Thus, for each candidate site , the signal quality
subject to constraints can be rewritten as

(4) (11)

(5) The resulting basic model, which amounts to

(6)
(12)
The first term in the objective function corresponds to the
total installation cost. Since is proportional to the power
emitted from TP when assigned to BS , the second term subject to
aims at favoring assignments which require a smaller total
emission power. is a tradeoff parameter between these (13)
two objectives. Constraints (4) make sure that each TP is
assigned to a single BS. Constraints (5) impose that TPs are
only assigned to sites where a BS is installed. Note that by (14)
restricting the assignment variables to take on binary
values, it is required that in every feasible solution, all active (15)
connections must be assigned to a single BS.
To account for the power limit on the user terminals, we need (16)
to include, for each pair of TPs and candidate site ,
the following constraint: falls within the class of standard capacitated facility location
problems which have been extensively studied in the opera-
(7) tions research literature (see [29]). Note that to obtain a for-
mulation which does not involve the variables such that
where is the maximum emission power and , it suffices to proceed as follows. For each
corresponds to the emission power required by a mobile station TP , let denote the set of all candidate sites to which
in TP to guarantee the target received power at site . TP can be assigned to while respecting the power limit .
Note that if , the TP cannot be assigned to Symmetrically, for each candidate site , let denote the
candidate site due to power limits, and therefore, the variable set of all TPs that can be assigned to while respecting the
can be omitted from the model. Otherwise, constraint (7) is power limit. Then replace the summation over all candidate
implied by the corresponding constraint (5). sites in the second term of the objective function (12) and in
The fundamental aspect to be taken into account is the quality constraints (13) by a summation over , and the summation
of the signal received by each BS. As mentioned in Section II, over all TPs in constraints (15) by one over . Finally, sub-
the simplest way to express the quality constraints is either to stitute all constraints (14) by for all and .
neglect the intercell interference or to consider that it amounts to Unfortunately even medium-size instances of these nonpoly-
a given fraction of the intracell interference as given in formula nomial (NP)-hard capacitated location problems turn out to be
(2) for nonzero values of the parameter . For each connection, out of reach of state-of-the-art optimization algorithms. But,
the quality constraint can then be rewritten as even more importantly, the capacity constraints (15) do not cap-
ture the distinctive features of the W-CDMA technology and,
(8) as we shall see in Section V-A, in most cases the above basic
model provides meaningless solutions.
which is equivalent to
B. Enhanced Model With Power-Based PC
(9) To make the model more realistic, intercell interference needs
to be considered explicitly and independently from intracell in-
Considering a power-based PC mechanism, the power received terference. The use of pseudorandom spreading codes implies
at BS from each mobile station in a TP assigned to that, for a specific uplink connection between TP and BS ,
AMALDI et al.: PLANNING UMTS BS LOCATION: OPTIMIZATION MODELS WITH PC AND ALGORITHMS 943

there is no significant difference in the two types of interfer- Thus, the enhanced model, assuming a power-based PC mech-
ence. In other words, in the SIR formula (1) and for each anism, amounts to the following nonlinear mathematical pro-
connection, the quality constraint amounts to gram:
, where is the minimum
SIR before despreading.
(19)
In the presence of a power-based PC mechanism, the thermal
noise is omitted as in the other works focusing on this type
of PC mechanism (see, e.g., [20]) and for each candidate site subject to (20)–(23), shown at the bottom of the page, where, for
the signal quality constraint can be expressed as follows: each pair of TP in and candidate site in , constraints (21)
corresponds to the most stringent constraint among (5) and (7).
As mentioned in Section III-A for the basic model, a formulation
involving only the variables such that
can be obtained by using appropriate summation sets and .
(17) To tackle this problem with state-of-the-art mixed integer pro-
gramming (MIP) solvers like CPLEX 7.0 [30], constraints (18)
and, hence, (22) can be linearized as follows:
where is by definition the power received from each as-
signed TP. It is not difficult to verify that constraint (17) en-
forces that, if a BS is installed in site (i.e., ), the (24)
SIR value in must exceed the given . For any single
connection assigned to the BS located in site , the numerator for a large enough value of . Indeed, constraint (24) amounts
of the left-hand-side term is the power of the relevant signal re- to (18) when and, due to the value of , it is always
ceived in while the denominator amounts to the total interfer- satisfied when . In the linearized version of the enhanced
ence due to all other connections. Indeed, the double summation model, the nonlinear constraints (22) are replaced by the corre-
term expresses the total power received at site from all TPs sponding inequalities (24).
, from which the received power of the relevant It is worth emphasizing that constraints (22) and (24) are al-
signal is substracted. More specifically, for any TP , the quan- ways satisfied when , regardless of the way the TPs are
tity amounts to the emission power required at TP assigned to the BSs, and when , these constraints can be
to guarantee a received power value of at site . Note that, restated as
since , the only term of the inner summation (over
index ) that is nonzero corresponds to the site to which TP is (25)
actually assigned. Thus, if this site is denoted by , the outer
summation can be rewritten as
where is the power received at site from Here, we define for one of the TP assigned
TP and is the number of connections required from TP . to BS and for all other TPs assigned to BS . For
Clearly, the contribution to the outer summation of any TP as- all TPs assigned to other BSs, we have . This
signed to site amounts to since . is clearly in contrast with standard capacity constraints arising
Multiplying both sides of the inequality (17) by the denom- in classical capacitated facility location problems that can be
inator of its left-hand side and dividing the left and right sides expressed, when , as
by , we obtain for each candidate site the bilinear
constraint
(26)

(18) where the “demand” of “client” does not depend on the

“facility” to which “client” is assigned (there is no summa-

(20)

(21)

(22)

(23)
944 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO. 5, SEPTEMBER 2003

tion on the second subscript of the variables) and, for each where . Note that is the power of the
“facility” , the constraint only involves the “clients” assigned signal received at BS from TP . If TP is assigned to site
to it [29]. In the context of the UMTS BS location problem, it is (i.e., ), this third-order nonlinear constraint makes
as if each TP “absorbs” part of the capacity of every BS and sure that the SIR level of the corresponding connection is high
not only that of the BS it is assigned to. Moreover, the amount of enough. Unlike in the power-based PC case, in this context, the
capacity requested from BS depends on the “distance” (gain) thermal noise is usually included to guarantee convergence of
between TP and BS , as well as on the “distance” (gain) be- the closed-loop PC mechanism used in real systems [21].
tween TP and the BS to which it is assigned. Thus, the SIR-based PC model amounts to the following
By analyzing the quality (SIR) constraints (17), one can es- mixed mathematical program:
tablish a simple but important property of the underlying assign-
ment subproblem of the BS location problem [31].
Property: Given any set of active BSs and set of (28)
TPs, only assignments of TPs to “closest” active BSs need to be
considered, where “closeness” is meant in terms of the required
emission power. subject to (29)–(33), shown at the bottom of the page, with bi-
This derives from the fact that if any one of the TPs is not nary variables and as well as real variables . Note that,
assigned to one of its “closest” BSs, the SIR level at each active unlike in the power-based PC case, there is here a signal quality
BS can only increase when that TP is reassigned to a closer BS. constraint (31) for each pair of TP in and candidate site in
Thus, the UMTS BS location problem under consideration , and obviously only those with are relevant.
turns out to be substantially different from standard capacitated
facility location problems, where, for any given set of active D. Different Planning Objectives
BSs, the optimal assignment is not known a priori and needs Although the generic objective function proposed in (3) (and
to be determined. the corresponding (12), (19), and (28) in the three models) takes
into account the installation costs and the total emission power;
C. Model With SIR-Based PC the appropriate choice depends on the specific planning objec-
Assuming a more sophisticated SIR-based PC mechanism tives. According to the traffic requirements and distribution, the
yields a more involved mathematical programming model since number of candidate sites and their locations as well as the mo-
the emission power , required to connect each TP to the bile station maximum power, the signal quality constraints (15),
candidate site it is assigned to, must be considered as an explicit (22), and, respectively, (31) can be infeasible. In real-world in-
variable. Indeed, if TP is assigned to site is not taken to stances where traffic patterns are based on short-to-mid term
be equal to , so as to guarantee a given prescribed predictions, it is likely that the system will be required to serve
received power for every active connection. In the pres- all traffic. On the other hand, when traffic patterns are based on
ence of an SIR-based PC mechanism, the emission power values long-term predictions, a multiperiod network planning strategy
can be freely selected provided they do not exceed the max- can be adopted [32] and, in the first stages, one has to cope with
imum emission power and that the SIR level of each active solutions that do not cover all traffic. In this case, it is reasonable
connection is not lower than a prescribed . Besides the to aim also at maximizing the fraction of traffic that is actually
new power variables , the core model is then as in (3)–(6) served. This can be achieved by relaxing the assignment con-
except that in the second term of the objective function straints (13), (20), and, respectively, (29)
is replaced by the actual emission power . To account for the
power limit on the user terminals, constraints (7) are replaced
by . Moreover, for each pair of TP and (34)
candidate site , the signal quality constraint is now

so as to allow some TPs not to be assigned. The additional term

can then be included in the objective func-
(27) tion with an appropriate negative weight parameter.

(29)

(30)

(31)

(32)
(33)
AMALDI et al.: PLANNING UMTS BS LOCATION: OPTIMIZATION MODELS WITH PC AND ALGORITHMS 945

IV. HEURISTIC ALGORITHMS In the randomized reverse greedy algorithm (Remove), BSs
are removed iteratively starting from . Given the current
Since the UMTS BS location models proposed in the previous
section contain the uncapacitated facility location problem as a , for each candidate site , the above procedure is
applied to so as to obtain corresponding and vectors.
special case, they turn out to be NP-hard. To obtain good ap-
Then, the following utility function is evaluated:
proximate solutions within a reasonable amount of computing
time, we have first devised greedy and reverse greedy random-
ized procedures (see [33]) that construct a solution (i.e., a subset (36)
of candidate sites where to activate BSs) by iteratively adding
or, respectively, removing BSs from the current solution. TS al-
where is the sum, over all BSs that have so far been
gorithms have also been developed for the power-based as well
installed, of the number of additional connections they could
as SIR-based PC models.
service, namely, of , where is defined as the
We first describe the algorithms for the power-based PC
difference between the current SIR and . is the
model. From Section III-B, we know that in this case, assigning
corresponding weight. At each iteration one is randomly
each TP to a “closest” active BS yields the largest possible SIR
selected among the fraction of those that yield the largest
value for each BS. Moreover, in this setting all connections to
value of , where the parameter is . As for the
a given BS have the same SIR level, denoted by . Given
Add procedure, the Remove procedure stops when the removal
any set of active BSs, if all traffic requests can not be covered,
of another BS worsens the current solution value according to
the central procedure of our algorithms aims at satisfying the
utility function .
largest fraction of demands [see the relaxed constraints (34)].
Given the randomized nature of the Add and Remove pro-
This subproblem amounts to a special case of the multidimen-
cedures and their relatively low computational requirements, a
sional knapsack problem which is difficult (NP-hard) to solve
multistart strategy is adopted. Specifically, the greedy procedure
optimally [34]. Since in our context good solutions are needed
is run a predefined number of times and the best solution found
in a short amount of time, we proceed as follows.
during all the runs is returned as output.
Given a set of active BSs, each TP is first assigned to one
of its “closest” BSs in . Then, TPs assigned to active BSs
B. TS Algorithm
with are considered by nonincreasing value of
emission power and deleted one at a time until all TS is a metaheuristic that guides a local search procedure
active BSs have an SIR of at least . to explore the solution space of optimization problems beyond
Thus, TPs which cause higher interference are first deleted local optima. The idea is to use the history of the search process
while the number of BSs affected by the deletion is not consid- through an appropriate memory scheme to prevent cycling (run-
ered. ning into feasible solutions that have already been generated)
and to explore regions of the solution space that are promising in
A. Randomized Greedy Procedures terms of the objective function. The modern TS paradigm goes
back to the seminal work by Glover [35], [36] and is extensively
In the first randomized greedy algorithm (Add), BSs are
discussed in [37].
added iteratively to starting from . At each iteration
The basic ingredients of a general TS strategy can be de-
there is a current set of sites (possibly empty) in which
scribed as follows. Starting from an initial feasible solution ,
BSs have already been installed. For each remaining candidate
a set of neighboring solutions are generated by applying
site , the above assignment procedure is then applied
a set of possible “moves” to . Then the best solution in the
to so as to obtain a corresponding vector . The
“neighborhood” is selected as the next iterate even if
characteristic vector of subset is simply defined
it does not strictly improve the value of the objective function
as for all and , otherwise. For each
and the process is repeated to generate a sequence of solutions
of these potential solutions, specified by the set of active sites
.
and a corresponding pair , the following utility
In order to prevent cycling and to try to escape from local op-
function is evaluated:
tima a list of “tabu moves” is maintained. The purpose of this
list is to forbid the opposite move that has been made at a given
(35) step for a certain number of iterations. A move that is added to
the list remains tabu for a number of iterations that corresponds
where the first term amounts to the fraction of traffic that is cur- to the length of the list. According to the “aspiration criteria,”
rently covered and the second one expresses the total cost for tabu moves can be clearly made if they lead to an improved so-
installing the BSs in the sites selected so far. The tradeoff pa- lution. The best solution encountered is stored as the algorithm
rameter allows us to assign higher priority to max- proceeds and it is returned after a maximum number of itera-
imize the first objective than to minimize the second one. At tions . and are two parameters of the method.
each iteration, one is randomly selected among the Not surprisingly, the efficiency and performance of a TS proce-
fraction of those that yield the largest value of , where dure strongly depend on the way the moves are defined and how
is a given parameter . The procedure stops when well they exploit the actual structure of the problem at hand.
the addition of a new BS worsens the current solution value ac- As an initial solution, we consider the set of active BSs
cording to utility function . provided by the Add or the Remove procedures together with
946 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO. 5, SEPTEMBER 2003

an assignment of the TPs to their closest active BS, when- constraints (27) in the variables , a solution satisfies all of
ever they are served. Note that the current solution is in a sense them with equality. Assuming that TPs are assigned to closest
fully characterized by the set of active BSs. Besides the active BSs, the system can then be simplified by reducing the
add and remove moves used in the randomized greedy proce- number of variables as well as the number of equations. Indeed,
dures, we do also define swap moves that amount to installing for each given active BS , the equations corresponding to all
a new BS in one of the empty sites while deleting one of the TPs assigned to BS are equivalent when considered as func-
active BSs. Exploring all possible swap moves for any given tions of . Denoting the power received from any such TP
current solution would, of course, be very time consuming even by , the single equation associated to each in can
for small-size instances. But, due to the actual structure of the be rewritten as
problem, it is reasonable to focus on swaps between candidate
sites that are relatively “close” to each other. For each active BS (37)
, we initially consider the set of available sites
that have the largest propagation gains with respect to and that The size of the resulting system is, thus, equal to the number of
are in a sense the best candidates for a swap. Let be a param- active BSs which is at most and usually much smaller than the
eter such that . The swaps involving the number of TPs. This size reduction plays an important role in
best sites in are systematically evaluated, while those corre- making our algorithms applicable to the more accurate model.
sponding to the remaining available sites in are considered Given the assignment and the solution of the the above
with a given probability . system, the emission power at the TPs are derived by setting
The objective function used to guide our TS algorithm is the if and, otherwise, .
utility function given in (36). As to the implementation of the
tabu list, BSs that are installed (disactivated) cannot be disacti- V. COMPUTATIONAL RESULTS
vated (reinstalled) during iterations. Although this imposes
To evaluate the performance of the proposed algorithms, we
stronger restrictions on the search process than just avoiding
have considered synthetic but realistic uplink instances gener-
considering solutions that have already been generated, we have
ated by using Hatas propagation model [38]. For each instance,
observed that it provides better experimental results. Indeed, by
we consider a rectangular service area with dimensions ,
reducing the size of the neighborhood examined at each itera-
a number of candidate sites in which to locate omnidirec-
tion, one allows the algorithm to explore a larger region of the
tional antennas, and a number of TPs. Using a pseudorandom
solution space. The ability of a local search procedure to explore
number generator each candidate site and each TP is assigned
solution-space areas far away from each other is usually referred
a position with uniform distribution in the service area. The ma-
to as diversification [37].
trix is obtained by using Hata’s formulas which give the at-
In the experiments described in Section V, TS is applied in
tenuation (loss) in decibels due to signal propagation. In par-
two different settings. On the one hand, TS iterations are used
ticular, the attenuation for urban areas is given by
in a multistart Add or Remove context as a local search pro-
cedure to improve the solutions obtained with each one of the
ten runs of the greedy method. Specifically, 200 iterations of TS
are applied after each one of the ten runs of Add or Remove and
(38)
the best solution encountered is returned. On the other hand, the
same total number of iterations of TS, namely 2000, are carried where is the signal frequency in megahertz, and are
out starting from a single initial solution provided by Add or Re- the heights of the base and the mobile station in meters, and is
move. Note that the advantage of Remove to generate a starting the distance in kilometers, while the formula for rural areas is
solution is that it allows for automatically checking whether all
traffic demands can be satisfied. (39)
Clearly , where denotes the distance
C. Extension to SIR-Based PC Model between TP and candidate site .
Although in the SIR-based case assigning TPs to closest BSs We considered three families of uplink instances with a ser-
is no longer guaranteed to yield the best possible SIR values, we vice area of 400 400 m, 1 1 km, and 1.5 1.5 km, respec-
make this simplifying assumption which reflects a conservative tively. Different instances of these families are obtained using
point of view in the sense that there might exist assignments of the pseudorandom generator. Two gain matrices are consid-
TPs to active BSs involving a smaller number of active BSs or a ered for each configuration using the urban and the rural Hata’s
lower total installation cost. Note that, from a planning point of formulas with
view, delving into such details does not seem appropriate since
MHz (40)
the actual assignments used during operation are dynamically
determined by the access procedure. Small-size instances are characterized by a service area of
Given a current set of active BSs and an assignment 400 400 m, candidate sites, TPs, and
, to compute the emitted powers it would be necessary to for all TPs . Medium-size instances are characterized by a
solve the system composed of constraints (27) for each active service area of 1 1 km, , and uniformly
connection between TP and BS together subject to the bounds distributed in for all . Large-size urban (LU)
on the maximum power. Since the resulting system contains instances are characterized by a service area of 1.5 1.5 km,
AMALDI et al.: PLANNING UMTS BS LOCATION: OPTIMIZATION MODELS WITH PC AND ALGORITHMS 947

TABLE I
RESULTS OBTAINED WITH ADD, REMOVE ( =  = 0:3), MULTISTART TS AND SINGLE-RUN TS FOR SMALL-SU AND RURAL (SR)
INSTANCES WITH m = 22; n = 95; u = 1. FOR EACH ALGORITHM, FROM LEFT TO RIGHT: MINIMUM NUMBER OF BSs INSTALLED,
THE AVERAGE NUMBER AND THE STANDARD DEVIATION OVER 50 RUNS

, and uniformly distributed in for

all . Finally, all instances have uniform installation costs,
namely for all .
The remaining parameters have been selected as fol-
lows: and (so that ),
dB, dBm, dBm. In
all the experiments reported here, and ,
which imply that in the utility functions (35) and (36), the first
term has higher priority than the second term and that in (36)
the second term has higher priority than the third one.

A. Shortcomings of the Model With Simplified SIR Formula

The first computational effort aimed at comparing the sim-
plified power-based PC model (i.e., the basic model (12)–(16)
with only the relevant variables ) with the enhanced power-
based PC model (19)–(23) in which intercell interference is
explicitly considered. Setting and the other parame-
ters as mentioned above, in the simplified model the maximum
number of users per BS, is bounded above by 23.97 and, hence, (a)
it is at most 23. The resulting models for the small instances
have been solved to optimality by using CPLEX 7.0 MIP solver
[30]. In all cases, the simplified model activates 5 BSs (which
corresponds to the lower bound, since is about 4.1) while
the optimal solution of the enhanced model always activates
just four BSs.
To evaluate the quality of the solutions yielded by the sim-
plified model, we consider the active BSs and the assignments
of TPs specified by the optimal solution provided by CPLEX,
and we compute the SIR value of each BS using a power-based
PC mechanism as well as the power received by each BS using
an SIR-based PC mechanism. Typical results obtained for one of
the small instances of Table I [instance small-size urban (SU-3)]
are reported in Fig. 1. SIR values and received powers are given
for each of the five active BSs. Note that in the power-based
PC setting, the power received is constant, while in the SIR-
based setting the SIR is constant. In the power-based setting,
SIR values often exceed the minimum level required to guar-
antee signal quality, while in the SIR-based setting, the SIR (b)
values are set to and the actual received powers
associated to a number of connections can be lower than . Fig. 1. Quality of the optimal solution (including five BSs) of the simplified
model with f = 0:4 for instance SU-3 of Table I. (a) SIR values obtained with
For a fair comparison between the solutions provided by the the power-based PC setting. (b) Received powers obtained with the SIR-based
simplified and enhanced models, we changed the value of pa- PC setting.
948 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO. 5, SEPTEMBER 2003

(SR). For the same instances, the optimal solutions, involving

four BSs in all cases, have been obtained by using CPLEX 7.0.
Although Add and Remove are heuristics with no guarantee to
provide an optimal solution, they do so in half of these cases
and the number of BSs installed never exceeds the minimum
number by more than one. It is worth noting that the computa-
tion time required by Add or Remove to find a close-to-optimal
solution for a single instance was less than 5 s on a Pentium
III/700-MHz personal computer, while CPLEX 7.0 MIP solver
required 5–20 min to find an optimal solution on an about
twice as fast computer. As a matter of fact, solving even such
small instances using a state-of-the-art MIP solver turns out to
be a challenging task due to the very delicate choice of the
value . If the parameter is too small, then some SIR
constraints that should be omitted will not be disactivated and,
therefore, the resulting solutions contain a larger number of
BSs than optimal solutions of the actual problem. On the other
hand, for too large values of , one runs into numerical prob-
lems related to machine precision which tend to override some
Fig. 2. Quality of the optimal solution (including four BSs) of the simplified SIR constraints and, hence, to yield solutions with a too small
model with f = 0:35 for instance SU-3: SIR values obtained with the
power-based PC setting. number of BSs.
In Table I, multistart TS consists of 50 runs of Add (A) or
Remove (R) followed by 200 iterations of TS while single-run
rameter (setting it to 0.35) so that also the simplified model
TS consists of Remove followed by 2000 iterations of TS. For
returns solutions with only four active BSs. The corresponding
these small instances, a tabu list of length is used,
results obtained for the same instance of Fig. 1 are reported in
and . As far as the best solutions
Fig. 2. Notice that in the power-based PC setting, the SIR values
are concerned, for these small instances the Remove procedure
drop far below any acceptable value, while in the SIR-based PC
provides as good solutions as the TS variants. However, in mul-
setting, it has not even been possible to find a feasible value for
tistart TS and single-run TS, the average quality of the solutions
the received powers, meaning that the PC mechanism does not
is better and the standard deviations are lower in all but one case.
converge to a stable solution.
Due to this more robust behavior, a single run of multistart TS
Interesting insight on the inadequacy of the location model
would suffice to yield the same best solutions for eight out of
with the simplified SIR constraints is provided by the distribu- the ten instances.
tion of the number of connections assigned to each active BS in
Table II reports the results obtained with Add, Remove (both
the solutions of the other more sophisticated models. A typical
with 50 runs), multistart TS (Add and Remove), and single-run
example for a medium-size instance (instance MU-3) is shown TS for ten medium-size instances. The number of TS iterations
in Fig. 3. In the the case of SIR-based PC model, a substan- for multistart and single-run TS are as for small-size instances.
tial fraction of BSs (here more than 37%) is assigned a number For medium-size instances, a tabu list of length is used,
of connections that is larger than 23, which is the strict upper and . The solutions found pro-
bound that would be imposed by the simplified power-based vided in all but one cases full traffic coverage. The number of
PC model. Solutions of the enhanced power-based PC model BSs installed by our Add and Remove randomized procedures
do also exhibit similar distributions. differ at most by three. None of them consistently outperforms
All our experiments show that the model with the simpli- the other one. However, the standard deviation of the number
fied SIR formula is not suitable for locating BSs in UMTS net- of BSs in the solutions given by Remove (over the 50 runs) is
works since it fails to capture some fundamental characteristics usually higher than that of the solutions provided by Add. The
of third-generation systems. solutions provided by the TS procedures require a few BSs less
than Add and Remove. Although there is no significant differ-
B. Comparison of Heuristic Algorithms for Power-Based PC ence among the three TS procedures, single-run TS provides in
Model all but one cases the best solution and it always does so at lower
In this subsection, the results obtained with the three algo- computational cost.
rithms for the enhanced power-based PC model (19)–(23) with The 50 runs of Add and Remove take in average 10 and, re-
no thermal noise are reported and discussed. spectively, 30 s for the small-size instances, and 1:50 and, re-
Results for the small-size instances obtained with the ran- spectively, 1:20 h for the medium-size instances. For large-size
domized Add and Remove procedures over instances more than 13 CPU hours are needed for Add and ap-
50 runs are reported in Table I. The solutions found always proximately 7 h for Remove. A single-run TS lasts in average
satisfy all 95 requested connections. Out of the ten instances 1:20 h for medium-size instances and 6 h for large-size ones.
mentioned in Table I, five have been generated using the Hata For solution quality comparison purposes, multistart TS was run
formula for urban areas (SU) and five using that for rural areas with the same total number of TS iterations as single-run TS and
AMALDI et al.: PLANNING UMTS BS LOCATION: OPTIMIZATION MODELS WITH PC AND ALGORITHMS 949

Fig. 3. Distribution of the number of TPs assigned to the various BSs for the medium-size instance MU-3.

TABLE II
RESULTS OBTAINED WITH THE ADD, REMOVE ( =  = 0:3), MULTISTART TS AND SINGLE-RUN TS FOR MEDIUM-SIZE URBAN (MU) AND RURAL (MR)
INSTANCES WITH m = 120; n = 400, AND u UNIFORMLY DISTRIBUTED IN f1; 2; 3g. FOR EACH ALGORITHM, FROM LEFT TO RIGHT: MINIMUM NUMBER OF
BSs INSTALLED, THE AVERAGE NUMBER, AND THE STANDARD DEVIATION OVER 50 RUNS. NOT ALL THE TRAFFIC IS COVERED

TABLE III
RESULTS OBTAINED WITH ADD AND REMOVE ( =  = 0:3) FOR LU INSTANCES WITH m = 200; n = 750; u UNIFORMLY DISTRIBUTED IN f1; 2g. FROM
LEFT TO RIGHT: FRACTION OF TRAFFIC COVERED, MINIMUM NUMBER OF BSs INSTALLED, AVERAGE NUMBER, AND STANDARD DEVIATION OVER TEN RUNS

this obviously led to higher (approximately twice as long) com- cities. The results are reported in Tables III and IV. Unlike
puting times. for the previous classes of instances, the traffic demand is
As shown in Table II, multistart TS (ten runs) and single-run not always satisfied. It is worth noting that Remove provides
TS yield for all instances better solutions than the best ones solutions with much higher average number of active BSs even
obtained with Add and Remove. In many cases, these solutions though the best solution found is worse than the best one yield
are obtained within less than 500 local search iterations. by Add only for two out of the five instances. In fact, the best
We have also applied Add and Remove (ten runs), multistart solutions found with Remove turn out to be better for instances
TS (ten runs with 200 iterations of local search each) as well LU-3 as well as LU-5 and equivalent for LU-1. Moreover, for
as single-run TS (1000 iterations) to five LU instances. This instance LU-2 the best solution provided by Remove contains
choice of parameter values, with 1500 active connections in the an additional BS but it covers the whole traffic. The advantage
average, is quite realistic for UMTS setting in medium-to-large of the Remove scheme to obtain the initial solutions is that it
950 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO. 5, SEPTEMBER 2003

TABLE IV
RESULTS FOR LU INSTANCES WITH m
= 200; n = 750; u UNIFORMLY DISTRIBUTED IN f1; 2g. FROM LEFT TO RIGHT: FRACTION OF TRAFFIC COVERED,
MINIMUM NUMBER OF BSs INSTALLED, AVERAGE NUMBER, AND STANDARD DEVIATION OVER TEN RUNS

naturally allows for testing whether all traffic demands can be TABLE V
COMPARISON BETWEEN MODELS WITH SIR-BASED AND POWER-BASED PC:
satisfied. NUMBER OF INSTALLED BSs WITH TABU SEARCH ALGORITHMS
According to Table IV, multistart TS and single-run TS al-
ways yield solutions of better quality than the best ones provided
by Add and Remove. For these large-size instances, a tabu list of
length is used, , and .
Note that for all five instances the improvement in terms of BSs
installed is substantial.

C. Comparison Between Models With Power-Based and

SIR-Based PC
We now discuss the results provided by the model with SIR-
based PC (28)–(33) pointing out the differences with respect to
those from the model with power-based PC (19)–(23). To ob-
tain meaningful solutions with the SIR-based model, a nonzero
thermal noise must be considered. For comparison purposes,
the same value of dB is also used in the model with
power-based PC.
Multistart TS is applied with ten runs and single-run TS with
2000 iterations. To maintain the computational times at a rea-
sonable level, TPs have been assigned to closest BSs in terms of
emitted powers, even though better performance (and possibly
also lower costs) may be attained with different types of assign-
ments. At each iteration, once the current solution is fully de-
termined (i.e., a TP-BS assignment is derived for the current set
of active BSs), the received powers are computed by solving the
related linear system (37). This constitutes the heavy part of the
computation. Tests have been conducted on the small-size in-
stances and both algorithms provided solutions with four BSs,
as in the enhanced power-based PC case. In order to empha-
size the differences, experiments were also carried out with the
medium-size instances. For each of the medium-size instances,
multistart TS took about 15 h while single-run TS took about
9 h. These computing times have to be compared to the 2:30 Fig. 4. Measured SIR values with the enhanced power-based PC model for
instance MU-3.
and 1:30 h, respectively, for the same type of algorithms ap-
plied to the enhanced power-based PC. This clearly indicates the
considerable additional computational load required to compute all BSs they are not assigned to. Thus, the system can support
the power values at each iteration. Table V shows the numer- more connections per BSs and, in practice, the capacity of the
ical results for the ten medium-size instances. For multistart TS overall network is better exploited.
the minimum number of installed BSs is reported together with The above observations are also confirmed by comparing the
the average and the standard deviation (over ten runs), while for SIR values at each BS and the received powers for each connec-
single-run TS the best solution is given. tion. Fig. 4 reports the SIR values measured in each active BS
Comparing the number of active BSs yielded by the enhanced by using the enhanced power-based PC model. Notice that only
power-based PC model with that obtained by the SIR-based a few BSs have an SIR equal to the required of 6 dB,
PC model, we observe that the latter one allows for a saving and for many BSs the service quality is far above the required
of at least six BSs. This is due to the fact that, since the mo- level. Thus, the emitted powers are higher than needed and as
bile stations can emit lower powers with respect to those in the a result the interference levels are higher and the scarce radio
power-based PC case, they generate lower interference toward resources are not used as efficiently as they could.
AMALDI et al.: PLANNING UMTS BS LOCATION: OPTIMIZATION MODELS WITH PC AND ALGORITHMS 951

VI. CONCLUDING REMARKS [8] A. Molina, G. E. Athanasiadou, and A. R. Nix, “The authomatic location
of base stations for optimized cellular coverage: A new combinatorial
The main features characterizing the important problem of approach,” Proc. IEEE VTC’99, pp. 606–610, May 1999.
planning UMTS networks using the W-CDMA air interface [9] Q. Hao, B.-H. Soong, E. Gunawan, J.-T. Ong, C.-B. Soh, and Z. Li, “A
low-cost cellular mobile communication system: A hierarchical opti-
have been discussed. Focusing on the uplink direction, we mization network resource planning approach,” IEEE J. Select. Areas
have investigated discrete optimization models for the UMTS Commun., vol. 15, pp. 1315–1326, Sept. 1997.
BS location problem that capture at different levels of detail [10] D. Parsons, The Mobile Radio Propagation Channel. New York:
Wiley, 1996.
the peculiarities of the signal quality constraints and the PC [11] W. K. Hale, “Frequency: Theory and applications,” Proc. IEEE, vol. 30,
mechanism for W-CDMA. Standard capacitated location pp. 1497–1514, 1980.
models being inappropriate, we have proposed an enhanced [12] A. Capone and M. Trubian, “Channel assignment problem in cellular
systems: A new model and tabu search algorithm,” IEEE Trans. Veh.
power-based PC model as well as a more accurate SIR-based Technol., vol. 48, pp. 1252–1260, July 1999.
PC one. [13] K. S. Gilhousen, I. M. Jacobs, R. Padovani, A. J. Viterbi, L. A. Weaver,
Since solving even medium-size instances of these NP-hard and C. E. Wheatley, “On the capacity of a cellular CDMA system,” IEEE
Trans. Veh. Technol., vol. 40, pp. 303–312, May 1991.
problems is beyond the reach of state-of-the-art commercial [14] D. Kim and D. G. Jeong, “Capacity unbalance between uplink and down-
optimization solvers, we have developed three heuristics for link in spectrally overlaid narrow-band and wide-band CDMA mobile
the power-based PC model. Our randomized greedy and re- systems,” IEEE Trans. Veh. Technol., vol. 49, pp. 1086–1093, July 2000.
[15] E. Amaldi, A. Capone, and F. Malucelli, “Base station configuration and
verse greedy procedures provide, in a reasonable amount of location problems in UMTS networks,” in Proc. 9th Int. Conf. Telecom-
time, good approximate solutions for medium-to-large size real- munication Systems, Modeling, and Analysis, 2001, pp. 341–348.
istic instances generated by using classical propagation models. [16] , “Optimizing base station siting in UMTS networks,” Proc. IEEE
VTC Spring 2001, vol. 4, pp. 2828–2832, May 2001.
A TS algorithm, which can be applied either in a multistart or [17] , “Improved models and algorithms for UMTS radio planning,”
single-run setting, allows us to further improve the approximate Proc. IEEE VTC Fall 2001, vol. 2, pp. 920–924, Oct. 2001.
solutions obtained with these greedy procedures. [18] A. Samukic, “UMTS universal mobile telecommunications system:
Development of standards for the third generation,” IEEE Trans. Veh.
The three above algorithms have also been extended to the Technol., vol. 47, pp. 1099–1104, Nov. 1998.
SIR-based model by assuming that TPs are assigned to a closest [19] H. Holma and A. Toskala, WCDMA for UMTS. New York: Wiley,
active BS. From the planning point of view, this is just a con- 2000.
[20] A. M. Viterbi and A. J. Viterbi, “Erlang capacity of a power controlled
servative assumption in the sense that there might exist solu- CDMA system,” IEEE J. Select. Areas Commun., vol. 11, pp. 892–900,
tions with less natural assignments but better objective function Aug. 1993.
values. [21] R. D. Yates, “A framework for uplink power control in cellular radio
systems,” IEEE J. Select. Areas Commun., vol. 13, pp. 1341–1347, Sept.
Our experimental results show that the enhanced power- 1995.
based PC model yields interesting solutions but those obtained [22] K. Tutschku, N. Gerlich, and P. Tran-Gia, “An integrated approach to
cellular network planning,” in Proc. 7th Int. Network Planning Sympo-
with the SIR-based model use in a more efficient way the scarce sium—Networks ’96, Sydney, Australia, Nov. 1996.
radio resources and the computed SIR values are closer to the [23] A. Molina, G. E. Athanasiadou, and A. R. Nix, “Cellular network ca-
actual values in real systems. pacity planning using the combination algorithm for total optimization,”
Proc. IEEE VTC 2000, pp. 2512–2516, May 2000.
[24] , “Optimized base station location algorithm for next generation
ACKNOWLEDGMENT microcellular networks,” Electron. Lett., vol. 36, no. 7, pp. 668–669,
2000.
The authors would like to thank M. Fumagalli and S. Pezzoli [25] P. Calégari, F. Guidec, P. Kuonen, and D. Wagner, “Genetic approach to
for their significant help in the long and tedious experimental radio network oprimization for mobile systems,” Proc. IEEE VTC ’97,
phase. Moreover, they are grateful to the anonymous referees pp. 755–759, May 1997.
[26] C. Y. Lee and H. G. Kang, “Cell planning with capacity expansion in
for helpful comments and suggestions. mobile communications: A tabu search approach,” IEEE Trans. Veh.
Technol., vol. 49, pp. 1678–1690, Sept. 2000.
[27] B. Chamaret, S. Josselin, P. Kuonen, M. Pizarroso, B. Salas-Manzanedo,
REFERENCES S. Ubeda, and D. Wagner, “Radio network optimization with maximum
[1] J. C. S. Cheung, M. A. Beach, and J. P. McGeehan, “Network planning independent set search,” Proc. IEEE VTC ’97, pp. 770–774, May 1997.
for third-generation mobile radio systems,” IEEE Commun. Mag., vol. [28] M. Galota, C. Glasser, S. Reith, and H. Vollmer, “A polynomial-time
32, pp. 54–59, Nov. 1994. approximation scheme for base station positioning in UMTS networks,”
[2] R. Menolascino, M. Pizarroso, C. Lepschy, and B. Salas, “Third genera- in Proc. 5th Int. Workshop Discrete Algorithms and Methods for Mobile
tion mobile systems planning issues,” Proc. IEEE VTC’98, pp. 830–834, Computing and Communications (DIAL-M), 2001, pp. 52–59. ACM.
May 1998. [29] M. Labbé and F. V. Louveaux, “Location problems,” in Annotated Bibli-
[3] E. Berruto, M. Gudmundson, R. Menolascino, W. Mohr, and M. ographies in Combinatorial Optimization, M. Dell’Amico, F. Maffioli,
Pizarroso, “Research activities on UMTS radio interface, network and S. Martello, Eds. New York: Wiley, 1997, ch. 16.
architectures, and planning,” IEEE Commun. Mag., vol. 36, pp. 82–95, [30] ILOG CPLEX [Online]. Available: http://www.ilog.com/prod-
Feb. 1998. ucts/cplex/
[4] M. Naghshineh and I. Katzela, “Channel assignment schemes for [31] E. Amaldi, A. Capone, and F. Malucelli, “Discrete models and algo-
cellular mobile telecommunication systems: A comprehensive survey,” rithms for the capacitated location problem arising in UMTS network
IEEE Pers. Commun., vol. 3, pp. 10–31, June 1996. planning,” in Proc. 5th Int. Workshop Discrete Algorithms and Methods
[5] H. D. Sherali, M. Pendyala, and T. Rappaport, “Optimal location of for Mobile Computing and Communications (DIAL-M), 2001, pp. 1–8.
transmitters for micro-cellular radio communication system design,” ACM.
IEEE J. Select. Areas Commun., vol. 14, pp. 662–673, May 1996. [32] P. Reininger, S. Iksal, A. Caminada, and J. Korczak, “Multi-stage opti-
[6] K. Tutschku, “Demand-based radio network planning of cellular mo- mization for mobile radio network planning,” Proc. IEEE VTC ’99, pp.
bile communication systems,” Proc. IEEE INFOCOM’98, vol. 3, pp. 2034–2038, May 1999.
1054–1061, Apr. 1998. [33] T. A. Feo and M. G. C. Resende, “Greedy randomized adaptive search
[7] R. Mathar and T. Niessen, “Optimum positioning of base stations for procedures,” J. Global Optimization, vol. 6, no. 2, pp. 109–133, 1995.
cellular radio networks,” Wireless Networks, vol. 6, no. 6, pp. 421–428, [34] S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer
2000. Implementations. New York: Wiley, 1990.
952 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO. 5, SEPTEMBER 2003

[35] F. Glover, “Tabu search—Part I,” ORSA J. Computing, vol. 1, no. 3, pp. Antonio Capone (S’95–M’98) received the Laurea
190–206, 1989. degree (M.S. equivalent) and the Ph.D. degree in
[36] , “Tabu search—Part II,” ORSA J. Computing, vol. 2, no. 1, pp. telecommunication engineering from the Politecnico
4–32, 1990. di Milano, Milan, Italy, in 1994 and 1998, respec-
[37] F. Glover and M. Laguna, Tabu Search. Norwell, MA: Kluwer, 1997. tively.
[38] M. Hata, “Empirical formula for propagation loss in land mobile radio From November 1997 to June 1998, he was an Ad-
service,” IEEE Trans. Veh. Technol., vol. VT-29, pp. 317–325, Aug. junct Professor at the University of Lecce. He is now
1980. an Assistant Professor at the Dipartimento di Elet-
[39] E. Amaldi, A. Capone, F. Malucelli, and F. Signori, “Optimization tronica e Informazione, Politecnico di Milano, Milan,
models and algorithms for downlink UMTS radio planning,” in Proc. Italy. His current research activities mainly include
IEEE Wireless Communications and Networking Conf., vol. 2, Mar. packet access in wireless cellular network, flow con-
2003, pp. 827–831. trol, and quality of service issues of IP networks, optimization techniques for
telecommunication systems.
Dr. Capone is a Member of the IEEE Communications and Vehicular Tech-
nology Societies.
Edoardo Amaldi received the Diploma in mathe-
matical engineering and the Doctorat ès Sciences
(Ph.D.), from the Swiss Federal Institute of Tech-
nology, in 1988 and 1994, respectively.
After one year in the Computational and Neural Federico Malucelli received the Laurea degree (M.S.
Systems Program, California Institute of Technology, equivalent) and the Ph.D. degree in computer science,
he returned to the Swiss Federal Institute of Tech- from the Universit à di Pisa, Italy, in 1988 and 1993,
nology as a Research Assistant. He then joined the respectively.
School of Operations Research and Industrial Engi- He is currently a Full Professor of Operations
neering, Cornell Univeristy, where he did research Research at the Politecnico di Milano, Milan,
and taught. Since 1998, he has been with the Dipar- Italy. His main contributions in the area are the
timento di Elettronica e Informazione, Politecnico di Milano, Italy, where he application of combinatorial optimization models
is currently an Associate Professor. His main research interests are in discrete and algorithms to solve practical problems arising
optimization and computational complexity with applications in fields such as in the field of telecommunications. He has authored
image and signal processing, telecommunications, and computational finance. about 30 scientific papers.