Multi-Oj Ective Strategies For Automatic Cell Planning of UMTS Networks

Download as pdf or txt
Download as pdf or txt
You are on page 1of 5

Multi-Oj ective Strategies for Automatic Cell Planning

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

v ic { 1,...,n }, f,(x)< XI) Figure I. Selection operator


and
3j s { I ,..., n},rj(x)<fj(x') b) Crowding:
A measure of distance for the solutions on the non-
A solution is said to be non-dominated if there exists no dominated front is defined, denoted as crowding distance [5].
solution that dominates it. The set of parameter vectors that are For any solution i on a non-dominated front, a cuboid is
non-dominated within the entire search space constitute the defined, having the i-1 and i+l nearest neighbors on the current
Pareto optimal set or the Pareto optimal front. non-dominated front as vertices. The average side length of the
cuboid is used to measure the crowding distance required for
the fitness assignment procedure.

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).

Results for Down Link (DL) and Up Link (UL) coverage


are summarized in Figures 4 and 5 respectively, for 144 kbps . . . -... ............
service. The Pareto optimal solution with the highest capacity Figure 5. Access probability in the initial network.
is represented here, and in the rest of the paper. These results
are obtained utilizing a probe mobile that scans the network . .-.. .... .....
!
surface which is divided into meshes. At the center of each
mesh, UL and DL powers required to establish a
communication are calculated. A mesh is considered as
covered if the required power does not exceed 24 and 36 dBm
in UL and DL respectively. The percentage of surface I
corresponding to the highest four power intervals is presented
in the figures. It is shown that the uncovered area is I
!
considerably reduced by the optimization.
I
Figures 6 and 7 present the probability of accessing the
network for 144 kbps service for indoor daylight penetration
margin, for the initial and optimized networks respectively. . ....... .... . "^.

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

0.5 < Paccn.


< 0.7

0.7 < Pa'cess


< 0.9
82%
< 0.95
0.9 < Poccss,
100 200 300 400 500 600
traffic denand

Figure 9. Percentage of mobiles served as a function of traffic demand for


Figure 7. Legend for P C C ~ S Eprobability
S in Figures 6 and 7 64 khps service.

Results for capacity are shown in Figures 9-11 for 12.2


(voice), M and 144 kbps services. The three figures present the
percentage of mobiles served as a function of the traffrc
demand. Both the Pareto optimal solution with the highest
coverage and the one with the highest capacity are represented.
One can see considerable improvement in capacity for all
services.
Next, the performance of the initial and optimized networks
is considered in terms of the blocking and dropping rates.
These quality indicators are of particular importance for two
reasons: first, they are not utilized by the ACP in the
Traffic dsrnand
optimization process, and second, they can be computed for the
real network by processing measured counters. An F i e r e IO. Percentage of mobiles setved as a function o f traffic demand for
improvement in performance with respect to these indicators 144 kbps service.
illustrates the robustness of the solutions produced by the ACP.
To compute the blocking and dropping rates, the semi-dynamic
simulator Atalante UMTS developed in FTR&D is utilized [7].
In Figure 12 the station with the worst average blocking rate is
considered. The blocking rate as a function of simulated time is
shown for both the initial and optimized networks. A
considerable reduction of the blocking rate can be observed for
the optimized network, with an average value of 10% with
respect to 71% for the initial one.
The average dropping rate calculated over the entire
simulation time for the same station considered in Figure 12
decreases from 32% to 0% for the initial and optimized
networks respectively.
100% Figure 11. Blocking rate as a function of simulated time far the initial (black)
98% and optimized (grey) nehyorks (statim with worst performance).
p 86%
f 94% The impact of the optimization on the global network
performance is considered next. The average blocking rate for
-
$ 92%
each station is presented in a descending order in Figure 13. A
+in~Ual net-& considerable global improvement with respect to the blocking
86% rate indicator is observed. It is noted that the stations have been
+opt"capa
sorted for each network individually, meaning that this Figure
84% does not indicate whether certain stations have seen their
800 1300 1600 2300 2800 performance degraded in spite of the global improvement.
Traffic demand

Figure 8. Percentage of mobiles served as a function oftraffic demand for


12.2 kbps service.
- 121 S. Ben Jamaa, Z. Altman, J.M. Picard B. Fourestie and J. Mourlan,
il
"."........I_. ...................................................................
"Manual and automatic design for UMTS networks,'' vol. IO, no 2,
Mobile Networks and Applications. April 2004.
[3] S . Ben Jamaa, Z. Altman, J.M. Picard, B. Fourestik, Optimisation des
reseaux mobiles utilisanl les Algorithms Genetique, chapler 8 in
Metaheunstiques pour I'optimisation dificile, J. DrCo et SI Editors,
Eyolles, 2003.
[4] D.E. Goldberg, Genetic Algorithms in Search, Optimization and
Machine Learning, Addison-Wesley, New York, 1989.
[5] K. Deb, A. Pratap, S. Aganual, and T. Meyarivan, "A fast and elitist
multiobjective Genetic Algorithm: NSGA-II", IEEE Trans. on
Evolutionary Computltion, vol. 6, pp. 182-197, April 2003.
[6] N. Siniva and K. Deb, "Multiobjective Optimization using
nondominated sorting in genetic algorithms", Evolutionary
figure 12. Average blocking rate for the first 130 stations in decreasing order, Computation, vol. 2, no 3, pp. 221-248, 1994.
for the initial (black) and optimized (prey) networks. ..
171 J.M. Picard. f . Garabedian. Z. Alman and H. Dubreil. '' Dmamic
control of UMTS networks by load target hming", E E E International
The average dropping rate for each station in descending Symp. VTC 2004, Milan, Italy, May 2004.
order is shown in Figure 14. A clear global improvement in the
dropping rate indicator is achieved. Both results for the
blocking and dropping rate illustrate the robustness of the
solution produced by the ACP.
I (1.7, .

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.

You might also like