In cellular communications networks, cells use beacon frequencies to ensure the smooth operation of the network, for example in handling call handovers from one cell to another. These frequencies are assigned according to a frequency plan, which is updated from time to time, in response to evolving network requirements. The migration from one frequency plan to a new one proceeds in stages, governed by the network's base station controllers. Existing methods result in periods of reduced network availability or performance during the reassignment process.

The problem posed to the Study Group was to develop a dynamic reassignment algorithm for implementing a new frequency plan so that there is little or no disruption of the network's performance during the transition. This problem was naturally formulated in terms of graph colouring and an effective algorithm was developed based on a straightforward approach of search and random colouring.

Problem presented by
Simon Brusch, Motorola Research

Study Group contributors
John Billingham (University of Nottingham)
Tim Gould (Lancaster University)
Sam Halliday (Heriot-Watt University)
Robert Leese (Smith Institute)
Colin Please (University of Southampton)
Ida Pu (Goldsmiths College London)
Hannu Rajaniemi (University of Edinburgh)
Eddie Wilson (University of Bristol)
Daniel Winterstein (University of Edinburgh)