Multi-Oj Ective Strategies For Automatic Cell Planning of UMTS Networks
Multi-Oj Ective Strategies For Automatic Cell Planning of UMTS Networks
Multi-Oj Ective Strategies For Automatic Cell Planning of UMTS Networks
of UMTS Networks
S . Ben Jamaa, 2. Altman, J.M. Picard and B. FourestiC
France Telecom R&D, DMR-IIM
38-40 rue du General Leclerc
92794 Issy les Moulineaux Cedex 9, France
e-mail: [email protected]
Abstract- Automatic cell planning aims at optimizing coverage, population of networks towards better solutions through
capacity and quality of service by automatically adjusting repetitive applications of genetic operators till high
antenna parameters and common channel powers. I n certain performance networks are obtained.
cases coverage and capacity can he antagonistic criteria, and
their aggregation in a single cost function may turn out to be The purpose of this paper is to present advanced features of
inefficient. Such a scenario may occur when the environment is the ACP aiming at simultaneously optimizing capacity and
hilly, when certain sites are unavailable, and in general, when coverage, as well as quality of service, macrodiversity and cost.
coverage objectives are difficult to achieve utilizing a manual Coverage and capacity can be antagonistic criteria that cannot
design process. To tackle this difficult and challenging problem, a be optimized in a satisfactory manner when aggregated in a
multi-objective Genetic Algorithm has been developed and single objective function. This difficult and challenging
utilized as the optimization engine of the automatic cell planner problem calls for multi-objective optimization techniques,
(ACP). An example of network optimization in a heterogeneous which are investigated in this paper.
and hilly environment is presented and the robustness of the
optimization is illustrated. To analyze the robustness of a solution produced by the
ACP, its performance is assessed utilizing simulated indicators
Keywords- Malt-ohjective optimization, Genetic algorithms, that can be obtained by processing counters from the real
Automatic cellplanning, CapaciQ, Coverage, UMTS. network. In the present work, a dynamic simulator [7] is
utilized to simulate blocking and dropping rates for both the
I. INTRODUCTION initial and the optimized networks. The notable improvement
obtained for the optimized network illustrates the efficiency
High quality network planning is one of the challenging and robustness of the optimization process.
tasks for UMTS mobile operators that requires deep
understanding of WCDMA mechanisms. Base stations in the
network are often electromagnetically coupled and the 11. ACP DESCRIPTION
modification of parameters (e.g. antenna tilt, common channel The general structure of the ACP is described in Figure 1. It
power) in one station can impact performance of other stations. comprises two main blocks: An optimization engine based on a
This feature of WCDMA networks is due to the sharing of multi-objective GA (see $3) and an evaluation engine. The
bandwidth resources between users, and renders planning and optimization engine guides the optimization process. It
quality design complex [l]. From operator point of view, the explores the solution space by iteratively selecting a population
performance and profitability directly depend on the capability of networks for evaluation, each of which is defined by the set
of the network planner to optimally parameterize the network. of parameters to be optimized.
To alleviate the burden of lengthy manual design processes,
and to improve manually designed networks, a UMTS
Automatic Cell Planner (ACP), has been developed in France
Telecom R&D [2, 31. This ACP automatically designs 3G
networks by adjusting antenna parameters and common
channel transmitted powers to optimize the network
performance in terms of capacity, quality of service (QoS),
service continuity and cost, for a target coverage fixed by the
designer. These objectives are aggregated and constitute the
objective function for the optimizer. The ACP is orchestrated
by a Genetic Algorithm (GA) [4], which simultaneously
processes a population of networks, each of which is defined
by a set of parameters to be optimized. The GA uses the Figure I . Block dia- ofthe multi-objective ACP.
Darwinian evolution as an optimization model that guides a
The evaluation engine performs an accurate evaluation of A . Special genetic operators
the network. It utilizes the traffic distribution introduced into Specific operators and data structures are needed to
the ACP (using forecasts or measurements). To achieve precise efficiently implement the Multi-Objective GA (MOGA), some
evaluation of the network QoS, the evaluation module of which are proposed in [5].
accurately computes basic UMTS quantities such as powers,
loads and interferences. It is noted that the large number of I ) Seleciion operator
parameters to optimize (which typically vanes between several Along with the convergence to the Pareto optimal set, the
hundreds and several thousands), and the inter-dependency of MOGA aims at maintaining high diversity of non-dominated
these parameters make the design process a complex solutions, namely selecting solutions which are well distributed
optimization problem that belongs to the class of NP-hard along the Pareto front. The selection operator combines a non-
problems. Special algorithms have been developed that allow dominated sorting (as in NSGA [ 6 ] )with a crowding density
an ultra-rapid evaluation of the network. Typically, the estimation (as in NSGA-I1 [ 5 ] ) . Then every individual is
evaluation time of a network with few hundreds of sectors is of assigned a fitness value and the selection is carried out using a
the order of a second. roulette wheel (see Figure 2).
For each network in the population, the evaluation engine a) Fitness assignment
computes a set of quality criteria which are introduced into the The fitness assignment is carried out in two steps. First, a
GA and guide it in the search space towards better solutions. given fitness value is assigned to each non-dominated solution
The multi-objective optimization methodology is described constituting the non-dominated front. To preserve diversity, the
presently. fitness of each of these solutions is updated by adding a
measure of its density on the current non-dominated front
11. OPTIMIZATION
MODEL (using the crowding operator defined below). Solutions situated
It is assumed without loss of generality that the problem is on the Pareto front are then removed and the assignment
a minimization problem. Consider n objectives, 5, i=l, ...,n, procedure is applied to the solutions constituting the next front.
each of which is a function of a set of parameters given by the Iteratively, a fitness value is assigned to all the population
vector x. The multi-objective optimization is formulated as abiding by the following rule: The fitness of a solution of a
follows: given front is less than the smallest fitness value assigned to a
solution in the preceding front.
minimise y = f(x)= &(X),J~(X),...,/~(X)) ,-___________________--------------
subject to
x = (XI .x* ,..., x,). x I lastfront Second fmnt Best h n t
{Y =Cv,.y* ....Y")€ Y
In the present case, the objectives can stand for coverage,
capacity, cost and other quality criteria. The vector x denotes 0
8
...
the parameters which are set for possible optimization, (i.e.
antenna parameters and common channel powers), and
represents a given network; X stands for the parameter space; y
denotes the objective vector and Y the objective space.
The set of optimal solutions of a multi-objective
optimization problem is the set of solutions for which the
objective vectors cannot be improved in any dimension without
degradation in another dimension. These solutions are known
as non-dominated or Pareto optimal solutions. Next the Pareto
dominance is defined for any two vectors X andX'. A
parameter vector X dominates I' if and only if
2421
2) Archiving: probability of coverage in both links as well as that of
To keep track of the best solutions, an archive is formed availability of resource. One can observe that the optimization
with the solutions of the non-dominated front corresponding to process has considerably reduced the area with low access
all past generations. In each iteration, the archive is updated to probability.
include possible solutions from the present population. If the 30%
total number of solutions exceeds the maximum archive size,
the crowding procedure can be used to select the solutions to be
kept.
111. RESULTS
In this section, an example of network optimization using
the multi-objective ACP is described. The network comprises
181 sectors: 108 sectors in a dense urban environment and 73
in an urban and hilly environment. The initial network
parameters have been set uniformly. Results of the
optimization are described below. In Figure 3, all the r:@re 3 . DL coverage results for the initial (grey) and optimized (white)
nrhvnrlrr
individuals generated during the optimization process are
drawn in the objective space (grey points). One can notice a I 7%. 4
considerable improvement in both capacity and coverage
criteria for all individuals in the final archive (black stars).
I:@re 4. UL coverage results for the initial (grey) and optimized (white)
networks.
Figure 2. Solutions generated by the MOGA (in grey), including the initial
and final solutions stored in the archive (in black).
The corresponding legend is depicted in Figure 8. These Figure 6. Access probability in the optimized network.
figures are of particular interest since they combine the
100%
98%
e
P-,, for 144 kbps indoor 96%
94%
92%
Paccess< 0.5
figure 13. Average dropping rate for the fin150 stations in decreasing order,
for the initial (black) and optimized (grey) networks.
IV. CONCLUSIONS
A multi-objective automatic cell planner (ACP) has been
described for combined coverage and capacity optimization of
UMTS networks. It optimizes network performance by
adjusting antenna parameters and common channel powers.
The ACP is orchestrated by a Multi-Objective Genetic
Algorithm (MOGA) that processes separately the different
objectives utilizing specialized genetic operators.
A detailed example of a network optimization in a
heterogeneous environment and in a hilly landscape has been
presented. Considerable improvement in the network
performance in terms of both coverage and capacity has been
achieved, illustrating the effectiveness of the multi-objective
optimization technique. The performance of the solution with
respect to indicators which are not utilized in the optimization
process, and that can he obtained by processing measured
counters illustrates the robustness of the optimization process.
REFERENCES
[I] H. Holma, and A. Toskala, WCDMA for UMTS, Radio Access for
Third Generation Mobile Communications, John Wiley & Sons La,
England, 2000.