Wireless Networks 11, 489–496, 2005C2005 Springer Science + Business Media, Inc. Manufactured in The Netherlands.On the Design Problem of Cellular Wireless NetworksSTEVEN CHAMBERLAND and SAMUEL PIERREComputer Engineering Department,´Ecole Polytechnique de Montr´eal, C.P. 6079, Succ. Centre-Ville, Montr´eal (Qu´ebec), Canada H3C 3A7Abstract. In this paper, we deal with the problem of how to design cellular networks in a cost-effective way. We first propose an optimizationmodel that deals with selecting the location of the base station controllers (BSCs) and mobile service switching centers (MSCs), selectingtheir types, designing the network topology and selecting the link types. In order to find a “good” solution, we propose a tabu search algorithm.Numerical results show that the tabu search algorithm produces solutions close to a proposed lower bound.Keywords: cellular networks, topological design, BSC and MSC location, capacity planning, tabu search1. IntroductionIn a typical cellular network, the area of coverage is geograph-ically divided into cells and the network topology is hierarchi-cally organized in order to reduce costs. Each cell is equippedwith a base transceiver station (BTS) that contains the radiotransceivers providing the radio interface with mobile stations.One or more BTSs are connected to a base station controller(BSC) that provides a number of functions related to resourceand mobility management as well as operation and mainte-nance for the overall radio network. One or more BSCs areconnected to a mobile switching center (MSC) or switch thatcontrol call setup, call routing, while performing many otherfunctions provided by a conventional communications switch.An MSC can be connected to other networks such as the pub-lic switched telephone network (PSTN), in order to provide alarger coverage.Cellular network operators dedicate an important propor-tion of their budget to acquire, install and maintain the facili-ties (BTS, BSC, MSC, etc.) that carry traffic from cell sites toswitches and other facilities. These facilities are often leasedfrom local exchangecarriers. The pressure to reduce costs addsnew urgency to the search for optimized networks which canminimize the cost of required facilities while satisfying a setof predetermined constraints.Typically, the design of cellular networks requires:rthe analysis of radio-wave propagation and/or the fieldtopology to identify a set of possible base stations (BTS,BSC) locations;rthe selection of a least-cost subset of locations (networknodes) as hubs where the traffic is to be aggregated andswitched;rthe assignment of each cell to a switch (MSC) while tak-ing into account a certain number of constraints includingcapacity constraints, routing-diversity to assure reliability,handoffs frequency, and so on;rthe selection of the type of links between the nodes ornetwork elements (BTS, BSC, MSC).Many aspects of the overall design problem refer to anumber of well-known operational research problems, suchas graph partitioning [9,10] or p-fixed hubs location prob-lem [13,14]. This kind of problems is NP-hard, thus exact al-gorithms are practically inappropriate for moderate and large-size cellular networks. As a result, heuristic approaches havebeen largely used for solving these aspects of the design prob-lem [1–3,5,10–12]. In particular, Cox and Sanchez [3] studiedthe whole design process and used a tabu search metaheuris-tic, with embedded knapsack and network flow subproblems todesign a least-cost telecommunications networks to carry cellsite traffic to wireless switches while meeting survivability, ca-pacity, and technical compatibility constraints. In this context,each optimization problem is solved while accounting for itsimpacts on the other ones. Merchant and Sengupta [10] stud-ied only the assignment problem. Their algorithm starts froman initial solution, which they attempt to improve through aseries of greedy moves, while avoiding to be stranded in alocal minimum. The moves used to escape a local minimumexplore only a very limited set of options. These moves de-pend on the initial solution and does not necessarily lead toa good final solution. Other heuristics, strongly inspired byMerchant and Sengupta [10], were proposed by Bhattacharjeeet al. [2]. These heuristics are based on the formation of cellsclusters related to the same switch. The cell where the switchresides is the root of the cluster, then each cluster is extendedby judiciously adding other cells. Several versions of the al-gorithm were proposed. In general, these algorithms improvethe results of Merchant and Sengupta, but remains neverthelessineffective for designing large-size cellular networks.In this paper, we are interested in a global approach to thecellular network design problem. The proposed problem dealswith jointlyrselecting the location of the BSCs and MSCs;rselecting the BSC and MSC types;rdesigning the network topology;rselecting the link types.490 CHAMBERLAND AND PIERREThis global problem has not been considered to date in theliterature as well as the selection subproblem of the BSC andMSC types.The paper is organized as follows. In Section 2, we presenta model for the design problem of cellular networks. In Sec-tion 3, we present a tabu search algorithm. Numerical resultsare presented in Section 4. Conclusions and directions for fur-ther research are discussed in Section 5.2. The design problem of cellular networksIn this section, we propose a model for the design of the net-work subsystem of cellular networks. This model is developedfor the second generation of cellular networks using, for in-stance, GSM (Global System for Mobile communications),CDMA (Code Division Multiple Access) or TDMA (TimeDivision Multiple Access) systems [15]. However, it can alsobe used for the design of third generation networks using, forinstance, WCDMA (Wideband CDMA) or CDMA2000 sys-tems [15], if a tree-topology architecture is selected for thenetwork subsystem.2.1. Problem formulationFor the design problem of cellular networks, the followinginformation is considered known:rthe location of the BTSs and their types;rthe traffic (in erlang) between the BTSs and from/to thepublic network;rthe location of potential sites to install the BSCs;rthe location of potential sites to install the MSCs;rthe different types of BSCs, their costs and capacities;rthe different types of MSCs, their costs and capacities;rthe installation cost of a given type