Doi: 10. 1016/S0305-0548(03)00202-8

---

Computers & Operations Research 32 (2005) 59–86
www.elsevier.com/locate/dsw
Cost-optimal topology planning of hierarchical
access networks
Istv(an G(odor
∗
, G(abor Magyar
Ericsson Research, Trac Analysis and Network Performance Laboratory, P.O. Box 107,
H-1300 Budapest 3, Hungary
Abstract
This paper deals with the problem of cost-optimal hierarchical topology planning for telecommunications
access networks. The generalized problem is computationally hard and only its substantially simpli/ed variants
have been studied before. We propose a heuristic algorithm relying on iterative problem decomposition,
clustering methods and local optimization. The main idea of the approach is to combine clustering and local
optimization operators and to apply the combined operators iteratively within the levels of the hierarchy. By an
extensive empirical analysis it is shown that the presented method e3ciently solves the underlying optimization
problem for instances of practical size, furthermore, it is robust to handle 4exibility in the problem statement
and in the cost function.
? 2003 Elsevier Ltd. All rights reserved.
Keywords: Network planning; Topology optimization; Location science; Hierarchical concentrator location; Mobile
telecommunications; UMTS
1. Introduction
This paper deals with cost-optimal topology planning of hierarchical telecommunication access
networks. The main planning task is to aggregate the user tra3c in a multi-level tree-like fashion
by the use of intermediate concentrator nodes in a cost-optimal way. We note that the problem
statement is general, therefore the proposed algorithms can be applied to several related problems
in the areas of facility location, hierarchical location-allocation, etc.
Current communication networks are typically separated into two major parts. One part is the
core network that consists of high-capacity switching equipment interconnected by a mesh of
high-bandwidth links. The other part is the access network that carries tra3c between user
terminals and the core network nodes. The core network interconnects di?erent areas of the access
∗
Corresponding author.
0305-0548/$ - see front matter ? 2003 Elsevier Ltd. All rights reserved.
doi:10.1016/S0305-0548(03)00202-8

---

60
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
network and interfaces towards external networks. The two parts are typically planned and operated
separately. In this paper, we deal with the access network.
Cost-optimal planning of access networks is a critical issue in designing today’s communications
networks, especially in the case of mobile networks (for example, GSM or UMTS, see Section
4
).
The typically smaller link capacities in an access network are more sensitive to improper dimen-
sioning than the capacities of large core network links; precise planning of links is crucial in order
to meet the quality of service requirements. In addition, access network represents a major part of
the total network cost, considering only their sheer size. The size and complexity of mobile access
networks is becoming enormous making manual planning a di3cult and time-consuming task. The
solution obtained by algorithmic optimization is superior to that of manual planning. Quick algo-
rithmic optimization allows the evaluation and comparison of di?erent deployment strategies; this is
not possible in case of manual network planning within the very short timeframes. A very important
requirement of the optimization procedure is technology-neutrality, as technology can change very
rapidly in the telecommunication environment. Cost-based access network optimization algorithms
play a central role in network planning software tools; their quality and e3ciency have an important
in4uence on the usefulness of the whole software package.
Our problem is to plan an access network, which consists of a number of trees. There are several
constraints on these access trees making the problem NP-hard. Therefore, we do not expect to /nd
the globally optimal solution, but we rely on heuristic algorithms. The main idea of our approach is
to combine clustering and local optimization operators and to iterate the combined operators within
the levels of the hierarchy.
The rest of the paper is organized as follows. Section
2
de/nes the optimization problem.
Section
3
brie4y investigates the related work in the /eld. Section
4
presents an application
example from the telecommunications sector; this environment will be used when presenting
computational results. Section
5
describes our algorithms, with the detailed pseudocodes in the
Appendix
A
. Section
6
demonstrates the robustness and e3ciency of our algorithms through an ex-
tensive empirical comparison. Section
7
contains the conclusions and outlines further open questions.
2. Problem denition
2.1. Network model
Fig.
1
gives a simpli/ed illustration of the network model that is used in the case of mobile access
network planning. The access network is modeled by a directed graph and it consists of aggregation
trees that collect the tra3c demands of base station nodes. The aggregation trees have a speci/ed
depth limit and there are certain degree constraints for intermediate concentrator nodes in each tree
level. In each aggregation tree, the tra3c 4ows through special concentrator nodes upwards to the
root node through transmission links. The concentrator nodes are selected from the nodes, therefore
the concentrators have their own tra3c demands as well.
2.2. Input
Let N = {1; : : : ; n} denote the set of nodes. Each input node i ∈ N is associated with trac
T
i
∈ T to be aggregated. Note that the tra3c can be any kind of complex data, we only require

---

I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
61