This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Kalvenes, J. Articles by Olinick, E. Search for Related Content

Base Station Location and Service Assignments in W–CDMA Networks

Edwin L. Cox School of Business, Southern Methodist University, Dallas, Texas 75275-0333, USA
Department of Engineering Management, Information, and Systems, School of Engineering, Southern Methodist University, Dallas, Texas 75275-0123, USA
Department of Engineering Management, Information, and Systems, School of Engineering, Southern Methodist University, Dallas, Texas 75275-0123, USA
kalvenes{at}smu.edu
jlk{at}engr.smu.edu
olinick{at}engr.smu.edu

Designing a wideband code division multiple access (W–CDMA) network is a complicated task requiring the selection of sites for radio towers, analysis of customer demand, and assurance of service quality in terms of signal-to-interference ratio requirements. This investigation presents a net-revenue maximization model that can help a network planner with the selection of tower sites and the calculation of service capacity. The integer programming model takes as input a set of candidate tower locations with corresponding costs, a number of customer locations with corresponding demand for traffic, and the revenue potential for each unit of capacity allocated to each demand point. Based on these data, the model can be used to determine the selection of radio towers and the service capacity of the resulting radio network. The basic model is a large integer program and requires a special algorithm for practical solution. Our algorithm uses a priority branching scheme, an optimization-gap tolerance between 1% and 10%, and two sets of global valid inequalities that tighten the upper bounds obtained from the linear programming relaxation. The algorithm has been implemented in software for the AMPL/CPLEX system and an empirical investigation has been conducted. Using over 300 problem instances with up to 40 towers and 250 service locations, various combinations of algorithm settings have been evaluated. Using the recommended setting results in a design tool that generally runs in under 20 minutes on a 667 MHz AlphaStation.

Key words: communications; programming; integer; applications
History: received October 2002; revised November 2004; accepted December 2004.