BSC location in wireless communication network with MSCs and cells fixed

Abstract

This thesis considers a BSC location problem in a wireless communication network, where the locations of MSC and Cells are fixed, and the possible locations of BSCs and traffic arrival rate are also given. In the problem, the three issues of (i) constructing BSCs among possible locations, (ii) connecting BSCs to MSC (iii) connecting each BTSs to BSC are jointly determined to minimize the sum of the average queueing delay cost and the cabling cost and the setup cost of BSC. The proposed problem is formulated as a nonlinear binary integer optimization problem, which is NP-complete. A heuristic solution algorithm based on the Lagrangian relaxation and subgradient optimizations method is developed. To test the performance of the heuristic algorithm, a computational experiment is performed with randomly-generated numerical problems. The results show that the Lagrangian heuristic gives good solutions within a reasonable amount of computational time, and so it may be used effectively for practical problems.