Two new algorithms for UMTS access network topology design

Present work introduces two network design algorithms for planning UMTS (Universal Mobile Telecommunication System) access networks. The task is to determine the cost-optimal number and location of the Radio Network Controller nodes and their connections to the Radio Base Stations (RBS) in a tree topology according to a number of planning constraints. First, a global algorithm to this general problem is proposed, which combines a metaheuristic technique with the solution of a specific b-matching problem. It is shown how a relatively complex algorithm can be performed within each step of a metaheuristic method still in reasonable time. Then, another method is introduced that is able to plan single RBS-trees. It can also be applied to make improvements on each tree created by the first algorithm. This approach applies iterative local improvements using branch-and-bound with Lagrangian lower bound. Eventually, it is demonstrated through a number of test cases that these algorithms are able to reduce the total cost of UMTS access networks, also compared to previous results. (C) 2004 Elsevier B.V. All rights reserved.