An adaptive multi-start graph partitioning algorithm for structuring cellular networks

Toril, Matías, Wille, Volker, Molina-Fernández, Iñigo and Walshaw, Chris (2011) An adaptive multi-start graph partitioning algorithm for structuring cellular networks. Journal of Heuristics, 17 (5). pp. 615-635. ISSN 1381-1231 (Print), 1572-9397 (Online) (doi:10.1007/s10732-010-9148-9)

Abstract

In mobile network design, the problem of assigning network elements to controllers when defining network structure can be modeled as a graph partitioning problem. In this paper, a comprehensive analysis of a sophisticated graph partitioning algorithm for grouping base stations into packet control units in a mobile network is presented. The proposed algorithm combines multi-level and adaptive multi-start schemes to obtain high quality solutions efficiently. Performance assessment is carried out on a set of problem instances built from measurements in a live network. Overall results confirm that the proposed algorithm finds solutions better than those obtained by the classical multi-level approaches and much faster than classical multistart approaches. The analysis of the optimization surface shows that the best local minima values follow a Gumbel distribution, which justifies the stagnation of naive multi-start approaches after a few attempts. Likewise, the analysis shows that the best local minima share strong similarities, which is the reason for the superiority of
adaptive multi-start approaches. Finally, a sensitivity analysis shows the best internal parameter settings in the algorithm.

Actions (login required)