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)Full text not available from this repository.
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.
|Additional Information:|| First published in print: 1 October 2011.  Published online: 30 October 2010.  Published as: Journal of Heuristics, (2011), Vol. 17, (5), pp 615-635.|
|Uncontrolled Keywords:||mobile network, optimization, graph partitioning, multi-level refinement, adaptive multi-start|
|Subjects:||Q Science > QA Mathematics|
|School / Department / Research Groups:||School of Computing & Mathematical Sciences|
School of Computing & Mathematical Sciences > Department of Computing and Information Systems
|Last Modified:||03 Oct 2013 12:24|
Actions (login required)