Base station location and channel allocation problems in cellular network design

In an increasingly competitive commercial environment, cellular wireless network providers are under enormous pressure to ensure that informed decisions are made with respect to the design of their networks.; In Section A, we address the problem of allocating an additional set of cell towers to an existing cellular network-this is labeled as the additional cell tower location problem. The goal of the problem is to maximize the completion probability of a randomly placed call. The objective function, which is the call completion probability of a randomly placed call, is highly nonlinear. We develop numerical examples to illustrate properties of the model and to gain insight into its behavior, and then apply the model to a sample case study in a rural section of Erie County, New York, using real time cell phone signal strength data.; We introduce two cases of this location problem. One is the discrete version where the call completion probability has to be maximized over a finite set of discrete points. The other is the version where it has to be maximized over a continuous surface. We solve the discrete version using Simulated Annealing (SA) and obtain very impressive results. For the continuous version, we develop a Geometric Search (GS) heuristic which is based on the output structure of several simple problems. This heuristic performs remarkably well giving optimal solutions in all the instances tested. Finally we show that for the continuous version, SA is not applicable by comparing the results obtained by GS and SA for certain problem instances.; Section B deals with an extended version of the model developed by Akella et al. (2005). In that paper, a unified model was developed that integrated the base station location and frequency channel assignment problems. In this dissertation, we will revisit this problem from a more practical perspective. We address several aspects of the cellular network planning problem, improving on the drawbacks of the previous model. We call this the Integrated Network Planning Tool (INPT) model. (Abstract shortened by UMI.)...