Planning UMTS base station location: optimization models with power control and algorithms

Abstract—Classical coverage models, adopted for second-gen-eration cellular systems, are not suited for planning universal mo-bile telecommunication system (UMTS) base station (BS) location because they are only based on signal predictions and do not con-sider the traffic distribution, the signal quality requirements, and the power control (PC) mechanism. In this paper, we propose dis-crete optimization models and algorithms aimed at supporting the decisions in the process of planning where to locate new BSs. These models consider the signal-to-interference ratio as quality measure and capture at different levels of detail the signal quality require-ments and the specific PC mechanism of the wideband CDMA air interface. Given that these UMTS BS location models are nonpoly-nomial (NP)-hard, we propose two randomized greedy procedures and a tabu search algorithm for the uplink (mobile to BS) direction which is the most stringent one from the traffic point of view in the presence of balanced connections such as voice calls. The different models, which take into account installation costs, signal quality and traffic coverage, and the corresponding algorithms, are com-pared on families of small to large-size instances generated by using classical propagation models. Index Terms—Code-division multiple access (CDMA), optimiza-tion algorithms, optimization models, planning, power control (PC), universal mobile telecommunication system (UMTS). I