UMTS is a highly advanced technology, far more complex than anything deployed in the telecommunication mass market before. The technology is also expensive for operators; in addition to spectrum license fees (the UMTS spectrum auction in Germany in 2000 generated close to 50 billion euros), operators incur large costs for building the necessary infrastructure. Radio network planning [6, 10] is required to control these costs and provide customers with high-quality services.

The key decisions network planners have to make are the selection of base station locations, the number of sectors to install and where to point the main lobe of each antenna. The objective of radio network planning is to provide maximum wireless coverage and capacity at minimal cost. Planning for UMTS differs substantially from previous wireless technologies, in particular GSM. For example, capacity planning is not just a matter of installing equipment (called hard capacity) as needed, but antenna configurations influence capacity due to interference with other cells yielding what is called soft capacity.

Deployment of UMTS started around 2002. The initial phase was coverage-driven, because the spectrum regulations often required operators to provide coverage for a prescribed fraction of the population at given times. Germany, for example, asked for 50 percent coverage of the population by the beginning of 2005. In the aftermath of the New-Economy bubble, operators aimed at a slow start. With growing customer demand, network capacity now comes into focus. At the beginning of UMTS deployment, it was basically unknown how to address interference-limited capacity planning appropriately. Only in the last two to three years has UMTS capacity planning come within reach of mathematical optimization methods.

In this article, we describe some of the modeling and solution steps and outline essential features of UMTS and their effects on planning. Next, we present the cornerstone of all (static) system models — the carrier-to-interference ratio equation. After that we derive a system of related interference-coupling equations that describe system performance at the cell level. Finally, we explain how local search algorithms can utilize this coupling system successfully to produce high-quality coverage and capacity in real-life networks. About 60 percent of the original GSM sites produce the same coverage with UMTS, and capacity improvements close to 15 percent can be achieved in comparison to a regular network layout.

UMTS Features and Their Effects


UMTS contains an array of features to efficiently use the scarce radio spectrum. Good planning requires a basic understanding of the technical details. We describe the main features and their effects on planning. Our focus lies on the most common UMTS radio interface variant, Wideband Code Division Multiple Access (W-CDMA). (Note: More specifically, we consider systems that apply Frequency Domain Division (FDD) to separate the downlink (base station to mobile) from the uplink (reverse direction) communications. The presentation in the following applies to both directions separately.)

W-CDMA relies on code division for concurrent medium access of different connections. Links may transmit on the entire available frequency band all the time, instead of using separate time and/or frequency slots as in GSM. Connections are separated by distinct codes; each transmission has a (locally) unique sequence of code symbols that stands for a given data symbol. A superposition of many signals arrives at the receiver. By applying the sender's code, an individual message can be recovered. The advantages of code division are that, unlike for GSM, no synchronization between different transmitters and no frequency planning are needed.

Figure 1: UMTS radio networks and modeling; (a) snapshot of users and sources of interference; (b) the interference-coupling matrix captures all essential information on network design and user properties. The colored connections between antennas indicate the off-diagonal matrix elements corresponding to the user configuration and network design depicted in (a).

Closely related to code division is spreading. Several code symbols are transmitted per user data symbol. The bandwidth of the radio signal is therefore larger than what is needed for direct transmission. The spreading improves resilience of communication to interference.

Interference poses a problem for decoding the signal; only if the signal quality (i.e., the ratio of the received signal over interference and noise) is high enough, can the user data be reliably recovered at the receiver. While increasing the transmit power will improve signal quality for the link in question, this adds to interference on all other links.

Power control in W-CDMA aims at an equilibrium of transmit powers with as little interference as possible. The principle is illustrated in Figure 2. Exactly 1,500 times per second, the receiver compares the current signal quality to a target value and asks the transmitter to update its power. The quality of the received signal is thus approximately held constant. In parallel, the receiver monitors the resulting decoding error rate and adapts the quality target periodically such as to operate at the maximum tolerable error rate.

Figure 2: Power control on a UMTS over one second: according to the current channel state (top graph) and the current level of interference (assumed constant), the transmit power is adjusted (middle graph) such as to achieve an approximately constant signal quality at the receiver (bottom graph).

The combination of features guarantees an efficient use of the radio spectrum; more users than ever can be served simultaneously. But the features involve effects that did not matter in network planning before. Cell breathing is a case in point; according to the level of interference at the receiver, the maximum distance that can be overcome with a limited power budget varies. The coverage area of a cell thus depends on the load.

Furthermore, soft capacity is an issue for urban planning scenarios, where coverage is not a problem. Figure 3 illustrates the soft capacity phenomenon: the amount of traffic that a cell can serve varies. If more interference is present, the cell's power budget is exhausted earlier. For example, interference is higher if users are close to the cell border; also, traffic in neighboring cells adds to interference. Capacity planning thus has to consider the number, properties and positions of users in a cell and also in the neighboring cells. The power levels resulting from the power control mechanism need to be calculated in order to determine if there is sufficient capacity for serving a given amount of traffic.

Figure 3: Soft capacity: even if the cell's resources suffice to serve a set of users (a) if all are located at the cell center, capacity may be exceeded if (b) the same users are located at the cell border, or (c) if there is too much interference from users in neighboring cells.

Static Model: Carrier to Interference Ratio Equation


Network planning commonly relies on static models [12]. Instead of considering the dynamic influences such as short-term channel variation and user mobility, snapshots of users' demand in time are evaluated. A schematic view of a user snapshot served by a radio network is depicted in Figure 1a. Two crucial assumptions for static modeling are: first, the average interference can be considered constant over short time spans; second, power control adjusts the signal quality at the receiver to the minimum feasible value that ensures proper decoding at all times. The bottom graph in Figure 2 is thus approximated by a straight horizontal line. This is called perfect power control.

The assumption of constant average signal quality is captured by the carrier-to-interference equation illustrated in Figure 4. (Note: We state the CIR equation for the uplink only, as it is simpler than that for the downlink. Moreover, some technicalities are omitted for the sake of a smoother presentation. A full account of the model can, for example, be found in [10]) An equation is formulated for each radio link. The fraction at the left-hand side is the link's carrier-to-interference ratio (CIR). The numerator contains the received signal power, which is the product of the transmit power and the attenuation factor. The denominator is the total strength of all other interfering signals and noise. Again, the transmitted powers are multiplied by the respective attenuation factors.

Figure 4: Static model: a system of CIR equations is used to calculate transmit powers and check capacity. The identification of sensible coefficients requires the collaboration with different fields in the engineering sciences.

In addition, an (experimentally determined) activity factor is introduced, indicating the fraction of the time a link is actually active. As an example, a link carrying voice telephony is typically active for 67 percent of the time in one direction (including protocol overhead). An average interference is thus considered. Because perfect power control is assumed, the CIR is equal to the connection-specific constant on the right hand side of the equation, the CIR target.

The set of all CIR equalities constitutes a linear equation system, whose solutions represent the equilibrium of transmit powers toward which power control drifts. In order to assess whether the network provides sufficient capacity to serve a given snapshot, we have to determine whether the CIR equation system admits a solution. Furthermore, the solution has to be positive in all components and within the cell power limits.

The concept of systems of CIR equations is simple to grasp, but using it in practice poses some challenges. For supplying the model with appropriate coefficient values, mathematicians rely upon the results of different disciplines in the engineering sciences. The number of users, their services and their positions in a snapshot is determined by traffic modeling. Traffic modeling usually identifies a stochastic distribution of usage intensities in the busy hour (the hour of the day during which the network is maximally loaded); an example traffic intensity function is depicted in Figure 5a. The user-specific parameters (activity factor and CIR target) are selected according to service and link models. Live measurements or detailed link-level simulations determine the CIR targets for the different services.

Figure 5: Elements of planning data: (a) average normalized traffic intensity in Berlin, (b) received signal strength and cell areas.

The attenuation factors between antennas and users are predicted by radio wave propagation models [11]. This is difficult in urban areas, because signals are reflected and diffracted by several obstacles and reach the receiver on multiple paths. Radio wave propagation prediction uses terrain height data and, ideally, building data. Also the influence of the antenna needs to be considered. Figure 5b illustrates a use of propagation data; for the indicated network configuration, the strongest received signal at all points in the planning area and the resulting cell structure are indicated.

There are two computational difficulties with using the static model for network planning. First, planning for a single snapshot is pointless. Many snapshots should be considered. Second, solving the CIR equation system is numerically difficult as the quantities involved often span a range of 10-13 orders of magnitude.

Distilling the Essence: Cell Coupling


The difficulties with the CIR equation system outlined above can be overcome. There is a mathematical model of the entire system that pinpoints the interference coupling among cells in a strikingly simple fashion. (Note: We focus on the uplink here. The same ideas apply to the downlink.) The model was first conceived as a technique for reducing the dimension of the CIR equation system from the number of users (typically several thousands) to the number of cells (typically a few hundred) [7]. To this end, cell power variables summing up (in the uplink) all average received powers at the base station antennas are introduced. By eliminating the link power variables from the system, we obtain an equation system describing the relation of the different cell powers:

The vector of average cell powers is here denoted by p. The coefficients of the cell power variables after the transformation form a nonnegative square matrix, the interference-coupling matrix, denoted by C. The interference-coupling matrix is constructed for a specific user configuration and network design. (See [10, 3] for details). For the user configuration and network design depicted in Figure 1a, the line color intensity in Figure 1b indicates the magnitude of the corresponding off-diagonal elements representing the cell coupling.

Originally, the dimension reduction technique provided merely a computational speedup for solving the CIR equation system in a two-step approach. First, the cell powers are computed as the solution of the coupling equation system. This is easy because the system is small and well-conditioned. Second, the individual link powers are derived.

Beyond the alleviation of computational problems, however, the coupling equation system enables a new view on the system at cell level. After all, individual link powers in a snapshot are of little interest for network planning. The cell powers are essential for capacity evaluation, and they can be computed without (explicitly) considering individual users. The coupling equation system thus allows one to understand the properties of a network through the coupling matrix alone. We next outline two approaches to UMTS network modeling and performance evaluation that rely on this principle.

The expected network performance for a random model of snapshots is usually more interesting than the network's performance on a single snapshot. The expected network performance can be estimated by solving the coupling equation with the expected coupling matrix. This corresponds to considering an "average snapshot" [1]; for typical random models, the corresponding calculations are straightforward. It can be shown empirically [3] that the expected coupling matrix is a good representative for the network design and its performance.

The coupling model also allows a top-level view on congestion control, the reaction of the system to overload situations. Congestion control can be represented at cell level by scaling the matrix columns corresponding to overloaded cells (the rows for the downlink) such that all cell powers remain within the acceptable limits. This can be formally represented by a coupling system with complementarity constraints [2].

The simplifications embodied in the model are not necessarily justified for arbitrary input data. For planning purposes and for realistic data as input, however, the simple model describes network capacity to a satisfactory degree: For typical signal variations over time and user mobility, the transition from dynamic to static models is feasible, because the dynamic mechanisms can be represented by short-term average with reasonable accuracy [5]. For typical service definitions, the aggregation of fine-granular users in the coupling matrix is feasible. Aggregating their individual properties does not entail too much loss of information. For typical random distributions of users, the expected coupling matrix is a valid first-order approximation, which allows to discriminate between good and bad network configurations, even though performance cannot be assessed to the last detail [3].

Unleashing optimization


On the basis of the compact cell-coupling model, optimization methods can be applied to UMTS planning. We outline developments in three areas: coverage and extension planning, capacity optimization and the derivation of bounds on optimization results.

In coverage optimization, arguably the most important decision is the selection of base station sites and thus the location of antennas. Choices for sites are limited; operators have to make do with whatever sites they can acquire or have built or rented already. Coverage optimization can be cast into a mathematical set-covering problem. The ground set to be covered in the planning area is typically "discrete-ized" into "pixels." Each potential base station site gives rise to sets providing coverage to a collection of pixels. The goal is to maximize coverage or, alternatively, minimize the cost of achieving a specified coverage target. Even for large instances with several hundred sites and dozens of potential configurations per site, such problems can be solved (close) to optimality using commercial mixed integer linear programming solvers.

In capacity planning, the predicted demand for services should be satisfied. Optimizing antenna directions is a key means to control interference coupling and thus to increase capacity. In the expected-coupling setting, this problem can be mapped to designing a network whose expected coupling matrix produces the lowest total transmit power estimates. The problem is inherently nonlinear, as the capacity required for serving an incremental amount of traffic in a cell increases with the amount of presently served traffic. The above methods based on the coupling-matrix, however, can evaluate a city-wide network within seconds. This is the basis for successful search methods.

The solution quality can be assessed with lower bounds. Separate bounds can be conceived for the interference coupling among cells (inter-cell interference) and interference generated within the cells (intra-cell interference). Inter-cell interference is perfectly reduced if cells do not overlap whatsoever (Figure 6a); intra-cell interference, on the other hand, is minimum if all cells have equal load (Figure 6b). The combination of both assumptions is perfectly balanced cells with no overlap; this scenario allows deducing a true lower bound (Figure 6c). The bound is typically poor, because overlap between cells is inevitable with seamless coverage. A more instructive reference value is derived if the minimum possible amount of overlap is taken into account in the regular scenario (Figure 6d). The latter value is expressed in the "gap" column in Table 1. For details on lower bounds, see [3].

Figure 6: Deriving quality certificates for capacity optimization: (a) interference among different cells is minimal if they do not overlap; (b) total interference generated within cells is lowest if cells are of equal size and load is evenly distributed; (c) the combination of both assumptions produces a lower bound; and (d) taking into account the technically least possible overlap in the idealized configuration produces a more realistic point of reference.

# cells gap to reference (load) performance improvement   area gsm umts avg. cell load blocking ratio capacity Berlin 56 km2 204 108 12.0% -16.2% -4.1 pp +13.5% Lisbon 21 km2 164 96 8.4% -10.0% -1.5 pp +9.7% Turin 274 km2 335 335 13.0% -14.4% -0.6 pp +8.4% Vienna 437 km2 628 361 0.1% -3.7% -0.5 pp +6.8% Table 1: Effect of site reduction and configuration fine-tuning for capacity maximization in four different, realistic scenarios. The performance improvement is determined by detailed Monte Carlo simulation.

In practical experiments, local search with 1-opt to 4-opt steps has been applied to the four large, realistic scenarios listed in Table 1. (Note: data sources: [8], [9].) The objective has been the minimization of overall transmit power. Prior to this capacity optimization step, a minimum number of sites and cells from a legacy GSM network were selected while maintaining coverage. In the case of Berlin, for example, 108 out of the 204 cells used in GSM sufficed to provide the coverage. The optimization with search methods managed to reduce the objective to only 12 percent more than the reference value described above. The network performance as determined by detailed simulation is significantly improved by optimization; the average cell load, which was primarily targeted in optimization, decreases by 16.2 percent. Also the blocking ratio (the percentage of users that are rejected on the average due to overload) decreases, in this case by 4.1 percent. All in all, 13.5 percent more capacity is provided on average. (Note: The average cell capacity estimation is based on the average other-to-own-cell-interference ratio, see [4].) The improvement by optimization is illustrated for the Lisbon scenario in Figure 7. In summary, the optimization success justifies the abstractions and simplifications made in modeling. For details, again, see [3].

Figure 7: Effect of optimization in the Lisbon scenario: cell areas and average transmit power (a) before and (b) after configuration fine-tuning for capacity maximization.

Summing Up


Real-world infrastructure planning is utterly complex. With a hands-on and interdisciplinary approach, however, challenges from practice can be made amenable to the toolbox of operations research and optimization. Following the guidelines described and exemplified for wireless technology here, mathematicians can expand the application areas of modern mathematics and create significant impact.

The example of UMTS radio network planning shows how the overall complexity can be reduced into a simple model capturing the essentials. Instrumental to this approach is the focus on typical real-world instances that guide the modeling and help to distinguish between phenomena that need to be considered and those that need not. For the capacity optimization of UMTS, a compact system model, various optimization models and optimization methods have been developed along these lines. From a mathematician's point of view, on the one hand, the optimization problems are still not satisfactorily addressed. Mathematical methods producing proven optimal solutions (or close to that) are still on the wish list. From a practitioner's point of view, on the other hand, the tools are well-developed and suited for daily business. The UMTS system model has a much wider scope. The concise description of interference coupling among cells is common to interference-limited radio interface with coupling among cells. Any spectrum-efficient future system is of that sort as, for example, the OFDMA scheme used in WiMAX. Thus, the approaches sketched here can be applied to the WiMAX planning. Quite an appealing perspective for carriers, who develop plans for deploying nation-wide WiMAX infrastructure.

Authors' note: This article highlights achievements in UMTS telecommunication network planning. We view this case as an example typical for modern infrastructure planning. New technologies, such as third-generation (3G) wireless radio systems, pose challenges that cannot be mastered by "traditional methodology." Besides operations research expertise, in-depth technical understanding and close interactions with engineers and practitioners are mandatory. Highly detailed solution approaches, however, usually result in optimization tasks that are way out of reach. To be able to apply optimization techniques, layers of system complexity have to be appropriately condensed to compact mathematical descriptions. In the end, the cooperative efforts may produce, as in the case presented here, results that initially seemed out of reach for mathematical approaches.

1. Z. Dziong, M. Krishnan, S. Kumar and S. Nanda, 1999, "Statistical Snap-shot for Multi-Cell CDMA System Capacity Analysis," Proceedings of IEEE WCNC, Vol. 3, pp. 1,234­1,237.
2. Andreas Eisenblatter, Hans-Florian Geerdes and Normen Rochau, 2005, "Analytical Approximate Load Control in W-CDMA Radio Networks," Proceedings of IEEE VTC 2005 Fall (Dallas, Texas).
3. Hans-Florian Geerdes, 2008, "UMTS Radio Network Planning: Mastering Cell Coupling for Capacity Optimization," Ph.D. thesis, TU Berlin.
4. Hans-Florian Geerdes and Andreas Eisenblatter, 2007, "Reconciling Theory and Practice: A Revised Pole Equation for W-CDMA Cell Powers," Proceedings of MSWIM'07 (Chania, Greece).
5. J. Laiho, A. Wacker, T. Novosad and A. Hamalainen, 2001, "Verification of W-CDMA Radio Network Planning Prediction Methods with Fully Dynamic Network Simulator," IEEE VTC Fall 2001.
6. Jaana Laiho, Achim Wacker and Tomas Novosad (eds.), 2002, "Radio Network Planning and Optimisation for UMTS," John Wiley & Sons.
7. Luis Mendo and Jose Marða Hernando, 2001, "On Dimension Reduction for the Power Control Problem," IEEE Transactions on Communications, Vol. 49, No. 2, pp. 243­248.
8. Momentum Project: "Momentum Public UMTS Planning Scenarios," 2003, avaliable online at http://momentum.zib.de/data.php, IST-2000-28088.
9. Antonella Munna, Silvia Ruiz Boque and Roberto Verdone, 2004, "Morans: Mobile Radio Access Network Reference Scenarios," Proceedings of WPMC'04 (Abano Terme, Italy).
10. Maciej Nawrocki, Hamid Aghvami and Mischa Dohler (eds.), 2006, "Understanding UMTS Radio Network Modelling, Planning and Automated Optimisation: Theory and Practice," John Wiley & Sons, Ltd.
11. S. R. Saunders, 1999, "Antennas and Propagation for Wireless Communication Systems," John Wiley & Sons, New York, N.Y.
12. A. Wacker, J. Laiho-Steffens, K. Sipila and M. Jasberg, 1999, "Static Simulator for Studying W-CDMA Radio Network Planning Issues," Proceedings of VTC-Spring 1999, Vol. 3, pp. 2,436­2,440.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2008 by the Institute for Operations Research and the Management Sciences. All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com


Web Site © Copyright 2008 by Lionheart Publishing, Inc. All rights reserved.