New Benders' Decomposition Approaches for W-CDMA Telecommunication Network Design

Benders Decomposition;Mathematical Programming;Analytic Center Cutting Plane Method;Telecommunication Network Planning;Management Sciences

Naoum-Sawaya, Joe

University of Waterloo

关键词: Benders Decomposition;    Mathematical Programming;    Analytic Center Cutting Plane Method;    Telecommunication Network Planning;    Management Sciences;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/2769/1/joe_naoum_sawaya_thesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Network planning is an essential phase in successfully operating state-of-the-art telecommunication systems. It helps carriers increase revenues by deploying the right technologies in a cost effective manner. More importantly, through the network planning phase, carriers determine the capital needed to build the network as well as the competitive pricing for the offered services. Through this phase, radio tower locations are selected from a pool of candidate locations so as to maximize the net revenue acquired from servicing a number of subscribers. In the Universal Mobile Telecommunication System (UMTS) which is based on the Wideband Code Division Multiple Access scheme (W-CDMA), the coverage area of each tower, called a cell, is not only affected by the signal;;s attenuation but is also affected by the assignment of the users to the towers. As the number of users in the system increases, interference levels increase and cell sizes decrease. This complicates the network planning problem since the capacity and coverage problems cannot be solved separately.To identify the optimal base station locations, traffic intensity and potential locations are determined in advance, then locations of base stations are chosen so as to satisfy minimum geographical coverage and minimum quality of service levels imposed by licensing agencies. This is implemented through two types of power control mechanisms. The power based power control mechanism, which is often discussed in literature, controls the power of the transmitted signal so that the power at the receiver exceeds a given threshold. On the other hand, the signal-to-interference ratio (SIR) based power control mechanism controls the power of the transmitted signal so that the ratio of the power of the received signal over the power of the interfering signals exceeds a given threshold. Solving the SIR based UMTS/W-CDMA network planning problem helps network providers in designing efficient and cost effective network infrastructure. In contrast to the power based UMTS/W-CDMA network planning problem, the solution of the SIR based model results in higher profits. In SIR based models, the power of the transmitted signals is decreased which lowers the interference and therefore increases the capacity of the overall network. Even though the SIR based power control mechanism is more efficient than the power based power control mechanism, it has a more complex implementation which has gained less attention in the network planning literature. In this thesis, a non-linear mixed integer problem that models the SIR based power control system is presented. The non-linear constraints are reformulated using linear expressions and the problem is exactly solved using a Benders decomposition approach. To overcome the computational difficulties faced by Benders decomposition, two novel extensions are presented. The first extension uses the analytic center cutting plane method for the Benders master problem, in an attempt to reduce the number of times the integer Benders master problem is solved. Additionally, we describe a heuristic that uses the analytic center properties to find feasible solutions for mixed integer problems. The second extension introduces a combinatorial Benders decomposition algorithm. This algorithm may be used for solving mixed integer problems with binary variables. In contrast to the classical Benders decomposition algorithm where the master problem is a mixed integer problem and the subproblem is a linear problem, this algorithm decomposes the problem into a mixed integer master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition, leading to a nested Benders algorithm. Valid cuts are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem to enhance the performance of the algorithm.It was found that valid cuts generated using the analytic centercutting plane method reduce the number of times the integerBenders master problem is solved and therefore reduce thecomputational time. It was also found that the combinatorialBenders reduces the complexity of the integermaster problem by reducing the number of integer variables in it.The valid cuts generated within the nested Benders algorithmproved to be beneficial in reducing the number of times thecombinatorial Benders master problem is solved and in reducing thecomputational time that the overall algorithm takes. Over 110instances of the UMTS/W-CDMA network planning problem ranging from20 demand points and 10 base stations to 140 demand points and 30base stations are solved to optimality.