Experiments with a Randomized Algorithm for a 
Frequency Assignment Problem

JANEZ ŽEROVNIK 
Faculty of Mechanical Engineering
University  of Maribor
Smetanova 17, SI-2000 Maribor
and
Department of  Theoretical Computer Science
Institute of Mathematics, Physics and Mechanics
Jadranska 19, SI-1111 Ljubljana
SLOVENIA

Abstract: - The problems of assigning frequencies to transmitters can be naturally modelled by generalizations of graph coloring problems.We start with a randomized graph coloring algorithm of Petford and Welsh and propose a randomized algorithm for minimizing the number of constraints violated when a set of frequencies available is fixed. Experiments on instances of various types relevant to mobile communication networks  are reported.

Key-Words: - frequency assignment problem,  randomized heuristics,  mobile telecommunications. 

1   Introduction
Frequency assignment (or frequency allocation) is one of the key applications in mobile networks engineering. The difficulty of practical problems comes from the fact that an acceptable solution must satisfy many constraints and the set of frequencies available  is limited.

Many versions of the problem  are intractable and therefore heuristics for finding near optimal solutions are sought. Various heuristics were recently used for frequency assignment including simulated annealing [5], genetic algorithms [10], tabu search [3], and others [7]. Many  of these are compared in [8]. Most of the results published in the literature concern the span optimization, probably because strong lower bounds were developed which enable decisions to be made on the optimality of the results (see [1] for an overview of lower bounding techniques). The problem where a fixed spectrum is given and the objective is to minimize the number of violations is less studied, although it seems that it is closer to practical problems. Benchmark datasets of real-like instances are however rare, because most companies keep this information confidental. An exception is the paper [9], where a set of instances was used to compare simulated annealing, tabu search and a genetic algorithm and the dataset is available on the internet. 
 
We develop an algorithm for minimizing the number of constraints violated in a frequency assignment from a  fixed set of available frequencies. The algorithm is based on the graph coloring algorithm of Petford and Welsh [11]. Analogous algorithm for minimizing the span was tested in [15]. It is similar to more well known general optimization techniques such as simulated annealing and generalized Boltzmann machines. The main difference is that here the 'temperature' is fixed, which results in a simpler tuning of the parameter(s). On the other hand, this may be one of the reasons for good performance because it is known that the probability of finding an optimal solution with simulated annealing algorithm is asymptotically worse  that the same probability for local search [6].

The paper is organized as follows: Section 2 introduces the frequency assignment problem while Section 3 presents the  algorithm; Section 4 reports on experiments and Section 5 gives conclusions.

2 The frequency assignment  problem
In this section we  give precise meaning to the frequency assignment problem for which our algorithm was designed. It is  a combinatorial optimization problem which can be naturally defined  using  weighted graphs. We use the usual graph theory terminology, see for example [16].

Throughout  the paper we assume that frequencies are taken from a fixed subset of natural numbers, FN. This covers a usual practical situation where  frequency bands are given but there are also some reserved frequencies which may not be used. These so called forbidden frequencies may exist due to technological or environmental constraints (government regulation, other radio systems…).

Specific constraints may be defined on neighboring pairs of transmitters. Usually, frequency separation constraints exist between geographically close transmitters in the service area. In this case we speak of far-site interference.In general, a constraint associated with an edge can be any set of forbidden differences. We will say that two transmitters are neighbors if there is a possibility of  interference. Furthermore, we will assume that the forbidden differences are of the form {0,1,…,w-1}, i.e. the constraint is that the difference between the assigned frequencies must be at least w. The values of w usually depend on the physical distance  between transmitters.

Another important type of constraints is based on  co-site interference. Namely, if there are more frequencies  needed at the same location, they must be separated at least by co-site difference.

In general, it is possible to define  more  complicated constraints modelling different types of interference which is due to various interference mechanisms such as harmonic constraints, adjacent channel constraints, co-site frequency constraints, intermodulation products and spurious emisions and responses. In this paper we will consider only co-site and far-site interference, because these two represent the most important interference problems to avoid.

We therefore  have  a set of locations (transmitters) with given demands (the numbers of frequencies needed) and given constraints  between pairs of transmitters. This can be modeled as a problem of multicoloring  a graph with constraints.

If  we regard a location with demand d as a clique on d vertices of an expanded graph G, the problem reduces to finding one frequency for each vertex. Edges of G connect pairs of vertices, for which there exists a constraint.

For arbitrary two nodes i and j we call wij the weight  of the edge ij.

A frequency planning function   c: V(G) F  assigns a frequency to every vertex of G.

If c is the frequency planning function, every  constraint can be written as

|c(i) - c(j) |   wij                     

In particular, if i and j correspond to two locations in original graph with possible  interference, wij encodes the constraint that the set of forbidden differences is {0,1,…wij-1}. Similarly, if i and j are vertices of a clique, which was expanded from the same location, and the co-site interference constraint is given by the set of forbidden differences is {0,1,…}, then wij =  +1. 
                                                       
A frequency planning function c is proper, if it violates no constraint. E(c), the cost of c is the number of constraints c violates.

Clearly E(c)0 and E(c)=0 if and only if c is proper.

The frequency assignment problem studied here is

Problem: (MINIMAL COST) FREQUENCY ASSIGNMENT
Input: weighted undirected graph G and a set F 
Task: find an assignment which minimizes the cost E 
 
A closely related problem is the problem of minimizing the span, i.e. minimizing the difference between the largest and the smallest frequency used.

Problem:  MINIMAL SPAN 
Input: weighted undirected graph G and a set F
Task: find a proper assignment which minimizes the span 
 
Note that these problems are clearly at least as hard as the graph coloring problems. (Just take all weights equal to 1 and F ={1,2,…,k} or F=N.)

3   The Algorithm
Petford and Welsh proposed a randomized algorithm for 3-coloring which mimics the behavior of a physical process based on multi-particle system of statistical mechanics called the antivoter model [11]. The algorithm starts with a random initial 3-coloring of the input graph and then applies an iterative process.  In each iteration a vertex creating a conflict is randomly taken uniformly and recolored according to some probability distribution. This distribution favors colors which are less represented in the neighborhood of the chosen vertex. There is a straightforward generalization of this algorithm to k-coloring, which behaves reasonably good on various types of graphs [4,13,18]. 

We use the same main idea, with some natural generalizations. A set of colors is replaced by a  finite subset of natural numbers corresponding to available frequencies. Simple constraints requesting different colors or frequencies at adjacent vertices are generalized to constraints depending on the edge weights and applying to frequencies assigned to  adjacent vertices.
 
The frequency assignment algorithm is

 Algorithm PW(T, Time_limit) 

1. assign available frequencies to nodes of the graph uniformly random
2. while  not stopping condition do 
      select a bad vertex v (randomly) 
      assign a new frequency to v 
 end while 

A bad vertex is selected uniformly random among vertices which are endpoints of some edge which violates a constraint. A new frequency is assigned at random from the set F.

Sampling is done according to the probability  distribution defined as follows:

The probability of frequency iF to be chosen as a new frequency of  the vertex v  is proportional to

exp( - Si /T) =  -S i

where Si  is the number of edges with one endpoint at v and violating the constraint provided frequency of v is set i. T  is a parameter of the algorithm, called temperature for reasons explained later.

The second parameter of the algorithm is the time limit, given as the maximal number of iterations of the while loop. This is at the same time the number of calls to the function which computes a new frequency and also the number of feasible solutions of the problem generated (some of them may be counted more than once).

The stopping condition we choose is: either a proper assignment was found or a time limit was reached. In the later case, the best solution found (with fewest constraints violated) is reported as an  approximate solution.
 
Choosing the optimal temperature and the time limit is in general an open problem. However, very simple tuning which is explained in the section on experiments was enough to obtain very good results on instances tested.

In the rest of the section we give some remarks on the parameters of the algorithm.

In the coloring problem, Si  is simply the number of neighbors of vertex v colored by i. The original algorithm of Petford and Welsh (for coloring) uses probabilities proportional to 4Si , which corresponds to T0.72. Larger values of T result in higher probability of accepting a move which increases the number of bad edges.  With low values of T,  the algorithm behaves very much like iterative improvement.

T is a parameter of the algorithm, which may be called temperature because of the analogy to the temperature of the simulated annealing algorithm and to the temperature of the Boltzmann machine neural network. These analogies follow from the following simple observation. Let us denote the old color of the current vertex by i and the new color by j. The number of bad edges E’ after the move is

E’ = E - Si + Sj 

where E is the number of bad edges before the change. We define E =  E –E’ = Si -Sj. At each step i is fixed and hence Si and E are fixed. Consequently, it is equivalent to define the probability of choosing color j to be proportional to either exp(-Sj/T), exp(E /T) or exp( -E’ /T).

Finally, recall that the number of bad edges is a usual definition of energy function in simulated annealing and Boltzmann machine. Therefore, the  algorithm PW is in close relationship to constant temperature operation of the generalized Boltzmann machine (for details, see [12] and the references there). The major difference is in the 'firing' rule. While in Boltzman machine model all neurons are fired with equal probability, in PW algorithm only bad vertices are activated. The algorithm PW differs from constant temperature simulated annealing in the acceptance criteria for the moves improving the cost function. These are always accepted by simulated annealing and only according to some (high) probability in the present algorithm.

4   Problem instances and results 
We give results of experiments on the set of instances tested in [9], which are available on the internet.

We first did a simple tuning of the parameter T. With relatively small time limit (set to 1000n iterations, where n is the number of vertices of the graph) we run the algorithm on a medium size instance (410 vertices) at temperatures T=0.1,0.2, 0.3,0.4. Since the results were promising around T=0.2, we checked also T=0.15 and T=0.25. In Table 1, min, max and average are respectively the minimal, maximal and the average value of the cost function obtained in 10 runs of the algorithm PW. 

Table 1.

T      	min  	 max   	average    

 0.1       	383   	396  	389.6       
 0.15    	370   	401  	383.9       
 0.2        372   	387  	379.2        
 0.25     	360   	394  	378.7       
 0.3      	379   	404  	386.6      
 0.4       	395   	432  	416.7     
 
We have no formal argument  why to start with these temperatures. We know from experiments that T=0.72, the original temperature of Petford and Welsh was often too high and that some lower temperatures do better in the case of graph coloring [13,14]. There is at least one seemingly  more advanced approach for tuning the temperature.

One could check some values of T  by short runs measuring the ratio between 'up' and 'down' moves. If the temperature is relatively low, the algorithm will behave like iterative improvement and this ratio will be close to 0. On the other hand, if the temperature is too high, the ratio is close to 1. It is therefore possible to get at  least some reasonable starting value for T by bisection. A heuristic for automatic tuning of the temperature is discussed in [14].

Since the temperatures T=0.2 and T=0.25 seemed to be good, we tested the algorithm with these two values on the whole available dataset of [9]. Our results were then compared to the best results obtained in [9] by simulated annealing, a genetic algorithm and tabu search, which were as follows.

Table 2.

                 SA[9]         GA[9]                TS[9]
  n       min    avg.     min  avg.           min   avg.  

282    121   128.5     501    506.9     128   134 
410    367   380.4   1160  1173.0     379   400.8 
450    151   161.4     845    849.0     176   188.0 
490    625   636.1   1828  1834.4     658   678.9
726  1488 1509.8	  3947  3960.8   1535 1602.8  

To make a comparison fair, we have to take into account the number of assignments tested as reported in [9], which corresponds to the number of iterations in our algorithm. GA explored 2e105 assignments for all instances. The  numbers of assignments for the other two problems  were  between 2.7e106  and 2.4e108 for SA and between 1.3e108  and 2.1e108 for TS. SA algorithm therefore explored up to 50 times more configurations and TS always explored approximately 100 times more configurations.

For this reason we defined  the time limit to be 10000n to let the algorithm PW generate  about the same number of assignments as SA and TS. Note that that the number of assignments allowed for GA in [9] was lower, but the quality of the results of GA was also much lower.

The next table gives the results of our final experiment. In the last column we put the best solutions known before this work. They were found by the FASoft software package [2]. (FASoft uses a combination of heuristics including SA, TS and GA.) It is claimed that the wall clock time for the experiment reported in  [2] was the same as in [9]. (The best solutions known are in boldface.)

Table 3.

           PW,T=0.2             PW,T=0.25      FASoft
n         min  max  avg.          min  max  avg.         min

252     19    21     19.700      20    21    20.500          9
282   110  116   113.100    112  119  115.500      114
410   343  366   354.300    347  357  315.600      361
450   147   154  151.100    140  154  145.400      130
490   607   644  625.800    601   640  616.800     580 
726 1465 1568 1515.000 1463 1527 1497.600  1466

Note that the number of configurations visited  for some larger instances was in our experiment much lower than reported in [9].

We conclude that in comparable or less effort (both in terms of time and in terms of configurations generated) our relatively simple algorithm was competititve to the combination of heuristics including simulated annealing, genetic algorithm and tabu search as implemented in [2,9].

Finally, we wish to say that we used very simple tuning of temperature T (and on one graph only). Probably, even better performance could be achieved if T would be tuned with some more effort.

5   Concluding remarks 
 
We tested Petford Welsh type randomized algorithm on frequency assignment problem with fixed set of available frequencies. Namely, in considerably shorter time we obtained comparable results to some popular heuristics including simulated annealing, a genetic algorithm and tabu search. Furthermore, in four out of six cases, the algorithm PW has found the best known solutions of the instances of the dataset [9]. We therefore conclude that the preliminary results are very promising. We intend to do further experiments on real-life instances. 

There are a lot of optimization problems referred to as frequency assignment problems. First, they differ in the level at which they model the interference. Here the simplest example is graph coloring, where all constraints only impose different frequencies at adjacent sites. On the other hand, it is in principle possible to design very complicated constraints modelling different types of interference which are due to various interference mechanisms such as harmonic constraints, adjacent channel constraints, co-site frequency constraints, intermodulation products and spurious emisions and responses. The cost function  to optimize can also  be defined in many ways, the sum of violated constraints used here being only a simple example. In practical problems some constraints are probably more costly if violated than others [17]. In principle, we do not see any problem to adopt the present algorithm to such more general situations.

References:
[1] S.M.Allen, D.H.Smith and  S.Hurley, Lower Bounding Techniques for Frequency Assignment, submitted to Discrete Mathematics.   http://www.cs.cf.ac.uk/User/Steve.Hurley/
[2] S.M.Allen, D.H.Smith, S.Hurley and  S.U.Thiel, Using Lower Bounds  for Minimum Span Frequency Assignment, 2nd International Conference on Metaheuristics MIC97, Sophia-Antipolis, 1997.
[3] D.J.Castelino, S.Hurley and N.M.Stephens, A Tabu Search Algorithm for Frequency Assignment, Annals of Operations Research 63 (1996) 301-319.
[4] B.Chamaret, S.Ubeda and  J.Žerovnik, A Randomized Algorithm for Graph Coloring Applied to Channel Allocation in Mobile Telephone Networks, in Proceedings of the 6th International Conference on Operational Research KOI'96 (T.Hunjak, Lj.Martić, L.Neralić, eds.), 25-30, 1996.
[5] M.Duque-Anton, D.Kunz and B.Ruber, Channel Assignment  for Cellular Radio Using Simulated Annealing, IEEE Transactions on Vehicular Technology vol. 42  14-21 (1993).
[6] A.Ferreira and J.Žerovnik, Bounding the probability of success of stochastic methods for global optimization, Journal of computers & mathematics with applications  25 (1993) 1-8 .
[7] A.I. Giortzis and L.F. Turner, A Mathematical Programming Approach to the Channel Assignement Problem in Radio  Networks, IEEE Vehicular Technology Conf,736-740, Atlanta, USA, 1996. 
[8] S.Hurley, D.H.Smith and S.U.Thiel, FASoft: A Software System for Frequency Assignment, to appear in Radio Science. 
     http://www.cs.cf.ac.uk/User/Steve.Hurley/
[9] S.Hurley, S.U.Thiel and D.H.Smith, A Comparison of Local Search Algorithms for Radio Link  Frequency Assignment Problems, 11th Annual ACM Symposium on Applied computing,  Philadelphia, USA, 1996, 251-257. (a set of benchmark problems at http://www.cs.cf.ac.uk/User/Steve.Hurley/)
[10] F.J. Jaimes-Romero and D. Munoz-Rodriguez, Channel Assignment in Cellular Systems Using Genetic Algorithms, IEEE Vehicular Technology Conf, 741-745, Atlanta, USA, 1996. 
[11] A.Petford and D.Welsh, A Randomised 3-colouring Algorithm, Discrete Mathematics 74  (1989) 253-261 
[12] J.Shawe-Taylor and J.Žerovnik, Boltzmann Machines  with Finite Alphabet, Artificial Neural Networks 2, vol.1., Brighton, U.K.  391-394 (1992).
[13] J.Shawe-Taylor and J.Žerovnik, Analysis of the Mean Field Annealing Algorithm for Graph Colouring, Journal of Artificial Neural Networks   2 (1995)  329-340 .
[14] J.Shawe-Taylor and J.Žerovnik, Adapting temperature  for some randomized local search algorithms, Preprint Series Dept. Math Univ. Ljubljana vol.36 (1998) no. 614.
[15] S.Ubeda and J.Žerovnik,  A Randomized  Algorithm for  a Channel Assignment Problem, Speedup 11 (1997) 14-19.
[16] R.Wilson, Introduction to Graph Theory, third  edition, Longman Scientific and Technical, Harlow 1985. 
[17] D.Youngs, Frequency Assignment for Cellular Radio Networks, in the IMA Conference series (number 60) 'Applications of Combinatorial Mathematics', C. Mitchell ed., (1995), 233 - 241.
[18] J.Žerovnik, A Randomized Algorithm for k-colorability, Discrete Mathematics 131 (1994) 379-393 .