Open Access Research

Column generation for frequency assignment in slow frequency hopping networks

Arie Koster and Martin Tieves*

Author Affiliations

Lehrstuhl 2 für Mathematik, RWTH, , Aachen, Germany

For all author emails, please log on.

EURASIP Journal on Wireless Communications and Networking 2012, 2012:253  doi:10.1186/1687-1499-2012-253

Published: 14 August 2012

Abstract

This article deals with the frequency assignment problem (FAP) in slow frequency hopping (GSM) networks, a generalization of the classical FAP. Due to symmetry in the solutions, a natural integer linear programming formulation does not yield a good solution procedure. Instead, we decompose the co-channel and adjacent channel interference minimization and develop a two-stage algorithm. The co-channel optimization problem is solved with a column generation model, whereas the second stage is solved by a cutting plane approach. Computational experiments reveal, that although no optimal solutions can be guaranteed, the approach provides promising results, both regarding practical applicability and further research potential.

Keywords:
Slow frequency hopping; Interference minimization; Column generation