Mathematical Programming Models for Third Generation Wireless Network Design

This chapter develops a series of optimization models for third-generation (3G) cellular network design leading up to a comprehensive model including the selection of base stations and mobile telephone switching office (MTSO) locations, and the assignment of mobiles to base stations. The models also consider the design of a backbone network connecting the base stations, MTSOs, and public switched telephone network (PSTN) gateways. These models take as input demand for cellular service in a given planning area, a set of candidate tower and MTSO locations with corresponding costs, costs for provisioning links between the candidate tower and MTSO locations as well as costs for linking the MTSOs to PSTN gateway nodes. Based on these inputs and propagation data for the planning area, the comprehensive model can be used to determine the optimal selection of radio towers, MTSO locations, backbone network topology, and the service capacity of the resulting radio network. For problem instances of practical interest, the model leads to large, difficult integer programs that require special solution techniques. Nevertheless, researchers have reported finding high-quality solutions, in reasonable amounts of CPU time, to problems with hundreds of candidate tower locations supporting tens of thousands of simultaneous cellular phone sessions. This chapter surveys strategies that have been developed to achieve these results.