Dynamic data resolution to improve the tractability of UMTS network planning

Transmission site selection and configuration for cellular networks is in general an NP-hard optimization problem. Consequently efforts to improve tractability are very valuable and meta-heuristic algorithms are now commonly applied in artificial intelligence frameworks and expert systems. The speed of network evaluation is a binding constraint on performance of meta-heuristic techniques. This is particularly challenging for CDMA-based systems because power allocation is required before coverage can be evaluated. The current most efficient heuristic for achieving this requires $O(n^{2}_{\mathit{cell}} \cdot n_{\mathit{stp}})$ time where n cell is the number of cells and n stp is the number of active user locations. In the large-scale scenarios that arise in practice, n stp is large compared to n cell and consequently tractability is significantly impeded by n stp . We introduce a new approach to improve tractability for the network planning problem. This concerns changing the resolution of the problem scenario by creating virtual entities which combine spatial traffic requirements, thus reducing the number of n stp that require evaluation. By solving a linear programming formulation of the planning problem exactly (for small instances) and using a heuristic (for large instances), we examine in detail the change in quality of solution that this method induces. The results show that only a marginal reduction in quality of network evaluation is observed, while computational tractability is improved. Copyright Springer Science+Business Media, LLC 2012