Toril, Matías, Wille, Volker, Molina-Fernández, Iñigo and Walshaw, Chris ORCID: https://orcid.org/0000-0003-0253-7779 (2010) 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.

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.

Item Type:	Article
Additional Information:	[1] First published in print: 1 October 2011. [2] Published online: 30 October 2010. [3] 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
Pre-2014 Departments:	School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Computing and Information Systems
Related URLs:	Publisher Organisation
Last Modified:	14 Oct 2016 09:11
URI:	http://gala.gre.ac.uk/id/eprint/4254

Actions (login required)

View Item